Aϵ*-DFS: an algorithm for minimizing search effort in sensor based mobile robot navigation

Presents an algorithm for minimizing the search effort of a mobile robot navigating in an unknown environment. First we describe a strategy for navigating a cylinder-shaped mobile robot in an area with unknown obstacles using range data. The strategy searches a graph which is constructed incrementally during the navigation process. Then we present a new algorithm for searching the graph which attempts to minimize the search effort, measured by the length of the path traveled by the robot. The algorithm, called A_ε*-DFS, combines features of the classical A* and DFS graph-search algorithms, and generates ε-optimal paths. Moreover, A_ε*-DFS is general and can be used by any online search strategy. The algorithm uses E as a parameter, where ε=0 corresponds to A* while ε=∞ corresponds to DFS. We study the performance of A_ε*-DFS for various values of ε on simulated environments, and indicate how to best choose ε for a given class of environments