Combining Search and Analogical Reasoning in Path Planning from Road Maps

Planning and Scheduling

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.