Design Tradeoffs in Partial Order (Plan Space) Planning

Subbarao Kambhampati

Despite the long history of classical planning, there has been very little comparative analysis of the performance tradeoffs offered by the multitude of existing planning algorithms. This is partly due to the many different vocabularies within which planning algorithms are usually expressed. In this paper I provide a generalized algorithm for refinemant planning, and show that planners that search in the space of (partial) plans are specific instantiations of this algorithm. The differont design choices in partial order planning correspond to the different ways of instantiating the generalized algorithm. I will analyze how these choices affect the search-space slze and refinement cost of the resultant planner. Finally, I will concentrate on two specific design choices, viz, protection strategies and tractability refinements, and develop some hypotheses regarding the effect of these choices on the performance on practical problems. I will support these hypotheses with a focused empirical study.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.