When perfect is not good enough: On the search behaviour of symbolic heuristic search

David Speck, Florian Geißer, Robert Mattmüller

    Research output: Contribution to journalConference articlepeer-review

    8 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)263-271
    Number of pages9
    JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
    Volume30
    Publication statusPublished - 29 May 2020
    Event30th International Conference on Automated Planning and Scheduling, ICAPS 2020 - Nancy, France
    Duration: 26 Oct 202030 Oct 2020

    Fingerprint

    Dive into the research topics of 'When perfect is not good enough: On the search behaviour of symbolic heuristic search'. Together they form a unique fingerprint.

    Cite this