Avneesh Sud
ABSTRACT
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.
- F. Aurenhammer. Voronoi diagrams: A survey of a fundamental geometric data structure. ACM Comput. Surv., 23(3):345--405, Sept. 1991. Google Scholar
Digital Library
- O. B. Bayazit, J.-M. Lien, and N. M. Amato. Better group behaviors in complex environments with global roadmaps. Int. Conf. on the Sim. and Syn. of Living Sys. (Alife), 2002. Google ScholarDigital Library
- M. Bennewitz and W. Burgard. Finding solvable priority schemes for decoupled path planning techniquesfor teams of mobile robots. Proceedings of the 9th Int. Symposium on Intelligent Robotic Systems (SIRS), 2001.Google Scholar
- J. Champagne and W. Tang. Real-time simulation of crowds using voronoi diagrams. EG UK Theory and Practice of Computer Graphics, 2005.Google Scholar
- H. Choset and J. Burdick. Sensor based motion planning: The hierarchical generalized Voronoi graph. In Algorithms for Robot Motion and Manipulation, pages 47--61. A K Peters, 1996.Google Scholar
- H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, 2005.Google Scholar
- O. C. Cordeiro, A. Braun, C. B. Silveria, S. R. Musse, and G. G. Cavalheiro. Concurrency on social forces simulation model. First International Workshop on Crowd Simulation, 2005.Google Scholar
- M. Denny. Solving geometric optimization problems using graphics hardware. In Proc. of Eurographics, 2003.Google ScholarCross Ref
- I. Fischer and C. Gotsman. Fast approximation of high order Voronoi diagrams and distance transforms on the GPU. Technical report CS TR-07-05, Harvard University, 2005.Google Scholar
- M. Foskey, M. Garber, M. Lin, and D. Manocha. A voronoi-based hybrid planner. Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2001.Google Scholar
- J. Funge, X. TU, and D. Terzopoulos. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. Proc. of ACM SIGGRAPH, 1999. Google ScholarDigital Library
- P. Glardon, R. Boulic, and D. Thalmann. Dynamic obstacle clearing for real-time character animation. Computer Graphics International, 2005. Google ScholarDigital Library
- L. Guibas, C. Holleman, and L. Kavraki. A probabilistic roadmap planner for flexible objects with a workspace medial-axis-based sampling approach. In Proc. of IROS, 1999.Google ScholarCross Ref
- D. Helbing, L. Buzna, and T. Werner. Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum 12, 2003.Google Scholar
- K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast computation of generalized voronoi diagrams using graphics hardware. Proceedings of ACM SIGGRAPH 1999, pages 277--286, 1999. Google ScholarDigital Library
- K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Interactive motion planning using hardware accelerated computation of generalized voronoi diagrams. IEEE Conference on Robotics and Automation, pages pp. 2931--2937, 2000.Google ScholarCross Ref
- K. Hoff, A. Zaferakis, M. Lin, and D. Manocha. Fast and simple 2d geometric proximity queries using graphics hardware. Proc. of ACM Symposium on Interactive 3D Graphics, pages 145--148, 2001. Google ScholarDigital Library
- A. Kamphuis and M. Overmars. Finding paths for coherent groups using clearance. Proc. of ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 2004. Google ScholarDigital Library
- F. Lamarche and S. Donikian. Crowd of virtual humans: a new approach for real-time navigation in complex and structured environments. Computer Graphics Forum, 23(3 (Sept)), 2004.Google Scholar
- J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991. Google ScholarDigital Library
- T.-T. Li and H.-C. Chou. Motion planning for a crowd of robots. Proc. of IEEE Int. Conf. on Robotics and Automation, 2003.Google Scholar
- C. Loscos, D. Marchal, and A. Meyer. Intuitive crowd behaviour in dense urban environments using local laws. Theory and Practice of Computer Graphics (TPCG'03), 2003. Google ScholarDigital Library
- S. R. MUSSE and D. Thalmann. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation, 1997.Google ScholarCross Ref
- A. Okabe, B. Boots, and K. Sugihara. Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley & Sons, 1992. ISBN 0 471 93430 5. Google ScholarDigital Library
- L. E. PARKER. Designing control laws for cooperative agent teams. Proc. of IEEE Int. Conf. on Robotics and Automation, 1993.Google Scholar
- N. Pelechano, K. O'Brien, B. Silverman, and N. Badler. Crowd simulation incorporating agent psychological models, roles and communication. First International Workshop on Crowd Simulation, 2005.Google ScholarCross Ref
- J. Pettre, J.-P. Laumond, and D. Thalmann. A navigation graph for real-time crowd animation on multilayered and uneven terrain. First International Workshop on Crowd Simulation, 2005.Google Scholar
- C. W. Reynolds. Flocks, herds, and schools: A distributed behavioral model. In M. C. Stone, editor, Computer Graphics (SIGGRAPH '87 Proceedings), volume 21, pages 25--34, July 1987. Google ScholarDigital Library
- M. SOFTWARE. http://www.massivesoftware.com, 2006.Google Scholar
- G. Still. Crowd Dynamics. PhD thesis, University of Warwik, UK, 2000. Ph.D. Thesis.Google Scholar
- A. Sud, N. Govindaraju, R. Gayle, I. Kabul, and D. Manocha. Fast proximity computation among deformable models using discrete voronoi diagrams. ACM Trans. Graph. (Proc ACM SIGGRAPH), 25(3):1144--1153, 2006. Google ScholarDigital Library
- A. Sud, N. Govindaraju, R. Gayle, and D. Manocha. Interactive 3d distance field computation using linear factorization. In Proc. ACM Symposium on Interactive 3D Graphics and Games, pages 117--124, 2006. Google ScholarDigital Library
- A. Sud, M. A. Otaduy, and D. Manocha. DiFi: Fast 3D distance field computation using graphics hardware. Computer Graphics Forum (Proc. Eurographics), 23(3):557--566, 2004.Google Scholar
- M. Sung, M. Gleicher, and S. Chenney. Scalable behaviors for crowd simulation. Computer Graphics Forum, 23(3 (Sept)), 2004.Google Scholar
- M. Sung, L. KOVAR, and M. Gleicher. Fast and accurate goal-directed motion synthesis for crowds. Proc. of SCA 2005, pages 291--300, 2005. Google ScholarDigital Library
- A. Treuille, S. Cooper, and Z. Popovic. Continuum crowds. Proc. of ACM SIGGRAPH, 2006. Google ScholarDigital Library
- X. Tu and D. Terzopoulos. Artificial fishes: Physics, locomotion, perception, behavior. In A. Glassner, editor, Proceedings of SIGGRAPH '94 (Orlando, Florida, July 24--29, 1994), Computer Graphics Proceedings, Annual Conference Series, pages 43--50. ACM SIGGRAPH, ACM Press, July 1994. ISBN 0-89791-667-0. Google ScholarDigital Library
- J. Vleugels and M. H. Overmars. Approximating Voronoi diagrams of convex sites in any dimension. International Journal of Computational Geometry and Applications, 8:201--222, 1998.Google ScholarCross Ref
- S. A. Wilmarth, N. M. Amato, and P. F. Stiller. Maprm: A probabilistic roadmap planner with sampling on the medial axis of the free space. IEEE Conference on Robotics and Automation, pages 1024--1031, 1999.Google ScholarCross Ref
Index Terms
- Real-time path planning for virtual agents in dynamic environments
Recommendations
Hierarchical path planning for situated agents in informed virtual geographic environments
SIMUTools '10: Proceedings of the 3rd International ICST Conference on Simulation Tools and TechniquesMulti-Agent Geo-Simulation (MAGS) is a modelling and simulation paradigm which involves a large number of autonomous situated agents of various extents evolving in, and interacting with, an explicit description of a geographic environment called a ...
Real-Time Path Planning in Dynamic Virtual Environments Using Multiagent Navigation Graphs
We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order ...
Continual planning and acting in dynamic multiagent environments
In order to behave intelligently, artificial agents must be able to deliberatively plan their future actions. Unfortunately, realistic agent environments are usually highly dynamic and only partially observable, which makes planning computationally ...
Comments