Temporal Landmarks: What Must Happen, and When

Authors

  • Erez Karpas Massachusetts Institute of Technology
  • David Wang Massachusetts Institute of Technology
  • Brian Williams Massachusetts Institute of Technology
  • Patrik Haslum The Australian National University and NICTA

DOI:

https://doi.org/10.1609/icaps.v25i1.13716

Keywords:

Automated Planning, Temporal Planning, Landmarks

Abstract

Current temporal planners have a hard time solving large, real-world problems which involve dealing with metric time and concurrent actions. While landmarks have enabled classical planners to scale up to significantly larger problems, they have not yet brought as much benefit to temporal planning. We argue that the reason for this is that for landmarks to make an effective addition to planning with complex temporal interactions (such as required concurrency), they must incorporate information about the timing of conditions and events. We define temporal landmarks, which associate time intervals and time points, respectively, with state and action landmarks, thereby capturing both what must happen and when it must happen. We show how to derive temporal landmarks and constraints on their associated time points from planning problems, and how exploiting them, in a planner-independent way, can improve planner performance. Notably, the greatest gain is on problems which require concurrency, showing that the temporal information we add to landmarks complements the reasoning used by current temporal planners.

Downloads

Published

2015-04-08

How to Cite

Karpas, E., Wang, D., Williams, B., & Haslum, P. (2015). Temporal Landmarks: What Must Happen, and When. Proceedings of the International Conference on Automated Planning and Scheduling, 25(1), 138-146. https://doi.org/10.1609/icaps.v25i1.13716