Abstraction Heuristics for Symbolic Bidirectional Search
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3272-3277.
Abstract
Symbolic bidirectional uniform-cost search is a prominent technique for cost-optimal planning. Thus, the question whether it can be further improved by making use of heuristic functions raises naturally. However, the use of heuristics in bidirectional search does not always improve its performance. We propose a novel way to use abstraction heuristics in symbolic bidirectional search in which the search only resorts to heuristics when it becomes unfeasible. We adapt the definition of partial and perimeter abstractions to bidirectional search, where A* is used to traverse the abstract state spaces and/or generate the perimeter. The results show that abstraction heuristics can further improve symbolic bidirectional search in some domains. In fact, the resulting planner, SymBA*, was the winner of the optimal-track of the last IPC.
@inproceedings{ijcai2016p463,
title = {Abstraction Heuristics for Symbolic Bidirectional Search},
author = {de Reyna, Álvaro Torralba Arias and Linares López, Carlos and Borrajo, Daniel},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {3272--3277},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/463},
}
TY - CPAPER TI - Abstraction Heuristics for Symbolic Bidirectional Search AU - de Reyna, Álvaro Torralba Arias AU - Linares López, Carlos AU - Borrajo, Daniel T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 3272 EP - 3277 UR - https://ijcai.org/proceedings/2016/463 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
