Robust bidirectional search via heuristic improvement

摘要: Although the heuristic search algorithm A* is well-known to be optimally efficient, this result explicitly assumes forward search. Bidirectional has long held promise for surpassing A*'s efficiency, and many varieties have been proposed, but it proven difficult achieve robust performance across multiple domains in practice. We introduce a simple bidirectional technique called Incremental KKAdd that judiciously performs backward improve accuracy of function any algorithm. integrate with A*, assess its theoretical properties, empirically evaluate seven benchmark domains. In best case, yields factor six reduction node expansions CPU time compared worst overhead provably bounded by user-supplied parameter, such as 1%. Viewing all domains, also surpasses previously proposed algorithms. These results indicate way leverage