Previous Up Next

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 apparent reason.

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”:

class 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.

The step method is simple; it just moves each of the drivers:

def step(self): for driver in self.drivers: self.move(driver)

And here’s the move method:

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 choose_acceleration, which 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 min_acc and max_acc. In my implementation, cars can accelerate with max_acc=1 and brake with min_acc=-10.
  • 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% and 102%.
  • 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 speed and loc attributes of driver.

Here’s the definition for the Driver class:

class Driver: def __init__(self, loc, speed=0): self.loc = loc self.speed = speed def choose_acceleration(self, d): return 1

The attributes loc and speed are the location and speed of the driver.

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 10.1:

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 by the x marks.

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 away.

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


Figure 10.2:

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.001 and 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.

10.3  Boids

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.

The 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 computations.

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 algorithm, and 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: 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:

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 speed and direction. The time step, dt, determines how far the boids move.

Many parameters influence flock behavior, including the range, angle and weight for each behavior, and the maneuverability, mu.

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 random.
  • 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 moving forward.
  • 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.

10.5  Exercises

Exercise 1  

In the traffic jam simulation, define a class, BetterDriver, that inherits from Driver and overrides choose_acceleration. See if you can define driving rules that do better than the basic implementation in Driver. You might try to achieve higher average speed, or a lower number of collisions.

Exercise 2  

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.

Exercise 3  

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 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.


Think DSP

Think Java

Think Bayes

Think Python 2e

Think Stats 2e

Think Complexity


Previous Up Next