=Paper=
{{Paper
|id=Vol-2243/paper11
|storemode=property
|title=Timeline-Based Planning over Dense Temporal Domains with Trigger-less Rules is NP-Complete
|pdfUrl=https://ceur-ws.org/Vol-2243/paper11.pdf
|volume=Vol-2243
|authors=Laura Bozzelli,Alberto Molinari,Angelo Montanari,Adriano Peron,Gerhard Woeginger
|dblpUrl=https://dblp.org/rec/conf/ictcs/BozzelliMMPW18
}}
==Timeline-Based Planning over Dense Temporal Domains with Trigger-less Rules is NP-Complete==
https://ceur-ws.org/Vol-2243/paper11.pdf
Timeline-Based Planning over Dense Temporal
Domains with Trigger-less Rules is
NP-Complete?
Laura Bozzelli1 , Alberto Molinari2 , Angelo Montanari2 , Adriano Peron1 , and
Gerhard Woeginger3
1
University of Napoli “Federico II”, Napoli, Italy
lr.bozzelli@gmail.com, adrperon@unina.it
2
University of Udine, Udine, Italy
molinari.alberto@gmail.com, angelo.montanari@uniud.it
3
RWTH-Aachen University, Aachen, Germany
woeginger@algo.rwth-aachen.de
Abstract. In timeline-based planning—an approach which is more de-
clarative than standard, action-based planning—the domain is described
by a finite set of independent, but interacting, state variables. The tem-
poral behavior of each variable is governed by a transition function, and
the sequence of values it takes over time is represented by a timeline. A
set of temporal constraints, called synchronization rules, impose suitable
conditions on the evolution of the values of variables.
The temporal domain is commonly assumed to be discrete, and the dense
case is dealt with by introducing an artificial discretization. Here, we
address the problem of timeline-based planning over dense temporal
domains, without discretizing them. However, since the unrestricted
version of the problem has been recently proved to be undecidable, we
focus on the case in which all synchronization rules are trigger-less, and
prove its NP-completeness.
Keywords: Timeline-Based Planning · Computational Complexity ·
Timed Automata · NP-completeness.
1 Introduction
In this paper, we study the problem of timeline-based planning. Unlike the
standard action-based planning, that focuses on the series of actions an agent
has to perform to reach a goal from the initial state of the world, timeline-based
one describes in a more declarative fashion what has to happen in order to
satisfy the goal. The domain is represented by a set of state variables, each one
?
The work by Bozzelli, Molinari, Montanari, and Peron has been supported by the
GNCS project Formal methods for verification and synthesis of discrete and hybrid
systems. The work by Molinari and Montanari has also been supported by the project
(PRID) ENCASE—Efforts in the uNderstanding of Complex interActing SystEms.
2 L. Bozzelli et al.
modeling a component. State variables are independent of each other, but a
set of synchronization rules constrain the temporal relations among them. The
evolution of the value of each state variable over time is controlled by a transition
function, and described by means of a timeline (a sequence of tokens).
Timeline-based planning has been applied in several contexts [2,4,5,10], but a
systematic study of its expressiveness and complexity has been undertaken only
recently. The temporal domain is typically assumed to be discrete; the dense
case is commonly dealt with by forcing a discretization of the domain. In [7,8]
Gigante et al. proved that timeline-based planning is EXPSPACE-complete.
In this paper, we address the timeline-based planning problem over dense
temporal domains, without resorting to any form of discretization. Since the
problem in its full generality is known to be undecidable over dense domains [3],
we restrict ourselves to a constrained form of synchronization rules, namely,
trigger-less ones, and give an optimal NP planning algorithm for this case.
Organization of the paper. In Section 2, we give some background knowledge
about timeline-based planning. Then, we show that if we allow only trigger-less
synchronization rules, the problem is decidable (unlike the general case). First,
in Section 3 we provide a PSPACE algorithm by encoding planning instances
into timed automata. Next, by exploiting a pair of fundamental bounds on
plans obtained from timed automata, in Section 4 we prove that timeline-based
planning with trigger-less rules is in fact NP-complete: we give an NP algorithm
and then a matching complexity lower bound. Conclusions give an assessment of
the achieved results and outline future research themes.
2 The Timeline-Based Planning Problem
In this section, we give an account of timeline-based planning (TP). We refer the
reader to [6,7] for details. Let N, R+ , and Q+ denote the naturals, non-negative
reals, and non-negative rationals, respectively. Let Intv be the set of intervals in
R+ whose endpoints are in Q+ ∪ {∞}.
In TP, domain knowledge is encoded by a set of state variables, whose behaviour
over time is described by transition functions and synchronization rules.
Definition 1. A state variable x is a triple x = (Vx , Tx , Dx ), where Vx is the
finite domain of the variable x, Tx : Vx → 2Vx is the value transition function,
which maps each v ∈ Vx to the (possibly empty) set of successor values, and
Dx : Vx → Intv is the constraint function that maps each v ∈ Vx to an interval.
A token for a variable x is a pair (v, d) consisting of a value v ∈ Vx and
a duration d ∈ R+ such that d ∈ Dx (v). Intuitively, a token for x represents
an interval of time where x takes value v. In the following we will also denote
(v, d) as (x, v, d) to make x explicit. The behavior of x is specified by means
of a timeline which is a non-empty sequence of tokens π = (v0 , d0 ) · · · (vn , dn )
consistent with Tx , i.e., vi+1 ∈ Tx (vi ) for all 0 ≤ i < n. The start time s(π, i) and
Trigger-Less Timeline-Based Planning on Dense Domains is NP-Complete 3
the end time e(π, i) of the i-th token (0 ≤ i ≤ n) of the timeline π are defined as
Pi Pi−1
e(π, i) = h=0 dh and s(π, i) = 0 if i = 0, and s(π, i) = h=0 dh otherwise.
Given a finite set SV of state variables, a multi-timeline of SV is a mapping
Π assigning to each state variable x ∈ SV a timeline for x. Multi-timelines of
SV can be constrained by a set of synchronization rules, which relate tokens,
possibly belonging to different timelines, through temporal constraints on the
start/end times of tokens (time-point constraints) and on the difference between
start/end times of tokens (interval constraints). The synchronization rules exploit
an alphabet Σ = {o, o0 , . . .} of token names to refer to the tokens along a
multi-timeline, and are based on the notions of atom and existential statement.
Definition 2. An atom is either a clause of the form o1 ≤eI1 ,e2 o2 (interval
atom), or of the forms o1 ≤eI1 t or o1 ≥eI1 t (time-point atom), where o1 , o2 ∈ Σ,
I ∈ Intv , t ∈ Q+ , and e1 , e2 ∈ {s, e}.
An atom ρ is evaluated with respect to a Σ-assignment λΠ for a given
multi-timeline Π which is a mapping assigning to each token name o ∈ Σ a pair
λΠ (o) = (π, i) such that π is a timeline of Π and 0 ≤ i < |π| is a position along
π (intuitively, (π, i) represents the token of Π referenced by the name o). An
interval atom o1 ≤eI1 ,e2 o2 is satisfied by λΠ if e2 (λΠ (o2 )) − e1 (λΠ (o1 )) ∈ I. A
point atom o ≤eI t (resp., o ≥eI t) is satisfied by λΠ if t − e(λΠ (o)) ∈ I (resp.,
e(λΠ (o)) − t ∈ I).
Definition 3. An existential statement E for a finite set SV of state variables
is a statement of the form E := ∃o1 [x1 = v1 ] · · · ∃on [xn = vn ].C, where C is a
conjunction of atoms, oi ∈ Σ, xi ∈ SV , and vi ∈ Vxi for each i = 1, . . . , n.
The elements oi [xi = vi ] are called quantifiers. A token name used in C, but
not occurring in any quantifier, is said to be free. Given a Σ-assignment λΠ
for a multi-timeline Π of SV , we say that λΠ is consistent with the existential
statement E if for each quantified token name oi , we have λΠ (oi ) = (π, h) where
π = Π(xi ) and the h-th token of π has value vi . A multi-timeline Π of SV
satisfies E if there exists a Σ-assignment λΠ for Π consistent with E such that
each atom in C is satisfied by λΠ .
Definition 4. A synchronization rule R for a finite set SV of state variables is a
rule of one of the forms o0 [x0 = v0 ] → E1 ∨ E2 ∨ . . . ∨ Ek , or > → E1 ∨ E2 ∨ . . . ∨ Ek ,
where o0 ∈ Σ, x0 ∈ SV , v0 ∈ Vx0 , and E1 , . . . , Ek are existential statements. In
rules of the first form (trigger rules), the quantifier o0 [x0 = v0 ] is called trigger,
and we require that only o0 may appear free in Ei (for i = 1, . . . , n). In rules of
the second form (trigger-less rules), we require that no token name appears free.
Intuitively, a trigger o0 [x0 = v0 ] acts as a universal quantifier, which states
that for all the tokens of the timeline for the state variable x0 , where x0 takes the
value v0 , at least one of the existential statements Ei must be satisfied. Trigger-less
rules simply assert the satisfaction of some existential statement.
The semantics of synchronization rules is formally defined as follows.
4 L. Bozzelli et al.
Definition 5. Let Π be a multi-timeline of a set SV of state variables. Given a
trigger-less rule R of SV , Π satisfies R if Π satisfies some existential statement
of R. Given a trigger rule R of SV with trigger o0 [x0 = v0 ], Π satisfies R if for
every position i of the timeline π = Π(x0 ) for x0 such that π(i) = (v0 , d), there
is an existential statement E of R and a Σ-assignment λΠ for Π consistent with
E such that λΠ (o0 ) = (π, i) and λΠ satisfies all the atoms of E.
A TP domain P = (SV, S) is specified by a finite set SV of state variables
and a finite set S of synchronization rules modeling their admissible behaviors.
Trigger-less rules can be used to express initial and intermediate conditions, and
the goals of the problem, while trigger rules are useful to specify invariants and
response requirements. A plan for P is a multi-timeline of SV satisfying all the
rules in S. The end time of the token ending last in P is said the horizon of P .
The TP problem is to decide if, given a TP domain P , there is a plan for P .
3 Timed Automata and Finite Bounds for Plans
TP over dense temporal domains is, in its full generality, undecidable [3]. However,
if we restrict to trigger-less synchronization rules only, we get a decidable (in fact,
NP-complete) problem. To show this, we start by encoding planning into a parallel
composition of timed automata (TA). The intuition is that each timeline can be
seen as a timed word “described” by the TA associated with the corresponding
variable. A plan for k variables is then a timed k-multiword, i.e., a timed word
over a structured alphabet featuring a component for each variable.
We call k-MWTA the composition of TAs accepting k-multiwords encoding
plans. We will show at the end of the section how to derive from k-MWTAs a
pair of bounds, on the number of tokens of a plan, and on its horizon, which will
be at the basis of the NP algorithm of the next section.
Let us recall some basic notions. Let w be a finite or infinite word over some
alphabet. An infinite timed word w over a finite alphabet Σ is an infinite word
w = (a1 , τ1 )(a2 , τ2 ) · · · over Σ × R+ (intuitively, τi is the time at which the
event ai occurs) such that the sequence τ = τ1 , τ2 , . . . of timestamps satisfies:
(1) τi ≤ τi+1 for all i ≥ 1 (monotonicity), and (2) for all t ∈ R+ , τi ≥ t for
some i ≥ 1 (divergence/progress). The timed word w is also denoted by the pair
(σ, τ ), where σ is the (untimed) infinite word a1 a2 · · · and τ is the sequence of
timestamps. An ω-timed language over Σ is a set of infinite timed words over Σ.
Let C be a set of clocks. A clock valuation val : C → R+ is a function assigning
a real value to each clock in C. A clock constraint over C is a Boolean combination
of atomic formulas of the form c • c0 + cst or c • cst, where • ∈ {≥, ≤}, c, c0 ∈ C,
and cst ∈ Q+ is a constant. We will often use the interval-based notation, for
instance, c ∈ [2, 7.4]. We denote by Φ(C) the set of clock constraints over C.
Given a clock valuation val for C and a clock constraint θ over C, we say that
val satisfies θ if θ evaluates to true replacing each occurrence of a clock c in θ by
val (c), and interpreting Boolean connectives in the standard way. Given t ∈ R+ ,
(val + t) denotes the valuation such that, for all c ∈ C, (val + t)(c) = val (c) + t.
For Res ⊆ C, val [Res](c) = 0 if c ∈ Res, and val [Res](c) = val (c) otherwise.
Trigger-Less Timeline-Based Planning on Dense Domains is NP-Complete 5
q0,x a
x=a
cx ∈ [1, 1], cx := 0
x=a x=b x=c x=b
x
... b
cx ∈ [2.9, 10),
cx := 0 t=1 t=7 t=10 t=13.9
x=c
cx ∈ [2, 8], cx := 0
x=b
w = (a, 1) (b, 7) (c, 10) (b, 13.9)
c
Fig. 1. (Part of) TA Ax for x = (Vx ,Tx ,Dx ), Fig. 2. An example of timeline for the
with Vx = {a, b, c, . . .}, b ∈ Tx (a), c ∈ Tx (b), state variable x of Fig. 1, with the timed
Dx (a) = [2.9, 10), Dx (b) = [2, 8], . . .. word encoding it, and accepted by Ax .
Definition 6 ([1]). A (Büchi) timed automaton (TA) over Σ is a tuple A =
(Σ, Q, Q0 , C, ∆, F ), where Q is a finite set of (control) states, Q0 ⊆ Q is the set
of initial states, C is a finite set of clocks, F ⊆ Q is the set of accepting states,
and ∆ ⊆ Q × Σ × Φ(C) × 2C × Q is the transition relation.
A configuration of A is a pair (q, sval ), where q ∈ Q, and sval is a clock valuation
for C. A run π of A on w = (σ, τ ) is an infinite sequence of configurations
π = (q0 , sval 0 )(q1 , sval 1 ) · · · such that q0 ∈ Q0 , sval 0 (c) = 0 for all c ∈ C
(initialization requirement), and the following constraint holds (consecution):
for all i ≥ 1, for some (qi−1 , σi , θ, Res, qi ) ∈ ∆, sval i = (sval i−1 + τi − τi−1 )[Res]
and (sval i−1 + τi − τi−1 ) |= θ (we let τ0 = 0). The run π is accepting if there are
infinitely many i ≥ 0 such that qi ∈ F . The timed language LT (A) of A is the
set of infinite timed words w over Σ s.t. there is an accepting run of A on w.
Let us now introduce the encoding of a timeline by a timed word, and the TA
for a state variable. Hereafter, we will assume that, for every x and every v ∈ Vx ,
we have Tx (v) 6= ∅; however, this constraint can easily be relaxed [3].
Definition 7. Let x = (Vx , Tx , Dx ) be a state variable. The timeline for x
encoded by a timed word (a1 , τ1 )(a2 , τ2 ) · · · is the sequence of tokens (x, a1 , t1 )
(x, a2 , t2 ) · · · , where, for i ≥ 1, ai ∈ Vx , ai+1 ∈ Tx (ai ), and ti = τi+1 −τi ∈ Dx (ai ).
Definition 8. A TA for a state variable x = (Vx , Tx , Dx ) is a tuple Ax =
(Vx , Q, {q0,x }, {cx }, ∆, Q), where Q = Vx ∪{q0,x } (q0,x 6∈ Vx ), and ∆ = {(v 0 , v, cx ∈
Dx (v 0 ), {cx }, v) | v 0 , v ∈ Vx , v ∈ Tx (v 0 )} ∪ {(q0,x , v, cx ∈ [1, 1], {cx }, v) | v ∈ Vx }.
Intuitively, Ax accepts all timed words encoding a timeline for the state variable x.
Let us note that all states are accepting. Moreover, the constraints of a transition
δ ∈ ∆ on the unique clock cx are determined by the (value of the) source state of
δ. The reason why we set cx ∈ [1, 1] on all the transitions from q0,x is technical
and will be clear later. See Fig. 1 and 2 for some examples.
In the following, we introduce the formalism of k-multiword TA (k-MWTA). A
k-MWTA accepts a language of timed k-multiwords, formally definedSas follows.
For k ≥ 1 pairwise disjoint alphabets Σ1 , . . . , Σk , and the symbol ∈
/ 1≤i≤k Σi ,
k-Σ denotes the multialphabet {(a1 , . . . , ak ) | ai ∈ Σi ∪ {}, for 1 ≤ i ≤ k} \
→
{(, . . . , )}. A k-multiword is a word over k-Σ. Intuitively, a k-multiword a 1
→
· a 2 · · · is a synchronization of k words over the alphabets Σ1 , . . . , Σk ; in
6 L. Bozzelli et al.
x = a11 x = a21 x = a31 x = a41
x
y = a12 y = a22 y = a32 y = a42
y
z = a13 z = a13 z = a23
z
t=1 t=4 t=7 t = 10.2 t = 13 t = 17.1 t = 20.9
((a11 , a12 , a13 ), 1) ((a21 , a32 , ), 7) ((a31 , , a23 ), 13) ((a41 , , ), 20.9)
((, a22 , ), 4) ((, , a13 ), 10.2) ((, a42 , ), 17.1)
Fig. 3. An example of timelines for x, y, z with the timed 3-multiword encoding them.
→
a j = (a1j , . . . akj ), for j ≥ 1, all the symbols aij such that aij 6= , with 1 ≤ i ≤ k,
occur at the same instant of time, and if aij = , the intended meaning is that no
symbol (event) of the i-th alphabet Σi occurs at that time. A timed k-multiword
is just a timed word (σ, τ ) where the untimed word σ is a k-multiword.
The notion of timeline encoded by a timed word can be extended to the
multi-timeline encoded by a timed k-multiword.
Definition 9. Let x1 , . . . , xk , with xi = (Vxi , Txi , Dxi ), be k state variables.
→ →
The timeline for xj encoded by a timed k-multiword ( a 1 , τ1 )( a 2 , τ2 ) · · · is the
→ →
timeline encoded by d ( a 1 [j], τ1 )( a 2 [j], τ2 ) · · · , where d((σ, τ )) is the timed
word obtained from (σ, τ ) removing occurrences of symbols (, τ 0 ), for any τ 0∈ R+ .
See Fig. 3 for an example. A k-MWTA can be viewed as a suitable parallel
composition of TAs communicating via shared clocks.
Definition 10. For 1 ≤ i ≤ k, let Ai = (Σi , Qi , Q0,i , Ci , ∆i , Fi ) be a TA. A
k-multiword TA (k-MWTA) for A1 , . . . , Ak is a TA k-A = (k-Σ, Q, Q0 , C, ∆, F ):
– Q = (Q1 × . . . × Qk ) ∪ {qf }, qf being an (optional) auxiliary final state,
– Q0 = Q0,1 × . . . × Q0,k , C = C1 ∪ . . . ∪ Ck, F = (F1 × . . . × Fk ) ∪ {qf },
– if (q1 , . . . ,qk ),(a1 , . . . ,ak ),Θ, Cl,(q10 , . . . ,qk0 ) ∈ ∆ and (q1 , . . . ,qk ),(q10 , . . . ,qk0 ) ∈
Vk Sk
Q \ {qf }, then Θ = i=1 θi , Cl = i=1 Resi , and, for all i = 1, . . . , k,
• if ai 6= , then there exists (qi , ai , θi , Resi , qi0 ) ∈ ∆i ,
• if ai = , then it holds qi = qi0 , θi = >, and Resi = ∅.
Notice that more than one k-MWTA can be generated from given A1 , . . . , Ak .
The ones we are interested in are those of Definition 11 and Definition 13 below.
We now instantiate Definition 10 over the TA for x1 , . . . , xk .
Definition 11. Let x1 , . . . , xk be k state variables and, for 1 ≤ i ≤ k, let
Axi = (Σi = Vxi , Qi , {q0,i }, {ci }, ∆i , Qi ). A k-MWTA for Ax1 , . . . , Axk is the
0 00
k-MWTA k-Ax1 ,...,xk = (k-Σ, Q, {q0 }, C, ∆ ∪ ∆ , F ), where:
= Q1 × . . . × Qk , q0 = (q0,1 , . . . , q0,k ), C = {c1 , . . . , ck }, F = Q1 × . . . × Qk ,
– Q
0
– (q1 , . . . , qk ), (a1 , . . . , ak ), Θ, Cl, (q10 , . . . , qk0 ) ∈ ∆ iff (q1 , . . . , qk ) 6= q0 , Θ =
Vk Sk
i=1 θi , Cl = i=1 Resi , and, for all i = 1, . . . , k,
• if ai 6= , then there exists (qi , ai , θi , Resi , qi0 ) ∈ ∆i ,
• if ai = , then it holds qi = qi0 , θi = >, and Resi = ∅.
00 Vk Sk
– ∆ ={(q0 ,(a1 , . . . , ak ), i=1 ci∈[1, 1], i=1{ci },(a1 , . . . ,ak ))|(a1 , . . . ,ak )∈Σ1×. . .×Σk}
Trigger-Less Timeline-Based Planning on Dense Domains is NP-Complete 7
Proposition 1. Let x1 , . . . , xk be k state variables, with k ≥ 1. LT (k-Ax1 ,...,xk )
is a set of k-multiwords, each one encoding a timeline for each of x1 , . . . , xk .
Let us now introduce the k-MWTA for the synchronizations rules. Since each
rule has the form E1 ∨ . . . ∨ En , we focus on a single Ei , the automaton for
the rule being just the union of the automata for E1 , . . . , En . Ei has the form
∃o1 [x1 = v1,j1 ] · · · ∃on [xn = vn,jn ].C, where C is a conjunction of atoms. We
associate two clock variables with each quantifier oi [xi = vi,ji ]—named coi ,S
and coi ,E —which, intuitively, are reset when the token chosen for oi starts and
ends, respectively. In order to select a suitable token along the timeline, coi ,S
and coi ,E are non-deterministically reset when xi takes the value vi,ji ∈ Vxi .
Moreover, to deal with atoms involving a time constant (time-point atoms), we
introduce a clock variable cglob , which measures the current time and is never
reset. For technical reasons, we assume that the start of activities is at time 1 and,
consequently, the reset of any coi ,S and coi ,E cannot happen before 1 time unit
has passed from the beginning of the timed word/plan. In fact, in Definition 8,
we have cx ∈ [1, 1] on all the transitions from q0,x (for this reason, we must also
add 1 to all time constants in all time-point atoms). This assumption implies
that the value of coi ,S is equal to that of cglob if coi ,S has never been reset, and
less otherwise. Since only one token for each quantifier is chosen in a timeline,
coi ,S must be reset only once: a transition resetting coi ,S is enabled only if the
constraint coi ,S = cglob is satisfied (likewise for coi ,E ).
We now define a TA for a state variable x, suitably resetting the clocks
associated with all the quantifiers over x. For a set of token names O, we denote
by Λ(O, x, v) the subset of names o ∈ S O such that o[x = v] for a variable x
and a value v ∈ Vx , and by Λ(O, x) = v∈Dx Λ(O, x, v). Moreover CS (O) (resp.,
CE (O)) represents the set {co,S | o ∈ O} (resp., {co,E | o ∈ O}).
Definition 12. Given x = (Vx , Tx , Dx ) and quantifiers o1 [x = v1 ], . . . , o` [x = v` ],
0 00
a TA for x, o1 , . . . , o` is Ax,o1 ,...,o` = (Vx , Q, {q0 }, C, ∆ ∪ ∆ , ∅), where:
– Q = Vx ∪ {q0 } and C= {cglob } ∪ {coi ,S , coi ,E | i = 1, . . . , `},
0
^ ^
– ∆ is the set of tuples v, a, co,S = cglob ∧ (co,S < cglob ∧ co,E = cglob )∧
o∈P o∈R
^
(co,S = cglob ∨ co,E < cglob ), CS (P ) ∪ CE (R), a
o∈Λ({o1 ,...,ok },x,v)\R
where v ∈ Vx , P ⊆ Λ({o1 , . . . , o` }, x, a) and R ⊆ Λ({o1 , . . . , o` }, x, v);
00
– ∆ = {(q0 , a, cglob ∈ [1, 1], CS (P ), a) | a ∈ Vx , P ⊆ Λ({o1 , . . . , o` }, x, a)}.
In Definition 12, R (resp., Λ({o1 , . . . , ok }, x, v)\R) is the set of token names whose
end clock must (resp., must not) be reset. The next k-MWTA is a synchronization
of TA (each one for the tokens over the same variable) for quantifiers in E.
Definition 13. Let x1 , . . . , xk be k variables and E = ∃o1 [xj1 = v1 ]· · ·∃on [xjn = vn ].C ,
with {j1 , . . . , jn } ⊆ {1, . . . , k}. A k-MWTA for x1 , . . . , xk , o1 , . . . , on , and E is a
k-MWTA for the TA Axi ,Λ({o1 ,...,on },xi ) = (Σi = Vxi , Qi , {q0,i }, Ci , ∆i , ∅), with
0 00 000 0000
1 ≤ i ≤ k, k-Ax1 ,...,xk ,E = (k-Σ, Q, {q0 }, C, ∆ ∪ ∆ ∪ ∆ ∪ ∆ , {qf }), where:
8 L. Bozzelli et al.
– Q = (Q1×. . .×Qk )∪{qf }, q0 = (q0,1 , . . . , q0,k ), C = {cglob }∪{coi ,S , coi ,E |i ∈ [1, n]},
k ^
0
^
– ∆ is the set of tuples (v1 , . . . , vk ), (a1 , . . . , ak ), co,S = cglob ∧
i=1 o∈Pi
^ ^
(co,S < cglob ∧ co,E = cglob ) ∧ (co,S = cglob ∨ co,E < cglob ) ,
o∈Ri o∈Ri
k
[
(CS (Pi ) ∪ CE (Ri )), (v10 , . . . , vk0 )
i=1
satisfying, for all i = 1, . . . , k, the following conditions:
• if ai = , then vi = vi0 , Pi = ∅, and Ri = Ri = ∅,
6 , ai = vi0 ∈ Dxi , Pi ⊆ Λ({o1 , . . . , on }, xi , vi0 ), Ri ∪R
• if ai = ˙ i = Λ({o1 , . . . , on },xi ,vi )
00 Sk
– ∆ = {(q0 , (a1 , . . . , ak ), cglob ∈ [1, 1], i=1 CS (Pi ), (a1 , . . . , ak )) | (a1 , . . . , ak ) ∈
Vx1 × . . . × Vxk , Pi ⊆ Λ({o1 , . . . , on }, xi , ai ) for 1 ≤ i ≤ k},
000 Vk
– ∆ = {(q, (a1 , . . . , ak ), ΦC ∧ i=1 (coi ,S < cglob ∧ coi ,E < cglob ), ∅, qf ) | q ∈
Vx1 × . . . × Vxk , (a1 , . . . , ak ) ∈ k-Σ}, where ΦC is the translation of C into a
(conjunction of ) TA clock constraint(s),
0000
– ∆ = {(qf , (a1 , . . . , ak ), >, ∅, qf ) | (a1 , . . . , ak ) ∈ k-Σ}.
Note that k-Ax1 ,...,xk ,E can enter qf only when all token clocks have been reset
Vk
( i=1 (coi ,S < cglob ∧ coi ,E < cglob )) and all C’s conditions are verified.
The TA Ã for a TP domain P = ({x1 , . . . , xk }, S) is built by exploiting the
standard union and intersection operations for TA: Ã is obtained by intersecting
(i) the k-MWTA k-Ax1 ,...,xk for the state variables W (Definition 11) with (ii) a TA
k-Ax1 ,...,xk ,R for each trigger-less rule R = > → 1≤i≤m Ei in S, which is the
disjunction of m k-MWTAk-Ax1 ,...,xk ,Ei (Definition 13), one for each Ei .
Proposition 2. LT (Ã) is the set of plans for P = ({x1 , . . . , xk }, S).
Theorem 1. Let P = (SV, S) be a TP domain with trigger-less rules only. The
problem of checking the existence of a plan for P is in PSPACE.
The theorem is proved by inspecting the standard PSPACE emptiness checking
algorithm for TA, in order to verify that the space complexity remains polynomial
also for k-MWTA. For details we refer the reader to [3]. The check involves
building the so-called region automaton [1] and concludes by an emptiness test
on a Büchi automaton of g = O(|C| · r · V) states, where C is the clock set of
Ã, r = O(|C|! · 2|C| · (2K + 2)|C| ) is the number of regions (K is the maximum
constant occurring in P 4 ), and V = O(|S| · (V k · d)|S|+1 ) is the number of states
of Ã, with V = maxki=1 |Vxi | and d the number of disjuncts in the longest S rule.
Exploiting this result, we can derive a finite horizon for the plans of a (any)
problem, that is, if a TP domain P = (SV, S) has a solution plan, then P also
4
I.e., an upper/lower bound of an interval of a token duration, a time constant in an
atom, or a bound at the subscript of an atom. We assume they are encoded in binary.
Trigger-Less Timeline-Based Planning on Dense Domains is NP-Complete 9
has a solution plan whose horizon is no greater than a given bound. Analogously,
we calculate a bound on the maximum number of tokens in a plan.
In order to check the emptiness of the previous Büchi automaton of g states,
it is enough to find a finite word uv, where: (i) |u|, |v| ≤ g, and (ii) there is a
run of the automaton that, from an initial state, upon reading u, reaches a state
q, and upon reading v from q reaches a final state and gets ultimately back to
q. Finally, we observe that each transition of the Büchi automaton corresponds
to the start point of at least a token in some timeline of (a plan for) P , and
at most a token for each timeline (when all these tokens start simultaneously).
This yields a bound on the number of tokens: 2 · g · |SV |. We can also derive a
bound on the horizon of the plan: 2 · g · |SV | · (K + 1). As a matter of fact, every
transition taken in the timed automaton may let at most K + 1 time units pass,
as K accounts in particular for the maximum constant to which a (any) clock
is compared (clearly, an unbounded quantity of time units may pass, but after
K + 1 the last region of the region automaton will certainly have been reached).
By exploiting this pair of bounds, we now describe an NP algorithm.
4 TP with Trigger-less Rules is NP-complete
To start with, we provide an example showing that there is no polynomial-size
plan for some TP domains. Thus, an explicit enumeration of all tokens across all
timelines does not represent a suitable polynomial-size certificate. Let p(i) be
the i-th prime number, assuming p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, and so
on. For 1 ≤ i ≤ n, let xi = ({vi }, {(vi , vi )}, Dxi ), with Dxi (vi ) = [p(i), p(i)]. The
Vn−1
rule > → ∃o1 [x1 = v1 ]· · · ∃on [xn = vn ]. i=1 oi ≤e,e
[0,0] oi+1 is asking for the existence
of a “synchronization point”, where n tokens (one for each variable) have their
ends
Qn aligned. n−1 Due to the allowed token durations, the first such time point is
i=1 p(i) ≥ 2 . Hence, in any plan, the timeline for x1 features at least 2n−1
tokens: no explicit polynomial-time enumeration of such tokens is possible. It
follows that there is no trivial guess-and-check NP algorithm.
We now present a non-deterministic polynomial-time algorithm, proving that
the TP problem with trigger-less rules is in NP. At the end of the section, we
will see that such problem is in fact NP-complete. The algorithm is structured
in 3 phases, whose description follows.
(Phase 1) Preprocessing. As a preliminary preprocessing phase, we consider
all rational values occurring in the input TP domain P = (SV, S)—be either
upper/lower bounds of an interval of a token duration, a time constant in an
atom, or upper/lower bounds (u or `) at the subscript of an atom—and convert
them into integers by multiplying them by the lcm γ of all denominators. This
involves a quadratic blowup in the input size, being constants encoded in binary.
Given a plan for P 0 (where all values are integers), we can obtain one for the
original P by dividing the start/end times of all tokens in each timeline by γ.
(Phase 2) Non-deterministic token positioning. The algorithm then non-
deterministically guesses, for every trigger-less rule in S, a disjunct—and deletes
all the others. Moreover, for each (left) quantifier oi [xi = vi ], it guesses the
10 L. Bozzelli et al.
integer part of both the start and the end time of the token for xi to which oi
is mapped. We call such time instants, respectively, sint (oi ) and eint (oi ).5 We
observe that all start/end times sint (oi ) and eint (oi ), being less than or equal to
2 · g · |SV | · (K + 1) (the finite horizon bound), have an integer part that can be
encoded with polynomially many bits (and thus can be generated in polynomial
time). Let us now consider the fractional parts of the start/end time of the tokens
associated with quantifiers (we denote them by sf rac (oi ) and ef rac (oi )). The
algorithm non-deterministically guesses an order of all such fractional parts. It
has to specify, for every token start/end time, whether it is integer (sf rac (oi ) = 0,
ef rac (oi ) = 0) or not (sf rac (oi ) > 0, ef rac (oi ) > 0). Every possibility can be
generated in polynomial time. Some trivial tests should be performed, i.e., for all
oi , sint (oi ) ≤ eint (oi ), each token is assigned an end time equal or greater than
its start time, and no two tokens for the same variable are overlapping.
It is routine to check that if we change the start/end time of (some of the)
tokens associated with quantifiers, but we leave unchanged (i) all the integer
parts, (ii) zeroness/non-zeroness of fractional parts, and (iii) the order of the
fractional parts, then the satisfaction of the (atoms in the) trigger-less rules does
not change. This is due to all the constants being integers, as a result of the
preprocessing step.6 Therefore we can now check whether all rules are satisfied.
(Phase 3) Enforcing legal token durations and timeline evolutions. We now
conclude by checking that: (i) all tokens associated with a quantifier have an
admissible duration, and that (ii) there exists a legal timeline evolution between
pairs of adjacent such tokens over the same variable (two tokens are adjacent if
there is no other token associated with a quantifier in between). We will enforce
all these requirements as constraints of a linear problem, which can be solved in
deterministic polynomial time (e.g., using the ellipsoid algorithm). When needed,
we use strict inequalities, which are not allowed in linear programs. We will show
later how to convert these into non-strict ones.
We start by associating non-negative variables αoi ,s , αoi ,e with the fractional
parts of the start/end times sf rac (oi ), ef rac (oi ) of every token for a quantifier
oi [xi = vi ]. First, we add the linear constraints 0 ≤ αoi ,s < 1, 0 ≤ αoi ,e < 1.
Then, we also need to enforce that the values of αoi ,s , αoi ,e respect the decided
order of the fractional parts, e.g., 0 = αoi ,s = αoj ,s < αok ,s < · · · < αoj ,e <
αoi ,e = αok ,e < · · · . To enforce requirement (i), we set, for all oi [xi = vi ],
a ≤ (eint (oi ) + αoi ,e ) − (sint (oi ) + αoi ,s ) ≤ b, where Dxi (vi ) = [a, b]. Clearly, strict
(<) inequalities must be used for a left/right open interval. To enforce (ii), i.e.,
the existence of a legal timeline evolution between each pair of adjacent tokens
for the same state variable, say oi [xi = vi ] and oj [xi = vj ], we proceed as follows
(analogous considerations hold for an evolution between t = 0 and the first token).
5
W.l.o.g., we can assume that all quantifiers refer to distinct tokens in timelines. As a
matter of fact, the algorithm can non-deterministically choose to force two (or more)
quantifiers oi [xi = vi ] and oj [xi = vi ], over the same variable and value, to refer to
the same token just by rewriting all occurrences of oj as oi in the atoms of the rules.
6
We observe that, by leaving unchanged all integer parts, fractional parts’ zeroness
and order, the region of the region graph of the timed automaton does not change.
Trigger-Less Timeline-Based Planning on Dense Domains is NP-Complete 11
Let us consider each state variable xi = (Vi , Ti , Di ) as a directed graph
G = (Vi , Ti ), where Di associates with each vertex v ∈ Vi a duration interval. We
have to decide whether there is (a) a path in G, possibly with repeated vertices
and edges, v0 · v1 · · · vn−1 · vn , where v0 ∈ Ti (vi ) and vn , with vj ∈ Ti (vn ), are
non-deterministically
Pn generated, and (b) a list of non-negative reals d0 , . . . , dn s.t.
i=0 d i = (sint (o j ) + αoj ,s ) − (eint (oi ) + αoi ,e ) and, for all 0 ≤ s ≤ n, ds ∈ Di (vs ).
0 0
To this aim, we guess a set of integers {αu,v | (u, v) ∈ Ti }. Intuitively, αu,v
is the number of times the solution path traverses (u, v). Since every time an
0
edge is traversed a new token starts, each αu,v is bounded by the number of
0
tokens, i.e., by 2 · g · |SV |. Hence the binary encoding of αu,v can be generated
in polynomial time. Then, we perform the following deterministic steps.
1. We consider the set E 0 := {(u, v) ∈ Ti | αu,v 0
> 0} (subset of the edges of G),
and we check whether it induces an (undirected) connected subgraph of G.
P 0 P 0 P 0
2. Check (a) (u,v)∈E 0 αu,v = (v,w)∈E 0 αv,w for v ∈ Vi \{v0 , vn } (b) (u,v0 )∈E 0 αu,v 0
P 0 P 0 P 0
= (v0 ,w)∈E 0 αv0 ,w − 1 (c) (u,vn )∈E 0 αu,vP n
= (vn ,w)∈E 0 αvn ,w + 1.
0
3. For all v ∈ Vi \ {v0 }, we define yv := (u,v)∈E 0 αu,v (y is the number of
Pv
times the solution path gets into v); moreover, yv0 := (v0 ,u)∈E 0 αv0 0 ,u .
4. We define the real non-negative variables zv , for every v ∈ Vi (zv is the total
waiting time of the path on the node v), subject to the following constraints:
a · yv ≤ zv ≤ b · yv , where D Pi (v) = [a, b] (the constraint is analogous for open
intervals). Finally, we set v∈Vi zv = (sint (oj ) + αoj ,s ) − (eint (oi ) + αoi ,e ).
0
Steps 1. and 2. together check that the values αu,v for the edges specify a
directed Eulerian path from v0 to vn in a multigraph. The following indeed holds.
Theorem 2 ([9]). Let G0 = (V 0 , E 0 ) be a directed multigraph (E 0 is a multiset).
G has a (directed) Eulerian path from v0 to vn iff: 1) the undirected version of
G0 is connected; 2) |{(u, v) ∈ E 0 }| = |{(v, w) ∈ E 0 }|, for all v ∈ V 0 \ {v0 , vn };
3) |{(u, v0 ) ∈ E 0 }| = |{(v0 , w) ∈ E 0 }| − 1; 4) |{(u, vn ) ∈ E 0 }| = |{(vn , w) ∈ E 0 }| + 1.
Steps 3. and 4. evaluate the waiting times of the path in some vertex v with
duration interval [a, b]. If the solution path visits v yv times, then each single visit
must take at least a and at most b units of time. Hence, the overall visitation
time is in between a · yv and b · yv . Vice versa, if the total visitation time is in
between a·yv and b·yv , then it can be split into yv intervals each falling into [a, b].
The algorithm concludes by solving the linear program given by the variables
αoi ,s and αoi ,e for each quantifier oi [xi = vi ], and, for each pair of adjacent tokens
in the same timeline, say for xi , for each v ∈ Vi , the variables zv subject to their
constraints. However, in order to conform to linear programming, we have to
replace all strict inequalities with non-strict ones. All constraints involving strict
inequalities we have written so far are of (or can easily be converted into) the
following forms: ξs < ηq + k or ξs > ηq + k, where s and q are variables, and
ξ, η, k are constants. We replace them, respectively, by ξs − ηq − k + βt ≤ 0
and ξs − ηq − k − βt ≥ 0, where βt is an additional fresh non-negative variable,
which is local to a single constraint. The original inequality and the new one are
equivalent if and only if βt is a small enough positive number. Moreover, we add
another non-negative variable, say r, which is subject to a constraint r ≤ βt , for
12 L. Bozzelli et al.
each of the introduced variables βt (i.e., r is less than or equal to the minimum
of all βt ’s). Finally, we maximize the value of r when solving the linear program.
We have that max r > 0 if and only if there is an admissible solution where the
values of all βt ’s are positive (and thus the original strict inequalities hold true).
We conclude with the next result (that holds even for a single state variable).
Theorem 3. Let P be a TP domain with trigger-less rules only. Checking the
existence of a plan for P is an NP-complete problem.
Proof. For NP-hardness, there is a reduction from the problem of the existence
of a Hamiltonian path in a directed graph G. Given G = (V, E), with |V | = n, we
define x = (V, E, Dx ), where Dx (v) = [1, 1] for each v ∈ V . We add the following
trigger-less rules, one for each v ∈ V : >→ ∃o[x = v].o ≥s[0,n−1] 0. The rule for v ∈ V
requires that there is a token (x, v, 1) on the timeline for x, starting no later than
n−1. G has a Hamiltonian path iff there is a plan for the planning problem. t u
5 Conclusions and Future Work
In this paper, we studied TP restricted to trigger-less rules, over dense temporal
domains, proving its NP-completeness. We analyzed this case as the unrestricted
version of the problem is known to be undecidable [3].
In future work, we will focus on decidability and complexity of intermediate
fragments of TP, namely, where forms of synchronization rules in between the
general ones and trigger-less are considered. For instance, we may allow only
rules for future, and/or non-singular intervals in the atoms of trigger-rules.
References
1. Alur, R., Dill, D.: A theory of timed automata. Th. Comp. Sci. 126, 183–235 (1994)
2. Barreiro, J., Boyce, M., Do, M., Frank, J., Iatauro, M., Kichkaylo, T., Morris, P.,
Ong, J., Remolina, E., Smith, T., Smith, D.: EUROPA: A Platform for AI Planning,
Scheduling, Constraint Programming, and Optimization. In: ICKEPS (2012)
3. Bozzelli, L., Molinari, A., Montanari, A., Peron, A.: Decidability and Complexity of
Timeline-based Planning over Dense Temporal Domains. In: KR (2018), extended
version at https://www.uniud.it/it/ateneo-uniud/ateneo-uniud-organizzazione/
dipartimenti/dmif/assets/preprints/1-2018-molinari
4. Cesta, A., Cortellessa, G., Fratini, S., Oddi, A., Policella, N.: An Innovative Product
for Space Mission Planning: A Posteriori Evaluation. In: ICAPS. pp. 57–64 (2007)
5. Chien, S., Tran, D., Rabideau, G., Schaffer, S., Mandl, D., Frye, S.: Timeline-based
space operations scheduling with external constraints. In: ICAPS. pp. 34–41 (2010)
6. Cialdea Mayer, M., Orlandini, A., Umbrico, A.: Planning and Execution with
Flexible Timelines: a Formal Account. Acta Informatica 53(6–8), 649–680 (2016)
7. Gigante, N., Montanari, A., Cialdea M., M., Orlandini, A.: Timelines are expressive
enough to capture action-based temporal planning. In: TIME. pp. 100–109 (2016)
8. Gigante, N., Montanari, A., Cialdea Mayer, M., Orlandini, A.: Complexity of
timeline-based planning. In: ICAPS. pp. 116–124 (2017)
9. Jungnickel, D.: Graphs, Networks and Algorithms. Springer (2013)
10. Muscettola, N.: HSTS: Integrating Planning and Scheduling. In: Intelligent Schedul-
ing, pp. 169–212. Morgan Kaufmann (1994)