Roadmaps using gradient extremal paths

Abstract

This work proposes a motion planning method based on the construction of a roadmap connecting the critical points of a potential field or a distance function. It aims to overcome the limitation of potential field methods due to local minima caused by concave obstacles. The roadmap is incrementally constructed by a two-step procedure. Starting from a minimum, adjacent saddle-points are found using a local saddle-point search method. Then, the new saddle-points are connected to the minima by gradient descent. A numerical continuation algorithm from the computational chemistry literature is used to find saddle-points. It traces the valleys of the potential field, which are gradient extremal paths, defined as the points where the gradient is an eigenvector of the Hessian matrix. The definition of gradient bisectors is also discussed. The presentation conclude simulations in cluttered environments.

Additional details