Epsilon-Safe Planning
This work addresses probabilistic planning for AI systems, but it appears incremental as it builds on existing conditional planners with modest extensions.
The paper tackles the problem of high-level conditional planning by introducing epsilon-safe planning, which ensures a probability of success of at least 1-epsilon for a user-specified epsilon, and presents algorithms based on existing conditional planners like CNLP and PLINTH, with results including extensions using independence assumptions and a more complex approach relaxing these assumptions.
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.