---
title: "On the Complexity and Expressiveness of Automated Planning Languages Supporting Temporal Reasoning"
authors:
  - "Nicola Gigante"
doi: "10.24963/ijcai.2017/750"
url: "https://ijcai.org/proceedings/2017/750"
pdf: "https://ijcai.org/proceedings/2017/0750.pdf"
venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"
year: 2017
pages: "5181-5182"
track: "Doctoral Consortium"
keywords:
  - "Artificial Intelligence: automated planning"
  - "Artificial Intelligence: planning"
---

# On the Complexity and Expressiveness of Automated Planning Languages Supporting Temporal Reasoning

Nicola Gigante

*Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 5181-5182. DOI: [10.24963/ijcai.2017/750](https://doi.org/10.24963/ijcai.2017/750)

## Abstract

Automated planning is an important area of Artificial Intelligence, which has been thoroughly developed in the last decades. In recent years, a significant amount of research has focused on planning languages and systems supporting temporal reasoning, recognizing its importance in modeling and solving real-world complex tasks. Many such languages are action-based, i.e. they model planning problems by specifying which actions can be executed at any given time to affect the environment. Timeline-based planning, a different paradigm originally introduced to support planning and scheduling of space operations, models planning domains as systems composed of a set of independent, but interacting, components, whose behavior over time, the timelines, is governed by a set of temporal constraints. A thorough theoretical study of timeline-based planning languages, and a rigorous comparison with action-based languages, are still missing. We outline recent results and future directions on this front.

## Full text

## On the Complexity and Expressiveness of Automated Planning Languages Supporting Temporal Reasoning

## Nicola Gigante

University of Udine, Italy gigante.nicola@spes.uniud.it

## Abstract

Automated planning is an important area of Artificial Intelligence, which has been thoroughly developed in the last decades. In recent years, a significant amount of research has focused on planning languages and systems supporting temporal reasoning, recognizing its importance in modeling and solving real-world complex tasks. Many such languages are action-based, i.e., they model planning problems by specifying which actions can be executed at any given time to affect the environment. Timeline-based planning, a different paradigm originally introduced to support planning and scheduling of space operations, models planning domains as systems composed of a set of independent, but interacting, components, whose behavior over time, the timelines, is governed by a set of temporal constraints. A thorough theoretical study of timeline-based planning languages, and a rigorous comparison with action-based languages, are still missing. We outline recent results and future directions on this front.

computationally much more complex than classical planning, since it is EXPSPACE-complete [Rintanen, 2007].

Automated planning has always been an important area of Artificial Intelligence, which has undertaken great developments during the last decades. In the action-based approach of classical planning, the task of the planner is to find a sequence of actions that, applied from an initial state, allow an executor to achieve a given goal. Modern domain description languages (e.g., PDDL [Gerevini et al., 2009]), usually adopt this point of view. Even in its simple form, classical planning is still a very hard problem, as it is PSPACE-complete, although complex classical planning problems can be solved very efficiently in practice by modern planners, thanks to the development of many effective search heuristics and steady progress of related areas such as boolean satisfiability checking, satisfiability modulo theories, and constraint satisfaction. Some problem domains, however, require a more explicit form of temporal reasoning, which does not fit well into classical planning where actions have discrete and instantaneous effects. Thus, temporal planning an extension of classical planning which models and reasons about time more explicitly, has been studied in the literature (among many others). Action-based temporal planning, in its general form, is A different paradigm, which instead has always been tightly related to temporal reasoning aspects, is timelinebased planning, which was introduced at NASA to support planning and scheduling of space operations [Muscettola, 1994]. In timeline-based planning languages, problem domains are modeled as systems composed of a set of independent, but interacting, components, whose behavior over time, the timelines, is governed by a set of temporal constraints. This point of view is different than the one of actionbased planning, as a single executor is generally not present, and the solution plan globally governs the behavior of the whole system. This approach, implemented in many planning and scheduling systems (e.g., EUROPA [Barreiro et al., 2012], ASPEN [Chien et al., 2000] and APSI-TRF [Cesta et al., 2009]), allows a greater modularity in the modeling of the behavior of systems composed of a high number of independent components, which has been proven useful in many complex use cases [Muscettola, 1994; Jónsson et al., 2000; Cesta et al., 2007]. The formalism supported by most of these systems, which has recently been thoroughly formalized by [Cialdea Mayer et al., 2016], allows one to model a kind of nondeterminism that affect the exact scheduling of activities (flexible timelines), and to model the behavior of the environment by specifying uncontrollable components.

Despite its applicability, general theoretical properties of this formalism have not been deeply studied, yet. In particular, a characterization of the computational complexity of the different levels of timeline-based planning problems is missing, as well as a comprehensive comparison of the expressive power of timeline-based languages, with respect to action-based counterparts. The goal of our work is twofold: (1) to progress towards a solid theoretical understanding of the fundamental issues regarding the timeline-based planning paradigm, and (2) to compare the expressiveness of timeline-based and action-based planning languages.

The results obtained so far explore both directions. In [Gigante et al., 2016] we provide a first expressiveness comparison between temporal action-based planning, in the form of the simple PDDL-equivalent planning language introduced by Rintanen [2007], and non-flexible timeline-based planning. Building upon the formalization of timelines provided in [Cialdea Mayer et al., 2016], we identify a syntactically restricted variant of non-flexible timeline-based planning that is expressive enough to compactly represent temporal actionbased planning problems, also showing it is EXPSPACEcomplete. In particular, the identified problem avoids both unbounded interval relations, and the specification of a fixed horizon for the solution. These results provided a first comparison between the two paradigms, but left some open questions. In [Gigante et al., 2017] we answer them by showing that the general non-flexible timeline-based planning problem, including unbounded interval relations, and the same problem when a fixed solution length is provided as part of the input, are respectively EXPSPACE- and NEXPTIME-complete.

Going forward, a great amount of work has still to be done to complete the picture. The complexity of the problem when flexible timelines are supported is maybe the most important open question, and, given the resulting nondeterminism, different action-based counterparts have to be identified to proceed with the expressiveness comparison. The complexity of the problem with the addition of uncontrollable components is the next natural step. Such a problem will probably better be approached in a game-theoretic setting.

In order to better understand the latter issues, and to compare the expressiveness of the two paradigms, a logical characterization of the formalism, i.e., finding which logical language is needed to represent timeline-based planning problems, is also an interesting goal to pursue. A similar result is known for classical planning, which can be compactly captured by Linear Temporal Logic (LTL) [Cialdea Mayer et al., 2007]. In [Della Monica et al., 2017], we provide a first step in this direction by showing that a suitably constrained fragment of the TPTL temporal logic [Alur and Henzinger, 1994], augmented with past modalities, can capture the restricted timeline-based planning problem of the kind studied in [Gigante et al., 2016]. A logical counterpart of the more general problem is still missing. These results will help compare the expressiveness of the different formalisms, and to understand the theoretical properties of problems with uncontrollable components mentioned above, by approaching them in terms of logical synthesis [Schewe and Tian, 2011].

## References

1. [Alur and Henzinger, 1994] R. Alur and T. A. Henzinger. A Really Temporal Logic. Journal of the ACM, 41(1):181- 204, 1994.
2. [Barreiro et al., 2012] J. Barreiro, M. Boyce, M. Do, J. Frank, M. Iatauro, T. Kichkaylo, P. Morris, J. Ong, E. Remolina, T. Smith, and D. Smith. EUROPA: A Plat- form for AI Planning, Scheduling, Constraint Program- ming, and Optimization. In Proc. of the 4 th International Competition on Knowledge Engineering for Planning and Scheduling, 2012.
3. [Cesta et al., 2007] A. Cesta, G. Cortellessa, S. Fratini, A. Oddi, and N. Policella. An Innovative Product for Space Mission Planning: An A Posteriori Evaluation. In Proc. of the 17 th International Conference on Automated Planning and Scheduling, pages 57-64, 2007.
4. [Cesta et al., 2009] A. Cesta, G. Cortellessa, S. Fratini, and A. Oddi. Developing an End-to-End Planning Application from a Timeline Representation Framework. In Proc. of the 21 st Conference on Innovative Applications of Artifi- cial Intelligence, pages 66-71, 2009.
5. [Chien et al., 2000] S. Chien, G. Rabideau, R. Knight, R. Sherwood, B. Engelhardt, D. Mutz, T. Estlin, B. Smith, F. Fisher, T. Barrett, G. Stebbins, and D. Tran. ASPEN -Automated Planning and Scheduling for Space Mission Operations. In Proc. of the 8 th International Conference on Space Operations, 2000.
6. [Cialdea Mayer et al., 2007] M. Cialdea Mayer, C. Limon- gelli, A. Orlandini, and V. Poggioni. Linear Tempo- ral Logic as an Executable Semantics for Planning Lan- guages. Journal of Logic, Language and Information, 16(1):63-89, 2007.
7. [Cialdea Mayer et al., 2016] M. Cialdea Mayer, A. Orlan- dini, and A. Umbrico. Planning and Execution with Flexi- ble Timelines: a Formal Account. Acta Informatica, 53(6- 8):649-680, 2016.
8. [Della Monica et al., 2017] D. Della Monica, N. Gigante, A. Montanari, P. Sala, and G. Sciavicco. Bounded Timed Propositional Temporal Logic with Past Captures Timeline-based Planning with Bounded Constraints. In Proc. of the 26 th International Joint Conference on Arti- ficial Intelligence. To appear, 2017.
9. [Gerevini et al., 2009] Alfonso Gerevini, Patrik Haslum, Derek Long, Alessandro Saetti, and Yannis Dimopoulos. Deterministic Planning in the Fifth International Planning Competition: PDDL3 and Experimental Evaluation of the Planners. Artificial Intelligence, 173(5-6):619-668, 2009.
10. [Gigante et al., 2016] N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini. Timelines are Expressive Enough to Capture Action-based Temporal Planning. In Proc. of the 23 rd International Symposium on Temporal Representation and Reasoning, pages 100-109, 2016.
11. [Gigante et al., 2017] N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini. Complexity of Timeline-based Planning. In Proc. of the 27 th International Conference on Automated Planning and Scheduling. To appear, 2017.
12. [Jónsson et al., 2000] Ari K. Jónsson, Paul H. Morris, Nicola Muscettola, Kanna Rajan, and Benjamin D. Smith. Plan- ning in Interplanetary Space: Theory and Practice. In Proc. of 5 th International Conference on Artificial Intel- ligence Planning and Scheduling, pages 177-186, 2000.
13. [Muscettola, 1994] Nicola Muscettola. HSTS: Integrating Planning and Scheduling. In Monte Zweben and Mark S. Fox, editors, Intelligent Scheduling, chapter 6, pages 169- 212.
14. Morgan Kaufmann, 1994.
15. [Rintanen, 2007] Jussi Rintanen. Complexity of Concurrent Temporal Planning. In Proc. of the 17 th International Conference on Automated Planning and Scheduling, pages 280-287, 2007.
16. [Schewe and Tian, 2011] Sven Schewe and Cong Tian. Syn- thesising Classic and Interval Temporal Logic. In 18 th In- ternational Symposium on Temporal Representation and Reasoning, pages 64-71, 2011.