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
}