A probabilistic roadmap approach for systems with closed kinematic chains

We present a randomized approach to path planning for articulated robots that have closed kinematic chains. The approach extends the probabilistic roadmap technique which has previously been applied to rigid and elastic objects, and articulated robots without closed chains. It provides a framework for path planning problems that must satisfy closure constraints in addition to standard collision constraints. This expands the power of the probabilistic roadmap technique to include a variety of problems such as manipulation planning using two open-chain manipulators that cooperatively grasp an object, forming a system with a closed chain, and planning for reconfigurable robots where the robot links may be rearranged in a loop to ease manipulation or locomotion. We generate the vertices and edges in our probabilistic roadmap. We focus on the problem of planning the motions for a collection of attached links in a 2D environment with obstacles. The approach has been implemented and successfully demonstrated on several examples.