Geometric Similarity Metrics for Case-Based Reasoning

Karen Zita Haigh and Jonathan Richard Shewchuk

Case-based reasoning is a problem solving method that uses stored solutions to problems to aid in solving similar new problems. One of the difficulties of case-based reasoning is identifying cases that are relevant to a problem. If the problem is defined on a geometric domain -- for instance, planning a route using a city map -- it becomes possible to take advantage of the geometry to simplify the task of finding appropriate cases. We propose a methodology for determining a set of cases which collectively forms a good basis for a new plan, and may include partial cases, unlike most existing similarity metrics. This methodology is applicable in continuous-valued domains, where one cannot rely on the traditional method of simple role-substitution and matching. The problem of identifying relevant cases is transformed into a geometric problem with an exact solution. We construct two similar algorithms for solving the geometric problem. The first algorithm returns a correct solution, but is prohibitively slow. The second algorithm, based on the use of a Delaunay triangulation as a heuristic to model the case library, is fast, and returns an approximate solution that is within a constant factor of optimum. Both algorithms return a good set of cases for geometric planning. We have implemented the second algorithm within a real-world robotics path planning domain.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.