Bridging the gap between abstractions and critical-path heuristics via hypergraphs

Marcel Steinmetz, Álvaro Torralba

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)

Abstract

Critical-path heuristics are among the most important families of admissible heuristics in classical planning. In this paper, we present a new family of heuristics, which we name hyperabstractions, given by the combination of the principal ideas underlying abstractions and critical-path heuristics. Hyperabstractions approximate goal distances through a mapping from states to sets of abstract states. The abstract transition behavior forms a relation between abstract states and sets of abstract states, and is formally represented via the notion of hypergraphs. We show that both abstractions and critical-path heuristics can naturally be expressed as members of this family. Moreover, we devise a method to construct hyperabstractions, using either a set of abstractions or a critical-path heuristic as a seed, in a way that guarantees that the resulting distance estimations dominate those of the input heuristics, sometimes even strictly. By finding suitable cost partitionings for hyperabstraction heuristics, this dominance result is preserved even in comparison to the additive combination of the input heuristics. Our experiments indicate the potential of this new class of heuristics, opening a wide range of future research topics.

Original languageEnglish
Title of host publicationProceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Number of pages9
PublisherAAAI Press
Publication date2019
Pages473-481
ISBN (Electronic)9781577358077
Publication statusPublished - 2019
Externally publishedYes
Event29th International Conference on Automated Planning and Scheduling, ICAPS 2019 - Berkeley, United States
Duration: 11 Jul 201915 Jul 2019

Conference

Conference29th International Conference on Automated Planning and Scheduling, ICAPS 2019
Country/TerritoryUnited States
CityBerkeley
Period11/07/201915/07/2019
SeriesProceedings International Conference on Automated Planning and Scheduling, ICAPS
ISSN2334-0835

Keywords

  • Planning and scheduling

Fingerprint

Dive into the research topics of 'Bridging the gap between abstractions and critical-path heuristics via hypergraphs'. Together they form a unique fingerprint.

Cite this