Better Parameter-Free Anytime Search by Minimizing Time Between Solutions

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Full Papers

This paper presents a new anytime search algorithm, anytime explicitestimation search (AEES). AEES is an anytime search algorithm which attempts to minimize the time between improvements to its incumbent solution by taking advantage of the differences between solution cost and length. We provide an argument that minimizing the time between solutions is ideal behavior for an anytime search algorithm and show that when actions have differing costs, many state-of-the-art search algorithms, including the search strategy of LAMA11 and anytime nonparametric A*, do not minimize the time between solutions. An empirical evaluation on seven domains shows that AEES often has boththe shortest time between incumbent solutions and the best solution in hand for a wide variety of cutoffs.

10.1609/socs.v3i1.18242