EXPLOITING CAUSAL STRUCTURE TO CONTROL RETRIEVAL AND REFITTING DURING PLAN REUSE

The ability to reuse existing plans to solve new planning problems can enable a domain‐independent planner to improve its average case efficiency by exploiting the problem distribution and avoiding repetition of planning effort. The pay‐off from plan reuse, however, crucially depends on finding effective solutions to two important underlying control problems: (i) controlling the retrieval of an appropriate plan and mapping to be reused in a new situation, and (ii) controlling the modification (refitting) of the retrieved plan so as to minimize perturbation to the applicable parts of the plan. This paper is concerned with the development of efficient domain‐independent solutions to these two problems. For the retrieval, it provides a domain independent similarity metric that utilizes the plan causal dependency structure to estimate the utility of reusing a given plan in a new problem situation. For the refitting, it presents a minimum‐conflict heuristic, again based on the causal dependency structure of the plan, to conservatively control the modification. The paper also discusses the implementation and evaluation of these strategies within the PRIAR plan modification framework.