A number of extensions of simple temporal networks have been proposed over the last years to face several sources of uncertainty, either in isolation or simultaneously. This paper focuses on a hierarchy of simple temporal networks where the top-level formalism is that of conditional simple temporal networks with uncertainty and decisions (CSTNUDs), a formalism dealing with controllable and uncontrollable durations and controllable and uncontrollable conditional constraints simultaneously. We propose an algorithm to check strong controllability of CSTNUDs. We prove that strong controllability of temporal networks in this hierarchy is NP-complete if controllable conditional constraints are considered.
STNUs model temporal plans with uncontrollable (but bounded) durations. STNUs (and all other formalisms specifying uncontrollable parts) bring with them three main notions of controllability: weak, strong and dynamic. Weak controllability is when, for each combination of uncontrollable parts known in advance, there exists a way to operate on the controllable part satisfying all constraints. Strong controllability is the opposite case and says that there exists a way to operate on the controllable part satisfying all constraints no matter what will happen. Dynamic controllability requires the existence of a strategy refining how we operate on the controllable part in real time depending on what is going on.
STNUs do not specify controllable nor uncontrollable conditional constraints. To model uncontrollable
conditional constraints in isolation, the formalism of CSTNs [
Let B = {a, b, . . . , z} be a finite set of Boolean variables, a label ` = λ1 . . . λn is any finite conjunction of literals λi over the variables in B (we omit the ∧ connective to ease reading). The empty label is denoted by . The label universe of B, denoted by B∗, is the set of all possible (consistent) labels drawn from B. For instance, if B = {a, b}, then B∗ = { , a, b, ¬a, ¬b, ab, a¬b, ¬ab, ¬a¬b}. Two labels `1, `2 ∈ B∗ are consistent if and only if their conjunction `1`2 is satisfiable.
Definition 3 (CSTN/CSTNU). A conditional simple temporal network (CSTN) is a tuple hT , O, B, O, Ci extending an STN with a finite set of observation time points O ⊆ T = {A?, . . . , Z?}, a finite set of Boolean variables B, a bijection O : B → O assigning a unique Boolean variable to each observation point (we write O−1 : O → B for the inverse), and turning C into a finite set of conditional constraints ` → Y − X ≤ k each meaning that if ` is true, then Y − X ≤ k must hold, with ` ∈ B∗, Y, X ∈ T and k ∈ R. Once we execute an observation time point A?, Nature sets instantaneously the uncontrollable truth value of the associated Boolean variable O−1(A?) = a. A conditional simple temporal network with uncertainty (CSTNU) is a tuple hT , O, B, O, L, Ci extending a CSTN with a finite set of contingent links.
CSTNUs deal with controllable and uncontrollable durations and uncontrollable conditionals
simultaneously. However, they fail to model controllable conditionals. To bridge this gap conditional simple
temporal network with uncertainty and decisions (CSTNUDs, [
Fig. 1a shows such a hierarchy. We graphically represent temporal networks as directed graphs whose sets of nodes coincide with the set of time points (decision and observation time points are suffixed with ! and ?, respectively). A double red edge A ⇒ C labeled by [x, y] models a contingent links (A, x, y, C). An edge X → Y labeled by hk, `i models a constraint ` → Y − X ≤ k. If ` = we just use k as a label. 2
Strong Controllability of CSTNUDs: Super Projections
Strong controllability of STNUs, CSTNs and CSTNUs is in P [
CSTNUD
STNUD
−5
−5
both methods are applied one after the other: first conditionals, then contingent links [
Theorem 1. Any STNU is strongly controllable if and only if its super-projection is consistent. Proof. Let N = hT , L, Ci be any STNU and N ∗ = hT ∗, C∗i its super-projection. Assume that N is strongly controllable. Let TX = T ∩ T ∗ be the set of non-contingent time points and let TC = T \ TX be the set of contingent time points N . Let t : TX 7→ R be a feasible scheduling of N (i.e., a scheduling satisfying all constraints no matter which durations Nature chooses for contingent links). Let t∗ be the extension of t on the new domain T ∗ (i.e., set of time points of N ∗) defined by the following three rules: Rule 1: t∗ is an extension of t, thus, for each non-contingent time point X ∈ TX , t∗(X) = t(X). Rule 2: if X = Cm for some contingent node C ∈ TC, then t∗(X) = t(act(C)) + L(C). Rule 3: if X = CM for some contingent node C ∈ TC, then t∗(X) = t(act(C)) + U (C). where act(C ) is the activation time point of C (in the original STNU) and L() and U () are the lower and upper bound vectors on the delays of contingent time points (i.e., all minimal and all maximal durations). Fact 1 For each constraint Y − X ≤ k ∈ C where Y and X are not contingent time points, then Y − X ≤ k ∈ C∗. t(Y ) − t(X) ≤ k holds by assumption and since by Rule 1 t(Y ) = t∗(Y ) and t(X) = t∗(X), then t∗(Y ) − t∗(X) ≤ k holds as well.
Fact 2 For each contingent link (A, x, y, C) ∈ L, t∗(Cm) ≤ t(C) ≤ t∗(CM ) because of Rules 2 and 3. Fact 3 For each constraint X − C ≤ −k ∈ C, with C a contingent time point, t(X) − t(C) ≤ −k holds by assumption and t∗(X) − t∗(Cm) ≤ −k and t∗(X) − t∗(CM ) ≤ −k hold because of Fact 2. Fact 4 For each constraint C − X ≤ k ∈ C, with C a contingent time point, t(C) − t(X) ≤ k holds by assumption and t∗(Cm) − t∗(X) ≤ k and t∗(CM ) − t∗(X) ≤ k hold because of Fact 2. Therefore, if t is a feasible schedule for N , then t∗ is a feasible schedule for N ∗ (Facts 1,2,3 and 4).
Likewise, if t∗ is a feasible schedule for N ∗, then t∗|X is a feasible schedule for N , where t∗|X is the projection of t∗ over the non-contingent time points of N . Indeed, let d : TC → R be a delay vector assigning a duration to each contingent time point C ∈ TC. For every possible delay vector d and for every possible contingent time point C of N , it holds that t(Cm) = t(act(C)) + L(C) ≤ t(act(C)) + d(C) ≤ t(act(C )) + L(C) = t(CM ) since L ≤ d ≤ U . That is, we only need to cope with delay vectors which are sandwiched in-between the lower bound vector and the upper bound vector. Without loss of generality consider a binary constraint Y − C ≤ k involving C in the original STNU N . Since t∗(Y ) − t∗(Cm) ≤ k and t∗(Y ) − t∗(CM ) ≤ k hold, then the original t(Y ) − t(C) ≤ k holds as well.
Likewise, a CSTNUD is strongly controllable if and only if its STND super projection is consistent (the proof extends that of Theorem 1 to accommodate uncontrollable conditionals as well).
Algorithm 1 provides an approach to solve strong controllability of CSTNUDs. Algorithm 1 first
applies Algorithm 2 to get rid of uncontrollable conditional constraints, then applies Algorithm 3 to
rewrite contingent links maintaining controllable conditional constraints and finally calls a StndSolver
(see [
Algorithm 1: CstnudStrongSchedule(N )
Input: A CSTNUD N = hT , O, D, B, O, L, Ci
Output: A strong temporal plan 1 return StndSolver(StnudSP(CstnudSP(N )))
IOnuptuptu: tA: TChSeTSNTUNDUND s=upheTr-,pOro,Djec,tBio,nO,NL∗, Ci 1 for a ∈ BD do 2 O∗(a) = O(a) 3 C∗ ← ∅ 4 for ` → Y − X ≤ k ∈ C do 5 Let `D be ` without literals over vars in BO 6 C∗ = C∗ ∪ {`D → Yi − Xi ≤ k} 7 return hT , D, BD, O∗, L, C∗i
IOnuptuptu: tA:nThSeTNSTUNDDNsu=pehrT-p,rDoj,eBc,tiOon,LN, C∗i 1 T ∗ ← ∅, C∗ ← ∅ 2 for X ∈ T do 3 if X is non-contingent then Δ(X) = {X} ; 4 else Δ(X) = {Xm, XM } ; 5 T ∗ ← T ∗ ∪ Δ(X) 6 for (A, x, y, C) ∈ L do 7 C∗ ← C∗ ∪ {Cm − Ai ≤ x, Ai − Cm ≤ −x,
CM − Ai ≤ y, Ai − CM ≤ −y}
8 for ` → Y − X ≤ k ∈ C do
9 for Yi ∈ Δ(Y ) do
10 for Xi ∈ Δ(X) do
11 C∗ ← C∗ ∪ {` → Yi − Xi ≤ k}
12 return hT ∗, D, B, O, C∗i
Theorem 2. Strong controllability of STNUDs, CSTNDs and CSTNUDs is NP-complete.
Proof. Hardness: Consequence of the fact that deciding consistency of STNDs is NP-hard and it is a
special case of deciding strong controllability of STNUDs, CSTNDs and CSTNUDs (when L = ∅, O = ∅
and L = O = ∅, respectively). Membership: Regardless of the formalism, a certificate of YES consists
of a truth value assignment s for BD and a schedule t for TX (set of non-contingent time points). To verify
it we use the reductions in Algorithm 2 to get rid of BO (if 6= ∅) and Algorithm 3 to rewrite L (if 6= ∅). If
L 6= ∅, then for each (A, x, y, C) ∈ L, t(Cm) = t(A) + x and t(CM ) = t(A) + y. Finally, we verify that
(s, t) is a YES certificate for the resulting STNDs. We know that this check is polynomial [
Conclusions and Future Work We provided a simple approach to check strong controllability of CSTNUDs based on an elementary local reduction. The resulting algorithm’s running time is upper bounded by (i) the product of a low-degree polynomial where the magnitude of the numbers does not occur and (ii) a singly exponential term of the form 2|D|, where D is the set of binary decisions. With small modifications the algorithm we gave can be adapted to all formalisms in Fig. 1a. The idea is to reduce a strong controllability problem to a consistency problem by computing super-projections. All formalisms in Fig. 1a are reducible to their super-projections in polynomial time. Strong controllability of STNUDs, CSTNDs, CSTNUDs is NP-complete.
As future work, we plan to deepen research on complexity of strong controllability for these and
for other classes of (temporal)-constraint networks such as those discussed (or employed) in [