# Deliberative Self-Organizing Traffic Lights with Elementary Cellular Automata

Authors: Jorge L. Zapotecatl; David A. Rosenblueth; Carlos Gershenson
Journal: Complexity
 (2017)

---

## Abstract

Self-organizing traffic lights have shown considerable improvements compared to traditional methods in computer simulations. Self-organizing methods, however, use sophisticated sensors, increasing their cost and limiting their deployment. We propose a novel approach using simple sensors to achieve self-organizing traffic light coordination. The proposed approach involves placing a computer and a presence sensor at the beginning of each block; each such sensor detects a single vehicle. Each computer builds a virtual environment simulating vehicle movement to predict arrivals and departures at the downstream intersection. At each intersection, a computer receives information across a data network from the computers of the neighboring blocks and runs a self-organizing method to control traffic lights. Our simulations showed a superior performance for our approach compared with a traditional method (a green wave) and a similar performance (close to optimal) compared with a self-organizing method using sophisticated sensors but at a lower cost. Moreover, the developed sensing approach exhibited greater robustness against sensor failures.


---

## Body

## 1. Introduction

Vehicular traffic has a number of negative effects in urban areas such as increased pollution, excessive fuel consumption, time lost in traffic, and stress. Traffic congestion occurs when the density (number of vehicles per unit length) creates a demand greater than the available space necessary for free flow on roads. This problem has motivated governments to regulate traffic flow (number of vehicles per unit of time) in attempts to reduce traffic congestion. Rules have been introduced to mediate potential conflicts between cars. Drivers have agreed on which side of the street to drive through, lanes regulate space usage, traffic signals prompt safe driving, and traffic lights coordinate crossings.A traffic light system will be more efficient if average speeds are increased, thereby reducing waiting times, fuel consumption, and pollution. For decades, researchers have been using mathematical and computational methods to find appropriate phases and offsets to regulate traffic lights [1–7]. An open-loop control method, called “green wave,” has been implemented in some areas of many cities to control traffic lights. The idea behind the green wave method [8] is as follows: if the consecutive traffic lights switch with a delay equivalent to the expected vehicle travel time between intersections, vehicles should not have to stop. Thus, waves of green light move through the street at the same velocity as vehicles.The green wave method can be useful because it is better than having no coordination at all. However, the green wave approach does not consider the current traffic conditions. At low densities, some vehicles wait behind a red light while the intersection is not used. On the other hand, at high densities, gridlocks at intersections are formed because the controller does not consider road saturation (see Figure1). Since the green wave method does not adapt to the current traffic conditions, it is common that vehicles go slower than the green wave due to traffic density. Moreover, in realistic street networks, only two directions can be coordinated, so a considerable fraction of vehicles go against green waves, substantially increasing their waiting times.Figure 1
Two disadvantages of the green wave method.
(a)
At low densities, idle intersections, while cars wait at red light
(b)
At high densities, gridlocks at intersections, as saturation is not sensedAn alternative to improve the performance of vehicular traffic is to use advanced traffic lights. The main proposed control systems using advanced traffic lights focus primarily on sensors placed at the intersection to count the vehicles approaching in certain distance [1–3]. However, the main disadvantages that prevent the implementation of such systems are related to cost and, in some cases, privacy.A method for controlling traffic lights using self-organization has outperformed in simulations the green wave method and has been shown to be close to optimality [4]. The essential idea of the self-organizing method is to use advanced traffic lights where sophisticated sensors detect vehicles approaching and departing from each intersection. The traffic light gives preference to the direction with most vehicles in upstream or with most space available downstream. However, because this method also requires a sophisticated infrastructure, it has the same drawbacks of the systems mentioned previously (see Figure 2). Moreover, cameras are not suitable for detecting vehicles in visibility-limiting weather.Figure 2
In the case of the self-organizing method, if a closed-loop system (CCTV) is used, a camera for each street where vehicles enter the intersection to detect approaching vehicles is required and a camera for every street is required where vehicles exit the intersection to detect vehicle dropout. From the images acquired, an algorithm recognizes vehicles approaching and leaving the intersection.
(a)
View from front camera
(b)
View from back camera


## 2. Related Work

This work focuses on vehicular traffic modeling based on cellular automata (CA). CA have an important role in the modeling of complex systems mainly because of the simplicity of their specification and the complexity in their behavior. Moreover, CA are computationally inexpensive and they can be parallelized allowing the simulation of large cities in the order of thousands of intersections. Time and space are discrete.The behavior of vehicles on the streets can be modeled with the elementary cellular automaton (ECA) rule 184; this rule has been used to model traffic flow [9–12]. An ECA consists of a linear array of cells where the current state of each cell depends on its previous state and the current states of its two closest neighbors. Each cell can take only values of 0 or 1. We can assume that one cell represents five meters, roughly the space occupied by a stationary vehicle.Rule184 simulates traffic flow so that vehicles are represented by 1 s and spaces are represented by 0 s. If the value of a cell is 0 and its closest neighbor to the left has value of 1, then in the next step of time the value of such a cell will change to 1. On the other hand, if the value of a cell is 1 and its closest neighbor to the left has value of 0, then in the next step of time the value of such a cell will change to 0. This models the movement of vehicles to the right. In the simulations to be presented below, streets are assumed to have only one lane in four different directions, forming a Manhattan-style grid [13]. If a light is red, all cells use rule 184 with two exceptions: rule 252 is applied to the previous cell of the intersection and rule 136 is applied to the next cell. In Figure 3, transition tables for the three rules used by the model are listed. The intersection cell is a special case, as it has four potential neighbors. The rule never changes (184). What changes is the neighborhood; that is, it takes as nearest neighbors only the two cells in the street with a green light (also using rule 184). A diagram of the cells around an intersection is shown in Figure 3.Figure 3
Set of rules applied in the ECA city model (184, 252, and 136) and the configuration of rules around an intersection [13].Rule252 is used to stop traffic flow. If there is a vehicle in the central cell (i.e., 010, 011, 110, and 111), it will remain there, so that the future state of the cell will remain 1. If there is a vehicle in the previous cell (i.e., 100 and 101), the next state of the cell will be 1. Only if there are no vehicles in the previous and central cell (i.e., 000 and 001), the state of the cell will remain at 0. Rule 136 is used to allow vehicles to move forward and to prevent vehicles crossing an intersection from “turning,” entering another street. Therefore, the future state of the cell will be 1 only if the cell ahead is occupied (i.e., 011 and 111).The model of vehicular traffic proposed by Nagel and Schreckenberg [14] (NaSch) can be seen as elaboration of ECA rule 184 with the following extensions: a discrete variable representing the velocity associated with each vehicle, an acceleration, a deceleration (due to the presence of other vehicles), and a random tendency to slow down. This deceleration attempts to model a human tendency to overreact while braking. The NaSch model exhibits phantom traffic jams and, depending on both the density and the probability of slowing down, these spontaneous jams appear or disappear indefinitely. Because a vehicle can have a velocity greater than one cell per time step, the NaSch model is not an ECA. The reason is that the next state of a cell depends not only on its nearest neighbors.Many variants of the NaSch model have been proposed, each with different degrees of realism. For example, the work presented by Nagel and Paczuski [15] inhibits the random deceleration of vehicles traveling at maximum velocity. This change eliminates phantom traffic jams and reproduces the slower-is-faster effect [16]. In the work presented by Fukui and Ishibashi [17], the authors consider only random behavior for vehicles traveling at maximum velocity. The random slowing of vehicles at full velocity models the fact that drivers traveling at high velocity (with no cruise control) cannot concentrate on the road indefinitely.Cellular automaton traffic flow modeling for two dimensions was conceived by Biham et al. [18]. In this model (BML), each cell represents an empty space or a vehicle that is traveling to the right or up. Except for the initial random positioning of the vehicles, this automaton is deterministic. Periodic boundary conditions are considered so that the number of vehicles is preserved. On even steps, only vehicles pointing upward move, while in odd steps, only vehicles pointing right move, unless a nonempty space is in front.The BML model is interesting for showing complex behavior (descriptive model) but not a realistic (predictive) model of vehicular traffic. More realistic vehicular traffic models have been developed as generalizations of the BML model [19–22]. Such generalizations are essentially an extension BML model for which the streets have an arbitrary length (instead of a single cell) and vehicles traveling between the intersections behave according to the NaSch model. Traffic lights are incorporated into models making vehicles decelerate or stop not only because a vehicle is in front but also when approaching a red light.Schadschneider et al. [21] experimented with a regular grid where vehicles move only right or upwards. Traffic lights were synchronized alternating between green and red (also called “marching” [23]).In the work presented by Simon and Nagel [19], the authors developed a more elaborate combination of the BML and NaSch models. Streets with different capacities can be modeled. For example, different numbers of lanes can be considered, without explicitly simulating several lanes. For computational reasons, the computer program used random traffic lights, which have the advantage of having to be checked only when a vehicle reaches the intersection.In relation with self-organizing traffic lights, the work presented by Gershenson and Rosenblueth [4, 5] is focused on the modeling of traffic lights to compare the performances of different control methods using elementary cellular automata and proposing various rules to increase the traffic flow. Two methods were evaluated to coordinate traffic lights: the traditional method called green wave and the self-organizing method. The simulations revealed the superiority of the self-organizing method over the green wave method in terms of traffic flow in a wide range of densities.The approach by Lämmer and Helbing [7] assumes a priority-based control of traffic lights by the vehicle flows and platoons. The considered local interactions lead to emergent coordination patterns such as green waves and achieve an efficient, decentralized traffic light control.In the work by de Gier et al. [6], the authors compare the effects of nonadaptive versus adaptive traffic lights on generic urban road networks based on cellular automata, in which instantaneous traffic state information is sent to the traffic signal schedule. The results show that the adaptive traffic lights result in better performance compared to nonadaptive ones.The work by Goel et al. [24] investigates the use of a distributed traffic signal control algorithm based on the concepts of self-organization. The distributed traffic signal control algorithm is benchmarked against traditional traffic signal algorithms. The distributed traffic signal control algorithm performs significantly better compared to the traditional traffic signal algorithms. A simulation model was created based on an abstraction of city road with multiple intersections using data on actual traffic counts.The research by Cesme and Furth [25] explores a paradigm “self-organizing signals” for traffic signal control based on local rules that create coordination mechanisms. Simulation tests in VISSIM performed on arterial corridors in Massachusetts and Arizona show overall delay reductions.


## 3. Traffic Light Controllers and Measures

This section presents the green wave and self-organizing methods [4]. In addition, the measures used to evaluate the performance of the methods are described in this section.


### 3.1. The Green Wave Method

The idea behind the green wave method is the following: if the consecutive traffic lights switch with an offset (i.e., delay) equivalent to the expected vehicle travel time between intersections, vehicles should not have to stop. Thus, waves of green lights move through the street at the same (expected) velocity as vehicles.This method has advantages, for example, when most of the traffic flows in the direction of the green wave at low densities. However, vehicles flowing in the transverse direction of the green wave will be delayed. Also, if traffic is flowing at velocities lower than expected, the green waves will go faster than vehicles and there will be delays.Implementing the green wave method in our ECA model requires synchronization of the traffic light cycleT with the travel time of the vehicles. This is achieved in our model only if the length of the street is a multiple of cycle T and periodic boundary conditions are applied. The traffic light cycle T is split into T/2 for green and red light, respectively.The lights can be in a state of a green light horizontally (east or westbound) and red light vertically (north or southbound) or a state of a green light vertically and a red light horizontally. The stateσi of the traffic lights is initialized as follows:(1)σi=greenverticalifx-ymodT+0.5≥T2greenhorizontalotherwise.Equation (1) initializes the state of a traffic light to have a green vertical light if the nearest integer of x coordinate minus y coordinate, modulus one cycle T, is greater than or equal to half a cycle. Otherwise, the state is set as horizontal green. With this equation, 50% of contiguous intersections of every street (vertical and horizontal) will have a green vertical state and the other half will have a green horizontal state. The states of intersections are arranged in such a way that the transitions from horizontal green to vertical green lie on skew diagonals.In addition, in order to set the green wave a local offsetwi is necessary for each traffic light. This offset is determined by the coordinates x and y of the intersection cells as follows:(2)wi=x-ymodT2+0.5.Equation (2) sets the offset by rounding to the nearest integer of x coordinate minus y coordinate, module T/2. This offset creates green waves to the south and east for regular or irregular grids. The purpose of setting the offset is to make intersections lying on the skew diagonals have the same offset value so as to switch their lights at the same time. In this way, free-flowing vehicles going either eastbound or southbound will be able to reach an intersection with a green light. To change the direction of the green wave, only the sign of x or y coordinate has to be changed.


### 3.2. The Self-Organizing Method

It has been postulated that the control of the traffic lights should not be addressed as an optimization problem but as an adaptation problem because traffic flows and densities constantly change [23]. Another reason to prefer an adaptive method is that the optimization has a high computational cost to search for possible solutions, as it is an EXP-complete problem [8]. An adaptive method that applies self-organization has shown substantial improvements in increasing traffic flow at different densities compared to the green wave method [4].The essential idea of the self-organizing method is to equip traffic lights with sensors that detect approaching vehicles. The traffic lights give preference to the street with most vehicles. Without requiring local communication, vehicles self-organize into “platoons” which flow faster as they can trigger a green light before reaching an intersection, stopping only when another platoon is crossing.With the self-organizing method, each intersection follows independently the same rules based solely on local traffic information. There are six rules (unrelated to ECA rules), where higher-numbered rules override lower-numbered rules. The parameters to be considered in the self-organizing method and the full set of rules are shown below (see Figure4).Figure 4
Rule1 attempts to turn a red light green when many vehicles approach it. Rule 2 prevents fast switching of traffic lights for high densities and also prevents a street from having always a green light. Rule 3 prevents “tails” of platoons from being cut, promoting the integrity of platoons. Rule 4 allows a quick change of lights at low densities, as isolated vehicles can activate the lights change as they approach an intersection without requiring them to form platoon. Rules 5 and 6 prevent gridlocks caused by stationary vehicles at intersections, while allowing flow in directions with space downstream.The algorithm of the self-organizing method is given as follows:(1)
On every tick, add to a counter the number of vehicles approaching or waiting at a red light within distanced. When this counter exceeds a threshold n, switch the light (whenever the light switches, reset the counter to 0).(2)
Lights remain green for a minimum timeu and a maximum time w.(3)
If few vehicles (m or fewer, but more than zero) are left to cross a green light at a short distance r, do not switch the light.(4)
If no vehicle is approaching a green light within a distanced and at least one vehicle is approaching the red light within a distance d, then switch the light.(5)
If there is a stationary vehicle on the road at short distancee beyond a green traffic light, then switch the light.(6)
If there are stationary vehicles on both directions at a short distancee beyond the intersection, then switch both lights to red. Once one of the directions is free, restore the green light in that direction.Rules with a higher number override rules with a lower number; for example, rule 5 overrides rules 1–4. The details and rationale for all rules can be found in [5]. It should be mentioned that maximum time w was added to rule 2 in this work, because when sensor errors occur, vehicles at low densities may remain undetected indefinitely behind a red light.


### 3.3. Performance Measures

The behavior of the model will depend strongly on the vehicle densityρ∈[0,1]. Trivial cases are the extremes ρ=0, where there are no vehicles, and ρ=1, where all cells are occupied by vehicles, so there is no space to move and flow is zero. The density can be easily calculated by dividing the number of cells with 1 (i.e., total number of vehicles, ∑‍si) by the total number of cells (S).(3)ρ=∑siS.The performance of the system can be measured with velocityv∈[0,1], which is simply the number of cells that changed from 0 to 1 over the total number of vehicles:(4)v=∑si′>0∑si,where si′ is the derivative of state si. If si′=1, the cell changed from 0 to 1. If si′=-1, the cell changed from 1 to 0. si′=0 when there is no change in the state of si, that is, there is no vehicle, or the vehicle at si has stopped.The flowJ of the system represents how much of the space is used by moving vehicles. It can be obtained by multiplying the vehicle density by the velocity:(5)J=ρυ.In the ECA rule 184 model of highway traffic, the maximum possible flow isJ=0.5 at a density ρ=0.5. This is because vehicles need at least one cell between them to move. If there are fewer vehicles, the flow will be lower, since there is no movement in free space. If there are more vehicles, then the flow will also be lower, since stationary vehicles do not move.When coordinating traffic lights, the best performance that can be theoretically achieved would be a system in which each intersection has the best performance possible of an isolated intersection. A lower performance implies that there is interference between traffic lights. Given the properties of our model of city traffic, (6) describe the optimal curves for single intersections of velocity and flow, which depend on the maximum flow Jmax allowed by an intersection:(6)voptim=1ifρ≤JmaxJmaxρifJmax<ρ<1-Jmax1-ρρif1-Jmax≤ρJoptim=ρifρ≤JmaxJmaxifJmax<ρ<1-Jmax1-ρif1-Jmax≤ρ.Ifρ≤Jmax, then the intersection can support a maximum velocity of 1 cells/tick. Following (5), the flow will then be equal to the density ρ, as all vehicles are moving. If Jmax<ρ<1-Jmax, then the flow of the intersection will be restricted by the maximum capacity of the intersection, that is, Jmax. This implies that vehicles will be using the intersection at all times, and the average velocity will be Jmax/ρ. If 1-Jmax≤ρ, the density of the streets is so high that it restricts the flow of vehicles on streets, reducing the flow to 1-ρ and the velocity to (1-ρ)/ρ.Notice that the flow optimumJoptim is symmetric, because there is symmetry in our city traffic model between vehicles (1 s) moving in one direction and spaces (0 s) moving in the opposite direction. This is also observed in the rule 184 model of highway traffic [12].


## 3.1. The Green Wave Method

The idea behind the green wave method is the following: if the consecutive traffic lights switch with an offset (i.e., delay) equivalent to the expected vehicle travel time between intersections, vehicles should not have to stop. Thus, waves of green lights move through the street at the same (expected) velocity as vehicles.This method has advantages, for example, when most of the traffic flows in the direction of the green wave at low densities. However, vehicles flowing in the transverse direction of the green wave will be delayed. Also, if traffic is flowing at velocities lower than expected, the green waves will go faster than vehicles and there will be delays.Implementing the green wave method in our ECA model requires synchronization of the traffic light cycleT with the travel time of the vehicles. This is achieved in our model only if the length of the street is a multiple of cycle T and periodic boundary conditions are applied. The traffic light cycle T is split into T/2 for green and red light, respectively.The lights can be in a state of a green light horizontally (east or westbound) and red light vertically (north or southbound) or a state of a green light vertically and a red light horizontally. The stateσi of the traffic lights is initialized as follows:(1)σi=greenverticalifx-ymodT+0.5≥T2greenhorizontalotherwise.Equation (1) initializes the state of a traffic light to have a green vertical light if the nearest integer of x coordinate minus y coordinate, modulus one cycle T, is greater than or equal to half a cycle. Otherwise, the state is set as horizontal green. With this equation, 50% of contiguous intersections of every street (vertical and horizontal) will have a green vertical state and the other half will have a green horizontal state. The states of intersections are arranged in such a way that the transitions from horizontal green to vertical green lie on skew diagonals.In addition, in order to set the green wave a local offsetwi is necessary for each traffic light. This offset is determined by the coordinates x and y of the intersection cells as follows:(2)wi=x-ymodT2+0.5.Equation (2) sets the offset by rounding to the nearest integer of x coordinate minus y coordinate, module T/2. This offset creates green waves to the south and east for regular or irregular grids. The purpose of setting the offset is to make intersections lying on the skew diagonals have the same offset value so as to switch their lights at the same time. In this way, free-flowing vehicles going either eastbound or southbound will be able to reach an intersection with a green light. To change the direction of the green wave, only the sign of x or y coordinate has to be changed.


## 3.2. The Self-Organizing Method

It has been postulated that the control of the traffic lights should not be addressed as an optimization problem but as an adaptation problem because traffic flows and densities constantly change [23]. Another reason to prefer an adaptive method is that the optimization has a high computational cost to search for possible solutions, as it is an EXP-complete problem [8]. An adaptive method that applies self-organization has shown substantial improvements in increasing traffic flow at different densities compared to the green wave method [4].The essential idea of the self-organizing method is to equip traffic lights with sensors that detect approaching vehicles. The traffic lights give preference to the street with most vehicles. Without requiring local communication, vehicles self-organize into “platoons” which flow faster as they can trigger a green light before reaching an intersection, stopping only when another platoon is crossing.With the self-organizing method, each intersection follows independently the same rules based solely on local traffic information. There are six rules (unrelated to ECA rules), where higher-numbered rules override lower-numbered rules. The parameters to be considered in the self-organizing method and the full set of rules are shown below (see Figure4).Figure 4
Rule1 attempts to turn a red light green when many vehicles approach it. Rule 2 prevents fast switching of traffic lights for high densities and also prevents a street from having always a green light. Rule 3 prevents “tails” of platoons from being cut, promoting the integrity of platoons. Rule 4 allows a quick change of lights at low densities, as isolated vehicles can activate the lights change as they approach an intersection without requiring them to form platoon. Rules 5 and 6 prevent gridlocks caused by stationary vehicles at intersections, while allowing flow in directions with space downstream.The algorithm of the self-organizing method is given as follows:(1)
On every tick, add to a counter the number of vehicles approaching or waiting at a red light within distanced. When this counter exceeds a threshold n, switch the light (whenever the light switches, reset the counter to 0).(2)
Lights remain green for a minimum timeu and a maximum time w.(3)
If few vehicles (m or fewer, but more than zero) are left to cross a green light at a short distance r, do not switch the light.(4)
If no vehicle is approaching a green light within a distanced and at least one vehicle is approaching the red light within a distance d, then switch the light.(5)
If there is a stationary vehicle on the road at short distancee beyond a green traffic light, then switch the light.(6)
If there are stationary vehicles on both directions at a short distancee beyond the intersection, then switch both lights to red. Once one of the directions is free, restore the green light in that direction.Rules with a higher number override rules with a lower number; for example, rule 5 overrides rules 1–4. The details and rationale for all rules can be found in [5]. It should be mentioned that maximum time w was added to rule 2 in this work, because when sensor errors occur, vehicles at low densities may remain undetected indefinitely behind a red light.


## 3.3. Performance Measures

The behavior of the model will depend strongly on the vehicle densityρ∈[0,1]. Trivial cases are the extremes ρ=0, where there are no vehicles, and ρ=1, where all cells are occupied by vehicles, so there is no space to move and flow is zero. The density can be easily calculated by dividing the number of cells with 1 (i.e., total number of vehicles, ∑‍si) by the total number of cells (S).(3)ρ=∑siS.The performance of the system can be measured with velocityv∈[0,1], which is simply the number of cells that changed from 0 to 1 over the total number of vehicles:(4)v=∑si′>0∑si,where si′ is the derivative of state si. If si′=1, the cell changed from 0 to 1. If si′=-1, the cell changed from 1 to 0. si′=0 when there is no change in the state of si, that is, there is no vehicle, or the vehicle at si has stopped.The flowJ of the system represents how much of the space is used by moving vehicles. It can be obtained by multiplying the vehicle density by the velocity:(5)J=ρυ.In the ECA rule 184 model of highway traffic, the maximum possible flow isJ=0.5 at a density ρ=0.5. This is because vehicles need at least one cell between them to move. If there are fewer vehicles, the flow will be lower, since there is no movement in free space. If there are more vehicles, then the flow will also be lower, since stationary vehicles do not move.When coordinating traffic lights, the best performance that can be theoretically achieved would be a system in which each intersection has the best performance possible of an isolated intersection. A lower performance implies that there is interference between traffic lights. Given the properties of our model of city traffic, (6) describe the optimal curves for single intersections of velocity and flow, which depend on the maximum flow Jmax allowed by an intersection:(6)voptim=1ifρ≤JmaxJmaxρifJmax<ρ<1-Jmax1-ρρif1-Jmax≤ρJoptim=ρifρ≤JmaxJmaxifJmax<ρ<1-Jmax1-ρif1-Jmax≤ρ.Ifρ≤Jmax, then the intersection can support a maximum velocity of 1 cells/tick. Following (5), the flow will then be equal to the density ρ, as all vehicles are moving. If Jmax<ρ<1-Jmax, then the flow of the intersection will be restricted by the maximum capacity of the intersection, that is, Jmax. This implies that vehicles will be using the intersection at all times, and the average velocity will be Jmax/ρ. If 1-Jmax≤ρ, the density of the streets is so high that it restricts the flow of vehicles on streets, reducing the flow to 1-ρ and the velocity to (1-ρ)/ρ.Notice that the flow optimumJoptim is symmetric, because there is symmetry in our city traffic model between vehicles (1 s) moving in one direction and spaces (0 s) moving in the opposite direction. This is also observed in the rule 184 model of highway traffic [12].


## 4. Deliberative Self-Organizing Traffic Lights

As an alternative to the limitations of the sensors required originally by the self-organizing method [5], we propose an approach using simple sensors to achieve self-organization. This involves placing at the beginning of each block a computer and a presence sensor which together are calledcomputer-sensor. In the same way, a computer and a traffic light are placed at each intersection which together are calledcomputer-light.Thecomputer-sensor can detect only one vehicle at each time step (see Figure 5), as opposed to detecting several vehicles approaching an intersection at each time step. Thecomputer-sensor that detects vehicles at the beginning of each block builds a virtual environment that simulates the movement of vehicles to predict which vehicles are arriving and leaving the intersection located at the end of the block (downstream). The vehicles simulated in the virtual environment by thecomputer-sensor are calledvirtual vehicles.Figure 5
Thecomputer-sensor shown in (a) is composed of a computer and a sensor which could be a simple camera. The example illustrates possible implementation of the sensor. However, the sensor may be an inductive loop, radar, or infrared sensor. In (b), the image obtained bycomputer-sensor is shown, in which only a car is recognized in the sensing area.
(a)
Computer-sensor
(b)
Top view from the cameraThecomputer-light receives information across a data network from thecomputer-sensors of the neighboring blocks and runs the self-organizing method to control the traffic light.Then, for each block, the system is composed of acomputer-sensor placed before the downstream intersection that sends information to thedownstream computer-light (for rules 1–4) andupstream computer-light (for rules 5 and 6) (see Figure 6).Figure 6
Thecomputer-sensor sends information of the positions of thevirtual vehicles predicted to thedownstream computer-light. Thecomputer-sensor also sends a message to theupstream computer-light to report if a vehicle is stationary in the sensing area. With information from localcomputer-sensors, eachcomputer-light applies the self-organizing method.
(a)
Computer-light
(b)
System componentsIn this work, we use an ECA to simulate the virtual environment. Thevirtual vehicles that are at or aftercomputer-sensor position and before the intersection are part of the set ofvirtual-vehicles-received by the downstream intersection. Thevirtual vehicles that are at or after the intersection and before the position downstreamcomputer-sensor are part of the set ofvirtual-vehicles-sent (see Figure 7).Figure 7
Eachcomputer-sensor uses a local simulation to predict the vehicles between thecomputer-sensor and thedownstream computer-light.This approach compared to the current proposals using sophisticated sensors has the following advantages:(i)
The infrastructure cost is lower because the sensor and detection algorithm are less sophisticated. For example, thecomputer-sensor can be integrated by a Raspberry Pi and an economic camera.(ii)
Privacy is respected because the sensor is directed only to a small sensing area marked on the street. Therefore, users (pedestrians or drivers) and their routes cannot be identified.(iii)
Vehicles do not require GPS (Global Positioning System), RFID (Radio-Frequency Identification), or other technologies to interact with the infrastructure.However, with this approach, a data network for the exchange of information is required. In the case of sophisticated sensors, a data network is not required, as there is no direct communication between intersections, although a network is desirable for system monitoring.In this work, we call the self-organizing method with sophisticated sensors areactive method because it bases its actions on current perceptions. The reactive method only maintains a counter wait time of the stationary vehicles behind a red light; however, it ignores the rest of the historical perceptions. On the other hand, we call self-organizing method with simple sensors adeliberative method because each sensor maintains an internal state that depends on the perceived history and decides whether vehicles are stationary or are approaching in the upstream and downstream intersections.


### 4.1. Deliberative Sensors Algorithm

The algorithm that runs thecomputer-sensor is responsible for simulating the virtual environment with both the information perceived by the sensor and the messages received by thedownstream computer-light. Thecomputer-sensor sends the information to thedownstream computer-light to run the self-organizing traffic lights method. In addition, thecomputer-sensor sends information to theupstream computer-light to indirectly share this information with thecomputer-sensor in the upstream block. The variables used in the algorithm that runs thecomputer-sensor are shown in Notations.When thecomputer-sensor starts its execution, it has no information on the density of vehicles that are on its block, so it assumes the worst case and completely fills the space reserved for the set ofvirtual-vehicles-received in the virtual environment. In addition, thecomputer-sensor initializes the value of variables received and sent to zero. Subsequently, Algorithm 1 is executed at each time step.Algorithm 1:Deliberative sensors algorithm.
(
1
)
s
t
o
p
=
f
a
l
s
e;
(
2
)
s
t
o
p
d
s
t
r
e
a
m
=
f
a
l
s
e
(
3
)
v
e
h
i
c
l
e
s
t
a
t
e
=
I
s
T
h
e
r
e
V
e
h
i
c
l
e
(
);
(
4
)
v
i
r
t
u
a
l
s
t
a
t
e
=
i
s
T
h
e
r
e
V
i
r
t
u
a
l
V
e
h
i
c
l
e
(
);
(
5
)
i
f
v
e
h
i
c
l
e
s
t
a
t
e
=
t
r
u
e
t
h
e
n
(
6
)
i
f
v
i
r
t
u
a
l
s
t
a
t
e
=
f
a
l
s
e
t
h
e
n
(
7
)
s
e
t
V
i
r
t
u
a
l
V
e
h
i
c
l
e
(
);
(
8
)
e
n
d
i
f
(
9
)
v
e
h
i
c
l
e
s
t
o
p
=
S
t
a
t
i
o
n
a
r
y
(
);
(
10
)
i
f
v
e
h
i
c
l
e
s
t
o
p
=
t
r
u
e
t
h
e
n
(
11
)
s
t
o
p
=
t
r
u
e;
(
12
)
e
l
s
e
(
13
)
r
e
c
e
i
v
e
d
=
r
e
c
e
i
v
e
d
+
1;
(
14
)
e
n
d
i
f
(
15
)
e
n
d
i
f
(
16
)
p
a
c
k
a
g
e
1
=
R
e
c
e
i
v
e
s
M
e
s
s
a
g
e
D
o
w
n
s
t
r
e
a
m
C
L
(
);
17
l
i
g
h
t
s
t
a
t
e
=
p
a
c
k
a
g
e
1
.
l
i
g
h
t
s
t
a
t
e;
(
18
)
s
t
o
p
d
s
t
r
e
a
m
=
p
a
c
k
a
g
e
1
.
s
t
o
p
d
s
t
r
e
a
m;
(
19
)
r
e
c
e
i
v
e
d
d
s
t
r
e
a
m
=
p
a
c
k
a
g
e
1
.
r
e
c
e
i
v
e
d
d
s
t
r
e
a
m;
(
20
)
r
e
s
u
l
t
s
=
S
i
m
u
l
a
t
e
V
i
r
t
u
a
l
E
n
v
i
r
o
n
m
e
n
t
l
i
g
h
t
s
t
a
t
e
,
s
t
o
p
d
s
t
r
e
a
m;
(
21
)
i
f
r
e
s
u
l
t
s
.
a
r
r
i
v
e
s
e
n
t
=
t
r
u
e
t
h
e
n
(
22
)
s
e
n
t
=
s
e
n
t
+
1;
(
23
)
e
n
d
i
f
(
24
)
i
f
r
e
s
u
l
t
s
.
s
t
o
p
r
e
c
e
i
v
e
d
=
t
r
u
e
∧
s
t
o
p
=
f
a
l
s
e
t
h
e
n
(
25
)
s
t
o
p
=
t
r
u
e;
(
26
)
e
n
d
i
f
(
27
)
i
f
r
e
s
u
l
t
s
.
s
t
o
p
s
e
n
t
=
t
r
u
e
∧
s
t
o
p
d
s
t
r
e
a
m
=
f
a
l
s
e
t
h
e
n
(
28
)
s
t
o
p
d
s
t
r
e
a
m
=
t
r
u
e;
(
29
)
e
n
d
i
f
(
30
)
l
i
g
h
t
c
h
a
n
g
e
=
L
i
g
h
t
G
r
e
e
n
C
h
a
n
g
e
l
i
g
h
t
s
t
a
t
e;
(
31
)
i
f
l
i
g
h
t
c
h
a
n
g
e
=
t
r
u
e
t
h
e
n
(
32
)
ϵ
=
r
e
c
e
i
v
e
d
d
s
t
r
e
a
m
-
s
e
n
t;
(
33
)
s
e
n
t
=
0;
(
34
)
e
n
d
i
f
(
35
)
r
e
s
u
l
t
s
=
C
o
u
n
t
V
e
h
i
c
l
e
s
V
i
r
t
u
a
l
E
n
v
i
r
o
n
m
e
n
t
(
);
(
36
)
p
a
c
k
a
g
e
2
.
n
=
r
e
s
u
l
t
s
.
n
+
ϵ
(
37
)
p
a
c
k
a
g
e
2
.
m
=
r
e
s
u
l
t
s
.
m
(
38
)
p
a
c
k
a
g
e
2
.
s
t
o
p
=
s
t
o
p
d
s
t
r
e
a
m
(
39
)
S
e
n
d
M
e
s
s
a
g
e
D
o
w
n
s
t
r
e
a
m
C
L
(
p
a
c
k
a
g
e
2
);
(
40
)
p
a
c
k
a
g
e
3
.
s
t
o
p
=
s
t
o
p
(
41
)
p
a
c
k
a
g
e
3
.
r
e
c
e
i
v
e
d
=
r
e
c
e
i
v
e
d
(
42
)
S
e
n
d
M
e
s
s
a
g
e
U
p
s
t
r
e
a
m
C
L
(
p
a
c
k
a
g
e
3
);
(
43
)
p
a
c
k
a
g
e
4
=
R
e
c
e
i
v
e
s
M
e
s
s
a
g
e
U
p
s
t
r
e
a
m
C
L
(
);
(
44
)
i
f
p
a
c
k
a
g
e
4
.
l
i
g
h
t
c
h
a
n
g
e
=
t
r
u
e
t
h
e
n
(
45
)
r
e
c
e
i
v
e
d
=
0;
(
46
)
e
n
d
i
fThe algorithm initializes the values of the variablesstop and stopdstream to false (lines (1)-(2)). If there is a vehicle in the sensing area, the functionIsThereVehicle returns true when such a condition is satisfied and false otherwise (line (3)). If there is avirtual vehicle in the position of the sensing area of the virtual environment, the functionisThereVirtualVehicle returns true when such a condition is satisfied and false otherwise (line (4)). If a vehicle is sensed and thevirtual vehicle is not registered in the corresponding position of the virtual environment, the functionsetVirtualVehicle creates avirtual vehicle in that position (line (7)). The verification is done to prevent the removal of avirtual vehicle and add it again in the same position. A case often occurs when a stationary vehicle in the sensing area is already registered in that position of the virtual environment.The functionStationary checks if there is a stationary vehicle in the sensing area. If such a condition is true, it returns true and false otherwise (line (9)). If the vehicle is stationary, the variable stop is set to true to indicate a stationary vehicle in the sensing area at the beginning of the block. Otherwise, if the vehicle is moving, the variable received is increased by one to indicate that a vehicle is received in the sensing area (line (13)).Thecomputer-sensor through the functionReceivesMessageDownstreamCL receives a package from thedownstream computer-light. The package contains information regarding the status of the traffic light, whether a vehicle is stationary, and the number of vehicles received in the downstream block. Subsequently, the information is set to the variables lightstate, stopdstream, and receiveddstream, respectively (lines (17)–(19)).The functionSimulateVirtualEnvironment simulates in the virtual environment the movement of the vehicles (line (20)):(i)
The movement of each member of the set ofvirtual-vehicles-received is simulated depending on the value of the variable lightstate (red or green) and the position of neighboringvirtual vehicles. If avirtual vehicle received goes through a green light and is at or after the intersection, it becomes part of the set ofvirtual-vehicles-sent.(ii)
The movement of each member of the set ofvirtual-vehicles-sent is simulated depending on the state variable stopdstream (true or false) and the position of neighboringvirtual vehicles. The variable stopdstream is similar to the traffic lights; if stopdstream is true and there arevirtual vehicles in the set ofvirtual-vehicles-sent, thevirtual vehicles cannot advance. If avirtual vehicle reaches the position of thedownstream computer-sensor, thevirtual vehicle is removed from the set ofvirtual-vehicles-sent and the functionSimulateVirtualEnvironment returns a value in the package results to indicate that avirtual vehicle arrived (line (20)).If the simulation registers avirtual vehicle that reaches thedownstream computer-sensor on the set ofvirtual-vehicles-sent, thecomputer-sensor increases the value of the variable sent by one (lines (21)–(23)).If the simulation registers avirtual stationary vehicle in the sensing area and the variable stop has the value false, then the value of the variable stop is set in true because thecomputer-sensor chooses the possibility that an error sensing occurred (lines (24)–(26)).If the virtual simulation registers avirtual stationary vehicle on the set ofvirtual-vehicles-sent and the variable stopdstream has the value false, then the value of the variable stopdstream is set in true because thecomputer-sensor selects the possibility that a sensing error occurred in thedownstream computer-sensor to avoid traffic jams at the intersection (lines (27)–(29)).It should be mentioned that because the overall simulation runs on an ECA, the virtual environment that runs thecomputer-sensor is performed with a local ECA, and considering a perfect sensor, intuitively it is natural to think that the simulation is completely deterministic. However, this is not the case because of the following reasons:(i)
At the beginning of the simulation, thecomputer-sensor has no information so it assumes the worst case and considers that the set ofvirtual-vehicles-received is full. In addition, thecomputer-sensor assumes that no virtual vehicle has been sent. Therefore, the “real” traffic state does not correspond to the state of the local virtual environment of thecomputer-sensor and the algorithm must implement a mechanism to rectify the situation.(ii)
When acomputer-sensor receives a green light, it assumes that the vehicles have started moving. However, in the global simulation, if a vehicle has a green light but there is another vehicle in the transversal direction occupying the intersection, then the vehicle does not advance and the prediction in the virtual environment will be out of phase. Thus, the algorithm should also rectify this situation.(iii)
The sensors may have errors, and consequently some vehicles may not be detected.The functionGreenLightChange determines if the light of thedownstream traffic light turned green and when the condition is true the absolute difference between the number of vehicles received by the downstream block and the number ofvirtual vehicles sent is calculated. Such a difference is set to the variable ϵ (line (32)). If the numbers of vehicles in receiveddstream and number ofvirtual vehicles sent are equal, then the value of the variable ϵ is set to zero because the numbers predicted between vehicles received by thedownstream computer-sensor andvirtual vehicles sent by thecomputer-sensor match. On the other hand, prediction errors occur if the numbers of vehicles received and thevirtual vehicles sent do not match, the value of ϵ is nonzero, and the value of the variable sent is set to zero (lines (32)-(33)).The functionCountVehiclesVirtualEnvironment counts the number ofvirtual vehicles that are received at distance d and distance r from the position of the intersection and set to variables n and m of the data structure results. The data structure results is the value returned by the function (line (35)). Subsequently, a package is created with the data n set to n+ϵ, m set to m, and stop set to stopdstream (lines (36)–(38)). The package is sent by the functionSendMessageDownstreamCL todownstream computer-light (line (39)). Thedownstream computer-light with the information contained in the package applies the method of self-organizing traffic lights.The number ofvirtual vehicles received at distance d and distance r is increased with ϵ to adjust the gap between the number of vehicles received by the downstream block andvirtual vehicles sent. The increase in the number ofvirtual vehicles received gives priority to the block for mitigating two undesirable situations: (1) when the number ofvirtual vehicles sent is lower than the vehicles received, it is inferred that the missing vehicles are still in the previous block; (2) when the number ofvirtual vehicles sent is greater than the vehicles received, it is inferred that there are excess vehicles in the previous block.Thecomputer-sensor through the functionSendMessageUpstreamCL sends a package with the values of the variables stop and received to theupstream computer-light (lines (40)–(42)). The package contains information regarding whether a vehicle is stationary and the number of vehicles received on the block ofcomputer-sensor.Finally, thecomputer-sensor through the functionReceivesMessageUpstreamCL receives a package ofupstream computer-light to report that the light of theupstream traffic light turned green and set the value of the variable received to zero (lines (43)–(46)).A system in the city of Duisburg has been developed with the purpose of predicting the state of the traffic by online simulation ofvirtual vehicles with cellular automata [26, 27]. Like our approach with deliberative traffic lights, in the Duisburg system, it is necessary to place sensors (inductive cycles) on the roads to detect the presence of the vehicles. However, unlike deliberative traffic lights, the Duisburg system has a centralized approach because one computer collects all the information obtained by the sensors and another computer executes the simulation on a global level. Our approach with deliberative traffic lights, by contrast, is distributed because eachcomputer-sensor collects the information and simulates the corresponding traffic only in its block, that is, at the local level. Deliberative traffic lights have the advantage that if acomputer-sensor fails, it does not imply that the entire system collapses, which does occur in the Duisburg system when the computer that collects the information from the sensors or the computer that performs the simulation fails.In addition, the online simulation of the Duisburg system aims to plan routes according to the state of the predicted traffic which will be sent to the driver. On the other hand, with the deliberative traffic lights, the simulation of eachcomputer-sensor has the objective of managing the traffic light.


## 4.1. Deliberative Sensors Algorithm

The algorithm that runs thecomputer-sensor is responsible for simulating the virtual environment with both the information perceived by the sensor and the messages received by thedownstream computer-light. Thecomputer-sensor sends the information to thedownstream computer-light to run the self-organizing traffic lights method. In addition, thecomputer-sensor sends information to theupstream computer-light to indirectly share this information with thecomputer-sensor in the upstream block. The variables used in the algorithm that runs thecomputer-sensor are shown in Notations.When thecomputer-sensor starts its execution, it has no information on the density of vehicles that are on its block, so it assumes the worst case and completely fills the space reserved for the set ofvirtual-vehicles-received in the virtual environment. In addition, thecomputer-sensor initializes the value of variables received and sent to zero. Subsequently, Algorithm 1 is executed at each time step.Algorithm 1:Deliberative sensors algorithm.
(
1
)
s
t
o
p
=
f
a
l
s
e;
(
2
)
s
t
o
p
d
s
t
r
e
a
m
=
f
a
l
s
e
(
3
)
v
e
h
i
c
l
e
s
t
a
t
e
=
I
s
T
h
e
r
e
V
e
h
i
c
l
e
(
);
(
4
)
v
i
r
t
u
a
l
s
t
a
t
e
=
i
s
T
h
e
r
e
V
i
r
t
u
a
l
V
e
h
i
c
l
e
(
);
(
5
)
i
f
v
e
h
i
c
l
e
s
t
a
t
e
=
t
r
u
e
t
h
e
n
(
6
)
i
f
v
i
r
t
u
a
l
s
t
a
t
e
=
f
a
l
s
e
t
h
e
n
(
7
)
s
e
t
V
i
r
t
u
a
l
V
e
h
i
c
l
e
(
);
(
8
)
e
n
d
i
f
(
9
)
v
e
h
i
c
l
e
s
t
o
p
=
S
t
a
t
i
o
n
a
r
y
(
);
(
10
)
i
f
v
e
h
i
c
l
e
s
t
o
p
=
t
r
u
e
t
h
e
n
(
11
)
s
t
o
p
=
t
r
u
e;
(
12
)
e
l
s
e
(
13
)
r
e
c
e
i
v
e
d
=
r
e
c
e
i
v
e
d
+
1;
(
14
)
e
n
d
i
f
(
15
)
e
n
d
i
f
(
16
)
p
a
c
k
a
g
e
1
=
R
e
c
e
i
v
e
s
M
e
s
s
a
g
e
D
o
w
n
s
t
r
e
a
m
C
L
(
);
17
l
i
g
h
t
s
t
a
t
e
=
p
a
c
k
a
g
e
1
.
l
i
g
h
t
s
t
a
t
e;
(
18
)
s
t
o
p
d
s
t
r
e
a
m
=
p
a
c
k
a
g
e
1
.
s
t
o
p
d
s
t
r
e
a
m;
(
19
)
r
e
c
e
i
v
e
d
d
s
t
r
e
a
m
=
p
a
c
k
a
g
e
1
.
r
e
c
e
i
v
e
d
d
s
t
r
e
a
m;
(
20
)
r
e
s
u
l
t
s
=
S
i
m
u
l
a
t
e
V
i
r
t
u
a
l
E
n
v
i
r
o
n
m
e
n
t
l
i
g
h
t
s
t
a
t
e
,
s
t
o
p
d
s
t
r
e
a
m;
(
21
)
i
f
r
e
s
u
l
t
s
.
a
r
r
i
v
e
s
e
n
t
=
t
r
u
e
t
h
e
n
(
22
)
s
e
n
t
=
s
e
n
t
+
1;
(
23
)
e
n
d
i
f
(
24
)
i
f
r
e
s
u
l
t
s
.
s
t
o
p
r
e
c
e
i
v
e
d
=
t
r
u
e
∧
s
t
o
p
=
f
a
l
s
e
t
h
e
n
(
25
)
s
t
o
p
=
t
r
u
e;
(
26
)
e
n
d
i
f
(
27
)
i
f
r
e
s
u
l
t
s
.
s
t
o
p
s
e
n
t
=
t
r
u
e
∧
s
t
o
p
d
s
t
r
e
a
m
=
f
a
l
s
e
t
h
e
n
(
28
)
s
t
o
p
d
s
t
r
e
a
m
=
t
r
u
e;
(
29
)
e
n
d
i
f
(
30
)
l
i
g
h
t
c
h
a
n
g
e
=
L
i
g
h
t
G
r
e
e
n
C
h
a
n
g
e
l
i
g
h
t
s
t
a
t
e;
(
31
)
i
f
l
i
g
h
t
c
h
a
n
g
e
=
t
r
u
e
t
h
e
n
(
32
)
ϵ
=
r
e
c
e
i
v
e
d
d
s
t
r
e
a
m
-
s
e
n
t;
(
33
)
s
e
n
t
=
0;
(
34
)
e
n
d
i
f
(
35
)
r
e
s
u
l
t
s
=
C
o
u
n
t
V
e
h
i
c
l
e
s
V
i
r
t
u
a
l
E
n
v
i
r
o
n
m
e
n
t
(
);
(
36
)
p
a
c
k
a
g
e
2
.
n
=
r
e
s
u
l
t
s
.
n
+
ϵ
(
37
)
p
a
c
k
a
g
e
2
.
m
=
r
e
s
u
l
t
s
.
m
(
38
)
p
a
c
k
a
g
e
2
.
s
t
o
p
=
s
t
o
p
d
s
t
r
e
a
m
(
39
)
S
e
n
d
M
e
s
s
a
g
e
D
o
w
n
s
t
r
e
a
m
C
L
(
p
a
c
k
a
g
e
2
);
(
40
)
p
a
c
k
a
g
e
3
.
s
t
o
p
=
s
t
o
p
(
41
)
p
a
c
k
a
g
e
3
.
r
e
c
e
i
v
e
d
=
r
e
c
e
i
v
e
d
(
42
)
S
e
n
d
M
e
s
s
a
g
e
U
p
s
t
r
e
a
m
C
L
(
p
a
c
k
a
g
e
3
);
(
43
)
p
a
c
k
a
g
e
4
=
R
e
c
e
i
v
e
s
M
e
s
s
a
g
e
U
p
s
t
r
e
a
m
C
L
(
);
(
44
)
i
f
p
a
c
k
a
g
e
4
.
l
i
g
h
t
c
h
a
n
g
e
=
t
r
u
e
t
h
e
n
(
45
)
r
e
c
e
i
v
e
d
=
0;
(
46
)
e
n
d
i
fThe algorithm initializes the values of the variablesstop and stopdstream to false (lines (1)-(2)). If there is a vehicle in the sensing area, the functionIsThereVehicle returns true when such a condition is satisfied and false otherwise (line (3)). If there is avirtual vehicle in the position of the sensing area of the virtual environment, the functionisThereVirtualVehicle returns true when such a condition is satisfied and false otherwise (line (4)). If a vehicle is sensed and thevirtual vehicle is not registered in the corresponding position of the virtual environment, the functionsetVirtualVehicle creates avirtual vehicle in that position (line (7)). The verification is done to prevent the removal of avirtual vehicle and add it again in the same position. A case often occurs when a stationary vehicle in the sensing area is already registered in that position of the virtual environment.The functionStationary checks if there is a stationary vehicle in the sensing area. If such a condition is true, it returns true and false otherwise (line (9)). If the vehicle is stationary, the variable stop is set to true to indicate a stationary vehicle in the sensing area at the beginning of the block. Otherwise, if the vehicle is moving, the variable received is increased by one to indicate that a vehicle is received in the sensing area (line (13)).Thecomputer-sensor through the functionReceivesMessageDownstreamCL receives a package from thedownstream computer-light. The package contains information regarding the status of the traffic light, whether a vehicle is stationary, and the number of vehicles received in the downstream block. Subsequently, the information is set to the variables lightstate, stopdstream, and receiveddstream, respectively (lines (17)–(19)).The functionSimulateVirtualEnvironment simulates in the virtual environment the movement of the vehicles (line (20)):(i)
The movement of each member of the set ofvirtual-vehicles-received is simulated depending on the value of the variable lightstate (red or green) and the position of neighboringvirtual vehicles. If avirtual vehicle received goes through a green light and is at or after the intersection, it becomes part of the set ofvirtual-vehicles-sent.(ii)
The movement of each member of the set ofvirtual-vehicles-sent is simulated depending on the state variable stopdstream (true or false) and the position of neighboringvirtual vehicles. The variable stopdstream is similar to the traffic lights; if stopdstream is true and there arevirtual vehicles in the set ofvirtual-vehicles-sent, thevirtual vehicles cannot advance. If avirtual vehicle reaches the position of thedownstream computer-sensor, thevirtual vehicle is removed from the set ofvirtual-vehicles-sent and the functionSimulateVirtualEnvironment returns a value in the package results to indicate that avirtual vehicle arrived (line (20)).If the simulation registers avirtual vehicle that reaches thedownstream computer-sensor on the set ofvirtual-vehicles-sent, thecomputer-sensor increases the value of the variable sent by one (lines (21)–(23)).If the simulation registers avirtual stationary vehicle in the sensing area and the variable stop has the value false, then the value of the variable stop is set in true because thecomputer-sensor chooses the possibility that an error sensing occurred (lines (24)–(26)).If the virtual simulation registers avirtual stationary vehicle on the set ofvirtual-vehicles-sent and the variable stopdstream has the value false, then the value of the variable stopdstream is set in true because thecomputer-sensor selects the possibility that a sensing error occurred in thedownstream computer-sensor to avoid traffic jams at the intersection (lines (27)–(29)).It should be mentioned that because the overall simulation runs on an ECA, the virtual environment that runs thecomputer-sensor is performed with a local ECA, and considering a perfect sensor, intuitively it is natural to think that the simulation is completely deterministic. However, this is not the case because of the following reasons:(i)
At the beginning of the simulation, thecomputer-sensor has no information so it assumes the worst case and considers that the set ofvirtual-vehicles-received is full. In addition, thecomputer-sensor assumes that no virtual vehicle has been sent. Therefore, the “real” traffic state does not correspond to the state of the local virtual environment of thecomputer-sensor and the algorithm must implement a mechanism to rectify the situation.(ii)
When acomputer-sensor receives a green light, it assumes that the vehicles have started moving. However, in the global simulation, if a vehicle has a green light but there is another vehicle in the transversal direction occupying the intersection, then the vehicle does not advance and the prediction in the virtual environment will be out of phase. Thus, the algorithm should also rectify this situation.(iii)
The sensors may have errors, and consequently some vehicles may not be detected.The functionGreenLightChange determines if the light of thedownstream traffic light turned green and when the condition is true the absolute difference between the number of vehicles received by the downstream block and the number ofvirtual vehicles sent is calculated. Such a difference is set to the variable ϵ (line (32)). If the numbers of vehicles in receiveddstream and number ofvirtual vehicles sent are equal, then the value of the variable ϵ is set to zero because the numbers predicted between vehicles received by thedownstream computer-sensor andvirtual vehicles sent by thecomputer-sensor match. On the other hand, prediction errors occur if the numbers of vehicles received and thevirtual vehicles sent do not match, the value of ϵ is nonzero, and the value of the variable sent is set to zero (lines (32)-(33)).The functionCountVehiclesVirtualEnvironment counts the number ofvirtual vehicles that are received at distance d and distance r from the position of the intersection and set to variables n and m of the data structure results. The data structure results is the value returned by the function (line (35)). Subsequently, a package is created with the data n set to n+ϵ, m set to m, and stop set to stopdstream (lines (36)–(38)). The package is sent by the functionSendMessageDownstreamCL todownstream computer-light (line (39)). Thedownstream computer-light with the information contained in the package applies the method of self-organizing traffic lights.The number ofvirtual vehicles received at distance d and distance r is increased with ϵ to adjust the gap between the number of vehicles received by the downstream block andvirtual vehicles sent. The increase in the number ofvirtual vehicles received gives priority to the block for mitigating two undesirable situations: (1) when the number ofvirtual vehicles sent is lower than the vehicles received, it is inferred that the missing vehicles are still in the previous block; (2) when the number ofvirtual vehicles sent is greater than the vehicles received, it is inferred that there are excess vehicles in the previous block.Thecomputer-sensor through the functionSendMessageUpstreamCL sends a package with the values of the variables stop and received to theupstream computer-light (lines (40)–(42)). The package contains information regarding whether a vehicle is stationary and the number of vehicles received on the block ofcomputer-sensor.Finally, thecomputer-sensor through the functionReceivesMessageUpstreamCL receives a package ofupstream computer-light to report that the light of theupstream traffic light turned green and set the value of the variable received to zero (lines (43)–(46)).A system in the city of Duisburg has been developed with the purpose of predicting the state of the traffic by online simulation ofvirtual vehicles with cellular automata [26, 27]. Like our approach with deliberative traffic lights, in the Duisburg system, it is necessary to place sensors (inductive cycles) on the roads to detect the presence of the vehicles. However, unlike deliberative traffic lights, the Duisburg system has a centralized approach because one computer collects all the information obtained by the sensors and another computer executes the simulation on a global level. Our approach with deliberative traffic lights, by contrast, is distributed because eachcomputer-sensor collects the information and simulates the corresponding traffic only in its block, that is, at the local level. Deliberative traffic lights have the advantage that if acomputer-sensor fails, it does not imply that the entire system collapses, which does occur in the Duisburg system when the computer that collects the information from the sensors or the computer that performs the simulation fails.In addition, the online simulation of the Duisburg system aims to plan routes according to the state of the predicted traffic which will be sent to the driver. On the other hand, with the deliberative traffic lights, the simulation of eachcomputer-sensor has the objective of managing the traffic light.


## 5. Results

To test the green wave and the reactive and deliberative self-organizing traffic lights methods, we constructed a hundred-by-hundred homogeneous street grid with alternating flow directions and cyclic boundaries. In our green wave method, the cycleT=85. The length of each street is 1,700 cells, that is, 8,500 meters (each cell is five meters). Every block has a distance of 16 cells (without the intersection). Thus, there are 80 simulated meters between streets (similar to streets in Manhattan). In the grid there are 330,000 cells, 10,000 intersections, and 200 streets (50 in each cardinal direction). It is worth mentioning that Manhattan has approximately 3,360 intersections, so the simulated city is about three times the size of Manhattan.The experiments consist in running the simulation with 50 different densities for the green- and the reactive and deliberative self-organizing methods. For each density, ten runs were executed and the results were averaged. Each run consisted of the following: there is an initial state where vehicles are placed randomly and homogeneously. Then, half an hour (5,400 ticks) is simulated. After these initial 5,400 ticks, the system is considered to have stabilized, that is, gone through a transient, so another half hour is simulated, where the velocity is measured at every tick. At the end of the simulation, the velocities of the second half hour are averaged to obtain the average velocityv and average flow J. The results are shown in Figure 8.Figure 8
The reactive and deliberative self-organizing methods achieve good performance for all densities compared to the green wave method. Both self-organizing methods are close to the optimality curves (see (6)).
(a)
Flow
(b)
VelocityTable1 shows the values of the parameters used by the self-organizing methods, as proposed in [4].Table 1
Parameters used by the self-organizing method [4]. The size of each block is 80 meters.
Variable
Abstract value
Scaled value
Description
Δt
1 tick
1/3 s
Time step in the simulation.
d
10 cells
50 m
Distance where the vehicles are detected approaching the intersection.
r
5 cells
25 m
Short distance where the vehicles are detected approaching the intersection.
e
3 cells
15 m
Distance where stationary vehicles are detected.
u
10 ticks
3.33 s
Minimum waiting time behind a red light.
w
600 ticks
200 s
Maximum waiting time behind a red light.
n
40 veh⋅ticks
13.33 veh⋅s
Accumulated number of vehicles at distanced.
m
2 vehicles
2 vehicles
Number of vehicles at distancer.The simulator with which we performed our experiments was developed in the C language. The reader is invited to access the code athttps://github.com/Zapotecatl/Traffic-Light.In the green wave method, we found the following phases:(i)
Theintermittent phase is between ρ>0 and ρ⪅0.22. At this phase, some vehicles are stationary behind a red light. The phase transition lies at ρ≈0.22, where there is a maximum flow of J≈0.17 (see Figure 8).(ii)
Thegridlock phase is presented for densities ρ⪆0.22; vehicles flowing on streets with green wave (southbound and eastbound) cannot keep the velocity of the green wave, so traffic jams move in the opposite direction of the flow. The queues of vehicles and platoons groups waiting behind a red light grow in opposite directions of the green wave and block intersections. Consequently, gridlocks occur (see Figure 8).For the reactive and deliberative self-organizing methods, we found the following phases:(i)
Thefree-flow phase is presented only for very low densities in the reactive and deliberative self-organizing methods in 0<ρ⪅0.000006, where v=1 and no vehicle has to stop. It should be noted that this phase almost disappeared because of the introduction of a maximum time w in rule 2. Nevertheless, this phase does not exist in realistic scenarios, as it requires periodic boundaries and no turning vehicles.(ii)
Thequasi-free-flow phase is presented in the reactive and deliberative self-organizing method in 0.000006<ρ⪅0.12, where few vehicles stop for little time. Most intersections have only one platoon requesting a green light, so this one is able to flow without having to stop, unless another platoon is crossing at the same time.(iii)
Theintermittent underutilized phase is presented in the reactive and deliberative self-organizing method between ρ≈0.12 and ρ≈0.22, where intersections are idling some of the time; that is, no vehicle uses them. The difference with thequasi-free-flow phase is that in theunderutilized intermittent phase there are two platoons requesting a green light in most of the cases. Thus, one platoon has to wait until the other one crosses.(iv)
Thequasi-full capacity intermittent phase is presented in the reactive and deliberative self-organizing methods between ρ≈0.22 and ρ≈0.4. There are always two platoons requesting a green light; however, there is a certain probability that the platoons are of different sizes. The smallest platoons generate lower demand and lead to idle intersections.(v)
Thefull capacity intermittent phase is presented in the reactive and deliberative self-organizing method between ρ≈0.4 and ρ≈0.68 with a maximum flow J≈0.257. This implies that the intersections are being used at full capacity. In thefull capacity intermittent phase there are no resources “lost” of free space because the intersections are being used constantly; that is, there are always vehicles crossing all intersections.(vi)
Theoverutilized intermittent phase is presented in the reactive and deliberative self-organizing methods between ρ≈0.68 and ρ≈0.8, where the density is such that rule 6 sometimes forces both directions to stop, thus reducing the flow of the intersections. This phase is similar to theunderutilized intermittent phase in the sense that the intersections cannot be used at their full flow capacity. In theunderutilized intermittent case, this is because there are no enough vehicles. In theoverutilized intermittent case, by contrast, this is because there are too many vehicles and intersections need to wait before one street can get a green light.(vii)
Thequasi-gridlock phase is presented in the reactive and deliberative self-organizing methods between ρ≈0.8 and ρ<1.0. Most vehicles are stationary, but free spaces move in the direction opposite of the vehicles between traffic jams at a velocity of one cell per tick.(viii)
Thegridlock phase is presented for high densities in the reactive and deliberative self-organizing method in ρ=1.0; that is, v=0. The vehicles cannot move because the density is too high and intersections are blocked from initial conditions.


### 5.1. Errors on Sensors

Each sensor has associated a probabilityP that represents the precision to detect vehicles, for example, if P=0.9 sensor will detect 90% of vehicles. This probability of precision is implemented within the functionIsThereVehicle. Therefore, in the reactive self-organizing method, the functionIsThereVehicle is called to verify the k cells contained within the sensing zone between the distances d and e. Moreover, in the case of deliberative self-organizing method, the functionIsThereVehicle is called once because the sensing area is only formed by a cell. In addition, at the time a vehicle is no longer detected by the sensor, the vehicle will remain imperceptible throughout its entire trajectory in the sensing area.The experiment consists in executing the simulation with six different degrees of sensor precisionP, 1.0, 0.9, 0.8, 0.7, 0.6, and 0.5, to evaluate the robustness of reactive and deliberative self-organizing methods against errors sensing.The configuration used for each run is the same as the experiments of the previous section to evaluate the performance of the three methods to control traffic lights. The results of the self-organizing reactive approach compared to the self-organizing deliberative method are shown in Figure9.Figure 9
Flow-density diagrams for different error rates.P represents the accuracy of the sensor.
(a)
Reactive self-organizing
(b)
Deliberative self-organizingThe simulation results with sensors to different levels of precision show that the deliberative self-organizing approach is more robust to sensing errors. This is because the deliberative method maintains the state of the environment in memory and sensing error only affects a cell. On the other hand, in the traditional approach, the state of the system is not maintained and the error is distributed in all cells because it is inherent in the sensing area. Therefore, the reactive method has no way to recover and requires a high degree of precision of the sensor because even when the precision of sensor is 90%, the flow collapses.


## 5.1. Errors on Sensors

Each sensor has associated a probabilityP that represents the precision to detect vehicles, for example, if P=0.9 sensor will detect 90% of vehicles. This probability of precision is implemented within the functionIsThereVehicle. Therefore, in the reactive self-organizing method, the functionIsThereVehicle is called to verify the k cells contained within the sensing zone between the distances d and e. Moreover, in the case of deliberative self-organizing method, the functionIsThereVehicle is called once because the sensing area is only formed by a cell. In addition, at the time a vehicle is no longer detected by the sensor, the vehicle will remain imperceptible throughout its entire trajectory in the sensing area.The experiment consists in executing the simulation with six different degrees of sensor precisionP, 1.0, 0.9, 0.8, 0.7, 0.6, and 0.5, to evaluate the robustness of reactive and deliberative self-organizing methods against errors sensing.The configuration used for each run is the same as the experiments of the previous section to evaluate the performance of the three methods to control traffic lights. The results of the self-organizing reactive approach compared to the self-organizing deliberative method are shown in Figure9.Figure 9
Flow-density diagrams for different error rates.P represents the accuracy of the sensor.
(a)
Reactive self-organizing
(b)
Deliberative self-organizingThe simulation results with sensors to different levels of precision show that the deliberative self-organizing approach is more robust to sensing errors. This is because the deliberative method maintains the state of the environment in memory and sensing error only affects a cell. On the other hand, in the traditional approach, the state of the system is not maintained and the error is distributed in all cells because it is inherent in the sensing area. Therefore, the reactive method has no way to recover and requires a high degree of precision of the sensor because even when the precision of sensor is 90%, the flow collapses.


## 6. Discussion

In our green wave method, the cycleT controls the synchronization of the traffic light with the travel time of vehicles around the torus. This synchronization is achieved in our model if the street length is a multiple of T, a condition for free-flow. Otherwise, the cycle of the traffic light and the travel time of the vehicles are out of synchrony. Thus, vehicles need to wait for a green light and the average velocity is less than one. We contrast the green wave method using the same settings in section 5 (Results) applying a global cycle T=85 with the green wave method applying a local cycle Ti at each traffic light set in a random value in the range of [2,T]. The lower limit of the range is 2 so as to give at least one time step for the green light and one time step for the red light. When the value of T is not the same for all traffic lights, there is no coordination between traffic lights and the flow is reduced because the movement of the vehicles is interfered by red lights (see Figure 10).Figure 10
Flow-density and velocity-density diagrams for green wave with the same global cycleT and a local cycle in the range of [2,T].
(a)
Flow
(b)
VelocityOur deliberative self-organizing algorithm bases its performance on the precision of thecomputer-sensor to detect and predict the movement of the vehicles in its block. However, if our ACE model allows vehicles to turn, thecomputer-sensor receives information from another block, a situation for which the deliberative self-organizing algorithm is not designed. In addition, when a vehicle tries to turn to enter a transverse street that is saturated, the flow stops because the vehicle obstructs the intersection and there is only one lane. The flow is not released until there is a space in the street where the vehicle is trying to enter or the vehicle decides to continue in the same direction in which it was.Approximately 20% of the vehicles turn into important avenues. However, the percentage is different depending on the topology of each city. In order to explore the effects produced in the reactive and deliberative self-organizing algorithm with the previously mentioned situations, we did an experiment consisting in varying the probability that a vehicle decides to turn at an intersection atp=0.0,0.1,0.2,0.3 (see Figure 11). The case with p=0 is relevant for its quasi symmetry and for the identification of phase transitions. A greater probability will cause more vehicles to attempt to enter other transversal streets, but there will also be a greater probability that such vehicles will again decide to change direction and continue their travel in the direction in which they were.Figure 11
Flow-density and velocity-density diagrams for different probabilities of turn in the reactive and deliberative algorithm.
(a)
Reactive self-organizing
(b)
Deliberative self-organizingFigure11 shows that the flow decreases in the deliberative and reactive self-organizing algorithm when vehicles turn. When the density is increased, the possibility that a vehicle tries to enter a transverse street that is saturated is greater and therefore the flow is reduced.Although our deliberative self-organizing algorithm was designed with the restriction that vehicles can only go in one direction, when vehicles are allowed to turn, the algorithm shows a similar performance to that of the reactive self-organizing algorithm. A future extension to our deliberative self-organizing algorithm is to delegate to thecomputer-light the responsibility of applying or not applying the compensation (through epsilon) to mitigate the prediction errors. For example, if an intersection has horizontaldownstream computer-light with a missing vehicle but in the verticaldownstream computer-light there is a surplus vehicle, thecomputer-light infers that a vehicle turns and would not apply compensations.Our experiments with errors on sensors show that a convenient strategy when sensors fail more than 10% is that the traffic lights apply the green wave method because it has a better performance in that case.


## 7. Conclusions

All major cities suffer from traffic jams. Technological improvements such as the one presented here can increase the capacity of urban infrastructure. However, if it becomes very efficient to travel by private vehicle, more people will be inclined to do so, increasing density and eventually decreasing traffic flow. This means that improvements to traffic infrastructure can actually generate a worse situation than the one they are trying to solve [28, 29]. For this reason, an integrated transportation plan is required to balance the demands and improvements over all transportation modes.Our city traffic model [13] is more useful for descriptive than predictive purposes. Its vehicle-space duality (both occupy the same space) yields symmetry in the flow optimality curves. Its simplicity allows the clear identification of phase transitions. We have also worked with realistic city traffic models [30, 31], obtaining similar results. We are in the process of developing a more realistic city traffic model to bridge both lines of research.It is clear that adaptive algorithms will outperform traditional static methods [32], as it was shown here. It is also important to develop robust methods, and the deliberative sensors achieve a considerable improvement over sophisticated sensors. In the performed experiments, 30% failure rate of the deliberative sensors performed better than 10% failure rate with sophisticated sensors.Sophisticated sensors could be improved to increase their robustness, for example, adding more cameras or processing, but this would increase their cost even more. As sensor technology evolves, probably it will be common to deploy robust and cheap sensors in cities in the near future. There might be other ways to increase the robustness of this approach, but its exploration is beyond the scope of this work.Considering the recent progress made in the development of autonomous vehicles [33, 34], decentralized algorithms such as the ones presented here will be useful in the coordination of autonomous vehicles at intersections as well.



---

*Source: 7691370-2017-05-30.xml*