Route Planning and Learning from Execution

Karen Zita Haigh, Jonathan Richard Shewchuk, and Manuela Veloso
Working notes from the AAAI Fall Symposium ``Planning and Learning: On to Real Applications'', November, 1994, pp. 58 - 64.


Download
  • Adobe portable document format (pdf) (102KB)
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.

Abstract
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.

Notes

Text Reference
Karen Zita Haigh, Jonathan Richard Shewchuk, and Manuela Veloso, "Route Planning and Learning from Execution," Working notes from the AAAI Fall Symposium ``Planning and Learning: On to Real Applications'', November, 1994, pp. 58 - 64.

BibTeX Reference
@inproceedings{Veloso_1994_2922,
   author = "Karen Zita Haigh and Jonathan Richard Shewchuk and Manuela Veloso",
   title = "Route Planning and Learning from Execution",
   booktitle = "Working notes from the AAAI Fall Symposium ``Planning and Learning: On to Real Applications''",
   pages = "58 - 64",
   publisher = "AAAI Press",
   month = "November",
   year = "1994",
}