Efficient Motion Planning of Highly Articulated Chains using Physics-based Sampling

Russell Gayle1, Stephane Redon2, Avneesh Sud1, Ming C. Lin1,
Dinesh Manocha1

1: {rgayle,sud,lin,dm}@cs.unc.edu      2: 

Articulated body planning

Planning benchmarks: (a) Serial Walls (300 DoF); (b) Tunnel (600 DoF); (c) Catheterization (2,500 DoF); (d) Pipes (2,000 DoF); (e) Debris (2,000 DoF). Each image shows the articulated chains in their final configurations.

We present a novel motion planning algorithm that efficiently generates physics-based samples in a kinematically and dynamically constrained space of a highly articulated chain. Similar to prior kinodynamic planning methods, the sampled nodes in our roadmaps are generated based on dynamic simulation.  Moreover, we bias these samples by using constraint forces designed to avoid collisions while moving toward the goal configuration. We adaptively reduce the complexity of the state space by determining a subset of joints that contribute most towards the motion and only simulate these joints. Based on these configurations, we compute a valid path that satisfies non-penetration, kinematic, and dynamics constraints. Our approach can be easily combined with a variety of motion planning algorithms including probabilistic roadmaps (PRMs) and rapidly-exploring random trees (RRTs) and applied to articulated robots with hundreds of joints.  We demonstrate the performance of our algorithm on several challenging benchmarks.
Efficient Motion Planning of Highly Articulated Chains using Physics-based Sampling
Russell Gayle, Stephane Redon, Avneesh Sud, Ming C. Lin, and Dinesh Manocha
UNC-CS Technical Report  TR06-014, 2006
Proceedings of the International Conference on Robotics and Automation (ICRA), 2007
pdf (518 KB)

Additional Media
Fully Articulated vs. Adaptive Dynamics
Large movie (140 MB)
Related Work
This work was supported in part by a Department of Energy High-Performance Computer Science Fellowship administered by the Krell Institute, ARO, NSF, AMSO, DARPA, ONR/VIRTE, and Intel Corporation.

Department of Computer Science
Campus Box 3175
UNC-Chapel Hill
Chapel Hill, NC 27599-3175