Forward-Chaining Planning in Nondeterministic Domains
Abstract
This paper presents a general technique for taking forward-chaining planners for deterministic domains (e.g., HSP, TLPlan, TALplanner, and SHOP2) and adapting them to work in nondeterministic domains. Our results suggest that our technique preserves many of the desirable properties of these planners, such as the ability to use heuristic techniques to achieve highly e cient 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 complexity analysis, and a similar complexity analysis shows that a nondeterminized version of TLPlan would perform similarly.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2004
- Accession Number
- ADA455918
Entities
People
- Dana S. Nau
- Ugur Kuter
Organizations
- University of Maryland