Carnegie Mellon University
Route Planning by Analogy

Karen Zita Haigh and Manuela Veloso
Case-Based Reasoning Research and Development, Proceedings of ICCBR-95, October, 1995, pp. 169 - 180.

  • Adobe portable document format (pdf) (320KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

There have been several efforts to create and use real maps in computer applications that automatically find good map routes. In general, online map representations do not include information that may be relevant for the purpose of generating good realistic routes, including for example traffic patterns, construction, or number of lanes. Furthermore, the notion of a good route is dependent on a variety of factors, such as the time of the day, and may also be user dependent. This motivation leads to our work on the accumulation and reuse of previously traversed routes as cases.

In this paper, we demonstrate our route planning method which retrieves and reuses multiple 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 the replay mechanism and how the planner produces the route plan by analogizing from the retrieved similar past routes. We discuss in particular the strategy used to merge a set of cases and generate the new route. We use illustrative examples and show some empirical results from a detailed online map of the city of Pittsburgh containing over 18,000 intersections and 25,000 street segments.


Text Reference
Karen Zita Haigh and Manuela Veloso, "Route Planning by Analogy," Case-Based Reasoning Research and Development, Proceedings of ICCBR-95, October, 1995, pp. 169 - 180.

BibTeX Reference
   author = "Karen Zita Haigh and Manuela Veloso",
   title = "Route Planning by Analogy",
   booktitle = "Case-Based Reasoning Research and Development, Proceedings of ICCBR-95",
   pages = "169 - 180",
   publisher = "Springer-Verlag",
   month = "October",
   year = "1995",