language: en

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

Eugene Fink
School of Computer Science Carnegie Mellon University
Pittsburgh, PA 15213, USA
eugene@cs.cmu.edu
Qiang Yang
School of Computing Science Simon Fraser University
Burnaby, BC V5A1S6, Canada
qyang@cs.sfu.ca

Abstract 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.

[Eugene Fink is supported by Wright Laboratory, Aeronautical Systems Center, Air Force Materiel Command, USAF, and the Advanced Research Projects Agency (ARPA) under grant number F33615-93-1-1330. Qiang Yang is supported by Natural Sciences and Engineering Research Council of Canada (NSERC) under grant number OGP0184883.]