Global robot path planning using exact variational methods

Abstract

A two-dimensional robot path planning algorithm with some simplifying constraints on the robot dynamics and obstacle shapes is presented. The global path planning problem is formulated as a variational optimization problem. Normally such a formulation is intractable, since an obstacle-cluttered environment will present multiple trajectories that are locally optimal solutions. To remove the intractability and derive an algorithm that produces a unique global solution, an embedding method is used. A fictitious third dimension is added to the two-dimensional formulation; local (but nonglobal solutions) in the original problem become saddle-point trajectories in the embedded formulation, allowing for convergence of a numerical algorithm to continue along a descent path. The computational algorithm becomes globally convergent: i.e. convergence to the global solution is achieved regardless of the initial choice of a nominal solution needed to start the numerical algorithm.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>