Complexity of timeline-based planning

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 a 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 nonflexible 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 NEXPTIM E-complete.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Gigante, Nicola
Montanari, Angelo
Mayer, Marta Cialdea
Orlandini, Andrea
international conference on automated planning and scheduling (ICAPS), pp. 116–124, Pittsburgh, USA, 18-23/06/2017
Resource Identifier:
ISTC Author: 
AndreA Orlandini's picture
Real name: