Combining Search and Analogical Reasoning in Path Planning from Road Maps
Karen Haigh and Manuela Veloso,
School of Computer Science, Carnegie Mellon University
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.
Also See JETAI for the journal paper.