In 1971 Thomas Schelling published “Dynamic Models of Segregation,” which proposes a simple model of racial segregation. The Schelling model is a grid; each cell in the grid represents a house. The houses are occupied by two kinds of “agents,” which I will label red and blue, in roughly equal numbers. About 10% of the houses are empty.
At any point in time, an agent might be happy or unhappy, depending on the other agents in the neighborhood. The neighborhood of each house is the set of eight adjacent cells. In one version of the model, agents are happy if they have at least two neighbors like themselves, and unhappy if they have one or zero.
The simulation proceeds by choosing an agent at random and checking to see whether it is happy. If so, then nothing happens; if not, the agent chooses one of the unoccupied cells at random and moves.
You might not be surprised to hear that this model leads to some segregation, but you might be surprised by the degree. Fairly quickly, clusters of similar agents start to appear. The clusters tend to grow and coalesce over time until there are a small number of large clusters and most agents live in homogeneous neighborhoods.
If you did not know the process and only saw the result, you might assume that the agents were virulent racists, but in fact all of them would be perfectly happy in a mixed neighborhood. Since they prefer not to be greatly outnumbered, they might be considered xenophobic at worst. Of course, these agents are a wild oversimplification of real people, so it may not be appropriate to apply these descriptions at all.
Racism is a complex human problem; it is hard to imagine that such a simple model could shed much light on it. And, in fact, Schelling’s model does not make an affirmative argument about what causes segregation in real cities. But it does provide a negative argument: if you observe segregation in a real city, you cannot conclude that the people in the city are racists. Schelling’s model is an existence proof that there is at least one alternative cause of segregation.
Agents that prefer mixed neighborhoods. Continuous space. Robustness as a property of holistic models.
In a recent book, The Big Sort, Bill Bishop argues that American society is increasingly segregated by political opinion, as people choose to live among like-minded neighbors.
The mechanism Bishop hypothesizes is not that people, like the agents in Schelling’s model, are more likely to move if they are isolated, but that when they move for any reason, they are likely to choose a neighborhood with people like themselves.
Modify your implementation of Schelling’s model to simulate this kind of behavior and see if it yields similar degrees of segregation.
Schelling’s model is one of the first, and one of the most famous, agent-based models. Since the 1970s, agent-based modeling has become an important tool in economics and other social sciences, and in some natural sciences.
The characteristics of agent-based models include:
Agent-based models are useful for modeling the dynamics of systems that are not in equilibrium (although they are also used to study equilibrium). And they are particularly useful for understanding relationships between individual decisions and system behavior.
For more about agent-based modeling, see wikipedia.org/wiki/Agent-based_model.
Agent-based models have been used to study the dynamics of highway traffic, especially the behavior of traffic jams. These models yield two non-obvious results:
As an example, I have implemented a simple highway simulation that you can download from greenteapress.com/compmod/Highway.py. This module uses TurtleWorld, which is part of Swampy. It defines two classes, Highway, which inherits from TurtleWorld, and Driver, which inherits from Turtle.
The Highway a one-lane road that forms a circle, but it is displayed as a series of rows that spiral down the canvas. Each Driver has a position, which is the distance it has travelled from the origin. The function Highway.project takes a Driver as a parameter and maps its position on the highway into a location on the canvas.
Each driver has a random color, and starts with a random speed and position. The initial speed is in the range from 4 to 8. Each Driver has an attribute, next, that refers to the Driver in front.
During each time step, each Driver chooses a new speed, based on the distance between it and the Driver in front. Here is the step function for Drivers.
def step(self):
# find the following distance
dist = self.next.position - self.position
if dist < 0:
dist += self.world.length()
# choose a speed and move (but don't overtake)
self.choose_speed(dist)
move = min(self.speed, dist)
self.position += move
# redraw
self.world.project(self)
self.redraw()
In Highway.py, the implementation of choose_speed
does nothing, so Drivers maintain constant speed. Because
they are not allowed to overtake, if a fast Driver catches up
with a slower Driver, it slows down and stays behind.
If you run this version of the program, you will see that fast Drivers quickly stack up behind slower Drivers and stay there. So this version of the model is not very interesting.
Real drivers tend to speed up when there is more space in front of them and slow down as they approach another car. It turns out that this behavior is sufficient to cause traffic jams.
This exercise asks you to implement a more detailed model of driver behavior and explore the conditions that cause traffic jams.
choose_speed
with a method that implements the following rules:The function make_highway takes an optional parameter, driver, which is the constructor it uses to create the Drivers. By
default, it uses Driver, but if you pass BadDriver as a
parameter, it will instantiate BadDrivers instead.
This way of organizing the program is a variation of the factory pattern, which you can read about at wikipedia.org/wiki/Factory_method_pattern.
In 1987 Craig Reynolds published an article, “Flocks, herds and schools: A distributed behavioral model,” that describes an agent-based model of herd behavior. Agents in these kinds of models are called “boids,” which is both a contraction of “bird-oid” and an accented pronunciation of “bird,” although boids are also used to model fish and herding land animals.
You can read an overview of the boid algorithm at red3d.com/cwr/boids/. Each agent simulates three behaviors:
Boids make decisions based on local information only; each boid only sees (or pays attention to) other boids in its field of vision and range.
The Visual module, also known as VPython, is well-suited for implementing boids. It provides simple 3-D graphics as well as vector objects and operations that are useful for the computations.
You can download my implementation from greenteapress.com/compmod/Boids.py. It is based in part on the description of boids in Flake, The Computational Beauty of Nature.
My program defines two classes: Boid, which inherits from a VPython cone, implements the boid algorithm; World contains a list of Boids and a “carrot,” which is a sphere the Boids are attracted to.
The boid algorithm uses get_neighbors to find other
boids in the field of view:
def get_neighbors(self, others, radius, angle):
boids = []
for other in others:
if other is self: continue
offset = other.pos - self.pos
# if not in range, skip it
if offset.mag > radius: continue
# if not within viewing angle, skip it
if self.vel.diff_angle(offset) > angle: continue
# otherwise add it to the list
boids.append(other)
return boids
get_neighbors uses vector subtraction to compute the
vector from self to other. The magnitude of
this vector is the distance to the other boid. diff_angle
computes the angle between the velocity of self, which
is also the line of sight, and the other boid.
center finds the center of mass of the boids in the field of view and returns a vector pointing toward it:
def center(self, others):
close = self.get_neighbors(others, r_center, a_center)
t = [other.pos for other in close]
if t:
center = sum(t)/len(t)
toward = vector(center - self.pos)
return limit_vector(toward)
else:
return null_vector
Similarly, avoid finds the center of mass of any obstacles in range and returns a vector pointing away from it, copy returns the difference between the current heading and the average heading of the neighbors, and love computes the heading toward the carrot.
set_goal computes the weighed sum of these goals and
sets the overall goal accordingly:
def set_goal(self, boids, carrot):
self.goal = (w_avoid * self.avoid(boids, carrot) +
w_center * self.center(boids) +
w_copy * self.copy(boids) +
w_love * self.love(carrot))
Finally, move updates the velocity, position and attitude of the boid:
def move(self, mu=0.1):
self.vel = (1-mu) * self.vel + mu * self.goal
self.vel.mag = 1
self.pos += dt * self.vel
self.axis = b_length * self.vel.norm()
The new velocity is the weighted sum of the old velocity and the goal. The parameter mu determines how quickly the birds can change direction. The time step, dt determines how far the boids move.
As you can see, there are many parameters that influence the behavior of the flock, including the range, angle and weight for each behavior, and the maneuverability, mu. These parameters influence the ability of the boids to form and maintain a flock and the patterns of motion and organization in the flock. For some settings, the boids resemble a flock of birds; other settings resemble a school of fish or a cloud flying insects.
Run my implementation of the boid algorithm and experiment with different parameters. What happens if you “turn off” one of the behaviors by setting the weight to 0?
To generate more bird-like behavior, Flake suggests adding a fourth behavior to maintain a clear line of sight; in other words, if there is another bird nearly directly ahead, the boid should move away laterally. What effect would you expect this rule to have on the behavior of the flock? Implement it and see.