Computing Large Convex Regions of Obstacle Free Space Through Semidefinite Programming
This paper presents iris (Iterative Regional Inflation by Semidefinite programming) a new method for quickly computing large polytopic and ellipsoidal regions of obstacle free space through a series of convex optimizations These regions can be used, for example, to efficiently optimize an objective over collision free positions in space for a robot manipulator. The algorithm alternates between two convex optimizations: (1) a quadratic program that generates a set of hyperplanes to separate a convex region of space from the set of obstacles and (2) a semidefinite program that finds a maximum volume ellipsoid inside the polytope intersection of the obstacle free half spaces defined by those hyperplanes. Both the hyperplanes and the ellipsoid are refined over several iterations to monotonically increase the volume of the inscribed ellipsoid, resulting in a large polytope and ellipsoid of obstacle free space. Practical applications of the algorithm are presented in 2D and 3D, and extensions to (N\ dimensional configuration spaces are discussed. Experiments demonstrate that the algorithm has a computation time which is linear in the number of obstacles, and our matlab [18] implementation converges in seconds for environments with millions of obstacles.
WAFR