Timeline-based planning is a paradigm that models temporal planning domains as sets of independent, but interacting, components. The behavior of the components can be described by means of a number of state variables whose evolution and interactions over time are governed by a set of temporal constraints. This paradigm is different from the one underlying the common action-based formalisms à la PDDL, where the focus is on what can be done by an executive agent. Although successfully used in many real-world applications, little work has been done on the expressiveness and complexity of the timeline-based formalism. The present paper provides a characterization of the complexity of non- flexible timeline-based planning, by proving that a general formulation of the problem is EXPSPACE-complete. Such a result extends a previous work where the same complexity bound was proved for a restricted fragment of timeline-based planning that was shown to be expressive enough to capture action-based temporal planning. In addition, we prove that requiring an upper bound to the solution horizon as part of the input decreases the complexity of the problem, that becomes NEXPTIME-complete.
Gigante, N., Montanari, A., Cialdea, M., & Orlandini, A. (2017). Complexity of Timeline-based Planning. In Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017) (pp.116-124). AAAI Press.
Titolo: | Complexity of Timeline-based Planning | |
Autori: | ||
Data di pubblicazione: | 2017 | |
Citazione: | Gigante, N., Montanari, A., Cialdea, M., & Orlandini, A. (2017). Complexity of Timeline-based Planning. In Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017) (pp.116-124). AAAI Press. | |
Handle: | http://hdl.handle.net/11590/326758 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Note | Licenza | |
---|---|---|---|---|---|
2017-ICAPS.pdf | Documento in Post-print | Nessuna Nota | Open Access Visualizza/Apri |