# Presentation: 084100

## The Challenge of Duration Uncertainty 

- David E. Smith
- John Bresina, Keith Golden, Richard Dearden, Nicolas Meuleau, Sailesh Ramakrishnan, Rich Washington

## Outline

**The Problem**
**objectives (goals)**
**actions**
**Approaches**
**(neo-) classical**
**MDP**
**heuristic augmentation**

## Operational Characteristics

**Brain dead**
**radiation**
**power**
**Safety**
**no risky operations**
**Communication**
**twice/day**

## ...............

**Brain dead**
**radiation**
**power**
**Safety**
**no risky operations**
**Communication**
**twice/day**

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

**Warmup NIR**

**Dig(5)**

**Drive(-1)**

**NIR**

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

**Compress**

**Drive(2)**

**1. Plan on the ground**

**3. Uplink**

**long**

**2. Extensive checking/simulation**

## The Planning Problem

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

**Warmup NIR**

**Dig(5)**

**Drive(-1)**

**NIR**

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

**Compress**

**Drive(2)**

**Maximize Scientific Return**

**Initial conditions**
**start time**
**pose**
**power available**
**...**
**Possible science objectives**
**images**
**samples**

## The Objectives

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

**Dig(5)**

**Drive(-1)**

**NIR**

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

**Compress**

**Drive(2)**

**Maximize Scientific Return**

**v=100**

**v=30**

**Warmup NIR**

**Decision Theoretic:**
**objectives are valued**
**choose**

**Initial conditions**
**start time**
**pose**
**power available**
**...**
**Possible science objectives**
**images**
**samples**

## The Real Problem

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

**Drive (-1)**

**Dig(60)**

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

**NIR**

**E > .1 Ah**
- ** ****= .05 Ah**
- ** ****= .02 Ah **

**E > .6 Ah**
- ** ****= .2 Ah**
- ** ****= .2 Ah **

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

**E > 7 Ah**
- ** ****= 5 Ah**
- ** ****= 2.5 Ah **

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

**V = 100**

**Compress**

**V = 10**

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

**E > 3 Ah**
- ** ****= 2 Ah**
- ** ****= .5 Ah **

**Warmup NIR**

**E > 5 Ah **
- ** ****= 3 Ah**
- ** ****= .5 Ah **

- ** ****= 400s**
- ** ****= 20s **

**Drive (2)**

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

## Uncertain Usage

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

**Drive (-1)**

**Dig(60)**

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

**NIR**

**E > .1 Ah**
- ** ****= .05 Ah**
- ** ****= .02 Ah **

**E > .6 Ah**
- ** ****= .2 Ah**
- ** ****= .2 Ah **

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

**E > 7 Ah**
- ** ****= 5 Ah**
- ** ****= 2.5 Ah **

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

**V = 100**

**Compress**

**V = 10**

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

**E > 3 Ah**
- ** ****= 2 Ah**
- ** ****= .5 Ah **

**Warmup NIR**

**E > 5 Ah **
- ** ****= 3 Ah**
- ** ****= .5 Ah **

- ** ****= 400s**
- ** ****= 20s **

**Drive (2)**

**Uncertain durations**

**Uncertain resource usage**

## Time & Resource Constraints

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

**Drive (-1)**

**Dig(60)**

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

**NIR**

**E > .1 Ah**
- ** ****= .05 Ah**
- ** ****= .02 Ah **

**E > .6 Ah**
- ** ****= .2 Ah**
- ** ****= .2 Ah **

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

**E > 7 Ah**
- ** ****= 5 Ah**
- ** ****= 2.5 Ah **

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

**V = 100**

**Compress**

**V = 10**

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

**E > 3 Ah**
- ** ****= 2 Ah**
- ** ****= .5 Ah **

**Warmup NIR**

**E > 5 Ah **
- ** ****= 3 Ah**
- ** ****= .5 Ah **

- ** ****= 400s**
- ** ****= 20s **

**Drive (2)**

**Time constraints**

**Resource constraints**

## How hard is it?

## How hard is it?

## Whazzzzup?

**Whazzzzup?**

## The Culprits

- Continuous time (& resources)
- Continuous outcomes
- Time (& resource) constraints
- Concurrency

**Time**

**Power**

**Storage**

**NIR**

**E > 2 Ah**

**t** ****** [10:00, 14:00]**

## The Culprits

**  ****Optimization**
**  ****Simplicity constraints**

**The Culprits**

- Continuous time (& resources)
- Continuous outcomes
- Time (& resource) constraints
- Concurrency

**Time**

**Power**

**Storage**

**NIR**

**E > 2 Ah**

**t** ****** [10:00, 14:00]**

## Outline

**The Problem**
**objectives (goals)**
**actions**
**Approaches**
**(neo-) classical**
**MDP**
**Heuristic augmentation**

## Classical Planning under Uncertainty

**Problems**

## MDP’s & POMDPS

**Non**
**Observable**

**Partially**
**Observable**

**Fully**
**Observable**

**CGP**
**CMBP**
**C-PLAN**
**Fragplan**

**SENSp**
**Cassandra**
**PUCCINI**
**SGP**
**QBF-Plan**
**GPT**
**MBP**

**WARPLAN-C**
**CNLP**

**Disjunction**

**Buridan**
**UDTPOP**

**C-Buridan**
**DTPOP**
**C-MAXPLAN**
**ZANDER**
**Mahinur**
**POMDPs**

**JIC**
**Plinth**
**Weaver**
**PGP**
**MDPs**

**Probability**

- Goal selection &optimization

**Advantages**

**Problems**

## Outline

**The Problem**
**objectives (goals)**
**actions**
**Approaches**
**(neo-) classical**
**MDP**
**Heuristic**
**Conservative planning**
**Augmentation**

## Conservative Planning

**Conservative Planning**

**Drive (-2)**

**Dig(60)**

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

**NIR**

**Lo res**

**Rock finder**

**NIR**

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

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

**V = 100**

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

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

**V = 50**

**HiRes**

**V = 10**

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

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

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

**V = 5**

**t=13:40**

**1500s**

**t=14:05**

**t=14:06**

**t=14:07**

**Assume ****t= ******** + ******

## Heuristic Augmentation

- Plan
- based on expectations
- Analyze
- utility of result
- Augment
- add a branch

## Just in Case (JIC) Scheduling

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

**Advantages:  **
**Tractable**
**Simple plans**
**Anytime**

**.1**

**.4**

**.2**

## The Seed

**Drive (-2)**

**Dig(60)**

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

**NIR**

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

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

**V = 100**

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

**t=13:35**

**Assume ****t= ******

**V = 50**

**t=13:52**

**t=13:53**

**t=13:54**

## Failure Point

**Drive (-2)**

**Dig(60)**

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

**NIR**

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

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

**V = 100**

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

**t=13:35**

**t=13:52**

**t=13:53**

**t=13:54**

## Failure Point

**Drive (-2)**

**Dig(60)**

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

**NIR**

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

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

**V = 100**

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

**t=13:35**

**Assume ****t= ******

**t=13:52**

**t=13:53**

**t=13:54**

**HiRes**

**V = 10**

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

## Where the Branch *Should* Go

**Drive (-2)**

**Dig(60)**

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

**NIR**

**Lo res**

**Rock finder**

**LIB**

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

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

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

**V = 100**

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

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

**V = 50**

**HiRes**

**V = 10**

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

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

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

**V = 5**

**Warmup LIB**

**t=13:40**

**1500s**

**t=14:05**

**t=14:10**

**t=14:12**

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

## Why?

**Drive (-2)**

**Dig(60)**

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

**NIR**

**Lo res**

**Rock finder**

**LIB**

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

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

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

**V = 100**

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

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

**V = 50**

**HiRes**

**V = 10**

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

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

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

**V = 5**

**Warmup LIB**

**t=13:40**

**1500s**

**t=14:05**

**t=14:10**

**t=14:12**

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

- Intermediate steps
- No inherent value
- Low impact on P
- Value of alternatives
- higher

## Just in Case (JIC) Planning

- Just in Case (JIC) Planning

- 1.	Seed plan
- 2.	**Identify best branch point**
- 3.	Generate a contingency branch
- 4.	Integrate the branch

**?**

**?**

**?**

## Evaluating Branch Points

- Probability distributions
- for time & resources
- Utility of current plan
- as a function of time & resources
- Expected utility of a branch
- as a function of time & resources

**Drive (-2)**

**Dig(60)**

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

**NIR**

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

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

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

**t=13:35**

**V = 100**

- Branch condition
- Utility gain

## Estimating Branch Utility

- Probability distributions
- for time & resources
- Utility of current plan
- as a function of time & resources
- Expected utility of a branch
- as a function of time & resources

**Drive (-2)**

**Dig(60)**

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

**NIR**

- ** ****= 40s**
- ** ****= 20s **

- ** ****= 60s**
- ** ****= 1s **

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

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

**t=13:35**

**V = 100**

- Build PlanGraph
- Back-propagate
- utility distributions

## Final Points

**Final Points**

- Continuous time (& resources)
- Continuous outcomes
- Time (& resource) constraints
- Concurrency

**Time**

**Power**

**Storage**

**NIR**

**E > 2 Ah**

**t** ****** [10:00, 14:00]**

**Nasty combination!**

**Pervasive to **
**observation planning**

**Existing approaches**
**painfully inadequate**

**World has round dice**

## Points

- Nasty Combination:
- Duration uncertainty
- Time constraints
- Features of:
- Rovers
- Observation planning
- Continuous outcomes common
- The world has round dice

## Computing Failure Probability

**t****0**

**D****1****(t) = ∆****0****(t-t****0****)**

**D****2****(t) = ∆****1****o ****D****1**

**...**

**D****3****(t) = ∆****2****o ****D****2**

**...**

## Computing Failure Probability

**[10 ,12]**

**[11 ,12]**

**[12 ,13]**

**[12 ,14]**

**t****0**

**D****1****(t) = ∆****0****(t-t****0****)**

**D****2****(t) = ∆****1****o ****D****1**

**...**

**P****1**** = ****∫****c****1****D****1****(t)**

**P****2**** = P****1**** ****∫****c****2****D****2****(t)**

**D****3****(t) = ∆****2****o ****D****2**

**...**