Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
Abstract
Despite recent improvements in search techniques for cost-optimal classical planning, the exponential growth of the size of the search frontier in A* is unavoidable. We investigate tiebreaking strategies for A*, experimentally analyzing the performance of standard tiebreaking strategies that break ties according to the heuristic value of the nodes. We find that tiebreaking has a significant impact on search algorithm performance when there are zero-cost operators that induce large plateau regions in the search space. We develop a new framework for tiebreaking based on a depth metric which measures distance from the entrance to the plateau, and propose a new, randomized strategy which significantly outperforms standard strategies on domains with zero-cost actions.
Cite
Text
Asai and Fukunaga. "Tiebreaking Strategies for A* Search: How to Explore the Final Frontier." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10071Markdown
[Asai and Fukunaga. "Tiebreaking Strategies for A* Search: How to Explore the Final Frontier." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/asai2016aaai-tiebreaking/) doi:10.1609/AAAI.V30I1.10071BibTeX
@inproceedings{asai2016aaai-tiebreaking,
title = {{Tiebreaking Strategies for A* Search: How to Explore the Final Frontier}},
author = {Asai, Masataro and Fukunaga, Alex S.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {673-679},
doi = {10.1609/AAAI.V30I1.10071},
url = {https://mlanthology.org/aaai/2016/asai2016aaai-tiebreaking/}
}