TY - JOUR AU - Speck, David AU - Geißer, Florian AU - Mattmüller, Robert PY - 2020/06/01 Y2 - 2024/03/28 TI - When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 30 IS - 1 SE - Main Track DO - 10.1609/icaps.v30i1.6670 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/6670 SP - 263-271 AB - <p>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 <em>blind</em> 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<sup>⋆</sup>. 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<sup>⋆</sup> and reveal another fundamental problem: we prove that the use of a heuristic does not always improve the search performance of BDDA<sup>⋆</sup>. In general, even the perfect heuristic can exponentially deteriorate search performance.</p> ER -