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|
|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.|
|Appare nelle tipologie:||4.1 Contributo in Atti di convegno|