Generalised Merge and Shrink Abstractions for Temporal Planning
Journal of Artificial Intelligence Research · 25.03.2026 · 85
DOI: 10.1613/jair.1.18212 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 25.03.2026. Verfasst von Martim Brandao und 3 weiteren Autor:innen.
Abstract (Originalsprache)
Temporal planning is a hard problem that requires good heuristic and memoization strategies to solve efficiently. Merge-and-shrink abstractions have been shown to serve as effective heuristics for classical planning, but it is still unclear how to implement merge-and-shrink in the temporal domain and how effective the method is in this setting. In this paper we propose a method to compute merge-and-shrink abstractions for general temporal planning problems, in a way that is applicable to both partial- and total-order temporal planners. We extend a previous publication to allow the formalism to apply to temporal problems with non-compression safe actions, in particular through the use of a classical planning surrogate of a temporal planning task. The method relies on pre-computing heuristics as formulas of temporal variables that are evaluated at search time, and it allows to use standard merging, shrinking and pruning strategies. Compared to state-of-the-art Relaxed Planning Graph heuristics, we show that the method leads to improvements in coverage, computation time, and number of expanded nodes to solve optimal problems, as well as leading to improvements in unsolvability-proving of problems with deadlines, and the time to compute Minimally Unsolvable Goal Subsets (MUGS). We exhaustively test the method over these problems and various usage settings, showing improvements in coverage of up to 53%, computation time up to 60%, and expanded nodes up to 75%.
Zitieren
APA
Brandao, M., Coles, A., Coles, A., & Eifler, R. (2026). Generalised Merge and Shrink Abstractions for Temporal Planning. Journal of Artificial Intelligence Research, 85. https://doi.org/10.1613/jair.1.18212
Vancouver
Brandao M, Coles A, Coles A, Eifler R. Generalised Merge and Shrink Abstractions for Temporal Planning. Journal of Artificial Intelligence Research. 2026;85. doi:10.1613/jair.1.18212
BibTeX
@article{Brandao2026,
author = {Brandao, Martim and Coles, Amanda and Coles, Andrew and Eifler, Rebecca},
title = {Generalised Merge and Shrink Abstractions for Temporal Planning},
journal = {Journal of Artificial Intelligence Research},
year = {2026},
volume = {85},
doi = {10.1613/jair.1.18212}
}
EUVIMED