Interactive navigation of heterogeneous agents using adaptive roadmaps.
We present a novel algorithm for collision-free navigation of a large number of independent agents in complex and dynamic environments. We introduce adaptive roadmaps to perform global path planning for each agent simultaneously. Our algorithm takes into account dynamic obstacles and interagents interaction forces to continuously update the roadmap based on a physically-based dynamics simulator. In order to efficiently update the links, we perform adaptive particle-based sampling along the links. We also introduce the notion of 'link bands' to resolve collisions among multiple agents. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.
Gayle
Russell
R
Department of Computer Science, University of North Carolina, Chapel Hill, NC 27599-3175, USA. rgayle@cs.unc.edu
Sud
Avneesh
A
Andersen
Erik
E
Guy
Stephen J
SJ
Lin
Ming C
MC
Manocha
Dinesh
D
D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D008954:Models, Biological; D014584:User-Computer Interface