TY - GEN
T1 - Bridging the gap between abstractions and critical-path heuristics via hypergraphs
AU - Steinmetz, Marcel
AU - Torralba, Álvaro
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Planning and scheduling
UR - http://www.scopus.com/inward/record.url?scp=85085603038&partnerID=8YFLogxK
M3 - Article in proceeding
AN - SCOPUS:85085603038
T3 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS
SP - 473
EP - 481
BT - Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019
A2 - Benton, J.
A2 - Lipovetzky, Nir
A2 - Onaindia, Eva
A2 - Smith, David E.
A2 - Srivastava, Siddharth
PB - AAAI Press
T2 - 29th International Conference on Automated Planning and Scheduling, ICAPS 2019
Y2 - 11 July 2019 through 15 July 2019
ER -