Efficient Temporal Planning Using Metastates

Authors

  • Amanda Coles King's College London
  • Andrew Coles King's College London
  • J. Christopher Beck University of Toronto

DOI:

https://doi.org/10.1609/aaai.v33i01.33017554

Abstract

When performing temporal planning as forward state-space search, effective state memoisation is challenging. Whereas in classical planning, two states are equal if they have the same facts and variable values, in temporal planning this is not the case: as the plans that led to the two states are subject to temporal constraints, one might be extendable into at temporally valid plan, while the other might not. In this paper, we present an approach for reducing the state space explosion that arises due to having to keep many copies of the same ‘classically’ equal state – states that are classically equal are aggregated into metastates, and these are separated lazily only in the case of temporal inconsistency. Our evaluation shows that this approach, implemented in OPTIC and compared to existing state-of-the-art memoisation techniques, improves performance across a range of temporal domains.

Downloads

Published

2019-07-17

How to Cite

Coles, A., Coles, A., & Beck, J. C. (2019). Efficient Temporal Planning Using Metastates. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 7554-7561. https://doi.org/10.1609/aaai.v33i01.33017554

Issue

Section

AAAI Technical Track: Planning, Routing, and Scheduling