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

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.