Abstract

Most practical partial-order planning systems employ some form of goal protection. However, it is not clear from previous work what the tradeo s are between the di erent goalprotection 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 di erent goal-protection strategy. Through a comparison of the three algorithms, we provide a detailed analysis of di erent goal protection methods, in order to identify the factors that determine the performance of the systems. The analysis clearly shows that the relative performance of the di erent 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 articial domain where we can control this ratio and show that in fact the planners show radically di erent 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.

Date

January 1, 1970

Authors

Craig A Knoblock, Qiang Yang

Journal

PROCEEDINGS OF THE BIENNIAL CONFERENCE-CANADIAN SOCIETY FOR COMPUTATIONAL STUDIES OF INTELLIGENCE

Pages

279-286

Publisher

CANADIAN INFORMATION PROCESSING SOCIETY