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.