Nagel-Schreckenberg model
Encyclopedia
The Nagel-Schreckenberg model is a theoretical model
for the simulation
of freeway traffic. The model was developed in the early 90s
by the German
physicist
s Kai Nagel and Michael Schreckenberg. It is essentially a simple cellular automaton
model for road traffic flow
that can reproduce traffic jams, i.e., show a slow down in average car speed when the road is crowded (high density of cars). The model shows how traffic jams can be thought of as an emergent or collective phenomenon due to interactions between cars on the road, when the density of cars is high and so cars are close to each on average.
). Each cell is either empty road or contains a single car, i.e., no more than one car can occupy a cell at any time. Each car is assigned a velocity which is an integer between 0 and a maximum velocity (= 5 in Nagel and Schreckenberg's original work).
Time is discretised into time steps. This discretization in both space and time results in a cellular automaton. You can think of a cell as being a few car lengths long and the maximum velocity as being the speed limit on the road. The time step is then the time taken for a car at the speed limit to travel around 10 car lengths. However, the model can also be thought as just a way to understand or to model features of traffic jams by showing how interactions between nearby cars cause the cars to slow down. In each time step, the procedure is as follows.
In each step, the following four actions are conducted in order from first to last, and all are applied to all cars. In each action the updates are applied to all cars in parallel.
These four actions are repeated many times, as long as is required to study an traffic jams that may form. The model is an example of an cellular automaton
. The model is for a single lane where cars cannot pass each other; there is no overtaking.
To the right is the result of an example simulation run of the Nagel-Schreckenberg model, with maximum velocity 5, density of cars 0.35 and probability of deceleration p = 0.3. It is a road of 100 cells. Cars are shown as black dots, and so, for example, if the road had a single car on it the plot would be white except for a single black line of slope - 1/5 (maximum velocity = 5). The lines have slopes that are steeper, indicating that jamming is slowing the cars down. Small traffic jams show up as dark bands, i.e., groups of cars that are nose-to-tail and moving slowly to the right. The rippling of the bands is due to the randomization step.
So, the Nagel-Schreckenberg model includes the effect of cars getting in each other's way and so slowing each other down. The average velocity at this density is a little over 1, while at low density it is a little less than the maximum velocity of 5. It also shows that this is a collective phenomenon in which cars bunch up into traffic jams. When jamming occurs the distribution of cars along the road becomes highly non-uniform.
, i.e., the cars always move in a set pattern once the original state of the road is set. With randomization this is not the case, as it is on a real road with human drivers. Randomization has the effect of rounding off an otherwise sharp transition. Just below this transition, one car braking due to a random slow can slow down the cars behind, spontaneously creating a jam. This feature of one car braking at random and causing a jam is absent in a deterministic model.
Computer simulation
A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...
for the simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
of freeway traffic. The model was developed in the early 90s
1990s
File:1990s decade montage.png|From left, clockwise: The Hubble Space Telescope floats in space after it was taken up in 1990; American F-16s and F-15s fly over burning oil fields and the USA Lexie in Operation Desert Storm, also known as the 1991 Gulf War; The signing of the Oslo Accords on...
by the German
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
physicist
Physicist
A physicist is a scientist who studies or practices physics. Physicists study a wide range of physical phenomena in many branches of physics spanning all length scales: from sub-atomic particles of which all ordinary matter is made to the behavior of the material Universe as a whole...
s Kai Nagel and Michael Schreckenberg. It is essentially a simple cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
model for road traffic flow
Traffic flow
Traffic flow, in mathematics and civil engineering, is the study of interactions between vehicles, drivers, and infrastructure , with the aim of understanding and developing an optimal road network with efficient movement of traffic and minimal traffic congestion problems.-History:Attempts to...
that can reproduce traffic jams, i.e., show a slow down in average car speed when the road is crowded (high density of cars). The model shows how traffic jams can be thought of as an emergent or collective phenomenon due to interactions between cars on the road, when the density of cars is high and so cars are close to each on average.
Outline of the model
In the Nagel-Schreckenberg model, a road is divided into cells. In the original model, these cells are aligned in a single row whose ends are connected so that all cells make up a circle (this is an example of what are called periodic boundary conditionsPeriodic boundary conditions
In mathematical models and computer simulations, periodic boundary conditions are a set of boundary conditions that are often used to simulate a large system by modelling a small part that is far from its edge...
). Each cell is either empty road or contains a single car, i.e., no more than one car can occupy a cell at any time. Each car is assigned a velocity which is an integer between 0 and a maximum velocity (= 5 in Nagel and Schreckenberg's original work).
Time is discretised into time steps. This discretization in both space and time results in a cellular automaton. You can think of a cell as being a few car lengths long and the maximum velocity as being the speed limit on the road. The time step is then the time taken for a car at the speed limit to travel around 10 car lengths. However, the model can also be thought as just a way to understand or to model features of traffic jams by showing how interactions between nearby cars cause the cars to slow down. In each time step, the procedure is as follows.
In each step, the following four actions are conducted in order from first to last, and all are applied to all cars. In each action the updates are applied to all cars in parallel.
- Acceleration: All cars not at the maximum velocity have their velocity increased by one unit. For example, if the velocity is 4 it is increased to 5.
- Slowing down: All cars are checked to see if the distance between it and the car in front (in units of cells) is smaller than its current velocity (which has units of cells per time step). If the distance is smaller than the velocity, the velocity is reduced to the number of empty cells in front of the car - to avoid a collision. For example, if the velocity of a car is now 5, but there are only 3 free cells in front of it, with the fourth cell occupied by another car, the car velocity is reduced to 3.
- Randomization: The speed of all cars that have a velocity of at least 1, is now reduced by one unit with a probability of p. For example, if p = 0.5, then if the velocity is 4, it is reduced to 3 50% of the time.
- Car motion: Finally, all cars are moved forward the number of cells equal to their velocity. For example, if the velocity is 3, the car is moved forward 3 cells.
These four actions are repeated many times, as long as is required to study an traffic jams that may form. The model is an example of an cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
. The model is for a single lane where cars cannot pass each other; there is no overtaking.
Example simulation in the state with traffic jams
Above and to the right is a plot of the average velocity as a function of the density of cars, obtained from a simulation of the original Nagel-Schreckenberg model. In the deterministic limit, p = 0, the velocity is constant at the maximum velocity (here 5) up to a density ρ = 1/(maximum velocity+1) = 1 / 6 = 0.167, at which point there is a discontinuity in the slope due to the sudden appearance of traffic jams. Then as the density increases further the average velocity decreases until it reaches zero when the road is 100% occupied. When p = 0.3, and so there are random decreases in velocity, then at low densities the average velocity is of course slower. However, note p > 0 also shifts the density at which jams appear to lower densities - traffic jams appear at the knee in the curve which for p = 0.3 is close to 0.15, and the random decelerations round off the discontinuity in the slope found for p = 0 at the onset of traffic jams.To the right is the result of an example simulation run of the Nagel-Schreckenberg model, with maximum velocity 5, density of cars 0.35 and probability of deceleration p = 0.3. It is a road of 100 cells. Cars are shown as black dots, and so, for example, if the road had a single car on it the plot would be white except for a single black line of slope - 1/5 (maximum velocity = 5). The lines have slopes that are steeper, indicating that jamming is slowing the cars down. Small traffic jams show up as dark bands, i.e., groups of cars that are nose-to-tail and moving slowly to the right. The rippling of the bands is due to the randomization step.
So, the Nagel-Schreckenberg model includes the effect of cars getting in each other's way and so slowing each other down. The average velocity at this density is a little over 1, while at low density it is a little less than the maximum velocity of 5. It also shows that this is a collective phenomenon in which cars bunch up into traffic jams. When jamming occurs the distribution of cars along the road becomes highly non-uniform.
Role of randomization
Without the randomization step (third action) the model is a deterministic algorithmDeterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
, i.e., the cars always move in a set pattern once the original state of the road is set. With randomization this is not the case, as it is on a real road with human drivers. Randomization has the effect of rounding off an otherwise sharp transition. Just below this transition, one car braking due to a random slow can slow down the cars behind, spontaneously creating a jam. This feature of one car braking at random and causing a jam is absent in a deterministic model.
Model Properties
- The model explains how traffic congestions can emerge without external influences, just because of crowding on a road.
- It was shown that variants of the Nagel-Schreckenberg model deliver (with a tolerance in the range of jam spacing) precisely the same results for vehicle trajectories as kinematic wave models and linear vehicle-following models.
- To reach a realistic model of congestion on freeways, the probability of slowing down in the third step of the model has to be higher for starting (after being forced to stop due to traffic congestion) than for all other cases.
- For a maximum speed of one (instead of five) and a probability of random slowing down, the model equals cellular automaton 184Rule 184Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:...
by Stephen WolframStephen WolframStephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
. - The model is minimalist, i.e. that the exclusion of any element of the model’s definition will immediately cause loss of crucial properties of traffic.
- A simulation of millions of vehicles with the Nagel-Schreckenberg model is possible with parallel working computersParallel computingParallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
.
Application
- The Nagel-Schreckenberg model was further developed during Nagel's research stay at the Los Alamos National LaboratoryLos Alamos National LaboratoryLos Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...
for parallel computing. The transportation forecastingTransportation forecastingTransportation forecasting is the process of estimating the number of vehicles or people that will use a specific transportation facility in the future. For instance, a forecast may estimate the number of vehicles on a planned road or bridge, the ridership on a railway line, the number of...
model TransimsTransimsTRANSIMS , is an integrated set of tools developed to conduct regional transportation system analyses...
is based on this work. - In the German stateStates of GermanyGermany is made up of sixteen which are partly sovereign constituent states of the Federal Republic of Germany. Land literally translates as "country", and constitutionally speaking, they are constituent countries...
(bundesland) of North Rhine-WestphaliaNorth Rhine-WestphaliaNorth Rhine-Westphalia is the most populous state of Germany, with four of the country's ten largest cities. The state was formed in 1946 as a merger of the northern Rhineland and Westphalia, both formerly part of Prussia. Its capital is Düsseldorf. The state is currently run by a coalition of the...
the Nagel-Schreckenberg model has been used as the foundation for a comprehensive traffic forecasting system which is accessibile online.
External links
- Link to the pdf of the original 1992 J. Phys I France paper of Nagel and Schreckenberg: http://www.ptt.uni-duisburg.de/fileadmin/docs/paper/1992/origca.pdf (PDF, 1038 KB)
- North Rhine-Westphalia's OLSIM traffic forecasting system http://www.autobahn.nrw.de (German)