On the Utility of Systematicity: Understanding Tradeoffs between Redundancy and Commitment in Partial-ordering Planning

Abstract

Recent work on foundations of partial-order planning has emphasized the importance of systematicity and elimination of redundancy in search space as a way to improve planning performance. In this paper, we investigate the utility of systematicity. Starting with a a rational reconstruction of the motivations for systematicity, we will conclude that it eliminates redundancy in the search space at the expense of increased commitment during planning. This increase in commitment leads to higher backtracking and increased solution depth, both of which can adversely affect the performance of the planner. We will argue that the performance of a planner is correlated more closely with the way it balances the tradeoff between redundancy and commitment, than with the systematicity of its search. We will discuss a spectrum of solutions for dealing with the redundancy-commitment tradeoff and show that systematic planners are at one extreme of this spectrum, with total least commitment planners like lWEAK on the other extreme. Based on empirical studies with seven planners that fall at different points in this spectrum, we will demonstrate that more efficient planners lie in the middle rather than at the extremes of this spectrum. We also identify characteristics of planners and problems that are predictive of planning performance.