Increasing search efficiency using multiple heuristics (Q1119028)

The authors present an extension called QA(\(\epsilon)\) of the classic heuristic graph search procedure \(A^*\) thoroughly developed and discussed in \textit{N. J. Nilsson}'s ``Principles of artificial intelligence'' (1982; Zbl 0474.68094). Notations and definitions refer to that presentation. QA(\(\epsilon)\) is designed to be a 2-pass variation of \(A^*\)-combining two heuristics for increasing search efficiency. The first heuristic is an efficient estimate but does not guarantee admissibility. Thus the number of nodes expanded is minimized. The second one is an underestimate and guarantees admissibility. The first pass, performing search using algorithm A with the first heuristic evaluation function f1, yields after termination with path P the intermediate result max\(\{\) f1(n)\(\}\). The second pass, performing search using algorithm \(A^*\) with the second heuristic evaluation function f2, checks each newly generated node bound to be discarded if \(f2(n)>\max \{f1(n)\}\cdot (1+\epsilon)\) with \(\epsilon >\emptyset\) holds. Now they claim that for some suitable choice \(\epsilon^*\) of \(\epsilon\), there exist a minimal cost path P such that \[ \max \{f1(n)\}\leq \min \{\max (f1(n)\}\}\cdot (1+\epsilon^*) \] for all admissible paths \(P'\) and node n element of P. Then \(QA(\epsilon^*)\) provides minimal cost solutions. Hence QA(\(\epsilon)\) performs better than A on the average, in particular for harder problems, though admissibility for arbitrary \(\epsilon\) is not guaranteed. Performance tests on the 8-puzzle problem, presented in the paper, tend to confirm this property.