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

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].