This HTML version of Think Complexity, 2nd Edition is provided for convenience, but it is not the best format of the book.
In particular, some of the symbols are not rendered correctly.
You might prefer to read the PDF version.
Chapter 10 Herds, Flocks, and Traffic Jams
NOTE: THIS CHAPTER IS NOT DONE!
The code for this chapter is in
chap10.ipynb, which is a
Jupyter notebook in the repository for this book. For more information
about working with this code, see Section ??.
10.1 Traffic jams
What causes traffic jams? In some cases there is an obvious cause,
like an accident, a speed trap, or something else that disturbs
the flow of traffic. But other times traffic jams appear for no
Agent-based models can help explain spontaneous traffic jams.
As an example, I implemented a simple highway simulation, based on
a model in Resnick, Turtles, Termites and Traffic Jams.
Here’s the class that represents the “highway”:
def __init__(self, n=10, length=1000, eps=0):
self.length = length
self.eps = eps
# create the drivers
locs = np.linspace(0, length, n, endpoint=False)
self.drivers = [Driver(loc) for loc in locs]
# and link them up
for i in range(n):
j = (i+1) % n
self.drivers[i].next = self.drivers[j]|
n is the number of cars.
length is the length of the
highway, which is 1000 by default (in arbitrary units).
eps is the amount of
random noise we’ll add to the system.
locs contains the locations of the drivers; initially
they are equally spaced along the highway.
Finally, we link the drivers so that each driver contains a reference
to the next driver in front. The highway is circular, so the
last driver contains a reference to the first.
step method is simple; it just moves each of the drivers:
| def step(self):
for driver in self.drivers:
And here’s the
| def move(self, driver):
d = self.distance(driver)
# let the driver choose acceleration
acc = driver.choose_acceleration(d)
acc = min(acc, self.max_acc)
acc = max(acc, self.min_acc)
speed = driver.speed + acc
# add random noise to speed
speed *= np.random.uniform(1-self.eps, 1+self.eps)
# keep it nonnegative and under the speed limit
speed = max(speed, 0)
speed = min(speed, self.speed_limit)
# if current speed would collide, stop
if speed > d:
speed = 0
# update speed and loc
driver.speed = speed
driver.loc += speed|
d is the distance between
driver and the next driver ahead.
This distance is passed to
specifies the behavior of the driver. This is the only decision the
driver gets to make; everything else is determined by the “physics”
of the simulation.
acc is acceleration, which limited by
max_acc. In my implementation, cars can accelerate with
max_acc=1 and brake with
speed is the old speed plus the requested acceleration, but
then we make some adjustments. First, we add random noise to
speed, because the world is not perfect.
eps determines the magnitude
of the noise, which is a percentage applied to
speed; for example, if
eps is 0.02,
speed is muliplied by a random number between 98%
- Then speed is bounded between 0 and
speed_limit, which is
40 in my implementation, so cars are not allowed to go backward or speed.
- If the requested speed would cause a collision with the next car,
speed is set to 0.
- Finally, we update the
Here’s the definition for the
def __init__(self, loc, speed=0):
self.loc = loc
self.speed = speed
def choose_acceleration(self, d):
speed are the location and speed of the
This implementation of
choose_acceleration is very simple:
it always accelerates at the maximum rate.
Since the cars start out equally spaced, we expect them all to
accelerate until they reach the speed limit, or until their speed
exceeds the space between them. At that point, at least one
“collision” will occur, causing some cars to stop.
Figure ?? shows a few steps in this process, starting with
30 cars and
eps=0.02. On the left is the configuration after
16 time steps, with the cars arranged in a circle.
Because of random noise, some cars are going faster
than others, and the spacing has become uneven.
During the next time step (center) two cars collide, indicated
During the next time step (right) two cars collide with the stopped
cars, and we can see the initial formation of a traffic jam. Once
a jam forms, it tends to persist, with additional cars approaching from
behind and colliding, and with the cars in the front accelerating
Under some conditions, the jam itself propagates backwards, as you
can see if you watch the animations in the notebook for this chapter.
10.2 Random Noise
As the number of cars increases, traffic jams become more severe.
Figure ?? shows the average speed cars are able to
achieve, as a function of the number of cars.
The top line shows results with
eps=0; that is, with no random
variation in speed. With 25 or fewer cars, the spacing between
cars is greater than 40, which allows cars to reach and maintain
the maximum speed, which is 40. With more than 25 cars, traffic
jams form and the average speed drops quickly.
This effect is a direct result of the physics of the simulation,
so it should not be surprising. If the length of the road is
1000, the spacing between
n cars is
1000/n. And since cars
can’t move faster than the space in front of them, the highest
average speed we expect is
1000/n or 40, whichever is less.
But that’s the best case scenario. With just a small amount of
randomness, things get much worse.
Figure ?? also shows results with
eps=0.01, which correspond to errors in speed of 0.1% and 1%.
With even a small amount of noise, the capacity of the highway
drops from 25 to 20 (by “capacity” I mean the maximum number
of cars that can reach and sustain the speed limit). And
with 1% errors, the capacity drops to 10. Ugh.
As one of the exercises at the end of this chapter, you’ll have a
chance to design a better driver; that is, you will experiment with
different strategies in
choose_acceleration and see if you can
find driver behaviors that improve average speed.
In 1987 Craig Reynolds published “Flocks, herds and
schools: A distributed behavioral model”, which describes an
agent-based model of herd behavior. You can download his
paper from http://www.red3d.com/cwr/papers/1987/boids.html.
Agents in this 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).
Each agent simulates three behaviors:
- Collision avoidance:
- Avoid obstacles, including other birds.
- Flock centering:
- Move toward the center of the flock.
- Velocity matching:
- Align velocity with neighboring birds.
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.
Visual package, 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
You can download my implementation from
thinkcomplex.com/Boids.py. It is based in part
on the description of boids in Flake, The Computational
Beauty of Nature.
The program defines two classes:
Boid, which implements the boid
World, which contains a list of Boids and a
“carrot” 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:
offset = other.pos - self.pos
# if not in range, skip it
if offset.mag > radius:
# if not within viewing angle, skip it
if self.vel.diff_angle(offset) > angle:
# otherwise add it to the list
get_neighbors uses vector subtraction to compute the
other. The magnitude of
this vector is the distance to the other boid.
computes the angle between the velocity of
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]
center = sum(t)/len(t)
toward = vector(center - self.pos)
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
computes the heading toward the carrot.
set_goal computes the weighed sum of these goals and
sets the overall goal:
| 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))|
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 speed and direction. The time step,
determines how far the boids move.
Many parameters influence flock behavior, including the range, angle
and weight for each behavior, and the maneuverability,
These parameters determine 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.
10.4 Free will
Many complex systems have properties, as a whole, that their
components do not:
- The Rule 30 cellular automaton is deterministic, and the rules
that govern its evolution are completely known. Nevertheless, it
generates a sequence that is statistically indistiguishable from
- The agents in Schelling’s model are not racist, but the outcome
of their interactions is as if they were.
- Agents in Sugarscape form waves that move diagonally even
though the agents cannot.
- Traffic jams move backward even though the cars in them are
- The behavior of flocks and herds emerges from local interactions
between their members.
These examples suggest an approach to several old and challenging
questions, including the problems of consciousness and free will.
Free will is the ability to make choices, but if our bodies and brains
are governed by deterministic physical laws, our choices would be
determined. Arguments about free will are innumerable; I will
only mention two:
- William James proposed a two-stage model in which
possible actions are generated by a random process and then selected
by a deterministic process. In that case our actions are
fundamentally unpredictable because the process that generates them
includes a random element.
- David Hume suggested that our perception of making choices
is an illusion; in that case, our actions are deterministic because
the system that produces them is deterministic.
These arguments reconcile the conflict in opposite ways, but they
agree that there is a conflict: the system cannot have free will if
the parts are deterministic.
The complex systems in this book suggest the alternative
that free will, at the level of options and decisions, is compatible
with determinism at the level of neurons (or some lower level). In
the same way that a traffic jam moves backward while the cars move
forward, a person can have free will even though neurons don’t.
In the traffic jam simulation, define a class,
that inherits from
Driver and overrides
See if you can define driving rules that do better than the basic
Driver. You might try to achieve higher
average speed, or a lower number of collisions.
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 directly ahead, the boid should move away
laterally. What effect do you expect this rule to have on the
behavior of the flock? Implement it and see.
Read more about free will at
http://en.wikipedia.org/wiki/Free_will. The view that free will
is compatible with determinism is called compatibilism. One of
the strongest challenges to compatibilism is the “consequence
argument”. What is the consequence argument? What response can you
give to the consequence argument based on what you have read in this