This paper presents a general approach to computing optimal feedback motion strategies for a holonomic or nonholonomic robot in a static workspeace. 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; hwever, the proposed approach applies to continuous spaces with geometric and nonholonomic constraints. By choosing a simplicial ocmplex 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.
展开▼
