Route Planning and Learning from Execution

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

There is a variety of applications that can benefit from the ability to
automatically find optimal or good routes from real maps. There have been
therefore several efforts to create and use real maps in computer
applications. However, for the purpose of route planning, maps cannot be seen
as static and complete, as there are dynamic factors and missing information
that affect the selection of good routes, such as time of the day, traffic,
construction, one versus multi-lane roads, residential areas, etc.  In this
paper, we describe our method for route planning and dynamic update of the
information available in a map. We show how we do route planning by reusing
past routing cases that collectively form a good basis for generating a new
routing plan.  We briefly present our similarity metric for retrieving a set
of similar routes.  The metric effectively takes into account the geometric
and continuous-valued characteristics of a city map. We then present how the
planner produces the route plan by analogy with the retrieved similar past
routes. Finally we show how a real traversal of the route is a learning
opportunity to refine the domain information and produce better routes. We
illustrate our algorithms on a detailed online map of the city of Pittsburgh
containing over 18,000 intersections and 25,000 street segments.


Working notes from the AAAI Fall Symposium "Planning and Learning: On to Real
Applications" (New Orleans, Louisiana), pages 58-64, AAAI Press, November 1994.
PostScript (163k, 7 pages).


BibTeX entry:

@inproceedings{haigh94b,
author = {Karen Zita Haigh and Jonathan Richard Shewchuk and
  Manuela M. Veloso},
title = {Route {P}lanning and {L}earning from {E}xecution},
booktitle = {Working Notes from the AAAI Fall Symposium ``Planning and
  Learning:  On to Real Applications''},
publisher = {AAAI Press},
address = {New Orleans, Louisiana},
pages = {58--64},
month = nov,
year = 1994
}