Exploiting Domain Geometry in Analogical Route Planning

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

Automated route planning consists of using real maps to automatically find
good map routes. Two shortcomings to standard methods are (i) that domain
information may be lacking, and (ii) that a ``good'' route can be hard to
define.  Most on-line map representations do not include information that may
be relevant for the purpose of generating good realistic routes, such as
traffic patterns, construction, and one-way streets.  The notion of a good
route is dependent not only on geometry (shortest path), but also on a variety
of other factors, such as the day and time, weather conditions, and perhaps
most importantly, user-dependent preferences.  These features can be learned
by evaluating real-world execution experience.

These difficulties motivate our work on applying analogical reasoning to route
planning.  Analogical reasoning is a method of using past experience to improve
problem solving performance in similar new situations.  Our approach consists
of the accumulation and reuse of previously traversed routes.  We exploit the
geometric characteristics of the map domain in the storage, retrieval, and
reuse phases of the analogical reasoning process.  Our route planning method
retrieves and reuses multiple past routing cases that collectively form a good
basis for generating a new routing plan.  To find a good set of past routes, we
have designed a similarity metric that takes into account the geometric and
continuous-valued characteristics of a city map.  The metric evaluates its own
performance and uses execution experience to improve its prediction of case
similarity, adaptability and executability.  We present the replay mechanism
that the planner uses to produce a route plan based on analogy with past routes
retrieved by the similarity metric.  We use illustrative examples and show some
empirical results from a detailed on-line map of the city of Pittsburgh,
containing over 18,000 intersections and 25,000 street segments.


Journal of Experimental and Theoretical Artificial Intelligence.
PostScript (1,419k, 30 pages).