Evaluating the Trade-Offs in Partial-Order Planning Algorithms

摘要

Most practical partial-order planning systems employ some form of goalprotection. 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.