Accession Number:

ADA455918

Title:

Forward-Chaining Planning in Nondeterministic Domains

Descriptive Note:

Conference paper

Corporate Author:

MARYLAND UNIV COLLEGE PARK DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Kuter, Ugur
• Nau, Dana

Report Date:

2004-01-01

Pagination or Media Count:

7.0

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.

Descriptors:

• *ARTIFICIAL INTELLIGENCE
• ALGORITHMS
• REPRINTS
• MATHEMATICAL LOGIC
• TIME STUDIES
• POLYNOMIALS
• HEURISTIC METHODS

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE