Efficient distance computation using best ellipsoid fit

Abstract

The effectiveness of the ellipsoid representation for geometrical reasoning is demonstrated in the context of robotics. Specifically, a robot collision-detection problem that consists of computing a quantity that reflects, as a function of the geometrical data, the amount of clearance between the robot and its environment is discussed. The method consists of two algorithms. The first computes the optimal ellipsoid surrounding a convex polyhedron. The second computes an analytic formula for the free margin about one ellipsoid with respect to another, as a standard eigenvalue problem. An efficient incremental version of the latter algorithm is proposed. This system has been implemented, and preliminary simulation results are provided.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>