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

91 Scopus citations

Abstract

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 publicationProceedings - VRST 2007, ACM Symposium on Virtual Reality Software and Technology
Pages99-107
Number of pages9
DOIs
StatePublished - Dec 1 2007
EventACM Symposium on Virtual Reality Software and Technology, VRST 2007 - Newport Beach, CA, United States
Duration: Nov 5 2007Nov 7 2007

Publication series

NameProceedings of the ACM Symposium on Virtual Reality Software and Technology, VRST

Other

OtherACM Symposium on Virtual Reality Software and Technology, VRST 2007
CountryUnited States
CityNewport Beach, CA
Period11/5/0711/7/07

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

  • Cite this

    Sud, A., Gayle, R., Andersen, E., Guy, S., Lin, M., & Manocha, D. (2007). Real-time navigation of independent agents using adaptive roadmaps. In Proceedings - VRST 2007, ACM Symposium on Virtual Reality Software and Technology (pp. 99-107). (Proceedings of the ACM Symposium on Virtual Reality Software and Technology, VRST). https://doi.org/10.1145/1315184.1315201