[ Welcome to NKS - SJSU ]

                   

 Traffic Flow with Cellular Automata

Henry Jiang

 

Home | Links | Applets | Papers | Class Plan | Participants

 

 

 

  Traffic Flow with Cellular Automata                  

 

                                Table of Content

Abstract: 2

Introduction: 2

NS Model: 2

FI Model: 3

The Basic Model: 3

Vehicle Movement: 3

Benyoussef’s Simulation: 4

Vmax = 1: 4

Vmax = 2: 5

The Two-Lane Model: 6

Traditional Lane Changing Rules: 7

NS Lane Changing Rules: 7

The Simulation: 8

Additional Reality-check Rules: 9

Result and Discussion: 11

One Lane Model: 11

Two Lane Model: 12

Reference: 12

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Abstract:

Cellular automata has been recently use in many scientific calculations and simulations.

In this paper, we will discover how cellular automata can be applied to traffic flow simulations. The cellular automata simulation is driven according to a set of local rules, which are defined as the local relationships between itself (the center cell) and the neighboring cells.

 

 

Introduction:

Traffic problem is a major problem in most of the major cities in the United States, as well as other major cities around the world. The need to accurately and realistically predict traffic flow is expanding. There has been recently much of interest in studying traffic flow with Cellular Automata models. Why CAs? CA models are conceptually simple, thus we can use a set of simple CA rules to produce complex behavior.  Through the use of powerful computers, these models can encapsulate the complexity of the real

world traffic behavior and produces clear physical patterns that are similar to those we see in everyday life. For example, CA models show the shifting from moving traffic to jamming traffic. 

 

NS Model:

The basic one-dimensional Cellular Automata model for highway traffic flow is the CA rule 1841. Cay Horstmann2, a professor at SJSU wrote an interesting Java Applet to simulate traffic flow with a 1-D CA based on Kai Nagel and Michael Schreckenberg3 (NS) rules. The NS model is a variation of rule 184, which is one of the elementary CA rules investigated by Wolfram. The model describes a one-lane traffic road with sequence of grid points, and each grid point is a square representing one vehicle.  There are many variations on the basic model. The NS model considered the effects of acceleration and delay of vehicles with high speed. The actual speed of the car at each time step depends on the “lambda” value that can be adjusted accordingly.  This model captures the realistic traffic situations where the car accelerates and decelerates.

 

FI Model:

Fukui and Ishibashi (FI)4 introduced yet another variation on the basic 1 D CA model, which generalizes the cellular automata rule 184. The FI models considered that cars could move by at most vmax sites in one time step if cars in front do not block them. More precisely, if the number of empty sites in front of a car is larger than vmax at time, then it can move forward at most vmax sites in the next time step with probability (1 inv f). Here, the probability f represents the degree of stochastic delay. The FI model differs from the NS model in that the increase in speed is instantaneous, and depends on vmax.  In general, the stochastic delay only applies to slower car since they do not slow down for the reason that they are already slow. The two models are identical for vmax = 1, vmax = 1 basically means the vehicles can only move 0 or 1 sites at each time step.

 

These simple models have been shown to reproduce at least qualitatively the features of real traffic flow. As we have seen in the above models, the basic idea is to formulate a model in space and time. The space in this case is the road divided into grid points or cells that may be empty or occupied by exactly one vehicle.

 

 

 

The Basic Model:

The FI4, a variation of the basic model, differs from the NS5 in that the increase in speed may not be gradual and stochastic delay only applies to high-speed cars. Therefore, the definition of Space Gap here only applies to the FI model. In the FI model, the vehicles can advance by at most M sites each time step if they are not block by vehicles in front. If M = 1, then the FI and NS is identical. Therefore we will be referring to the FI model from now on.

Vehicle Movement:

The model contains three parameters: the maximum speed Vmax which is same for all the vehicles, the probability of cars arriving onto the road, and the probability of some cars on the road slowing down. The following paragraphs will explain how the vehicles move according to the rules.

Defined Space Gap as “the distance between successive vehicles in the traffic lane measured from a common reference point on the vehicles, in the case, any parts from the vehicle can be use as a reference point.”  The optimal space gap is therefore the smallest gap between two vehicles without causing an accident. If all the vehicles maintain the optimal space gap, then the density of the road is maximized.  As one suspects, the space gap has a direct relationship with the speed of the vehicles.

This model considered the fact that not all drivers adhere to the legal speed limit, and therefore a fraction of the vehicles accelerates. Similarly, some drivers may choose to decelerate without a reasonable cause. Combining the two factors, we can develop a relationship between accelerating, decelerating, and maintaining constant speed.

· Pkeep - Probability of maintaining speed

· Pacc - Probability of increasing speed/accelerating

· Pbreak - Probability of decreasing speed/decelerating

A random number Î[0,1] is used to decide whether a vehicle will decelerate to the legal speed, maintain constant speed, or accelerate to the maximum speed (maximum speed is user-defined). The user may specify the probabilities of accelerating and decelerating and maintain constant, however, these probabilities should add up to 1. At each time step of the simulation, a random number is generated for each of the probability as follows:  

            If  random number x < Pkeep , keep constant speed at current time step.

            Else if x < Pbreak, vehicle should break.

            Else vehicle should accelerate.

The probability of decelerating deserves some explanation since breaking is totally legitimate in certain situations. The drivers who are driving with unsafe space gap may choose to break to achieve optimal space gap.

Benyoussef’s Simulation:

The average occupation of each cell (vehicles on the lane), the average velocity and the flow of vehicles are all depended on the space gap mentioned above. Benyoussef4 discussed the time evolution of these dependants using the time evolution of the dynamical equations with the mean field approximation (MFA) and using numerical simulations. Benyoussef’s simulation setup is basically the same as Hortsmann’s applet simulation where during each updating procedure, the new cars positions do not influence the rest and only previous positions have to be taken into account. Benyoussef’s simulation obtains the average occupation, average velocity, and the flow by averaging the velocities and currents over 21 cells.

 

Vmax = 1:

The simulation studies Vmax = 1 and Vmax = 2.  In the case of Vmax = 1, the simulation takes a different turn from the traditional simulation methods. Instead of using density as “order parameter” [4, pg. 6], it uses the average velocity calculated above to determine three phases of traffic flow: traffic jamming phase, moving phase, and maximal flow phase. The moving phase corresponds to low vehicle density while the jamming phase refers to high vehicle density.  The three phases exhibit two transitions; the first order transition is formed by the moving phase to the jamming phase and vice versa; the second order transition is formed from the moving or jamming phase to the maximal flow phase and vice versa. If the desired traffic flow is the moving phase, then inject fewer vehicles onto the road. If the desired traffic flow is the jamming phase, then inject vehicles to make the road denser. The interesting phase is the maximal flow phase, which is achieved by finding equilibrium point between the entering and exiting rates and the average velocity of the vehicles. The phase diagram from the simulation shows that by increasing the braking probability p, the equilibrium point is always at ½ entering and ½ exiting as shown on figure 3.  On the other hand, the braking probability “arises only as a factor in the dynamical evolution of the MFA equations” [4, pg.6], and it only affects the time required to reach the steady state.

 

FIG. 2. Phase diagram (entering rate; exiting rate) in the case vmax = 1, obtained from MFA (continuous line) and simulations (dashed line) for different values of p indicated in the figures.

 

Vmax = 2:

In the case of Vmax = 2, the vehicle can move one or two sites during each time step provided the two sites ahead are empty; otherwise, it can move only one site or remain constant.  In contrast to Vmax = 1, the braking probability plays a major role in determining the steady state. Using the comparison between the MFA equation and Benyoussef’s simulation, increasing braking probability allows the number of vehicles entering the road exceeds the number of vehicles exiting it. And as a result, the equilibrium between the entering rate and exiting rate is destroyed. The maximal flow phase, therefore, is no longer at ½ = ½. Instead, the maximal flow phase occurs at ½ entering = 1/3 exiting as shown on figure 4.

FIG. 4. Phase diagram (entering rate; exiting rate) in the case vmax = 2, for different values of p.

 

The basic model does not mention rules for switching lanes despite its idealism in modeling real traffic flow. Realistically, we would need some rules for changing lanes; we can do this by adding addition rules to the above. There are several factors that will determine the rules, these include local vehicle density, vehicle distribution, but will ignore local road topology. This model includes both deterministic and random components.

The deterministic component of lane changing is based on the above rules for the movement of the vehicles in a one-lane road. Instead of looking at just one lane, now the model considers the behaviors of vehicles in a two-lane road. The vehicle will change lanes if the traffic conditions are better on either of the neighboring lanes.

 

The Two-Lane Model:

Much of the work done in the past by individuals, government agencies, or private institutes have been concentrated on the basic 1 D CA model, we’ve only discussed the basic 1 D CA model thus far. The attention now is to focus on the two-lane CA model by Kai Nagel ET EL5.  The idea proposed in this model is to look for systematical structures in the rule sets for lane changing. 

Traditional Lane Changing Rules:

The traditional two-lane model uses the microscopic model by Wiedemann6. Following Wiedemann’s model, Sparmann7 distinguishes between the wish to change lanes at any given time and the decision to change lanes. Imagine a lane change from the right to left, a wish to change lane is a result of another vehicle ahead obstructing, and a decision to change lane is the action of changing lane if there’s enough space in the other lane.  On the other hand, if the vehicle is changing lane from left to right, then a wish to change lanes is if in both lanes there is nothing ahead obstructing. The term obstructing is defined to be psychophysiological thresholds. What this means is that there are three outcomes: no obstruction, light obstruction, and heavy obstruction, depending on the speed difference and distance.

In practice, the Wiedemann model uses a time discrete formulation of differential equation. But with the increasing “popularity” of using cellular automata to simulate differential equations, M. Cremer8 and co-workers implemented cellular automata lane changing rules. Following Sparmann, they set the rules as follows:

“Lanes are changed to the left if a slower vehicle is less than ll cells ahead and if a gap of size Dx exists on the left lane; lanes are changed to the right if, in the right lane, there is no slower vehicle less than lr cells ahead and there is a gap of size Dx in the right lane.”  [5, pg. 3]

By looking at Sparmann’s suggestion on lane changing, one can see that the density inversion of lane usage. Yet, nobody has included this detail in their research.  The NS model stressed the importance of density inversion of lane usage.

NS Lane Changing Rules:

The NS two-lane model first considers “Security”. Security in a sense is very much like the Space Gap discussed above, it means that one leaves enough space in front and behind oneself.  Security is easily enforced as long as one stays in a single-lane road. In the case of two lanes, changing lanes means that there must be enough space in front and behind the target lane. This may not be so obvious in some cases. For example, a compact vehicle may have different security standard with an eighteen-wheeler truck. Let’s defined Security Gap to be the gap between boundaries [-Vmax, v], v = current vehicle velocity that wants to change lane, Vmax = maximum velocity of vehicles allowed. In summary, a lane is changed if the security gap is fulfilled and if there’s a good reason to change lanes. The second fulfillment exactly described in Sparmann’s wish and decision.

In analyzing the rules for changing lanes, we need to understand that the driving behaviors vary in different countries. For example, in hypothetical Germany freeways, passing is not allowed on the right. This means that if a vehicle is on the right lane, it can change to left if there is a slow vehicle on the same lane or in the left (vr<v.OR.vl<v). The vehicle changes back to the right lane as soon as the velocities of cars on both lanes are sufficiently large (vr>v AND vl>v).  In hypothetical American freeways, passing on the right lane is allowed, however in practice, it rarely happens due to the nature that slower vehicles merge on to the freeway from the right. The vehicle changes back if there is a faster car on the right (or none at all). This driving behavior characterizes the asymmetric (also known as the German) lane changing rules, which is used in NS’s paper.

 

The Simulation:

As we have mentioned above, the advantage of using powerful computer to implement a set of simple rules (cellular automata) immediately takes effect in this model. The lane changing algorithm implemented is as follows:

 

“In even time steps, perform lane changes from the right to the left. All vehicles in the right lane for which the incentive criterion (vr<v.OR.vl<v) and the security criterion  ([-vmax ,v]) are fulfilled are simultaneously moved to the left. In odd time steps, perform lane changes from left to right. All vehicles in the left lane for which the incentive criterion (vr>v AND vl>v) and the security criterion

([-vmax ,v]) are fulfilled are simultaneously moved to the right.” [5, pg. 4]

 

There’s also a very critical factor not mentioned in the above rule. The number of sites one looks ahead can’t be too close and can’t be too far. If one looks too close, one does not see close ahead vehicles and therefore will brake with a high probability. If one looks too far, “one has a tendency to go to the left lane already far away from the obstructing vehicle, thus leading a strong density inversion at low densities.” [5, pg. 4]

The author of this simulation decided to look ahead at most 16 sites and suggested that this look ahead parameter can be adjusted to density inversion.

 

The rules for vehicle movements are taken straightforward from NS’s one-lane model: If the velocity is lower than maximum allowed, accelerate with a probability. Else if the velocity is greater than the security gap, then slow down to avoid accidents. Else with a certain probability, slow down the vehicle for no good reason. These rules generate reasonable relationships between velocity, density, and flow. One important discovery to note is that these rules generate the density inversion below maximum flow.

 

After comparing the velocity-based (NS) and gap-based (Wagner [5, pg. 4], one has a reason to change lane even there’s not enough space) lane changing rules, a “slack” variable S is introduced to the NS simulation.  The problem with velocity-base rules is that the maximum inversion is reached at a very low density. This problem can be fix easily if one incorporates a slack value S into the rules similar to the one in the gap-based rules in addition to the look ahead. In doing so, the look ahead distance is reduced to obtain realistic lane usage.  Nevertheless, it also introduced the side effect that traffic never reverts to an equal lane usage.  To overcome this side effect, the simulation considers vehicles with zero speed attempts to change lane when the speed on the other lane is higher than in its own lane (“symmetrization”).

 

Although maximum inversion is achieved, it is unclear how to account for the presence of slower vehicles such as trucks. As we have mentioned before, the security gap should be different for vehicles of different size in reality. NS’s two-lane model follows Wieldmann’s data, which includes 10% trucks, by giving 10% of the vehicles a lower maximum velocity and keeping the same acceleration capabilities for all vehicles. The result from adding the above rules to the model is that the maximum flow shifts toward higher densities.

 

Additional Reality-check Rules:

With the addition of the slack variable and 10% slower vehicles, the NS two-lane simulation result sets are now closer to reality. As one studies the result sets, one will see that traffic with slow vehicles is different from traffic without slow vehicles. In investigating whether flow breakdown is related to a single-lane breakdown in the left lane, this model simulates traffic with slow vehicles and traffic without slow vehicles separately.

 

In the case of traffic flow with the absence of slow vehicles, the lane usage at maximum flow for one-lane and two-lane is not much of the difference using the “basic” velocity-based rules.

 

             

                                            

                                               

                                               

The Fundamental Diagram (a) shows density vs. flow plot for the single-lane rules, in two independent lanes. Fundamental Diagram (b) shows the left lane of basic velocity-based lane changing rules. And Diagram (c) is the plot for the right lane of basic velocity-based lane changing rules. The Fundamental Diagrams are in perfect compliance with the claim that lane usage is not much of the difference; the points near maximum flow are almost the same. Diagram (b) shows the left lane, which is the same as the right lane in (c). So one might suspect that flow breakdown is independent. As it turns out, left lane reaches maximum flow earlier than right lane and from then on all the additional incoming density is position to the right lane. When the combined density of both lanes is higher than the maximum flow density, flow breakdown occurs.

When slow vehicles are included in the simulation, the two-lane situation behaves more like the one-lane situation than the two-lane situation without slow vehicles. This suggests that the presence of slow vehicles is more critical in analyzing traffic flow than the difference between one-lane and two-lane.  Realistic situations reinforced this suggestion; fast vehicles jam up behind a slow vehicle and create the stop-and-go, go-and-stop dynamic. Two slow vehicles moving side by side, disallowing any form of lane changing create the stop-and-go dynamic in the two-lane situation. The basic velocity-based lane changing rules shows the vehicles on both “jamming” lanes have similar length. On the other hand, the additional slack and “symmetrization” rules, there are more vehicles on the left lane than on the right lane.

                

                                                 

The same Fundamental Diagrams with slow vehicles, indicates that the maximum flow points don’t have a lot in common. In (b) and (c), the points look promising, however, the points near maximum flow are higher in (b) the left lane than in (c) the right lane. The flow in the left lane is higher than the right lane and the one-lane traffic flow. Unlike before, the flow breakdown is cause by the slow vehicles on both lanes.

 

Result and Discussion:

One Lane Model:

In this paper, we have studied models based on the NS models with the maximal acceleration vmax (FI models). We have seen simulations using probabilities to determine the movement of the vehicles. We also have seen cars could enter the road with an entering rate (1 inv p) probability and removed from it with an exiting rate (1 inv p) probability. This kind of system exhibits three phases for vmax = 1, a moving phase, a jamming phase and the maximal flow phase. The transition from one phase to another is affected by the entering rate and exiting rate, and the average velocity. The maximum flow phase occurs at 50% entering rate = 50% exiting rate with high average velocity. When vmax = 2, the maximum flow phase does not occur at 50% = 50%. The system only exhibits first order transition due to lost of the equilibrium point.

 

The author of this paper have also set up a different set of rules to simulate traffic flow following the same idea of the basic model. Instead of using probabilities to determine the movement of the vehicles, the simulation uses a set of preset rules. The preset rules take the current vehicle as the center cell and look at its neighbors in a one-lane road. The speed of the current vehicle is therefore predicted by its neighbors. For low density, the simulation exhibits maximum flow even if vmax = 2.  This kind of behavior is a class III classification in Wolfram’s book “A New Kind Of Science”, which is completely random behavior. For high density, the simulation exhibits almost class IV behaviors, that traffic flow repeats itself on some part of the road after certain number of steps while other parts of the road exhibits random behavior such as jamming phase or maximum flow phase.

 

Two Lane Model:

The NS two-lane model introduces lane changing rules while using the same one-lane vehicle movements. The rules were broken into two parts, the first part uses Sparmann’s notion of  wish and decision and the security gaps to determine lane changing. Second, there’s the security criterion which seems to be universal for all reasonable lane changing rules. The exact value for the security gap doesn’t seem to matter much as long as it’s sufficiently large.  So the rules simply means “change to the left when either in your lane or in the left lane somebody is obstructing you” and “change back when this is no longer true.’’ [5, pg. 12] Since applying the above rules will introduce generic density inversion at high density, the simulation adds “symmetrization” to the rules. And both the velocity-based and gap-based model with slow or without slow vehicles give satisfying result.

 

 

 

Reference:

[1] Steven Wolfram, A New Kind of Science, (Wolfram Media, Inc.) page 56.

 

[2] Cay Horstmann, Traffic Simulator Applet, http://www.horstmann.com/applets/RoadApplet/RoadApplet.html.

 

[3] M. Blue, B.W. Bush, Information content in the Nagel-Schreckenberg cellular      automata traffic model, PDF file, http://public.lanl.gov/bwb/Information%20content%20in%20the%20Nagel-Schreckenberg%20cellular%20automata%20traffic%20model.pdf                       

Abstract: estimate the set dimension and find bounds for the set entropy of a cellular automata model for single lane traffic.

 

[4] A. Benyoussef et al., Traffic Flow in a 1 D Cellular Automata Model with Open Boundaries, (Chinese Journal of Physics, Vol. 39, NO. 5, October 2001), PDF file, http://psroc.phys.ntu.edu.tw/cjp/v39/428.pdf

Abstract: focuses on the effect of breaking probability and a maximum velocity on the density, flow and average velocity of cars moving in the middle of the road.

 

[5] Kai Nagel et al., Two-lane traffic rules for cellular automata: A systematic approach,(Physical Review E, Vol. 58 No. 2, Aug. 1998), PDF file, http://www.sim.inf.ethz.ch/papers/nagel-etc-2lane/nagel-etc-2lane.pdf

Abstract: summarize different approaches to lane changing and the results and propose a general scheme, according to which realistic lane changing rules can be developed; test this scheme by applying it to several lane changing rules, which, in spite of their differences, generate similar and realistic results.

 

[6] R. Wiedemann, Schriftenreihe Heft 8, Institute for Transportation Science, University of Karlsruhe, Karlsruhe (unpublished)

 

[7] U. Sparmann, Spurwechselvorga¨nge auf Zweispurigen BABRichtungsfahrbahnen, No. 263 in Forschung Straßenbau und Straßenverkehrstechnik (Bundesminister fu¨r Verkehr, Bonn–Bad Godesberg, 1978)

 

[8] M. Cremer and J. Ludwig, Math. Computer Simulation 28, 297 (1986).

 

 

 

 

All NKS-SJSU Applets are Open Source Shareware, Papers are Copryight to their Authors.