Real-time navigation of independent agents using adaptive roadmaps

Avneesh Sud, Russell Gayle, Erik Andersen, Stephen Guy, Ming Lin, Dinesh Manocha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


We present a novel algorithm for navigating a large number of independent agents in complex and dynamic environments. We compute adaptive roadmaps to perform global path planning for each agent simultaneously. We take into account dynamic obstacles and inter-agents interaction forces to continuously update the roadmap by using a physically-based agent dynamics simulator. We also introduce the notion of 'link bands' for resolving collisions among multiple agents. We present efficient techniques to compute the guiding path forces and perform lazy updates to the roadmap. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.

Original languageEnglish (US)
Title of host publicationACM SIGGRAPH 2008 Classes
Number of pages1
StatePublished - Dec 1 2008
EventACM SIGGRAPH 2008 Classes - Los Angeles, CA, United States
Duration: Aug 11 2008Aug 15 2008


OtherACM SIGGRAPH 2008 Classes
Country/TerritoryUnited States
CityLos Angeles, CA


Dive into the research topics of 'Real-time navigation of independent agents using adaptive roadmaps'. Together they form a unique fingerprint.

Cite this