Bridging the Gap Between Abstractions and Critical-Path Heuristics via Hypergraphs
conference contribution
posted on 2023-11-29, 18:10authored byMarcel 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",
}