A FLEXIBLE MODEL FOR TRAFFIC SIMULATION AND TRAFFIC SIGNAL CONTROL OPTIMIZATION
TAN NGUYEN
This paper is submitted for COMP3740
Abstract. The aim of this work is to develop a flexible traffic model based on the recent development of traffic theory and apply the devel- oped model to simulate traffic and signal control in order to identify the optimal signal control policy in several traffic scenarios. The pa- per starts with a review of the cell transmission model, the widely used model in traffic theory. Several impracticalities of the theory are pointed out and necessary modifications are offered in order to build a flexible computer based traffic model successfully. Finally, the developed model is used for simulation of different traffic scenarios with three common traffic signal control policies to identify their strengths and weaknesses, which is essential for optimizing traffic control and enables us to answer important questions like ”Is the most widely used signal control policy (fixed time with offset) the most effective one?”.
1. Introduction
Nowadays, as a consequence of the population boom, traffic congestion is a huge problem of every bigger city in the world. Its economical cost amounts to billions of dollars, not to mention its environmental impact. The apparent solution to this problem is to extend the infrastructure, but this solution is very expensive, time consuming, and is often subjected to environmental and social constraints. The other way around is to improve the traffic flow control, such that congestion is minimized. This second approach is much cheaper, faster, more efficient, and is not subjected to constraints that expansion of traffic infrastructure may have to cope with.
Traffic models play the crucial role in the study of optimization of traffic control. As planning can be only as good as the model, the traffic model is the number one factor that defines the success of a traffic control system. An automated traffic control system based on an unrealistic traffic model is a guaranteed disaster. Thus, more than ever, traffic models are being studied intensively by researchers all over the world.
It is very important for an implementation of a generic model to have declarative semantics rather than procedural semantics (e.g. Java code).
Date: May 17, 2011.
Key words and phrases. traffic flow, traffic modeling, traffic simulation, traffic signal control optimization, RDDL model.
This work was completed with the support of Dr. Scott Sanner.
1
2 TAN NGUYEN
This is because of the fact that models with declarative semantics can be ex- ploited by other programs (planners) to analyze the transition semantics and build abstractions and/or apply different techniques like regression-planning or receding horizon control, which without declarative semantics would be impossible. The model presented in this paper uses RDDL (Relational Dy- namic Influence Diagram Language) – see [2]. As its name may suggests, this is a declarative language for description of relationship of variables between transitions of the system. This language is extremely suitable for building traffic model, because the nature of traffic modeling is the encode of change of states of the traffic network when time advances from t to t + 1.
In this paper, the cell-transmission model (CTM) discussed by Daganzo in [1] and [2] will be studied. It is a well known macroscopic traffic model that gives relatively accurate prediction of macroscopic traffic flows (in con- sistent with kinematic wave theory) under all traffic condition. The model is reviewed in part 2 of this paper. Nonetheless, this model lacks some impor- tant factors when it come to practical implementation, perhaps due to some oversimplifications. Thus part 3 introduces some extension to the CTM in order to make it more flexible and practical for real traffic simulation. Part 4 discusses about an application of the developed model in traffic control optimization by designing an experiment of different traffic control policies applied to different traffic scenarios. Part 5 presents the overall conclusion of this paper, as well as suggestions for some possible future works.
2. Background
In traffic theory, when the level of detail is the main criterion, traffic models are classified into macroscopic models and microscopic models. A microscopic model traces every single vehicle in the system individually, so that during the simulation, all vehicles, together with their interactions, are simulated using the model. The sum of results of all simulated vehicles in the system generates an image or snapshot of the traffic situation. Input parameters of microscopic models are often very detail for every objects, e.g. for every section of roads it may requires speed limit, number of lanes, over- taking prohibitions etc.; for every vehicle it may requires origin, destination, desired velocity, acceleration and deceleration abilities, vehicle type, driving style (aggressiveness) etc. Because of its level of detail, microscopic mod- els are computationally intensive and thus only suit simulation of a small section of the traffic network.
On the other hand, macroscopic models use aggregate variables to sim- ulate traffic situation. Vehicles are no longer traced individually, they’re rather considered collectively by traffic density (number of vehicles per kilo- meter), traffic flow (number of vehicles passing a road section per second), and average velocity of all vehicles. The first model of this kind was de- veloped by Lighthill and Whitham [3] in 1955, where only traffic density was considered. Then the model is further extended by many others to be able to cope with shock waves and stop-and-go traffic in congested traffic situation. Macroscopic models, comparing to microscopic model, are less computationally intensive, thus allows a faster and larger simulation of the traffic network. They also have much fewer parameters than microscopic
TRAFFIC MODEL AND OPTIMIZATION 3
models, which make them easier for fine tuning the traffic network control system. These advantages make macroscopic models much more suitable for optimization of traffic network.
The following section discusses the (macroscopic) CTM [2], and gives a quick overview of traffic control policies.
2.1. The Cell-Transmission Model.
2.1.1. The Terminology. In traffic theory, the traffic network is divided into cells. Each cell represents a section of the road. Thus there are fundamental physical quantities associated to a cell. These are traffic density, free flow velocity, traffic flow, and shockwave speed. Traffic density k (cars/m) is the number of cars per unit length. The maximum traffic density is called jam density, denoted by kj. It is the maximum number of cars that can possibly be ”compressed” into the given cell. Free flow velocity v (m/s) is the average speed of cars in the given cell when there’s no traffic jam. It is often given by the speed limit of the road section represented by the given cell. Traffic flow q (cars/s) is the rate at which cars flow through a given point. Maximum traffic flow qmax is the maximum possible flow in accordance with the conditions of the cell. Shockwave speed w (m/s) is the speed with which disturbances propagate backward when traffic is congested.
Figure 1. The equation of state of the cell-transmission model. [2]
The relationship between traffic flow q, density k and velocity v is natu- rally q = v · k. However, q can’t be greater than qmax, and in cases when there’s traffic jam ahead, q can be only the ”remaining” density times the shockwave speed. All these observations is expressed in graphical presenta- tion given in Figure 1. When cars started flowing into the cell (from another
4 TAN NGUYEN
cell linked to this cell), the density k of the cell starts increasing, the flow q = v · k also increases constantly with the increase of k. Some time later, the flow q reaches its maximum qmax and can’t be increased further. At this point more incoming cars only increase the density k of the cell. At a certain level of k, the cell is so dense, that incoming cars can enter the cell at a speed much slower than the free flow speed. It means the effective velocity is decreasing, causing a decreasing flow into the cell. At this stage the flow is q = w(kj − k). The shockwave speed w is the speed, with which traffic jam propagates backward. For example, at time t, the end of a 100m cell became stuck, and at time t + 5, this event was propagated to the beginning of the cell (the beginning had became stuck), then the shockwave speed is 100/5 = 20 m/s. When the cell’s density reaches its maximum kj, the flow is zero, there’s no room for more cars to flow into the cell. Therefore the equation for relationship of all these basic variable is:
(1) q = min{vk, qmax, w(kj − k)}
2.1.2. CTM Network Representation. The CTM assumes that the road is divided into homogeneous sections (cells) with lengths equal the distance traveled by free-flowing traffic in one clock interval. The traffic network is described as a graph of cells. The possible vehicle transfers between two cells are represented by a link between them. The topology of the detailed network is defined by specifying for each link k a ”beginning” cell Bk and an ”ending” cell Ek. For each cell i, Qi is defined as the maximum number of vehicles that could enter cell i per unit time (one clock interval), Ni is defined as the maximum number of cars that can occupy cell i (maximum occupancy). The state of the network is then given by {ni}: the set of num- ber of vehicles contained in each cell of the network. As this is a macroscopic model, these numbers are not necessarily natural numbers, but rather real numbers. Note that comparing to the standard physical properties of a cell introduced in previous section, each cell in CTM is characterized by only two values: maximum throughput Qi and maximum occupancy Ni. This significant simplification is due to the assumption above, that cells lengths equal the distance traveled by free-flowing traffic in one clock interval. By this assumption, in one clock interval, all cars in a cell Bk will move to the next cell Ek, assuming there’s no traffic jam.
Figure 2. Representation of merge and diverge. [2]
The CTM further restricts the maximum number of arcs (links) entering and/or leaving a node (cell) to 3. Thus, cells can be classified into three types: ”diverge” if only one link enters the cell but two leave it, ”merge” if
TRAFFIC MODEL AND OPTIMIZATION 5
two links enter and one leaves, and ”ordinary” if one enters and one leaves (see Figure 2 above). By stacking up these basic elements we can represent any traffic network. For example an intersection can be represented by multiple diverges and merges connected together. This representation of the network greatly reduces the complexity of the network flow calculation, because it is now necessary to identify only three equations for the three linking types: ordinary, merge, and diverge.
2.1.3. CTM Ordinary Links. Ordinary link is the most easy one to calculate. Let yk(t) denote the flow on link k from clock tick t to clock tick t+1 between the beginning cell Bk and the ending cell Ek. Furthermore, for each cell I let SI(t) and RI(t) denote the sending and receiving capacity of that cell from clock tick t to clock tick t + 1. Apparently, the sending capacity SI (t) can not exceed neither the maximum throughput QI nor the number of car in the given cell nI . Thus, the equation for the sending capacity is:
(2) SI(t) = min{QI,nI}
The receiving capacity also can not exceed the maximum throughput QI, and if maximum is not yet reached, it will equal a fraction of the ”remaining” capacity of the cell δI [NI − nI ], where δI = wI /vI denote the shockwave speed coefficient of cell I – note that in Equation (1) we have: w(kj − k) = (w/v)(N − n). Thus, the equation for the receiving capacity is:
(3) RI(t)=min{QI,δI[NI −nI]}
Because the flow yk(t) can not exceed neither the sending capacity SBk(t)
nor the receiving capacity REk(t), its equation must be: (4) yk(t) = min{SBk(t), REk(t)}
2.1.4. CTM Diverges. Diverge can also be easily calculated if we know the turning percentages. Suppose we have a diverge as shown in Figure 2(b), and let βEk(t) and βCk(t) denote the proportions of SBk(t) going each ap- propriate link. Apparently, βEk(t) + βCk(t) = 1, and:
(5) yk(t) = min{βEk(t)SBk(t), REk(t)} and yck(t) = min{βCk(t)SBk(t), RCk(t)}
Note that, in general, the percentages of left/right turn depends on the destinations of vehicles in the flow. A fixed assignment of this percentages like the above may not be very accurate. A better model is to determine these percentage dynamically from the ”known” routes of the traffic flow, but that model goes well beyond the scope of this paper and thus will not be presented here.
2.1.5. CTM Merges. Merge is perhaps the most complicated one to calculate in CTM. Clearly, from Figure 2(a), the flows must satisfy these constraints:
(6) yk(t) ≤ SBk(t); yck(t) ≤ SCk(t) and
(7) yk(t) + yck(t) ≤ REk
6 TAN NGUYEN
If SBk + SCk ≤ REk then cell Ek receives all the flows from Bk and Ck. Thus we have:
(8) yk(t) = SBk(t) and yck(t) = SCk(t) ifREk ≥SBk +SCk
In other cases we assume, that as long as the supply of vehicles from both approaches, SBk(t) and SCk(t), is not exhausted, a fraction pk of the vehicles come from Bk and the remainder pck from Ck, where pk + pck = 1. These ”p” constants represent sort of priority of the appropriate flow.
Figure 3. Graph of the merge equation constraints. [2]
Figure 3 shows the graph of possible flow for a merge. The shaded rec- tangle represents all solutions for Equation (6). The left half plane to the line yk + yck = REk represent all possible solutions for Equation (7), three cases (i, ii, and iii) of possible position of that line are shown in the graph. The line yck/yk = pck/pk representing the flow proportion is also shown.
Case (iii) arises when REk ≥ SBk + SCk and this is already solved by equation (9) (the solution is the coordinates of point P in the graph). In case (i) and (ii) the solution is the coordinates of point Q and R, because they maximize the possible flows, meanwhile satisfy all the given constraints.
TRAFFIC MODEL AND OPTIMIZATION 7
We note that in both cases, the solution point is the middle point of the three intersection points of these four lines: yck = SCk, yk = SBk, yck/yk = pck/pk, and yk + yck = REk. Thus we have:
(9) yk(t) = mid{SBk, REk − SCk, pkREk} yck(t) = mid{SCk, REk − SBk, pckREk}
ifREk
// ensure a diverge cell flows into two other cells
forall_{?c: cell} [DIVERGE-CELL(?c)
=> ((sum_{?c2 : cell} NEXT(?c, ?c2)) == 2)];
};
// Reward is the sum of number of vehicle that have arrived
reward = sum_{?c : cell} n(?c) * LAST(?c);
Figures 4 and 5 show the visualization of the RDDL model in various instances. The visualization is written in Java, which read states from the
12 TAN NGUYEN
RDDL model and draw the appropriate traffic network diagram. Note that the cell color is interpolated from white to red in accordance with the density level of the cell (from zero to maximum density). The cells with green color are either a charging cell or a discharging cell. Each cell have a cyan triangle indicating the existence of traffic movement and its direction. Traffic signal is indicated by either an green arrow showing the allowed direction (green light direction), or a yellow circle representing that all directions is not allowed.
Figure 4. Visualization of a roundabout 4. Policy Evaluation
4.1. Experiment Description. This part represents an empirical traffic control policy evaluation using the extended CTM. A 3×3 grid of one-way roads is used to simulate a part of a city (see Figure 5). There are traffic sig- nal at each of the 9 intersections of the grid. The distance between adjacent intersection is 400m. Nine traffic scenarios are considered as follows:
• High traffic in all directions
• High traffic west-east and medium traffic north-south
TRAFFIC MODEL AND OPTIMIZATION 13
Figure 5. Visualization of a grid of 3×3 one-way roads with 9 intersections including traffic signal at every intersection
• High traffic west-east and low traffic north-south
• Medium traffic west-east and high traffic north-south • Medium traffic in all directions
• Medium traffic west-east and low traffic north-south • Low traffic west-east and high traffic north-south
• Low traffic west-east and medium traffic north-south • Low traffic in all directions
The three traffic control policies described in the background part are tested against the above 9 traffic scenarios in order to assess their effective- ness in each case. Each control policy is set with optimal parameters for the given traffic grid. A script is then used to run each control policy with each traffic scenario and store the results to an output file. The result of each test is the number of vehicles that managed to go through the traffic network (that is equivalent to the number of vehicles arrived to LAST cells). For every test, the number of time steps is set to 2000 (approximately half an hour) to ensure the run-time is long enough, so that the policy fully exposed its potential.
14 TAN NGUYEN
4.2. Experiment Result. The following tables list the results of the ex- periment:
Table 1. Random policy test result
Table 2. Fixed time with offset policy test result
Table 3. Local adaptive policy test result
4.3. Experiment Evaluation. From the result tables above, it can be eas- ily seen that the random policy has the worst performance, with an average of approximately 10% lower performance than the other two policies. On the other hand, it was quite difficult to set the optimal parameters for the fixed time with offset policy to optimize traffic flow in both directions, but the symmetry of the results shows that the parameters were set correctly (otherwise there would be a significant difference between the result of e.g. west-east high, north-south low traffic versus west-east low, north-south high traffic).
The interesting findings is the comparison of performance between fixed time with offset policy and the local adaptive policy. While the fixed time with offset policy has about 5% higher performance in all scenarios where the the traffic in both directions is from medium to high, the local adap- tive policy really shows its advantage in cases where traffic is low in one direction and above low level in the other direction with performance about 20% higher than that of fixed time with offset policy (note that if traffic is low in both directions then the performance is the same regardless of what policy is used). This is perhaps an important finding, because in practice, many intersections would have the same characteristics suitable for adaptive control policy (one direction with low traffic, the other with high traffic), and we have shown that by replacing the commonly used fixed time with offset policy by local adaptive policy we would have a boost of about 20% traffic throughput in these intersection.
W-E / N-S
HIGH
MEDIUM
LOW
HIGH
17877
17956
12756
MEDIUM
17755
17731
12767
LOW
12821
12924
7618
W-E / N-S
HIGH
MEDIUM
LOW
HIGH
20159
19794
13911
MEDIUM
19775
19411
13527
LOW
13872
13872
7624
W-E / N-S
HIGH
MEDIUM
LOW
HIGH
18826
18714
19815
MEDIUM
18744
18588
15248
LOW
19852
15231
7621
TRAFFIC MODEL AND OPTIMIZATION 15
Table 4 summarizes the suitability of each type of policy for each traffic scenario. FT means fixed time with offset policy, AD means local adaptive policy, ANY means any policy is suitable
Table 4. Suitability of traffic control policy for each traffic scenario.
5. Conclusion and Future Work
This paper has extended the CTM model in order to produce a practical traffic model in RDDL. The model is then used in an empirical evaluation of several traffic control policies, which has successfully pointed out the suitability of each type of control policy for certain traffic scenarios. It showed, that the common fixed time with offset control policy is not the best policy in all cases, and a suitable combination of fixed time with offset control policy with local adaptive control policy may significantly boost the performance of the traffic network.
Due to a very limited time scope of the project, this paper hasn’t con- sidered and/or explored several problems to a greater details. For example: the implementation of a planner to optimize parameters of control policies, the model of known routes instead of the turn probability for diverges, the optimization of the model for better computational performance etc. These perhaps cane be subjects of work in the future.
References
1. Daganzo C.F., The cell-transmission model: A simple dynamic representation of high- way traffic. Department of Civil Engineering and Institute of Transportation Studies, University of California, Berkeley CA 94720 (1993)
2. Daganzo C.F., The cell transmission model: Network traffic. Department of Civil Engineering and Institute of Transportation Studies, University of California, Berkeley CA 94720 (1994)
3. Lighthill M. J. and Whitham G.B., On kinematic waves II. A theory of traffic flow on long crowded roads. (1955).
4. Sanner S., Relational Dynamic Influence Diagram Language (RDDL): Language De- scription. NICTA, Australia (2011)
Research School of Computer Science, College of Engineering & Computer Science, Australian National University
E-mail address: u4702662@anu.edu.au
W-E / N-S
HIGH
MEDIUM
LOW
HIGH
FT
FT
LA
MEDIUM
FT
FT
LA
LOW
LA
LA
ANY