Discrete Math


Simulating when a Green Light turns Red

January 9th, 2010

In a previous post, I talked about the Stochastic Traffic Cellular Automaton. I am finally going to post some simulations of this method. If you want to see the code, please leave a comment.

In this simulation, I will be modeling the traffic flow of an intersection when a green light turns red. From personal experience, you know that traffic will slowly get backed-up behind the red light. This can be described as a shock wave.

In Chapter 5 in Mark Holmes book “Introduction to the Foundations of Applied Mathematics”, he sets-up the exact same problem. If you want more details on the problem, you can download the chapter for free on his website.

In my simulation, I have discretized the road into 1000 segments and evenly distribute 250 cars as the initial data. I then set the max speed M to 2 and the probability to slow-down p to .25.

The following picture shows you how the simulation ran. Each row (left to right) represents the entire road where the black spots represent cars. As you move down, you will see how the road changed for each time-step. It might take you some time to make sense of the picture.

As you can see, the traffic on the right hand side starts to pile-up more and more as time goes on. This can be easily seen by the following movie.

The top plot shows the simulation for the Stochastic Traffic Cellular Automaton model. The plot below it shows the exact solution to the continuous Lighthill-Whitham PDE Model which I described in my poster presentation. As you can see, the two models behave very similarly.

Lastly, I ran the simulation 10,000 times. After running the simulations, I calculated the probability that a car exists in a particular road segment. This created a traffic density curve similar to the Lighthill-Whitham model which is shown in the following video.

Comments(0) - Discrete Math

Stochastic Traffic Cellular Automaton

November 17th, 2009

Lately, I have started to study Traffic Flow Models. This post will hopefully be a start of a long series of posts regarding the field. Typically, there are two types of approaches when modeling traffic flow. The first approach is to treat traffic as a fluid. In this model, the behavior of individual cars are not directly modeled. Instead of modeling cars, this approach models the behavior of traffic density using Constitutive Laws. The second approach attempts to model traffic flow using a Cellular Automaton. The basic idea is that the driver’s behavior only depends on the car(s) immediately in-front and behind him. In this post, I am going to construct a simple model to describe this later approach.

First, let us divide the road into equal segments of length \Delta x and divide time likewise into equal time-steps \Delta t. The road would look something like this:

At any given timestep, a car can only occupy one grid space. This space is represented by the integer x. After each time-step, we will move the car according to it’s current velocity. We will define the integer m as the number of steps that the car will take at each time-step. Hence, the new car position will follow the iterative formula x_{new} = x_{old} + m_{new}. In order to understand Stochastic Traffic Cellular Automaton, we will also have to define two more variables. The first is g which the number of steps between the car and the car in-front of it. The second variable is M which corresponds to the max distance that any car can move on a time-step.

The Stochastic Traffic Cellular Automaton model will then follow the following steps for each car on the road for each time-step:

Speed-up: If m_{old} \neq M , then m_{new} = m_{old} + 1
Do not Overrun: If m_{new} > g_{old} , then m_{new} = g_{old}
Randomization: If m_{new} \neq 0 , then with probability p take m_{new} = m_{new}-1 .
Move Car: x_{new} = x_{old} +m_{new} .

Without any traffic, a driver would speed up to a velocity of \frac{M}{\Delta t} with an acceleration of \frac{1}{\Delta t^2}. If there is a car in front, it makes sure that it doesn’t crash into the car (which is usually a good idea). Lastly, there is a random factor placed into the equation. This is to make the model non-deterministic. For example, a driver could over-brake or do other non-deterministic behaviors. The randomization is created to encapsulate all these possible behaviors. As you can see, the model is very basic. However, we can add further rules if we want a more accurate description of a driver.

If you want to try coding this up, I would try simulating traffic behind a red light. What happens when the light turns green?

Holmes, Mark, Introduction to the Foundations of Applied Mathematics, Chapter 5
K. Nagel and M. Schreckenberg, J. Physique I, 2, 2221 (1992), A cellular automaton model for freeway traffic

Comments(1) - Discrete Math