On the Utility of Systematicity: Understanding Tradeoffs Between Redundancy and Commitment in Partial-Ordering Planning

Abstract

Although the idea of generating plans through nonlinear or partially ordered partially instantiated (POPI) planningI has been around for almost twenty years, it is only recently that the search space characteristics of POPI planners have received particular attention. A big thrust in this work has been on reducing the redundancy in the search space of POPI planners. This was largely motivated by the belief that redundancy reduction will lead to improvements in planning efficiency[10, 8]. One approach towards redundancy elimination, that turned out to be particularly influential (as evidencedby several closely related extensions [8, 18, 16, 2, 17]), was that of McAllester’s [8]. McAllester showed that it is possible to design a POPI planner that is systematic in the strong sense that it never visits two equivalent plans or plans having overlapping linearizations. Such systematic planners were claimed to be more efficient than planners that admit redundancy in their search space. While search space redundancy is an important factor affecting the efficiency of a P O PI planner, another (perhaps) equally important one is the level of commitment in the planner. After all, avoiding premature commitment was one of the primary motivations for POPI planning. There is a tradeoff between the redundancy elimination and least commitment, in that often the redundancy is eliminated at the expense of increased commitment in the planner. For example, McAllester’s planner achieves systematicity by keeping track of the causal structures of the plans generated during search, and ensuring that each branch of the search space commits to and protects mutually exclusive causal structures for the partial plans. We will see that such protection amounts to a strong form of premature commitment, which increases the amount of backtracking as well as the solution depth, and can have an adverse effect on the performance of the planner. In this paper we shall argue that the performance of a POPI planner depends more closely on the way it deals with the tradeoff between redundancy and commitment, than with the systematicity of its search. We will start with a rational reconstruction of the motivations behind systematicity in POPI planning and show that systematicity is just one extreme solution for the tradeoff between redundancy and commitment. We will show that there are a spectrum of solutions to this tradeoff, and identify the dimensions along which they vary. We will explore the relative utility of the different solutions through a comparative study of seven planners that fall at different points on the spectrum. Our studies show that