A Comparison of the SNLP and TWEAK Planning Algorithms

Foundations of Automatic Planning - The Classical Approach and Beyond

Volume

Papers from the 1993 AAAI Spring Symposium

Contents

Most current partial-order planning systems are based on either the TWEAK or SNLP planning algorithms. Both planning algorithms are complete and correct. The SNLP algorithm distinguishes itself from TWEAK in that it is also systematic, so it never generates redundant plans in its search space. This paper compares the two planning algorithms and shows that SNLP'S systematicity property does not imply that the planner is more efficient than TWEAK. To compare the two systems, we review the SNLP algorithm and describe how it can be easily transformed into TWEAK. Then we present a complexity analysis of each system and identify the factors that determine the performance of the systems. Finally, we present results on a set of classic planning problems, which show that the relative performance of the two systems depends on the characteristics of the problems being solved.