# Presentation: 568745

## Highway Car Traffic as a Complex System

**Highway Car Traffic as a Complex System**
**The Physicist’s Point of view**

## What is a complex system?

- (New York: Springer-Verlag 2004)

- it consists of a large number of interacting agents,
- it exhibits emergence, that is, a self-organizing collective behavior difficult to anticipate from the knowledge of agents behavior,
- its emergent behavior does not result from the existence of a central controller.

- Example: Project inspired by the behavior of termites gathering wood chips into piles.http://education.mit.edu/starlogo/

- Randomly distributed wood chips (left figure) eventually end up in a single pile (right figure).  Density of wood: 0.25, number of termites: 75.

## First model: K. Nagel and M. Schreckenberg:                    A Cellular Automaton Model for Freeway Traffic,        Journal de Physique I 2 2221-2229 (1992)
Review: D. Chowdhury, L. Santen, and A. Schadschneider,                                                                   Statistical Physics of VehicularTraffic and Some Related Systems,                                                                             Physics Reports 329 199-329 (2000)

- Review: D. Chowdhury, L. Santen, and A. Schadschneider,                                                                   *Statistical Physics of VehicularTraffic and Some Related Systems,   *                                                                          Physics Reports **329** 199-329 (2000)

- Cellular Automaton Models of
- Highway Traffic Flow

## What is a model?

- A model is a simplified mathematical representation of a system.
- In the actual system many features are likely to be important.
- Not all of them, however, should be included in the model.
- Only a few relevant features which are thought to play an essential role in the interpretation of the observed phenomena should be retained.
- A simple model, if it captures the key elements of a complex system, may elicit highly relevant questions.

## Simplest model:A one-lane highway traffic flow

- free-moving phase

- jammed phase

- critical state

- At each time step a car (a blue square) either moves to the neighboring right cell if, and only if, it is empty (a yellow square) or does not move.
- Each figure represents 30 time steps for different car densities.

- A linear array of cells either occupied (by a car) or empty

## The existence of two phases: a free-moving phase for a car density less than a critical value and a jammed phase for a  car density greater than this critical value.
Local jams (sequence of stopped cars) are moving backwards.

- The existence of two phases: a free-moving phase for a car density less than a critical value and a jammed phase for a  car density greater than this critical value.
- Local jams (sequence of stopped cars) are moving backwards.

- This very simple model shows:

- A cellular automaton is a dynamical system

## The previous model is a simplified deterministic version of the Nagel-Schreckenberg model. It assumes that 1- car speeds can only take two values: 0 or 1,  and 2- car drivers always move if they can

- If we assume that car speeds take the values

- and adopt the moving rule: a car occupying cell i and having d empty cells on its right moves, at the next time step, to cell

- A slightly more general model

## free-moving phase

- jammed phase

- yellow: empty cell,  red: speed 0, blue: speed 1, green: speed 2
-             color code at time t indicates speed at time t-1

- critical density given by:

- Deterministic cellular automaton models of highway traffic flow obey a variational principle which states that, for a given car density, the average car speed is a non-decreasing function of time.
- N. Boccara, *On the existence of a variational  principle for deterministic cellular automaton* *models of highway  traffic flow*,
- International Journal of Modern Physics C **12 **1-16 (2001)

## A phase space S whose elements represent possible states of the system;
 time t, which may be discrete or continuous;
and an evolution law, that is, a rule thatallows to determine the state at time t from the knowledge of the states at all previous times.

-  time t, which may be discrete or continuous;
- and an evolution law, that is, a rule thatallows to determine the state at time t from the knowledge of the states at all previous times.

- What is a dynamical system?

- The notion of dynamical system includes the following ingredients:

## Two examples of dynamical systems:

- 1- Bulgarian solitaire

- For instance, if N=10 (which corresponds to n=4), starting from the partition  {1,2,7}, we obtain the following sequence:
-                                    {1,3,6}, {2,3,5}, {1,2,3,4}.

- A pack of N = n (n+1)/2 cards is divided into k packs of

- cards, where

- A move consists in taking exactly one card of each pack and forming a new pack.

- By repeating this operation a sufficiently large number of times any initial configuration eventually converges to a configuration that consists of n packs of, respectively,
- 1, 2, . . ., n  cards.

## Numbers N of the form n(n+1)/2 are known as triangular numbers. 

- What happens if the number of cards is not triangular?
- Since the number of partitions of a finite integer is finite, any initial partition leads into a cycle of partitions. For example, if N=8, starting from {8}, we obtain the sequence:
- {7, 1}, {6, 2}, {5, 2, 1}, {4, 3, 1 }, {3, 3, 2}, {3, 2, 2, 1}, {4,2,1,1}, {4,3,1}.
- For any positive integer N, the convergence towards a cycle, which is of length 1 if N is triangular, has been proved by J. Brandt,  *Cycles of Partitions*, Proceedings of the American Mathematical Society **85** 483--487 (1982).
- In the case of a triangular number, it has been shown that the number of moves, before the final configuration is reached, is at most equal to n(n-1).
- The Bulgarian solitaire is a time-discrete dynamical system.  Its phase space consists of all the partitions of the number N.

## 2- Original Collatz problem

- Many iteration problems are simple to state but often intractably hard to solve. Probably the most famous one is the so-called 3x+1 problem, also known as the Collatz conjecture,which asserts that, starting from any positive integer n, repeated iteration of the function f defined by

- always returns 1.

## Its inverse is defined by

- The function f is bijective and is, therefore, a permutation of the natural numbers. The study of the iterates of f has been called the original Collatz problem
- (see L. C. Lagarias,  *The 3x+1 Problem and Its Generalizations*,
- American Mathematical Monthly  **92** 3-23 (1985))

- Here is a less known conjecture that, like the 3x+1 problem, has not been solved.
- Consider the function f defined, for all positive integers, by

## If we consider the first natural numbers, we obtain the

- following permutation:
- 1  2  3  4  5  6  7  8  9
- 1  3  2  5  7  4  9  11  6
- While some cycles are finite, e.g., (3,2,3)
- or (5,7,9,6,4,5), it has been conjectured that there exist
- infinite cycles. For instance, none of the 250,000 successive
- iterates of 8 is equal to 8. This is also the case for 14 and 16.
- For this particular dynamical system, the phase space is the set
- of all positive integers, and the evolution rule is reversible.

## What is a 1D cellular automaton?

- the local evolution rule is a map

- such that

- are, respectively, the left and right radii of rule f.

- where

## Critical behavior of a cellular automaton highway traffic model 

- In the deterministic Nagel-Schreckenberg model the transition from the free-moving phase to the jammed phase may be viewed as second-order phase transition

- 1- What is the order parameter?
- 2- What is the symmetry-breaking field?
- 3- What is the physical quantity characterizing the linear response of       the order parameter to the symmetry-breaking field?
- 4- What are the critical exponents?
- 5- Can we find scaling relations?

- N. Boccara and H. Fukś,
*Critical Behavior  of a Cellular Automaton Highway Traffic Model *,
- Journal of Physics A: Mathematical and General **33** 3407-3415 (2000)

## Symmetry considerations

- In a standard second-order phase transition, at high temperature, the system is in the disordered phase, i.e., the phase of higher symmetry.
- Below a critical temperature, the system is in the ordered phase characterized by a nonzero value of a symmetry-breaking order parameter.
- The symmetry group of the ordered phase is a subgroup of the symmetry group of the disordered phase.

## For the transition from the free-moving phase to the jammed phase, the control parameter is the car density.

- The average car velocity is exactly given by:

- This expression shows that below the critical car density:

- all cars move at the maximum velocity, while above the critical density, the average velocity is less than the maximum speed.

## (e, e, 2)

- N. Boccara and H. Fukś,
*Number-conserving  Cellular Automaton Rules* ,
- Fundamenta Informaticae  **52  **1-13 (2002)

- Limit sets of number-conserving cellular automaton rules have, in most cases, a very simple structure, and are reached after a number of time steps of the order of the lattice size.

- Below the critical density
- any configuration in the limit set consists of “perfect tiles” as shown below:

- in a sea of cells in state (e)

## (e)

- a configuration in the limit set consists of a mixture of tiles containing  cells of type:

- (0)

- (e,1)

- (e,e,2)

- Tiles of type  (0) and  (e,1) found in the limit set of the jammed phase are called defective

## If in the deterministic model we introduce random braking, then, even at low density, some tiles become defective which causes the average velocity to be less than the maximum speed

- maximum speed: 2
- car density: 0.2
- braking probability: 0.25

- random braking means that a driver who could move at velocity v has a probability p to move at velocity v-1

## The random braking parameter p can, therefore, be viewed as the symmetry-breaking field, and the order parameter m, conjugate to that field, is

- since

- we obtain

## Critical exponents

- For this particular system, in the vicinity of the transition point, the asymptotic behavior is characterized by the  exponents β, γ, γ’, and δ defined by

- Close to the critical point, critical exponents satisfy scaling relations. If we assume that m is a generalized homogeneous function of p and ρ-ρc ,   that is,

- then

- β is exactly equal to 1

## Numerical simulations

- Divergence of ∂m/∂p  at the critical point

- Log-Log plot of (m(p)-m(0))/p as a function of |ρ-ρc|  for ρ<ρc

- Log-Log plot of (m(p)-m(0))/p as a function of |ρ-ρc|  for ρ>ρc

## Log-Log plot of m as a function of p for ρ=ρc

- Log-Log plot of m as a function of p for ρ=ρc

- Numerical simulations show that

- γ ≃ γ’ ≃ 1  and  δ  ≃  2

- These critical exponents satisfy the
-       scaling relation   γ = (δ-1)β

## These results can also be  obtained using an approximate technique, called local structure theory, at order 3 going beyond the mean-field approximation (order 0).

- H. A. Gutowitz H. A.,  J. D. Victor J. D., and B. W. Knight
*Local Structure Theory for CellularAutomata*,
- Physica D 28 18--48 (1987)

## THE END