Forward-chaining planning in nondeterministic domains

In this paper, we present a general technique for tak- ing forward-chaining planners for deterministic do- mains (e.g., HSP, TLPlan, TALplanner, and SHOP2) and adapting them to work in nondeterministic do- mains. Our results suggest that our technique pre- serves many of the desirable properties of these plan- ners, such as the ability to use heuristic techniques to achieve highly efficient planning.In our experimental studies on two problem domains, the well-known MBP algorithm took exponential time, confirming prior results by others. A nondeterminized version of SHOP2 took only polynomial time. The polynomial-time figures are confirmed by a complex- ity analysis, and a similar complexity analysis shows that a nondeterminized version of TLPlan would per- form similarly.