DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 04-2 Modeling Traffic Jams with Cellular Automata

Date prepared: September 9, 2004

Stephanie Edwards University of Dayton Dayton, OH 45469-2316 email: sedwards@udayton.edu

Mark Ginn Appalachian State University Boone, NC 28608-2092 email: ginnmc@appstate.edu

John Harris Furman University Greenville, SC 29613 email: john.harris@furman.edu

Gregory Rhoads Appalachian State University Boone, NC 28608-2092 email: rhoadsgs@appstate.edu

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                         Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

Module Description Information

• Title:

Modelling Traffic Jams with Cellular Automata

• Authors:

Stephanie Edwards, University of Dayton Mark Ginn, Appalachian State University John Harris, Furman University Gregory Rhoads, Appalachian State University

• Abstract:

The module touches on several topics of mathematical interest. Mathematical modeling in general is discussed briefly at the start, and then some details regarding traffic models are given. Cellular automata (CA), both deterministic and probabilistic, are introduced as a method for modeling traffic flow. The software package Mirek’s Cellebration (MCell) is presented as a way of handling the long-run forecasting of different CAs.

• Informal Description:

The concept of cellular automata is motivated by easy-to-follow examples. While much of the material in the module concerns simple deterministic CAs, there is a section at the end on probabilistic CAs. Instructors could spend as much or as little time as desired on each type. MCell is a software package that is available for free download, and students will enjoy trying out its many interesting features. Regarding traffic, students can easily experiment with initial densities and other features that affect the way traffic flows. There are plenty of exercises throughout the module that give students the opportunity to solidify the concepts for themselves.

• Target Audience:

This module is designed for advanced high school students and lower level college students. It would be a good module for a liberal arts mathematics class.

• Prerequisites:

This module assumes some familiarity with computers and downloading software from the internet. It assumes that the students have had high school algebra.

• Mathematical Field:

Probability, Discrete Mathematics, Cellular Automata

• Applications Areas:

This module uses cellular automata and technology to model traffic jams.

• Mathematics Subject Classification:

Primary: 37B15 Secondary: 60K30 • Contact Information:

Stephanie Edwards University of Dayton Dayton, OH 45469-2316 email: sedwards@udayton.edu

Mark Ginn Appalachian State University Boone, NC, 28608-2092 email: ginnmc@appstate.edu

John Harris Furman University Greeneville, SC, 29613 email: john.harris@furman.edu

Gregory Rhoads Appalachian State University Boone, NC, 28608-2092 email: rhoadsgs@appstate.edu

• Other DIMACS modules related to this module:

04-1: Probability and Chip Firing Games

Contents

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Modeling Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 One Dimensional Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 MCell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 To find this rule in MCell: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 The Slow Lane: Deterministic Traffic Model . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 “Move if you can” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Modeling Traffic Using MCell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Densities in the move-if-you-can model . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 The Expressway: Probabilistic Traffic Model . . . . . . . . . . . . . . . . . . . . . . . 24 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 A Simple Probabilistic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3 The Probabilistic Traffic CA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

ABSTRACT

The module touches on several topics of mathematical interest. Mathematical modeling in general is discussed briefly at the start, and then some details regarding traffic models are given. Cellular automata (CA), both deterministic and probabilistic, are introduced as a method for modeling traffic flow. The software package Mirek’s Cellebration (MCell) is presented as a way of handling the long-run forecasting of different CAs.

1 Introduction

What comes to mind when you hear the term “traffic jam?” Congestion, brake lights, aggravation, road rage, horn blowing — the list goes on and on. Traffic jams are indeed unpleasant.

What causes traffic jams? Accidents, construction work, lane closings, and incompetent drivers are often to blame. But why is it that some jams just seem to appear out of nowhere? In this module we will use mathematics to help us to understand — that is, to model — this highway phenomenon.

Before beginning, let us first discuss mathematical models in general. A mathematical model is a type of mathematical construction that is used to simulate real world phenomena. The mathematical model can then be analyzed in the hope that the information obtained from the model will give some information about the real world phenomena. Mathematical models are used in a wide variety of situations, from weather forecasting and financial markets to epidemiology, medicine, and traffic.

Mathematical models can be used for many different purposes. Often they are used to make predictions about the future, as is the case in weather and economic forecasts. Sometimes they are used not to make predictions but rather to try to understand the phenomena being modelled. This is often the case in epidemiology where analyzing data about the number of people that have a disease at a given time can give some information about how the disease is spread. While many people have made mathematical models of traffic flow for forecasting purposes, our model will be of the second type. We will try to build a model to help us understand how traffic jams form and then maybe what can be done to help alleviate them.

A mathematical model may be as simple as a single equation or a system of equations or something much more complex. Typically, the more complex the model the better it simulates the real world situation being modelled. However complex models tend to be more difficult to analyze so simpler models are used instead. Often there are trade-offs to be made between complexity and accuracy. In our situation, we will be trying to come up with the simplest model we can that exhibits the desired phenomena.

1.1 Modeling Traffic

Several different mathematical models for traffic have emerged in recent years. Physicists and mathematicians alike have applied numerous methods to the study of traffic flow [2]. One model relates traffic to liquid. Think about how traffic flow looks from an airplane — at times, the traffic down below almost looks like fluid flowing down the highway. Kinetic theories, Newtonian mechanics, and differential equations are sophisticated mathematical elements of other investigations. An August, 1999 Washington Post article [7] described results of recent traffic research in the following way.

Scientists have identified “phase changes” in traffic, similar to the sudden transitions that occur when steam turns to water or water to ice. Understanding the timing and dynamics of phase changes in traffic, like those in nature, poses a challenge for physicists. …

Phase 1. When traffic is light, motorists drive much as they like, moving at the speed they want and changing lanes easily. Motorists are comparable to steam particles with great freedom of movement.

Phase 2. As the road becomes crowded, motorists suddenly lose much of their freedom and are forced to drive as part of the overall traffic stream, moving at the speed of the general flow and often unable to change lanes. This phase, similar to water, has been called “synchronized” flow.

Phase 3. In heavy congestion, traffic is stop-and-go. Like water freezing into ice, the motorists are stuck in place.

In 2001 Larry Gray and David Griffeath [3] developed the first simple, discrete model in which each of the three phases mentioned in the Post article can be observed. We will investigate their model in this module. Their model uses one dimensional cellular automata. We will study cellular automata in the next section.

1.2 One Dimensional Cellular Automata

Let’s begin this section by looking at some examples.

Example 1.1. Think about a number line which extends infinitely in both directions, and imagine that there is a little light bulb situated on the top of every whole number. Here is a small piece of the number line.

Light Bulbs

At 12:00 noon, some of the light bulbs are on and some are off. At 12:01, the lights have switched states. Again at 12:02, the lights have switched again. Do you see the pattern developing? Can you predict how the lights will look at 12:03?

In this example, the lights are really following two simple rules:

• Rule 1: If a light bulb is on during the present time unit, then it will switch to off one time unit later.

• Rule 2: If a light bulb is off during the present time unit, then it will switch to on one time unit later.

Note: our time units are represented by minutes in this example.

These two rules can be altered to form other interesting sequences of lights. The next example illustrates this idea.

Example 1.2. Consider the following figure. Again, there are light bulbs on top of each number along the infinite number line. We are shown only a small piece of the line.

Light bulbs turning on and off.

Notice that with each passing minute, some lights switch states, and some do not. Why is this? Can you detect the pattern?

Again, there are just two simple rules that govern the action of the lights in this example. Notice how Rule 2 has a bit of a new look.

• Rule 1: If a light bulb is on during the present time unit, then it will switch to off one time unit later.

• Rule 2: If a light bulb is off during the present time unit, then it will switch to on one time unit later only if exactly one of the two adjacent lights is presently on. Otherwise, the light stays off.

Let’s examine this particular example more closely. At 12:00, the lights at 12, 14, and 17 were on. So, according to Rule 1, at 12:01, each of these lights switched to off. The light at 13 was off at 12:00, and both of its adjacent lights (neighbors), 12 and 14, were on at that time. Thus according to Rule 2, 13 stayed off at 12:01. (The only way that a light which is off can switch to on is if exactly one of the two adjacent lights (neighbors) is on). The light at 15 was also off at 12:00, and exactly one of its neighbor lights, namely 14, was on. Therefore, according to Rule 2, the light at 15 switches on at 12:01.

So why the question marks? Take for example the light at 11, which is off at 12:00. Since we cannot see the light at 10, there is no way for us to know how many of 11’s neighbor lights are on. For this reason, we don’t know how the light at 11 will look at 12:01 — hence the question mark. The other question marks in the figure arise from similar reasons. See if you can figure out why they are there.

There is an interesting difference to note between these two examples. In Example 1.1, the future status of a particular light bulb depended only on the current status of that light bulb. In Example 1.2, however, a light bulb’s future status depends not only on its own current status, but also on the current status of light bulbs near it.

Example 1.3. In this example, we will use 0’s and 1’s to denote off light bulbs and on light bulbs respectively. We will use the same rule as we used in Example 1.2 but with a different configuration of on and off light bulbs.

t = 0 0 1 0 1 1 0 0 0
t = 1
t = 2
t = 3

Notice how we don’t know where on the number line these light bulbs are sitting - but we actually don’t care! Now, we can use the rule to fill in the rest of the table.

\begin{matrix}t = 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ t = 1 & ? & 0 & 0 & 0 & 0 & 1 & 0 & ? \\ t = 2 & ? & ? & 0 & 0 & 1 & 0 & ? & ? \\ t = 3 & ? & ? & ? & 1 & 0 & ? & ? & ? \end{matrix}

Example 1.4. In this example, we again use 0’s and 1’s to denote off light bulbs and on light bulbs respectively. We will use the same rule as we used in Example 1.3 but the only difference is the series of dots before the initial 0 and after the last 0. These dots mean that the 0’s continue infinitely to the left and to the right (i.e. no more 1’s).

t = 0 ⋯ 0 1 0 1 1 0 0 0 ⋯
t = 1
t = 2
t = 3

Now, we can use the rule to fill in the rest of the table. The dots (or knowing that 0’s continue infinitely to the left and the right) allows us to completely fill in the table.

\begin{matrix}t = 0 & ⋯ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0⋯ \\ t = 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ t = 2 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ t = 3 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{matrix}

Example 1.5. Again, in this example, we will use 0’s and 1’s to denote off light bulbs and on light bulbs respectively. Our rules are the following:

• Rule 1: If a light bulb is on during the present minute, then it will switch to off in the next minute only if its right neighbor is off during the present minute.

• Rule 2: If a light bulb is off during the present minute, then it will switch to on in the next minute only if its left neighbor is on during the present minute.

Now, consider the following initial configuration of on and off light bulbs.

t = 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0

After the first time step, our table will look like the following.

\begin{matrix}t = 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ t = 1 & ? & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \end{matrix}

And now we see what happens at time steps 2 and 3.

\begin{matrix}t = 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ t = 1 & ? & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ t = 2 & ? & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ t = 3 & ? & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & ? \end{matrix}

These examples are illustrations of a mathematical construction called cellular automata (or CA for short). A CA can be thought of as an intricate collection of identical objects, each of which is said to be in some particular state (on or off, for example). As distinct time periods pass, the objects (or cells), may change from state to state according to a particular set of rules. These rules and the list of possible states are the same for each object.

These examples are very simple examples of a cellular automata. There are several aspects of these CAs that can be varied to form other CAs. Here are some examples.

• The set of possible states could be different. Instead of two (off and on), there could be three (say, off, dim, and bright), or more.

• The rule can vary in terms of the neighboring cells’ status. For instance, the 0’s might change to 1’s if one or two neighboring (adjacent) cells have 1’s in them.

• The rule could be different in that the relevant neighborhood might be larger. In the example above, it was just the status of the two closest neighbors that affected the center cell. It very well could be that this “range” of cells is bigger.

• The playing field might be different. Instead of the one dimensional number line, grids of higher dimensions could be used. The most famous two dimensional cellular automata is John Conway’s “Game of Life”.

For more information about cellular automata, we refer the reader to S. Wolfram’s book [9].

1.3 Exercises

As in the examples in this section, ⋯ 0 means that 0’s continue infinitely to the left and 0 ⋯ means that 0’s continue infinitely to the right. If no dots are present, it is unknown what is happening to the left and/or the right.

(1) Consider the following rule: An off light turns on if it has at least one on neighbor. An on light bulb goes off if it has exactly 2 on neighbors. The following represents an initial configuration (at t = 0). Fill in the boxes for t = 1, 2, 3. Use 1 to denote an on light and 0 to denote an off light.

t = 0 0 0 0 1 1 0 0 0
t = 1
t = 2
t = 3

(2) Using the same rule as in Exercise (1), fill in the boxes for t = 1, 2, 3. Use 1 to denote an on light and 0 to denote an off light. The dots that appear next to the zeros mean that 0’s continue to the left and to the right (i.e. no more 1’s).

t = 0 ⋯ 0 0 0 1 1 0 0 0 ⋯
t = 1
t = 2
t = 3

(3) Using the same rule as in Exercise (1), fill in the boxes for t = 1, 2, 3. Use 1 to denote an on light and 0 to denote an off light. The dots that appear next to the zeros mean that 0’s continue to the left and to the right (i.e. no more 1’s).

t = 0 ⋯ 0 0 0 1 1 0 0 0 1 0 0 0⋯
t = 1
t = 2
t = 3

(4) Using the rule from Example 1.2, fill in the boxes for t = 1, 2, 3, 4, 5, 6, 7. Use 1 to denote an on light and 0 to denote an off light. The dots that appear next to the zeros mean that 0’s continue to the left and to the right (i.e. no more 1’s).

t = 0 ⋯ 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0⋯

t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 t = 7

Note: These rules, together with this initial configuration, give rise to a CA called “Pascal’s Triangle”. Can you see why?

(5) Use the rule from Example 1.2 with the following exception: If a light is on and both of its neighbors are off, the light remains on. Fill in the boxes for t = 1, 2, 3, 4, 5, 6, 7. Use 1 to denote an on light and 0 to denote an off light. The dots that appear next to the zeros mean that 0’s continue to the left and to the right (i.e. no more 1’s).

t = 0 ⋯ 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0⋯

t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 t = 7

How does this CA differ from the one in the previous exercise?

(6) Can traffic lights and/or digital clocks be thought of as cellular automata? Explain!

2 MCell

In Section 1 we calculated how certain initial configurations behave under a given rule for a few time periods. It is easy to see how difficult it would be to calculate what happens “in the long run,” or as time increases. Fortunately, there is an amazing software program available called Mirek’s Cellebration, or MCell, for short, created by Mirek Wojtowicz [8]. It can be downloaded for free from http://psoup.math.wisc.edu/mcell/. You will need internet access to download the program and once it is installed, you will not need the internet. In this section we will introduce the reader to some of the features of MCell.

We will use MCell to explore Example 1.2. The rules used in the example were as follows:

• Rule 1: If a light bulb is on during the present time unit, then it will switch to off one time unit later.

• Rule 2: If a light bulb is off during the present time unit, then it will switch to on one time unit later only if exactly one of the two adjacent lights is presently on. Otherwise, the light stays off.

We could represent these rules in another way. Let us begin by exploring rule 1: If the light bulb is on at the present time unit then it will switch to off one time unit later. Suppose a light bulb is on and both of its neighbors are off. Using 0’s and 1’s as before we can denote this situation in the following way:

left neighbor light bulb right neighbor 0  1  0

Or simply: 010

If exactly one neighbor light is on, the situation would be: 110 or 011. And if both neighbor lights are on we have 111. In each of these situations, the middle light (the light of interest) will go off. So we can denote this occurrence in the following way:

present time unit next time unit

0 1 0 →  0

Then the other scenarios are

present time unit next time unit

0 1 1 →  0
1 1 0 →  0
1 1 1 →  0

We can extend this idea to include rule 2 - If a light bulb is off during the present time, then it will switch to on in the next time only if exactly one of the two adjacent lights is presently on. Otherwise, the light stays off. We can write both of the rules in one table in the following way.

initial time unit next time unit
010  0
011  0
110  0
111  0
000  0
001  1
100  1
101  0

This table shows the cell in question and each of its two neighbors. We can see that all of the on lights go off and the off lights come on only when exactly one of its neighbors is on. This is the way our computer software represents the rule. Recall, we mentioned in the exercises in the previous section, that these rules were called “Pascal’s Triangle”.

2.1 To find this rule in MCell:

Recall, MCell is available to download for free from http://psoup.math.wisc.edu/mcell/. Once installed, it does not require internet access to run.

• Open up MCell

• You will see a list of folders in the upper left-hand corner of the screen. Click on the MCell folder and then open the folder called “1D Binary.”

MCell Screen

• Below the list of folders, there is now a list of *.mcl files - open the one called “Pascal’s Triangle.mcl.”

• Go to the ‘Rules’ menu (along the top of the screen) and open ‘Rules - setup’

Mcell - Setting - Rules Screen

• On the left-hand side of the dialog box will be the rules, in a format similar to the table we just created above. Click OK after you’ve looked at the rule. It is possible to change the rules here.

• Press the “continuous play” button and see MCell run the rule! If you want to see one step at a time, press the “slow play” button which is located immediately to the right of the “continuous play” button.

Continuous Play Button

• You can enlarge and shrink the viewing area by using the magnifying glass buttons (+ to enlarge, - to shrink). The button on the far right is a “Shrink to fit” button which picks a nice size for you.

• To stop MCell from drawing, press the “stop” button (the square).

Stop Button

Example 2.1. Using MCell, 1D Binary, try out Pascal’s Triangle and see if you get the following picture. (Use “Shrink to fit”.) Note - you may have colors other than black and white in your screen - it is OK!

MCell - Pascal’s Triangle

Example 2.2. Using MCell, 1D Binary, try out Kites.mcl and see if you get the following picture. (Use “Shrink to fit”.)

MCell - Kites

2.2 Exercises

Note: once you have run a rule, to reset the screen, click on that rule again.

(1) Run the rule “SolitonsA.mcl”. Look at the rules and change the first rule so that you have the light turning on instead of staying off. Does the picture look different now? Describe.

(2) Run the rule “SolitonsA.mcl”. Look at the rules and change the fourth rule so that you have the light turning off instead of staying on. Does the picture look different now? Describe.

(3) Run the rule “SolitonsD1.mcl”. Look at the rules and change the first rule so that you have the light turning on instead of staying off. Does the picture look different now? Describe.

(4) Run the rule “SolitonsD1.mcl”. Look at the rules and change the fifth rule so that you have the light turning off instead of staying on. Does the picture look different now? Describe.

(5) Run the rule “Brownian motion.mcl”. Look at the rules. These rules can also be stated as: If a light has both neighbors off, then the light does not change. Otherwise, the light changes. Change the rule to one that can be stated as: If a light has both neighbors off, then the light turns on. Write down the rule in the form of a table. Run the rule and describe the differences.

�

(6) Run the rule “Brownian motion.mcl”. Look at the rules. These rules can also be stated as: If a light has both neighbors off, then the light does not change. Otherwise, the light changes. Change the rule to one that can be stated as: If a light has both neighbors off, then the light turns off. Write down the rule in the form of a table. Run the rule and describe the differences.

3 The Slow Lane: Deterministic Traffic Model

Back in Section 1, we saw that

• Cellular automata are collections of identical objects having one of a finite number of states and a set of rules for determining how the state of an object changes from one moment to the next.

• An example of a cellular automata is a sequence of light bulbs which can have one of two states on or off.

One of the goals of modelling is to find a mathematical representation of a real-life situation that we wish to study. The model must also be simple enough to be easily analyzed. No one will argue that our light bulb example is simple, and in this section, we show that we can use the same ideas to model traffic flow on a one-lane highway. We will study the model built by Gray and Griffeath [3]. There are other models of traffic out there (see [1], [4], [5], [6]).

Our one-lane highway will not include on-ramps, off-ramps, or other ways for cars to enter or exit the road. This assumption may seem unrealistic, but our goal is to find the simplest “interesting” model which contains traffic jams. We will also assume our highway is infinitely long.

Let us represent our highway by the infinite real number line with the integers denoting the possible locations of the cars. At each integer, we will assign a value of either 0 or 1. Assigning a value of 1 will indicate a car occupies that location, and a 0 will indicate the location is empty. Notice the similarities between the highway example and the light bulb example. The light bulbs correspond to the locations on the highway and each has two possible states: on/off for the light bulbs and car/no-car for the highway example.

Example 3.1. This is an example of a possible configuration of a highway.

Cars

We will assume cars are located in locations 2, 3, 6, 10, 11, and 12 while locations 1, 4, 5, 7, 8, 9, 13, 14, and 15 are empty. We will represent our highway with the following table (note: the picture only goes up to location 13, however, our table representation goes up to location 15):

location 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
t = 0  0 1 1 0 0 1 0 0 0 1 1 1 0 0 0

As seen in the picture, each car is traveling to the right (towards higher numbers). From here on out, we assume that the cars will be traveling to the right.

13