title: Interactive navigation of heterogeneous agents using adaptive roadmaps.
abstract: 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.
authors.affiliation: Department of Computer Science, University of North Carolina, Chapel Hill, NC 27599-3175, USA. rgayle@cs.unc.edu
authors.forename: Russell
authors.initials: R
authors.lastname: Gayle
authors.forename: Avneesh
authors.initials: A
authors.lastname: Sud
authors.forename: Erik
authors.initials: E
authors.lastname: Andersen
authors.forename: Stephen J
authors.initials: SJ
authors.lastname: Guy
authors.forename: Ming C
authors.initials: MC
authors.lastname: Lin
authors.forename: Dinesh
authors.initials: D
authors.lastname: Manocha
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D008954:Models, Biological; D014584:User-Computer Interface