When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search

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.