|Navigation within an indoor environment: An exhibit hall of a trade show that consists of 511 booths and 1,000 human agents. Each agent has a distinct goal (i.e. visiting one of the booths) and behavior characteristic. Our navigation algorithm based on AERO can compute collision-free paths simultaneously for all 1,000 agents at 22 fps on a PC with 3Ghz Pentium D CPU.|
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.
Avneesh Sud, Russell Gayle, Stephen Guy,
Erik Andersen, Ming Lin, and Dinesh Manocha Real-time Simulation of Heterogenous Crowds, UNC Technical Report 2007.
Reactive Deforming Roadmaps: Motion Planning of Multiple Robots in Dynamic Environments
Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware
Proximity Query and Collision
Detection Research at the UNC Computer Science GAMMA Group.
Army Research Office
National Science Foundation