Coordinated motion planning of planar linkages
John F. Kutcher · 1992
Coordinating the motion of several robot linkages is of theoretical and practical interest. Obstacles in the allowable region preclude certain motions, making the problem of coordination difficult. We develop a formal model for expressing linkage motion planning problems and give a general algorithm for computing the traceable partition of an arbitrary acyclic planar linkage. This partition allows us to characterize and plan all possible motions of the linkage and test the accessibility of two given configurations. Often, an analysis of this partition yields an efficient polynomial algorithm for planning the coordinated motion of multi-link robot arms. We establish that our algorithm's running time is polynomial in the size of the traceable partition it computes. To analyze this size for a given problem instance, we develop an extensive theory to assist in identifying redundant regions in these spaces. By removing these regions at intermediate phases of the computation, our general algorithm gives an effective solution to a large class of motion planning problems; and in particular, to problems that involve the coordinated motion planning of multi-link robot arms in half-plane. We investigate these problems in great detail, with powerful techniques that can be generalized to a wide class of linkage systems. For the two-shoulder problem (i.e., coordinating the motion of two multi-link robot arms constrained to a half-plane), we show that the traceable partition computed by our algorithm can be defined by $O(n\sp2)$ arcs and $O(n\sp2)$ 'states', when the arms' shoulders lie on the barrier; and by $O(n\sp3)$ arcs and $O(n\sp4)$ 'states', when they do not. After this initial pre-processing phase, our data structure can then be used to compute efficiently a variety of motion planning queries, such as determining the reachability of a given initial configuration. The true contribution of this thesis, however, lies not in the forementioned bounds, but in the generality of the techniques used to achieve them. In fact, the specific structure of the two-shoulder problem is not used until the final stages of the analysis; giving credibility to our belief that this thesis lays an innovative framework for developing very efficient algorithms for a large class of related problems.