Chapter 12 Case study: Ant trails
Chloe Vilain and Andrew Pikler
In nature, ants scavenge for food as a swarm. They choose their paths from the nest based on pheromone density, favoring paths with higher concentrations of pheromone. Individuals lay pheromone trails upon finding food, allowing other members of their colony to passively follow them to the food source. Because paths leading to food have higher pheromone density, increasing numbers of ants choose these successful paths. As a result, ant trails transition over time from random paths to streamlined routes. This organization and appearance of patterns over time is an example of emergence, the process by which complex systems and patterns arise from a multiplicity of simple systems.
Ant feeding patterns lend themselves to simulation with agent-based models, which simulate the actions and interactions of autonomous agents to assess their effects on the system as a whole. When we model ant feeding patterns, each ant is an agent in the model, a self-governing individual that makes decisions based on its surroundings. When simulating large numbers of ants, behavior emerges that is reflective of ant behavior in the natural world. Beyond being intrinsically fascinating, such models have applications in the “real world” in areas ranging from city planning to film production.
12.2 Model Overview
We can see one example of an agent-based model in Deneuborg et al.’s 1989 paper The Blind Leading the Blind: Modeling Chemically Mediated Army Ant Raid Patterns, available from http://www.ulb.ac.be/sciences/use/publications/JLD/58.eps.
The premise of the model is that as ants move around they deposit a pheromone, which increases the likelihood that other ants will follow the same path. Ants that have found food lay more pheromone than ants that haven’t, making it likely that other ants will follow their paths to find more food.
The ants live in a two-dimensional world of discrete points arranged in a grid. At each step of the model, each ant has a certain probability of moving to one of two neighboring coordinates in the direction the ant is facing, away from the nest—forward left or forward right (see Figure 12.1). All ants start in a corner of the world, which we call the nest; at each time step of the simulation, we add more ants to the nest. This leads to a constant stream of outgoing ants.
Once an ant has found food, it turns back towards the nest. It obeys the same rules for motion—that is, in each time step, its choice to move either forward left or forward right is influenced by the amounts of pheromone it sees, except now, these choices take it back towards the nest. Also, after moving, the ant lays more pheromone than it did while foraging for food. This significantly increases the probability that other foraging ants will follow its path to find, potentially, more food.
In its starting configuration, each point in the world has a chance of containing food. Once this starting condition has been set, we let the simulation run for about 1000 time steps, and plot the result. You can see the plot of one such simulation in Figure 12.2, which is similar to the actual foraging patterns Deneuborg et al. present in their Figure 1.
Download the code for our simulation, from thinkcomplex.com/ants.py. Run it for 1000 time steps and see if your results look similar to Figure 12.2. The simulation can be computationally intensive; 1000 time steps took almost two minutes on our computer, so be patient!
12.3 API design
Challenges of writing a simulation such as this include designing classes that are easy for human readers of the code to understand, and implementing data structures that allow the code to execute efficiently.
One way to break up a model into classes is to list the main nouns you use when describing the model, and then represent the most prominent of those nouns as objects. In our model, the primary objects are the World, which contains Ants, and Locations that represent points in the grid.
The next step is to decide what information about the current state of the model an instance of each class is responsible for. In our case, the behavior of the World is defined by what Ants and Locations can do, so it makes sense to design our classes bottom-up and consider the World only once we have at least a tentative idea for the methods and attributes of Ants and Locations.
For Ants, the most important information is where they are in the World, so each ant has the attributes x and y to store its coordinates. Also, each Ant keeps track of whether or not it is currently carrying food. Each Ant has only local information about the World; keeping track of all the Ants is the job of the World object itself.
Ants provide two methods the World uses to interact with them:
Locations know even less than Ants; each Location only keeps track of the food and pheromone it contains. Locations provide accessor methods that Ants and the World use to modify the Location’s food and pheromone amounts.
Locations do not keep track of their coordinates on the map, because they never change. Instead, this information is represented implicitly by a dictionary that maps from coordinates to Location objects.
There is only one World object; this instance keeps track of all existing Ants and Locations. The World provides methods for controlling the state of the simulation: move_ants advances the simulation by one time step by calling every existing Ant’s move method, and evaporating a proportion of pheromone from each Location. Other methods include add_ants, which adds a specified number of ants to the nest, place_food, which puts food at each Location with some probability, and get_location, which looks up the Location at given coordinates.
12.4 Sparse matrices
The group of Locations that make up our World is implemented as a sparse matrix. In this representation, Locations don’t exist until they are needed; World.get_location is responsible for fetching either the existing Location at the given coordinates, or creating a new Location if it doesn’t exist.
An alternate implementation would be a dense matrix, either a Python list of lists or a Numpy array. In our case, the sparse matrix has two advantages:
We use the wx Python package to plot a picture of the ants after the simulation finishes running.
We define a class called AntPlot which takes a World, creates a wx window, and plots the ants (see in Figure 12.2):
class AntPlot: def __init__(self, world): self.world = world self.app = wx.PySimpleApp() self.w = 500 self.h = 500 self.frame = wx.Frame(None, -1, 'Ant Plot', size=(self.w, self.h)) self.canvas = FloatCanvas(self.frame, -1) def draw(self): positions = self.world.get_ant_dict() for pos in positions: x, y = pos x -= self.w / 2 y -= self.h / 2 self.canvas.AddPoint((x, y)) self.frame.Show() self.app.MainLoop()
We use a wx FloatCanvas to plot the ants. Most canvases in GUI libraries define the point (0, 0) as the upper left corner of the canvas and have x increase to the left and y increase down, but the coordinates in the FloatCanvas work like in math—the origin is the middle, and the positive y direction is up. This allows us to write simpler code because we don’t have to transform our coordinates to the canvas’s system.
If you are interested in exploring wx further, AntPlot might be a good starting point.
To understand the behavior of the model better, make some changes and see what effect they have. For example, try altering the pheromone amounts in the model. What happens when Ants deposit significantly more or less pheromone? What happens when Ants only lay pheromone when leaving the nest? When returning?
The distribution of food affects the structure of the trails. In ant.py, each Location has a 50% probability of containing one particle of food. What happens when each Location has a 1% probability of containing 50 pieces of food?
So far, we have modeled one nest of ants. What happens with multiple nests? Pick a value d and modify the code such that Ants spawn at (0, d) and (d, 0) in addition to (0,0). Do the trails of ants converge, or do they all remain distinct?
Keep track of the amount of food collected in each nest. Does one of the nests do better than the others?
What happens when ants from one nest lay slightly higher amounts of pheromone than those from the other nests?
Agent-based models have numerous applications, from modeling traffic patterns to creating realistic battle simulations. The entertainment industry uses agent-based models to simulate crowds in films, games, and advertisements.
This kind of modeling is more scalable than filming; it is easier to simulate a large crowd than to recruit a thousands of extras. Agent-based models make it feasible to create large-scale, visually stunning sequences.
The Lord of the Rings trilogy is a salient example. Visual effects developers were tasked with creating battles with hundreds of thousands of soldiers from a variety of races with different fighting techniques. They implemented an agent-based model where each agent had about 200 possible motions (animated using motion capture). Agents followed simple rules to chose possible responses based on logic and probabilities. Different races—elves, orcs and men—were based on the same “master agent” but had different weapons, abilities and programmed attack responses.
Simulating thousands of agents in tandem allowed for exceptionally complex battle sequences. The results sometimes surprised even the programmers—in one simulation, a number of agents fled the battle. They were not programmed to flee; that is, fleeing was not explicitly an option. Rather, this behavior emerged from the interaction of agents following simple rules. This unexpected action, which would be realistic in an actual battle scenario, demonstrates the power of agent-based models.
The software developed for the trilogy, called Massive, has become the industry standard for simulating large-scale battle sequences. Massive has since been used for battle sequences in movies like Chronicles of Narnia and 300, and for more benign crowd simulations Happy Feet and Avatar.
The models used in these films are more complicated than our simulated ant trails, but they are examples of the same concept. Like the agents in Lord of the Rings, our ants follow simple rules, but their interactions yield realistic, complex, and sometimes unpredictable, behavior.
Like this book?
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.