An adaptive planner based on learning of planning performance

Abstract

Planning in complex domains can be computationally very expensive. One way of improving planning efficiency is to make use of past experience so as to avoid repetition of planning effort. This is the idea behind the case-based planning framework, where plans are not constructed from scratch, but rather are retrieved from a case library and adapted to solve the current problem. But case-based planners often face the problem of incurring more computational cost for retrieving and modifying a case for reuse, than what can be saved by reusing the case. In this work, a case-based planning system is presented that learns to predict the performance of a given planner (called the default planner) in a training phase, and exploits this knowledge to retrieve and reuse cases such that planning effort is saved. The system does not involve any modification of the plan being reused. This is a salient aspect of the system, since many case-based planners involve plan modification, which has been shown to be at least as expensive as generating a plan from scratch, in the worst case. Furthermore, the system uses a very efficient method for matching a new problem with solved cases. The average-case performance of an implementation of the system has been found to be significantly better than that of the default planner in a test domain. It is hypothesized that this approach can be used to improve the performance of other planners as well. The effectiveness of the system hinges mainly on the learning strategy and on the extraction of relevant features.