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 bast 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 formation 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 the 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 analogical planning by combining the benefits of several base cases when no single plan contributes enough information to the analogy. The effectiveness of this approach is demonstrated with examples from the domain of automatic programming.