Programs with Flexible Time

When?

Contributions:
Brian Williams
Patrick Conrad
Simon Fang
Paul Morris
Nicola Muscettola
Pedro Santana
Julie Shah
John Stedl
Steve Levine
Andrew Wang Tuesday, Feb 16th
courtesy of JPL
 Assignments

Problems Sets:
• Pset 1 due tomorrow (Wednesday) at 11:59pm

• Pset 2 released tomorrow

Interesting references:
• Dechter, R., I. Meiri, J. Pearl, “Temporal Constraint Networks,” Artificial
Intelligence, 49, pp. 61-95,1991.

• Muscettola, N., P. Morris and I. Tsamardinos, “Reformulating Temporal Plans for

Efficient Execution.” Intl Conf. on Knowledge Representation and Reasoning
(KRR), 1998.
 Outline

• Programs with Flexible Time

– Intro
– Describing temporal plans
– Exposing implicit constraints
– Consistency checking
– Offline scheduling
– Online execution
– Reformulating for faster online execution
 A single “cognitive system”
language and executive.
%#"#$

Uhura

!$

!!#%'(
#$!'$
!
&#$

)A3@ !$

 
Kirk

%$
$$!
 
$$ $
%$$

Burton

 $
%! $

Pike
! %#! !!# %$
 
! %!#$
%$$
! $
Sulu
 $
"%$

Bones
 !$$
(
&#$
© source unknown. All rights reserved. This content is excluded
   

 


from our Creative Commons license. For moreinformation,
see [Link] 
   

 Flexible Time

• Flexible time = more robustness

• We tell cognitive robot:
– Timing requirements (“engage boosters 2-4
minutes after launch but before reaching orbit”)
– Cognitive robot schedules autonomously.

 This image is in the public domain.

 Execution of Timed
Model-based Programs
7;/53'173<13(/@53BA&=D3@ 
&=D3@ 
"
I%/@/::3:
I'3?C3<13
1
"
- .
&.
&=D3@
&=D3@ 5=B=>

- .
&.
&=D3@
&=D3@ 5=B=>

.
&=D3@
- .
&= =D3@ 7;/53(/@53BA
2
- .
&.
&=D3@
&=D3@ 5=B=> 
J
I'3?C3<13
I' 3?C3<1
C3<13
- .
.
&=D3@
&=D3@ 5=B=> 
- .& .&=D3@ 7;/53(/@53BA
&=D3@ 7;/53(/@53BA
"
- .
&=D3@
.
&=D3@ 5=B=> 
- .
.
&=D3@
&=D3@ 5=B=> 
J "
J "
in RMPL [williams et al 01]

[5,10] [5,10] [2,5] [5,10]

%#% 
&=D3@ 5=B=> &=D3@ 5=B=> &=D3@ 7;/53(/@53BA &=D3@ 5=B=> 

[5,10] [5,10] [2,5] [5,10]

&=D3@ 5=B=>  &=D3@ 7;/53(/@53BA &=D3@ 5=B=>  &=D3@ 5=B=> 

Focus of today
Decisions include what, how, who and when.
 %$
"%
%!
%"!#
$%&# $


!!# %
 #
(
$& 
%
$%#%
!
%'%$
!
%
( [Muscettola, Morris,Tsamardinos,KR 98]

 To Execute a Temporal Plan
'1632C:3
$44:7<3
'1632C:3
$<:7<3

1. Describe Temporal Plan 1. Describe Temporal Plan

2. Test Consistency 2. Test Consistency

3. Schedule Plan 3. Reformulate Plan

=44:7<3
=<:7<3
4. Execute Plan 4. Dynamically Schedule Plan


 To Execute a Temporal Plan
'1632C:3
$44:7<3
'1632C:3
$<:7<3

1. Describe Temporal Plan

2. Test Consistency

3. Schedule Plan

=44:7<3
=<:7<3
4. Execute Plan


 Describe Temporal Plan

• Activities to perform
• Relationships among activities
This image is in the public domain.

&3;=D3
#
'6C<B *3<B
#
'6C<B

'B=E &3:3/A3
!==>

(@/G

5@3AA
'3BC>

=<475C@3
*3<B
(==:A :C72
/>A ')
&31=<475 &3:3/A3
!==>

(@/G

B

B;/F


 Metric Temporal Relations

K =7<5
B=
B63
AB=@3
B/93A
/B
:3/AB

;7<
/<2
/B
;=AB

;7<

[10min, 30min]
Activity: Going to the store

K @3/2
A6=C:2
03
3/B3<
E7B67<
=<3
2/G
=4
0/97<5

[0d, 1d]
Activity: Bake Bread Activity: Eat Bread
Simplify by reducing interval relations to
relations on timepoints.

Activity A

A- A+
Start Activity A End Activity A
 Metric Temporal Relations

K =7<5
B=
B63
AB=@3
B/93A
/B
:3/AB

;7<
/<2
/B
;=AB

;7<

[10m,30m]
G- G+ 10 < [G+ - G-] < 30

Start Going to Store End Going to Store

K @3/2
A6=C:2
03
3/B3<
E7B67<
=<3
2/G
=4
0/97<5
[0d,1d]
B+ E- 0 < [E- - B+] < 1

End Bake Bread Start Eat Bread

 Qualitative Temporal Relations
[Allen 83]

+
034=@3
, X Y ,
/4B3@
+

+
;33BA
, X Y ,
;3B0G
+
+
=D3@:/>A
, X Y ,
=D3@:/>>320G
+
+
2C@7<5
, XY ,
1=<B/7<A
+

+
AB/@BA
, X Y ,
AB/@B320G
+
+
47<7A63A
, Y X ,
47<7A6320G
+
+
3?C/:A
, Y
X ,
3?C/:A
+

+
27A8=7<B
,
 Qualitative Temporal Relations
Expressed as timepoint inequalities:
[0,inf]
+
034=@3
, X Y + 
, X+ Y-
[0,0]
+
;33BA
, X Y + 
, X+ Y-
+
=D3@:/>A
, X Y , 
+ and X- < Y+
+
2C@7<5
, XY , 
+ and X+ < Y+

+
AB/@BA
, X Y + 
, and X+ < Y+

+
47<7A63A
, Y X + 
, and X+ = Y+
+
3?C/:A
, Y
X + 
, and X+ = Y+
+
27A8=7<B
, + 
, or Y+ < X-
[Villain & Kautz; Simmons]

 Temporal Relations Described by a
Simple Temporal Network (STN)
• Simple Temporal Network [Dechter, Meiri, Pearl 91]
• Tuple <X, C> where:
• variables X1,…Xn, represent time points [l 1 , u1 ]
X1 X3
(real-valued domains)
[l 2 , u2 ] [l 3 , u3 ]
• binary constraints C of the form: X2
(X k − X i ) ∈ [aik , bik ].

– called links.

Sufficient to represent: Can’t represent:

• simple metric constraints • Allen’s disjoint relation
• all Allen relations but 1…


 Modeling Visualization

• [Link]


 To Execute a Temporal Plan
'1632C:3
$44:7<3
[1,10] B [1,1]
1. Describe Temporal Plan A D
[0,9] C [2,2]

2. Test Consistency

3. Schedule Plan

=44:7<3
=<:7<3
4. Execute Plan


 Consistency of an STN

Input: STN <X, C> where Cj = < <Xk, Xi>, <aj, bj> >

[1,10] B [1,1]
A D
[0,9] C [2,2]

STN is consistent iff there exists an assignment to times X

satisfying C.


 Schedule of an STN

Input: STN <X, C> where Cj = < <Xk, Xi>, <aj, bj> >

[1,10] B [1,1]
A D
[0,9] C [2,2]

Schedule is assignment to all timepoints X consistent with

constraints.


 How to find schedule?

• Idea: Transform STN

– Transform to distance-graph
– Common graph algorithms (i.e., shortest path)
will apply
 Transformation to distance graph

• (Board)
 "/>
'(#
B=
7AB/<13

@/>6

Simple Temporal Network Distance Graph

u
[l, u]
A B A B

-l

l  B –A  u B –A  u

l  B –A A– B -l

K )>>3@0=C<2
;/>>32
B=
=CB5=7<5
<=<<35/B7D3
/@1
K !=E3@0=C<2
;/>>32
B=
7<1=;7<5
<35/B7D3
/@1

[Dechter, Meiri, Pearl 91]

 Algorithm: offline scheduling

Initialize execution window to [-∞, ∞] for each event

while unexecuted events:
xi = pick any unexecuted event
ti = pick any time in xi’s execution window
Propagate to all xi’s neighbors & update their windows
 Naïve (and wrong) scheduling

• (Board)


 Propagating to neighbors
Tighten neighbor’s execution windows:

- outgoing edges to neighbor: u’ = min(u, ti + wu)

- incoming edges from neighbor: l’ = max(l, ti - wl)

[u, l]  tightened [u’, l’]

wu

wl
xi = ti


 Exposing Implicit Constraints

• (Board)


 [10,20] [30,40] 20 40

+ !A !3
+ -10
!A -30
!3
[10,20] -10
20
[40,50] 50
'A '3
'A '3
-40
[60,70]
70
-60


 APSP Graph: Windows of
Feasible Values
20 40

+ -10
!A -30
!3
-10
20
  50

!/B3AB
(7;3A
'A -40
'3
  
70
-60
  

   K!A 7<
- 
.
    K!3
7<
- 
 .

 /@:73AB
(7;3A K'A 7<
- 
.

%'%
25@/>6 K'3
7<
- 
 .


 Dispatchable form

• An STN or distance graph is dispatchable if:

– Can be properly scheduled via local propagations
to neighbors only
• Requires all implicit constraints be explicit


 Checking Consistency

• (Board)
 6319
@/>6
=<A7AB3<1G
K =<A7AB3<B
744 5@/>6
6/A
<=
<35/B7D3
1G1:3A
K 3B31B
0G
1=;>CB7<5
A6=@B3AB
>/B6
4@=;
=<3
3D3<B
B=
/::
=B63@A
K '7<5:3
'=C@13
'6=@B3AB
%/B6
'''%
K D3<B
;CAB
@3/16
/::
=B63@A

F/;>:3
=4
7<1=<A7AB3<B
1=<AB@/7<B
1
[2, 1]
A B A B

-2

Simple Temporal Network Distance Graph

 Summary

• To schedule, want a simple, local-propagation

algorithm
– Requires exposing implicit constraints
• All-pairs shortest path (APSP) exposes all
implicit constraints
– Puts network in dispatchable form
• Negative cycle in APSP: inconsistent.
 To Execute a Temporal Plan
'1632C:3
$44:7<3
'1632C:3
$<:7<3

1. Describe Temporal Plan 1. Describe Temporal Plan

2. Test Consistency 2. Test Consistency

3. Schedule Plan 3. Reformulate Plan

=44:7<3
=<:7<3
4. Execute Plan 4. Dynamically Schedule Plan
 Algorithm: offline scheduling

Compute dispatchable form (i.e., APSP)

Initialize execution window to [-∞, ∞] for each event
while unexecuted events:
xi = pick any unexecuted event
ti = pick any time in xi’s execution window
Propagate to all xi’s neighbors & update their windows


 The original STN

[0,10] [1, 1]

[0,10] [2, 2]


Distance graph transformation

10 1
0 -1
10
2
-2
0


 All pairs shortest path

10 1
A B C D
-1 -1
A 0 10 9 11 -1
9 1
B -1 0 -1 1 2

C 0 1 0 2 -2
0
D -2 -1 -2 0 11

-2


Computing a schedule

10 1
-1 -1
9 1 -1
2
-2
0

11

-2


 Computing a schedule

[-∞, ∞]
10 1
-1 -1
[-∞, ∞] 9 1 -1 [-∞, ∞]
2
-2
0
[-∞, ∞]
11

-2
Initialize execution windows for each event in the plan


 Computing a schedule

[-∞, ∞]
10 1
-1 -1
t=0 9 1 -1 [-∞, ∞]
2
-2
0
[-∞, ∞]
11

-2
Assign the first event


 Computing a schedule
outgoing edges to neighbor: u’ = min(u, ti + wu)
incoming edges from neighbor: l’ = max(l, ti - wl)

[-∞, 10]
10 1
-1 -1
t=0 9 1 -1 [-∞, ∞]
2
-2
0
[-∞, ∞]
11

-2
Propagate updated time bounds to neighbors


 Computing a schedule
outgoing edges to neighbor: u’ = min(u, ti + wu )
incoming edges from neighbor: l’ = max(l, ti - wl)

[1, 10]
10 1
-1 -1
t=0 9 1 -1 [-∞, ∞]
2
-2
0
[-∞, ∞]
11

-2
Propagate updated time bounds to neighbors


 Computing a schedule

[1, 10]
10 1
-1 -1
t=0 9 1 -1 [-∞, ∞]
2
-2
0
[0, 9]
11

-2
Propagate updated time bounds to neighbors


 Computing a schedule

[1, 10]
10 1
-1 -1
t=0 9 1 -1 [2, 11]
2
-2
0
[0, 9]
11

-2
Propagate updated time bounds to neighbors


 Computing a schedule

t=3
10 1
-1 -1
t=0 9 1 -1 [2, 11]
2
-2
0
[0, 9]
11

-2
Arbitrarily pick another time point and assign it...


 Computing a schedule

t=3
10 1
-1 -1
t=0 9 1 -1 [2, 11]
2
-2
0
[2, 2]
11

-2
Propagate updated time bounds to neighbors


 Computing a schedule

t=3
10 1
-1 -1
t=0 9 1 -1 [4, 4]
2
-2
0
[2, 2]
11

-2
Propagate updated time bounds to neighbors


 Computing a schedule

t=3
10 1
-1 -1
t=0 9 1 -1 [4, 4]
2
-2
0
t=2
11

-2
Pick another event and assign it


 Computing a schedule

t=3
10 1
-1 -1
t=0 9 1 -1 [4, 4]
2
-2
0
t=2
11

-2
Propagate to neighbors


 Computing a schedule

t=3
10 1
-1 -1
t=0 9 1 -1 t=4
2
-2
0
t=2
11

-2
Assign the final event


 Pre-computed schedules not robust
against fluctuations
• We’ve just computed a schedule:
tA = 0, tB = 3, tC = 2, tD = 4
• But what if there’s a disturbance?
– i.e., what if tB = 3.1?
– i.e., what if tB = 4?
– i.e., what if tB = 100?
• Pre-computed schedules not robust against
fluctuations!
• Solution: Dispatch dynamically online.
– Schedule events “on the fly,” after observing past event times.
– Increases robustness to many unanticipated fluctuations.
– Flexible temporal constraints allow this!


 To Execute a Temporal Plan
'1632C:3
$44:7<3
'1632C:3
$<:7<3

1. Describe Temporal Plan 1. Describe Temporal Plan

2. Test Consistency 2. Test Consistency

3. Schedule Plan 3. Reformulate Plan

=44:7<3
=<:7<3
4. Execute Plan 4. Dynamically Schedule Plan


 How do we schedule online?

• First, consider naive (incorrect!) approach.

• Similar to offline schedule algorithm, but now online:
– Wait until current time in execution window (“active”)

• (Still a problem though as we’ll see shortly)


 Naïve (wrong!) online dispatcher

Compute dispatchable form (i.e., APSP)

Initialize execution window to [-∞, ∞] for each event
while unexecuted events:
xi = pick any unexecuted event if current time in window
ti = now
Propagate to all xi’s neighbors & update their windows


 Naïve (wrong!) online scheduling

[-∞, ∞]
10 1
-1 -1
t=0 9 1 -1 [-∞, ∞]
2
-2
0
[-∞, ∞]
11

-2
Arbitrarily picking next event…


 Naïve (wrong!) online scheduling

t=3
10 1
-1 -1
t=0 9 1 -1 [2, 11]
2
-2
0
[0, 9]
11

-2
Arbitrarily picking next event…


 Naïve (wrong!) online scheduling

t=3
10 1
-1 -1
t=0 9 1 -1 [4, 4]
2
-2
0
t=2
11

-2
...but wait! We just assigned a past time!


 Enablement conditions dictate the
ordering of dispatched events
• Online: must assign monotonically increasing times
– whereas offline algorithms may assign in any order.

• How can we constrain dispatcher to do this?

• Solution: determine “enablement conditions” by

analyzing negative edges.
– Allows us to infer if some edges must precede other edges


 Enablement conditions dictate the
ordering of dispatched events
• Negative edges from APSP dictate ordering constraints
10 1
-1 -1
9 1 -1
2
-2
0

11

-2


 Enablement conditions dictate the
ordering of dispatched events
• Negative edges from APSP dictate ordering constraints
10 1
-1 -1
9 1 -1
2
-2
0

11

-2

B must occur after both A and C!


 Enablement conditions dictate the
ordering of dispatched events
• An event is enabled if all its neighbors over negative
edges have already been dispatched.
– All “predecessors” have been dispatched.

• Modify online dispatching algorithm to only dispatch

events if they are enabled.

• An event is active is the current time is within that

event’s execution window


 Corrected online dispatcher

Compute dispatchable form (i.e., APSP)

Initialize execution window to [-∞, ∞] for each event
E  {events with no predecessors} # set of enabled events
S  {} # set of executed events
while unexecuted events:
Wait until some event xi in E is active
ti = now # dispatch xi now at ti
Propagate to all xi’s neighbors & update their windows
Add xi to S
Add to E any now-enabled events


 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {A, C}

Initialize execution windows to [-∞, ∞] S = {}
E  {events with no predecessors}
S  {} [-∞, ∞]
while unexecuted events: 10 1
Wait until some event xi in E is active
[-∞, ∞] [-∞, ∞]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
A, C initially in E – have no [-∞, ∞]
11
negative, outgoing edges
-2

3
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {A, C}

Initialize execution windows to [-∞, ∞] S = {}
E  {events with no predecessors}
S  {} [-∞, ∞]
while unexecuted events: 10 1
Wait until some event xi in E is active
[-∞, ∞] [-∞, ∞]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
A is enabled and in E. [-∞, ∞]
(could have chosen C too) 11

-2

4
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {C}

Initialize execution windows to [-∞, ∞] S = {A}
E  {events with no predecessors}
S  {} [1, 10]
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 [2, 11]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
Dispatch A and propagate [0, 9]
11

-2

5
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {C}

Initialize execution windows to [-∞, ∞] S = {A}
E  {events with no predecessors}
S  {} [1, 10]
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 [2, 11]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
B, D not enabled! But C still is. [0, 9]
11

-2

6
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {}

Initialize execution windows to [-∞, ∞] S = {A, C}
E  {events with no predecessors}
S  {} [3, 3]
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 [4, 4]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
Dispatch & propagate C. t=2
11

-2

7
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {B}

Initialize execution windows to [-∞, ∞] S = {A, C}
E  {events with no predecessors}
S  {} [3, 3]
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 [4, 4]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
B is now enabled (but still not D). t=2
11

-2

68
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {}

Initialize execution windows to [-∞, ∞] S = {A, C, B}
E  {events with no predecessors}
S  {} t=3
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 [4, 4]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
Dispatch & propagate B. t=2
11

-2

69
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {D}

Initialize execution windows to [-∞, ∞] S = {A, C, B}
E  {events with no predecessors}
S  {} t=3
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 [4, 4]
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
D is finally enabled. t=2
11

-2

0
 Running online dispatcher

Compute dispatchable form (i.e., APSP) E = {}

Initialize execution windows to [-∞, ∞] S = {A, C, B, D}
E  {events with no predecessors}
S  {} t=3
while unexecuted events: 10 1
Wait until some event xi in E is active
t=0 t=4
ti = now -1 -1
Propagate to xi’s neighbors 9 1 -1
Add xi to S 2
Add to E any now-enabled events
-2
0
Finish up by dispatching D! t=2
11

-2
73

1
 Online dispatching algorithm remarks

• By considering predecessors, we guarantee that events

assigned monotonically increasing times online.
• Capable of responding to fluctuations that do not affect
overall temporal feasibility.
• (Note: must be run on an dispatchable / APSP graph!)

2
 Online dispatcher efficiency
• Consider an STN with n edges.
• How many edges in APSP distance graph?

Compute dispatchable form (i.e., APSP)

Initialize execution windows to [-∞, ∞]
E  {events with no predecessors}
S  {}
while unexecuted events:
Wait until some event xi in E is active
ti = now
Propagate to xi’s neighbors
Add xi to S
Add to E any now-enabled events

3
 Online dispatcher efficiency
• Consider an STN with n edges.
• How many edges in APSP distance graph? n2.

Compute dispatchable form (i.e., APSP)

Initialize execution windows to [-∞, ∞]
E  {events with no predecessors}
S  {}
while unexecuted events:
Wait until some event xi in E is active
ti = now
Propagate to xi’s neighbors
Add xi to S
Add to E any now-enabled events

4
 Online dispatcher efficiency
• Consider an STN with n edges.
• How many edges in APSP distance graph? n2.
• How many neighbors to propagate to each step?

Compute dispatchable form (i.e., APSP)

Initialize execution windows to [-∞, ∞]
E  {events with no predecessors}
S  {}
while unexecuted events:
Wait until some event xi in E is active
ti = now
Propagate to xi’s neighbors
Add xi to S
Add to E any now-enabled events

5
 Online dispatcher efficiency
• Consider an STN with n edges.
• How many edges in APSP distance graph? n2.
• How many neighbors to propagate to each step? n.

Compute dispatchable form (i.e., APSP)

Initialize execution windows to [-∞, ∞]
E  {events with no predecessors}
S  {}
while unexecuted events:
Wait until some event xi in E is active
ti = now
Propagate to xi’s neighbors
Add xi to S
Add to E any now-enabled events

6
 Online dispatcher efficiency
• Consider an STN with n edges.
• How many edges in APSP distance graph? n2.
• How many neighbors to propagate to each step? n.
• Large STNs: propagation slow. Want to reduce this.

Compute dispatchable form (i.e., APSP)

Initialize execution windows to [-∞, ∞]
E  {events with no predecessors}
S  {}
while unexecuted events:
Wait until some event xi in E is active
ti = now
Propagate to xi’s neighbors
Add xi to S
Add to E any now-enabled events

7
 To Execute a Temporal Plan
'1632C:3
$44:7<3
'1632C:3
$<:7<3

1. Describe Temporal Plan 1. Describe Temporal Plan

2. Test Consistency 2. Test Consistency

3. Schedule Plan 3. Reformulate Plan

=44:7<3
=<:7<3
4. Execute Plan 4. Dynamically Schedule Plan

7
79
You don’t need all those edges!

10 1

-1 -1

9 1 -1
2

-2
0

11

-2

0
 You don’t need all those edges!

10 1 1

-1 -1 -1
9 1 -1 1 -1
9
2

-2
0 0

11

-2 Equivalent minimal dispatchable network

1
 You don’t need all those edges!
Let’s consider a specific triangle
of edges.

10 1

-1 -1

9 1 -1
2

-2
0

11

-2

2
 You don’t need all those edges!
Let’s consider a specific triangle
of edges.
Do we really need the bottom
10 1 edge?
-1 -1

9 1 -1
2

-2
0

11

-2

3
 You don’t need all those edges!
Let’s consider a different triangle
of edges.
Do we really need the bottom
10 1 edge?
-1 -1

9 1 -1
2

-2
0

11

-2

4
 A ropes analogy
10

10
Imagine a “unidirectional rope” of
length 10 constraining sliders on a track.
5
 Rope analogy
10

10

Imagine a “unidirectional rope” of

length 10 constraining sliders on a track.
6
 Rope analogy
10 1

11

10
1

11

Now add in ropes for other constraints

7
 Rope analogy
10 1

11

Imagine pulling A and D as tightly as

possible.

10
1

11

88
 Rope analogy
10 1

11

Can we remove rope AD without changing behavior?

10
1

11

Yes! Same possible positions for A, B,

D.
8
 Rope analogy
10 1

11

Can we remove ropes AB, BD without changing

behavior?

10
1

11
No. AD still constrained, but B could slide freely! Not the
same behavior. Collectively, AB and BD entail AD (but AD
does not entail both AB and AD).
0
 Upper dominating edges - detection
from APSP

dBC If dAC, dBC ≥ 0 and

dAB + dBC = dAC
then BC dominates AC

dAC

(Proof omitted - based on triangle rule property of

APSP. Please see notes / reading for more info)
1
 Lower dominating edges - detection
from APSP

dAB
If dAB, dAC < 0 and
dAB + dBC = dAC
then AB dominates AC
dAC

(Proof omitted - based on triangle rule property of

APSP. Please see notes / reading for more info)
2
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2

3
 Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2
Upper dominated!

4
 Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2
Upper dominated!

5
 Dominance example

Upper dominated!
10 1
-1 -1
9 1 -1
2
-2
0

11

-2

6
 Dominance example

Upper dominated!
10 1
-1 -1
9 1 -1
2
-2
0

11

-2

7
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2
Upper dominated!

98
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2
Upper dominated!

99
 Dominance example

Lower dominated!
10 1
-1 -1
9 1 -1
2
-2
0

11

-2

0
 Dominance example

Lower dominated!
10 1
-1 -1
9 1 -1
2
-2
0

11

-2

1
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2
Lower dominated!
2
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2
Lower dominated!
3
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2 Lower dominated!

4
Dominance example

10 1
-1 -1
9 1 -1
2
-2
0

11

-2 Lower dominated!

5
Dominance example

1
-1
9 1 -1

6
 Dominance example
10 1
-1 -1
9 1 -1 Original APSP distance graph
2
-2
0

11

-2 1
-1
... now in minimal 9 1 -1
dispatchable form!

0
7
 Dominance example
[0,10] [1, 1]

Original STN

[0,10] [2, 2]

1
-1
... now in minimal 9 1 -1
dispatchable form!

0
8
 FilteringAlgorithm(G)
Input: A dispatchable APSP-graph G
Output: A minimal dispatchable graph
1 for each pair of intersecting edges in G
2 if both dominate each other
3 if neither is marked
4 arbitrarily mark one for elimination
5 end if
6 else if one dominates the other
7 mark dominated edge for elimination
8 end if
9 end for
10 remove all marked edges from graph
11 return G

09
 Avoiding Intermediate Graph
Explosion
K Problem:
L All pairs shortest path table computation consumed O(n2) space
L Only used as an intermediate - not needed after minimal dispatchable graph
obtained.

K Solution:
L Interleave process of APSP construction with edge elimination.
K Never have to build whole APSP graph.

[Tsarmardinos 1998]
0
 Recap

• Recap
– To schedule online, times must monotonically increase - use enablement
conditions
– Running online allows greater flexibility to fluctuations
– However, propagation costs can be large for large graphs
– Can reduce edges by using domination to make graph smaller

1
 To Execute a Temporal Plan
'1632C:3
$44:7<3 STN D Graph
[1,10] B [1,1] 10 B 1
-1
1. Describe Temporal Plan A D A -1
2 D
9
[0,9] C [2,2] 0 C -2

2. Test Consistency Detect negative loops

(SSSP).

3. Schedule Plan APSP + Decomposition.

=44:7<3
=<:7<3
4. Execute Plan

[Dechter, Meiri, Pearl 91]

2
 To Execute a Temporal Plan
'1632C:3
$44:7<3 Problem: delays and fluctuations in task
duration can cause plan failure.

1. Describe Temporal Plan

Observation: temporal constraints
leave room to adapt.
2. Test Consistency
Flexible Execution adapts through
dynamic scheduling:
3. Schedule Plan
Assign time to event when executed.
L Guarantee that all constraints will
=44:7<3
be satisfied.
=<:7<3 L Schedule with low latency through
4. Execute Plan pre-compilation.

[Muscettola, Morris, Tsmardinos KR98]

3
 To Execute a Temporal Plan
'1632C:3
$44:7<3 &
  

1. Describe Temporal Plan 1. Describe Temporal Plan

2. Test Consistency 2. Test Consistency

3. Schedule Plan 3. Reformulate Plan

=44:7<3 ~ Decomposable STN

=<:7<3
4. Execute Plan 4. Dynamically Execute Plan

How do we schedule on line?

4
 Outline: To Execute a Temporal
Plan
'1632C:3
$<:7<3 [1,10] B [1,1]
A D
1. Describe Temporal Plan [0,9] C [2,2]

(=
;7<7;7H3
:/B3<1G

@3;=D3
@32C<2/<B

2. Test Consistency
3253A

B [1,1]

3. Reformulate Plan A [1,1] D

[0,9] C

=44:7<3 t=3
=<:7<3 t=0 B [1,1] t=4
A [1,1] D
4. Dynamically Execute Plan
[0,9] C
t=2
-"CA13BB=:/
"=@@7A
(A/;/@27<=A
&.
5
MIT OpenCourseWare
[Link]

16.412J / 6.834J Cognitive Robotics

Spring 2016

For information about citing these materials or our Terms of Use, visit: [Link]