We extend randomized path planning algorithms to the case of articulated robots that have closed kinematic chains. This is an important class of problems, which includes applications such as manipulation planning using multiple open-chain manipulators that cooperatively grasp an object and planning for reconfigurable robots in which links might be arranged in a loop to ease manipulation or locomotion. Applications also exist in areas beyond robotics, including computer graphics, computational chemistry, and virtual prototyping. Such applications typically involve high degrees of freedom and a parameterization of the configurations that satisfy closure constraints is usually not available. We show how to implement key primitive operations of randomized path planners for general closed kinematics chains. These primitives include the generation of random free configurations and the generation of local paths. To demonstrate the feasibility of our primitives for general chains, we show their application to recently developed randomized planners and present computed results for high-dimensional problems.

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.