David Speck, Florian Geißer, Robert Mattmüller |
PosterID:
47
PDF
Slides
Poster
BibTeX
|
| 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. | |
| Canb | 10/28/2020, 18:00 – 19:00 |
| 10/30/2020, 01:00 – 02:00 |
| Paris | 10/28/2020, 08:00 – 09:00 |
| 10/29/2020, 15:00 – 16:00 |
| NYC | 10/28/2020, 03:00 – 04:00 |
| 10/29/2020, 10:00 – 11:00 |
| LA | 10/28/2020, 00:00 – 01:00 |
| 10/29/2020, 07:00 – 08:00 |
Certified Unsolvability for SAT Planning with Property Directed Reachability
Salomé Eriksson, Malte Helmert
When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search
David Speck, Florian Geißer, Robert Mattmüller
Lifted Successor Generation Using Query Optimization Techniques
Augusto B. Corrêa, Florian Pommerening, Malte Helmert, Guillem Francès
Through the Lens of Sequence Submodularity
Sara Bernardini, Fabio Fagnani, Chiara Piacentini