Design tradeoffs in partial order (plan space) planning

Abstract

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 refinement planning, and show that planners that search in the space of (partial) plans are specific instantiations of this algorithm. The different 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 size 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 focussed empiri...

Cite this paper

@article{b1994design,
  title = {{Design tradeoffs in partial order (plan space) planning}},
  author = {B, Subbarao Kambhampati},
  pages = {92--97},
  year = {1994}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers