The Base Selection Task in Analogical Planning

Abstract

Analogical planning provides a means of solving problems where other machine learning methods fail, because it does not require numerous previous examples or a rich domain theory. Given a problem in an unfamiliar domain (the target case), an analogical planning system locates a successful plan in a similar domain (the base case), and uses the similarities to generate the target plan. Unfortunately, the analogical planning process is expensive and inflexible . Many of the limiting factors reside in the base selection step, which drives the analogy fo rmation process. This paper describes two ways of increasing the effectiveness and efficiency of analogical planning. First, a parallel graph-match base selection algorithm is presented. A parallel implementation on th e Connection Machine is described and shown to substantially decrease the complexity of base selection. Second, a base-case merge algorithm is shown to increase the flexibility of analogica l planning by comb inin g the benefits of severa l base cases when no single plan cont ribut es enough information to the ana logy. The e ffectiveness of this approach is demonstrated with examp les from the domain of automatic programmmg.