An Adaptive Planner based on Learning of Planning Performance

Saving and reusing previously constructed plans is largely regarded as a promising approach to deal with the intractability of domain-independent planning (Hammond 1989; Kambhampati and Hendler 1992). But it has been shown that syntactically matching a new problem with a candidate case is NP-hard, and modifying a plan to suit a new problem can be strictly more difficult than generating a plan from scratch (Nebel and Koehler 1995). We present a case-based planning system that does not involve any plan modification and performs case matching very efficiently. The system involves essentially a default planner, a plan library and learning from a set of training examples (cases solved by the default planner). To solve a new problem (with initial state INEW and goal state GNEW), a case (with initial state IR, goal state GR and solved plan PR) is retrieved from the library, such that the original task of finding a plan is reduced to that of finding two potentially simpler sub-plans. The first sub-plan PI transforms INEW into IR. The second sub-plan PG transforms GR into GNEW. If an appropriate case is retrieved, PI and PG can be constructed by the default planner with less computational effort, and a concatenation of PI, PR and PG constitutes a solution plan, as shown in the figure below. The most appropriate case is one where the predicted combined cost of developing PI and PG is the least, and significantly smaller than planning from scratch