PDDL STRIPS NEXPSPACE NEXPTIME PTIME University of Udine, Udine,
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Gigante and A. Montanari’s work was mainly done
while on leave at _The University of Western Australia_. The work was
supported by the GNCS project _Formal methods for verification and synthesis
of discrete and hybrid systems_ (N. Gigante, A. Montanari, M. Cialdea Mayer)
and the PRID project _ENCASE - Efforts in the uNderstanding of Complex
interActing SystEms_ (N. Gigante, A. Montanari). University of Roma Tre, Rome,
Italy<EMAIL_ADDRESS>National Research Council, Rome, Italy
<EMAIL_ADDRESS>The University of Western Australia, Perth,
Australia<EMAIL_ADDRESS>Reynolds acknowledges the support of
Australian Research Council funding (DP140103365). N. Gigante, A. Montanari,
M. Cialdea Mayer, A. Orlandini, and M. Reynolds

###### Acknowledgements.

Natasha Alechina, Kjetil Nørvåg, and Wojciech Penczek 3 25th International
Symposium on Temporal Representation and Reasoning (TIME 2018) TIME 2018 TIME
2018 October 15–17, 2018 Warsaw, Poland 120 13

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

Nicola Gigante and Angelo Montanari  ,  Marta Cialdea Mayer  ,  Andrea
Orlandini  and  Mark Reynolds

###### Abstract.

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.

###### Key words and phrases:

Timeline-based planning with uncertainty; strategic games; decidability

###### 1991 Mathematics Subject Classification:

CCS → Computing methodologies → Artificial intelligence → Planning and
scheduling → Planning under uncertainty

###### category:

##  1\. Introduction

In the timeline-based approach to planning [20], the world is modelled as a
set of independent, but interacting, components, whose behaviour over time,
the _timelines_ , is governed by a set of temporal constraints. This approach
differs from the classical _action-based_ planning, relying on [13], for its
more declarative nature and its focus on temporal reasoning (see, [9, 11, 14,
15, 16, 20]). Timeline-based systems have been successfully deployed in a
number of complex scenarios, ranging from space operations [3, 7, 20] to
manufacturing [5, 23]. An important feature of timeline-based planning systems
is their ability to integrate planning with execution by means of _flexible
plans_ , which represent envelopes of possible solutions that differ in the
execution times and/or the duration of tasks. Flexible plans allow the
controller to handle the _temporal uncertainty_ involved in dealing with
partially controllable elements and the external environment. Cialdea Mayer et
al.[9] rigorously defined the concept of timeline-based planning specification
as well as _dynamically controllable_ flexible plans, which can be executed
guaranteeing to satisfy the problem constraints while reactively handling any
_temporal uncertainty_ in the uncontrollable behaviour. A technique for
synthesising dynamic control strategies is shown in [8].

Other forms of uncertainty, such as _nondeterminism_ (_which_ tasks the
environment chooses to perform), are not supported: even for external
variables, completely controlled by the environment, their evolution is known
up to temporal uncertainty only. This choice to focus on temporal reasoning
and temporal uncertainty is coherent with the history and scope of timeline-
based systems. However, it is not completely reflected into the grammar of
modelling languages used in timeline-based systems, which are expressive
enough to model complex scenarios that require the system to handle non-
temporal nondeterminism. In such cases, current systems often employ a _re-
planning_ stage as part of their execution cycle (see, [23]): any mismatch
between the expected and actual behaviours of the environment results into a
revision of the flexible plan, which then can resume execution. Unfortunately,
the cost of such a re-planning phase may be incompatible with the requirements
of real-time execution and, more importantly, if a wrong choice is made by the
original flexible plan, the re-planning might happen too late to be able to
recover a controllable state of the system. Hence, knowledge engineers have to
explicitly account for this problem if they want to avoid unnecessary failures
and costly re-planning during execution, which make the system less effective
and more complex to use.

Nondeterministic planning issues have been extensively investigated within the
action-based planning framework following different approaches such as, for
instance, reactive planning systems [4], deductive planning [22], POMDP [17],
and model checking [12]. More recently, fully observable nondeterministic
(FOND) planning problems have been addressed [18, 19] also considering
temporally extended goals [6, 21]. However, action-based planning does not
support flexible plans and temporal uncertainty, and it does not take into
account controllability issues. Recently, SMT-based techniques have been
exploited to deal with uncontrollable durations in strong temporal planning
[10]; however, dynamic controllability issues are not addressed.

This paper defines the novel concept of _timeline-based planning game_ , a
game-theoretic generalisation of the timeline-based planning problem with
uncertainty, which uniformly treats both temporal uncertainty and general
nondeterminism. In these games, the controller tries to satisfy the given
temporal constraints no matter what the choices of the environment are. We
compare the proposed games with the current approaches based on flexible
plans. In particular, we show how current timeline-based modelling languages
can express problems that, only seeming to involve temporal uncertainty at
first, in fact model scenarios which would require the controller to handle
non-temporal nondeterminism. We show that these problems do not admit
dynamically controllable flexible plans (as defined in [9]), but do admit
winning strategies when seen as instances of timeline-based games. A study of
the decidability and complexity of the problem of establishing the existence
of a winning strategy for a given timeline-based planning game concludes the
paper.

The paper is structured as follows. Section 2 briefly recaps the basic
definitions, and Section 3 discusses the limitations of the approach employed
in state-of-the-art timeline-based planning systems. Then, Section 4 defines
timeline-based planning games, and shows its greater generality with respect
to the current approach. Finally, Section 5 addresses decidability and
complexity issues. Section 6 concludes discussing future developments.

##  2\. Timeline-based planning

This section introduces timeline-based planning and describes the state of the
art of the field with regards to how uncertainty is handled by current
timeline-based systems. As a representative of the modelling languages used by
existing systems, we chose the formal language introduced in [9]. We first
introduce the basic concepts of the framework, without considering
uncertainty, as studied in [15, 16]; then, we add uncertainty to the picture
and discuss how it is handled by current systems.

###  2.1. Basic definitions

State variables are the basic building blocks of the timeline-based planning
framework.

######  Definition 2.1 (State variables).

A _state variable_ is a tuple $x=(V_{x},T_{x},D_{x},\gamma_{x})$, where:

  * •

$V_{x}$ is the _finite domain_ of the variable;

  * •

$T_{x}:V_{x}\to 2^{V_{x}}$ is the _value transition function_ , which maps
each value $v\in V_{x}$ to the set of values that can follow it;

  * •

$D_{x}:V_{x}\to\mathbb{N}^{+}\times(\mathbb{N}^{+}\cup\\{+\infty\\})$ is a
function that maps each $v\in V_{x}$ to the pair
$(d^{x=v}_{min},d^{x=v}_{max})$ of the minimum and maximum duration of any
interval over which $x=v$;

  * •

$\gamma_{x}:V_{x}\to\\{\mathsf{c},\mathsf{u}\\}$ is a function called
_controllability tag_ (see Section 2.2).

Which value is taken by a state variable over a specified time interval is
described by means of _tokens_. The behaviour of a state variable over time is
modelled by a finite sequence of tokens, called a _timeline_.

######  Definition 2.2 (Timelines).

A _token_ for $x$ is a tuple $\tau=(x,v,d)$, where $x$ is a state variable,
$v\in V_{x}$ is the value held by the variable, and $d\in\mathbb{N}^{+}$ is
the _duration_ of the token. A _timeline_ for a state variable
$x=(V_{x},T_{x},D_{x},\gamma_{x})$ is a finite sequence
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k}\rangle$ of tokens for $x$.

For any token $\tau_{i}=(x,v_{i},d_{i})$ in a timeline
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k}\rangle$ we can define the
functions $\operatorname{\mathsf{start-
time}}(\mathsf{T},i)=\sum_{j=1}^{i-1}d_{j}$ and $\operatorname{\mathsf{end-
time}}(\mathsf{T},i)=\operatorname{\mathsf{start-time}}(\mathsf{T},i)+d_{i}$,
hence mapping each token to the corresponding time interval
$[\operatorname{\mathsf{start-time}},\operatorname{\mathsf{end-time}})$ (right
extremum excluded). As an example, the time interval associated with the token
$\tau_{1}=(x,2,5)$ is $[0,5)$. When there is no ambiguity, we write
$\operatorname{\mathsf{start-time}}(\tau_{i})$ and $\operatorname{\mathsf{end-
time}}(\tau_{i})$ to denote, respectively, $\operatorname{\mathsf{start-
time}}(\mathsf{T},i)$ and $\operatorname{\mathsf{end-time}}(\mathsf{T},i)$.
The _horizon_ of a timeline
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k}\rangle$ is defined as
$\mathcal{H}(\mathsf{T})=\operatorname{\mathsf{end-time}}(\tau_{k})$. A
timeline $\mathsf{T}$ can be empty, in which case we define its horizon as
$\mathcal{H}(\mathsf{T})=0$.

The problem domain and the goal are modelled by a set of temporal constraints,
called _synchronisation rules_. For the sake of space, we do not provide a
detailed account of their syntax. Informally, each synchronisation rule has
the following form:

$\displaystyle\mathit{rule}$
$\displaystyle{}\mathrel{:=}a_{0}[x_{0}=v_{0}]\longrightarrow\mathcal{E}_{1}\mathrel{\vee}\mathcal{E}_{2}\mathrel{\vee}\ldots\mathrel{\vee}\mathcal{E}_{k},\
with$ $\displaystyle\mathcal{E}_{i}$ $\displaystyle{}\mathrel{:=}\exists
a_{1}[x_{1}=v_{1}]a_{2}[x_{2}=v_{2}]\ldots
a_{n}[x_{n}=v_{n}]\mathrel{.}\mathcal{C}$

where $x_{0},\ldots,x_{n}$ are state variables and $v_{0},\ldots,v_{n}$ are
values, with $v_{i}\in V_{x_{i}}$ for all $i$. Each rule thus consists of a
_trigger_ ($a[x_{0}=v_{0}]$) and a disjunction of _existential statements_. It
is satisfied if for each token satisfying the trigger, at least one of the
disjuncts is satisfied. The trigger can be empty ($\mathsf{T}$), in which case
the rule is said to be _triggerless_ and asks for the satisfaction of the body
without any precondition. Each existential statement requires the existence of
some tokens such that the clause $\mathcal{C}$ is satisfied. The clause is in
turn a conjunction of _atoms_ , that is, atomic relations between endpoints of
the quantified tokens, of the form $a\leq^{e_{1},e_{2}}_{[l,u]}b$, where $a$
and $b$ are token names, $e_{1},e_{2}\in\\{\mathsf{s},\mathsf{e}\\}$,
$l\in\mathbb{N}$, and $u\in\mathbb{N}\cup\\{+\infty\\}$. Intuitively, each
atom relates the start ($\mathsf{s}$) or end ($\mathsf{e}$) of the two tokens,
and $l$ and $u$ are respectively a lower and upper bound to the distance
between the two endpoints. Pointwise atoms relating a single endpoint with a
specific point in time are also possible, $a\leq^{\mathsf{s}}_{[l,u]}t$. An
atom $a\leq^{e_{1},e_{2}}_{[l,u]}b$ is _bounded_ if $u\neq+\infty$, and
_unbounded_ otherwise. With these basic atomic relations, one can express all
the Allen’s relations over time intervals [1]. As an example, one can define
$a\mathbin{\mathsf{meets}}b$ as $a\leq^{\mathsf{e,s}}_{[0,0]}b$, or
$a\mathbin{\mathsf{during}}b$ as $a\leq^{\mathsf{s,s}}_{[0,+\infty]}b\land
b\leq^{\mathsf{e,e}}_{[0,+\infty]}a$. Moreover, one can constrain the duration
of tokens, writing $\operatorname{\mathsf{duration}}(a)=k$ or
$\operatorname{\mathsf{duration}}(a)\geq k$ as a shorthand for, respectively,
$a\leq^{\mathsf{s,e}}_{[k,k]}a$ and $a\leq^{\mathsf{s,e}}_{[k,+\infty]}a$.
Moreover, disjunctions in synchronisation rules allows one to express some
forms of conditional (if/then/else) statements.

In the simplest setting, a timeline-based planning problem consists of a set
of state variables and a set of rules that represent the problem domain and
the goal. A solution to such a problem is simply a set of timelines that
satisfy the rules.

######  Definition 2.3 (Timeline-based planning problem).

A _timeline-based planning problem_ is a pair $P=(\mathit{SV},S)$, where
$\mathit{SV}$ is a set of state variables and $S$ is a set of synchronisation
rules over $\mathit{SV}$.

######  Definition 2.4 (Solution plan).

A _scheduled solution plan_ for a problem $P=(\mathit{SV},S)$ is a set
$\Gamma$ of scheduled timelines, one for each $x\in\mathit{SV}$, such that
$v_{i+1}\in T_{x}(v_{i})$ and $d_{min}^{x=v}\leq d_{i}\leq d_{max}^{x=v}$ for
all tokens $\tau_{i}=(x_{i},v_{i},d_{i})\in\mathsf{T}_{x}$, and all the rules
in $S$ are satisfied.

Note that the controllability tags $\gamma_{x}$ of state variables are ignored
in Definition 2.4, as it only considers the problem of satisfying the
synchronisation rules and the issues arising from the execution of the plan
are not considered. Even without considering any form of uncertainty,
timeline-based planning is already quite a hard problem. Indeed, we know from
[16] that the problem of deciding whether there exists a solution plan for a
given timeline-based planning problem is -complete.

As an example, consider Fig. 1, which shows a possible solution for a problem
with two state variables, $x_{\mathsf{cam}}$ and $x_{\mathsf{dir}}$, that
respectively represent the on/off state of a camera and its direction. The
transition function $T_{x_{\mathsf{dir}}}$ of the second variable is such that
the camera can only stay still or move counterclockwise, that is,
$T_{x_{\mathsf{dir}}}(\leftarrow)=\\{\leftarrow,\downarrow\\}$. The first rule
states the system requirement that the camera must remain switched off at
least four time steps after each use, to let the components cool down. The
objective of the system is that of performing some shoots of a given duration,
provided the camera is pointed in the right direction: a shoot downwards
lasting two time steps, and a shoot toward left lasting three time steps, in
an arbitrary order. This objective is encoded by the second and third
synchronisation rules, which are triggerless. The last rule expresses the fact
that the camera is initially pointed upwards.

$\displaystyle a[x_{\mathsf{cam}}=\mathsf{on}]\longrightarrow{}$
$\displaystyle\exists
b[x_{\mathsf{cam}}=\mathsf{off}]\mathrel{.}a\mathbin{\mathsf{meets}}b\land\operatorname{\mathsf{duration}}(b)\geq
4$ $\displaystyle\top\longrightarrow{}$ $\displaystyle\exists
a[x_{\mathsf{cam}}=\mathsf{on}]\;b[x_{\mathsf{dir}}=\;\downarrow]\mathrel{.}\operatorname{\mathsf{duration}}(a)=2\land
a\mathbin{\mathsf{during}}b$ $\displaystyle\top\longrightarrow{}$
$\displaystyle\exists
a[x_{\mathsf{cam}}=\mathsf{on}]\;b[x_{\mathsf{dir}}=\;\leftarrow]\mathrel{.}\operatorname{\mathsf{duration}}(a)=3\land
a\mathbin{\mathsf{during}}b$ $\displaystyle\top\longrightarrow{}$
$\displaystyle\exists
a[x_{\mathsf{dir}}=\;\uparrow]\mathrel{.}a=^{\mathsf{s}}0$

${x_{\mathsf{cam}}}$${x_{\mathsf{dir}}}$${\mathsf{on}}$${\mathsf{on}}$${\uparrow}$${\leftarrow}$${\downarrow}$${\rightarrow}$${\uparrow}$${\leftarrow}$${\mathsf{off}}$${\mathsf{off}}$

Figure 1. An example of timeline-based planning problem. Two state variables
are used to represent the on/off state of a camera $x_{\mathsf{cam}}$ and its
pointing direction $x_{\mathsf{dir}}$. The transition function of $x_{dir}$
forces the camera to only move counterclockwise.

###  2.2. Timeline-based planning with uncertainty

A distinguishing feature of existing timeline-based planning systems is their
ability to integrate planning and execution, accounting for the unavoidable
uncertainty that comes from the interaction with the environment where the
plan is executed. We now recall how timeline-based planning problems with
uncertainty are defined in [9].

Two different sources of uncertainty can be represented by this model. The
first comes from _external variables_ , which are completely under the control
of the environment, in contrast to _controlled variables_ (also called
_planned_ variables), which are dealt with the system. The planner is not
allowed to decide anything regarding the behaviour of external variables. The
second is the duration of _uncontrollable tokens_. The _controllability tag_
$\gamma_{x}$, associated with each state variable $x$, states whether a token
where $x=v$ is _controllable_ ($\gamma_{x}(v)=\mathsf{c}$) or _uncontrollable_
($\gamma_{x}(v)=\mathsf{u})$. The execution of uncontrollable tokens is
planned and performed by the system, but their duration cannot be known in
advance, one may go shopping without knowing how much time he/she will have to
wait at the counter. In both cases, only _temporal_ uncertainty is considered
in the current approach.

To deal with the uncertainty inherent in the execution of the plan, timeline-
based planning systems make use of the concept of _flexible timeline_.

######  Definition 2.5 (Flexible timeline).

A _flexible token_ is a tuple $\tau=(x,v,[e,e^{\prime}],[d,d^{\prime}])$,
where $x$ is a state variable, $v\in V_{x}$,
$[e,e^{\prime}]\in\mathbb{N}\times\mathbb{N}$ is the interval of possible
token _end times_ 111Flexible tokens report their end times rather than their
start times because in this way a flexible timeline can precisely constrain
its horizon., and $[d,d^{\prime}]\in\mathbb{N}^{+}\times\mathbb{N}^{+}$ is the
interval of possible token _durations_.

A _flexible timeline_ for a state variable $x=(V_{x},T_{x},D_{x},\gamma_{x})$
is a finite sequence $\mathsf{T}_{x}=\langle\tau_{1},\ldots,\tau_{k}\rangle$
of flexible tokens for $x$ where
$[e_{1},e_{1}^{\prime}]=[d_{1},d_{1}^{\prime}]$, and
$[e_{i},e_{i}^{\prime}]\subseteq[e_{i-1}+d_{i},e_{i-1}^{\prime}+d_{i}^{\prime}]$
for all $1<i\leq k$.

A flexible timeline represents a set of different timelines which differ in
the precise timings of the described events. Tokens, timelines, and plans will
also be referred as _scheduled_ tokens, timelines and plans, to better
differentiate them from flexible ones. A scheduled timeline
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k}\rangle$ is an _instance_ of a
flexible timeline
$\mathsf{T}^{\prime}=\langle\tau^{\prime}_{1},\ldots,\tau^{\prime}_{k}\rangle$
if for each $\tau_{i}=(x,v,d)$ and
$\tau^{\prime}_{i}=(x^{\prime},v^{\prime},[e,e^{\prime}],[d,d^{\prime}])$, we
have $x=x^{\prime}$, $v=v^{\prime}$, $d\in[d,d^{\prime}]$, and
$\operatorname{\mathsf{end-time}}(\tau_{i})\in[e,e^{\prime}]$.

Flexibility can be naturally lifted from timelines to plans. The notion of
_flexible plan_ is formally defined as follows.

######  Definition 2.6 (Flexible plan).

A _flexible plan_ over a set of state variables $\mathit{SV}$ is a pair
$\Pi=(\Gamma,\mathcal{R})$, where $\Gamma$ is a set of _flexible timelines_ ,
exactly one for each $x\in\mathit{SV}$, and $\mathcal{R}$ is a set of _atoms_
over the tokens occurring in $\Gamma$.

Given a flexible plan $\Pi=(\Gamma,\mathcal{R})$, a scheduled plan
$\Gamma^{\prime}$ is an _instance_ of $\Pi$ if the timelines in
$\Gamma^{\prime}$ are instances of those in $\Gamma$, and they satisfy the
atoms in $\mathcal{R}$.

A flexible plan can be viewed as a tentative set of solutions to a planning
problem where the precise timing of execution and the duration of tokens are
chosen during execution. The set of atoms that comes together with the set of
flexible timelines allow the plan to specify additional constraints over the
tokens that compose the timelines. Flexible plans can in particular be used to
describe the expected behaviour of external variables, of which one may know
the future evolution only up to some temporal uncertainty. It is worth
pointing out that a flexible plan is _unconditional_ , a single plan is
committed to a specific sequence of state variable values, and the only
freedom left concerns token durations.

A timeline-based planning problem with uncertainty is formally defined as
follows.

######  Definition 2.7 (Timeline-based planning problem with uncertainty).

A _timeline-based planning problem with uncertainty_ is a tuple
$P=(\mathit{SV}_{C},\mathit{SV}_{E},S,\mathcal{O})$, where:

  * •

$\mathit{SV}_{C}$ and $\mathit{SV}_{E}$ are the sets of, respectively, the
_controlled_ and the _external_ variables;

  * •

$S$ is a set of synchronisation rules over
$\mathit{SV}_{C}\cup\mathit{SV}_{E}$;

  * •

the _observation_ $\mathcal{O}=(\Gamma_{E},\mathcal{R}_{E})$ is a flexible
plan over $\mathit{SV}_{E}$ specifying the behaviour of external variables.

Definition 2.7 differs from Definition 2.3 in two main respects: it splits the
set of variables into controlled and external ones and it includes a flexible
plan describing the temporally uncertain behaviour of external variables.

To solve the problem, one has to find a set of flexible timelines for the
controlled variables such that the rules can be satisfied by a suitable set of
instances.

######  Definition 2.8 (Flexible solution plan).

Let $P=(\mathit{SV}_{C},\mathit{SV}_{E},S,\mathcal{O})$, with
$\mathcal{O}=(\Gamma_{E},\mathcal{R}_{E})$ be a timeline-based planning
problem with uncertainty. A flexible plan $\Pi=(\Gamma,\mathcal{R})$ over
$\mathit{SV}_{C}\cup\mathit{SV}_{E}$ is a _flexible solution plan_ for $P$ if:

  1. (1)

$\Pi$ agrees with $\mathcal{O}$, that is, $\Gamma_{E}\subseteq\Gamma$ and
$\mathcal{R}_{E}\subseteq\mathcal{R}$;

  2. (2)

the plan does not restrict the duration of uncontrollable tokens, that is, for
any $\mathsf{T}\in\Gamma$ and any token
$\tau=(x,v,[e,e^{\prime}],[d,d^{\prime}])\in\mathsf{T}$, if
$\gamma_{x}(v)=\mathsf{u}$, then $d=d^{x=v}_{min}$ and
$d^{\prime}=d^{x=v}_{max}$;

  3. (3)

any _instance_ of $\Gamma$ is a scheduled solution plan for the timeline-based
planning problem $P^{\prime}=(\mathit{SV}_{C}\cup\mathit{SV}_{E},S)$, and
there exists at least one such instance.

Note that, despite the name, which is borrowed from [9], the observation
$\mathcal{O}$ is rather an description of the environment behaviour, which is
supposed to be completely known up to the given temporal uncertainty. Usual
definitions of planning problems involve the specification of a maximum bound
on the _horizon_ of the solution plans. For the sake of generality, we omit
this parameter, as it can be expressed by suitable synchronisation rules.

According to Item 3 of Definition 2.8, any instance of a flexible plan
satisfies the synchronisation rules of the problem. However, there is no
guarantee that one such instance exists for each possible instance of the
external timelines. In other words, Definition 2.8 does not guarantee that a
flexible solution plan can be executed in any possible scenario. Thus, a
control strategy is needed to determine how to schedule controllable tasks.
Because of space concerns, we cannot present all the details of the definition
of control strategy, which is thoroughly illustrated in [9]. Informally, it
can be thought of as a function $\sigma$ which chooses how to schedule the
start time of tokens for controlled variables, and the end time of
controllable tokens, during execution. A flexible solution plan $\Pi$ is said
to be _weakly controllable_ if for each possible schedule of tokens for
external variables and of uncontrollable tokens, there is a control strategy
$\sigma$ such that following $\sigma$ during execution results into an
instance of $\Pi$. It is said to be _strongly controllable_ if, conversely, a
single control strategy $\sigma$ exists which results into an instance of
$\Pi$ whatever the schedule of the endpoints under its control by the
environment is. Finally, it is said to be _dynamically controllable_ if the
controlled endpoints can be scheduled by taking into account, at any given
time, only the past history of the execution in such a way that an instance of
$\Pi$ is obtained. Given its generality and wider applicability, dynamic
controllability is definitely the most interesting form of controllability.
Notice that these concepts, whose definition in the context of flexible plans
for timeline-based planning is given in [9], have analogous counterparts in
the context of temporal networks [24].

Timeline-based systems which aim at handling both planning and execution
cannot simply produce flexible plans, but have to ensure a chosen degree of
controllability of the produced plans. As an example, the PLATINUm system [23]
employs a two-phase process where a flexible plan is first produced and then
checked for the existence of a dynamic control strategy. Dynamic
controllability of a flexible plan can be checked, for instance, via a
reduction to timed game automata [8]. Since uncontrollable flexible plans are
not suitable to be executed, the problem is considered to be solved only when
a dynamically controllable flexible solution plan is found, together with its
dynamic control strategy.

##  3\. Limitations of the current approach

The focus of timeline-based systems on temporal reasoning and temporal
uncertainty clearly emerges from the previous section. This focus has its
roots in the history of the paradigm and the typical application scenarios
where timeline-based systems have been employed. The exclusive focus on
temporal uncertainty is especially evident in the treatment of external
variables: their behaviour is supposed to be completely known excepting only
the precise timing of specific events. Consider, for example, a satellite in
orbit doing some measurements and transmitting the results back to Earth. In
such a domain, external variables might be used to represent visibility
windows where the different ground stations can be reached by the satellite.
The precise timing of those windows is uncertain, but everything else is known
(even months) in advance. Nevertheless, to handle the case of a mismatch
between the expected and the observed behaviour of the environment, systems
such as PLATINUm employ a feedback loop where a _failure manager_ is in charge
of triggering, if needed, a _re-planning_ (or plan repair) phase, which should
produce a new flexible plan, with a suitable control strategy, taking into
account the newly acquired observations (the name of the $\mathcal{O}$
component in Definition 2.7 comes from this scenario).

In contrast to domains as the above one, other applications might require to
re-plan more frequently. As an example, in robotics scenarios such as those
discussed in [23], where the planned system interacts with a human agent, one
cannot hope to represent with temporal uncertainty alone all the possible
variability of the behaviour of the external environment. In these scenarios,
most often re-plans get triggered to handle the unpredicted outcomes of
generally nondeterministic choices that the external agents can make, rather
than to fix problems in the domain model. This observation motivates us in
proposing an interpretation of timeline-based problems that is able to handle
both temporal uncertainty and general nondeterminism, extending and
generalising the current approach based on flexible plans.

As a matter of fact, it turns out that the domain description languages
commonly in use, here exemplified by the formal syntax defined in Section 2,
can easily express scenarios where the need to handle general nondeterminism
arise in problems which apparently only involved temporal uncertainty. To see
how this may happen, consider a simple timeline-based planning problem with
uncertainty $P=(\mathit{SV}_{C},\mathit{SV}_{E},S,\mathcal{O})$, with a single
state variable $x$, with $V_{x}=\\{v_{1},v_{2},v_{3}\\}$,
$\mathit{SV}_{E}=\varnothing$, and $S$ consisting of the following
synchronisation rules:

$\displaystyle a[x=v_{1}]\longrightarrow{}$ $\displaystyle\exists
b[x=v_{2}]\mathrel{.}a\leq^{\mathsf{e,s}}_{[0,0]}b\land
a\leq^{\mathsf{s,e}}_{[0,5]}a{}\mathrel{\vee}{}\exists
c[x=v_{3}]\mathrel{.}a\leq^{\mathsf{e,s}}_{[0,0]}c\land
a\leq^{\mathsf{s,e}}_{[6,10]}a$ $\displaystyle\top\longrightarrow{}$
$\displaystyle\exists a[x=v_{1}]\mathrel{.}a=^{\mathsf{s}}0$

Suppose that $D_{x}(v)=[1,10]$ for all $v\in V_{x}$, and that
$\gamma_{x}(v_{1})=\mathsf{u}$ and
$\gamma_{x}(v_{2})=\gamma_{x}(v_{3})=\mathsf{c}$, that is, tokens where
$x=v_{1}$ are uncontrollable. The rules require the execution to start with a
token where $x=v_{1}$, followed by a token where either $x=v_{2}$ or $x=v_{3}$
depending on the duration of the first token. This scenario is, intuitively,
trivial to control. The system must execute $x=v_{1}$ as a first token due to
the second rule. Then, the environment controls its duration, and the system
simply has to wait for the token to end, and then execute either $x=v_{2}$ or
$x=v_{3}$ depending on how long the first token lasted. However, there are no
flexible plans that represent this simple strategy, since each given plan must
fix the value of every token in advance. To guarantee the satisfaction of the
rules, the choice of which value to assign to $x$ on the second token must be
made during the execution, but this is not possible because of the exclusively
sequential nature of flexible plans. In this case, therefore, the problem
would be considered as unsolvable, even if the goals stated by the rules seem
simple to achieve.

The issues discussed here come from the lack of a proper support for general
nondeterminism in the framework of flexible plans. However, the last example
shows that this is not just a missing feature of current systems, but rather a
class of scenarios that can be easily modelled by (the syntax of) timeline-
based description languages but whose solutions are not captured by the
commonly considered semantics. The _timeline-based planning games_ defined in
the next section provide a clean way to express the solution to this kind of
scenario, providing a semantics to timeline-based planning problems with
uncertainty capable of modelling both temporal uncertainty and general
nondeterminism in a uniform way. Moreover, they handle the external variables
in the most general way, without assuming any knowledge of their future
behaviour.

##  4\. Timeline-based planning games

Let us now introduce _timeline-based planning games_. They generalise dynamic
control strategies for flexible plans while suitably handling the limitations
discussed in Section 3.

######  Definition 4.1 (Timeline-based planning game).

A _timeline-based planning game_ is a tuple
$G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$, where
$\mathit{SV}_{C}$ and $\mathit{SV}_{E}$ are the sets of, respectively, the
_controlled_ and the _external_ variables, and $\mathcal{S}$ and $\mathcal{D}$
are two sets of synchronisation rules, respectively called _system_ and
_domain_ rules, involving variables from both $\mathit{SV}_{C}$ and
$\mathit{SV}_{E}$.

Intuitively, a timeline-based planning game
$G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$ is a turn-based,
two-player game played by the controller, Charlie, and the environment, Eve.
By playing the game, the players progressively build the timelines of a
_scheduled plan_ (see Definition 2.4). At each round, each player makes a move
deciding which tokens to start and/or to stop and at which time. Both players
are constrained by the set $\mathcal{D}$ of _domain_ rules, which describe the
basic rules governing the world. Domain rules replace and generalise the
_observation_ $\mathcal{O}$ of Definition 2.7, allowing one to freely model
the interaction between the system and the environment. They are not intended
to be Eve’s (or Charlie’s) _goals_ , but, rather, a background knowledge about
the world that can be assumed to hold at any time. Since neither player can
violate $\mathcal{D}$, the strategy of each player may safely assume the
validity of such rules. In addition, Charlie is responsible for satisfying the
set $\mathcal{S}$ of _system_ rules, which describe the rules governing the
controlled system, including its goals. Charlie wins if, assuming Eve behaves
according to the domain rules, he manages to construct a plan satisfying the
system rules. In contrast, Eve wins if, while satisfying the domain rules, she
prevents Charlie from winning, either by forcing him to violate some system
rule, or by indefinitely postponing the fulfilment of his goals.

Let us now formally describe the way in which a play of a (timeline-based)
planning game evolves. First of all, we observe that at any given time during
the play, the plan will be partially built, waiting for some tokens to be
completed. A _partial plan_ is a plan where the last token on each timeline
may be unfinished (_open_ token). A timeline whose last token is open is
called an _open_ timeline.

######  Definition 4.2 (Open timeline).

Let $G=(SV_{C},SV_{E},\mathcal{S},\mathcal{D})$ be a planning game and let
$SV=SV_{C}\,\cup\,SV_{E}$. An _open token_ for $G$ is a pair $\tau=(x,v)$,
where $x\in\mathit{SV}$ and $v\in V_{x}$. An _open timeline_ for
$x\in\mathit{SV}$ is a non-empty finite sequence of tokens
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k-1},\tau_{k}\rangle$, where
$\langle\tau_{1},\ldots,\tau_{k-1}\rangle$ is a scheduled timeline for $x$ and
$\tau_{k}=(x,v_{k})$ is an open token.

We will refer to tokens and timelines as defined in Definition 2.2 as _closed_
tokens and _closed_ timelines, respectively. In an open timeline
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k}\rangle$, only
$\operatorname{\mathsf{start-time}}(\tau_{k})$ is defined for its last open
token $\tau_{k}$: $\operatorname{\mathsf{start-time}}(\tau_{0})=0$ and
$\operatorname{\mathsf{start-time}}(\tau_{i})=\operatorname{\mathsf{end-
time}}(\tau_{i-1})$ for $i>1$. Recall that $\mathcal{H}(\mathsf{T})$ for a
closed timeline is the $\operatorname{\mathsf{end-time}}$ of its last token
and that $\mathcal{H}(\mathsf{T})=0$ for empty timelines. For an open timeline
$\mathsf{T}=\langle\tau_{1},\ldots,\tau_{k-1},\tau_{k}\rangle$, we define its
horizon as the $\operatorname{\mathsf{end-time}}$ of its last _closed_ token,
$\mathcal{H}(\mathsf{T})=\operatorname{\mathsf{end-time}}(\tau_{k-1})$ (which
is equal to $\operatorname{\mathsf{start-time}}(\tau_{k})$).

######  Definition 4.3 (Partial plan).

Let $G=(SV_{C},SV_{E},\mathcal{S},\mathcal{D})$ be a planning game and let
$SV=SV_{C}\ \cup\ SV_{E}$. A _partial plan_ for $G$ is a pair
$\Pi=(\Gamma,\operatorname{\mathsf{now}})$, where $\Gamma$ is a set of
timelines, either open or closed, one for each $x\in\mathit{SV}$, and
$\operatorname{\mathsf{now}}\in\mathbb{N}$ is the current time, such that:

  1. (1)

$\mathcal{H}(\mathsf{T})<\operatorname{\mathsf{now}}$ for any _open_ timeline
$\mathsf{T}\in\Gamma$;

  2. (2)

$\mathcal{H}(\mathsf{T})=\operatorname{\mathsf{now}}$ for any _closed_
timeline $\mathsf{T}\in\Gamma$;

(a)${x}$${y}$${0}$${0}$${1}$${1}$${3}$${3}$${2}$${2}$${\tau_{1}}$${\tau_{2}}$${\mathsf{now}}$(b)${x}$${y}$${0}$${0}$${1}$${1}$${3}$${3}$${2}$${2}$${\tau_{1}}$${\tau_{2}}$${\tau_{3}}$${\mathsf{now}}$(c)${x}$${y}$${0}$${0}$${1}$${1}$${2}$${2}$${3}$${3}$${\tau_{1}}$${\tau_{2}}$${\tau_{3}}$${\mathsf{now}}$
Figure 2. Examples of partial plans: (a) two tokens for variables $x$ and $y$
where $\operatorname{\mathsf{end-time}}(\tau_{1})=\operatorname{\mathsf{end-
time}}(\tau_{2})=2$ and $\operatorname{\mathsf{now}}=2$; (b)
$\operatorname{\mathsf{end-time}}(\tau_{1})=2$, $\operatorname{\mathsf{end-
time}}(\tau_{2})=1$, while $\tau_{3}$ continues; (c) incorrect partial plan,
because $\tau_{3}$ continues over the end of $\tau_{1}$ and a successor for
$\tau_{1}$ is unspecified.

For a partial plan $\Pi=(\Gamma,\operatorname{\mathsf{now}})$, we write
$\mathsf{T}\in\Pi$ to mean $\mathsf{T}\in\Gamma$, and we define
$\mathcal{H}(\Pi)=\max_{\mathsf{T}\in\Pi}\mathcal{H}(\mathsf{T})$ and
$\operatorname{\mathsf{now}}(\Pi)=\operatorname{\mathsf{now}}$. The set of all
possible partial plans for a given game $G$ is denoted as $\mathbf{\Pi}_{G}$,
or simply $\mathbf{\Pi}$ where $G$ is understood.

Definition 4.3 implies that time cannot advance after the end of a token
without specifying its successor, and ensures that the partial plan has been
built only up to $\operatorname{\mathsf{now}}$. Figure 2 shows an example of
invalid partial plan where a token continues after the end of another and the
successor of the latter is not specified, forming an invalid gap in the
description of the timelines. It also implies that if any empty, thus closed,
timeline is present, then all timelines are empty. Thus, a unique well-defined
_empty_ partial plan exists, which we will denote by $\Pi_{\varnothing}$, with
all empty timelines and $\operatorname{\mathsf{now}}(\Pi_{\varnothing})=0$.

Players incrementally build a partial plan by extending the initially empty
partial plan $\Pi_{\varnothing}$. This is done by means of actions that
specify which tokens to start and/or end.

######  Definition 4.4 (Action).

Let $G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$ be a
planning game and let $SV=SV_{C}\ \cup\ SV_{E}$. An _action_ $\alpha$ for $G$
is a term of the form $\operatorname{\mathsf{start}}(x,v)$ or
$\operatorname{\mathsf{end}}(x,v)$, where $x\in\mathit{SV}$ and $v\in V_{x}$.
The set of actions is partitioned into the set $\mathsf{A}_{C}$ of Charlie’s
actions and the set $\mathsf{A}_{E}$ of Eve’s actions. An action belongs to
$\mathsf{A}_{C}$ (resp., $\mathsf{A}_{E}$) if it is of the form
$\operatorname{\mathsf{start}}(x,v)$, for some $x\in\mathit{SV}_{C}$ (resp.,
$x\in\mathit{SV}_{E}$) and $v\in V_{x}$, or of the form
$\operatorname{\mathsf{end}}(x,v)$, for some $x\in\mathit{SV}$, $v\in V_{x}$,
and $\gamma_{x}(v)=\mathsf{c}$ (resp., $\gamma_{x}(v)=\mathsf{u}$).

Definition 4.4 can be read as follows. When an action
$\operatorname{\mathsf{start}}(x,v)$ or $\operatorname{\mathsf{end}}(x,v)$ is
executed by a player, a token for the variable $x$, where $x=v$, respectively
starts or ends. Ending a task (a token) and starting the next one are two
different actions, even if, as it will be precisely stated later, the end of a
token must be immediately followed by the start of the next one. Depending on
who owns the variable and the involved value, each action can be executed only
by a specific player. More precisely, players can start tokens for the
variables that they own, and end the tokens that hold values that they
control.

It is worth noticing that, in contrast to the original definition of timeline-
based planning problems with uncertainty (Definition 2.7), Definition 4.4
admits cases where $x\in\mathit{SV}_{E}$ and $\gamma_{x}(v)=c$ for some $v\in
V_{x}$, that is, cases where Charlie may control the duration of a variable
that belongs to Eve. This situation is symmetrical to the more common one
where Eve controls the duration of a variable that belongs to Charlie, and
there is no need, in our setting, to impose any asymmetry.

Actions are combined into _moves_ that can start and/or end multiple tokens at
once.

######  Definition 4.5 (Move).

Let $G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$ be a
timeline-based planning game. A  _move_ $\mu$ is a term of the form
$\operatorname{\mathsf{wait}}(t)$ or $\operatorname{\mathsf{play}}(t,A)$,
where $t\in\mathbb{N}$ is the _timestamp_ of the move,
$A\subseteq\mathsf{A}_{C}$ or $A\subseteq\mathsf{A}_{E}$, and for each
$x\in\mathit{SV}_{C}\cup\mathit{SV}_{E}$, _at most one_ action in $A$ involves
$x$. The set of moves is partitioned into the set $\mathsf{M}_{C}$ of
Charlie’s moves and the set $\mathsf{M}_{E}$ of Eve’s moves. A move $\mu$
belongs to $\mathsf{M}_{C}$ if it is either of the form
$\mu=\operatorname{\mathsf{wait}}(t)$ or of the form
$\mu=\operatorname{\mathsf{play}}(t,A)$ and $A\subseteq\mathsf{A}_{C}$, while
it belongs to $\mathsf{M}_{E}$ only if it is of the form
$\mu_{E}=\operatorname{\mathsf{play}}(t,A)$ and $A\subseteq\mathsf{A}_{E}$.

According to Definition 4.5, Charlie can either execute some set of actions
$A$, by playing a $\operatorname{\mathsf{play}}(t,A)$ move, or wait until some
given time $t$, by playing $\operatorname{\mathsf{wait}}(t)$. In contrast, Eve
has a unique kind of move available, , $\operatorname{\mathsf{play}}(t,A)$,
which executes the actions in $A$ at time $t$.

We are now ready to introduce the fundamental notion of round.

######  Definition 4.6 (Round).

A _round_ $\rho$ is a pair of moves
$(\mu_{C},\mu_{E})\in\mathsf{M}_{C}\times\mathsf{M}_{E}$. Let $\Pi$ be a
partial plan. A round $\rho=(\mu_{C},\mu_{E})$ is _applicable_ to $\Pi$ if the
following conditions are met.

  1. (1)

Integrity conditions:

    1. (a)

any action of the form $\operatorname{\mathsf{start}}(x,v)$ is executed by
either $\mu_{C}$ or $\mu_{E}$ if and only if $\mathsf{T}_{x}\in\Pi$ is a
closed timeline;

    2. (b)

for any action of the form $\operatorname{\mathsf{end}}(x,v)$, executed by
$\mu_{C}$ or $\mu_{E}$, either an action $\operatorname{\mathsf{start}}(x,v)$
is being executed by either moves, or $\mathsf{T}_{x}\in\Pi$ is an open
timeline $\mathsf{T}_{x}=\langle\tau_{1},\ldots,\tau_{k}\rangle$ and its open
token is $\tau_{k}=(x,v)$.

  2. (2)

Timing conditions:

    1. (a)

if $\mu_{C}=\operatorname{\mathsf{play}}(t_{C},A_{C})$ and
$\mu_{E}=\operatorname{\mathsf{play}}(t_{E},A_{E})$, then
$t_{C}=t_{E}=\operatorname{\mathsf{now}}(\Pi)$;

    2. (b)

if $\mu_{C}=\operatorname{\mathsf{wait}}(t_{C})$ and
$\mu_{E}=\operatorname{\mathsf{play}}(t_{E},A_{E})$, then
$t_{C}>\operatorname{\mathsf{now}}(\Pi)$ and $t_{E}\leq t_{C}$.

A single move from either player is _applicable_ to $\Pi$ if there exists at
least one move from the other player such that the round combining the two
moves is applicable to $\Pi$.

The conditions that make a round applicable can be interpreted as follows.
Item 1 ensures that the actions played by each move of the round are
consistent with the current state of the timelines in the partial plan. In
particular, a $\operatorname{\mathsf{start}}$ action has to follow a
$\operatorname{\mathsf{end}}$ one, and $\operatorname{\mathsf{start}}$ actions
cannot be played on timelines that are already open. Note that both
$\operatorname{\mathsf{start}}(x,v)$ and $\operatorname{\mathsf{end}}(x,v)$
for the same $x$ and $v$ can be played at the same round, possibly by two
different players, provided that the timeline was previously closed. In this
case, the move builds a token of unitary length (see Definition 4.7). Item 2
constrains the timings of the moves of a round: if Charlie does not wait, then
he has to play immediately, that is, $t_{C}=\operatorname{\mathsf{now}}(\Pi)$;
otherwise, he can wait until an arbitrary future time point $t_{C}$. In both
cases, Eve must play at a timestamp $t_{E}\leq t_{C}$. This restriction has
the following meaning. The advancement of time during the game is determined
mostly by Charlie, who can make it advance one step at the time, by playing at
each round, or skip some time steps at once without playing anything, by
waiting. In both cases, Eve’s moves must specify what the environment is
doing, if anything, in the meantime, hence the requirement that $t_{E}\leq
t_{C}$. If $t_{E}<t_{C}$, then time advances only up to $t_{E}$, so that at
the next round Charlie can timely reply to Eve’s move.

The next definition specifies the effects of players’ moves.

######  Definition 4.7 (Outcome of a round).

Let $\Pi$ be a partial plan and $\rho=(\mu_{C},\mu_{E})$ be an applicable
round. The _outcome_ of the application of $\rho$ to $\Pi$ is a partial plan
$\rho(\Pi)$, which is obtained from $\Pi$ by applying the following ordered
sequence of steps:

  1. (1)

for each $\mu\in\\{\mu_{C},\mu_{E}\\}$, if
$\mu=\operatorname{\mathsf{play}}(t,A)$, then, for any
$\operatorname{\mathsf{start}}(x,v)\in A$, an open token $\tau=(x,v)$ is
appended to $\mathsf{T}_{x}$;

  2. (2)

for each $\mu\in\\{\mu_{C},\mu_{E}\\}$, if
$\mu=\operatorname{\mathsf{play}}(t,A)$, then, for any
$\operatorname{\mathsf{end}}(x,v)\in A$, the last open token $\tau=(x,v)$ of
$\mathsf{T}_{x}$ (possibly added at the previous step) is replaced by a closed
token $\tau^{\prime}=(x,v,d)$, where $d=t-\operatorname{\mathsf{start-
time}}(\tau)+1$;

  3. (3)

$\operatorname{\mathsf{now}}(\rho(\Pi))=\min(t_{C},t_{E})+1$, where either
$\mu_{C}=\operatorname{\mathsf{play}}(t_{C},A_{C})$ or
$\mu_{C}=\operatorname{\mathsf{wait}}(t_{C})$, and
$\mu_{E}=\operatorname{\mathsf{play}}(t_{E},A_{E})$.

The effects of $\operatorname{\mathsf{start}}$ and
$\operatorname{\mathsf{end}}$ actions are defined in Items 1 and 2,
respectively. The steps are intended to be applied one after the other in
order to handle the case where both $\operatorname{\mathsf{start}}(x,v)$ and
$\operatorname{\mathsf{end}}(x,v)$ are played in the same round. Time advances
according to Item 3, depending on the timestamps of the moves. Note that if no
$\operatorname{\mathsf{wait}}$ move is played, the new current time
corresponds to the horizon of the resulting partial plan.

A play of a planning game is just a sequence of rounds applied to the empty
plan $\Pi_{\varnothing}$.

######  Definition 4.8 (Play).

Let $G$ be a planning game and $\Pi_{0}$ be a partial plan (we call it an
initial partial plan). A _play_ for $G$ from $\Pi_{0}$ is a sequence
$\overline{\rho}=\langle\rho_{0},\ldots,\rho_{k}\rangle$ of rounds such that
$\rho_{0}$ is applicable to $\Pi_{0}$ and $\rho_{i+1}$ is applicable to
$\Pi_{i+1}=\rho_{i}(\Pi_{i})$, for $1\leq i<k$.

Let $\overline{\rho}=\langle\rho_{0},\ldots,\rho_{k}\rangle$ be a play and
$\Pi$ be a partial plan. We denote by
$\overline{\rho}(\Pi)=\rho_{k}(\ldots\rho_{0}(\Pi))$ the _outcome_ of
$\overline{\rho}$ applied to $\Pi$. Where the initial partial plan is not
mentioned, it is understood that the play is applied to $\Pi_{\varnothing}$.
Each non-empty partial plan $\Pi$ can be _closed_ to form a scheduled plan
$\Pi^{\prime}$ (see Definition 2.4) by closing all the open tokens of open
timelines at time $\operatorname{\mathsf{now}}(\Pi)$. In the following, when
the context is clear, we will interchangeably speak of a partial plan as a
scheduled plan by implicitly referring to its closure. It can be easily
checked that rounds as specified in Definition 4.5 suffice to build any
possible scheduled plan over the game variables, for any partial plan $\Pi$,
there exists a play $\overline{\rho}$ such that
$\Pi=\overline{\rho}(\Pi_{\varnothing})$.

######  Definition 4.9 (Strategy for Charlie).

A _strategy for Charlie_ is a function
$\sigma_{C}:\mathbf{\Pi}\to\mathsf{M}_{C}$ that maps any given partial plan
$\Pi$ to a move $\mu_{C}$ applicable to $\Pi$.

######  Definition 4.10 (Strategy for Eve).

A _strategy for Eve_ is a function
$\sigma_{E}:\mathbf{\Pi}\times\mathsf{M}_{C}\to\mathsf{M}_{E}$ that, given a
partial plan $\Pi$ and Charlie’s move $\mu_{C}$ applicable to $\Pi$, returns
the next Eve’s move $\mu_{E}$ such that $\rho=(\mu_{C},\mu_{E})$ is applicable
to $\Pi$.

A play $\overline{\rho}$ is said to be _played according to_ a strategy
$\sigma_{C}$ for Charlie, starting from some initial partial plan $\Pi_{0}$,
if $\rho_{i}=(\sigma_{C}(\Pi_{i-1}),\mu_{E}^{i})$, for some $\mu_{E}^{i}$, for
all $0<i<|\overline{\rho}|$, and to be played according to a strategy
$\sigma_{E}$ for Eve if
$\rho_{i}=(\mu_{C}^{i},\sigma_{E}(\Pi_{i-1},\mu_{C}^{i}))$, for all
$0<i<|\overline{\rho}|$. For any pair of strategies $(\sigma_{C},\sigma_{E})$
and any $k\geq 0$, there is a unique run
$\overline{\rho}_{k}(\sigma_{C},\sigma_{E})$ of length $k$ played according to
$\sigma_{C}$ and $\sigma_{E}$.

It is worth to note that, according to our definition of strategy, Charlie can
base his decisions only on the previous rounds of the game, not including
Eve’s move at the current round. Together with the fact that time strictly
increases of at least one time unit at each round, this implies that Charlie
has to wait at least one time unit to react to a move by Eve. This models the
realistic assumption that the _sense-reason-react_ loop of the controller
needs a finite amount of time to be executed, and is coherent with the
semantics of dynamic control strategies of flexible plans from [9].

Let $G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$ be a
planning game. We define two timeline-based planning problems,
$P_{\mathcal{D}}=(\mathit{SV},\mathcal{D})$ and
$P_{G}=(\mathit{SV},\mathcal{D}\cup\mathcal{S})$, for $G$. A partial plan is
_admissible_ if it is a solution plan for $P_{\mathcal{D}}$, and _successful_
if it is a solution plan for $P_{G}$. Similarly a play $\overline{\rho}$ is
admissible or successful if its outcome $\overline{\rho}(\Pi_{\varnothing})$
is, respectively, admissible or successful.

######  Definition 4.11 (Admissible strategy for Eve).

A strategy $\sigma_{E}$ for Eve is _admissible_ if for each strategy
$\sigma_{C}$ for Charlie, there is a $k\geq 0$ such that the play
$\overline{\rho}_{k}(\sigma_{C},\sigma_{E})$ is admissible.

######  Definition 4.12 (Winning strategy for Charlie).

Let $\sigma_{C}$ be a strategy for Charlie. We say that $\sigma_{C}$ is a
_winning strategy_ for Charlie if for any _admissible_ strategy $\sigma_{E}$
for Eve, there exists an $n\geq 0$ such that the play
$\overline{\rho}_{n}(\sigma_{C},\sigma_{E})$ is successful.

We say that Charlie _wins_ the game $G$ if he has a winning strategy, while
Eve _wins_ the game if such a strategy does not exist. Let us consider again
the problem described in Section 3 to show a simple winning strategy. The
problem can be viewed as a game with the rules in Fig. 1 belonging to
$\mathcal{S}$ and $\mathcal{D}$ empty. After playing
$\operatorname{\mathsf{start}}(x,v_{1})$ at the beginning, Charlie only has to
wait for Eve to play $\operatorname{\mathsf{end}}(x,v_{1})$, and then play
$\operatorname{\mathsf{start}}(x,v_{2})$ or
$\operatorname{\mathsf{start}}(x,v_{3})$ according to the current timestamp.

A more involved example can be obtained by considering two variables
$x\in\mathit{SV}_{C}$ and $y\in\mathit{SV}_{E}$, with
$V_{x}=V_{y}=\\{go,stop\\}$, unit duration, and rules as follows.

$\mathcal{S}=${2*a[x=stop]${}\longrightarrow{}$∃b[y=stop] .b $\leq$^e,s_[0,0]
a}2*⊤${}\longrightarrow{}$∃a[x=stop] .⊤$\mathcal{D}$
={⊤${}\longrightarrow{}$∃a[y=stop] .⊤}

Here, Charlie’s ultimate goal is to realise $x=stop$, but this can only happen
after Eve realised $y=stop$. This is guaranteed to happen, since we consider
only admissible strategies. Hence, the winning strategy for Charlie only
chooses $x=go$ until Eve chooses $y=stop$, and then wins by executing
$x=stop$. If $\mathcal{D}$ was instead empty, a winning strategy would not
exist since a strategy that never chooses $y=stop$ would be admissible. This
would therefore be a case where Charlie looses because Eve can indefinitely
postpone his victory.

Let us compare now the concept of _dynamic controllability_ of flexible plans,
as defined in [9], with the existence of winning strategies for timeline-based
planning games, and show the greater generality of the latter concept.

The first step is to back the claim of this greater generality. Indeed, it can
be shown that for any timeline-based planning problem with uncertainty
$P=(\mathit{SV}_{C},\mathit{SV}_{E},S,\mathcal{O})$ there is an _associated
timeline-based planning game_
$G_{P}=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{D},\mathcal{S})$, such that a
dynamically controllable flexible solution plan for $P$ gives us a winning
strategy for $\mathcal{G}$. To this aim, we need a way to represent as a game
any given planning problem with uncertainty. Intuitively, this can be done by
encoding the observations $\mathcal{O}$ into suitable domain rules. The game
associated with a problem therefore mimics the exact setting described by the
problem. What follows shows that such a game does indeed exist, and that there
is a close relationship between its winning strategies and the dynamically
controllable flexible plans for the problem.

theoremplanstostrategiesthm Let $P$ be a timeline-based planning problem with
uncertainty. If $P$ admits a _dynamically controllable flexible solution plan_
, then Charlie has a winning strategy for the associated timeline-based
planning game $G_{P}$.

Definition 4.12 shows that the proposed framework can represent any timeline-
based planning problem with uncertainty, and that the notion of winning
strategy for a game subsumes that of dynamically controllable flexible plan.
Moreover, it can be seen that the game setting is strictly more expressive,
there are cases where no dynamically controllable flexible plans exist, but a
winning strategy can be found. This is the case with the example problem
discussed in Section 3, which has an easy winning strategy when seen as a
game, while it has no dynamically controllable flexible plan. Therefore, one
can prove the following theorem.

theoremnoplansthm There exists a timeline-based planning problem with
uncertainty $P=(\mathit{SV}_{C},\mathit{SV}_{E},S,\mathcal{O})$ such that
there are no dynamically controllable flexible plans for $P$, but Charlie has
a winning strategy for the associated planning game $G_{P}$.

##  5\. Decidability and complexity

A natural question about timeline-based planning games is whether a winning
strategy for a given game can effectively be found. In this section, we
positively answer the question, showing that a winning strategy, if it exists,
can be found with an algorithm that runs in doubly exponential time. Proofs
are omitted because of space concerns, but are available in Gigante’s Ph.D.
thesis [Gigante19].

The proposed algorithm makes use of the concept of _concurrent game structure_
(CGS) [2], in particular, of the specific subclass of _turn-based synchronous
game structures_ (simply _game structures_ , from now on), that, in the case
of two players only, can be defined as follows.

######  Definition 5.1 (Turn-based synchronous game structure [2]).

A _turn-based synchronous game structure_ is a tuple
$S=(Q_{1},Q_{2},M_{1},M_{2},\mathcal{P},\pi,\delta_{C},\delta_{E})$, where:

  1. (1)

$Q_{1}$ and $Q_{2}$ are the finite sets of _states_ belonging to Player 1 and
Player 2, respectively;

  2. (2)

$M_{1}$ and $M_{2}$ are the finite sets of _moves_ available to Player 2 and
Player 2, respectively;

  3. (3)

$\mathcal{P}$ is a finite set of _proposition letters_ ;

  4. (4)

$\pi:Q_{1}\cup Q_{2}\to 2^{\mathcal{P}}$ provides the set of proposition
letters that hold at any given state;

  5. (5)

$\delta_{1}:Q_{1}\times M_{1}\times Q_{2}$ and $\delta_{2}:Q_{2}\times
M_{2}\times Q_{1}$ are the _transition relations_ , that specify the states
reachable from a given one by applying a move by either player.

We proceed in two steps. We first provide a suitable encoding of a timeline-
based planning game $G$ into a corresponding game structure, and then we
exploit existing machinery for ATL* model checking [2] to find a winning
strategy for $G$.

Let us focus on the first step. To encode a timeline-based planning game into
a game structure, one may think of interpreting partial plans as states,
marking with some proposition letter $d$ those which satisfy the domain rules
and with $w$ those where the system rules are satisfied. However, such an
encoding can, in principle, lead to an infinite state space, as the number of
possible partial plans is infinite: the set of moves available to each player
is infinite, as they specify a timestamp; moreover, at any given time, a rule
triggered by one of the current tokens may require to look arbitrarily back in
the past in order to check (the possibility of) its satisfaction. We now show
how to constrain the state space to be finite.

First of all, we observe that arbitrarily large timestamps can only be
introduced by $\operatorname{\mathsf{wait}}$ moves played by Charlie, as the
timestamp of any $\operatorname{\mathsf{play}}$ move played by Charlie is
forced to be equal to $\operatorname{\mathsf{now}}$ and the timestamp of any
Eve’s move is bounded by the one of a Charlie’s move. Now, even though
$\operatorname{\mathsf{wait}}$ moves are useful for Charlie to skip a given
amount of time without executing a sequence of empty
$\operatorname{\mathsf{play}}$ moves, they can always be replaced by such a
sequence, and thus it can be easily shown that if a winning strategy exists,
another one exists which does not use any $\operatorname{\mathsf{wait}}$ move.
Hence, w.l.o.g., we can safely restrict ourselves to a _finite_ set of moves
of form $\operatorname{\mathsf{play}}(t,A)$, with
$t=\operatorname{\mathsf{now}}$.

$a[x=v_{a}]\longrightarrow\exists
b[x=v_{b}]c[x=v_{c}]d[x=v_{d}]e[x=v_{e}]\mathrel{.}b\leq^{\mathsf{e,s}}_{[0,3]}a\land
c\leq^{\mathsf{e,s}}_{[0,+\infty]}b\land d\leq^{\mathsf{s,s}}_{[0,5]}c\land
e\leq^{\mathsf{s,e}}_{[0,5]}d$

(a)${\leq\operatorname{\mathsf{w}}(G)}$${v_{a}}$${v_{b}}$${v_{c}}$${v_{d}}$${v_{e}}$${\leq\operatorname{\mathsf{w}}(G)}$(b)${\leq\operatorname{\mathsf{w}}(G)}$${v_{a}}$${v_{b}}$${d\leq^{\mathsf{s,s}}_{[0,5]}c\land
e\leq^{\mathsf{s,e}}_{[0,5]}d}$${\operatorname{\mathsf{now}}}$

Figure 3. How to represent the distant history of a play of a game $G$ in a
compact way: (a) the complete description of the timeline; and (b) the compact
description of the distant history.

Let us focus now on the partial plans to show that not every single detail of
their distant past has to be remembered. Consider a timeline-based planning
game $G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$, and let
the _window_ of $G$, $\operatorname{\mathsf{w}}(G)$, be the product of all the
non-zero lower and upper bounds appearing in any bounded atom of any rule, and
all the non-zero lower and upper bounds on the length of tokens of any state
variable. The window of the game gives a coarse upper bound on how far from a
given point a chain of bounded atoms can look, which is a fundamental
parameter of any timeline-based planning problem, it has been exploited in
[16] to study the complexity of the plan existence problem.

For the sake of clarification, consider the above half of Figure 3, which
shows a timeline satisfying a particular synchronisation rule. The
satisfaction of bounded and unbounded atoms of the rule by tokens are
represented by solid and dashed arrows, respectively. The depicted tokens can
be partitioned in two blocks, which satisfy two different groups of bounded
atoms. Once the first group has been witnessed, only its existence need to be
remembered, not the precise position or length of its tokens, since any
bounded atom involving the trigger cannot be affected by anything farther than
the window $\operatorname{\mathsf{w}}(G)$. Hence, while the events happening
at most $\operatorname{\mathsf{w}}(G)$ time steps before
$\operatorname{\mathsf{now}}$ need to be remembered in detail, the
satisfaction of the other group of atoms can be remembered symbolically as
shown in the bottom half of Figure 3, by remembering the existence of the
tokens satisfying each required group of atoms, and their relative ordering.
The same has to be done to remember future requests triggered by tokens
appeared in the past.

It can be easily checked that
$\operatorname{\mathsf{w}}(G)\in\mathcal{O}(2^{|G|})$, and that the number of
bits needed to store the succinct representation of the history and of future
requests is exponential as well. Hence, we can build a data structure of size
at most _exponential_ in the size of $G$, that, during the whole play, can be
used to represent the current state and the past history of the game.

Let $\Pi$ be a partial plan. We denote by $[\Pi]$ its succinct representation,
and by $[\mathbf{\Pi}_{G}]$ the set of the succinct representations of all the
possible partial plans on $G$. For any round $\rho$, we can easily specify its
application to the succinct representation of a partial plan in such a way
that $\rho([\Pi])=[\rho(\Pi)]$. Similarly, given $[\Pi]$, we can easily check
whether $\Pi$ is a solution plan for a given timeline-based planning problem.

We are now ready to define the _game structure_ $\mathcal{G}$ associated with
a planning game $G$.

######  Definition 5.2 (Game structure for a planning game).

Let $G=(\mathit{SV}_{C},\mathit{SV}_{E},\mathcal{S},\mathcal{D})$ be a
timeline-based planning game. The corresponding game structure $\mathcal{G}$
is a tuple $(Q_{C},Q_{E},M_{C},$
$M_{E},\mathcal{P},\pi,\delta_{C},\delta_{E})$, where:

  1. (1)

$Q_{C}=[\mathbf{\Pi}_{G}]$ and
$Q_{E}\subseteq[\mathbf{\Pi}_{G}]\times\mathsf{M}_{C}$;

  2. (2)

$M_{C}=\mathsf{M}_{C}$ and $M_{E}=\mathsf{M}_{E}$;

  3. (3)

$\mathcal{P}=\\{d,w\\}$, where $d$ and $w$ are proposition letters,

  4. (4)

$\pi(q_{E})=\varnothing$, for any $q_{E}\in Q_{E}$, and $d\in\pi([\Pi])$
(resp., $w\in\pi([\Pi])$ if and only if $\Pi$ is a solution plan for
$P_{\mathcal{D}}$ (resp., $P_{G}$);

  5. (5)

$([\Pi],\mu_{C},([\Pi],\mu_{C}))\in\delta_{C}$ if and only if
$\mu_{C}=\operatorname{\mathsf{play}}(t,A)$ is applicable to $\Pi$ and
$t=\operatorname{\mathsf{now}}$;

  6. (6)

$(([\Pi],\mu_{C}),\mu_{E},[\Pi^{\prime}])\in\delta_{E}$ if and only if
$\rho=(\mu_{C},\mu_{E})$ is applicable to $\Pi$ and
$\rho([\Pi])=[\Pi^{\prime}]$.

The winning condition for Charlie (see Definition 4.12) can be expressed by
means of the following ATL* formula, where Player 1 is interpreted as Charlie
and Player 2 as Eve:222ATL* is a branching-time temporal logic similar to
CTL*, that allows one to quantify over the strategies of the different players
of a game structure and to differentiate between paths played according to
those strategies.

$\varphi\equiv\langle\\!\langle
1\rangle\\!\rangle\bigl{(}\operatorname{\mathsf{F}}d\to\operatorname{\mathsf{F}}(d\land
w)\bigr{)}$

The formula asks for the existence of a strategy $\sigma_{C}$ for Charlie
($\langle\\!\langle 1\rangle\\!\rangle$) such that, for all paths played
according to $\sigma_{C}$, if the path is played according to an admissible
strategy for Eve ($\operatorname{\mathsf{F}}d$), then there is a future point
where $d\land w$ holds ($\operatorname{\mathsf{F}}(d\land w)$), Charlie wins.
By applying known ATL* model-checking algorithms on the game structure
encoding the planning game and the above formula, one may solve the problem.

It can be proved that any strategy satisfying the above ATL* formula
corresponds to a winning strategy for Charlie on the original timeline-based
planning game. The proposed compact representation of partial plans has
exponential size, and thus the game structure has a doubly exponential number
of states. Since ATL* model-checking of fixed-size formulae over game
structures is -complete [2], the following theorem holds.

######  Theorem 5.3.

Let $G$ be a timeline-based planning game. The problem of establishing whether
Charlie has a winning strategy on $G$ belongs to 2EXPTIME.

##  6\. Conclusions and future work

This paper defines _timeline-based planning games_ , a novel game-theoretic
approach to timeline-based planning with uncertainty. Unlike current
formulations based on dynamic controllability of flexible plans, the proposed
one can uniformly deal with both temporal uncertainty and general
nondeterminism, and it is strictly more expressive. We showed that a winning
strategy can be found in doubly exponential time. Whether there exists a
matching complexity lower bound, how to synthesise a finite-state machine
implementing such a strategy, and how hard the synthesis problem is are still
open issues.

## References

  * [1] J. F. Allen.  Maintaining Knowledge about Temporal Intervals.  Communications of the ACM, 26(11):832–843, 1983.
  * [2] Rajeev Alur, Thomas A. Henzinger, and Orna Kupferman.  Alternating-time Temporal Logic.  Journal of the ACM, 49(5):672–713, 2002.
  * [3] 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 Platform for AI Planning, Scheduling, Constraint Programming, and Optimization.  In Proc. of the 4th International Competition on Knowledge Engineering for Planning and Scheduling, 2012.
  * [4] M. Beetz and D. McDermott.  Improving robot plans during their execution.  In Proc. of the International Conference on Artificial Intelligence Planning Systems (AIPS), 1994.
  * [5] S. Borgo, A. Cesta, A. Orlandini, and A. Umbrico.  A Planning-Based Architecture for a Reconfigurable Manufacturing System.  In Proc. of the 26th International Conference on Automated Planning and Scheduling, pages 358–366, 2016.
  * [6] A. Camacho, E. Triantafillou, C. Muise, J. A. Baier, and S. A. McIlraith.  Non-deterministic planning with temporally extended goals: LTL over finite and infinite traces.  In Proc. of the 31st AAAI Conference on Artificial Intelligence, 2017.
  * [7] 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 21st Conference on Innovative Applications of Artificial Intelligence, pages 66–71, 2009.
  * [8] M. Cialdea Mayer and A. Orlandini.  An Executable Semantics of Flexible Plans in Terms of Timed Game Automata.  In Proc. of the 22nd International Symposium on Temporal Representation and Reasoning, pages 160–169, 2015.
  * [9] M. Cialdea Mayer, A. Orlandini, and A. Umbrico.  Planning and Execution with Flexible Timelines: a Formal Account.  Acta Informatica, 53(6-8):649–680, 2016.
  * [10] A. Cimatti, M. Do, A. Micheli, M. Roveri, and D. E. Smith.  Strong temporal planning with uncontrollable durations.  Artificial Intelligence, 256:1 – 34, 2018.
  * [11] A. Cimatti, A. Micheli, and M. Roveri.  Timelines with Temporal Uncertainty.  In Proc. the 27th AAAI Conference on Artificial Intelligence, 2013.
  * [12] A. Cimatti, M. Pistore, M. Roveri, and P. Traverso.  Weak, strong, and strong cyclic planning via symbolic model checking.  Artificial Intelligence, 147(1):35 – 84, 2003.
  * [13] M. Fox and D. Long.  PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.  Journal of Artificial Intelligence Research, 20:61–124, 2003.
  * [14] J. Frank.  What is a timeline?  In Proc. of the 4th Workshop on Knowledge Engineering for Planning and Scheduling, pages 31–38, 2013.
  * [15] N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini.  Timelines are Expressive Enough to Capture Action-based Temporal Planning.  In Proc. of the 23rd International Symposium on Temporal Representation and Reasoning, pages 100–109, 2016.
  * [16] N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini.  Complexity of timeline-based planning.  In Proc. of the 27th International Conference on Automated Planning and Scheduling, pages 116–124, 2017.
  * [17] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra.  Planning and acting in partially observable stochastic domains.  Artificial Intelligence, 101(1):99 – 134, 1998.
  * [18] C. Muise, S. A. McIlraith, and J. C. Beck.  Improved non-deterministic planning by exploiting state relevance.  In Proc. of the 22nd International Conference on Automated Planning and Scheduling, 2012.
  * [19] C. Muise, S.A. McIlraith, and V. Belle.  Non-deterministic planning with conditional effects.  In Proc. of the 24th International Conference on Automated Planning and Scheduling, 2014.
  * [20] N. Muscettola.  HSTS: Integrating Planning and Scheduling.  In Monte Zweben and Mark S. Fox, editors, Intelligent Scheduling, chapter 6, pages 169–212. Morgan Kaufmann, 1994.
  * [21] F. Patrizi, N. Lipovetzky, and H. Geffner.  Fair LTL synthesis for non-deterministic systems using strong cyclic planners.  In Proc. of the 23rd International Joint Conference on Artificial Intelligence, 2014.
  * [22] S. Steel.  Action under uncertainty.  Journal of Logic and Computation, 4(5):767–795, 1994.
  * [23] A. Umbrico, A. Cesta, M. Cialdea Mayer, and A. Orlandini.  PLATINUm: A New Framework for Planning and Acting in Human-Robot Collaborative Scenarios.  In Proc. of the 16th International Conference of the Italian Association for Artificial Intelligence, pages 498–512, 2017\.
  * [24] T. Vidal and H. Fargier.  Handling Contingency in Temporal Constraint Networks: from Consistency to Controllabilities.  Journal of Experimental and Theoretical Artificial Intelligence, 11(1):23–45, 1999.