On the Complexity of Case-Based Planning

Case-based reasoning [23, 1, 32] is a problem solving methodology based on using a library of solutions for similar problems, i.e., a library of "cases" with their respective solutions. Roughly speaking, case-based planning consists into storing generated plans and using them for finding new plans [15, 8, 29]. In practice, what is stored is not only a specific problem with a specific solution, but also some additional information that is considered useful to the aim of solving new problems, e.g., information about how the plan has been derived [30], why it works [20, 16], when it would not work [17], etc. Different case-based planners differ on how they store cases, which cases they retrieve when the solution of a new problem is needed, how they adapt a solution to a new problem, whether they use one or more cases for building a