Potential search: A new greedy anytime heuristic search

In this paper we explore a novel approach for anytime heuris-tic search, in which the node that is most probable to im-prove the incumbent solution is expanded first. This is espe-cially suited for the ”anytime aspect ” of anytime algorithms- the possibility that the algorithm will be be halted any-time throughout the search. The potential of a node to im-prove the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust