A game-theoretic approach to timeline-based planning with uncertainty

arXiv.org Artificial Intelligence

In timeline-based planning, domains are described as sets of independent, but interacting, components, whose behaviour over time (the set of timelines) is governed by a set of temporal constraints. A distinguishing feature of timeline-based planning systems is the ability to integrate planning with execution by synthesising control strategies for flexible plans. However, flexible plans can only represent temporal uncertainty, while more complex forms of nondeterminism are needed to deal with a wider range of realistic problems. In this paper, we propose a novel game-theoretic approach to timeline-based planning problems, generalising the state of the art while uniformly handling temporal uncertainty and nondeterminism. We define a general concept of timeline-based game and we show that the notion of winning strategy for these games is strictly more general than that of control strategy for dynamically controllable flexible plans. Moreover, we show that the problem of establishing the existence of such winning strategies is decidable using a doubly exponential amount of space.


A Novel Automata-Theoretic Approach to Timeline-Based Planning

AAAI Conferences

Timeline-based planning is a well-established approach successfully employed in a number of application domains.  A very restricted fragment, featuring only bounded temporal relations and token durations, is expressive enough to capture action-based temporal planning. As for computational complexity, it has been shown to be EXPSPACE-complete when unbounded temporal relations, but only bounded token durations, are allowed. In this paper, we present a novel automata-theoretic characterisation of timeline-based planning where the existence of a plan is shown to be equivalent to the nonemptiness of the language recognised by a nondeterministic finite-state  automaton that suitably encodes all the problem constraints (timelines and  synchronisation rules). Besides allowing us to restate known complexity results in a fairly natural and compact way, such an alternative characterisation makes it possible to finally establish the exact complexity of the full version of the problem with unbounded temporal relations and token durations, which was still open and turns out to be EXPSPACE-complete. Moreover, the proposed technique is general enough to cope with (infinite) recurrent goals, which received little attention so far, despite being quite common in real-word application scenarios.


Complexity of Timeline-Based Planning

AAAI Conferences

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, such as 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.


Timeline-Based Planning for Engaging Training Experiences

AAAI Conferences

This paper reports on a novel use of timeline-based planning as the core element of a dynamic training environment specifically designed for crisis managers. It describes an effort to build a complete application that helps the trainer to create and deliver engaging and personalized training lessons for decision making skills in crisis management domains. The paper emphasis is given to (a) the timeline-based representation as the core component for creating training sessions and a trainee's model; (b) the combination of planning and execution functionalities required to maintain and dynamically adapt a "lesson plan" on the basis of individual interactions, behaviors and performance; (c) the "mixed-initiative" approach pursued, that allows the trainer to keep control of the activity loop. The application has been fielded and evaluated through a psychophysiological assessment within a real crisis training room involving 18 real strategic decision makers in a three-days of classes experience, overall demonstrating the ability of the system to fully support trainees engagement thanks to the flexibility injected by the planning technology.


Decidability and Complexity of Timeline-Based Planning over Dense Temporal Domains

AAAI Conferences

In timeline-based planning, the planning domain is modeled as a set of independent, but interacting, components each one represented by a number of state variables, whose behavior over time (timelines) is governed by temporal constraints (synchronization rules). The temporal domain is typically assumed to be discrete. In this paper, we address decidability and complexity issues for timeline-based planning over dense temporal domains without resorting to any form of discretization. We first prove that the general problem is undecidable, and then we show that decidability can be recovered by constraining the logical structure of synchronization rules.