Front-to-Front Heuristic Search for Satisficing Classical Planning

Front-to-Front Heuristic Search for Satisficing Classical Planning

Ryo Kuroiwa, Alex Fukunaga

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 4098-4105. https://doi.org/10.24963/ijcai.2020/567

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.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Planning and Scheduling
Planning and Scheduling: Search in Planning and Scheduling