Home research People General Info Seminars Resources Intranet

Troy McMahon, Shawna L. Thomas, Nancy M. Amato, "Sampling Based Motion Planning with Reachable Volumes," Technical Report, TR14-003, Parasol Laboratory, Department of Computer Science, Texas A&M University, (replaces TR13-008), Feb 2014.
Technical Report(pdf, abstract)

We introduce a new concept, reachable volumes, which denotes the set of points that the end effector of a chain or linkage can reach.We show that the reachable volume of a chain is equivalent to the Minkowski sum of the reachable volumes of its links, which gives us an efficient method for computing reachable volumes. We present a method for generating configurations using reachable volumes which is applicable to various types of robots including chain robots (with and without closure constraints), tree-like robots, and complex robots including both loops and branches. We also describe how to apply constraints (both on end effectors and internal joints) using reachable volumes. Unlike previous methods, our method works for robots that include spherical and prismatic joints as well as planar joints. We present visualizations of reachable volumes for various example robots including closed chains and grasper robots as well as for examples with joint and end effector constraints. Such visualizations allow an operator to see what various portions of the robot can reach and guide robot design. We experimentally validate reachable volume sampling, both with and without constraints on end effectors and/or internal joints. We show that reachable volume samples are less likely to be invalid due to self collisions, making reachable volume sampling significantly more efficient for higher dimensional problems. We also show that these samples are easier to connect than others, resulting in better connected roadmaps. We demonstrate that our method can be applied to 262-dof, multiloop, and tree-like linkages including combinations of planar, prismatic and spherical joints. In contrast, existing methods either cannot be used for these problems or do not produce good quality solutions.