Simulation level of detail for multiagent control

ABSTRACT

Many classes of applications require multiagent navigation control algorithms to specify the movements and actions of heterogeneous groups containing thousands of characters. The scale and complexity of these interacting character groups require navigation control algorithms that are both generalizable and specifically tuned to particular character platforms. We propose a technique called simulation level of detail (LOD) that provides a simulation-based interface between navigation control algorithms and the specific mobile characters on which they operate. A simulation LOD efficiently models a character's ability to move given its dynamic state and provides this simplified version of the character to navigation controllers for use in run-time search algorithms that compute locomotion actions. We develop our simulation LOD algorithms on groups of physically simulated human and alien bicyclists and demonstrate reusable controllers that provide improvements in path following and herding tasks.

REFERENCES

• 1: Matthew Brand , Aaron Hertzmann, Style machines, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.183-192, July 2000 [doi>10.1145/344779.344865]
• 2: David C. Brogan , Jessica K. Hodgins, Group behaviors for systems with significant dynamics, Robot colonies, Kluwer Academic Publishers, Norwell, MA, 1997
• 3: David C. Brogan , Ronald A. Metoyer , Jessica K. Hodgins, Dynamically Simulated Characters in Virtual Environments, IEEE Computer Graphics and Applications, v.18 n.5, p.58-69, September 1998 [doi>10.1109/38.708561]
• 4: Deborah A. Carlson , Jessica K. Hodgins, Simulation levels of detail for real-time animation, Proceedings of the conference on Graphics interface '97, p.1-8, May 1997, Kelowna, British Columbia, Canada
• 5: Stephen Chenney , Jeffrey Ichnowski , David Forsyth, Dynamics Modeling and Culling, IEEE Computer Graphics and Applications, v.19 n.2, p.79-87, March 1999 [doi>10.1109/38.749126]
• 6: W. T. Dempster and G. R. L. Gaughran. Properties of body segments based on size and weight. American Journal of Anatomy, 120:33--54, 1965.
• 7: Petros Faloutsos , Michiel van de Panne , Demetri Terzopoulos, Composable controllers for physics-based character animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.251-260, August 2001 [doi>10.1145/383259.383287]
• 8: Michael Gleicher, Retargetting motion to new characters, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.33-42, July 1998 [doi>10.1145/280814.280820]
• 9: Radek Grzeszczuk , Demetri Terzopoulos , Geoffrey Hinton, NeuroAnimator: fast neural network emulation and control of physics-based models, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.9-20, July 1998 [doi>10.1145/280814.280816]
• 10: D. O'Brien, S. Fisher, and M. Lin. Automatic simplification of particle system dynamics. In Computer Animation, 2001.
• 11: Carol O'Sullivan , John Dingliana, Collisions and perception, ACM Transactions on Graphics (TOG), v.20 n.3, p.151-168, July 2001 [doi>10.1145/501786.501788]
• 12: P. Stone and M. Veloso. Team-partitioned, opaque-transition reinforcement learning. Technical report, Carnegie Mellon University, April 1998.
• 13: K. H. Tan and M. A. Lewis. Virtual structures for high-precision cooperative mobile robotic control. In IROS 1996, November 1996.
• 14: P. K. C. Wang. Navigation strategies for multiple autonomous robots moving in formation. In Journal of Robotic Systems, volume 8(2), pages 177--195, 1991.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

General Terms:
Algorithms

Keywords:
mobile agents, multiagent simulation, path planning