\documentclass[11pt]{article}

%\usepackage{maple2e}

\usepackage{dimacsmodules}

\usepackage{amsfonts}

\usepackage{amssymb}

\usepackage{amsmath}

\usepackage{amsthm}

%\usepackage{macros}
%latex2e
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{question}[theorem]{Question}
\newtheorem{prop}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{notation}[theorem]{Notation}

\theoremstyle{remark}
\newtheorem*{note}{Note}
\newtheorem*{claim}{Claim}

%\renewcommand\theenumi{\roman{enumi}}
%\renewcommand\theenumi{\alph{enumi}}
\renewcommand\labelenumi{(\theenumi)}

\renewcommand\cases[1]{\left\{\mbox{\begin{tabular}{@{$}l@{$
\qquad}l}#1\end{tabular}}\right.}
\newcommand\intv[3]{{#1}\leq{#2}\leq{#3}}
\newcommand\interval[3]{{#1}\leq{#2}\leq{#3}}
\newcommand\bdry{\partial}
\newcommand\half{\frac12}
\newcommand\be{\begin{equation}}
\newcommand\ee{\end{equation}}
\newcommand\best{\begin{equation*}}
\newcommand\eest{\end{equation*}}
\newcommand\hs[1]{\hspace{#1 em}}
\newcommand\bea{\begin{eqnarray}}
\newcommand\eea{\end{eqnarray}}
\newcommand\inv{^{-1}}
\newcommand\im{\hbox{Im}}
\newcommand\inte{\hbox{Int}}
\newcommand\re{\hbox{Re}}
\newcommand\hp{H^{+}}
\newcommand\hm{H^{-}}
\newcommand\sgn{\hbox{sgn}}
\newcommand\ord{\hbox{ord}}
\newcommand\goes{\rightarrow}

\newcommand\integers{\mathbb Z}
\newcommand\naturals{\mathbb N}
\newcommand\rationals{\mathbb Q}
\newcommand\reals{\mathbb R}
\newcommand\complexes{\mathbb C}
\newcommand\ds{\displaystyle}
\newcommand\sss{\scriptstyle}


\usepackage{epsfig}

%\input{epsf.def}

%\usepackage{exam}

%\usepackage{../../std}

\textheight 9 in

%\parindent 0in

%\pagestyle{empty}

%\setlength{\topmargin}{ 0. in}

%\setlength{\headheight}{1cm}

%\setlength{\headsep}{0.3cm}

%\setlength{\oddsidemargin}{0.6 cm}

%\setlength{\evensidemargin}{-0.2cm}

%\setlength{\textwidth}{6 in}

\begin{document}

\pagenumbering{roman}
\begin{publicity}

\begin{center}
\vspace{.4in}
{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{0.7in}

{\Large \bf MODULE 04-2}\\
{\Large \bf Modeling Traffic Jams with Cellular Automata}\\
{\large \bf Date prepared: \today}

\vspace{.5in}

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

\bigskip

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

\bigskip

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

\bigskip

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

\end{center}
\vfill

\end{publicity}

\setcounter{page}{0}
\newpage

\begin{center}
{\large \bf Module Description Information}
\end{center}

\begin{itemize}

\item {\bf Title:}

Modelling Traffic Jams with Cellular Automata

\item {\bf Authors:}

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

\item {\bf Abstract:}

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

\item {\bf 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.

\item {\bf 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.

\item {\bf Prerequisites:}

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

\item {\bf Mathematical Field:}

Probability, Discrete Mathematics, Cellular Automata

\item {\bf Applications Areas:}

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

\item {\bf Mathematics Subject Classification:}

Primary:  37B15\\
Secondary:  60K30

\item {\bf Contact Information:}

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

\bigskip

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

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

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

\item {\bf Other DIMACS modules related to this module:}

04-1:  Probability and Chip Firing Games

\end{itemize}

\newpage
\setcounter{page}{0}
\pagenumbering{arabic}
\tableofcontents

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


\newpage
\setcounter{section}{0}








%\rightline{\large Reconnect 2000}



%\rightline{\large Group \#4}



%\rightline{\large Stephanie Edwards}



%\rightline{\large Mark Ginn - contact person}



%\rightline{\large John Harris}



%\rightline{\large Greg Rhoads}







%\vskip 2 in



%\centerline{\Huge Modeling Traffic Jams with Cellular Automata}





%\newpage



%\title{Modeling Traffic Jams with Cellular Automata}

%\author{Stephanie Edwards,  Mark Ginn, John Harris, Greg Rhoads}



%\maketitle



\section{Introduction}\label{S:intro}

%        \input{intro}

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.

\vspace{.1in}

\subsection{Modeling Traffic}

\vspace{.1in}

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 \cite{Chow}.  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 {\em Washington Post} article \cite{post} described
results of recent traffic research in the following way.

\begin{quotation}
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. \ldots

{\em 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.

{\em 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.

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

In 2001 Larry Gray and David Griffeath \cite{larry} developed the
first simple, discrete model in which each of the three phases
mentioned in the {\em 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.

\vspace{.1in}

\subsection{One Dimensional Cellular Automata}

\vspace{.1in}

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

\begin{example}\label{E:example1}
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.\vskip0.05truein

%\epsfxsize = 4.7truein
\epsfysize = 2.4truein \centerline{\epsfbox{Images/lightbulb1.eps}}
\centerline{Light Bulbs} \vskip0.1truein At 12:00 noon, some of
the light bulbs are {\em on} and some are {\em 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:

\begin{itemize}
\item {\bf Rule 1:} If a light bulb is {\em on} during the present
time unit, then it will switch to {\em off} one time unit later.
\item {\bf Rule 2:} If a light bulb is {\em off} during the
present time unit, then it will switch to {\em on} one time unit
later.
\end{itemize}
Note:  our time units are represented by minutes in this example.
\end{example}

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

\begin{example}\label{E:example2}
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.

\vskip0.05truein
%\epsfxsize = 4.7truein
\epsfysize = 2.5truein
\centerline{\epsfbox{Images/lightbulb2.eps}} \centerline{Light
bulbs turning {\em on} and {\em off}.} \vskip0.1truein

 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.

\begin{itemize}
\item {\bf Rule 1:} If a light bulb is {\em on} during the present
time unit, then it will switch to {\em off} one time unit later.
\item {\bf Rule 2:} If a light bulb is {\em off} during the
present time unit, then it will switch to {\em on} one time unit
later {\em only if} exactly one of the two adjacent lights is
presently {\em on}. Otherwise, the light stays {\em off}.
\end{itemize}

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

So why the question marks?  Take for example the light at 11,
which is {\em 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 {\em 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.
\end{example}

There is an interesting difference to note between these two
examples. In Example \ref{E:example1}, the future status of a
particular light bulb depended only on the current status of {\em
that} light bulb.  In Example \ref{E:example2}, 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.

\begin{example}\label{E:example3}
In this example, we will use 0's and 1's to denote {\em off} light
bulbs and {\em on} light bulbs respectively.  We will use the same
rule as we used in Example~\ref{E:example2} but with a different
configuration of {\em on} and {\em off} light bulbs.

\bigskip

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $t=0$ &
0&1&0&1&1&0&0&0\\ \hline \hline $t=1$ & & & & & & & & \\
\hline $t=2$ & & & & & & & & \\ \hline $t=3$ & & & & & & & & \\
\hline
\end{tabular}}

\bigskip

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.

\bigskip

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $t=0$ &
0&1&0&1&1&0&0&0\\ \hline \hline $t=1$ & ?& 0 &0 &0 &0 &1 &0&? \\
\hline $t=2$ &? &? & 0&0 &1 &0 & ?&? \\ \hline $t=3$ & ?& ?&? & 1&
0& ?& ?&? \\ \hline
\end{tabular}}
\end{example}


\begin{example}\label{E:example4}
In this example, we again use 0's and 1's to denote {\em off}
light bulbs and {\em on} light bulbs respectively.  We will use
the same rule as we used in Example~\ref{E:example3} 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).

\bigskip

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $t=0$ &
$\cdots$ 0&1&0&1&1&0&0&0 $\cdots$\\ \hline \hline $t=1$ & & & & & & & & \\
\hline $t=2$ & & & & & & & & \\ \hline $t=3$ & & & & & & & & \\
\hline
\end{tabular}}

\bigskip

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.

\bigskip

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $t=0$ &
$\cdots$0&1&0&1&1&0&0&0$\cdots$\\ \hline \hline $t=1$ & 1& 0 &0 &0 &0 &1 &0&0 \\
\hline $t=2$ &0 &1 & 0&0 &1 &0 & 1&0 \\ \hline $t=3$ & 1& 0&1 & 1&
0& 0& 0&1 \\ \hline
\end{tabular}}
\end{example}

\begin{example}\label{E:miyc}
Again, in this example, we will use 0's and 1's to denote {\em
off} light bulbs and {\em on} light bulbs respectively.  Our rules
are the following:

\begin{itemize}
\item {\bf Rule 1:} If a light bulb is {\em on} during the present
minute, then it will switch to {\em off} in the next minute {\em
only if} its right neighbor is {\em off} during the present
minute. \item {\bf Rule 2:} If a light bulb is {\em off} during
the present minute, then it will switch to {\em on} in the next
minute {\em only if} its left neighbor is {\em on} during the
present minute.
\end{itemize}

\noindent Now, consider the following initial configuration of
{\em on} and {\em off} light bulbs.

\bigskip

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ &0&1&1&1&0&1&0&0&0&1&1&1&1&0&0 \\ \hline
%\hline
%$t=1$ & & & & & & & & & & & & & & & \\ \hline
%$t=2$ & & & & & & & & & & & & & & & \\ \hline
%$t=3$ & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

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

\bigskip

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ &0&1&1&1&0&1&0&0&0&1&1&1&1&0&0\\ \hline \hline $t=1$
&?&1&1&0&1&0&1&0&0&1&1&1&0&1&0\\ \hline
%$t=2$ & & & & & & & & & & & & & & & \\ \hline
%$t=3$ & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

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

\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ &0&1&1&1&0&1&0&0&0&1&1&1&1&0&0\\ \hline \hline $t=1$
&?&1&1&0&1&0&1&0&0&1&1&1&0&1&0\\ \hline $t=2$
&?&1&0&1&0&1&0&1&0&1&1&0&1&0&1\\ \hline $t=3$
&?&0&1&0&1&0&1&0&1&1&0&1&0&1&?\\ \hline
\end{tabular}}
\end{example}

These examples are illustrations of a mathematical construction
called {\bf 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 ({\em on} or {\em
off}, for example).  As distinct time periods pass, the objects
(or {\em 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.

\vspace{.1in}

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.

\begin{itemize}

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

\item The rule can vary in terms of the neighboring cells' status.
For instance, the 0's might change to 1's if one {\em or} two
neighboring (adjacent) cells have 1's in them.

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

\item 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''.

\end{itemize}

For more information about cellular automata, we refer the reader
to S. Wolfram's book \cite{wolfram}.



\bigskip

\subsection{Exercises}

As in the examples in this section, $\cdots 0$ means that 0's
continue infinitely to the left and $0 \cdots $ 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.

\begin{enumerate}

\item  Consider the following rule: An {\it off} light turns {\em
on} if it has at least one {\it on} neighbor.  An {\it on} light
bulb goes {\em off} if it has exactly 2 {\it 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 {\em on} light and
0 to denote an {\em off} light.

\bigskip
\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $t=0$ &
0&0&0&1&1&0&0&0\\ \hline \hline $t=1$ & & & & & & & & \\
\hline $t=2$ & & & & & & & & \\ \hline $t=3$ & & & & & & & & \\
\hline
\end{tabular}}

\item  Using the same rule as in Exercise (1), fill in the boxes
for $t=1, 2, 3$.  Use 1 to denote an {\em on} light and 0 to
denote an {\em 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).

\bigskip
\centerline {\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline $t=0$ &
$\cdots $0&0&0&1&1&0&0&0 $\cdots $\\ \hline \hline $t=1$ & & & & & & & & \\
\hline $t=2$ & & & & & & & & \\ \hline $t=3$ & & & & & & & & \\
\hline
\end{tabular}}


\item  Using the same rule as in Exercise (1), fill in the boxes
for $t=1, 2, 3$.  Use 1 to denote an {\em on} light and 0 to
denote an {\em 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).

\bigskip

\centerline{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|} \hline
$t=0$ & $\cdots$0&0&0&1&1&0&0&0&1&0& 0&0$\cdots$\\
\hline\hline $t=1$ & & & & & & & & & & & & \\ \hline $t=2$ & & & &
& & & & & & & & \\ \hline $t=3$ & & & & & & & & & & & & \\ \hline
\end{tabular}}

\item  Using the rule from Example~\ref{E:example2}, fill in the
boxes for $t=1, 2, 3, 4, 5, 6, 7$.  Use 1 to denote an {\em on}
light and 0 to denote an {\em 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).

\bigskip

\centerline{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$t=0$ & $\cdots$0&0&0&0&0&0&0&1&0&0&0&0&0& 0&0$\cdots$\\
\hline\hline $t=1$ & & & & & & & & & & & & & & & \\ \hline $t=2$ &
& & & & & & & & & & & & & & \\ \hline $t=3$ & & & & & & & & & & &
& & & & \\ \hline $t=4$ & & & & & & & & & & & & & & & \\ \hline
$t=5$ & & & & & & & & & & & & & & & \\ \hline $t=6$ & & & & & & &
& & & & & & & & \\ \hline $t=7$ & & & & & & & & & & & & & & & \\
\hline
\end{tabular}}

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

\item  Use the rule from Example~\ref{E:example2} with the
following exception:  If a light is {\it on} and both of its
neighbors are {\em off}, the light remains {\em on}.  Fill in the
boxes for $t=1, 2, 3, 4, 5, 6, 7$.  Use 1 to denote an {\em on}
light and 0 to denote an {\em 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).

\bigskip

\centerline{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$t=0$ & $\cdots$0&0&0&0&0&0&0&1&0&0&0&0&0& 0&0$\cdots$\\
\hline\hline $t=1$ & & & & & & & & & & & & & & & \\ \hline $t=2$ &
& & & & & & & & & & & & & & \\ \hline $t=3$ & & & & & & & & & & &
& & & & \\ \hline $t=4$ & & & & & & & & & & & & & & & \\ \hline
$t=5$ & & & & & & & & & & & & & & & \\ \hline $t=6$ & & & & & & &
& & & & & & & & \\ \hline $t=7$ & & & & & & & & & & & & & & & \\
\hline
\end{tabular}}

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

\bigskip

\item  Can traffic lights and/or digital clocks be thought of as
cellular automata?  Explain!

\end{enumerate}


\section{MCell}\label{S:mcell}

 %       \input{mcell}
In Section~\ref{S:intro} 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 {\it MCell}, for short, created by Mirek
Wojtowicz \cite{mcell}.  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~\ref{E:example2}. The rules
used in the example were as follows:

\begin{itemize}
\item {\bf Rule 1:} If a light bulb is {\em on} during the present
time unit, then it will switch to {\em off} one time unit later.
\item {\bf Rule 2:} If a light bulb is {\em off} during the
present time unit, then it will switch to {\em on} one time unit
later {\em only if} exactly one of the two adjacent lights is
presently {\em on}. Otherwise, the light stays {\em off}.
\end{itemize}

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

\bigskip

\centerline{\begin{tabular}{ccc}
left neighbor & light bulb & right neighbor \\
\hline 0 & 1 & 0 \\
\end{tabular}}
\noindent

\smallskip

\centerline{Or simply:  $010$}

\bigskip

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

\bigskip

\centerline{present time unit \quad next time unit}

\centerline{
\begin{tabular}{|c|c|c|} \hline
0&1&0\\ \hline
\end{tabular} $\rightarrow$
\begin{tabular} {|c|c|c|} \hline
\hbox{ } & 0 &\hbox{ }  \\ \hline
\end{tabular}}

\bigskip

\noindent Then the other scenarios are

\centerline{present time unit \quad next time unit}

\centerline{
\begin{tabular}{|c|c|c|} \hline
0&1&1\\ \hline
\end{tabular} $\rightarrow$
\begin{tabular} {|c|c|c|} \hline
\hbox{ }  & 0 & \hbox{ } \\ \hline
\end{tabular}}

\centerline{
\begin{tabular}{|c|c|c|} \hline
1&1&0\\ \hline
\end{tabular} $\rightarrow$
\begin{tabular} {|c|c|c|} \hline
 \hbox{ } & 0 & \hbox{ } \\ \hline
\end{tabular}}

\centerline{
\begin{tabular}{|c|c|c|} \hline
1&1&1\\ \hline
\end{tabular} $\rightarrow$
\begin{tabular} {|c|c|c|} \hline
\hbox{ } & 0 &\hbox{ }  \\ \hline
\end{tabular}}


\bigskip

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

\medskip \centerline{\begin{tabular}{|c|c|} \hline initial time
unit & next
time unit \\ \hline\hline 010 & 0\\ \hline 011 & 0 \\ \hline 110 & 0 \\
\hline 111 & 0 \\ \hline 000 & 0\\ \hline 001 & 1\\ \hline 100 &
1\\ \hline 101 & 0 \\ \hline
\end{tabular}}
\medskip

\noindent This table shows the cell in question and each of its
two neighbors.  We can see that all of the {\it on} lights go {\it
off} and the {\it off} lights come {\it on} only when exactly one
of its neighbors is {\it 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''.

\subsection{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.

\begin{itemize}
\item  Open up MCell \item  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.''


\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 3truein \centerline{\epsfbox{Images/mcellintro1.eps}
} \centerline{MCell Screen} \vspace{0.1in}

\item  Below the list of folders, there is now a list of *.mcl
files - open the one called ``Pascal's Triangle.mcl.''


\item Go to the `Rules' menu (along the top of the screen) and
open `Rules - setup'


\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 3truein \centerline{\epsfbox{Images/mcellintro2.eps}}
\centerline{Mcell - Setting - Rules Screen} \vspace{0.1in}


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


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

\vspace{0.1in}
%\epsfxsize = 2.7truein
\epsfysize = .8truein \centerline{\epsfbox{Images/playbutton.eps}}
\centerline{Continuous Play Button} \vspace{0.1in}

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

\item To stop MCell from drawing, press the ``stop'' button (the
square).

\vspace{0.1in}
%\epsfxsize = 2.7truein
\epsfysize = .8truein \centerline{\epsfbox{Images/stopbutton.eps}}
\centerline{Stop Button} \vspace{0.1in}

\end{itemize}

\begin{example}\label{E:on-off-2} 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!

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 1.9truein \centerline{ \epsfbox{Images/pascal.eps}}
\centerline{MCell - Pascal's Triangle} \vspace{0.1in}
\end{example}

\begin{example}\label{E:kites}
Using MCell, 1D Binary, try out Kites.mcl and see if you get the
following picture.  (Use ``Shrink to fit''.)

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 1.9truein \centerline{\epsfbox{Images/kite.eps}}
\centerline{MCell - Kites} \vspace{0.1in}
\end{example}

\subsection{Exercises}
Note:  once you have run a rule, to reset the screen, click on
that rule again.
\begin{enumerate}
\item  Run the rule ``SolitonsA.mcl''.  Look at the rules and
change the first rule so that you have the light turning {\em on}
instead of staying {\em off}.  Does the picture look different
now?  Describe.

\item  Run the rule ``SolitonsA.mcl''.  Look at the rules and
change the fourth rule so that you have the light turning {\em
off}\hbox{ }instead of staying {\em on}.  Does the picture look
different now?  Describe.

\item  Run the rule ``SolitonsD1.mcl''.  Look at the rules and
change the first rule so that you have the light turning {\em on}
instead of staying {\em off}.  Does the picture look different
now?  Describe.

\item  Run the rule ``SolitonsD1.mcl''.  Look at the rules and
change the fifth rule so that you have the light turning {\em off}
instead of staying {\em on}.  Does the picture look different now?
Describe.

\item  Run the rule ``Brownian motion.mcl''.  Look at the rules.
These rules can also be stated as:  If a light has both neighbors
{\em 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 {\em off}, then the light turns {\em on}.
Write down the rule in the form of a table. Run the rule and
describe the differences.

\item  Run the rule ``Brownian motion.mcl''.  Look at the rules.
These rules can also be stated as:  If a light has both neighbors
{\em 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 {\em off}, then the light turns {\em
off}. Write down the rule in the form of a table. Run the rule and
describe the differences.

\end{enumerate}

\section{The Slow Lane: Deterministic Traffic Model}\label{S:move}

%        \input{MIYCmodel}
Back in Section 1, we saw that
\begin{itemize}
\item  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.

\item An example of a cellular automata is a sequence of light
bulbs which can have one of two states {\em on} or {\em off}.
\end{itemize}

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 \cite{larry}.  There are other models of traffic out
there (see \cite{bkns}, \cite{kmk}, \cite{nwws},  \cite{rt}).

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: {\em on/off} for the light bulbs and {\em
car/no-car} for the highway example.

\begin{example}\label{E:cars}  This is an example of a possible
configuration of a highway.

\vskip0.3truein
%\epsfxsize = 4.7truein
\epsfysize = 0.7truein \centerline{\epsfbox{Images/car.eps}}
\centerline{Cars} \vspace{.2in}

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

\bigskip

\centerline{\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\rm location} &  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 &14&15\\
\hline \hline {$t=0$}  &  0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 &  1 &
1 &  1 & 0&0&0
\\
\hline
\end{tabular}}
\vspace{.2in}

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

Being infinitely long, our highway is difficult to represent.  We
will get around this by using a loop to represent the highway and
have the cars move continuously around the loop.  Thus, in the
previous example, position 15 and 1 are adjacent and the 6 cars
represented will move within the 15 positions.  MCell allows one
to specify the length of the loop - by default it is 600
positions.

\subsection{``Move if you can''}

We need to decide how our cars will move.  What goes through your
mind when you are deciding whether or not to press on the
accelerator and move ahead?  The distance between you and the next
car?  The tempo of the music on the radio?  How late you are?

There are many factors that determine your driving habits but  we
want to keep our model simple.  Therefore, we establish one rule:
\begin{itemize}
\item[]{\bf ``Move if you can'' rule:}  A car will move to the
next (to the right) location if and only if the next location is
empty (has no car in it).
\end{itemize}

Let us see what our rule implies about the cars in
Example~\ref{E:cars} above. Remember that locations 15 and 1 are
adjacent --- so using the ``Move if you can'' model, a car in cell
15 will move to cell 1 if there is no car in cell 1. Here is a
table representing the flow of traffic for time $t=0, 1, 2, 3, 4$.
Note that the car in position 15 at time $t=3$ moves to position 1
at time $t=4$.

\bigskip

\centerline{\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\rm location} &  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 &14&15\\
\hline \hline{$t=0$}  &  0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 &  1 &
1 &  1 &  0
&0&0\\
\hline{$t=1$}  &  0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 &  1 &  1 &  0 &  1 &0&0\\
\hline{$t=2$}  &  1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 &  1 &  0 &  1 &  0 &1&0\\
\hline{$t=3$}  &  0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 &  0 &  1 &  0 &  1 &0&1\\
\hline{$t=4$}  &  1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 &  1 &  0 &  1 &  0 &1&0\\
\hline
\end{tabular}}
\vspace{.2in}

Notice that Example \ref{E:miyc} is exactly the ``Move if you
can'' model applied to light bulbs.

Now we have a model of the highway set up and would like to see
what happens to cars as time proceeds.  Specifically, we are
interested in seeing if traffic flows freely or if it ``jams'' up.
We need first to define these terms.

\begin{definition}
For the ``Move if you can'' model, if $n \geq 2,$ we will define a
{\bf jam of  size $n$} to be $n$ consecutive 1's with a 0 in the
location immediately before and after the sequence of 1's.
\end{definition}

A jam will be a group of cars in adjacent locations.  In
Example~\ref{E:cars}, notice that initially there is a jam of size
2 in locations 2-3 and a jam of size 3 in locations 10-12. In the
``Move if you can'' model, the lead car in a jam will
automatically move ahead at the next time step while the other
cars in the jam remain stationary.  In the course of driving, a
specific car may be a member of many different jams. For example,
it could encounter the back end of a jam while driving along, have
to wait for the cars ahead to move out, proceed driving again only
to encounter the back of a new jam and start the process over
again.

These initial jams may have been caused by an accident, a police
officer with radar,  an animal running across the road, or many
other possible reasons. We are not interested in why the jams
occurs but in how they dissipate and if they reform.

Looking back at table above, we see that the initial jam at
locations 2-3 was gone at $t=1$ and the jam at locations 10-12 was
completely gone at $t=2.$ In fact, at $t=2$ every car has an open
space in front of it and proceeds forward at $t=3.$  This
situation where every car continues to move forward will happen at
every future time step; the cars are flowing freely from one
location to the next.  (You will be asked to explain why this
occurs in the exercises.)  This jam-free behavior will be given a
special name.

\begin{definition}\label{D:freeflow}  A configuration for the ``Move if you can''
model is said to be in {\bf free flow} if every car has an open
space in front of it at the end of a time step.
\end{definition}

%\input{MIYCMcell}

\subsection{Modeling Traffic Using MCell}

One question we have been trying to answer is, ``When do we get
jams?''  It takes SO long to do each step and this makes it
difficult to see what will happen in the long run - will a jam
occur?  Fortunately, MCell helps us with this.  We will now begin
a brief introduction to MCell and talk about some of its features.


\begin{itemize}
\item  Open up MCell.

\item  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 ``Special Rules.''

\item  Below the list of folders, there is now a list of *.mcl
files - open the one called ``Traffic CA.mcl.''

\item  Go to the `Color' menu (along the top of the screen) and
click on the `color bar'.  On the left side of the color bar
window are left/right buttons with `1/25' underneath the buttons.
Press on the left button until it reads `1/2' underneath the
buttons.  The will allow you to use 2 states - on or off, occupied
or empty.

\item Go to the `Rules' menu (along the top of the screen) and
open `Rules setup'

\item You will see the words `Accelerating', `Braking',
Congested', and `Driving'.  The numbers in the white box represent
the rules.  We will talk about their exact meaning in Section 4.

%\epsfxsize = 4.7truein
\epsfysize = 2.8truein \centerline{ \epsfbox{Images/trules.eps}}
\centerline{MCell - Traffic Rules} \vspace{0.1in}

\item  Press the ``Play'' button and see MCell run the rule!

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = .8truein \centerline{
\epsfbox{Images/playbutton.eps}} \centerline{MCell - Play button}
\vspace{0.1in}


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

\item To stop MCell from drawing, press the ``stop'' button (the
square).

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = .8truein \centerline{
\epsfbox{Images/stopbutton.eps}} \centerline{MCell - Stop button}
\vspace{0.1in}


\item  You can clear the screen and put your own initial
conditions in there.  Press the ``new screen'' button and then
click on the spots where you would like to put cars. Remember,
only put cars on the first row!  It will help immensely if you
enlarge the viewing area.

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = .8truein \centerline{\epsfbox{Images/newscreen.eps}}
\centerline{MCell - New screen button} \vspace{0.1in}

\end{itemize}

Now, the ``Rules...'' screen looks very different from the ones we
have used up to now.  The difference is due to the fact that MCell
allows the user to insert various probabilities into this model.
The probabilities relate to different possible driving methods,
and we will talk more about them in Section 4.  For now, let us
set each of the four probabilities to 1 (which is actually the
defining feature of the ``Move if you can'' model).

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 2.8truein \centerline{\epsfbox{Images/trules1.eps}}
\centerline{MCell - Traffic Rules screen with Probabilities set at
1} \vspace{0.1in}

MCell will allow us to look at MANY cars at a time, and that is
certainly helpful. Next to the play button is another play button
with a 1 next to it.  Clicking this button once will show one time
period passing.  We'll call this button the {\bf slow play
button}.  If you enlarge the viewing area many many times, you
will be able to see each distinct car.  Clicking successively will
allow you to see each car over several distinct time periods.
  This is
MUCH faster than doing it by hand!

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize =.8truein \centerline{ \epsfbox{Images/slowplay.eps}}
\centerline{MCell - Slow play button} \vspace{0.1in}

\begin{example}  Think back to Example~\ref{E:miyc}.  As we
mentioned before, the rules we used for the lights turning {\em
on} and {\em off} are the same rules for the ``Move if you can''
model.  In this example, we will use MCell to look at how the
traffic moves through multiple time periods.  Recall the initial
conditions:

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ &0&1&1&1&0&1&0&0&0&1&1&1&1&0&0&1&1&1&0&0\\ \hline
\end{tabular}}

\bigskip

Since we have only 20 locations, we will need to adjust the board
size for MCell. To do this we go to ``Settings - Board...'' and
the Board Size will be in the upper left hand corner.  Click on
``Other'' and set the board size to be 20 by 20. (Mcell forces the
size to be a square and the lengths/widths must be multiples of
20.) When we put this into MCell, we get:

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 3truein \centerline{\epsfbox{Images/miyc.eps}}
\centerline{MCell - ``Move if you can'' initial configuration}
\vspace{0.1in}

For clarity, let us reiterate a few points.  First, the black
squares in the first row of the above figure represent cars, and
the white squares represent spaces without cars.  Second, {\em
cars move from left to right}.  Third, as a car moves off of the
right side of the screen, it reappears on the left side of the
screen.

In this example, the initial configuration contains 3 distinct
``jams'' of cars.  Reading from left to right, there are jams of
size 3, 4, and 3 respectively.

\noindent Using the ``slow play'' button we  get the following
picture after 9 time periods.  Notice that the number of cars on
each line remains the same.  This is because when a car exits the
screen on the right hand side, it reappears on the left hand side
of the screen.

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 3truein \centerline{\epsfbox{Images/miyc10.eps}}
\centerline{MCell - ``Move if you can'' after 9 time periods}
\vspace{0.1in}


Look at the big picture here.  At the beginning there are three
jams, and over time they seem to (more or less) work themselves
out. Why is it that the jams themselves look like they are moving
backward? Maybe we can answer that question after looking at
another example.


\end{example}

\begin{example}\label{E:80}
In this example, we let MCell itself randomly choose the initial
configuration of cars.   To do this, simply press the ``random''
key. (Our board size is 600 by 500.)

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = .8truein \centerline{\epsfbox{Images/random.eps}}
\centerline{MCell - Random button} \vspace{0.1in}

\noindent Before setting up the initial configuration, MCell asks
us to choose the percentage of spots that will be occupied by
cars.

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 3truein \centerline{\epsfbox{Images/percent.eps}}
\centerline{MCell - How to chose a certain density} \vspace{0.1in}

\noindent  For our example, we will choose 80\% (think of this as
the first row of spots being 80\% filled with cars).  Make sure
that you have clicked the button to the left of ``Mono, one
state''.  Press the Apply and then Close buttons and the screen
will have the cars it. Now play the rule and look at the long term
behavior.

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 2.5truein \centerline{\epsfbox{Images/awhile.eps}}
\centerline{MCell - long term behavior of the rule above}
\vspace{0.1in}
\end{example}

\noindent  So what is this figure showing?  Each horizontal slice
represents one time period, and the solid black sections are the
``jams.'' Notice again that it appears the jams are moving
backwards!

To understand what is happening, let us take a smaller version of
this example and concentrate on a single jam. We make our board 20
by 20.  To do this, go to the `Settings' menu and open `Settings -
board''.  Then make the board 20 x 20.  We will begin with the
following initial conditions:

%\begin{example}
\label{E:jams}

\medskip

\centerline{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 &
1 & 1 & 1 & 1 & 1 & 0 & 0\\ \hline
\end{tabular}}

\bigskip

\noindent  We have a jam of size 8 and a jam of size 5.  As we
look what happens over time, we again see that the jams tend to
move to the left.  One way to think of why this occurs is that the
car in the front of the jam leaves because there is an empty space
ahead of it.  The rest of the jam does not move, and
 another car catches up with the jam and then becomes
part of the jam  (and thus creating a jam that is the same size as
the one during the previous time period).

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 1.5truein \centerline{\epsfbox{Images/jams.eps}}
\centerline{MCell - Traffic Jams} \vspace{0.1in}
%\end{example}


\begin{example}\label{E:freeflow}  Now that we have seen a
bit about the behavior of jams, let us consider another situation.
Again we will be using a 20 by 20 board and the ``Move if you
can'' rule.  But this time our initial configuration will have
fewer cars in it:


\bigskip

\centerline{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 &
0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline
\end{tabular}}

\bigskip

We have a jam of length 8.  As we run MCell we see that the jams
dissolves and we are in free flow.

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 3truein \centerline{\epsfbox{Images/freeflow.eps}}
\centerline{MCell - Free Flow} \vspace{0.1in}
\end{example}

What makes Example~\ref{E:jams} and \ref{E:freeflow} different is
the number of cars  in the initial configuration (the {\em
density}).   In the next section we will talk about the role on
the initial densities.

\subsection{Densities in the move-if-you-can model}

\bigskip

In the last section, we looked at the long range behavior of the
``move if you can'' model under different initial conditions.  In
Example~\ref{E:cars}, we had 15 locations and 6 cars and noticed
that no matter where the 6 cars were initially placed, eventually
all cars would be in free flow.  Then we used MCell and started
with 20 locations and 11 cars and found that again, eventually the
cars would go into free flow.  In Example~\ref{E:80} we changed
the initial number of cars so that 80\% of the locations were
filled.  Even after many iterations of MCell, traffic jams existed
at every time step.  We would like to determine how the number of
cars affects the long range behavior of the traffic pattern.
First, let us give a definition for this initial number of cars.

\begin{definition}  If $\rho \in [0,1],$ we say the initial
configuration has {\bf density $\rho$} if the percentage of
locations filled with carsin the initial configuration is $\rho.$
\end{definition}

For example, if $\rho = \frac12,$ then exactly half of the
locations will have a car assigned to it.  In
Example~\ref{E:cars}, we had 15 locations and 6 cars so $\rho =
6/15 = 40\%.$  If the density is less than or equal to
$\rho=\frac12$ (or $50\%$), the traffic will eventually be in free
flow, otherwise there will be at least one jam.


\subsection{Exercises}
\begin{enumerate}
\item  The following table was built in the Example~\ref{E:cars}.
(Recall that the right end of the table wraps back around to the
left end!)

\bigskip

\centerline{\begin{tabular}{|l||c||c|c|c|c|c|c|c|c|c|c|} \hline
{\rm location} & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline \hline {\rm state } & $t=0$ & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1
& 0 & 0 \\ \hline {\rm state } & $t=1$ & 0 & 1 & 0 & 1 & 0 & 0 & 1
& 0 & 1 & 0 \\ \hline
\end{tabular}}

\bigskip

Determine the status of the 10 locations for $t=2$ and $t=3$ in
the ``Move if you can'' model.  Determine the density of the
initial configuration.

\bigskip

\centerline{\begin{tabular}{|l||c||c|c|c|c|c|c|c|c|c|c|} \hline
{\rm location} & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline\hline {\rm state } & $t=0$ & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1
& 0 & 0 \\ \hline {\rm state } & $t=1$ & 0 & 1 & 0 & 1 & 0 & 0 & 1
& 0
& 1 & 0 \\ \hline {\rm state } & $t=2$ & & & & & & & & & & \\
\hline {\rm state } & $t=3$ & & & & & & & & & &\\ \hline
\end{tabular}}

\item Determine the status of the 10 locations for $t=1$, $t=2$
and $t=3$ in the ``Move if you can'' model.  Determine the density
of the initial configuration.

\bigskip

\centerline{\begin{tabular}{|l||c||c|c|c|c|c|c|c|c|c|c|} \hline
{\rm location} & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline {\rm state } & $t=0$ & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 &
0 \\ \hline {\rm state } & $t=1$ & & & & & & & & & & \\ \hline
{\rm state } & $t=2$ & & & & & & & & & & \\ \hline {\rm state } &
$t=3$ & & & & & & & & & &\\ \hline
\end{tabular}}


\item  Consider the following initial conditions.  Without using
MCell, fill in the rest of the table using the ``Move if you can''
Model.  Determine the density of the initial configuration.

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$t=0$ &1&1&1&1&1&1&0&0&0&0&0&0&1&1&1&0&0&1&1&0 \\
\hline \hline $t=1$ & & & & & & & & & & & & & & & & & & & &\\
\hline $t=2$ & & & & & & & & & & & & & & & & & & & &\\ \hline
$t=3$ & & & & & & & & & & & & & & & & & & & &\\ \hline $t=4$ & & &
& & & & & & & & & & & & & & & & &\\ \hline $t=5$ & & & & & & & & &
& & & & & & & & & & &\\ \hline
\end{tabular}}

\item  Consider the initial conditions from the previous model.
Using MCell, fill in the rest of the table using the ``Move if you
can'' rules. (Use a 20 by 20 board.)  Determine the density of the
initial configuration.

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$t=0$ &1&1&1&1&1&1&0&0&0&0&0&0&1&1&1&0&0&1&1&0 \\
\hline \hline $t=1$ & & & & & & & & & & & & & & & & & & & & \\
\hline $t=2$ & & & & & & & & & & & & & & & & & & & & \\ \hline
$t=3$ & & & & & & & & & & & & & & & & & & & & \\ \hline $t=4$ & &
& & & & & & & & & & & & & & & & & & \\ \hline $t=5$ & & & & & & &
& & & & & & & & & & & & & \\ \hline $t=6$ & & & & & & & & & & & &
& & & & & & & & \\ \hline $t=7$ & & & & & & & & & & & & & & & & &
& & & \\ \hline $t=8$ & & & & & & & & & & & & & & & & & & & & \\
\hline $t=9$ & & & & & & & & & & & & & & & & & & & & \\ \hline
$t=10$ & & & & & & & & & & & & & & & & & & & &\\
\hline
$t=11$ & & & & & & & & & & & & & & & & & & & & \\
\hline
$t=12$ & & & & & & & & & & & & & & & & & & & & \\
\hline
$t=13$ & & & & & & & & & & & & & & & & & & & & \\
\hline
$t=14$ & & & & & & & & & & & & & & & & & & & & \\
\hline
$t=15$ & & & & & & & & & & & & & & & & & & & & \\
\hline $t=16$ & & & & & & & & & & & & & & & & & & & & \\ \hline
$t=17$ & & & & & & & & & & & & & & & & & & & & \\ \hline $t=18$ &
& & & & & & & & & & & & & & & & & & & \\ \hline $t=19$ & & & & & &
& & & & & & & & & & & & & & \\ \hline
\end{tabular}}


\item  Consider the initial conditions from the previous model.
Using the play button, look at the long term behavior.  Write a
paragraph describing what you see.  Make sure to comment on jams
and free flow.  Is free flow ever attained?

\item  Using MCell and a 20 by 20 board, randomly place cars on
the screen with a 40\% density.  Write down your initial
configuration:

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

Will you attain free flow?  If so, how many time periods until it
occurs.

Do this 5 more times:

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}


\item  Using MCell and a 20 by 20 board, randomly place cars on
the screen with a 70\% density.  Write down your initial
configuration:

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

Will you attain free flow?  If so, how many time periods until it
occurs.

Do this 5 more times:

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\bigskip

\centerline
{\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $t=0$ & & & & & & & & & & & & & & & & & & & & \\ \hline
\end{tabular}}

\item Explain why if a system is in free flow in the ``Move if you
can'' model, then every car would move forward at the next time
step.
\bigskip

\item Explain why if a system is in free flow in the ``Move if you
can'' model, then every car would move forward at {\bf every
future} time step. (Hence the name: free flow.)
\bigskip


\item Argue that if $\rho > 50\%,$ then there must be a jam in the
initial configuration.

\item  The previous exercise implies that if $\rho > 50\%,$ then
there must be a jam at every time step.  Explain why.

\item Run MCell with various densities $\rho < 50\%$ and look at
the long term behavior.  Describe what you eventually see. Make a
conjecture about the long term behavior of the ``Move if you can''
model with $\rho < 50\%.$  Use a 40 by 40 board and remember to
use the ``shrink to fit'' button.

\item Use a table to write down all possibilities for the status
of a location and its immediate neighbors, then determine the
status of the location at the next time step using the ``Move if
you can'' model.


\end{enumerate}


\section{The Expressway:  Probabilistic Traffic Model}\label{S:prob}

%       \input{ASEPmodel}

\subsection{ Introduction}

Recall the descriptions of the three phases of traffic mentioned
at the beginning of this module.

\begin{quotation}

{\em 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.

{\em 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.

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

\end{quotation}

The model developed in the last section was certainly a simple
model of traffic flow that we were able to analyze fairly well.
However it did not demonstrate the three phases of traffic that we
wished to see.  Rather, we only got the first and third types of
traffic, free flow and persistant traffic jams.  Before we go on
and develop a more complex model, let's first discuss the three
phases a bit more.

Consider the first MCell screen shot shown below.



\vspace{0.1in}

%\epsfxsize = 4.7truein

\epsfysize = 3truein

\centerline{\epsfbox{Images/20percent5439.eps}}
\centerline{Example Free Flow} \vspace{0.1in}



This gives a more realistic example of free flow than we saw in
the ``Move if you can'' model.  Here cars move, for the most part,
independently of one another.  While traffic jams do occasionally
appear, they quickly dissipate and return to free flow.  Notice
that our definition of free flow given in
Definition~\ref{D:freeflow} does not fit this situation.  A
mathematically precise definition of free flow is quite technical
and is beyond the scope of this module \cite{larry}.



\vspace{0.1in}

%\epsfxsize = 4.7truein

\epsfysize = 3truein

\centerline{\epsfbox{Images/50percent5439.eps}} \centerline{Second
Phase of Traffic} \vspace{0.1in}



The above screen shows the second phase of traffic.  Here traffic
is moving fairly well and there are no very long traffic jams
although virtually every car spends most of its time in contact
with the cars adjacent to it.  While traffic jams do form in this
situation, they tend to eventually go away as new ones form in a
different place.



\vspace{0.1in}

%\epsfxsize = 4.7truein

\epsfysize = 3truein

\centerline{\epsfbox{Images/80percent5439.eps}} \centerline{Third
Phase of Traffic} \vspace{0.1in}



Finally, we have the third phase shown in the above screen is a
definite traffic jam. Long jams that move backwards along the road
with only brief escapes into small pieces of free flow typify this
phase.

These are the three phases of traffic flow that we would like to
model.  We will look at various attempts to do this in the next
sections.

\subsection{ A Simple Probabilistic Model}

We will attempt to improve our model by adding some randomness to
the process.  In
 Section 3, our model made the assumption that all drivers who had an opening
ahead of them moved forward immediately.  Anyone who has ever
watched a long line of cars start after being stopped at a traffic
light knows that this is certainly not the case. In this section
we will assume that there is some randomness as to whether a
person who {\em can} move ahead {\em does} by saying that any car
with a space ahead of them will move ahead with probability $p$.
Let us first consider the case where $p=\frac{1}{2}$.  In this
case we can think of each driver with a space ahead of them
flipping a coin at each time period.  If the coin comes up heads,
they move ahead one space, if it comes up tails they stay where
they are for that time period. (A more realistic model might
consider whether the driver is dialing their cell phone or
adjusting the radio, but we will stick to flipping coins.)  Now
hopefully in reality drivers move ahead more often than half of
the time there is an open place in front of them so we will have
$p$ greater than $\frac{1}{2}$. In this case, say with $p=.9$, we
can just think of flipping a coin weighted so that it comes up
heads $90 \%$ of the time and tails only $10 \%$ of the time.
Hopefully it is intuitive to the reader that in this situation the
cars would move more quickly down our infinite highway.

%\vspace{1 in}

%{\bf Exercise}  Try to simulate this model in class.  Line up a group of students as
%cars, spaced randomly on a circular grid.  Have each one with a space in front of them
%flip a coin and see if they move ahead.  Make sure the students understand the way this
%model works before moving on.

%\vspace{1 in}

MCell also does a nice job of simulating this model.  To see this,
open MCell and in the Special Rules folder open the Traffic CA
rules.  Then, under the Settings menu, open the Settings - Rules
dialog box.  In this box, change the numbers next to Accelerating,
Braking, Congested, and Driving to all be the same.  Whatever
number is placed in the boxes is the probability $p$ that a car
with a space ahead of it will move forward.  Let us look at what
happens with $p=.8$.  Recall that to set the initial seeding you
press the random key and select one of the percentages given as
the percentage of available cells to be filled.  Let's look at how
the picture changes as we go from a low density to a high density.
In the figure below we see screen shots with densities $20\%, 40
\%, 60 \%$, and $80 \%$.

\vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 2truein
\centerline{\epsfbox{Images/20mcell-8.eps}\qquad \epsfysize =
2truein\epsfbox{Images/40mcell-8.eps}} \centerline{Density 20\%
\qquad\qquad\qquad\qquad\qquad\qquad\quad Density 40\%}
\vspace{0.1in} \vspace{0.1in}
%\epsfxsize = 4.7truein
\epsfysize = 2truein
\centerline{\epsfbox{Images/60mcell-8.eps}\qquad \epsfysize =
2truein\epsfbox{Images/80mcell-8.eps}}\centerline{Density 60\%
\qquad\qquad\qquad\qquad\qquad\qquad\quad Density 80\%}
\vspace{0.1in}

While the third picture with $60 \%$ density seems to be the
``synchronized'' flow of phase 2, a longer look at this model in
motion shows that the jams eventually work themselves out.  Hence
this is just a special case of Phase 1.  In fact, a lot of
research has been done on this model and it has been proven that
synchronous flow never occurs \cite{larry}. As this model does not
exhibit the behavior we are looking for, we will move once again
to a more complex model.



\subsection{The Probabilistic Traffic CA}

In an attempt to further refine the probabilistic model of the
last section, Gray and Griffeath \cite{larry} noticed that drivers
were concerned with more than just if there was an empty space in
front of them, they were also concerned about the situation
further ahead of them and behind them. Hence they came up with
four different scenarios that a driver with an empty space
directly ahead of them can face and assigned the car a different
probability of advance for each  of the scenarios.  These
scenarios are {\em acceleration, braking, congestion,} and {\em
driving}.  Here is a table describing the four situations for a
driver in position $x$:

\bigskip

\centerline{\begin{tabular}{|c||c|c|c|c|c|} \hline {\em transition
type}&$x-1$&$x$&$x+1$&$x+2$&{\em probability of advance}\\ \hline
{\bf acceleration} &1 &1 &0& 0& $\alpha$\\ \hline {\bf braking}
&0 &1 &0 &1& $\beta$ \\ \hline {\bf congestion}   &1 &1 &0 &1&
$\gamma$ \\ \hline {\bf driving}      &0 &1 &0 &0& $\delta$ \\
\hline
\end{tabular}
}

\bigskip

Let's clarify this table a bit.  The {\em acceleration} row tells
us that if an initial situation is 1100, then in the next time
interval, the {\em second} car will advance {\em with probability}
$\alpha$.  Similarly, the {\em braking} row tells us that if an
initial situation is 0101, then in the  next time interval, the
second car will advance with probability $\beta$.

The four scenarios can be thought of in driving terms in the
following manner:
\begin{itemize}
 \item {\bf acceleration} --- In this situation, the car has reached the front of a jam and is accelerating off.
 \item {\bf braking} --- In this situation, the car is coming up behind some
congestion and needs to brake. \item {\bf congestion} --- In this
situation, the car has found an opening in the middle of some
congestion. \item {\bf driving}  --- Here the car is away from
other cars and driving on its own.
\end{itemize}

It is important to note that when $\beta$, the braking
probability, gets larger, the car is {\em less} likely to brake
--- $\beta$ is actually the probability of moving forward in a
braking situation.

This model finally seemed to be getting at what the researchers
desired. The three MCell screen shots at the beginning of this
section are pictures of MCell running this model with $(\alpha,
\beta, \gamma, \delta)$ set to $( .5,.4,.3,.9)$ with $\rho$ taking
on the values of $.2, .5,$ and $.8$ in each of the three pictures
respectively.  So Gray and Griffeath finally had a fairly simple
model that captured the aspects of traffic flow they wanted to
analyze.  Now all they had to do was analyze the model to
determine which values of the parameters gave rise to which of the
three phases.  Unfortunately, this model proved to be too complex
a task.  After all, there are five different parameters $\alpha,
\beta, \gamma, \delta,$ and $\rho$ that can all change.  Trying to
determine exactly which values of which of these parameters put
the traffic flow in which phase was a very complex task.  So they
tried to simplify the model in a way that preserved the behavior
they were looking for while at the same time made it easier to
analyze.  They achieved this by considering the special case of
{\em symmetric cruise control}.

A traffic CA is said to be in {\em cruise control} if $\delta=1$ .
This is the familiar situation of cars on the open road moving at
top speed. This is a nice assumption to have for the analysis as
it takes one bit of randomness out of the model.

We say that a traffic CA is {\em symmetric}  if $\gamma = \delta$.
This may seem like a strange assumption to make at first.  It says
that we advance in traffic as fast as we do on the open road.  It
would certainly make sense to think that drivers would be more
cautious and advance more slowly in congestion (although there are
freeways in many metropolitan areas where this behavior is
exhibited daily). This is a simplification that makes the
mathematics much easier.  The reason for this comes from
considering anti-cars.   An {\em anti-car} is simply a place in
the CA that does not contain a car (a blank space). Notice that as
cars move down our infinite highway to the right, anti-cars move
down it to the left.  In the case of a symmetric traffic CA, the
probability of a car moving to the right is the same as an
anti-car moving to the left.  Thus the behavior of cars in a
traffic CA with density $\rho$ is the same as the behavior of
anti-cars in a traffic CA with density $1- \rho$. (Assuming that
$\alpha, \beta, \gamma,$ and $\delta$ all remain the same.)  This
essentially cuts the amount of work that needs to be done in half.

Even with this simplified model, a complete analysis of traffic
behavior is not known.  As a matter of fact, as of the writing of
this module, only the behavior on the boundaries of this model,
when both $\alpha$ and $\beta$ are set to either $0$ or $1$, is
completely understood, and  some of these cases were even hard to
analyze.  We will examine how  this model behaves for several
different sets of parameters in the exercises and see that it
does, in fact, exhibit all three phases.

%\input{exercises4}
\subsection{Exercises}

\begin{enumerate}

\item \label{E:1} Recall Example~\ref{E:cars} where the initial
conditions were:

\vspace{.2in}
\centerline{\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\rm location} &  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline \hline{$t=0$}  &  0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 &  1 &
1 &  1 &  0
\\
\hline{$t=1$}  &  & & & & & & & & &  & & &  \\
\hline{$t=2$}  &  & & & & & & & & &  & & &  \\
\hline{$t=3$}  &  & & & & & & & & &  & & &  \\
\hline{$t=4$}  &  & & & & & & & & &  & & &  \\
\hline{$t=5$}  &  & & & & & & & & &  & & &  \\
\hline{$t=6$}  &  & & & & & & & & &  & & &  \\
\hline
\end{tabular}}
\vspace{.2in}

Complete the table using the simple probabilistic model which
allows a car to move forward if there is room, with probability
$\frac12$.  Use a coin to determine if the car will move ahead.

\item Let $\rho = 0.75$ and assume an initial configuration

\bigskip

\centerline{\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|} \hline {\rm
location} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
{$t=0$} & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 &  0 \\ \hline {$t=1$}
& & & & & & & & & &\\ \hline  {$t=2$} & & & & & & & & & &\\ \hline
{$t=3$} & & & & & & & & & &\\ \hline
\end{tabular}}

\bigskip
Let the probability that a car moves ahead to an open stop be
0.75.  To determine if a car moves ahead to a vacant location,
flip two fair coins and move if you get at least one head (the
probability of getting at least 1 head is $0.75$ with two fair
coins).   Fill in the table above.

\item \label{E:2} Recall Example~\ref{E:cars} where the initial
conditions were:

\bigskip

\centerline{\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\rm location} &  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline \hline{$t=0$}  &  0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 &  1 &
1 &  1 &  0
\\
\hline{$t=1$}  &  & & & & & & & & &  & & &  \\
\hline{$t=2$}  &  & & & & & & & & &  & & &  \\
\hline{$t=3$}  &  & & & & & & & & &  & & &  \\
\hline{$t=4$}  &  & & & & & & & & &  & & &  \\
\hline{$t=5$}  &  & & & & & & & & &  & & &  \\
\hline{$t=6$}  &  & & & & & & & & &  & & &  \\
\hline
\end{tabular}}
\vspace{.2in}

Complete the table using the simple probabilistic model which
allows a car to move forward if there is room, with probability
$\frac16$. Have the car move ahead if a 1 is rolled on a die and
there is room. Otherwise the car will stay put.

\item In the ``Move if you can'' model, the initial configuration
in Exercises~\ref{E:1} and \ref{E:2} resulted in free flow after 2
time steps (see Example~\ref{E:cars}).  In paragraph form,
describe your results from Exercises~\ref{E:1} and \ref{E:2}.  How
does the probability change the outcome?  Is there free flow?  If
so, after how many time periods?

\item Let's consider the Symmetric Cruise Control model with
$\alpha=.6$ and $\beta = .6$.  To set the model up this way in
MCell, we need to open Mcell and then in the 'Rules' menu at the
top open the 'Rules setup' dialog box.  In this dialog box,
$\alpha$ is the number next to Accelerating and $\beta$ is the
number next to Braking.  Recall that since this is the symmetric
cruise control, both $\gamma$ and $\delta$, the numbers next to
Congestion and Driving, should be set to $1$.  Set these numbers
and click the OK button.
    \begin{enumerate}
    \item Run this model with initial densities set to $ 30 \%, 50 \%,$ and $70 \%$.
Describe what you see in each case and determine which of the
three phases is represented.

    \item  Now look at initial densities $40 \%$ and $60 \%$.  What do you see
    here?
Be sure to let the model run for a while so you are viewing the
long term behavior.
    \end{enumerate}

\item  Now let's look at the Symmetric Cruise Control model with
$\alpha = .2$ and $\beta =.6$
    \begin{enumerate}
    \item  Before we begin, think about what this set of parameters has changed about our driver's
driving habits.  How should this model differ from the one in the
previous exercise?

    \item Now set up MCell to run this rule and run it with density $40 \%$.  Describe what you
see.  How does this differ from what we saw in the last exercise?
Once again, make sure to let the model run for a while before
making your observations.
    \end{enumerate}
\end{enumerate}


\section{Concluding Remarks}
%        \input{conclusion}

Automobile traffic affects almost everyone. As the number of cars
on public roads increases, learning more about the nature of
traffic becomes even more beneficial.  The models discussed in
this module are attempts to describe traffic patterns
mathematically.

The ``Move if you can'' model was straightforward
--- any car that had an open space in front of
it would move into that space.  In this model the traffic pattern
evolved into a freely moving state --- as long as there were not
too many cars on the road.  If the road was more than 50\% covered
with cars, though, then jams were always present.

In Section 4 we increased the complexity of the model a bit by
incorporating some randomness.  First we fixed it so that a car
would move into an open
 space ahead of it with probability
$p$.  This variation produced both Phase 1 and Phase 3 traffic
flows.  We then increased the model's complexity once more by
assigning probabilities to the four possible actions of a car on
the road: acceleration, braking, moving in congestion, and
driving.  This model finally did show all three phases of traffic
flow.

These models, and other similar ones, have helped researchers to
learn about traffic patterns. By varying probabilities and initial
road conditions, the researchers have shown that ``phantom traffic
jams'' can just appear out of nowhere --- even if all drivers are
driving similarly to one another. It is interesting to note that
the models described here started simple and gradually got more
complex. This is typical of mathematical modeling --- the more you
would like to learn about a phenomenon, the more complex the model
needs to be.

What else can be learned about traffic?  Is there something that
can be done to reduce the number of traffic jams?  Is there a way
to make the roads safer for drivers?  These questions may be very
difficult, and solving them just may require us to develop better
models.

%\section{Notation and Definitions}\label{S:ND}

%       \input{defs}



\addcontentsline{toc}{section}{\numberline{}References}
\bibliographystyle{amsplain}
\bibliography{referen}

\end{document}
