When Perfect is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search
Date
2020
Authors
Speck, David
Geißer, Florian
Mattmueller, Robert
Journal Title
Journal ISSN
Volume Title
Publisher
AAAI Press
Abstract
Symbolic search has proven to be a competitive approach to cost-optimal planning, as it compactly represents sets of states by symbolic data structures. While heuristics for symbolic search exist, symbolic bidirectional blind search empirically outperforms its heuristic counterpart and is therefore the dominant search strategy. This prompts the question of why heuristics do not seem to pay off in symbolic search. As a first step in answering this question, we investigate the search behaviour of symbolic heuristic search by means of BDDA*. Previous work identified the partitioning of state sets according to their heuristic values as the main bottleneck. We theoretically and empirically evaluate the search behaviour of BDDA* and reveal another fundamental problem: we prove that the use of a heuristic does not always improve the search performance of BDDA*. In general, even the perfect heuristic can exponentially deteriorate search performance.
Description
Keywords
Citation
Collections
Source
Proceedings of the 30th International Conference on Automated Planning and Scheduling
Type
Conference paper
Book Title
Entity type
Access Statement
Free Access via publisher website
License Rights
Restricted until
2099-12-31
Downloads
File
Description