Route Planning and Learning from Execution
Karen Zita Haigh, Jonathan Richard Shewchuk, Manuela Veloso · 1994
There is a variety ofapplications thatcan benefit from the ability oautomatically find optimal orgood routes from real maps. There have been therefore several efforts ocreate and use real maps in computer applications. However, for the purpose ofroute planning, maps cannot beseen as static and complete, as there are dynamic factors and missing informa-tion that affect the selection of good routes, such as time of the day, traffic, construction, one versus multi-lane roads, res-idential areas, etc. In this paper, we describe our method for route planning and dynamic update of the information avail-able in a map. We show how we do route planning by reusing past routing cases that collectively form a good basis for gen-erating a new routing plan. We briefly present our similarity metric for retrieving a set of similar routes. The metric effec-tively takes into account he 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 de-tailed online map of the city of Pittsburgh containing over 18,000 intersections and 25,000 street segments.