Automatically Selecting and Using Primary Effects in Planning: Theory and Experiments,
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
Using primary effects of operators in planning is an effective approach to reducing planning time and improving solution quality. However, the characterization of good primary effects has remained at an informal level. In addition, no method has previously been known to automatically learn the primary effects of operators from a given domain specification. In this paper we formalize the use of primary effects in planning, present a criterion for selecting useful primary effects that guarantee the efficiency and completeness of planning, and prove the near-optimality of solutions found by planning with primary effects. Based on the formalization, we describe an inductive learning algorithm that automatically selects primary effects of operators. We show that the learning algorithm performs efficiently, producing plans that are near-optimal with high probability. We also empirically demonstrate the effectiveness of the learned primary effects in reducing search.
- Personnel Management and Labor Relations