A Closest Point Algorithm for Parametric Surfaces with Global Uniform Asymptotic Stability

Volkan Patoglu and R. Brent Gillespie

Submitted January 2005, IEEE Transactions on Robotics

We present an algorithm that determines the point on a convex parametric surface patch that lies closest to a given (possibly moving) point. Any initial point belonging to the surface patch converges to the closest point (which might itself be moving) without ever leaving the patch. The algorithm renders the patch invariant and is globally uniformly asymptotically stable. The algorithm is based on a control problem formulation and solution via a switching controller and common control Lyapunov function. Analytic limits of performance are available, delineating values for control gains needed to out-run motion (and shape) and preserve convergence under discretization. Together with a top-level switching algorithm based on Voronoi diagrams, the closest point algorithm treats parametric models formed by tiling together convex surface patches. Simulation results are used to demonstrate invariance of the surface patch, global convergence, limits of performance, relationships between low- evel and toplevel switching, and a comparison to competing Newton-iteration based methods.