Combining Search and Analogical Reasoning in Path Planning from Road Maps

Karen Haigh and Manuela Veloso
Case-Based Reasoning: Papers from the 1993 Workshop, July, 1993, pp. 79 - 85.


Download
  • Adobe portable document format (pdf) (139KB)
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
Path planning from road maps is a task that may involve multiple goal interactions and multiple ways of achieving a goal. This problem is recognized as a difficult problem solving task. In this domain it is particularly interesting to explore learning techniques that can improve the problem solver's efficiency both at plan generation and plan execution. We want to study the problem from two particular novel angles: that of real execution in an autonomous vehicle (instead of simulated execution); and that of interspersing execution and replanning as an additional learning experience.

This paper presents the initial work towards this goal, namely the integration of analogical reasoning with problem solving when applied to the domain of path planning from large real maps. We show how the complexity of path planning is related to multiple ways of achieving the goals. We review the case representation and describe how these cases are reused in path planning where we interleave a breadth-first problem solving search technique with analogical case replay. Finally, we show empirical results using a real road map.


Notes

Text Reference
Karen Haigh and Manuela Veloso, "Combining Search and Analogical Reasoning in Path Planning from Road Maps," Case-Based Reasoning: Papers from the 1993 Workshop, July, 1993, pp. 79 - 85.

BibTeX Reference
@inproceedings{Veloso_1993_2923,
   author = "Karen Haigh and Manuela Veloso",
   title = "Combining Search and Analogical Reasoning in Path Planning from Road Maps",
   booktitle = "Case-Based Reasoning: Papers from the 1993 Workshop",
   pages = "79 - 85",
   publisher = "AAAi Press",
   month = "July",
   year = "1993",
}