# Presentation: 037085

## Probabilistic Reasoningfor Robust Plan Execution

**Steve Schaffer, Brad Clement, Steve Chien****{first_name.last_name}@jpl.nasa.gov****Artificial Intelligence Group****Jet Propulsion Laboratory****California Institute of Technology**

## Handling Uncertainty

- Why?
- Better account for competing requirements of safety, science, and engineering concerns
- Sequence generation and validation rely on the accuracy of models
- Current process limits the capabilities by
- improperly evaluating alternative courses of action
- restricting the time horizon of operations between command uplinks
- Fully exploit the capabilities of a spacecraft and enable greater autonomous operation
- Capabilities
- Avoid constraint violations
- Identify sources of greatest risk
- Balance risk and efficiency
- Allow for varying user risk preferences
- Make execution more reliable

- Approaches
- Conservative estimates of effects
- Bound resource capacities
- Slack padding
- Re-planning
- Handle in execution system
- Contingency planning

## Main Idea

- Represent uncertainty of action effects and durations as parametric, continuous probability distribution functions
- Propagate distributions through plan to project states/resources
- Score plan based on risk
- risk = probability outside limits
- Plan to reduce risk

## “Full Probabilistic” Modeling

- Durations and resource usage normally distributed

## Modeling Approximations

- Full probabilistic
- Means only
- Track only the expected value (mean)
- Same as non-probabilistic risk-ignorant
- Pessimistic
- Track only “worst” possible value
- “Worst” depends on domain / resource
- Single peak
- For time-dependent multimodals
- Track only one “average” Gaussian
- Chebyshev bound
- Distribution-free limit on probability density
- Only track the mean and standard deviation

- single peak

## Evaluation Domains

- Abstract testbed
- one resource
- various consumers, replenishers
- schedule within time horizon
- conflicts resolvable
- Orbiter domain
- image planet, process, downlink
- ~10 resources, ~10 actions
- schedule goals within horizon
- conflicts not all resolvable – must minimize

**Notes:**
The testbed had different actions available to it depending on what was being tested.

The Orbiter domain actions make reservations on multiple resources. It must deal with windows of opportunity for imaging and downlink. There is also not necessarily a perfect solution.

## Evaluation Methodology

- Generate plan (batch mode)
- Use different approximations
- Planner is not allowed to remove goals
- Run plan on stochastic simulator
- Score execution by # errors caused
- error = resource oversubscribed

**Notes:**
The stochastic simulator used the same probability distributions as were modeled. We have not evaluated the effect of differing modeled and actual distributions (yet).

## Planning in ASPEN

- Start
- (if conflicts exist and user time-limit not exceeded)

- ...

- Select probable conflict

- Select a repair method

- ...

- move

- ...

- ...

- Select an activity

- Select a start time

## Results: Abstract Domain

- Full probabilistic performs best
- Single peak performs well when variance low
- Chebyshev worst

**Notes:**
Discussion??

## Results: Runtime

|  | Full probabilistic | Means only | Pessimistic | Single peak | Chebyshev |
| --- | --- | --- | --- | --- | --- |
| consumable | 35s | 2s | 2s | 30s | 25s |
| consumable 2x std dev | 35s | 2s | 2s | 35s | 25s |
| non-consumable | 3s | 3s | 400s | 5s | 600s |

- Mean run times on the abstract domain problems
- Runs were terminated after 2000 iterations

## Results: Orbiter Domain

- Full probabilistic performs best
- Single peak performs well
- Chebyshev worst

## Results: Problem Size

- Means only worse on average for larger problems

## Results: Problem Difficulty

## Results: User Risk Metric

- Means only worse on average for low risk tolerance

## Result: Time Behavior

## Conclusions

- Alternative methods for handling uncertain continuous variables
- Full probabilistic reasoning is most robust
- superior plans
- fewer errors
- tailored to user risk attitudes
- but requires modeling overhead
- and computationally expensive
- suited for high risk-averseness / cost of failure
- Naive approximations do almost as well

## Future Directions

- Direct temporal constraints
- Domain-specific pessimistic approximation
- Need to also evaluate
- bounded distributions
- particle filter representation
- Integration with execution system
- observations update distributions
- dynamic replanning

## Overcoming Normal Representation Inaccuracies

- Normals give probability to valuesfrom -∞ to ∞
- Variable domain inaccuracy
- duration must be greater than zero
- usage is either > 0 or < 0 (if replenishing)
- more problematic with small means and high variance
- Timeline domain inaccuracy
- Resources often have only one bound of conflict(e.g. can’t have an overfull battery)
- Becomes a problem for mixture of consumers and replenishers

## Solution to variable domain inaccuracy
redistribute impossible value probability intonormal

Timeline domain inaccuracy
move impossible value probabilityinto a spike withsame integral

- redistribute impossible value probability intonormal
- Timeline domain inaccuracy
- move impossible value probabilityinto a spike withsame integral

*Overcoming Normal Representation Inaccuracies*

## Particle Filter Representation

- Commonly used for robot localization
- A Monte Carlo simulation draws sample values (particles) from source random variables toderive likelihoods of alternative states

- In a planner, the particles approximate state/resource projections; the more particles, the more precise the estimate
- Gets around exponential peak computations of normal representation by trading precision and time

## Handling Temporal Constraints

- A good execution system can issue a command when a preceding activity finishes.
- When activities are giventemporal constraints (e.g. back-to-back), thereshould be no probability ofoverlap.
- To handle this, a Bayes net can be constructed based on temporal constraints to calculate the resource distribution resulting from different possible usage contribution combinations.