Evaluating the Trade-Offs in Partial-Order Planning Algorithms
Abstract
Most practical partial-order planning systems employ some form of goal protection. However, it is not clear from previous work what the tradeoffs are between the different goal protection strategies. Is it better to protect against all threats to a subgoal, some threats, or no threats at all? In this paper, we consider three well-known planning algorithms, SNLP, NONLIN, and TWEAK. Each algorithm makes use of a different goal protection strategy. Through a comparison of the three algorithms, we provide a detailed analysis of different goal protection methods, in order to identify the facts that determine the performance of the systems. The analysis clearly shows that the relative performance of the different goal-protection methods used by the systems, depends on the characteristics of the problems being solved. One of the main determining factors of performance is the ratio of the number of negative threats to the number of positive threats. We present an artificial domain where we can control this ratio and show that in fact the planners show radically different performance as the ratio is varied. The implication of this result for someone implementing a planning system is that the most appropriate algorithm will depend on the types of problems to be solved by the planner. Partial-order planning, Goal protection, Algorithms, TWEAK, SNLP, NONLIN
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1994
- Accession Number
- ADA285876
Entities
People
- Craig Knoblock
- Qiang Yang
Organizations
- University of Southern California