Interactive navigation of heterogeneous agents using adaptive roadmaps

R. Gayle, A. Sud, E. Andersen, S. J. Guy, M. C. Lin, D. Manocha

Research output: Contribution to journalArticle

28 Scopus citations


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.

Original languageEnglish (US)
Article number4544511
Pages (from-to)34-48
Number of pages15
JournalIEEE Transactions on Visualization and Computer Graphics
Issue number1
StatePublished - Jan 1 2009


  • Crowd simulation
  • Multiagent path planning
  • Pedestrian dynamics

Fingerprint Dive into the research topics of 'Interactive navigation of heterogeneous agents using adaptive roadmaps'. Together they form a unique fingerprint.

  • Cite this