The pathology of heuristic search in the 8-puzzle

摘要

In practice, an incomplete heuristic search nearly always finds better solutions if itnis allowed to search deeper, i.e. expand and heuristically evaluate more nodes innthe search tree. On the rare occasions when searching deeper is not beneficial, ancurious phenomenon called ‘search pathology’ occurs. In this article, we study thenpathology and gain of a deeper search of the minimin algorithm in the 8-puzzle,na domain often used for evaluating single-agent search algorithms. We havenanalysed the influence of various properties of the search tree and the heuristicnevaluation function on the gain and the pathology. In order to investigate a broadnrange of the properties, the original 8-puzzle was extended with diagonal moves,nyielding a larger variety of search trees. It turned out that in the 8-puzzle, ansubstantial proportion of the solvable positions is pathological under variousnparameters. More importantly, the search parameters that enable the highestngains are quite consistent in pathological and non-pathological positions alike,nthus pointing to potentially successful search strategies.