ABSTRACT
This paper presents a general approach to comput ing 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 com plex. 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 choos ing a simplicial complex representation instead of a straightforward grid, the number of interpolation op erations (which are required for continuous-state, nu merical 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 twodimensional configuration space.
