COLLISION-FREE PATH PLANNING OF ARTICULATED MANIPULATORS

A method is presented to efficiently compute a collision free path for manipulators with polyhedral links moving among polyhedral obstacles. The method is based on an analytical representation of the boundaries of configuration space obstacles (CSOB), obtained by modeling the con tacts between manipulator links and obstacle as higher kinematic pairs . The contact conditions and manipulator kinematics are expressed in t erms of homogeneous transformations, providing analytic relations betw een the joint angles and the contact variables. The set of joint angle s associated with permissible contact variables forms the boundary of the CSOB. Using these analytical relations, the free space is efficien tly divided into free-cells. Each contiguous set of free-cells is then represented by a connected graph that is of polynomial complexity in the number of geometric features of the obstacles and links. The short est collision-free path on the graph is found using a best-first searc h. Examples are presented which demonstrate the method for a two link planar manipulator.