Merge and Shrink Abstractions for Temporal Planning

Authors

  • Martim Brandao King's College London
  • Amanda Coles King's College London
  • Andrew Coles King's College London
  • Jörg Hoffmann Saarland University

Keywords:

Temporal Planning, Merge-and-shrink, Heuristics

Abstract

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 they have not yet been applied to temporal planning. Currently, 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 temporal planning, applicable to both partial- and total-order temporal planners. The method relies on pre-computing heuristics as formulas of temporal variables that are evaluated at search time, and it allows to use standard shrinking strategies and label reduction. 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 explored nodes to solve optimal problems, as well as leading to improvements in unsolvability-proving of problems with deadlines.

Downloads

Published

2022-06-13

How to Cite

Brandao, M., Coles, A., Coles, A., & Hoffmann, J. (2022). Merge and Shrink Abstractions for Temporal Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 16-25. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19781