Front-to-Front Heuristic Search for Satisficing Classical Planning
Abstract
Although symbolic bidirectional search is successful in optimal classical planning, state-of-the-art satisficing planners do not use bidirectional search. Previous bidirectional search planners for satisficing planning behaved similarly to a trivial portfolio, which independently executes forward and backward search without the desired ``meet-in-the-middle'' behavior of bidirectional search where the forward and backward search frontiers intersect at some point relatively far from the forward and backward start states. In this paper, we propose Top-to-Top Bidirectional Search (TTBS), a new bidirectional search strategy with front-to-front heuristic evaluation. We show that TTBS strongly exhibits ``meet-in-the-middle'' behavior and can solve instances solved by neither forward nor backward search on a number of domains.
Cite
Text
Kuroiwa and Fukunaga. "Front-to-Front Heuristic Search for Satisficing Classical Planning." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/567Markdown
[Kuroiwa and Fukunaga. "Front-to-Front Heuristic Search for Satisficing Classical Planning." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/kuroiwa2020ijcai-front/) doi:10.24963/IJCAI.2020/567BibTeX
@inproceedings{kuroiwa2020ijcai-front,
title = {{Front-to-Front Heuristic Search for Satisficing Classical Planning}},
author = {Kuroiwa, Ryo and Fukunaga, Alex},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {4098-4105},
doi = {10.24963/IJCAI.2020/567},
url = {https://mlanthology.org/ijcai/2020/kuroiwa2020ijcai-front/}
}