CISPA
Browse

File(s) not publicly available

Bridging the Gap Between Abstractions and Critical-Path Heuristics via Hypergraphs

conference contribution
posted on 2023-11-29, 18:10 authored by Marcel Steinmetz, Álvaro Torralba
Abstractions and 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.

History

Preferred Citation

Marcel Steinmetz and Álvaro Torralba. Bridging the Gap Between Abstractions and Critical-Path Heuristics via Hypergraphs. In: International Conference on Automated Planning and Scheduling (ICAPS). 2019.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Conference on Automated Planning and Scheduling (ICAPS)

Legacy Posted Date

2019-06-23

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_2935, title = "Bridging the Gap Between Abstractions and Critical-Path Heuristics via Hypergraphs", author = "Steinmetz, Marcel and Torralba, Álvaro", booktitle="{International Conference on Automated Planning and Scheduling (ICAPS)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC