Configuration Workspaces of Series-Parallel Mechanisms

The workspace of a mechanism is the set of positions and orientations that is reachable by its end effector. Workspaces have numerous applications, including motion planning, mechanism design, and manufacturing process planning, but their representation and computation is challenging due to high dimensionality and geometric/topological complexity. We propose a new formulation of the workspace computation problem for a large class of mechanisms represented by series-parallel constraint graphs. A wide variety of allowable constraints include all lower pair, some higher pair, and non-collision constraints. We show that the workspace of such mechanisms may be computed by a constraint propagation algorithm. After the space of all rigid body motions is discretized, these operations can be efficiently implemented using the Fast Fourier Transform and a depth first search. In contrast to algebraic formulations, the proposed method assures that all configurations in the computed workspace not only satisfy pairwise constraints but can be reached without breaking and reassembling the mechanism.