Motion planning using medial axis

Abstract

This paper addresses the problem of planning the motion of a polygonal object through a set of planar obstacles. We propose a two-disk motion planning strategy 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 (MAT) of the free space which can be generated efficiently using the method developed in [11]. We determine two minima] overlapping disks that fully enclose the moving object, and then constrain the centers of the two disks to move continuously aJong a path on the medial axis. In this paper we direct our efforts 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. We have proved that if the cut is optimal. the resultant minimal disks for two smaller polygons have equal diameters. Based on the geometry of a convex polygon, we formulated the problem as an optimization problem to determine a local optimum for a given edge pair. For a concave polygon, we propose a method to create a hypothetical convex polygon for approximating a given concave polygon, and then perform optimization using the method described above. We have proved that the maximal radii of the disks covering the hypothetical convex polygon generated from a concave polygon is 1.25 times of the radii of the disks that covers the original concave polygon. This shows that the approximation of a concave polygon using a minimal convex polygon does not yield too conservative solution. Simulations are presented for a variety of polygons. The method is being used for disassembly motion planning of a subassembly within its parent subassembly.