Maximum-Clearance Planar Motion Planning Based on Recent Developments in Computing Minkowski Sums and Voronoi Diagrams

Abstract

We present a maximum-clearance motion planning algorithm for planar geometric models with three degrees of freedom (translation and rotation). This work is based on recent developments in real-time algorithms for computing the Minkowski sums and Voronoi diagrams of planar geometric models bounded by G1-continuous sequences of circular arcs. Compared with their counterparts using polygons with no G1-continuity at vertices, the circle-based approach greatly simplifies the Voronoi structure of the collision-free space for the motion planning in a plane with three degrees of freedom. We demonstrate the effectiveness of the proposed approach by test sets of maximum-clearance motion planning through narrow passages in a plane.