A Newton Method for Faster Navigation in Cluttered Environments
Santiago Paternain, Aryan Mokhtari, Alejandro Ribeiro · 2018
Navigation functions are a common alternative to navigate cluttered environments. The main idea is to combine repulsive potentials from the obstacles and an attractive potential with minimum at the desired destination. By following the negative gradient of the navigation function convergence to the destination while avoiding the obstacles is guaranteed. Rimon-Koditschek artificial potentials are a particular class of potentials that can be tuned to be navigation functions in the case of focally admissible obstacles. While this provides a large class of problems in which they can be used, they suffer from the drawback that by design unstable manifolds of the saddle points have associated Hessian eigenvalues that are smaller than those associated to the stable manifold. This makes the escape from the saddle point to take a large time. To tackle this issue, we propose a second-order method that pre-multiplies the gradient by a modified Hessian to account for the curvature of the function. The method is shown to escape saddles exponentially with base 3/2 independently of the condition number of the Hessian.