The Ants of Geometry
About 15 years ago, I was a young graduate student. I had decided to pursue mathematics after reading James Gleick’s book Chaos about the…
About 15 years ago, I was a young graduate student. I had decided to pursue mathematics after reading James Gleick’s book Chaos about the development of Chaos Theory. I would later learn that mathematically chaos theory was a niche and pretty dead area of dynamical systems research. At that time, however, complexity theory was all the rage. From the Santa Fe Institute to the New England Complex Systems Institute, whole research centers were being dedicated to the study of complex systems. What had started out with games like Conway’s Game of Life, had emerged as its own field with the unique mission statement to study systems, not as they had been traditionally investigated by reduction to constituent parts, but by relating similar emergent behavior across disparate systems. An example is the power law which appears in areas as different as finance and forest fires: e.g., billionaires and major conflagrations are both rare according to their magnitude.
I started out grad school as a recipient of a moderately prestigious VIGRE fellowship which gave me leverage to study whatever I wanted under a, at the time, generous stipend and tuition waiver. In the midst of graduate level courses in real and functional analysis, partial differential equations, dynamical systems, and the like, I was expected to begin some sort of research project ASAP to lead into my eventual Ph.D. thesis.
I took up with a kindly professor who I thought was elderly at the time, but at my present age would probably consider to be late middle age (how our ideas about age change as we get older!) His background was in differential geometry but he had abandoned the field in order to study complexity theory. In a twist, however, his idea of complexity theory research was to study how complexity could give rise to geometry.
Thus, the ants of geometry was born out of a merger between ant algorithms from complexity theory and the geometric structures that appear in nature.
Ant algorithms go back at least 30 years and are a subset of cellular automata. Cellular automata are those two dimensional blocklike structures that appear in Conway’s Game of Life and, based on simple rules, can create some amazingly complex structures.
Langton’s ant is an example of such an algorithm:
With the following two simple rules, this algorithm can generate incredibly complex structures.
At a white square, turn 90° clockwise, flip the color of the square, move forward one unit
At a black square, turn 90° counter-clockwise, flip the color of the square, move forward one unit
While pixel-based line drawing algorithms, such as Bresenham’s, have been around for a long time, they tend to be based on a pre-existing Euclidean line model. Thus, Euclidean geometry can easily give rise to pixelated geometry.
What is more interesting is when one is interested in the opposite: how does a cellular automata or ant algorithm give rise to Euclidean or other geometry when it has no notion of such geometries to begin with?
It turns out that it is fairly easy to develop an algorithm to generate a straight line or segment from simple rules. A cellular line between a point A and a point B in two dimensions can simply be thought of as a partition of the integer representing the y axis or height of the line. Thus, if you start at point (0,0) and which to end up at point (6,10) you just need some even partitioning of the number 10 into 6 integers.
The key to developing an ant algorithm, however, is that the ant must find the terminal cell (where you want the line to end) by making moves that are (a) not dependent on any notion of Euclidean geometry and (b) making only north and north eastward moves (assuming that they keep to the first quadrant of the numbers and start at the origin of the graph).
Why north and northeast? Well in partition theory this refers to either adding one to the current integer or starting a new integer in the partition with one.
The algorithm is simple: each ant, starting at (0,0) will move either north or diagonally north east based on a probability that is proportional to how far north or east it must move. So to reach (6,10) it must move north east about 60% of the time and north only about 40% of the time.
The algorithm requires several ants to work because not every ant will reach the terminal cell. Some will miss it, but some will hit it and those are likely to have created a straight line there but perhaps crooked.
One more thing is required. The ants will leave pheromones behind on the cells to show the other ants how to get there. Those that reach the terminal cell get their pheromones enhanced so that more ants will follow. (This is like the successful ant following its own path back.)
You can see that, after a while, those ants that reach the terminal cell by the straightest route will have the most pheromones and the line will only become straighter with time. Real ants do something similar.
Can we create other Euclidean objects this way? Perhaps a circle?
While a line is based on the idea of direction, a circle is based on the idea of distance. If we do not assume any definition of distance, but simply define a set of rules for our ants to follow, will the idea of distance arise?
Likely yes, in this case, the phenomenon has been observed in nature and is called an ant mill:
In this situation, ants simply follow one another endlessly.
In this case, you simply need a group of ants following a straight line and have some in the vanguard turn and start following the tail of the group. Eventually, this will make a nice circular motion as the attempt to correct themselves. Computers can simulate this phenomenon quite easily.
If you have lines and circles, you can also define other Euclidean ideas such as angles and parallel lines as well as Euclidean operations that require a compass. All with just ants and pheromones on a grid!
Dorigo, Marco, Gianni Di Caro, and Luca M. Gambardella. “Ant algorithms for discrete optimization.” Artificial life 5.2 (1999): 137–172.
Geer, Panama, Harry W. McLaughlin, and Keith Unsworth. “Discrete lines and ant algorithms.” (2001).