Automatically Selecting and Using Primary Effects in Planning: Theory and Experiments

The use of primary effects of operators is an effective approach to improving the efficiency of planning. The characterization of “good” primary effects, however, has remained at an informal level and there have been no algorithms for selecting primary effects of operators. We formalize the use of primary effects in planning and present a criterion for selecting useful primary effects, which guarantees efficiency and completeness. We analyze the efficiency of planning with primary effects and the quality of the resulting plans. We then describe a learning algorithm that automatically selects primary effects and demonstrate, both analytically and empirically, that the use of this algorithm significantly reduces planning time and does not compromise completeness.