# Presentation: 034871

## Incremental Contingency Planning  Richard Dearden, Nicolas Meuleau, Sailesh Ramakrishnan, David E. Smith, Rich Washington

- ?

## Why Contingency Planning ??

- CPU, memory, time
- Safety
- sequence checking
- Anticipation
- setup steps

## The Planning Problem

**Visual servo (.2, -.15)**

**Warmup NIR**

**Dig(5)**

**Drive(-1)**

**NIR**

**.........**

**Compress**

**Drive(2)**

**Maximize (Expected) Scientific Return**

**Given:**
**start time**
**pose**
**energy available**
**actions with uncertain:**
**durations**
**resource usage**
**Possible science objectives**
**images**
**samples**

## Technical Challenges

- Continuous time (& resources)
- Continuous outcomes
- Time (& resource) constraints
- Concurrency
- Goal selection & optimization
- g1, g2, g3, g4 ...

## Just in Case (JIC) Scheduling

**Just in Case (JIC) Scheduling**

- 1.	Seed schedule
- 2.	Identify most likely failure
- 3.	Generate a contingency branch
- 4.	Integrate the branch

**Advantages:  **
**Tractability**
**Simple plans**
**Anytime**

**.4**

**.2**

**.1**

## Just in Case (JIC) Planning

**Just in Case (JIC) ****Planning**

- 1.	Seed plan
- 2.	Identify most likely failure
- 3.	Generate a contingency branch
- 4.	Integrate the branch

**.4**

**.2**

**.1**

## Limits of JIC Scheduling Heuristics

**Dig(60)**

**Visual servo (.2, -.15)**

**Lo res**

**Rock finder**

**LIB**

- ** ****= 120s**
- ** ****= 60s **

- ** ****= 300s**
- ** ****= 5s **

- ** ****= 1000s**
- ** ****= 500s **

**t** ****** [9:00, 16:00]**
- ** ****= 5s**
- ** ****= 1s **

- ** ****= 120s**
- ** ****= 20s **

**V = 50**

**HiRes**

**V = 10**

**t** ****** [10:00, 13:50]**
- ** ****= 600s**
- ** ****= 60s **

**t** ****** [9:00, 14:30]**
- ** ****= 5s**
- ** ****= 1s **

**V = 5**

**Warmup LIB**

- ** ****= 1200s**
- ** ****= 20s **

**Most probable failure points may not be the best branch-points:**
- It is often too late to attempt other goals when the plan is about to fail.** **

****** ****:**** ****most probable failures**
**$  **** **** ****: most interesting branch point**

- True for all initial states in the grey box.

- 

- 

**Drive (-2)**

**NIR**

- 

**V = 100**

**t** ****** [10:00, 14:00]**
- ** ****= 600s**
- ** ****= 60s **

**$**

## Just in Case (JIC) Planning

**Just in Case (JIC) ****Planning**

- 1.	Seed plan
- 2.	Identify best branch point
- 3.	Generate a contingency branch
- 5.  Evaluate & Integrate the branch

**?**

**?**

**?**

**Construct plangraph**
**Back-propagate value tables**
**Compute gain**
**Select branch condition & goals**

**?**

**r**

**V****b**

**V****m**

## Construct Plangraph

**g****1**

**g****2**

**g****3**

**g****4**

## Value Tables

**g****1**

**g****2**

**g****3**

**g****4**

**V****1**

**V****2**

**V****3**

**V****4**

**r**

**r**

**r**

**r**

## Example 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Simple Propagation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Simple Propagation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Simple Propagation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Conjunctions 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 2

- t

## Propagation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 2

- t

## Propagation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Combining Tables 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Discharging Assumptions 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Propagation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

## Combining Tables 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 5

## Combining Tables 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 5

- 5

- 25

- 8

## Ordering 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 5

- 5

- 25

- 8

- DCE

- CDE

- AB

## Achieving Multiple Goals 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 5

- 5

- 25

- 15

- 5

- 25

- 8

- 30

- g+g’

- g

- g’

- +

## Achieving Multiple Goals 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 5

## Goal Annotation 

- A

- E

- B

- (1, 5)

- (3, 3)

- (10, 15)

- (10, 15)

- (2, 2)

- C

- D

- s

- t

- r

- q

- p

- g

- g’

- 1

- 5

- g

- g

- g’

- g’

- g’

- g’

- g’

## Just in Case (JIC) Planning

**Just in Case (JIC) ****Planning**

- 1.	Seed plan
- 2.	Identify best branch point
- 3.	Generate a contingency branch
- 5.  Evaluate & Integrate the branch

**?**

**?**

**?**

- Construct plangraph
- Back-propagate value tables
- Compute gain
- Select branch condition & goals

**?**

**r**

**V****b**

**V****m**

## Estimating Branch Value

**V****1**

**V****2**

**V****3**

**V****4**

**V**

**r**

**V**

**r**

**V**

**r**

- Max

## Plan Statistics

**r**

**V****1**

**V****2**

**V****3**

**V****4**

**P**

**r**

**plan value function**

**resource probability**

**V****m**

## Expected Branch Gain

**V****1**

**V****2**

**V****3**

**V****4**

**P**

**r**

## Selecting the Branch Condition

**V****1**

**V****2**

**V****3**

**V****4**

**P**

**r**

**branch **
**condition**

**branch **
**condition**

## Selecting Branch Goals

**r**

**V****1**

**V****2**

**V****3**

**V****4**

**P**

**r**

**branch **
**goals**

- g1

- g3

- g3

- g1

## Evaluating the Branch

- 1.	Seed plan
- 2.	Identify best branch point
- 3.	Generate a contingency branch
- 4.	Evaluate & integrate the branch

**?**

**?**

**?**

**?**

**Compute value function**
**Compute actual gain**

## Actual Branch Gain

**r**

**V****b**

**P**

**r**

**V****m**

**Branch value function**

**actual branch condition**

## Remarks: Single Plangraph

**Remarks: ****Single Plangraph**

- 1.	Seed plan
- 2.	Identify best branch point
- 3.	Generate a contingency branch
- 5.  Evaluate & Integrate the branch

**?**

**?**

**?**

- Construct plangraph
- Back-propagate value tables
- Compute gain
- Select branch condition & goals

**?**

**r**

**V****b**

**V****m**

## Plan Graph

**g****1**

**g****2**

**g****3**

**g****4**

**V****1**

**V****2**

**V****3**

**V****4**

**r**

**r**

**r**

**r**

## Branch Initial Conditions

**v**

**r**

**v**

**r**

**v**

**r**

**v**

**r**

**v**

**r**

- {p}

- {q,r}

- {p,r}

## Single Plangraph

- 1.	Seed plan
- 2.	Identify best branch point
- 3.	Generate a contingency branch
- 4.	Evaluate & integrate the branch

**?**

**?**

**?**

**?**

- Discharge conditions
- Compute gain
- Select branch condition & goals

- Construct single plangraph
- Back-propagate value tables

## Issues

**Sensor costs**
**Setup steps**
**Utility updates**
**Floating contingencies**

## The End.

**The End.**