Efficient Temporal Planning Using Metastates


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




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.




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



AAAI Technical Track: Planning, Routing, and Scheduling