@Article{BergmannMunozavilaVelosoMelis1998,
author = {Bergmann, R and Muñoz-Avila, H and Veloso, M and Melis, E},
title = {Case-Based Reasoning Applied to Planning},
booktitle = {Case-Based Reasoning Technology, From Foundations to Applications},
editor = {Lenz, M; Bartsch-Spörl, B; Burkhard, HD; Wess, S},
publisher = {Berlin:Springer-Verlag},
year = {1998},
ISSN = {0302-9743 (Print), 1611-3349 (Online)},
ISBN = {3540645721},
volume = {1400/1998},
pages = {169-199}
}
The chapter summarized here is from a book on case-based reasoning (CBR) and reviews four planning systems that use CBR built on top of generative planners to design new plans.
Planning software is used by organizations to allocate resources over time to achieve a goal. Sophisticated packages can use AI techniques to determine the best order to carry out tasks and are used in areas such as disaster relief and transportation. Classical techniques for such planning involve a search through a space of possible actions, which can be very slow. Such generative planners start at an initial state and use defined actions (called operators) to reach certain goals. Many of these methods are based on the STRIPS (Stanford Research Institute Problem Solver) planner from the 1970s.
Typically planning systems define their plans using a restricted language with terms for the initial and final states and the operations that can be made to go between them. Planning is difficult because the space of possible steps that has to be searched is very large and each step can change the options available.
The systems described in the book chapter reviewed here consolidate the experience gained in previous activities to speed up the design of new plans (sometimes by a factor of 1000). An important aspect of the design of such systems is the trade-off between adapting a few cases to fit a problem and having to search through many cases to find a better fit. Two approaches to reusing cases are transformational adaptation, where the case is modified to fit the problem, and generative adaptation, where different cases can be combined for a better fit.
The four systems are compared in this chapter on how they retrieve, reuse, revise, and retain cases, and on how they perform in their environments. The authors of the chapter were all involved in creating their respective systems.
PRODIGY/ANALOGY, developed at Carnegie Melon, was the first planner to combine STRIPS-style generative planning with case-based reasoning. It uses means-ends analysis with a backward-chaining, state-space search. The project is led by Manuela Veloso, one of the authors of this chapter. The system stores each solution together with a justification for each decision. These justifications are indexed and can be used in similar problems to guide the search for solutions. PRODIGY/ANALOGY uses generative adaptation to merge cases. This is also called a reconstructive method as lines of reasoning are transferred. As cases are written in a simple language, they can be interleaved so that the goals from one match those of another and can build toward a solution. The system is used in transportation and logistics.
CAPLAN/CBC (Computer Assisted Planning/Case-Based Control), from the University of Kaiserslautern, was tested in planning processes for manufacturing mechanical workpieces where raw pieces of metal have to be cut into specific shapes on a lathe in specific steps. Because such pieces have to be machined in a certain order, the software uses a geometric reasoner to determine which goals rely on which others and so which cases can be retrieved. CAPLAN/CBC uses partial-order planning, where the order of steps in the plan is decoupled from the order in which the steps are generated. The user may intervene in the process to change the order of tasks. The planning component CAPLAN is built on the REDUX problem solver where decisions are used to achieve goals on a goal graph. A case contains the goals plus accepted and rejected decisions and their justifications. After a case is selected, its goals are mapped onto the problem and steps selected that can be used. Héctor Muñoz-Avila is one of the authors.
PARIS (Plan Abstraction and Refinement in an Integrated System), also from the University of Kaiserslautern, is a domain-independent planner and uses a more abstract method of retrieving, reusing and retaining cases. This simplifies the cases and reduces their number while making them more flexible for reuse. Concrete cases are converted into abstract cases by aggregating the steps into higher-level functions. Different levels of abstraction can then serve as a hierarchical index for the concrete cases they were derived from and used to match the problem and can also be used to prune out unneeded cases. Reusing and adapting a case then consists of the generative planner rebuilding the detailed back into the steps. PARIS has been tested in manufacturing and shown to be fast and flexible. Ralph Bergmann is one of the creators of PARIS.
Finally, ABALONE, from the Universities of Saarbrücken and Edinburgh, uses cases in proving theorems. Erica Melis is one of the creators of this method. In this domain, a proof is achieved through axioms, lemmas, and theorems. ABALONE is built on the proof planner CLAM from Edinburgh, which uses induction and heuristics to create plan for finding a proof. ABALONE adds a level where analogies from previous proofs can be used to devise a new plan. The system finds a mapping from a retrieved source theorem to the target problem and reformulates the steps as needed. The system also stores justifications so that it can suggest lemmas needed, and can override the heuristics and default configurations of the CLAM planner.
The chapter ends by summarizing the differences in how the four packages store, retrieve, reuse, and adapt cases. It also mentions other similar systems including PRIAR (a hierarchical planner), MRL (for formal logic), PLAGIATOR (a theorem prover), and MPA (Multi-Plan Adaptor). Future work suggested in CBR for planning includes knowledge engineering for better case usage and maintenance, user interaction to modify steps, and practical integration into industry applications.