Motion planning using medial axis

October 1992

Motion planning using medial axis

Authors:

Yangsheng Xu, Raju S. Mattikalli, and Pradeep Khosla

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.
@workshop{Xu-1992-15885,
author = {Yangsheng Xu And Raju S. Mattikalli And Pradeep Khosla},
title = {Motion planning using medial axis},
booktitle = {Proceedings of IFAC Workshop on Intelligent Manufacturing Systems (IMS '92)},
year = {1992},
month = {October},
volume = {25},
pages = {135 - 140},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.