Constrained Heuristic Search

Abstract

We propose a model of problem solving that provides both structure and focus to search. The model achieves this by combining constraint satisfaction with heuristic search. We introduce the concepts of topology and texture to characterize problem structure and areas to focus attention respectively. The resulting model reduces search complexity and provides a more principled explanation of the nature and power of heuristics in problem solving. We demonstrate the model of Constrained Heuristic Search in two domains: spatial planning and factory scheduling. In the former we demonstrate significant reductions in search.