Symbolic perimeter abstraction heuristics for cost-optimal planning

Álvaro Torralba*, Carlos Linares López, Daniel Borrajo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

5 Citations (Scopus)

Abstract

In the context of heuristic search within automated planning, abstraction heuristics map the problem into an abstract instance and use the optimal solution cost in the abstract state space as an estimate for the real solution cost. Their flexibility in choosing different abstract mappings makes abstractions a powerful tool to obtain domain-independent heuristics. Different types of abstraction heuristics exist depending on how the mapping is defined, like Pattern Databases (PDBs) or Merge-and-Shrink (M&S). In this paper, we consider two variants of PDBs, symbolic and perimeter PDBs, combining them to take advantage of their synergy. Symbolic PDBs use decision diagrams in order to efficiently traverse the abstract state space. Perimeter PDBs derive more informed estimates by first constructing a perimeter around the goal and then using it to initialize the abstract search. We generalize this idea by considering a hierarchy of abstractions. Our algorithm starts by constructing a symbolic perimeter around the goal and, whenever continuing the search becomes unfeasible, it switches to a more abstracted state space. By delaying the use of an abstraction, the algorithm derives heuristics as informed as possible. Moreover, we prove that M&S abstractions with a linear merge strategy can be efficiently represented as decision diagrams, enabling the use of symbolic search with M&S abstractions as well as with PDBs. Our experimental evaluation shows that symbolic perimeter abstractions are competitive with other state-of-the-art heuristics.

Original languageEnglish
JournalArtificial Intelligence
Volume259
Pages (from-to)1-31
Number of pages31
ISSN0004-3702
DOIs
Publication statusPublished - Jun 2018
Externally publishedYes

Keywords

  • Abstraction heuristics
  • Automated planning
  • Cost-optimal planning
  • Planning systems
  • Symbolic search

Fingerprint

Dive into the research topics of 'Symbolic perimeter abstraction heuristics for cost-optimal planning'. Together they form a unique fingerprint.

Cite this