@conference {18871, title = {Forward-chaining planning in nondeterministic domains}, year = {2004}, month = {2004///}, pages = {513 - 518}, abstract = {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. }, url = {https://www.aaai.org/Papers/AAAI/2004/AAAI04-082.pdf}, author = {Kuter,U. and Nau, Dana S.} }