Change Detection in Heuristic Search

Abstract

The order in which nodes are explored in a (depth-first) iter-ative deepening search strategy is principally determined by the condition under which a path of the search tree is cut off in each search phase. A corresponding criterion, which has a strong influence on the performance of the overall (heuris-tic) search procedure, is generally realized in the form of an upper cost bound. In this paper, we develop an effective and computationally efficient termination criterion based on sta-tistical methods of change detection. The criterion is local in the sense that it depends on properties of a path itself, rather than on the comparison with other paths. Loosely speaking, the idea is to take a systematic change in the (heuristic) eval-uation of nodes along a search path as an indication of sub-optimality. An expected utility criterion which also takes the consequence of the suboptimal search decision on the solu-tion quality into account is proposed as a generalization of this idea.