PowerPoint PresentationCassini Saturn Orbital InsertionSlide 3OutlineSlide 5Slide 6Slide 7Qualitative Temporal Constraints (Allen 83)Slide 9Qualitative Temporal Constraints maybe Expressed as Inequalities (Vilain, Kautz 86)Metric Time: Quantitative Temporal Constraint Networks (Dechter, Meiri, Pearl 91)Visualize TCSP as Directed Constraint GraphSimple Temporal Networks (Dechter, Meiri, Pearl 91)Simple Temporal NetworkSlide 17TCSP Queries (Dechter, Meiri, Pearl, AIJ91)Slide 19Slide 20To Query STN Map to Distance Graph Gd = < V,Ed >Induced Constraints for GdCompute Intersected Paths by All Pairs Shortest Path (e.g., Floyd-Warshall’s algorithm )Shortest Paths of GdSTN Minimum NetworkTest Consistency: No Negative CyclesLatest SolutionEarliest SolutionFeasible ValuesSolution by DecompositionSlide 32Slide 33Slide 34Slide 36Temporal Planning,Scheduling and Execution 1Brian C. Williams16.412J/6.834J November 25th, 2002courtesy JPLCassini Saturn Orbital InsertionModel-basedProgramming& ExecutionTask-DecompositionExecutionReactive Task ExpansionProjectiveTask ExpansionGoalsPlan RunnerTaskDispatchFlexible Sequence (Plans)CommandsObservationsModesGoalsHistories(?)SchedulerTemporalPlannerOutline•Temporal Planning•Representing Time•Temporal Consistency and Scheduling•Execution with Dynamic SchedulingModel-basedExecution(w planner)Task-DecompositionExecutionReactive Task ExpansionProjectiveTask ExpansionGoalsPlanRunnerTaskDispatchFlexible Sequence (Plans)CommandsObservationsModesGoalsHistories(?)SchedulerTemporalPlannerModel-basedExecution(w planner)Task-DecompositionExecutionReactive Task ExpansionProjectiveTask ExpansionGoalsPlanRunnerTaskDispatchFlexible Sequence (Plans)CommandsObservationsModesGoalsHistories(?)SchedulerTemporalPlannerOutline•Temporal Planning•Representing Time•Temporal Consistency and Scheduling•Execution with Dynamic SchedulingYQualitative Temporal Constraints(Allen 83)•x before y•x meets y•x overlaps y•x during y •x starts y•x finishes y•x equals yX YX YX YYXYXY XX•y after x•y met-by x•y overlapped-by x•y contains x•y started-by x•y finished-by x•y equals xDeep Space One Example:Temporal ConstraintsMax_ThrustIdleIdlePokeTimerAttitudeAccumSEP ActionSEP_SegmentTh_Segcontained_byequalsequalsmeetsmeetscontained_byStart_UpStart_UpShut_Down Shut_DownThr_BoundaryThrustThrustThrustThrustStandbyStandbyStandbyTh_SegaTh_Seg Th_SegIdle_SegIdle_SegAccum_NO_ThrAccum_ThrAccum_ThrAccum_ThrThr_Boundarycontained_byCP(Ips_Tvc)CP(Ips_Tvc)CP(Ips_Tvc)contained_byTh_SegQualitative Temporal Constraintsmaybe Expressed as Inequalities (Vilain, Kautz 86)•x before y X+ < Y-•x meets y X+ = Y-•x overlaps y (Y- < X+) & (X- < Y+) •x during y (Y- < X-) & (X+ < Y+) •x starts y(X- = Y-) & (X+ < Y+) •x finishes y (X- < Y-) & (X+ = Y+) •x equals y (X- = Y-) & (X+ = Y+)Metric Time: Quantitative Temporal Constraint Networks(Dechter, Meiri, Pearl 91)•A set of time points Xi at which events occur.•Unary constraints(a0 < Xi < b0 ) or (a1 < Xi < b1 ) or . . .•Binary constraints (a0 < Xj - Xi < b0 ) or (a1 < Xj - Xi < b1 ) or . . .Visualize TCSP asDirected Constraint Graph1 3420[10,20][30,40][60,inf][10,20][20,30][40,50][60,70]Simple Temporal Networks(Dechter, Meiri, Pearl 91)Simple Temporal Network:•A set of time points Xi at which events occur.•Unary constraints(a0 < Xi < b0 ) or (a1 < Xi < b1 ) or . . .•Binary constraints (a0 < Xj - Xi < b0 ) or (a1 < Xj - Xi < b1 ) or . . .Sufficient to represent:• most Allen relations • simple metric constraintsSufficient to represent:• most Allen relations • simple metric constraintsCan’t represent:• Disjoint tokensCan’t represent:• Disjoint tokensSimple Temporal Network•Tij = (aij Xi - Xj bij)1 3420[10,20][30,40][60,inf][10,20][20,30][40,50][60,70] A Completed Plan Forms an STNA Completed Plan Forms an STNTCSP Queries(Dechter, Meiri, Pearl, AIJ91)•Is the TCSP consistent?•What are the feasible times for each Xi?•What are the feasible durations between each Xi and Xj?•What is a consistent set of times?•What are the earliest possible times?•What are the latest possible times?TCSP Queries(Dechter, Meiri, Pearl, AIJ91)•Is the TCSP consistent? Planning•What are the feasible times for each Xi?•What are the feasible durations between each Xi and Xj?•What is a consistent set of times?•What are the earliest possible times? Execution•What are the latest possible times?Outline•Temporal Planning•Representing Time•Temporal Consistency and Scheduling•Execution with Dynamic SchedulingTo Query STN Map toDistance Graph Gd = < V,Ed >701 34202050-1040-3020-10-40-601 3420[10,20] [30,40][10,20][40,50][60,70]Tij = (aij Xj - Xi bij)Xj - Xi bijXi - Xj - aijEdge encodes an upper bound on distance to target from source.Induced Constraints for Gd•Path constraint: i0 =i, i1 = . . ., ik = j→Intersected path constraints:where dij is the shortest path from i to j Xj Xi aij 1,ijj 1kXj XidijCompute Intersected Pathsby All Pairs Shortest Path(e.g., Floyd-Warshall’s algorithm )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 do4. for i, j := 1 to n do5. dij min{dij, dik + dkj};ikj0 1 2 3 40 0 20 50 30 701 -10 0 40 20 602 -40 -30 0 -10 303 -20 -10 20 0 504 -60 -50 -20 -40 0d-graphShortest Paths of Gd701 24302050-1040-3020-10-40-60STN Minimum Network0 1 2 3 40 [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 40 0 20 50 30 701 -10 0 40 20 602 -40 -30 0 -10 303 -20 -10 20 0 504 -60 -50 -20 -40 0d-graph STN minimum networkTest Consistency: No Negative Cycles0 1 2 3 40 0 20 50 30 701 -10 0 40 20 602 -40 -30 0 -10 303 -20 -10 20 0 504 -60 -50 -20 -40 0d-graph701 24302050-1040-3020-10-40-60Latest Solution0 1 2 3 40 0 20 50 30 701 -10 0 40 20 602 -40 -30 0 -10 303 -20 -10 20 0 504 -60 -50 -20 -40 0701 24302050-1040-3020-10-40-60d-graphNode 0 is the reference.Earliest Solution0 1 2 3 40 0 20 50 30 701 -10 0 40 20 602 -40 -30 0 -10 303 -20 -10 20 0 504 -60 -50 -20 -40 0701 24302050-1040-3020-10-40-60d-graphNode 0 is the reference.Feasible Values0 1 2 3 40 0 20
View Full Document
Unlocking...