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. Our work 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 in our probabilistic roadmap by sampling random configurations that ignore kinematic closure, and by performing randomized gradient descent to force satisfaction of the closure constraints. We generate edges in the roadmap by executing a randomized traversal of the constraint surface between two vertices. In this paper, we focus our presentation on the problem of planning the motions for a collection of attached links in a two-dimensional environment with obstacles. The approach has been implemented and successfully demonstrated on several examples.