Solving the moving obstacle path planning problem using embedded variational methods

An analytically derived algorithm to solve a simple two-dimensional robot planning problem subject to moving obstacle constraints is presented. Normally a variational formulation is intractable since an obstacle-cluttered environment will present multiple trajectories that are locally optimal solutions. To derive an algorithm which produces a unique solution, an embedding method commonly found in homotopic methods 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 direction. The computational algorithm becomes globally convergent, i.e., convergence to the global solution is achieved regardless of the choice of initial trajectory used to start the algorithm. Simulation results demonstrate the effectiveness of the algorithm