Towards finding optimal solutions with non-admissible heuristics: a new technique
Henry W. Davis, Anna Bramanti-Gregor, Xiaofeng Chen · 1989
A problem with A * is that it fails to guarantee optimal solutions when its heuristic, h, overestimates. Since optimal solutions are often desired and an underestimating h is not always available, we seek to remedy this. From a nonadmissible h an admissible one is generated using h's statistical properties. The new heuristic, hm, is obtained by inverting h with respect to its own least upper bound function. The set of nodes expanded when A * uses g + hm as an evaluator is compared with the set of nodes expanded using other approaches which have been suggested in the literature. A considerable potential savings in node expansion when using hm is indicated. In 8-puzzle experiments A * using g +hm expands one fifth as many nodes as does the best alternative approach. 1.