Numerical computation of optimal navigation functions on a simplicial complex

Abstract

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