HCSM: a framework for behavior and scenario control in virtual environments

ABSTRACT

This paper presents HCSM, a framework for behavior and scenario control based on communicating hierarchical, concurrent state machines. We specify the structure and an operational execution model of HCSM's state machines. Without providing formal semantics, we provide enough detail to implement the state machines and an execution engine to run them. HCSM explicitly marries the reactive (or logical) portion of system behavior with the control activities that produce the behavior. HCSM state machines contain activity functions that produce outputs each time a machine is executed. An activity function's output value is computed as a function of accessible external data and the outputs of lower-level state machines. We show how this enables HCSM to model behaviors that involve attending to multiple concurrent concerns and arbitrating between conflicting demands for limited resources. The execution algorithm is free of order dependencies that cause robustness and stability problems in behavior modeling. In addition, we examine the problems of populating virtual environments with autonomous agents exhibiting interesting behavior and of authoring scenarios involving such agents. We argue that HCSM is well suited for modeling the reactive behavior of autonomous agents and for directing such agents to produce desired situations. We demonstrate use of HCSM for modeling vehicle behavior and orchestrating scenarios in the Iowa Driving Simulator, an immersive real-time virtual driving environment.

REFERENCES

• 1: AIqONSON, J. 1994. The SIMCORE tactics representation and specification language. In Proceedings of the Fourth Computer Generated Forces and Behavwral Representation Conference (Orlando, FL, May)
• 2: BADLER, N., BECKET, W., AND GRANIERI, J. 1995 Towards real-time simulated human agents In Proceedings of the First Workshop on Simulation and lnteractwn tn Vtrtual Envzronments (Umvermty of Iowa, July), 126-129
• 3: Norman I. Badler , Bonnie L. Webber , Welton Becket , Matthew Stone , Christopher Geib , Michael Moore , Catherine Pelachaud , Barry D. Reich, Planning for animation, Interactive computer animation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 4: Joseph Bates, Virtual reality, art, and entertainment, Presence: Teleoperators and Virtual Environments, v.1 n.1, p.133-138, Winter 1992
• 5: BECKE'?, W. 1994. The jack Lisp API. Version 1.1. Tech Rep. MS-CIS~94-01 (or Human Modehng and Simulation Lab 59), Computer and Infbrmation Smence Dept., Umversity of Pennsylvania, Feb.
• 6: Bruce M. Blumberg , Tinsley A. Galyean, Multi-level direction of autonomous creatures for real-time virtual environments, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.47-54, September 1995 [doi>10.1145/218380.218405]
• 7: BRAVE, Y. AND HEYMANN, M. 1993. Control of discrete event systems modeled as hmrarchmal state machines. IEEE Trans. Autom Control 38, 12 (Dec.), 1803 1819.
• 8: BROO~S, R A. 1989. A robot that walks: Emergent behaviors from a carefully evolved network. In Proceedings of the 2989 IEEE Internatmnal Conference on Robotics and Automatmn (Scottsdale, AZ, May), 692-696
• 9: BROOKS, R. A, 1986. A robust layered control system for a mobile robot. IEEE Robotics Autom. RA-2, i (March}, 14 23.
• 10: CREMER, J. F. AND KEARNEY, J. K. 1994. Scenario authoring for virtual environments. In Procee&ngs of the IMAGE VII Conference }Tucson, AZ, June), 141 149
• 11: CRE~iER, J. F. AND STEWART, A. J. 1989. The architecture of Newton, a general-purpose dynamics mmulator. {n Proceedings of the 1989 IEEE Internatwna{ Conference on Robotzcs and Automatmn (May), 1806-1811.
• 12: DONIK~AN, S. AND ARNALDI, B. 1994. Complexity and concurrency for behavioral animation and simulation. In Proceedings of the Ftfth Eurog'raphws Workshop on Anirnatzon and S~mulatlon (Oslo, Sept }, 101 113.
• 13: Marc D. Donner, Real-time control of walking, Birkhauser Boston Inc., Cambridge, MA, 1987
• 14: Paul A. Fishwick, Simulation Model Design and Execution: Building Digital Worlds, Prentice Hall PTR, Upper Saddle River, NJ, 1995
• 15: Stuart A. Hansen, Conceptual control programming for physical system simulation, University of Iowa, Iowa City, IA, 1993
• 16: HANSEN, S. A., KEARNEY, J., AND CREMER, J. 1994. Morton control through communicating, hierarchical state machines. In Procecding~ oft,he F~/~h Eurographlcs Workshop on An~matlon and Smzulatton (Oslo, Sept.), 115-129.
• 17: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 18: David Harel , Amir Pnueli , Hagi Lachover , Amnon Naamad , Michal Politi , Rivi Sherman , Aharon Shtull-Trauring , Mark Trakhtenbrot, STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, v.16 n.4, p.403-414, April 1990 [doi>10.1109/32.54292]
• 19: HEYMANN, M. 1992. Concurrency and discrete event control. In Dzscrete Event Dynamic Systems: AT~alyzing Complexity and Performance in the Modern World, Y.-C. Ho, Ed., IEEE, New York, 65-75.
• 20: KELSO, M., WEYHRAUCH, P, AND BATES, J. 1993. Dramatic presence. PRESENCE: Teleoperators Virtual Environ. 2, 1, 1-15.
• 21: Ko, H. AND CREMER, J. 1995. Real-time human locomotion from simple positional streams. Presence: Teleoperators Virtual Environ. (submitted).
• 22: Jon Kuhl , Douglas Evans , Yiannis Papelis , Richard Romano , Ginger Watson, The Iowa Driving Simulator: An Immersive Research Environment, Computer, v.28 n.7, p.35-41, July 1995 [doi>10.1109/2.391039]
• 23: Brenda Laurel, Computers as theatre, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 24: LOYALL, A. B. AND BATES, J. 1993. Real-time control of animated broad agents. In Proceedings of the Fifteenth Annual Conference of the Congitive Science Society (Boulder, CO, June).
• 25: MAES, P. 1990. Designing Autonomous Agents. Cambridge, MA, MIT Press.
• 26: MCGEHEE, D., DINGUS, T., PAPELIS, Y., AND BARTELME, M. 1995. The use of specialized scenes and scenarios on the Iowa Driving Simulator for the evaluation of rear-end crash avoidance performance. Transportation Research Board meeting, Washington, DC.
• 27: PRAEHOFER, H. 1991. Systems theoretic formalisms for combined discrete-continuous system simulation. Int. J. Gen. Syst. 19, 3, 219 240.
• 28: RAMADGE, r. AND WONHAM, W. 1992. The control of discrete event systems. In Discrete Event Dynamic Systems: Analyzing Complexity and Performance in the Modern World, Y.-C. Ho, Ed. IEEE, New York, 48-64.
• 29: P. J. Ramadge , W. M. Wonham, Supervisory control of a class of discrete event processes, SIAM Journal on Control and Optimization, v.25 n.1, p.206-230, Jan. 1987 [doi>10.1137/0325013]
• 30: Douglas A. Reece, Selective perception for robot driving, Carnegie Mellon University, Pittsburgh, PA, 1992
• 31: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 32: SHAWVER, D. AND STANSFIELD, S. 1995. VR/IS Lab Virtual Actor Research Overview. In Proceedings of the First Workshop on Simulatzon and Interaction in V~rtual Environments (The University of Iowa, July), 120-125.
• 33: TAMBE, M., JOHNSON, W. L., JONES, R., KOSS, F., LAIRD, J., ROSENBLOOM, P., AND SCHWAMB, K. 1995. Intelligent agents for interactive simulation environments. A/Magazine 16, 1, 15 39.
• 34: Bernard P. Zeigler, Object-oriented simulation with hierarchical, modular models: intelligent agents and endomorphic systems, Academic Press Professional, Inc., San Diego, CA, 1990
• 35: ZEIGLER, B. 1989. DEVS representation of dynamical systems: Event-based intelligent control. Proc. IEEE 77, i (Jan.), 72-80.
• 36: ZEIGLER, B. AND KIM, J. Extending the DEVS-Scheme knowledge-based simulation environment for real-time event-based control. IEEE Trans. Robotics Aurora. 9~ 3, 351-356.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Interactive environments

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems
          Subjects: Environments

General Terms:
Algorithms, Theory

Keywords:
autonomous agents, behavior modeling, interactive simulation, reactive systems, real-time simulation, scenario control, state machines, virtual environments