Path Planning for Ellipsoidal Robots and General Obstacles via Closed-Form Characterization of Minkowski Operations

Path planning has long been one of the major research areas in robotics, with PRM and RRT being two of the most effective path planners. Though they are generally very efficient, these two sample-based planners can become computationally expensive in the important special case of narrow passage problems. This paper develops a path planning paradigm which uses ellipsoids and superquadrics to respectively encapsulate the rigid parts of the robot and obstacles. The main benefit in doing this is that configuration-space obstacles can be parameterized in closed form, thereby allowing prior knowledge to be used to avoid sampling infeasible configurations, in order to solve the narrow passage problem efficiently. Benchmark results for single-body robots show that, remarkably, the proposed method outperforms the sample-based planners in terms of the computational time in searching for a path through narrow corridors. Feasible extensions that integrate with sample-based planners to further solve the high dimensional multi-body problems are discussed, which will require substantial additional theoretical development in the future.