Overview

In this paper we consider the motion planning problem for closed chain systems. We propose an extension of the PRM methodology which uses the kinematics of the closed chain system to guide the generation and connection of closure configurations. In particular, we break the closed chains into a set of open subchains, apply standard PRM random sampling techniques and forward kinematics to one subset of the subchains, and then use inverse kinematics on the remaining subchains to enforce the closure constraints. This strategy preserves the PRM sampling philosophy, while addressing the fact that the probability that a random configuration will satisfy the closure constraints is zero, which has proven problematical in previous attempts to apply the PRM methodology to closed chain systems.

Another distinguishing feature of our approach is that we adopt a two-stage strategy, both of which employ the PRM framework. First, we disregard the environment, fix the position and orientation of one link (the "virtual" base) of the system, and construct a kinematic roadmap which contains different self-collision-free closure configurations. Next, we populate the environment with copies of the kinematic roadmap (nodes and edges), and then use rigid body planners to connect configurations of the same closure type. This two-stage approach enables us to amortize the cost of computing and connecting closure configurations.

Our results in 3-dimensional workspaces show that good roadmaps for closed chains with many links can be...