Route Planning and Learning from Execution
Karen Zita Haigh, Jonathan Richard Shewchuck and Manuela Veloso,
School of Computer Science, Carnegie Mellon University
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.