Combining Search and Analogical Reasoning in Path Planning from Road Maps
Karen Zita Haigh, Manuela Veloso · 1993
Path planning from road maps is a task that may involve multiple goal interactions and multiple ways of achieving a goal. This prob-lem is recognized as a difficult problem solv-ing task. In this domain it is particularly in-teresting 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 par-ticular novel angles: that of real execution in an autonomous vehicle (instead of simulated execution); and that of interspersing execu-tion and replanning as an additional learn-ing experience. This paper presents the ini-tial work towards this goal, namely the inte-gration 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 re-view 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.