Complete path planning for planar closed chains among point obstacles

Abstract — A method to compute an exact cell decomposi-tion and corresponding connectivity graph of the configura-tion space (C-space) of a planar closed chain manipulator moving among point obstacles is developed. By studying the global properties of the loop closure and collision con-straint set, a cylindrical decomposition of the collision-free portion of C-space (C-free) is obtained without translating the constraints into polynomials as required by Collins’ method [1]. Once the graph is constructed, motion planning proceeds in the usual way; graph search followed by path construction. Experimental results demonstrate the effectiveness of the algorithm. I