Simple Temporal Problems with Uncertainty (Vidal,Fargier ’99) Thierry Vidal, Hélène Fargier: Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell. 11(1): 23-45 (1999)
Paul H. Morris, Nicola Muscettola: Managing Temporal Uncertainty Through Waypoint Controllability. IJCAI 1999: 1253-1258
Paul H. Morris, Nicola Muscettola: Temporal Dynamic Controllability Revisited. AAAI 2005: 1193-1198. 2004. 25
Paul Morris: A Structural Ch
Simple Temporal Problems with Uncertainty (Vidal,Fargier ’99) Thierry Vidal, Hélène Fargier: Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell. 11(1): 23-45 (1999)
Paul H. Morris, Nicola Muscettola: Managing Temporal Uncertainty Through Waypoint Controllability. IJCAI 1999: 1253-1258
Paul H. Morris, Nicola Muscettola: Temporal Dynamic Controllability Revisited. AAAI 2005: 1193-1198. 2004. 25
Paul Morris: A Structural Characterization of Temporal Dynamic Controllability. CP 2006: 375-389
Simple Temporal Problems with Uncertainty Informally, an STPU is an STP where some of the variables are not under the control of the agent, i.e. the agent cannot decide which value to assign to them.
An STPU:
Set of executable timepoints (controllable assignment);
Set of contingent timepoints (uncontrollable assignment);
Set requirement constraints TiJ:
Binary
Temporal interval I=[a,b] meaning a≤XJ-Xi≤b
Set of contingent constraints Thk:
Binary: on an executable Xh and a contingent timepoint Xk
Temporal interval I=[c,d] meaning 0≤c≤Xk-Xh≤d
STPUs Definitions Given an STPU P
A control sequence d is an assignment to the executable timepoints
A situation w is a set of durations on contingent constraints (set of elements of contingent intervals)
A schedule is a complete assignment to the variables of P
A schedule is viable if it is consistent with all the constraints. Sol(P) is the set of all viable schedules of P.
STPUs Definitions Given an STPU P
A projection Pw corresponding to situation w is the STP obtained replacing each contingent constraint with its duration in w. Proj(P) is the set of all projection of P.
A viable strategy S: Proj(P) → Sol(P) maps every projection Pw into a schedule including w
Notation [S(Pw)]x : time assigned to executable variable x by schedule S(Pw)
[S(Pw)]
Controllability Strong Controllability Dynamic Controllability Weak Controllability There is a plan
that will work
whatever happens
In the future I can build a plan
while things
happen that will
be successful. For every possible
scenario there is a
plan
Strong Controllability (SC) of STPUs An STP with Uncertainty is Strongly Controllable if there is an assignment to all the executable time points consistent with all the possible scenarios (=complete assignments to contingent points)
(Vidal, Fargier, 1999)
Start-
clouds End-
clouds Start-
aiming End-
aiming 31 40 0 10 20 25 Executable Executable Contingent Executable Aiming should start no more than 10 s. before End-clouds. 30 0 31 50 25 35 35 40
Strong Controllability: formal definition An STPU P is Strongly Controllable (SC) iff there is an execution strategy S s.t.
∀Pw ∈Proj(P), S(Pw) is a solution of Pw, in other words S is viable
and [S(P1)]x = [S(P2)]x, ∀P1, P2 ∈Proj(P)
Strong requirement
Useful when the situation is not observable at all
Or when the solution must be known beforehand
Testing Strong Controllability Main idea
Characterize the constraint induced on executable variables from the strong consistency requirement new constraints on executable variables
Remove all contingent variables and all constraints involving them we get an STP
The STP is consistent iff the STPU is strongly controllable
Induced constraints (1) Induction(1)
A,B executable
Zi contingent
Contingent constraint Zi-A∈[x,y] and requirement constraint Zi-B ∈[u,v]
Induce constraint B-A∈[y-v,x-u] A B Zi u v x y w y-v x-u New constraint
Induced constraints (2) Induction(2)
A,B executable
Ci,Cj contingent
Contingent constraints:
Ci-A∈[li,ui]
Cj-B∈[lj,uj]
requirement constraint Cj-Ci ∈[a,b]
Induce constraint Y-X∈[ui-lj+a, li-uj+b] a b lj uj wj ui-lj+a li-uj+b li ui wi New constraint A B Ci Cj
SC Algorithm Input: STPU Q=(Xe,Xc,Cr,Cc)
Output: minimal STP
STP P (Xe,∅)
P all constraints of Q defined only on executable variables
for every distinct pair of contingent constraints Ci and Cj in Ce
P P ∪ all constraints induced from Ci with induction 1
P P ∪ all constraints induced from Cj with induction 1
P P ∪ all constraints induced from Ci and Cj by induction 2
P’ Solve(P)
If P consistent then return P’
else return “not strongly controllable”
Example 3 11 5 8 1 3 X Y C2 C3 0 10 0 10 2 A B -5 5 C1 1 15 2 5 X Y 2 A B -5 1 0 10 1 4 X Y 2 A B -5 1 2 10 1 4 3 6 STPU Induced STP Minimal STP
SC Algorithm is sound and complete An STPU P is strongly controllable iff the execution of SC-Algorithm(P) does not terminate with “not strongly controllable”
Proof
SC-Algorithm(P) terminates with “not sc” if the derived STP is not consistent
This happens iff there is an inconsistency caused by:
constraints of Q defined only on executables,
in this case intrinsically inconsistent and thus not strongly controllable, or
constraints of Q only on executable and some induced constraints
in this case it is never possible to satisfy the constraints of Q on executables and control all possible durations of some contingent events not SC
only induced constraints
in this case there are two or more contingent events which are controlled by disjoint sets of control sequences involving common variables not SC
Complexity of SC Algorithm Building the set of induced constraints can be done in linear time in cardinality of the set of constraints O(|Cr|+|Cc|), thus O(|Xe ∪ Xc|2)
Solving the STP is O(|Xe|3)
Usually |Xc|<<|Xe| and the second dominates
Weak Controllability: formal definition An STPU P is Weakly Controllable (SC) iff there is an execution strategy S s.t.
∀Pw ∈Proj(P), S(Pw) is a solution of Pw
in other words if there is viable strategy
An STPU is weakly controllable if every situation has at least one consistent schedule.
However there maybe different schedules for different situations.
Weak requirement
Relevant in applications where the situation may become available just before execution starts
Pseudo-controllability Consider the STPU as an STP (forgetting about the distinction between contingent and executable events)
The STPU is pseudo-controllable iff in the minimal network of the associated STP no interval on a contingent constraint is tightened
Pseudo and Weak Controllability Weak Controllability Pseudo Controllability
Proof
To show this we show that if the STPU is not pseudo-controllable then it is not weakly controllable
If it is not pseudo-c then there must be at least on interval on a contingent constraint which has been tightened
This means that some possible duration of the contingent event has been ruled out not belonging to any solution of the STP
This means that any projection associated to a scenario including that duration for the contingent constraint does not have a schedule not weakly controllable
The converse does not hold:
weak controllability requires that ALL possible combination of all durations of all contingent constraints must have a schedule
Pseudo-controllability just guarantees that for each possible duration there is at least a projection that has a schedule
We can thus use pseudo-controllability as a preprocessing step for weak controllability
Comments