by Avneesh Sud, Erik Andersen, Sean Curtis, Ming Lin, and Dinesh Manocha.

Paper
Video 1 Video 2

Fruit stealing simulation: A simulation of 96 fruit pickers (yellow dots) in an orchard with 64K fruit (dark blue and purple) on 64 trees (brown trunks) and 4 farmers (white shirts). Each agent maintains an independent goal. Left: Initial top view of the orchard Middle: Top view in the middle of simulation with many fruit collected Right: Perspective view of same time step. Our multi-agent navigation graph based algorithm can perform path planning at 8 fps on a high-end PC.

We present a novel approach for real-time path planning of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed from the first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues for accurate computation. Our algorithm is used for real-time multi-agent planning in pursuit-evasion and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.

Publication