Outline Review: Constraint-based Interval Planning Simple Temporal Networks Schedulability and Scheduling Review: Temporal, Model-based Programming Managing Execution Uncertainty Execution with Dynamic Scheduling Execution with Explicit Models of Uncertainty TCSP Queries (Dechter, Meiri, Pearl, AlJ91) Is the TCSP consistent? Planning What are the feasible times for each X? Planning What are the feasible durations between Planning each X: and X? What is a consistent set of times? Scheduling What are the earliest possible times Scheduling What are the latest possible times?
Outline • Review: Constraint-based Interval Planning • Simple Temporal Networks • Schedulability and Scheduling • Review: Temporal, Model-based Programming • Managing Execution Uncertainty – Execution with Dynamic Scheduling – Execution with Explicit Models of Uncertainty TCSP Queries (Dechter, Meiri, Pearl, AIJ91) • Is the TCSP consistent? Planning • What are the feasible times for each Xi ? Planning • What are the feasible durations between Planning each Xi and Xj ? • What is a consistent set of times? Scheduling • What are the earliest possible times? Scheduling • What are the latest possible times?
To Query an STN Map to a Distance Graph Gd=<V,Ed> Edge encodes an upper bound on distance to target from source Negative edges are lower bounds T=(aX-X1≤b) X1≤b X< 020[3040 40 [0.20y 40,50] -40 [60,70] 70 Ga Induces Constraints Path constraint: i0=i,1=.,k=j X-xs∑a -Conjoined path constraints result in the shortest path as Douno where d; is the shortest path from i to j
To Query an STN Map to a Distance Graph Gd = < V,Ed > 70 1 3 2 4 0 20 50 -10 40 -30 20 -10 -40 -60 1 3 2 4 0 [10,20] [30,40] [10,20] [40,50] [60,70] Tij = (aijd Xj- Xi d bij) Xj- Xi dbij Xi- Xj d - aij • Edge encodes an upper bound on distance to target from source. • Negative edges are lower bounds. Gd Induces Constraints • Path constraint: i0 =i, i1 = . . ., ik = j ĺ Conjoined path constraints result in the shortest path as bound: where dij is the shortest path from i to j Xj Xi d ai j1 ,i j j 1 k ¦ Xj Xi d dij
Conjoined Paths Computed using All Pairs shortest path (e. g, Floyd-Warshall, Johnson for i' =1 to n do d+ 2 for 1,j: =I to n do di+ 3. for k =1 to n do 4. for 1,j: =I to n do 5. di+ min di, dik dki: k Shortest Paths of Gd 01234 20 0020503070 10 -100402060 10 2-40-300-1030 3-20-1020050 4-60-50-20-400 70
Conjoined Paths Computed using All Pairs Shortest Path (e.g., Floyd-Warshall, Johnson) 1. for i := 1 to n do dii 0; 2. for i, j := 1 to n do dij aij; 3. for k := 1 to n do 4. for i, j := 1 to n do 5. dij min{dij, dik + dkj}; i k j 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph Shortest Paths of Gd 70 1 2 3 4 0 20 50 -10 40 -30 20 -10 -40 -60
STN Minimum Network 0020503070 -100402060 120101[030401[10.2015060 2-40-300-1030 2[50-401-40,-30]p[20-10][20,30 3-20-1020050 3[-3020]20-10110200[40.501 60-50-20-400 40.-601[6050130.20150.401 d-graph StN minimum network Schedulability: Plan Consistency No negative cycleS:-5>TA-TA=0 01234 0、20503070 100 10 2060 -40-3001030 -40 3-20-1020050 4-60-50-20-400
STN Minimum Network 0 1 2 3 4 0 [0] [10,20] [40,50] [20,30] [60,70] 1 [-20,-10] [0] [30,40] [10,20] [50,60] 2 [-50,-40] [-40,-30] [0] [-20,-10] [20,30] 3 [-30,-20] [-20,-10] [10,20] [0] [40,50] 4 [-70,-60] [-60,-50] [-30,-20] [-50,-40] [0] 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph STN minimum network Schedulability: Plan Consistency 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 d-graph 70 1 2 3 4 0 20 50 -10 40 -30 20 -10 -40 -60 No negative cycles: -5 > TA – TA = 0
Scheduling: Latest Solution Node o is the reference 20 40 0[020503070 -30 1-100402060 10 50 2-40-300-1030 3-20-1020050 60 4-60-50-20-400 70 d-graph Scheduling: Earliest Solution Nodes is the reference 20 40 0020503070 00402060 2-40-300-1030 3-20-1020050 4-60-50-20-40 70 d-graph
Scheduling: Latest Solution 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 70 1 2 3 4 0 20 50 -10 40 -30 20 -10 -40 -60 d-graph Node 0 is the reference. S1 = (d01, . . . , d0n) Scheduling: Earliest Solution 0 1 2 3 4 0 0 20 50 30 70 1 -10 0 40 20 60 2 -40 -30 0 -10 30 3 -20 -10 20 0 50 4 -60 -50 -20 -40 0 70 1 2 3 4 0 20 50 -10 40 -30 20 -10 -40 -60 d-graph Node 0 is the reference. S1 = (-d10, . . . , -dn0)