Exploiting Domain Geometry in Analogical Route Planning

Karen Zita Haigh, Jonathan Richard Shewchuk, and Manuela Veloso
Journal of Experimental and Theoretical Artificial Intelligence, No. 9, October, 1997, pp. 509 - 541.


Download
  • Adobe portable document format (pdf) (614KB)
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
Automated route planning consists of using real maps to automatically find good map routes. Two shortcomings to standard methods are (i) that domain information may be lacking, and (ii) that a ``good'' route can be hard to define. Most on-line map representations do not include information that may be relevant for the purpose of generating good realistic routes, such as traffic patterns, construction, and one-way streets. The notion of a good route is dependent not only on geometry (shortest path), but also on a variety of other factors, such as the day and time, weather conditions, and perhaps most importantly, user-dependent preferences. These features can be learned by evaluating real-world execution experience.

These difficulties motivate our work on applying analogical reasoning to route planning. Analogical reasoning is a method of using past experience to improve problem solving performance in similar new situations. Our approach consists of the accumulation and reuse of previously traversed routes. We exploit the geometric characteristics of the map domain in the storage, retrieval, and reuse phases of the analogical reasoning process. Our route planning method retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan. To find a good set of past routes, we have designed a similarity metric that takes into account the geometric and continuous-valued characteristics of a city map. The metric evaluates its own performance and uses execution experience to improve its prediction of case similarity, adaptability and executability. We present the replay mechanism that the planner uses to produce a route plan based on analogy with past routes retrieved by the similarity metric. We use illustrative examples and show some empirical results from a detailed on-line 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, "Exploiting Domain Geometry in Analogical Route Planning," Journal of Experimental and Theoretical Artificial Intelligence, No. 9, October, 1997, pp. 509 - 541.

BibTeX Reference
@article{Veloso_1997_2913,
   author = "Karen Zita Haigh and Jonathan Richard Shewchuk and Manuela Veloso",
   title = "Exploiting Domain Geometry in Analogical Route Planning",
   journal = "Journal of Experimental and Theoretical Artificial Intelligence",
   pages = "509 - 541",
   month = "October",
   year = "1997",
   number = "9",
}