Two-Disk Motion Planning Strategy

Abstract

The problem of planning the motion of a polygonal object through a set of planar obstacles is addressed. A two-disk motion planning strategy is proposed to navigate the object within the free space between the obstacles from an initial location to a final location. This method makes use of the medial axis transform of the free space. Two minimal overlapping disks are determined that fully enclose the moving object, and then the centers of the two disks are constrained to move continuously along a path on the medial axis. Efforts are also directed to the problem of finding the two enclosing disks for a moving object which is considered as a polygon. The problem has been considered as being optimally cutting a polygon into two smaller polygons such that each of smaller polygons can be covered by a minimal disk. It is proved that if the cut is optimal, the resultant minimal disks for two smaller polygons have equal diameters.