Navigating virtual agents in online virtual worlds

ABSTRACT

We present an approach for navigating autonomous virtual agents in online virtual worlds that are based on a centralized server network topology. Each agent's motion is controlled through local and global navigation. Our local navigation model is based on artificial social forces that has been extended to account for inaccurate sensing from network latency. Global navigation for each virtual agent is based on cell decomposition and computes high level paths. The overall computation is balanced by performing local navigation on client machines and global navigation on the server. We have implemented our navigation algorithm into the Second Life virtual world and highlight our results by simulating up to 18 virtual agents over multiple different client computers.

REFERENCES

• 1: Ashida, K., Lee, S. J., Allbeck, J., Sun, H., Badler, N., and Metaxas, D. 2001. Pedestrians: Creating agent behaviors through statistical analysis of observation data. Proc. Computer Animation.
• 2: Bainbridge, W. S. 2007. The scientific research potential of virtual worlds. Science.
• 3: Helbing, D., Buzna, L., and Werner, T. 2003. Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum 12.
• 4: Hoogendoorn, S. P., Luding, S., Bovy, P., Schreckenberg, M., and Wolf, D. 2000. Traffic and Granular Flow. Springer.
• 5: Steven M. LaValle, Planning Algorithms, Cambridge University Press, New York, NY, 2006
• 6: Taras I. Lakoba , D. J. Kaup , Neal M. Finkelstein, Modifications of the Helbing-Molnár-Farkas-Vicsek Social Force Model for Pedestrian Evolution, Simulation, v.81 n.5, p.339-352, May 2005 [doi>10.1177/0037549705052772]
• 7: Musse, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation, 39--51.
• 8: Pelechano, N., O'Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. First International Workshop on Crowd Simulation.
• 9: Pettre, J., Grillon, H., and Thalmann, D. 2007. Crowds of moving objects: Navigation planning and simulation. In ICRA, 3062--3067.
• 10: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.25-34, July 1987
• 11: Wei Shao , Demetri Terzopoulos, Autonomous pedestrians, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073371]
• 12: Sandeep Singhal , Michael Zyda, Networked virtual environments: design and implementation, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1999
• 13: Sud, A., Andersen, E., Curtis, S., Lin, M., and Manocha, D. 2007. Real-time path planning for virtual agents in dynamic environments. Proc. of IEEE VR, 91--98.
• 14: Avneesh Sud , Russell Gayle , Erik Andersen , Stephen Guy , Ming Lin , Dinesh Manocha, Real-time navigation of independent agents using adaptive roadmaps, Proceedings of the 2007 ACM symposium on Virtual reality software and technology, November 05-07, 2007, Newport Beach, California [doi>10.1145/1315184.1315201]
• 15: Thalmann, D., O'Sullivan, C., Ciechomski, P., and Dobbyn, S. 2006. Populating Virtual Environments with Crowds. Eurographics 2006 Tutorial Notes.
• 16: Adrien Treuille , Seth Cooper , Zoran Popović, Continuum crowds, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 17: Xiaoyuan Tu , Demetri Terzopoulos, Artificial fishes: physics, locomotion, perception, behavior, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.43-50, July 1994 [doi>10.1145/192161.192170]
• 18: Jur van den Berg , Sachin Patil , Jason Sewall , Dinesh Manocha , Ming Lin, Interactive navigation of multiple agents in crowded environments, Proceedings of the 2008 symposium on Interactive 3D graphics and games, February 15-17, 2008, Redwood City, California [doi>10.1145/1342250.1342272]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Artificial, augmented, and virtual realities

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: World Wide Web (WWW)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
avatar behaviors, crowd simulation, virtual worlds