James Shannon
Exploring the real world applications of cellular automata and its application to the simulation of flocking behavior
What is a cellular automaton?
Shannon explains that a cellular automaton (CA) is an n-dimensional arrangement of cells. These cells can be of variable geometry and arranged in a discrete or infinite repetitive pattern. For example, the squares of a chess board could be seen as a two-dimensional automaton. These cells have a given number of states, usually 1 or 0, living or dead. They also have a specific number of neighboring cells, depending on the structure and dimensions of the board. In these simulations the states of the cells are all modified simultaneously, according to the state of the neighboring cells and the rules that determine the evolution of the individuals. To better grasp the idea, let us focus in a one-dimensional automaton, where each cell has a Boolean state, 0 or 1. A cell thus has two neighbors, one on the left and one on the right. We then have a neighborhood of 3 cells (counting the one whose state is updated). Therefore, this one-dimensional CA has 2^3 (8) possible configuration. In two dimensions with a neighborhood of 8 cells, there are 2^9 (512) configurations and thus as many rules to apply to the automaton. These rules are classified in four categories according to their effect on the evolution of the cells which Shannon details as:
Category 1: Nearly all layouts evolve quickly into stable and homogeneous structures. All the initial random elements of these layouts disappear.
Category 2: Almost all arrangements evolve into stable or oscillating structures. Some of the initial random arrangements may dissipate, but usually a small portion of them remain. Finally, local changes in the original structures do not spread to neighboring structures.
Category 3: Almost all models evolve in a pseudo-random or chaotic manner. All structures that appear in these models are susceptible to destruction by ambient noise. Any changes in the local models will generally spread throughout the simulation space indefinitely.
Category 4: Almost all models evolve into complex structures that behave in fascinating ways. Local structures tend to form and can survive for long periods of time.
Cellular automaton applications
Shannon is particularly interested in Category 4 rules, some of which are capable of transforming a cellular automaton into a universal computing system. This has been proven for Rule 110 and for Conway’s game of life. This implies that with enough resources and time a cellular automaton associated with the right rule can solve any computational problem based on an algorithmic procedure. One can also mention the category 3 rule 30 which induces a chaotic and aperiodic behavior of a cellular automaton. This rule is considered to be the key to understanding how simple rules can eventually exhibit emergent and chaotic behavior in nature:
Above is the appearance of Rule 30-like pattern on the shell of a conical snail species known as the textile Conus.
Conway's Game of life
Shannon familiarizes us with the concept of cellular automatons by introducing us to the game of life, designed by the British mathematician John Horton Conway in 1970. This game takes place on a two dimensional grid similar to a chess board, and progresses through generations. Indeed, at each iteration, a cell will count how many of its 8 neighboring cells are alive. And this information is then subjected to the rules that govern the game. We can already notice similarities with Reynolds’s Boids theory, indeed each element evolves in the world according to a limited "sphere of perception". And most importantly, the rules governing their movements are excessively simple.
1. A cell that is currently dead will be reborn in the next generation if exactly 3 of its neighbors are alive in the current generation.
2. A living cell will only stay alive in the next generation if 2 or 3 of its neighbors are alive, otherwise it dies.
Simulation's controls :
Press 'p' to start or stop the simulation
's' to play the simulation step by step
'e' to clear all cells
'r' to randomize the grid"
'+' and '-' to change the simulation's speed
You can also draw patterns using the left click of the mouse
The task requires to create a grid in the form of a "torus of revolution", i.e. each symmetrically opposite edge will be linked together. And that kind of grid is a feature that we will use in the incoming flocking simulation. In short, this means that when an object leaves the screen on one side it reappears on the other, essentially creating an infinite board.
Once the grid has been created, a reasonable proportion of "living" cells appear randomly. These cells will then count their living neighbors and follow the rules explained above.
As explained in the first chapter, the game of life is a category 4 cellular automaton, i.e. local structures can form and persist over time. Since the game of life is very famous, many structures have been discovered. For example, oscillating structures called spaceships, which move in the space of the game by copying themselves to an adjacent position after a number of iterations. There are also structures that, starting from a seed, bloom for a certain time to form explosions, flowers or complex patterns. We can also mention cannons, which are oscillating structures capable of creating vessels periodically. In short it is established that a cellular automaton is a system capable of producing a tangible simulation of a flock of birds.
Flocking simulation
Below is an animation of a cellular automata whose rules allow the appearance of a flocking behaviour
Simulation's controls :
Press 'p' to start or stop the simulation
's' to play the simulation step by step
'e' to clear all cells
'r' to randomize the grid"
'+' and '-' to change the simulation's speed
You can also draw patterns using the left click of the mouse
A few details on the simulation
Based on the work of Shannon, I tried to reproduce a flock of bird using the graphical programming tool p5.js and the JavaScript language. This object-oriented language allows us to create classes composed of parameters and methods. A common popularization is to compare a class to an everyday object, like a car. Thus the car class is a model for all the other cars that will be derived from it. These cars have wheels (parameters) and can be driven (method). In the case of our cellular automaton we will try to simplify as much as possible the parameters assigned to the cells, in this case, an alive or dead state and an account of living neighbors. The state of the cell is binary, 0 or 1, dead or alive. Our system is subjected to a variant of the "Collision Avoidance", "Velocity Matching" and "Flock Centering" rules detailed in the previous simulation of a flock according to Reynolds. Indeed the "Velocity matching" rule is not necessary since the moving cells travel only by one cell each turn, thus at the same speed.
Setting up a cell:
A cell symbolizes a member of the flock that will have to interact with its neighbors by respecting a small number of rules. This cell will be assigned a reduced area of perception in accordance with the fact that a bird cannot coordinate with all the members of a flock, but only with a few neighbors. In our cellular automaton, this area of perception, and thus the number of possible neighbors, depends on the geometry of the board. At each iteration, this neighborhood will be explored in search of living cells. Moreover, the neighborhood is composed of two layers (see figure below), the first one (in red) is used to detect neighbors too close to apply the collision avoidance rule, and the second one (in orange) is used to detect neighbors for the flock centering rule.
Setting up the board:
Shannon established in his research that a grid with hexagonal cells allows the agents to take less rigid trajectories than a grid with square cells. Moreover Processing allows us to easily draw polygons. Thus the grid will be composed of lines of hexagons nested in quincunxes rows, which will create an offset that will have to be taken into account in the design of the simulation’s algorithms.
Setting up the environment:
As we observed earlier with the simulation of a flock of Boids, the environment plays an important role in the simulation. Without external disturbances the swarm would find a resting position where the rules of separation and clustering are simultaneously respected. Thus it is necessary to establish a migration point that the cells will try to reach. In our simulation this point will be the mouse cursor. Below is a preview of the grid:
Basics of the algorithm:
The evolution of a cellular automaton is generational, i.e. all cells will update themselves simultaneously. We can therefore create an algorithm that will update the position of a cell according to its environment and the rules established by Shannon.
The choice of the best displacement is thus made in five steps (refer to the figure below):
First, the cell explores its neighborhood and counts the number of living cells in its first neighborhood layer (in blue) then in the second one (in purple). Here we have two neighbors.
If there are neighbors in the first layer, we record their positions, and then steer the cell away from them. (blue arrow)
If there are neighbors in the second layer, we record their positions, and then steer the cell closer from them. (purple arrow)
Finally a last steering suggestion is made to move the cell closer to the migration point. (red arrow)
The last step is to sum up these suggestions to achieve a displacement sensitive to the rules of collision avoidance, flock centering and environmental disturbance (here it is the need to migrate). The black cell will then be instructed to move to the grey cell.
