Planning with reachable distances

Abstract: Motion planning for spatially constrained robots is difficult due to addi-tional constraints placed on the robot, such as closure constraints for closed chains or requirements on end effector placement for articulated linkages. It is usually computationally too expensive to apply sampling-based planners to these problems since it is difficult to generate valid configurations. We overcome this challenge by redefining the robot’s degrees of freedom and constraints into a new set of param-eters, called reachable distance space (RD-space), in which all configurations lie in the set of constraint-satisfying subspaces. This enables us to directly sample the constrained subspaces with complexity linear in the robot’s complexity. In addition to supporting efficient sampling of configurations, we show that the RD-space for-mulation naturally supports planning, and in particular, we design a local planner suitable for use by sampling-based planners. We demonstrate the effectiveness and efficiency of our approach for spatially constrained systems including closed chain planning with multiple loops, restricted end effector sampling, and on-line planning for drawing (or sculpting).