Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping
Keywords:Planning, Routing, And Scheduling (PRS)
AbstractThe field of Temporal Planning (TP) is receiving increasing interest for its many real-world applications. Most of the literature focuses on the TP problem of finding a plan, with algorithms that are not guaranteed to terminate when the problem admits no solution. In this paper, we present sound and complete decision procedures that address the dual problem of proving that no plan exists, which has important applications in oversubscription, model validation and optimization. We focus on the expressive and practically relevant semantics of action non-self-overlapping, recently proved to be PSPACE-complete. For this subclass, we propose two approaches: a reduction of the planning problem to model-checking of Timed Transition Systems, and a heuristic-search algorithm where temporal constraints are represented by Difference Bound Matrices. We implemented the approaches, and carried out an experimental evaluation against other state-of-the-art TP tools. On benchmarks that admit no plans, both approaches dramatically outperform the other planners, while the heuristic-search algorithm remains competitive on solvable benchmarks.
How to Cite
Panjkovic, S., Micheli, A., & Cimatti, A. (2022). Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 9886-9893. https://doi.org/10.1609/aaai.v36i9.21225
AAAI Technical Track on Planning, Routing, and Scheduling