Reactive Deforming Roadmaps: Motion Planning of Multiple Robots in Dynamic Environments

Russell Gayle, Avneesh Sud, Ming C. Lin, Dinesh Manocha

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



Reactive Deforming Roadmaps applied to Crowd Simulation. (a) The green links defom as the light blue obstacles approach the link. (b) Links are removed (such as the one that was near the circled obstacle) based on proximity and amount of deformation. (c) Using RDR, we were able to plan the paths for many pedestrians in a city environment.



Abstract
We present a novel algorithm for motion planning of multiple robots amongst dynamic obstacles. Our approach is based on a new roadmap representation that uses deformable links and dynamically retracts to capture the connectivity of the free space. We use Newtonian Physics and Hooke's Law to update the position of the milestones and deform the links in response to the motion of other robots and the obstacles. Based on this roadmap representation, we describe our planning algorithms that can compute collision-free paths for tens of robots in dynamic environments.
Paper
Reactive Deforming Roadmaps: Motion Planning of Multiple Robots in Dynamic Environments
Russell Gayle, Avneesh Sud, Ming C. Lin, Dinesh Manocha
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2007

pdf (613K)


Additional Media


Small Movie (MPEG - 5MB)
Note: May not work with quicktime. Has been tested with VLC and Windows Media Player.
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