TABLE OF CONTENTS Steven M. LaValle, Iowa State University, Ames, IA, USA
This paper presents a general approach to computing optimal feedback motion strategies for a holonomic or nonholonomic robot in a static workspace. The proposed algorithm synthesizes a numerical navigation function defined by interpolation in a simplicial complex. The computation progresses much in the same way as Dijkstra's algorithm for graphs; however, the proposed approach applies to continuous spaces with geometric and nonholonomic constraints. By choosing a simplicial complex representation instead of a straightforward grid, the number of interpolation operations (which are required for continuous-state, numerical dynamic programming) is reduced from 2 n to n + 1, in which n is the dimension of the configuration space. Some preliminary findings are discussed for an implementation of the algorithm for the case of a two-dimensional configuration space.
Many applications in robotics require automatically computing a motion strategy that brings a complex geometric body from an initial configuration to a goal configuration while satisfying geometric constraints. Basic motion planning (or path planning) approaches typically do not apply in cases that are further complicated by imprecise localization and nonholonomic constraints. For example, in mobile robot or vehicle navigation, both the current and future configurations can only be estimated during execution using sensing and predictive models. A pre-planned path might have to be repeatedly adjusted due to such uncertainties; however, a preferable alternative would be to immediately know the optimal motion command given the current configuration (assuming the geometry and goal configuration...
