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/sub /spl epsiv//*-DFS, combines features of the classical A* and DFS graph-search algorithms, and generates /spl epsiv/-optimal paths. Moreover, A/sub /spl epsiv//*-DFS is general and can be used by any online search strategy. The algorithm uses E as a parameter, where /spl epsiv/=0 corresponds to A* while /spl epsiv/=/spl infin/ corresponds to DFS. We study the performance of A/sub /spl epsiv//*-DFS for various values of /spl epsiv/ on simulated environments, and indicate how to best choose /spl epsiv/ for a given class of environments.