Epsilon-safe Planning

Decision-Theoretic Planning

Volume

Papers from the 1994 AAAI Spring Symposium

Contents

We introduce an approach to high-level conditional planning we call e-safe planning. This probabilistic approach commits us to planning to meet some specified goal with a probability of success of at least 1-e for some user-supplied e. We describe an algorithm for e-safe planning based on PLINTH, a conditional linear planner we have developed. We present a straightforward extension to PLINTH for which computing the necessary probabilities is simple, employing a commonly-made but perhaps overly-strong independence assumption. We also discuss a second approach to e-safe planning which relaxes this independence assumption, involving the incremental construction of a probability dependence model in conjunction with the construction of the plan graph.