An asynchronous integration and event detection algorithm for simulating multi-agent hybrid systems

ABSTRACT

A simulation algorithm is presented for multi-agent hybrid systems---systems consisting of many sets of nonsmooth differential equations---such as systems involving multiple rigid bodies, vehicles, or airplanes. The differential equations are partitioned into coupled subsystems, called "agents"; and the conditions which trigger the discontinuities in the derivatives, called "events", may depend on the global state vector. Such systems normally require significant computational resources to simulate because a global time step is used to ensure the discontinuity is properly handled. When the number of systems is large, forcing all system to be simulated at the same rate creates a computational bottleneck, dramatically decreasing efficiency. By using a control systems approach for selecting integration step sizes, we avoid using a global time step. Each subsystem can be simulated asynchronously when the state is away from the event. As the state approaches the event, the simulation is able to synchronize each of the local time clocks in such a way that the discontinuities are properly handled without the need for "roll back". The algorithm's operation and utility is demonstrated on an example problem inspired by autonomous highway vehicles. Using a combination of stochastic modelling and numerical experiments we show that the algorithm requires significantly less computation time when compared with traditional simulation techniques for such problems, and scales more favorably with problem size.

REFERENCES

• 1: Rajeev Alur , Calin Belta , Franjo Ivancic, Hybrid Modeling and Simulation of Biomolecular Networks, Proceedings of the 4th International Workshop on Hybrid Systems: Computation and Control, p.19-32, March 28-30, 2001
• 2: Rajeev Alur , Radu Grosu , Yerang Hur , Vijay Kumar , Insup Lee, Modular Specification of Hybrid Systems in CHARON, Proceedings of the Third International Workshop on Hybrid Systems: Computation and Control, p.6-19, March 23-25, 2000
• 3: Uri M. Ascher , Linda R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 4: Vishal Bahl , Andreas A. Linninger, Modeling of Continuous-Discrete Processes, Proceedings of the 4th International Workshop on Hybrid Systems: Computation and Control, p.387-402, March 28-30, 2001
• 5: Michael Stephen Branicky, Studies in hybrid systems: modeling, analysis, and control, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 6: Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999 [doi>10.1145/347823.347828]
• 7: Cellier, F. 1979. Combined discrete/ continuous system simulation by use of digital computers: techniques and tools. Ph.D. dissertation. ETH Zurich, Zurich, Switzerland.
• 8: Deshpande, A. G. and Semenzato, L. 1995. Shift programming language and runtime system for dynamic networks of hybrid automata. California PATH project technical report.
• 9: Ch. Engstler , Ch. Lubich, Multirate extrapolation methods for differential equations with different time scales, Computing, v.58 n.2, p.173-185, 1997 [doi>10.1007/BF02684438]
• 10: Esposito, J. and Kumar, V. 2001. Efficient dynamic simulation of robotic systems with hierarchy. In IEEE International Conference on Robotics and Automation (Seoul, Korea). IEEE Computer Society Press, Los Alamitos, Calif., 2818--2823.
• 11: Esposito, J., Pappas, G., and Kumar, V. 2001a. Multi-agent hybrid system simulation. In IEEE Conference on Decision and Control (Orlando, Fla), IEEE Computer Society Press, Los Alamitos, Calif.
• 12: Joel Matthew Esposito , Vijay Kumar, Simulation and control of hybrid systems with applications to mobile robotics, 2002
• 13: Joel M. Esposito , Vijay Kumar , George J. Pappas, Accurate Event Detection for Simulating Hybrid Systems, Proceedings of the 4th International Workshop on Hybrid Systems: Computation and Control, p.204-217, March 28-30, 2001
• 14: Fierro, R., Das, A., Spletzer, J., Esposito, J., Kumar, V., Ostrowski, J. P., Taylor, C. J., Hur, Y., Alur, R., Lee, I., Grudic, G., and Southold, B. 2002. A framework and architecture for multi-robot coordination. Inte. J. Robot. Automat. 21, 10-11 (Oct.--Nov.), 2407--2411.
• 15: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 16: C. W. Gear , O. Osterby, Solving Ordinary Differential Equations with Discontinuities, ACM Transactions on Mathematical Software (TOMS), v.10 n.1, p.23-44, March 1984 [doi>10.1145/356068.356071]
• 17: Gear, C. and Wells, D. 1984. Multirate linear multistep methods. BIT 24, 484--502.
• 18: Distributed Simulation of Multi-Agent Hybrid Systems, Proceedings of the Fifth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.356, April 29-May 01, 2002
• 19: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 20: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 21: Maler, O. and Pnueli, A., Eds. 2003. 6th International Workshop, Hybrid Systems: Computation and Control (Prague, Czech Republic). Lecture Notes in Computer Society, vol. 2623. Springer-Verlag, New York.
• 22: Brian Mirtich, Timewarp rigid body simulation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.193-200, July 2000 [doi>10.1145/344779.344866]
• 23: Pieter J. Mosterman, An Overview of Hybrid Simulation Phenomena and Their Support by Simulation Packages, Proceedings of the Second International Workshop on Hybrid Systems: Computation and Control, p.165-177, March 29-31, 1999
• 24: David M. Nicol , L. Felipe Perrone, Cost/benefit analysis of interval jumping in power-control simulation, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 25: Taeshin Park , Paul I. Barton, State event location in differential-algebraic models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.2, p.137-165, April 1996 [doi>10.1145/232807.232809]
• 26: L. F. Shampine , I. Gladwell , R. W. Brankin, Reliable solution of special event location problems for ODEs, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.11-25, March 1991 [doi>10.1145/103147.103149]
• 27: Steinman, J. 1992. SPEEDED: A unified framework to parallel simulation. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation. 75--83.
• 28: Tomlin, C., Pappas, G. J., and Sastry, S. 1998. Conflict resolution for air traffic management: A study in multi-agent hybrid systems. IEEE Trans. Automat. Cont. 43, 4.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation

General Terms:
Algorithms

Keywords:
Event detection, hybrid systems, multi-agent systems, numerical integration