The following disclaimer applies, and is copied into the start of each relevant page, in case they are taken out of context.
This is just a brief overview of some techniques presented in an entirely informal way, to give an appreciation of the basic principles by cutting away all the confusing details, and therefore is not to be taken as an exact comprehensive summary, but merely indicative of the underlying principles in the general case.
Cellular automata
...provide a simple way to simulated discrete or continuous systems through an aggregation of simple automata executing simple rule driven state transitions and find applications from basic computation through to simulation of social, traffic or computer networks, through to continuum dynamics applicable to fluid dynamics, including floods, fires, pollutant dispersal, avalanches and earthquakes. As automata, they can easily investigate the effect of partially distributed algorithms in control and other applications.CS & mathematicians think of them as a set of interacting automata, and easily see their computing power but are frequently not interested in their ensemble group behaviour or simulation applications.
Physicists tend to think of them as a set of particles interacting under some universal laws and easily see their group behaviour applications but are generally not interested in their computing power.
Examples
: boids flocking, game of life, predator-prey relationships, traffic simulations etc.To get a basic idea of the power and simplicity of rules applied, the 'world' is split up into discrete cells with update rules applied over the entire world at each discrete time step. Integer arithmetic leads to speed at expense of some accuracy, but catches the main trends.
Boids
: world is split up into cells which boids fly through (or alternatively cells can be boids which have state indicating their position)Update Rules: stay together but not too close; avoid obstacles; follow the average group motion;
Game of Life
: 'world' is cellular mesh with occupancy states updated on each generation- based on no. of neighbours : too few or many - die/retreat; just right : reproduce/expand.
Traffic simulation
- capable of accurate real-time simulation of autobahn system in mid-90s on a PC- world is roadway split up into cells (~ 5 metres long) which hold car + safety space;
- typical velocity ranges from 0 - (3) - 5 cells per second corresponding ~ from 0 - (50) - 90Km/h
(which is the optimal speed for maximum throughput - while throughput initially rises linearly with speed, higher speeds demand greater safety space (proportional to speed squared) so that overall road density, utilisation & throughput eventually decreases.)
Update rules...from the front...!
- if space available in front (no. of empty cells) < current speed limit,
then increment speed;
else move forward no. of cells available.
Tricks of the trade.
A little randomness in speed is introduced to model the several issues that introduce variations which arise in normal driving, and can accurately model variations in speed in normal highway driving. For city driving, either source destination information is required, or estimates of averaged probabilities for turns at various junctions are required.
As you can see, the rules are trivially simple, but yet can realistically model complex group behaviour.
Some ideas may come from 'brainstorming'
- either modelling the brain as interactions of neurons
- or modelling weather storms as examples of vortices.
Some extensions include adding intelligence or learning capabilities to the automata, in which case they can simulate intelligent agent behaviour.