Complete real-time path planning during sensor-based discovery

Abstract

Sensor-based discovery path planning is problematic because the path needs to be continually recomputed as new information is discovered. A process-based client-server approach is presented that permits concurrent sensor-based map updates, robot localization corrections, as well as concurrent path computation and execution. A harmonic function is constantly recomputed using an iteration kernel on an occupancy-grid representation of what is known about the world at any current time. The path produced (i.e., by steepest gradient descent on the harmonic function) is optimal in the sense of minimizing the distance to the goal as well as minimizing the hitting probability. This helps alleviate the influence of uncertainty on path planning. In addition, the computation time for generating the path is insignificant provided that the harmonic function has converged. On a regular grid, the computation of the harmonic function is linear in the total number of grid elements. A quad-tree representation is proposed to help minimize the computation time by reducing the number of grid elements and minimally representing large spaces void of obstacles and goals. The computation time is found to be approximately reduced by a factor of n/sup 2/, where n is the ratio of grid elements in the regular grid divided by the number in the reduced quad representation.