Geometric Similarity Metrics for Case-Based Reasoning

               Karen Zita Haigh and Jonathan Richard Shewchuk
                         School of Computer Science
                         Carnegie Mellon University
                       Pittsburgh, Pennsylvania 15213

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.


Case-Based Reasoning:  Working Notes from the AAAI-94 Workshop (Seattle,
Washington), pages 182-187, AAAI Press, August 1994.  PostScript (156k,
6 pages).


BibTeX entry:

@inproceedings{haigh94a,
author = {Karen Zita Haigh and Jonathan Richard Shewchuk},
title = {Geometric {S}imilarity {M}etrics for {C}ase-{B}ased {R}easoning},
booktitle = {Case-Based Reasoning:  Working Notes from the AAAI-94 Workshop},
publisher = {AAAI Press},
address = {Seattle, Washington},
pages = {182--187},
month = aug,
year = 1994
}