Geometric Similarity Metrics for Case-Based Reasoning
Karen Zita Haigh and Jonathan Richard Shewchuck,
School of Computer Science, Carnegie Mellon University
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.
Also See JETAI for the journal paper.