  We introduce an approach to high-level conditional planning we call
epsilon-safe planning. This probabilistic approach commits us to planning to
meet some specified goal with a probability of success of at least 1-epsilon
for some user-supplied epsilon. We describe several algorithms for epsilon-safe
planning based on conditional planners. The two conditional planners we discuss
are Peot and Smith's nonlinear conditional planner, CNLP, and our own linear
conditional planner, PLINTH. We present a straightforward extension to
conditional planners 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 epsilon-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.
