# Presentation: 505507

## The Prospects for 

**Real Planning**

**David E. Smith**
**desmith@arc.nasa.gov**

## Planning

**Find:**
**	****program of actions that achieves the objective**

## Planning

**Find:**
**	****program**** of actions that achieves the ****objective**

**partially-ordered set**

**goals**

## Factions

**Classical planning**
**(STRIPS, operator-based, first-principles)**
**?**
**HTN planning**
**“****practical” planning**
**MDP & POMDP planning**
**planning under uncertainty**

## Problems w/ Classical Planning

**Classical planning**
**performance**
**time**
**resources**
**HTN planning**
**MDP & POMDP planning**

## Outline

**Background**
**Performance advances**
**Resources**
**Time**
**Relevance to DX**

## The Classical Representation

**Operators**:

**Goals**:

- Goal1

- Goal2

- Goal3

- Op

**Inits**:

- P1

- P2

- P3

- P4

## Simple Spacecraft Problem

**Observation-1**
**target**
**instruments**
**Observation-2**
**Observation-3**
**Observation-4**
**...**

**calibrated**

**pointing**

## Example

**I****x**

**Im**

**p****C**

_**Init**_

_**Actions**_

**C**

**c**

**T****y**

**p****x**

**I****A**

_**Goal**_

**p****C**

## POCL Planning(SNLP, UCPOP)

- 1. Select an open condition
- 2. Choose an op that can achieve it
- Link to an existing instance
- Add a new instance
- 3. Resolve threats

**Im**

**I****A**

**p****C**

**F**

**I****A**

**F**

**C**

**Im**

**I****A**

**F**

**c**

**p****A**

**C**

**p****C**

**Im**

**I****A**

**F**

**c**

**p****A**

**S**

**T****A**

**¬p****C**

**C**

**p****C**

**Im**

**I****A**

**F**

**c**

**p****A**

**S**

**p****C**

## Outline

**Background**
**Performance advances**
**Resources**
**Time**
**Relevance to DX**

## Fully Automated Logistics Time Comparison

**Fully Automated Logistics Time Comparison**

- 0.1

- 10

- 1000

- 16

- 17

- 18

- 19

- 20

- 21

- 22

- 23

- 24

- 25

- 26

- 27

- 28

- 29

- 30

- 31

- 32

- 33

- 34

- 35

- 36

- 37

- 38

- 39

- 40

- 41

**Seconds**

-  System

- R

-  FF

-  HSP2

-  STAN

-  GRT

- Mips

## STRIPS Miconic 10 Time Comparison

**STRIPS Miconic 10 Time Comparison**

- 0.01

- 1

- 100

- 10000

- 2

- 4

- 6

- 8

- 10

- 12

- 14

- 16

- 18

- 20

- 22

- 24

- 26

- 28

- 30

- 32

- 34

- 36

- 38

- 40

- 42

- 44

- 46

- 48

- 50

- 52

- 54

- 56

- 58

- 60

**Seconds**

-  System R

-  TokenPlan

-  STAN

-  AltAlt

-  GRT

## Performance Advances

**Reachability****	****& Mutex reasoning**
**(Graphplan)**
**Distance-based heuristics**
**(HSP)**

## The Plan Graph

## Graphplan

## Example

**I****x**

**Im**

**p****C**

_**Init**_

_**Actions**_

**C**

**c**

**T****y**

**p****x**

**I****A**

_**Goal**_

**p****C**

## Level 0

**0**

**1**

**2**

**3**

**p****C**
**...**

## Level 1

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**C**

**p****C**
**...**

**T****A**

## Mutual Exclusion

**Two actions are mutex if**
** ****one clobbers the other’s effects or preconditions**
** ****they have mutex preconditions**
**	****	****	**
**Two propositions are mutex if**
** ****all ways of achieving them are mutex****	****	**

## Mutex for Level 1

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**C**

**T****A**

## Level 2

**Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**C**

**C**

**T****A**

**T****A**

## Mutex for Level 2

**Mutex for Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**C**

**C**

**T****A**

**T****A**

## Level 3

**Level 3**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**I****A**

**C**

**C**

**T****A**

**T****A**

**T****A**

## Mutex for Level 3

**Mutex for Level 3**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**C**

**C**

**T****A**

**T****A**

**T****A**

**I****A**

## Finding a Solution

**Finding a Solution**

**T****A**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**C**

**C**

**√**

**√**

**I****A**

**T****A**

**T****A**

## Finding a Solution – Level 3

**Finding a Solution – Level 3**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**C**

**C**

**T****A**

**T****A**

**I****A**

**T****A**

## Finding a Solution – Level 2

**Finding a Solution – Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**I****A**

**C**

**T****A**

**T****A**

**T****A**

**C**

## Finding a Solution – Level 2

**Finding a Solution – Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**I****A**

**C**

**C**

- Fails

**T****A**

**T****A**

**T****A**

## Finding a Solution – Level 2

**Finding a Solution – Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**I****A**

**C**

**C**

- Fails

**T****A**

**T****A**

**T****A**

## Finding a Solution – Level 2

**Finding a Solution – Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**I****A**

**C**

**C**

**T****A**

**T****A**

**T****A**

## Finding a Solution – Level 2

**Finding a Solution – Level 2**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**I****A**

**C**

**C**

**T****A**

**T****A**

**T****A**

## Finding a Solution – Level 1

**Finding a Solution – Level 1**

**0**

**1**

**2**

**3**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**p****C**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**...**

**c**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**C**

**C**

**C**

**I****A**

**T****A**

**T****A**

**T****A**

## Advantages of Graphplan

**Expansion & mutex are polynomial**
**Search over fixed structure**
**Mutex prunes branches early**

## AIPS-98 Competition

**BlackBox****	****	****Graphplan ******** SATplan**
**IPP****	****	****	****	****Graphplan**
**SGP****	****	****	****	****Graphplan**
**STAN****	****	****	****	****Graphplan**
**HSP****	****	****	****	****Forward State Space / Distance Heuristic**

## Performance Advances

**Reachability****	****& Mutex reasoning**
**(Graphplan)**
**Distance-based heuristics**
**(HSP)**

- √

## ?

**I****A**

**I2****A**

**I1****A**

**c1**

**c2**

**p****A**

**p****A**

- ...

- ...

**Inits**

## 

**I****A**

**Im1**

- D(a) = ca + ppre(a)D(p)

- D(c1)

- cIm1

- D(pa)

## D(Im1)

- D(Im1)

**I****A**

- D(p) = minapD(a)

- D(Im2)

- min

## 2-Camera Problem

_**Init**_

_**Actions**_

**W1**

**o1**

**¬o1**

## 2-Instrument Plan Graph

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**** **
**...**

**¬o1**
**o1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o2**
**p****C**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

**I1****A**

## Distances – Level 0

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**** **
**...**

**¬o1**
**o1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o2**
**p****C**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

- 0

- 0

- 0

## Distances– Level 1

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**** **
**...**

**¬o1**
**o1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o2**
**p****C**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

- 0

- 0

- 0

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 1

- 1

- 1

## Distances– Level 2

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**** **
**...**

**¬o1**
**o1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o2**
**p****C**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

- 0

- 0

- 0

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 1

- 1

- 1

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 2

- 1

- 1

- 1

- 2

## Distances– Level 3

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**** **
**...**

**¬o1**
**o1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o2**
**p****C**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

- 0

- 0

- 0

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 1

- 1

- 1

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 2

- 1

- 1

- 1

- 2

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 2

- 3

- 1

- 1

- 1

- 2

- 3

## Distances– Level 4

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**** **
**...**

**¬o1**
**o1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**...**

**¬o1**
**o2**
**p****C**
**...**

**¬o1**
**o1**
**c1**
**o2**
**c2**
**p****C**
**¬p****c**
**p****A**
**I****A**
**...**

- 0

- 0

- 0

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 1

- 1

- 1

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 2

- 1

- 1

- 1

- 2

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 2

- 3

- 1

- 1

- 1

- 2

- 3

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 2

- 3

- 1

- 1

- 1

- 2

- 3

- 4

## Regression + A*

**I****A**

- 4

- 3

**c1**

**c2**

**p****A**

**p****A**

- 1

- 1

**Regression + A*******

## Remarks

**Admissible?**
**underestimates – conflicts**
**overestimates – shared subplans**
**Refinements**
**Applicability?**
**Regression**
**Graphplan**
**Forward state space**
**POCL**

## AIPS-2000 Competition

**AltAlt****	****	****Regression + Distance**
**FF****	****	****	****	****Forward-SS + Distance**
**GRT****	****	****Forward-SS + Distance**
**HSP2****	****	****Regression + Distance**
**STAN****	****	****(Forward-SS  + Distance) + Graphplan**

**Reachability & Mutex reasoning**
**Distance-based heuristics**

## The Lesson

- It’s the heuristic, stupid!

## Outline

**Performance Advances**
**mutex + distance**
**Resources**
**Time**
**Relevance**

- √

## Complications

**Observation-1**
**priority**
**time window**
**target**
**instruments**
**duration**
**Observation-2**
**Observation-3**
**Observation-4**
**...**

**calibration**
**target1**
**target2**
**...**

**consumables:**
**fuel**
**power**
**data storage**
**cryogen**

**angle between targets**
- ** ****turn duration**

**Objective:**
**maximize science return**

**linked**

## Resources

- 			  Discrete		Continuous
- 			single/multiple	   	    (metric)
- Reusable		 instruments		  bandwidth
- Consumable		 solid rockets		      fuel

## Reusable Resources(single-capacity)

- TakeImage (?target, ?instr):
- 	Res: 	?instr
- 	Pre:	Calibrated(?instr), Pointing(?target)
- 	Eff:	Image(?target)

- Prevent concurrent actions

- Mutual exclusion between actions:
- Graphplan 		trivial
- Satplan    		¬A1  ¬A2
- POCL		A1<A2  A2<A1

## Reusable Resources(multiple-capacity)

- TakeImage (?target, ?instr):
- 	Res: 	?instr
- 	Pre:	Calibrated(?instr), Pointing(?target)
- 	Eff:	Image(?target)

- Suppose:  2 cameras
- Simple approach:  name the cameras

- Mutual exclusion between actions:
- Graphplan 		trivial
- Satplan    		¬A1  ¬A2
- POCL		 ?instr1≠?instr2   A1<A2  A2<A1

##  usage ≤ capacity

- TakeImage (?target):
- 	Res: 	Camera(1)
- 	Pre:	Pointing(?target)
- 	Eff:	Image(?target)

- 2 Cameras:
- Not named

- Explicit checking of concurrent actions to ensure:
-  usage ≤ capacity

- Capacity(Camera)=2

##  usage > capacity

-  usage > capacity

- Mutual exclusion between sets of actions:
- Graphplan 		n-ary mutex
- Satplan    		¬(A1  A2  A3  ...)
- POCL		A1<A2  A2<A1  A1<A3  A3<A1  ...

- Graph Techniques
- IxTeT

- Profiling heuristics
- Sadeh, Fox, Beck
- O-Plan

## √

**Performance Advances **
**Resources**
**Reusable**
**Single-capacity ******** binary mutex****	****	****easy**
**Multiple-capacity ******** n-ary mutex****	****	****tricky**
**specialized algorithms**
**search heuristics**
**Consumable**
**Time**
**Relevance**

## Consumable Resources

- Turn (?target):
- Pre:		Pointing(?direction), ?direction ≠ ?target
- 		Fuel ≥ Angle(?direction,?target) *ConsumptionRate
- Eff:		¬Pointing(?direction), Pointing(?target)
- 		Fuel –= Angle(?direction,?target) *ConsumptionRate

- Simple approach:
- wait until all variables are instantiated

## LP Approaches

- Zeno:
- open conditions:  P1, P2, P3, P4, P5, I1, I2, I3
- constraints: V1, V2, T1, T2, T3, E1, E2

- Simplex

**T****A**

**¬p****C**

**C**

**p****C**

**Im**

**I****A**

**F**

**c**

**p****A**

**S**

**p****x**

- Fuel ≥ ...

- Fuel – k = Fuel’

## LP Approaches:   LPSAT

- Turn (?target):
- Pre:		Pointing(?direction), ?direction ≠ ?target
- 		Fuel ≥ Angle(?direction,?target) *ConsumptionRate
- Eff:		¬Pointing(?direction), Pointing(?target)
- 		Fuel –= Angle(?direction,?target) *ConsumptionRate

- ¬Turn-T3-T71 v
- {Pointing-T31  C11
-  ¬Pointing-T32  Pointing-T72  C22 }
- C11  Fuel1 ≥ Angle(T3,T7) *ConsumptionRate
- C22  Fuel2 = Fuel1 – Angle(T3,T7) *ConsumptionRate

- Simplex

- SAT engine

## Concurrent Continuous Change

- Turn (?target):
- Pre:		Pointing(?direction), ?direction ≠ ?target
- 		Fuel ≥ Angle(?direction,?target) *ConsumptionRate
- Eff:		¬Pointing(?direction), Pointing(?target)
- 		Fuel –= Angle(?direction,?target) *ConsumptionRate

- Fuel = F(t)

- Time

- Fuel

- Time

## Summary

**Performance Advances**
**Resources**
**Reusable**
**Consumable**
**Equality and Inequality conditions**
**Time**
**Relevance**

## World Description

- State-centric:
- for each time describe propositions that are true

- Proposition-centric:
- for each proposition describe times it is true

- Pointing(A7)

- Calibrated(Cam2)

- Turn(A7)

- Pointing(Earth)

## Allen’s Ordering Relationships

## TakeImage Schema

- TakeImage(?target, ?instr)A
-       	P {Calibrated(?instr)P    Contains(P, A)}
- 	 Q {Pointing(?target)Q    Contains(Q, A)}
- 	 R {Image(?target)R    Meets(A, R)}

- TakeImage (?target, ?instr):
- Pre: Calibrated(?instr), Pointing(?target)
- Eff:	 Image(?target)

## Shorthand

- TakeImage (?target, ?instr)
- 	contained-by		Calibrated(?instr)
- 	contained-by		Pointing(?target)
- 	meets			Image(?target)

## Turn

- Turn (?target)
- 	met-by		Pointing(?direction)
- 	meets			Pointing(?target)

## Calibrate

- Calibrate (?instr)
- 	met-by		On(?instr)
- 	contained-by		CalibrationTarget(?target)
- 	contained-by		Pointing(?target)
- 	meets			Calibrated(?instr)

## Algorithm

- Choose:
- introduce an action & instantiate constraints
- coalesce propositions
- Propagate constraints

## Initial Plan

- Past

- Image(A7)

- meets

- Future

- meets

- 0

- ∞

## Expansion 1

- Image(A7)

- Future

- meets

- ∞

- Pointing(A7)

- Calibrated(?instr)

- TakeImage(A7, ?instr)

- meets

- contains

- contains

- before

## Expansion 2

- Image(A7)

- Pointing(A7)

- Calibrated(?instr)

- TakeImage(A7, ?instr)

- meets

- contains

- contains

- Pointing(?direction)

- Turn(A7)

- Pointing(?caltarget)

- CalibrationTarget(?caltarget)

- Calibrate(?instr)

- meets

- meets

- meets

- meets

- contains

- contains

- On(?instr)

- before

## Coalescing

## Coalescing

- Pointing(Earth)

- Off(Cam1)

- On(Cam2)

- CalibrationTarget(T17)

- Image(A7)

- Pointing(A7)

- Calibrated(Cam2)

- TakeImage(A7, Cam2)

- meets

- contains

- contains

- Turn(A7)

- Pointing(T17)

- Calibrate(Cam2)

- meets

- meets

- meets

- meets

- contains

- contains

- before

## Expansion 3

- Pointing(Earth)

- Off(Cam1)

- On(Cam2)

- CalibrationTarget(T17)

- Image(A7)

- Pointing(A7)

- Calibrated(Cam2)

- TakeImage(A7, Cam2)

- meets

- contains

- contains

- Turn(A7)

- Pointing(T17)

- Calibrate(Cam2)

- meets

- meets

- meets

- meets

- contains

- contains

- Turn(T17)

- meets

- meets

- Pointing(?direction)

## Coalescing

- Pointing(Earth)

- Off(Cam1)

- On(Cam2)

- CalibrationTarget(T17)

- Image(A7)

- Pointing(A7)

- Calibrated(Cam2)

- TakeImage(A7, Cam2)

- meets

- contains

- contains

- Turn(A7)

- Pointing(T17)

- Calibrate(Cam2)

- meets

- meets

- meets

- meets

- contains

- contains

- Turn(T17)

- meets

- meets

## POCL vs CBI

- 	    POCL	   CBI
- search	goal-directed	 goal-directed
- strategy
- temporal	before/after	complex
- reasoning
- protection	causal links	  meets & contains
- conflicts	    threats	  mutex
- conflict	   proactive	    lazy
- resolution

## CBI  Planners

- Zeno (Penberthy)	intervals, no CSP
- Trains (Allen)
- Descartes (Joslin)	extreme least commitment
- IxTeT (Ghallab)	functional rep.
- HSTS (Muscettola)	functional rep., activities

## Timelines

- Pointing=Turn (?target)
- 	met-by		Pointing=?direction
- 	meets		Pointing=?target

- Earth

- A7

- Turn(A7)

- T17

- ?direction

- ?

- Pointing:

- Turn (?target)
- 	met-by		Pointing(?direction)
- 	meets		Pointing(?target)

## CBI vs POCL

- Less commitment
- CSP propagation
- Timelines

## Salvation

- Reachability & mutex analysis
- Distance heuristics

## Reachability Analysis

- Pointing(Earth)

- Pointing(A7)

- Calibrate(Cam1,T5)

- Status(Cam1, Calibrated)

- meets

- contains

- Turn(A7)

- meets

- [0]

- [0, ∞]

- [5, ∞]

- meets

- [5, ∞]

- Pointing(T5)

- Turn(T5)

- [3, ∞]

- meets

- [3, ∞]

- meets

- [0, ∞]

- [3, ∞]

- [8, ∞]

- [0, 13]

- mutex rules more complex
-  (Smith & Weld - IJCAI99)

- [0, ∞]

## Distance Heuristics

- Distance metrics
- time required
- fuel required
- ...

## Summary

**Performance advances**
**Mutex & distance heuristics**
**Resources**
**Reusable – ****n-ary mutex**
**Consumable – ****equality & inequality**
**Time**
**Intervals, CBI**
**Relevance**

## Relevance to DX

- Repair
- shutdown, access, multiple steps, restart
- Control of broken device
- isolation (test generation)
- continued operation
- DX as planning
- finding “program” of events