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

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