|
Large Scale Simulations Using Particle Physics Codes
We have simulated in lesser detail the control of larger numbers of vehicles (up to 1000 so far) trying to locate a number of targets in a large outdoor facility. These simulations use software initially developed to simulate molecular interactions in plasma physics and celestial body interactions in galactic physics. Grid-based techniques limit the range of interaction thus reducing the computational load on computing the interactive forces.
The physics-based modeling of swarms of autonomous robots utilizes the approaches of statistical mechanics, molecular dynamics, and plasma physics. The advantages of this approach include leveraging a large body of work on stability, fluctuation spectra, equilibrium, and efficient computation of the dynamics of potentially large ensembles of interacting objects.
Plasma simulation methods make possible the comparative theoretical study of cooperative behavior in certain limits. We have been investigating swarming and collaborative behavior from a statistical mechanics point of view where the motion or flight of vehicles is dictated by the physics of particles in potential fields. The motion is a combination of real potentials (gravity, drag, propulsion) and fictitious potentials (anti-collision and target seeking) generated by models and sensors. In the limit where the real and fictitious potentials are similar to physical, Coulomb, or EM electrodynamics, the mature sciences of plasma and statistical mechanics theory can be applied to the system to study stability, fluctuations, dissipation and entropy in provable limits.
As an example consider the images below, taken from a Particle-In-Cell (PIC) code simulation taken to the ballistic limit. This simulation models the injection and swarming behavior of 1000 autonomous agents deployed at two locations in a complex urban environment. In this simulation the autonomous vehicles are assumed to be man made, with the ability to communicate over a specified distance. After injection into urban environment all members of the swarm travel in a straight line at a constant velocity until they collide with an obstacle. Momentum is conserved during all collisions, whether with other members of the swarm or with walls within the simulated urban environment. As the simulation progresses members of the swarm fill the area, searching for two targets, shown in purple. Each member of the swarm acts with complete autonomy until it either finds one of the targets or comes into communications range of another member of the swarm that has. When a target is located, the robot in question stops and broadcasts a signal stating that a target has been found. Upon entering communications range other members of the swarm also stop moving and broadcast the same signal. Over time the swarm gradually ceases to move as more and more robots relay the message that a target has been located.
Figure 6: Ballistic simulation of a swarm in a complex urban environment
Modern plasma simulations accurately follow large numbers (~106) of charged particles interacting with each other self-consistently. The particles move according to the forces from both applied (external) fields as well as fields the particles generate themselves. Abstractly, this is mathematically equivalent to a swarm of communicating vehicles moving according to the forces applied to them, as shown below. In this example, as with the first, a PIC code was modified to simulate the collective behavior of a swarm of 103 robots injected into an complex urban environment. In this simulation friction, drag, inertia, and a pursuer's swarming and target seeking forces were added to the model. The effect of adding these forces is striking. When the simulation begins the swarm is divided into two tightly packed groups. Intermediate range swarming forces and target seeking forces pull the separate halves of the swarm towards each other and towards the two targets very quickly. As the simulation progresses, nearest-neighbor repulsive forces prevent the separate groups from re-forming a single, compact group. Eventually the forces begin to reach equilibrium, with groups of robots near each target, and a larger number distributed throughout the search area.
As the example below shows, plasma simulation codes can accurately compute complex trajectories and efficiently handle large numbers of particles and vehicles. Large populations are an issue because N interacting or communicating objects generally require N2 communication events, which is an unfavorable numerical scaling for a simulation that must be time stepped to resolve group dynamics. Plasma simulation codes efficiently handle this communication bottleneck by grouping near (strongly communicating) and far (weakly communicating) neighbors onto virtual meshes or into linked lists. The computational requirements of PIC codes scale as O (N), where N is the number of particles. Gridless particle simulation codes scale as O (N2), and grid-optional methods scale as O (N), O (N log (N)), or O (N2) depending on parameters set at run-time.
Figure 7: PIC simulation of a swarm in a complex urban environment |
