Constraint-Based Motion Planning of Deformable Robots

Russell GayleMing C. Lin, Dinesh Manocha

{rgayle,lin,dm}@cs.unc.edu


Deforming cylinder among serial walls

Various steps in a planned path. A deformable cylinder must navigate through holes in the walls in order to reach its destination. The robot's large diameter is too large for the robot to fit through the holes without deforming.



Abstract
We present a novel algorithm for motion planning of a deformable robot in a static environment. Given the initial and final configuration of the robot, our algorithm computes an approximate path using the probabilistic roadmap method. We use "constraint-based planning" to simulate robot deformation and make appropriate path adjustments and corrections to compute a collision-free path. Our algorithm takes into account geometric constraints like non-penetration and physical constraints like volume preservation. We highlight the performance of our planner on different scenarios of varying complexity.
Paper
Constrait-Based Motion Planning of Deformable Robots
Russell Gayle, Ming C. Lin, and Dinesh Manocha
Proceedings of International Conference of Robotics and Automation (ICRA), 2005
Paper: pdf (846KB)
Presentation Slides: ppt (available upon request)


Performance
This table describes the performance of our algorithm on various planning scenarios. Images of the scenarios and the various steps of the path planned for them can be found below. At the time, these values were comparable to planners for deformable robots with similar complexity.

Scenario
Obstacle
(tris)
Robot
(tris)
Path Est. Time
(sec)
Total Sim Time
(sec)
Avg Step Time
(sec)
Ball In Cup
500
320
1.0
41.5
0.015
Sphere World
3200
320
1.0
333.16
0.077
Holes In Walls
216
720
48
605.958
0.037
Tunnel
72
720
575
833.24
0.068
Additional Media
Ball in cup
Deformable ball in cup sequence

Sphere world
A deforming sphere (in wireframe) among several other spheres

Tunnel
Deforming cylinder in a tunnel scenario
Related Work
Acknowldgements
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.

DOE-HPCSF ARO NSF ONR DARPA
GAMMA
UNC-CS GAMMA Group
Department of Computer Science
Campus Box 3175
UNC-Chapel Hill
Chapel Hill, NC 27599-3175