# Deep Reinforcement Learning for Traffic Light Control in Intelligent
Transportation Systems

Xiao-Yang Liu+, , Ming Zhu+∗, , Sem Borst, ,
and Anwar Walid +Equal contribution.∗Corresponding author.X.-Y. Liu is with
the Department of Electrical Engineering, Columbia University, New York, NY
10027, USA E-mail<EMAIL_ADDRESS>Zhu was supported by National
Natural Science Foundations of China (Grant No. 61902387).M. Zhu is with the
Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences,
Shenzhen 518055, China. E-mail<EMAIL_ADDRESS>Borst and A.
Walid are with Nokia Bell Labs<EMAIL_ADDRESS>anwar.walid@nokia-bell-
labs.com.

###### Abstract

Smart traffic lights in intelligent transportation systems (ITSs) are
envisioned to greatly increase traffic efficiency and reduce congestion. Deep
reinforcement learning (DRL) is a promising approach to adaptively control
traffic lights based on the real-time traffic situation in a road network.
However, conventional methods may suffer from poor scalability. In this paper,
we investigate deep reinforcement learning to control traffic lights, and both
theoretical analysis and numerical experiments show that the intelligent
behavior “greenwave” (i.e., a vehicle will see a progressive cascade of green
lights, and not have to brake at any intersection) emerges naturally a grid
road network, which is proved to be the optimal policy in an avenue with
multiple cross streets. As a first step, we use two DRL algorithms for the
traffic light control problems in two scenarios. In a single road
intersection, we verify that the deep Q-network (DQN) algorithm delivers a
thresholding policy; and in a grid road network, we adopt the deep
deterministic policy gradient (DDPG) algorithm. Secondly, numerical
experiments show that the DQN algorithm delivers the optimal control, and the
DDPG algorithm with passive observations has the capability to produce on its
own a high-level intelligent behavior in a grid road network, namely, the
“greenwave” policy emerges. We also verify the “greenwave” patterns in a
$5\times 10$ grid road network. Thirdly, the “greenwave” patterns demonstrate
that DRL algorithms produce favorable solutions since the “greenwave” policy
shown in experiment results is proved to be optimal in a specified traffic
model (an avenue with multiple cross streets). The delivered policies both in
a single road intersection and a grid road network demonstrate the scalability
of DRL algorithms.

###### Index Terms:

Traffic light control, intelligent transportation systems, Markov Decision
Process (MDP), deep reinforcement learning, scalability, greenwave, high-level
intelligent behavior.

##  I Introduction

Smart traffic lights play an important role in intelligent transportation
systems (ITSs) [1, 2, 3, 4], since they may greatly increase traffic
efficiency and reduce congestion. According to a report [5], the annual cost
caused by traffic congestion in the US has grown from $75 billion in 2000 to
$179 billion in 2017. Vehicles’ energy consumption and emission at road
intersections are highly related to the control policies of traffic lights
[6]. Deep reinforcement learning (DRL) [7, 8, 9] is a promising approach to
adaptively adjust the control policies of traffic lights according to the
real-time traffic situation, e.g., the traffic throughput in each road.

Conventional methods for traffic light control may suffer from poor
scalability. 1) Classic optimization based methods [10, 11, 12, 13, 14, 15,
16, 17, 18, 19] make decisions based on parameters calculated from traffic
data, and heuristic rules obtained from expert knowledge. The number of
parameters is also large if the road network is large, requiring a large
amount of computing resource and leading to poor scalability. These heuristic
rules are based on experiences, and may not cover all cases in complicated
traffic scenarios, lacking flexibility. For example, in Maxband [12], all
intersections should share the same cycle length, which is the maximum cycle
lengths of all intersections; and in Max-pressue [14], the pressure (the total
queue length on incoming approaches minus the outgoing approaches) is only
calculated when the current phase time is larger than the minimum phase
duration length, which is set by expert knowledge. 2) The problem of adaptive
traffic light control can be formulated as a Markov Decision Process (MDP)
[20, 21, 22], since the effects of a control action depend only on that state
and not on the prior history. Conventional MDP-based methods such as value
iteration, policy iteration and dynamic programming can obtain the optimal
policy for relatively small-scale problems. However, the state-action space
grows exponentially with the number of road intersections, becoming infeasible
in a large road network. 3) Some DRL algorithms such as the deep Q-network
(DQN) algorithm are not scalable either. The actions in the DQN algorithm are
discrete. When the number of road intersections increases [8, 23], the number
of Q-values to be estimated increases exponentially. It is not practical to
approximate such a large number of Q-values. Therefore, some DRL algorithms
such as DQN may not produce a feasible solution in a large road network.

Deep reinforcement learning algorithms [24, 25] may not obtain a favorable
solution in traffic light control. Neural networks are used to approximate the
Q-function [26] and/or policy; however, they are black-box and have poor
interpretation. Neural networks receive states (e.g., the number of waiting
cars in each road, and the traffic light configure) and actions (e.g.,
“continuing” or “switching”), and produce the estimated Q-values without
offering any interpretation. There is no guarantee for DRL to which stochastic
gradient descent methods converge. In another word, whether the output action
produces the maximum Q-value over all actions in a state is not guaranteed.
Moreover, over-fitting or under-fitting may occur. Therefore, the estimated
Q-values may not be accurate, and the output action may not produce the
maximum Q-value.

In this paper, we investigate deep reinforcement learning approaches to
control traffic lights, and analyze their performance. In a single road
intersection, we demonstrate that the policies obtained by the DQN algorithm
matches the optimal control obtained by a conventional MDP approach. In a grid
road network, we adopt the deep deterministic policy gradient (DDPG)
algorithm; and it is not practical to obtain the optimal policy by
conventional MDP approaches since the state-action space is too large; and we
prove that the intelligent behavior “greenwave” (i.e., a vehicle will see a
progressive cascade of green lights, and does not have to brake at any
intersection) is theoretically optimal in a specified traffic model. Numerical
results show that the “greenwave” policy emerges by applying the DDPG
algorithm, confirming its ability to produce the high-level intelligent
behavior.

Our main contributions can be summarized as follows:

  * $\bullet$

We use two DRL algorithms for the traffic light control problems in two
scenarios. In a single road intersection, we verify that the deep Q-network
(DQN) algorithm delivers a thresholding policy, which matches the optimal
control; and in a grid road network, we adopt the deep deterministic policy
gradient (DDPG) algorithm.

  * $\bullet$

Numerical experiments show that the DDPG algorithm with passive observations
has the capability to produce on its own a high-level intelligent behavior in
a grid road network, namely, the “greenwave” policy emerges. We also examine
the “greenwave” patterns.

  * $\bullet$

The “greenwave” patterns delivered by the DDPG algorithm demonstrate that DRL
algorithms produce favorable solutions since the “greenwave” policy is optimal
in a specified traffic model (an avenue with multiple cross streets). The
policies both in a single road intersection and a grid road network
demonstrate the scalability of DRL algorithms in solving traffic light control
problems.

Figure 1: An intersection with two traffic flows (left), and the corresponding
state-transition diagram (right).

The remainder of the paper is organized as follows. Section II describes the
related works. Section III gives a detailed description of the road
intersection model and the problem statement. Section IV provides
specification of DRL algorithms for a single intersection as well as a grid
road network. Section V evaluates the performance of the proposed DRL
algorithms and illustrates the emergence of “greenwave” patterns. Section VI
concludes this paper.

##  II Related Works

Existing works on traffic light control can be classified into two categories,
conventional methods and DRL methods.

###  II-A Conventional Methods

Traffic light control is in fact a mixed-integer linear programming problem
[27] that is NP-hard. Traffic light control heavily relies on accurate traffic
parameters such as the vehicles’ position and speed. Conventional techniques
measure them using sensors [28, 29, 30], e.g., infrared sensors and inductive
loop detectors. To collect the traffic data and compute policies for plenty of
intersections in real-time, high data transmission rate and enough computing
resource are required. Techniques such as wireless communications [31, 32] and
edge cloud computing [33] can significantly improve the data transmission rate
and computing efficiency. Conventional methods mainly include classic
optimization based methods [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
evolutionary algorithms [34, 35, 36], and fuzzy logic [37, 38].

Classic optimization based methods [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
usually adjust the cycle time and the phase splits based on parameters and
heuristic rules. The time for green light is usually longer than needed, which
causes a large amount of wasted time for waiting cars or pedestrians.

  * $\bullet$

Methods for single road intersection. The Webster method calculates the
desired cycle length, and then calculates the green time splits, which are
proportional to the ratios of critical lane volumes over each phase. Hofri _et
al._[19] proposed a thresholding policy for a single road intersection with
two queues, which depends on the traffic flow data and simulation experiments;
however, it may not be available in all real traffic situations.

  * $\bullet$

Methods for multiple road intersections. Both GreenWave [11] and Maxband [12]
methods aim to reduce the number of stops for vehicles; however, GreenWave
only optimizes only one direction, and Maxband optimizes two opposite
diretions. Both GreenWave and Maxband require the same cycle length for all
intersections. In the self-organizing traffic light (SOTL) [13] method, the
requests for a green signal from the current phase and other competing phases
are measured, and then certain rules are built to make decisions (“continuing”
or “switching”). Its performance is highly dependent on the rules. In the Max-
pressure [14] method, the pressure of all phases is calculated, and then
choose the phase with the maximum pressure. In the Sydney coordinated adaptive
traffic system (SCATS) [15] method, the degree of saturation (DS), i.e., the
ratio of effective green time to the available green time, for each phase in
the current signal plan is calculated, and then the DSs for other signal plans
are calculated, and finally the plan with the minimum total DS is selected. To
reduce the large fluctuations of traffic flows, Lammer _et al._[17] proposed a
method to adjust the duration and the order of green phases, which reaches the
stabilization of queues and red-time duration.

These methods have poor scalability. If the road network is large, the number
of parameters is also large, leading to much time spent on parameter
calculating and tuning. Moreover, heuristic rules and some parameters are
highly based on expert knowledge without optimality gurantee.

Evolutionary algorithms [39, 40] especially genetic algorithms are usually
used in multi-objective optimization, e.g., fuel consumption, number of stops,
traffic flow throughput, and vehicles’ waiting time [34, 35, 36]. In theory,
these algorithms are based on the concept of survival of the fittest through
stochastic optimization and heuristics. Take genetic algorithms as an example.
The solutions are encoded as chromosomes, and in the next generation, through
reproduction, crossover, and a very small probability of mutation, new
offsprings are generated, and the ones with large fit values will survive. In
this way, in each generation or iteration, the solutions move nearer to the
local or even global optimal points. Brian _et al._[36] proposed a genetic
algorithm to minimize fuel consumption, emission, delay and number of stops.
Turky _et al._[35] used a genetic algorithm to dynamically control the red and
green duration to optimize the vehicle and the pedestrian flow throughput.
However, the performance of genetic algorithms may depend on some parameters
such as the population size, the number of generations, and the mutation
probability, and there is no performance guarantee. For example, genetic
algorithms may not obtain successful solutions if the population size is
small. Therefore, evolutionary algorithms may obtain an unfavorable solution
within limited time.

Fuzzy logic [37, 38] can be used in traffic light control problems, since the
ambiguity in the linguistic terms (e.g., low-, medium- and high-speed) can be
represented using fuzzy sets. To compensate the traffic flow fluctuation, Ali
_et al._[37] used fuzzy logic to monitor and handle the alternation of the
traffic condition between two successive cycles. Hawi _et al._[38] used fuzzy
logic and wireless sensor networks to control traffic lights, where wireless
sensor networks collect traffic data in real-time and fuzzy logic outputs the
order of the green light assignment with traffic quantity and waiting time as
the input. In the above methods, designing the fuzzy logic needs high human
expertise and regular updating of rules, and generally accurate reasoning
cannot be given. Moreover, the performance depends on the heuristic rules and
parameters, and there is no guarantee of stability or optimality.

###  II-B Deep Reinforcement Learning Methods

DRL methods have various formulations, including state, action, and reward,
leading to various results. Based on formulations, DRL algorithms are applied,
and these algorithms are classified into single-agent and multi-agent ones.

First, we discuss DRL formulations.

  * $\bullet$

State formulation. The state is generally the combinations of the following
items: queue length [41], waiting time [42], volume [43] (number of vehicles
on the lane/road), delay [44] (realistic travel time minus the expected travel
time), speed, phase duration (of the current phase) [45], congestion [46]
(denoted by 0/1 or the congestion level), and image or matrix [47, 48]
(demonstrating positions of vehicles, where “0” denotes absence and “1”
denotes presence), etc. There is a trend of using image/matrix as the state
recent years; however, the dimension of state is very large, e.g., more than
one thousand, which leads to long training time.

  * $\bullet$

Action formulation. The action generally has four types: set current phase
duration [49], set phase ratio [50], continuing/switching [51], and select the
next phase [52]. The former two types of actions are continuous, and the
latter two ones are discrete. Selecting the next phase is more flexible since
the traffic light does not need to change cyclically. Here, we select
continuing/switching, since it is comprehensive.

  * $\bullet$

Reward formulation. The action generally includes the following items: queue
length [41], waiting time [51], throughput [49], speed [51], and pressure [53]
(the number of incoming vehicles minus the outgoing ones). Some research works
use a weighted linear combination of the above items as reward. The tuning of
weights is an important issue, and minor changes for weights may lead to very
different results. To avoid this case, we only select queue length as the
reward.

Secondly, we discribe single-agent and multi-agent DRL approaches. In single-
agent DRL approaches, the agent learns the Q-value for all actions of each
state, and chooses the action with maximum approximated Q-value on that state.
Through a bootstrap learning process, the agent obtains a policy for an end-
to-end task with raw input data. These methods are only applied in small or
medium-sized road networks due to poor scalability. DQN and its variants [25,
8] are commonly used methods. Liang _et al._[8] proposed to use the dueling
double DQN with prioritized experience replay to decide the traffic signal
duration. The single-agent DRL methods have a global view of the traffic
situations; however, they may not be practical in very large-scale road
networks.

In multi-agent DRL approaches [54, 42, 55, 56, 57, 58], each agent controls a
traffic light in an intersection, and also considers the states and actions of
its neighborhoods to cooperate with them. The sum of weighted reward of
neighbor agents plus its own is then treated as a global reward. Liu _et
al._[56] proposed a cooperative Q-learning with a function approximation
algorithm so that each local intersection can cooperatively make decisions
without any central supervising agents. Chu _et al._[42] proposed an actor-
critic based multi-agent DRL method to stabilize the learning procedure,
improve the observability and reduce the learning difficulty. Xu _et al._[55]
proposed a multi-agent DRL approach to optimize the signal timing plans at
intersections. Wu _et al._[54] proposed a multi-agent DDPG method for traffic
light control, where long short-term memory (LSTM) [59] is used to improve the
stability of the environment caused by partial observable state. Multi-agent
DRL methods can control traffic lights in a cooperative way among agents in a
very large-scale road network. However, these methods generally may not have a
global view of the traffic situations needed for the favorable control policy.
Moreover, how to balance the utilities of an agent and its neighborhoods is
also a hard problem.

The above DRL algorithms use the black-box neural networks to fit the
Q-function, and stochastic gradient descent methods to minimize the non-convex
loss function. These methods cannot provide guarantee the scalablity. In DQN
methods, the number of approximated Q-values under each state over all actions
increases exponentially with the increasing of the number of road
intersections. The DQN algorithm needs too much computing resource and time to
estimate the Q-values in a large road network, leading to the poor
scalability. Multi-agent DRL methods such as multi-agent DDPG [54] also may
not guarantee for the scalability, since they are black-box and the optimal
policy may not be obtained.

Different from the existing methods, we apply DRL methods, namely, DQN and
DDPG, to optimize the control policy for traffic lights in a single road
intersection and a grid road network, respectively. Considering that the DQN
algorithm has poor scalability, it is only used in a single road intersection.
Considering that the DDPG algorithm can handle complicated scenarios using
continuous actions, it is used in a grid road network. We obtain the optimal
policy in a single road intersection using a conventional method, and obtains
the optimal policy in a grid road network under specified traffic model, i.e.,
“greenwave” policy. Simulation results show that the DQN algorithm delivers
the optimal control, and the proposed DDPG algorithm produces a high-level
intelligent behavior in real-time, i.e., the “greenwave” pattern emerges.

##  III Model Description and Problem Formulation

In this section, we present the models and optimization goals for single and
multiple traffic lights. For the ease of exposition, we consider an admittedly
stylized model which captures the most essential features governing the
dynamics of traffic flows at road intersections. Our central aim is to broadly
explore the performance and scalability of DRL algorithms in optimizing real-
time control policies, rather than to develop a practical policy for a
specific instance. Thus, we adopt a discrete-time formulation to simplify the
description and allow conventional MDP techniques for comparison. The methods
and results can naturally extend to continuous-time operation.

###  III-A Model for Single Traffic Light

Figure 2: Illustration of a road network with grid topology.

We start with a single intersection scenario to facilitate the validation of
DRL algorithms. We consider the simplest meaningful setup with two
intersecting unidirectional traffic flows as schematically depicted in the
left part of Fig. 1. We assume two directions with 1 and 2 denoting a west-to-
east direction (avenue) and a north-to-south direction (cross street),
respectively. Therefore, there are two traffic flows denoted by 1 and 2. The
state $S(t)$ at the beginning of time slot $t$ may be described by the three-
tuple $(X_{1}(t),X_{2}(t);L(t))$, with $X_{i}(t),~{}i\in\\{1,2\\}$ denoting
the number of vehicles of traffic flow $i$ waiting to pass the intersection
and $L(t)\in\\{0,1,2,3\\}$ denoting the configuration of the traffic lights:

  * $\bullet$

“0”, i.e., ‘green’: green light for flow $1$ (avenue) and hence red light for
flow $2$ (cross street);

  * $\bullet$

“1”, i.e., ‘yellow’: yellow light for flow $1$ (avenue) and hence red light
for flow $2$ (cross street);

  * $\bullet$

“2”, i.e., ‘red’: red light for flow $1$ (avenue) and hence green light for
flow $2$ (cross street);

  * $\bullet$

“3”, i.e., ‘orange’: red light for flow $1$ (avenue) and hence yellow light
for flow $2$ (cross street).

Each configuration $L(t)$ can either be simply continued in the next time slot
or otherwise be switched to the natural subsequent configuration $(L(t)+1)\mod
4$. This is determined by the action $A(t)\in\\{0,1\\}$ selected at the end of
time slot $t$, which is represented by a binary variable: “0” for continuing,
and “1” for switching. Then we have

$L(t+1)=(L(t)+A(t))\mod 4.$ (1)

These rules give rise to a strictly cyclic control sequence as illustrated in
the right part of Fig. 1.

The evolution of the queue state over time is governed by the recursion

$\begin{split}&(X_{1}(t+1),X_{2}(t+1))\\\
&=(X_{1}(t)+C_{1}(t)-D_{1}(t),X_{2}(t)+C_{2}(t)-D_{2}(t)),\end{split}$ (2)

with $C_{i}(t)$ denoting the number of vehicles of traffic flow $i$ appearing
at the intersection during time slot $t$ and $D_{i}(t)$ denoting the number of
departing vehicles of traffic flow $i$ crossing the intersection during time
slot $t$. We make the simplified assumption that if a traffic flow is granted
the green light, exactly one waiting vehicle, if any, will cross the
intersection during that time slot, i.e.,

$\begin{split}D_{1}(t)&=\min\\{1,X_{1}(t)\\},~{}~{}\text{if}~{}L(t)=0,\\\
D_{1}(t)&=0,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}L(t)\neq
0;\\\ D_{2}(t)&=\min\\{1,X_{2}(t)\\},~{}~{}\text{if}~{}L(t)=2,\\\
D_{2}(t)&=0,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}L(t)\neq
2.\end{split}$ (3)

###  III-B Model for Multiple Traffic Lights

To examine the scalability property of DRL algorithms in more complex
scenarios, we consider a grid road network as depicted in Fig. 2.
Specifically, we investigate a grid road network with $N$ intersections and
bidirectional traffic flows, representing an avenue with multiple cross
streets. We do not account for any traffic flows making left or right turns,
since the model could be easily generalized to accommodate it. The state
$S(t)$ at the beginning of time slot $t$ may be described by a $(5\,N)$-tuple
$(X_{n1}(t),X_{n2}(t),X_{n3}(t),X_{n4}(t);L_{n}(t))_{n\in\\{1,...,N\\}}$. The
first four components denote the number of vehicles waiting to cross the
$n$-th intersection with 1, 2, 3, and 4 denoting the west-to-east, north-to-
south, east-to-west, and south-to-north directions, respectively. The last
component $L_{n}(t)\in\\{0,1,2,3\\}$ indicates the configuration of the
traffic light at the $n$-th intersection similar as before:

$L_{n}(t+1)=(L_{n}(t)+A_{n}(t))\mod 4,$ (4)

with $A_{n}(t)\in\\{0,1\\}$ denoting the action selected for the $n$-th road
intersection at the end of time slot $t$. The evolution of the various queue
states is determined by the recursion

$X_{ni}(t+1)=X_{ni}(t)+C_{ni}(t)-D_{ni}(t),$ (5)

with $C_{ni}(t)$ denoting the number of vehicles in direction $i$ appearing at
the $n$-th intersection during time slot $t$ and $D_{ni}(t)$ denoting the
number of vehicles in direction $i$ crossing the $n$-th intersection during
time slot $t$, $i\in\\{1,...,4\\}$, $n\in\\{1,...,N\\}$. Note that

$\begin{split}&D_{n1}(t)=\min\\{1,X_{n1}(t)\\},~{}~{}D_{n3}(t)=\min\\{1,X_{n3}(t)\\},\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}L_{n}(t)=0,\\\
&D_{n1}(t)=0,~{}~{}D_{n3}(t)=0,~{}\,\text{if}~{}L_{n}(t)\neq 0;\\\
&D_{n2}(t)=\min\\{1,X_{n2}(t)\\},~{}~{}D_{n4}(t)=\min\\{1,X_{n4}(t)\\},\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}L_{n}(t)=2,\\\
&D_{n2}(t)=0,~{}~{}D_{n4}(t)=0,~{}\,\text{if}~{}L_{n}(t)\neq 2.\end{split}$
(6)

Algorithm 1: Environment simulation (one step) for a single road intersection
or a grid road network
---
1: Select action $a$ according to line 3 in Alg. 2 [a single road
intersection] or line 3 in Alg. 3 [a grid road network];
2: Generate random variables $C_{1}$, $C_{2}$ [a single road intersection] or
$C_{n1}$, $C_{n3}$ and $C_{n2}$, $C_{n4}$ for all $n\in\\{1,...,N\\}$
[a grid road network];
3: Execute action $a$, determine the new queue states and traffic light states
$X_{1}^{\prime},X_{2}^{\prime},L^{\prime}$ according to (1) $\sim$ (3)
[a single road intersection] or $X^{\prime}_{n1},X^{\prime}_{n2}$,
$X^{\prime}_{n3},X^{\prime}_{n4}=0$; $L^{\prime}_{n}=0$ for all
$n\in\\{1,...,N\\}$ according to (4) $\sim$ (6)
[a grid road network];
4: Calculate the reward $r=-(|X_{1}^{\prime}|^{2}+|X_{2}^{\prime}|^{2})$ [a
single road intersection] or
$r=-\sum_{n=1}^{N}\sum_{i=1}^{4}|X_{ni}^{\prime}|^{2}$
[a grid road network];
5: Update states: $X_{1}=X_{1}^{\prime},X_{2}=X_{2}^{\prime},L=L^{\prime}$ [a
single road intersection] or $X_{n1}=X^{\prime}_{n1},X_{n2}=X^{\prime}_{n2}$,
$X_{n3}=X^{\prime}_{n3},$
$X_{n4}=X^{\prime}_{n4}$, $L_{n}=L^{\prime}_{n}$ for all $n\in\\{1,...,N\\}$
[a grid road network].
Algorithm 2: DQN for a single road intersection
---
1: Initialize $X_{1}=X_{2}=0,L=0$, action-value $Q$ with random weights
$\theta_{0}$, batch size $M$, number of time steps $K$,
and replay buffer $D$;
2: for steps $k=1,\dots,K$
3: Select $a=\arg\underset{\bar{a}\in\mathcal{A}}{\max}~{}Q(s,\bar{a})$ with
probability $1-\epsilon$ or a random action $a$ with probability $\epsilon$;
4: Execute action $a$, get new state
$s^{\prime}=[X_{1}^{\prime},X_{2}^{\prime};L^{\prime}]$ and reward $r$ from
Alg. 1;
5: Store transition $(s,a,r,s^{\prime})$ in replay buffer $D$;
6: Sample a mini-batch of $M$ transitions
$\\{(s^{j}_{t},a^{j}_{t},r^{j}_{t},s^{j}_{t+1})\\}_{j}$;
7: Update the networks using Adam optimizer:
$\nabla_{\theta_{k}}\text{Loss}(\theta_{k})=\mathbb{E}_{s^{j}_{t},a^{j}_{t},r^{j}_{t},s^{j}_{t+1}}\bigg{[}(r+\gamma\max_{a^{j}_{t+1}}\big{(}Q(s^{j}_{t+1},a^{j}_{t+1}|\theta_{k-1})\big{)}-Q(s^{j}_{t},a^{j}_{t}|\theta_{k}))\nabla_{\theta_{k}}Q(s^{j}_{t},a^{j}_{t}|\theta_{k})\bigg{]}$.

###  III-C Objective Function for Optimization

We assume that the “congestion cost” in time slot $t$ may be expressed as a
function of the queue state. A quadratic function $Z(X(t))$ is applied to
formulate the congestion cost. In the single road intersection scenario,
$X(t)=(X_{1}(t),X_{2}(t))$, and $Z(X(t))=X_{1}^{2}(t)+X_{2}^{2}(t)$. In the
grid road network with $N$ intersections,
$X(t)=(X_{n1}(t),X_{n2}(t),X_{n3}(t),X_{n4}(t))_{n\in\\{1,...,N\\}}$, and
$Z(X(t))=\sum_{n=1}^{N}\sum_{i=1}^{4}X_{ni}^{2}(t)$.

The optimization goal is to find a dynamic control policy which selects
actions over time slots $\\{0,1,...,T\\}$ to minimize the long-term expected
discounted cost $\mathbb{E}\left[\sum_{t=0}^{T}\gamma^{t}Z(X(t))\right]$, with
$\gamma\in(0,1]$ representing a discount factor.

##  IV Deep Reinforcement Learning Algorithms

Algorithm 3: DDPG for a grid road network
---
1: Initialize batch size $M$, number of time steps $K$, and replay buffer $D$,
the actor and the critic’s online networks
($\mu(s|\theta^{\mu})$ and $Q(s,a|{\theta^{Q}})$) with parameters
$\theta^{\mu}$ and $\theta^{Q}$, and target networks
($\mu^{\prime}(s|\theta^{\mu^{\prime}})$ and
$Q^{\prime}(s,a|\theta^{Q^{\prime}})$) with parameters;
$\theta^{\mu^{\prime}}$ and $\theta^{Q^{\prime}}$, queue states and traffic
light states: $X_{n1},X_{n2}$, $X_{n3},X_{n4}=0$; $L_{n}=0$ for all
$n\in\\{1,...,N\\}$;
2: For steps $k=1,\dots,K$
3: Choose action $a=\mu(s|\theta^{\mu})+\mathcal{N}$, where $\mathcal{N}$ is
Gaussian noise;
4: Execute action $a$, get new state $s^{\prime}=[X_{n1},X_{n2}$,
$X_{n3},X_{n4};L_{n}]$ for all $n\in\\{1,...,N\\}$ and reward $r$ from Alg. 1;
5: Store transition $(s,a,r,s^{\prime})$ in memory;
6: Sample a mini-batch of $M$ transitions
$\\{(s^{j}_{t},a^{j}_{t},r^{j}_{t},s^{j}_{t+1})\\}_{j}$;
7: Calculate the target Q-value: $y^{j}=r^{j}_{t}+\gamma
Q^{\prime}(s^{j}_{t+1},\mu^{\prime}(s^{j}_{t+1}|\theta^{\mu^{\prime}})|\theta^{Q^{\prime}})$;
8: Update the critic’s online Q-network $Q$ by minimizing the loss function:
$\nabla_{\theta^{Q}}\text{Loss}_{t}(\theta^{Q})=\nabla_{\theta^{Q}}[\frac{1}{M}\sum^{M}_{j=1}(y^{j}-Q(s^{j}_{t},a^{j}_{t}|\theta^{Q}))^{2}]$;
9: Update the actor’s online policy network with the sampled policy gradient
by the chain rule:
$\mathbb{E}_{s_{t}}[\nabla_{\theta^{\mu}}Q(s,a|\theta^{Q})|_{s=s_{t},a=\mu(s_{t}|\theta^{\mu})}]=\mathbb{E}_{s_{t}}[\nabla_{a}Q(s,a|\theta^{Q})|_{s=s_{t},a=\mu(s_{t})}\nabla_{\theta^{\mu}}\mu(s|\theta^{\mu})|_{s=s_{t}}]$;
10: Update the critic’s target Q-network $Q^{\prime}$ and actor’s target
policy network $\mu^{\prime}$:
$\theta^{Q^{\prime}}\leftarrow\tau\theta^{Q}+(1-\tau)\theta^{Q^{\prime}}$,
$\theta^{\mu^{\prime}}\leftarrow\tau\theta^{\mu}+(1-\tau)\theta^{\mu^{\prime}}$
with $\tau\ll 1$.

In this section, we first show a brief description of the reinforcement
learning and Q-Learning. Then we propose two deep reinforcement learning
schemes, DQN [25] and DDPG [60] algorithms in different scenarios. We use the
DQN algorithm in a single road intersection in Fig. 1. While we use the DDPG
algorithm in a grid road network in Fig. 2. The DDPG algorithm applies the
actor-critic framework in continuous action space. The traffic lights’ actions
in our experiments are discrete, i.e., $A(t)\in\\{0,1\\}$, thus we apply a
discretization process to the conventional DDPG algorithm. Finally, we
demonstrate that the ”greenwave” control policy is optimal in a grid road
network.

###  IV-A Reinforcement Learning and Q-Learning

Definition of cost function. We define a discounted congestion cost over time
slots $\\{0,1,...,T\\}$ of a road intersection under policy $\pi$ with the
discount factor $\gamma$

$V_{\pi}=-\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T}\gamma^{t}|X(t)|^{2}\right],$
(7)

where $|X(t)|^{2}\overset{\text{def}}{=}|X_{1}(t)|^{2}+|X_{2}(t)|^{2}$ in a
single intersection or
$|X(t)|^{2}\overset{\text{def}}{=}\sum_{n=1}^{N}\sum_{i=1}^{4}|X_{ni}(t)|^{2}$
in a grid road network. The optimization goal in Subsection III-C is to
minimize the long-term expected queue length, thus we take the negative value
to be consistent with the maximization operation. The optimal policy
$\widehat{\pi}$ satisfies

$V_{\widehat{\pi}}=-\sup\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T}\gamma^{t}|X(t)|^{2}\right].$
(8)

Combining the Bellman optimality equation [61] and
$V_{\widehat{\pi}}=-\max\mathbb{E}[\sum_{t=0}^{T}\gamma^{t}|X(t)|^{2}]$, we
derive the following equation

$V_{\widehat{\pi}}=\max\\{r_{t}+\gamma\max\sum_{k=1}^{T-t}\gamma^{k-1}r_{t+k}\\},$
(9)

where $r_{t}=-|X(t)|^{2}$. We define $Q(s,a)$ to be the maximum achievable
expected discounted reward (or minimum discounted congestion cost in our
context) under the optimal policy starting from state $s=(X;L)$ when action
$a$ is taken. $Q(s,a)$ satisfies the equation

$\begin{split}Q(s,a)&=r(s,a)+\gamma\sum\limits_{s^{\prime}\in\mathcal{S}}p(s,s^{\prime};a)~{}\max\limits_{a^{\prime}\in\mathcal{A}}~{}Q(s^{\prime},a^{\prime})\\\
&=r(s,a)+\gamma\mathbb{E}\left[\underset{a^{\prime}\in\mathcal{A}}{\max}~{}Q(s^{\prime},a^{\prime})\right],\end{split}$
(10)

with $r(s,a)=-Z(X)$ denoting the reward (i.e., negative congestion cost) in
queue state $X$, and $p(s,s^{\prime};a)$ denoting the transition probability
from state $s$ to state $s^{\prime}$ when action $a$ is taken.

###  IV-B DQN for Single Road Intersection

In the DQN algorithm [62], the neural network takes the state and action as
the input, and the action-value as the output. Compared with traditional
Q-learning algorithms, the neural network of DQN is used as a function
approximator to estimate the action-value function. The neural network is
trained by adjusting its parameters in each iteration to reduce the mean-
squared error in the Bellman equation.

In addition, the DQN algorithm uses an experience replay buffer to update
network parameters. It has two advantages: 1) enabling the stochastic gradient
decent algorithm [63]; and 2) removing the correlations between consecutive
transitions.

We simulate the environment using use Alg. 1. Line 1 selects an action
according to DRL algorithms. Line 2 generates the number of arrival vehicles
of each traffic flow. Line 3 calculates new queue states and traffic light
states. Line 4 calculates the reward. Finally, line 5 updates all states.

Alg. 2 shows the details of the DQN for a single road intersection. Line 1 is
the initialization. Lines 2 $\sim$ 7 are a $K$-step loop of the train process.
Line 3 determines the action. Line 4 executes the action, and updates the new
queue states and traffic light states, and get the reward. Line 5 stores the
state transition. Line 6 samples a mini-batch of transitions, and line 7
updates the networks.

###  IV-C Scalable DDPG for Grid Road Network

The DDPG algorithm [60] applies neural networks, i.e., a critic and an actor,
to approximate the action-value and action policy, respectively. The critic
takes the state and action as the input, and action-value as the output. The
actor takes the state as the input, and the action policy as the output. This
actor-critic approach has two advantages: 1) it uses neural networks as
approximators, essentially compressing the state and action space to much
smaller latent parameter space, and 2) the gradient descent method can be used
to update the network weights, which greatly speeds up the convergence and
reduces the training time. Therefore, the memory and computational resources
are largely saved. The DDPG algorithm has shown impressive and powerful skills
in AlphaGo zero [64] and Atari game playing [65].

Besides the actor-critic approach, the DDPG algorithm mainly uses three
techniques to solve MDP problems: experience replay buffer, soft update, and
exploration noise. The experience replay buffer stores transitions just as
described in the DQN algorithms. Soft update with a low learning rate is
introduced to improve the stability of learning. Exploration noise is added to
the actor’s target policy to obtain a new exploration policy, which helps to
explore the other space to get better policy.

The DDPG algorithm is first trained offline using memory as the sample pool.
In the training process, the DDPG algorithm samples transitions online, and
trains the agent on collected data offline in memory for further learning. The
networks are updated with the Adam optimizer [66] gradient-descent. In the
test process, the DDPG algorithms run in an online form without the
exploration noise.

The conventional DDPG algorithm has a continuous action space, while the
traffic control actions in our model are discrete, i.e.,
$A_{n}(t)\in\\{0,1\\}$. Therefore, we apply a discretization process to
transform the continuous outputs of the actor network to discrete ones. A
modified sigmoid function is added to the output layer of actor network as
activation:

$\widehat{y}=\text{sigmoid}(\widehat{\alpha}\,\widehat{x}),$ (11)

where $\widehat{x},\widehat{y}$ are inputs and outputs of the final layer, and
$\widehat{\alpha}$ is the ratio for steepening the sigmoid function. Combining
the modified sigmoid activation function with a node-wise binarization
process, our discrete DDPG algorithm can reduce the errors caused by the
continuous-to-discrete transformation to a great degree.

To converge to a favorable strategy in a grid road network, we set the number
of cars and traffic light states at all intersections as inputs in DDPG. Let’s
take intersection $n$ as an example. The number of cars on each queue is
$[X_{n1},X_{n2},X_{n3},X_{n4}]$, and a light state is $L_{n}$. The observation
tuple $S=[X_{n1},X_{n2},X_{n3},X_{n4},L_{n}]$ is a quintuple, which is also
the inputs of both the critic’s online Q-network and the actor’s online policy
network.

Alg. 3 shows the details of DDPG for a grid road network. Line 1 is the
initialization. In the following for-loop (line 2 $\sim$ 6), we train the
policy. Line 3 chooses an action based on the actor’s online policy network
and the exploration noise. Line 4 executes the action and gets the new state
and reward. Line 5 stores the state transition. Line 6 samples a mini-batch of
transitions. Line 7 calculate the target Q-value, and line 8 updates the
critic’s online Q-network. Line 9 updates the actor’s online policy network.
Line 10 updates the critic’s target Q-network $Q^{\prime}$ and actor’s target
policy network $\mu^{\prime}$ based on their online networks, respectively.

###  IV-D Optimality of the “Greenwave” Policy

In this subsection, we demonstrate the optimality of the “greenwave” control
policy in a grid road network with symmetric fluid traffic.

To obtain the optimal policy in a grid road network, we first obtain the
optimal policy in a single intersection, and then extend it to a grid road
network to obtain the “greenwave” policy.

In a single intersection scenario, the optimal policy is a “thresholding
policy” [19]. The traffic light changes only when the difference between two
queue lengths reaches a critical value.

In the grid road network scenario, we assume there is an avenue (i.e., an
artery road) with multiple cross streets. We imagine that all the
intersections constitute a large “intersection”. The “greenwave” policy is
defined as follows: the traffic lights simultaneously change only when the
difference between the avenue’s queue length and the cross streets’ queue
length reaches a critical value. For a vehicle in the avenue, it will see a
progressive cascade of green lights, and not have to brake at any
intersection. Therefore, this control policy is called “greenwave”. The
“greenwave” policy achieves the optimality in a grid road network (an avenue
with multiple cross streets). The detailed proof is moved to the appendix.

##  V Performance Evaluation

Figure 3: Performance of DQN control policy (left), fixed-cycle policy
(middle), and the optimal policy (right) for single intersection. Tests of 300
steps in simulation are shown with average reward and number of waiting cars.
Better policies are supposed to reduce the numbers of waiting cars. The DQN
algorithm matches the optimal policy.

Figure 4: Comparison for a single intersection with different car
arrival/passing ratio.

Figure 5: Stabilization of a single intersection with large initial queue
length.

Figure 6: DDPG policy for a grid road network with $5\times 10$ intersections.

In this section, we first show experiment settings, and then present the
results in a single road intersection, and finally demonstrate the results in
a grid road network, especially the emergence of “greenwave” patterns.

###  V-A Experiment Settings

In the experiments, we apply a 2-layer fully-connected neural network in DQN
in the single intersection scenario, with size 400 and tanh as activation
function. For the grid road network scenario, we apply a 4-layer fully-
connected neural network in DDPG with size 600 for both the actor and critic.
The actor needs to output near-binary values as action values, therefore, it
has one modified sigmoid activation function for the last output layer; while
the critic network has no activation function for the last output layer.

The outputs of the actor network are clipped to binary values 0 and 1
indicating the traffic light state continuing and switching. We take an
episode length of 150 steps of simulation for collecting the learning samples,
and train both actor and critic networks with a batch size of 64 and $\gamma$
= 0.99. The Ornstein-Uhlenbeck noise [67] with variance 0.3 is applied for
explorations.

The implementation of our algorithms uses the deep learning framework
TensorFlow [68]. Our simulations are executed on a server with Linux OS, 200
GB memory, two Intel(R) Xeon(R) Gold 5118<EMAIL_ADDRESS>GHz, a Tesla V100-PCIE
GPU.

Let’s discuss the traffic environment settings. The vehicle arrival rate
indicates the number of vehicles arriving from outside of the road networks
into the road networks on each intersection per time slot, which is set to be
a random value with upper bound $C_{a}$ for avenue or $C_{c}$ for cross
streets; and the vehicle passing rates represents the number of vehicles
passing one intersection within one time step, and set to be fixed number of
16 and 4 for avenue and cross streets, respectively. The arrival/passing ratio
is the ratio of arrival rate to passing rate. The comparison of average queue
length (averaged sum of queueing cars on all roads over time) in a single
intersection with respect to the arrival/passing ratio for different policies
is shown in Fig. 5.

###  V-B Verifying Optimal Control in Single Road Intersection

As an initial validation benchmark, we first consider a single road
intersection scenario as described in Subsection III-A. The reason for
considering this toy scenario is that the state-action space is sufficiently
small and the optimal policy can be computed using a conventional MDP approach
such as policy iteration. We assume the numbers of arriving vehicles of both
traffic flows in each time step are represented by the random variables, which
are independent and Bernoulli distributed with parameter $P=0.25$.

In the single intersection, the optimal policy is a “thresholding policy”
[19]. And the optimal policy can be obtained using the policy iteration
algorithm by the MDP toolbox [69], which is a “thresholding policy” [19].
Comparisons of the policies derived by the DQN algorithm, the fixed-cycle
policy, and the optimal policy, are shown in Fig. 3. The result of the DQN
policy coincides with that of the optimal policy. The training time using DQN
is very short and can be ignored, since the state-action space is too small in
a single road intersection. In particular, they match the optimal performance
and exhibit a similar thresholding structure. This structural property was
established in [19] for a strongly related two-queue dynamic optimization
problem (with switch-over costs rather than switch-over times). Fig. 5
explores the effects of different arrival/passing ratio. As the car
arrival/passing ratio increases, the queue length also increases. And the
policy learned by DQN shows better effects than the fixed-cycle policy. Fig. 5
studies the stabilization with large initial queue lengths. The
arrival/passing ratio is 0.5. The policy learned by DQN shows capability of
stabilizing the traffic.

###  V-C “Greenwave” in Grid Road Network

We now turn to a grid road network as Fig. 2. This is a more challenging
scenario. It serves to examine the scalability properties of our DDPG
algorithm. Moreover, it has more highly complex interactions arising from the
vehicle flow along the avenue.

We assume the numbers of arriving vehicles in eastern and western direction
for the avenue in each time step are represented by random variables, which
are independent and Bernoulli distributed with parameter $P_{1}=0.5$. The
numbers of arriving vehicles in southern and northern directions on each of
the $N$ cross streets in each time step are represented by random variables,
which are independent and Bernoulli distributed with parameter $P_{2}=0.25$.
Next, we evaluate the performance in a 5 $\times$ 10 grid road network.

The car numbers with time steps are shown in Fig. 6. The conventional MDP
approach such as policy iteration is computationally infeasible due to the
state-action space explosion, and hence whether our algorithm is favorable
cannot be assessed quantitatively. Therefore, we examine qualitative features
to validate the intelligent behavior and evaluate its performance merit. In
particular, we observe the emergence of “greenwave” patterns, even though such
structural features are not explicitly prescribed in the optimization process.
This emergent intelligence confirms the capability of our algorithms to learn
favorable structural properties solely from passive observations.

##  VI Conclusion

We have explored the potential for deep Q-network (DQN) and deep deterministic
policy gradient (DDPG) algorithms to optimize real-time traffic light control
policies in a single road intersection and a grid road network. As an initial
benchmark, we established that the policy obtained from the DQN algorithm
matches the optimal policy achieved by a conventional MDP approach in a single
intersection. We subsequently evaluated the scalability of the DDPG algorithm
in a grid road network, and demonstrated the emergence of the high-level
intelligent behavior named as “greenwave” policies, confirming its ability to
learn desirable structural features. We also theoretically proved that the
“greenwave” policy is the optimal control policy under a specified traffic
flow model (an avenue with multiple cross streets). The “greenwave” patterns
demonstrate that DRL algorithms output favorable solutions in a grid road
network.

In future research, we will consider the traffic flows with stochastic
arrivals and departures of vehicles among all areas of a road network, and we
intend to investigate locality properties and analyze how to design
distributed coordination schemes for wide-scale deployment scenarios using new
techniques, e.g., multi-agent DRL algorithms, hierarchical DRL algorithms, and
edge computing.

## References

  * [1] W. Hong, G. Tao, H. Wang, and C. Wang, “Traffic signal control with adaptive online-learning scheme using multiple-model neural networks,” IEEE transactions on neural networks and learning systems (TNNLS), 2022.
  * [2] F.-X. Devailly, D. Larocque, and L. Charlin, “Ig-rl: Inductive graph reinforcement learning for massive-scale traffic signal control,” IEEE Transactions on Intelligent Transportation Systems (TITS), 2021.
  * [3] M. M. Vazifeh, P. Santi, G. Resta, S. Strogatz, and C. Ratti, “Addressing the minimum fleet problem in on-demand urban mobility,” Nature, vol. 557, no. 7706, p. 534, 2018.
  * [4] M. Zhu, X.-Y. Liu, F. Tang, M. Qiu, R. Shen, W. Shu, and M.-Y. Wu, “Public vehicles for future urban transportation,” IEEE Transactions on Intelligent Transportation Systems (TITS), vol. 17, no. 12, pp. 3344–3353, 2016\.
  * [5] “New study underscores economy / traffic jam link.” https://mobility.tamu.edu/umr/media-information/press-release/, 2021.
  * [6] T.-Q. Tang, Z.-Y. Yi, and Q.-F. Lin, “Effects of signal light on the fuel consumption and emissions under car-following model,” Elsevier Physica A: Statistical Mechanics and its Applications, vol. 469, pp. 200–205, 2017.
  * [7] Y. Liu, S. Liu, Y. Wang, F. Lombardi, and J. Han, “A survey of stochastic computing neural networks for machine learning applications,” IEEE Transactions on Neural Networks and Learning Systems (TNNLS), vol. 32, no. 7, pp. 2809–2824, 2020.
  * [8] X. Liang, X. Du, G. Wang, and Z. Han, “A deep reinforcement learning network for traffic light cycle control,” IEEE Transactions on Vehicular Technology (TVT), vol. 68, no. 2, pp. 1243–1253, 2019.
  * [9] R. Mao, R. Cui, and C. P. Chen, “Broad learning with reinforcement learning signal feedback: Theory and applications,” IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2021.
  * [10] P. Koonce and L. Rodegerdts, “Traffic signal timing manual.,” tech. rep., United States. Federal Highway Administration, 2008.
  * [11] R. P. Roess, E. S. Prassas, and W. R. McShane, Traffic engineering.  Pearson/Prentice Hall, 2004.
  * [12] J. D. Little, M. D. Kelson, and N. H. Gartner, “Maxband: A versatile program for setting signals on arteries and triangular networks,” 1981.
  * [13] S.-B. Cools, C. Gershenson, and B. D’Hooghe, “Self-organizing traffic lights: A realistic simulation,” in Springer Advances in applied self-organizing systems, pp. 45–55, 2013.
  * [14] P. Varaiya, “The max-pressure controller for arbitrary networks of signalized intersections,” in Springer Advances in dynamic network modeling in complex transportation systems, pp. 27–66, 2013.
  * [15] P. Lowrie, “Scats-a traffic responsive method of controlling urban traffic,” Sales information brochure published by Roads & Traffic Authority, Sydney, Australia, 1990.
  * [16] S. Lämmer and D. Helbing, “Self-control of traffic lights and vehicle flows in urban road networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 04, p. P04019, 2008.
  * [17] S. Lämmer and D. Helbing, “Self-stabilizing decentralized signal control of realistic, saturated network traffic,” Santa Fe Institute, 2010.
  * [18] I. M. Albatish and S. S. Abu-Naser, “Modeling and controlling smart traffic light system using a rule based system,” in IEEE International Conference on Promising Electronic Technologies (ICPET), pp. 55–60, 2019.
  * [19] M. Hofri and K. W. Ross, “On the optimal control of two queues with server setup times and its analysis,” SIAM Journal on Computing, vol. 16, no. 2, pp. 399–420, 1987.
  * [20] S. Onori, L. Serrao, and G. Rizzoni, “Dynamic programming,” in Hybrid Electric Vehicles, pp. 41–49, Springer, 2016.
  * [21] M. L. Puterman, Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * [22] S. M. Ross, Introduction to stochastic dynamic programming.  Academic press, 2014.
  * [23] N. Kumar, S. S. Rahman, and N. Dhakad, “Fuzzy inference enabled deep reinforcement learning-based traffic light control for intelligent transportation system,” IEEE Transactions on Intelligent Transportation Systems (TITS), 2020.
  * [24] A. Haydari and Y. Yilmaz, “Deep reinforcement learning for intelligent transportation systems: A survey,” IEEE Transactions on Intelligent Transportation Systems (TITS), 2020.
  * [25] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, p. 529, 2015.
  * [26] T. Tan, F. Bao, Y. Deng, A. Jin, Q. Dai, and J. Wang, “Cooperative deep reinforcement learning for large-scale traffic grid signal control,” IEEE transactions on cybernetics, vol. 50, no. 6, pp. 2687–2700, 2019.
  * [27] W.-H. Lin and C. Wang, “An enhanced 0-1 mixed-integer LP formulation for traffic signal control,” IEEE Transactions on Intelligent transportation systems (TITS), vol. 5, no. 4, pp. 238–245, 2004.
  * [28] L. P. J. Rani, M. K. Kumar, K. Naresh, and S. Vignesh, “Dynamic traffic management system using infrared (IR) and Internet of Things (IoT),” in IEEE International Conference on Science Technology Engineering & Management (ICONSTEM), pp. 353–357, 2017.
  * [29] V. Kodire, S. Bhaskaran, and H. Vishwas, “Gps and zigbee based traffic signal preemption,” in IEEE International Conference on Inventive Computation Technologies (ICICT), vol. 2, pp. 1–5, 2016.
  * [30] S. Panichpapiboon and P. Leakkaw, “Traffic density estimation: A mobile sensing approach,” IEEE Communications Magazine, vol. 55, no. 12, pp. 126–131, 2017.
  * [31] M. Zhu, X.-Y. Liu, and X. Wang, “Deep reinforcement learning for unmanned aerial vehicle-assisted vehicular networks,” IEEE Transactions on Intelligent Transportation Systems (TITS), submitted, p. 15, 2021.
  * [32] Z. Ma, M. Xiao, Y. Xiao, Z. Pang, H. V. Poor, and B. Vucetic, “High-reliability and low-latency wireless communication for internet of things: challenges, fundamentals, and enabling technologies,” IEEE Internet of Things Journal (IOTJ), vol. 6, no. 5, pp. 7946–7970, 2019.
  * [33] H. Wu, Z. Zhang, C. Guan, K. Wolter, and M. Xu, “Collaborate edge and cloud computing with distributed deep learning for smart city internet of things,” IEEE Internet of Things Journal (IOTJ), vol. 7, no. 9, pp. 8099–8110, 2020\.
  * [34] H. Wang, P. Hu, P. Wang, and H. Wang, “A genetic timing scheduling model for urban traffic signal control,” Elsevier Information Sciences, 2021.
  * [35] A. M. Turky, M. S. Ahmad, and M. Z. M. Yusoff, “The use of genetic algorithm for traffic light and pedestrian crossing control,” International Journal of Computer Science and Network Security, vol. 9, no. 2, pp. 88–96, 2009\.
  * [36] B. “Brian” Park, I. Yun, and K. Ahn, “Stochastic optimization for sustainable traffic signal control,” Taylor & Francis International journal of sustainable transportation, vol. 3, no. 4, pp. 263–284, 2009.
  * [37] M. E. M. ALI, A. DURDU, S. A. CELTEK, and A. Yilmaz, “An adaptive method for traffic signal control based on fuzzy logic with webster and modified webster formula using sumo traffic simulator,” IEEE Access, 2021.
  * [38] R. Hawi, G. Okeyo, and M. Kimwele, “Smart traffic light control using fuzzy logic and wireless sensor network,” in IEEE Computing Conference, pp. 450–460, 2017.
  * [39] P. W. Shaikh, M. El-Abd, M. Khanafer, and K. Gao, “A review on swarm intelligence and evolutionary algorithms for solving the traffic signal control problem,” IEEE transactions on intelligent transportation systems (TITS), vol. 23, no. 1, pp. 48–63, 2020.
  * [40] H. R. Maier, S. Razavi, Z. Kapelan, L. S. Matott, J. Kasprzyk, and B. A. Tolson, “Introductory overview: Optimization using evolutionary algorithms and other metaheuristics,” Elsevier Environmental modelling & software, vol. 114, pp. 195–213, 2019.
  * [41] H. Wei, G. Zheng, H. Yao, and Z. Li, “Intellilight: A reinforcement learning approach for intelligent traffic light control,” in ACM International Conference on Knowledge Discovery & Data Mining (SIGKDD), pp. 2496–2505, 2018\.
  * [42] T. Chu, J. Wang, L. Codecà, and Z. Li, “Multi-agent deep reinforcement learning for large-scale traffic signal control,” IEEE Transactions on Intelligent Transportation Systems (TITS), vol. 21, no. 3, pp. 1086–1095, 2019\.
  * [43] P. Balaji, X. German, and D. Srinivasan, “Urban traffic signal control using reinforcement learning agents,” IET Intelligent Transport Systems, vol. 4, no. 3, pp. 177–188, 2010.
  * [44] I. Arel, C. Liu, T. Urbanik, and A. G. Kohls, “Reinforcement learning-based multi-agent system for network traffic signal control,” IET Intelligent Transport Systems, vol. 4, no. 2, pp. 128–135, 2010.
  * [45] P. Mannion, J. Duggan, and E. Howley, “An experimental review of reinforcement learning algorithms for adaptive traffic signal control,” Springer Autonomic road transport support systems, pp. 47–66, 2016.
  * [46] B. Bakker, S. Whiteson, L. Kester, and F. C. Groen, “Traffic light control by multiagent reinforcement learning systems,” in Springer Interactive Collaborative Information Systems, pp. 475–510, 2010.
  * [47] S. S. Mousavi, M. Schukat, and E. Howley, “Traffic light control using deep policy-gradient and value-function-based reinforcement learning,” IET Intelligent Transport Systems, vol. 11, no. 7, pp. 417–423, 2017.
  * [48] H. Wei, G. Zheng, H. Yao, and Z. Li, “Intellilight: A reinforcement learning approach for intelligent traffic light control,” in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2496–2505, ACM, 2018.
  * [49] M. Aslani, M. S. Mesgari, and M. Wiering, “Adaptive traffic signal control with actor-critic methods in a real-world traffic network with different traffic disruption events,” Elsevier Transportation Research Part C: Emerging Technologies, vol. 85, pp. 732–752, 2017.
  * [50] M. Abdoos, N. Mozayani, and A. L. Bazzan, “Traffic light control in non-stationary environments based on multi agent q-learning,” in IEEE conference on intelligent transportation systems (ITSC), pp. 1580–1585, 2011\.
  * [51] E. Van der Pol and F. A. Oliehoek, “Coordinated deep reinforcement learners for traffic light control,” Advances in Neural Information Processing Systems (NeurIPS), vol. 1, 2016.
  * [52] X. Zang, H. Yao, G. Zheng, N. Xu, K. Xu, and Z. Li, “Metalight: Value-based meta-reinforcement learning for traffic signal control,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 1153–1160, 2020\.
  * [53] C. Chen, H. Wei, N. Xu, G. Zheng, M. Yang, Y. Xiong, K. Xu, and Z. Li, “Toward a thousand lights: Decentralized deep reinforcement learning for large-scale traffic signal control,” in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), vol. 34, pp. 3414–3421, 2020.
  * [54] T. Wu, P. Zhou, K. Liu, Y. Yuan, and D. O. Wu, “Multi-agent deep reinforcement learning for urban traffic light control in vehicular networks,” IEEE Transactions on Vehicular Technology (TVT), vol. PP, no. 99, pp. 1–1, 2020.
  * [55] M. Xu, K. An, L. H. Vu, Z. Ye, J. Feng, and E. Chen, “Optimizing multi-agent based urban traffic signal control system,” Taylor & Francis Journal of Intelligent Transportation Systems, vol. 23, no. 4, pp. 357–369, 2019.
  * [56] W. Liu, J. Liu, J. Peng, and Z. Zhu, “Cooperative multi-agent traffic signal control system using fast gradient-descent function approximation for V2I networks,” in IEEE International Conference on Communications (ICC), pp. 2562–2567, 2014.
  * [57] Y. Liu, L. Liu, and W.-P. Chen, “Intelligent traffic light control using distributed multi-agent Q learning,” in IEEE International Conference on Intelligent Transportation Systems (ITSC), pp. 1–8, 2017.
  * [58] K. Zhang, Z. Yang, and T. Başar, “Multi-agent reinforcement learning: A selective overview of theories and algorithms,” Springer Handbook of Reinforcement Learning and Control, pp. 321–384, 2021.
  * [59] Y. Yu, X. Si, C. Hu, and J. Zhang, “A review of recurrent neural networks: Lstm cells and network architectures,” Neural computation, vol. 31, no. 7, pp. 1235–1270, 2019.
  * [60] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” in International Conference on Learning Representations (ICLR), 2016.
  * [61] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction.  MIT press, 2018.
  * [62] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, p. 529, 2015.
  * [63] A. Daniely, “Sgd learns the conjugate kernel class of the network,” in Advances in Neural Information Processing Systems (NIPS), pp. 2422–2430, 2017\.
  * [64] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al., “Mastering the game of go without human knowledge,” Nature, vol. 550, no. 7676, p. 354, 2017.
  * [65] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” arXiv preprint arXiv:1312.5602, 2013.
  * [66] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” arXiv preprint arXiv:1412.6980, 2014.
  * [67] W. Horsthemke and R. Lefever, “A perturbation expansion for external wide band markovian noise: Application to transitions induced by ornstein-uhlenbeck noise,” Springer Zeitschrift für Physik B Condensed Matter, vol. 40, no. 3, pp. 241–247, 1980.
  * [68] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al., “Tensorflow: A system for large-scale machine learning,” in USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 265–283, 2016.
  * [69] “Python Markov decision process (MDP) Toolbox (2022).”
https://pymdptoolbox.readthedocs.io/en/latest/api/mdptoolbox.html.

|  Xiao-Yang Liu received M.S. degree in Electrical Engineering from Columbia
University, New York, NY, USA, in 2018, and is currently a Ph.D. candidate at
the Department of Electrical Engineering, Columbia University, New York, NY,
USA. His research interests include tensor and tensor networks, high
performance tensor computing, high performance tensor computing, deep
learning, non-convex optimization, big data analysis and IoT applications.
---|---
|
Ming Zhu received the Ph.D. degree in Computer Science and Engineering in
Shanghai Jiao Tong University, Shanghai, China. He is now an Assistant
Professor in the Shenzhen Institutes of Advanced Technology, Chinese Academy
of Sciences, Shenzhen, China. His research interests are in the area of
autonomous driving, intelligent transportation systems, big data, deep
learning, and tensor networks.
---|---
|  Sem Borst Sem Borst received his MSc degree in applied mathematics from the
University of Twente in 1990, and his PhD degree from Tilburg University in
1994. In 1994, he was a visiting scholar at the Statistical Laboratory of the
University of Cambridge, England. In 1995, Sem joined the Mathematics of
Networks and Systems research department of Bell Labs in Murray Hill, USA. In
addition to his position at TU/e, he maintains a (part-time) affiliation with
Bell Labs. Sem has published over 190 papers in refereed journals and
conference proceedings, and his H-index is 39. He serves or has served on the
editorial boards of several journals, such as ACM Transactions on Modeling and
Performance Evaluation of Computing Systems, IEEE/ACM Transactions on
Networking, Mathematical Methods of Operations Research and Queueing Systems,
and served as program committee member of various conferences.
---|---
|  Anwar Walid Anwar Walid (F’09) received the B.S. and M.S. degrees in
electrical and computer engineering from New York University, New York, NY,
USA, and the Ph.D. degree from Columbia University, New York, NY, USA. He is a
Director of Network Intelligence and a Distributed Systems Research, and a
Distinguished Member of the Research Staff with Nokia Bell Labs, Murray Hill,
NJ, USA, where he also served as the Head of the Mathematics of System
Research Department and the Director of University Research Partnerships. He
is an Adjunct Professor with the Electrical Engineering Department, Columbia
University. He has over 20 U.S. and international granted patents on various
aspects of networking and computing. His current research interests include
control and optimization of distributed systems, learning models and
algorithms with applications to Internet of Things, digital health, smart
transportations, cloud computing, and software defined networking. Dr. Walid
was a recipient of IEEE and ACM Awards, including the 2017 IEEE Communications
Society William R. Bennett Prize and the ACM SIGMETRICS/International
Federation for Information Processing (IFIP) Performance Best Paper Award. He
served as an Associate Editor for the IEEE/ACM Transactions on Cloud
Computing, IEEE Network Magazine, and the IEEE/ACM Transactions on Networking.
He served as the Technical Program Chair for IEEE INFOCOM, the General Chair
of the 2018 IEEE/ACM Conference on Connected Health (CHASE), and the Guest
Editor of the IEEE Internet of Things Journal “Special Issue on AI-Enabled
Cognitive Communications and Networking for Internet of Things.” He is an
elected member of the IFIP Working Group 7.3 and Tau Beta Pi Engineering Honor
Society.
---|---

We first describe the traffic model. Then, we discuss the stability condition
and the queue length evolution. Finally, we prove the optimality of the
“greenwave” control policy.

A. Model Description

Consider a grid road network topology with $N$ nodes, representing an avenue
(i.e., an artery road) with $N$ cross streets. Avenue traffic arrives at node
$1$ as a deterministic ‘fluid flow’ with a constant rate $\lambda_{0}$, and
must traverse all the nodes before it leaves the network after passing through
node $N$. In addition, cross traffic arrives at each node $n$ as a
deterministic fluid flow with a constant rate $\lambda_{n}$ and leaves the
network after passing through that node, $n\in\\{1,...,N\\}$. For stability,
we assume that $\lambda_{0}+\lambda_{n}<1$ for all $n\in\\{1,...,N\\}$.

Avenue traffic can only flow through node $n$ when the traffic light is green,
either at unit rate when it is backed up at node $n$, $n\in\\{1,...,N\\}$, or
otherwise at the outflow rate of the upstream node $n-1$ (when $n>1$) or the
external arrival rate $\lambda_{0}$ (when $n=1$). Likewise, cross traffic can
only flow through node $n$ when the traffic light is red, either at unit rate
when it is backed up, or otherwise at the arrival rate $\lambda_{n}$,
$n\in\\{1,...,N\\}$.

Denote by $Y_{n}$ and $O_{n}$ the (fixed) durations of the yellow and orange
periods at node $n\in\\{1,...,N\\}$, respectively. The lengths of the $k$-th
green and red periods at node $n\in\\{1,...,N\\}$ can be controlled, and are
denoted by $G_{n}^{(k)}$ and $R_{n}^{(k)}$, respectively. For compactness,
denote by $U_{n}^{(k)}=G_{n}^{(k)}+R_{n}^{(k)}+Y_{n}+O_{n}$ the length of the
$k$-th control cycle at node $n\in\\{1,...,N\\}$. Further, we define

$G_{n}=\lim_{K\to\infty}\frac{1}{K}\sum_{k=1}^{K}G_{n}^{(k)},~{}R_{n}=\lim_{K\to\infty}\frac{1}{K}\sum_{k=1}^{K}R_{n}^{(k)},$
(12)

as the long-term average durations of the green and red periods at node $n$,
assuming these limits to exist. Denote by $U_{n}$ the long-term average
control cycle length at node $n$,

$U_{n}=G_{n}+R_{n}+Y_{n}+O_{n},~{}n\in\\{1,...,N\\}.$ (13)

B. Stability Condition

To ensure the stability of queues, it is required that

$\frac{G_{n}}{U_{n}}\geq\lambda_{0},~{}~{}\frac{R_{n}}{U_{n}}\geq\lambda_{n},~{}~{}n\in\\{1,...,N\\},$
(14)

since the avenue traffic arrives continuously at rate $\lambda_{0}$ and can
only pass node $n$ at unit rate during green periods at that node, and
likewise, the cross traffic at node $n$ arrives continuously at rate
$\lambda_{n}$ and can only pass at unit rate during red periods at that node.

Throughout the remainder of the appendix, we assume that the inequations in
(14) are satisfied. Invoking (13), the two inequations in (14) may be
equivalently expressed as

$\begin{split}G_{n}&\geq\frac{\lambda_{0}}{1-\lambda_{0}}\left(R_{n}+Y_{n}+O_{n}\right),~{}n\in\\{1,...,N\\},\\\
R_{n}&\geq\frac{\lambda_{n}}{1-\lambda_{n}}\left(G_{n}+Y_{n}+O_{n}\right),~{}n\in\\{1,...,N\\},\end{split}$
(15)

or in the following forms

$\begin{split}R_{n}&\leq\frac{1-\lambda_{0}}{\lambda_{0}}G_{n}-Y_{n}-O_{n},~{}n\in\\{1,...,N\\},\\\
G_{n}&\leq\frac{1-\lambda_{n}}{\lambda_{n}}R_{n}-Y_{n}-O_{n},~{}n\in\\{1,...,N\\}.\end{split}$
(16)

Considering that

$\displaystyle
1-\frac{G_{n}}{U_{n}}-\frac{R_{n}}{U_{n}}=\frac{Y_{n}+O_{n}}{U_{n}}\overset{\eqref{Eqn:StabilityCondition}}{\leq}1-\lambda_{0}-\lambda_{n},$
(17)

therefore,

$U_{n}\geq\frac{Y_{n}+O_{n}}{1-\lambda_{0}-\lambda_{n}}.$ (18)

Further, from (14) and (18), we obtain

$\displaystyle
G_{n}\geq\frac{\lambda_{0}}{1-\lambda_{0}-\lambda_{n}}(Y_{n}+O_{n}),$ (19)
$\displaystyle
R_{n}\geq\frac{\lambda_{n}}{1-\lambda_{0}-\lambda_{n}}(Y_{n}+O_{n}).$ (20)

Note that (13) and (14) together yield

$\lambda_{0}+\lambda_{n}\leq 1-\frac{Y_{n}+O_{n}}{U_{n}}<1,$ (21)

as assumed above, and the next lemma states some further useful inequations,
whose proofs are provided in the appendix.

######  Lemma 1.

For all $n\in\\{1,...,N\\}$,

$\frac{(G_{n}+Y_{n}+O_{n})^{2}}{U_{n}}\geq\frac{\lambda_{0}(p_{n}+1)^{2}(Y_{n}+O_{n})}{p_{n}},$
(22)
$\frac{(R_{n}+Y_{n}+O_{n})^{2}}{U_{n}}\geq\frac{\lambda_{n}(q_{n}+1)^{2}(Y_{n}+O_{n})}{q_{n}},$
(23)
$p_{n}=\max\\{1,\frac{\lambda_{0}}{1-\lambda_{0}-\lambda_{n}}\\},~{}~{}q_{n}=\max\\{1,\frac{\lambda_{n}}{1-\lambda_{0}-\lambda_{n}}\\}.$

The above inequations are strict unless $G_{n}=p_{n}(Y_{n}+O_{n})$ and
$R_{n}=q_{n}(Y_{n}+O_{n})$, respectively.

###### Proof.

We only show the proof of (22) since the proof of (23) is similar. We have

$\frac{(G_{n}+Y_{n}+O_{n})^{2}}{U_{n}}\overset{\eqref{Eqn:StabilityCondition}}{\geq}\frac{\lambda_{0}(G_{n}+Y_{n}+O_{n})^{2}}{G_{n}}.$

Differentiation shows that the right-hand size is increasing in $G_{n}$ for
$G_{n}\geq Y_{n}+O_{n}$, and decreasing in $G_{n}$ for $G_{n}<Y_{n}+O_{n}$.
Thus, combining the lower bound of $G_{n}$ in (19), the minimum value of the
right-hand side is attained for $G_{n}=p_{n}(Y_{n}+O_{n})$ with
$p_{n}=\max\\{1,\frac{\lambda_{0}}{1-\lambda_{0}-\lambda_{n}}\\}$, and equals

$\frac{\lambda_{0}(p_{n}+1)^{2}(Y_{n}+O_{n})}{p_{n}},$

yielding the lower bound (22). It also follows that the lower bound is strict
unless $G_{n}=p_{n}(Y_{n}+O_{n})$. ∎

C. Queue Evolution

Denote by $\widehat{\Phi}_{n}(b,t)$ and $\widehat{\Psi}_{n}(b,t)$ the queue
length of the avenue and the cross traffic at node $n$ at time $t$ with the
traffic flow begins from the time $b$, respectively. Let $\Phi_{n}(b,t)$ and
$\Psi_{n}(b,t)$ be the lower bounds of $\widehat{\Phi}_{n}(b,t)$ and
$\widehat{\Psi}_{n}(b,t)$. If the traffic flow starts from the time $b=0$,
$\widehat{\Phi}_{n}(b,t)$, $\widehat{\Psi}_{n}(b,t)$, $\Phi_{n}(b,t)$ and
$\Psi_{n}(b,t)$ are simplified as $\widehat{\Phi}_{n}(t)$,
$\widehat{\Psi}_{n}(t)$, $\Phi_{n}(t)$ and $\Psi_{n}(t)$, respectively. Denote
by $\overline{G}_{n}(b,t)$ and $\overline{R}_{n}(b,t)$ the amount of non-green
and non-red time at node $n\in\\{1,...,N\\}$, during the time interval
$(b,t]$, respectively. Now, observe that $\widehat{\Phi}_{1}(b,t)$ increases
at rate $\lambda_{0}$ during non-green periods at node 1 and decreases at rate
$1-\lambda_{0}$ during green periods. Thus,

$\begin{split}\widehat{\Phi}_{1}(b,t)&\geq\lambda_{0}\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b-\overline{G}_{1}(b,t))\\\
&=\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b),\end{split}$ (24)

for all $b\leq t$, yielding

$\widehat{\Phi}_{1}(b,t)\geq\sup_{s\leq
t}\\{\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\\},$ (25)

and assuming $\widehat{\Phi}_{1}(0)=0$, we in fact have

$\Phi_{1}(t)=\sup_{s\leq t}\\{\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\\}.$
(26)

######  Remark 1.

Without loss of generality, we assume that each control cycle ends with a
green period, and thus starts with a yellow period. Denote by $B^{(k)}$ the
start time of the $k$-th control cycle at node 1. It can be shown that

$\displaystyle\Phi_{1}(t)=\sup_{s\leq
t}\\{\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\\}$
$\displaystyle=\max\\{\sup_{l\in\\{1,...,\kappa(t)\\}}\\{\overline{G}_{1}(B^{(l)},t)\\!-\\!(1\\!-\\!\lambda_{0})(t\\!-\\!B^{(l)})\\},\\!0\\},$
(27)

where $\kappa(t)$ is the maximum number of cycles until time $t$.

First, if $b\in[B^{(l-1)}+\overline{G}_{1}^{(l-1)},B^{(l)}]$, thus
$\overline{G}_{1}(b,t)=\overline{G}_{1}(B^{(l)},t)$, and
$\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\leq\overline{G}_{1}(B^{(l)},t)-(1-\lambda_{0})(t-B^{(l)})$.
Secondly, if $b\in[B^{(l)},B^{(l)}+\overline{G}_{1}^{(l)}]$, thus
$\overline{G}_{1}(b,t)=\overline{G}_{1}(B^{(l)},t)-(b-B^{(l)})$ with
$b-B^{(l)}\geq 0$, and
$\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\leq\overline{G}_{1}(B^{(l)},t)-(1-\lambda_{0})(t-B^{(l)})$.
The above two cases are finally merged as
$\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\leq\overline{G}_{1}(B^{(l)},t)-(1-\lambda_{0})(t-B^{(l)})$
for all
$b\in[B^{(l-1)}+\overline{G}_{1}^{(l-1)},B^{(l)}+\overline{G}_{1}^{(l)}]$. We
see that,
$\overline{G}_{1}(b,t)-(1-\lambda_{0})(t-b)\leq\overline{G}_{1}(B^{(l)},t)-(1-\lambda_{0})(t-B^{(l)})$
is always satisfied for each cycle $l\in\\{1,...,\kappa(t)\\}$.

Likewise, at node $n$, $\widehat{\Psi}_{n}(b,t)$ increases at rate
$\lambda_{n}$ during non-red periods and decreases at rate $1-\lambda_{n}$
during red periods. Thus,

$\displaystyle\widehat{\Psi}_{n}(b,t)\\!$ $\displaystyle\geq$
$\displaystyle\\!\lambda_{n}\overline{R}_{n}(b,t)\\!-\\!(1-\lambda_{n})(t-b-\overline{R}_{n}(b,t))$
(28) $\displaystyle=$
$\displaystyle\\!\overline{R}_{n}(b,t)-(1-\lambda_{n})(t-b),$

for all $b\leq t$, yielding

$\widehat{\Psi}_{n}(t)\geq\sup_{s\leq
t}\\{\overline{R}_{n}(b,t)-(1-\lambda_{n})(t-b)\\},$ (29)

and assuming $\widehat{\Psi}_{n}(0)=0$, we in fact have

$\Psi_{n}(t)=\sup_{s\leq t}\\{\overline{R}_{n}(b,t)-(1-\lambda_{n})(t-b)\\}.$
(30)

The dynamics of $\widehat{\Phi}_{n}(t)$ are similar but also different, since
the inflow rate of avenue traffic at node $n$ is not fixed, and equal to the
outflow rate of the upstream node $n-1$. Denote by $\eta_{n}(t)$ the outflow
rate of avenue traffic at node $n$ at time $t$, and note that $\eta_{n}(t)=0$
during non-green periods, $\eta_{n}(t)=1$ during green periods when
$\widehat{\Phi}_{n}(t)>0$, and $\eta_{n}(t)=\eta_{n-1}(t)$ during green
periods, and $\eta_{n}(t)=0$ when $\widehat{\Phi}_{n}(t)=0$ in all periods.
Assuming $\widehat{\Phi}_{n}(0)=0$, we have

$\Phi_{n}(t)=\sup_{s\leq
t}\\{\int_{x=0}^{t}\eta_{n-1}(x)dx-(t-b-\overline{G}_{n}(b,t))\\}.$ (31)

Define

$\displaystyle\Phi_{n}=\lim\sup_{T\to\infty}\frac{1}{T}\int_{t=0}^{T}\Phi_{n}(t)dt,$
$\displaystyle\Psi_{n}=\lim\sup_{T\to\infty}\frac{1}{T}\int_{t=0}^{T}\Psi_{n}(t)dt,$

as the long-term average queue length of the avenue and the cross traffic at
node $n$, respectively. The lower bound of $\Phi_{1}(t)$ is obtained by Lemma
2.

######  Lemma 2.

$\displaystyle\Phi_{1}(t)\geq\sum_{k=1}^{\infty}\max\\{\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})U^{(k)},0\\},$
(32)

which is further deduced as

$\displaystyle\Phi_{1}(t)\geq\sum_{k=1}^{\infty}\max\\{\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})|t-B^{(k)}|,0\\}.$
(33)

###### Proof.

Without loss of generality we assume that each control cycle ends with a green
period (and thus starts with a yellow period). For compactness, denote by
$\overline{G}_{1}^{(k)}=R_{1}^{(k)}+Y_{1}+O_{1}$ the amount of non-green time
during the $k$-th control cycle at node $1$. Denote by $B^{(k)}$ the start
time of the $k$-th control cycle at node $1$. Define

$\overline{G}_{1}^{(k)}(t)=\max\\{\min\\{\overline{G}_{1}^{(k)},t-B^{(k)}\\},0\\},$

as the amount of non-green time during the $k$-th control cycle at node $1$
that has elapsed by time $t$, or equivalently,

$\overline{G}_{1}^{(k)}(t)=\left\\{\begin{array}[]{ll}0,&~{}\text{if}~{}t\leq
B^{(k)},\\\ t-B^{(k)},&~{}\text{if}~{}B^{(k)}\leq t\leq
B^{(k)}+\overline{G}_{1}^{(k)},\\\
\overline{G}_{1}^{(k)},&~{}\text{if}~{}t\geq
B^{(k)}+\overline{G}_{1}^{(k)}.\end{array}\right.$ (34)

Define
$\overline{G}_{1}^{(k)}(b,t)=\overline{G}_{1}^{(k)}(t)-\overline{G}_{1}^{(k)}(b)$
as the amount of non-green time during the $k$-th control cycle that occurs in
the time interval $(b,t]$ at node 1, and note that
$\overline{G}_{1}(b,t)=\sum_{k=1}^{\infty}\overline{G}_{1}^{(k)}(b,t)$ is
total amount of non-green time that occurs in the time interval $(b,t]$ at
node 1. Let $U^{(k)}$ be the duration of the $k$-th cycle.

$\displaystyle\Phi_{1}(t)\overset{\eqref{Eqn:Phi1tEqual}}{=}\sup_{l\in\\{1,...,\kappa(t)\\}}\\{\overline{G}_{1}(B^{(l)},t)\\!-\\!(1\\!-\\!\lambda_{0})(t\\!-\\!B^{(l)})\\}$
$\displaystyle\geq\overline{G}_{1}^{(1)}(B^{(1)},t)-(1-\lambda_{0})(t-B^{(1)})$
$\displaystyle=\sum_{k=1}^{\kappa(t)}[\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})U^{(k)}]$
(35)
$\displaystyle\geq\sum_{k=1}^{\kappa(t)}[\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})(t-B^{(k)})].$
(36)

When $k\geq\kappa(t)+1$, $\overline{G}_{1}^{(k)}(t)=0$, and
$\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})U^{(k)}<0$. Therefore, combining
(35), (32) is obtained. When $k=\kappa(t)+1$, $t-B^{(k)}=0$. When
$k\geq\kappa(t)+2$, $t-B^{(k)}<0$, and $|t-B^{(k)}|>0$. Therefore,
$\sum_{k=1}^{\kappa(t)}[\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})(t-B^{(k)})]=\sum_{k=1}^{\infty}\max\\{\overline{G}_{1}^{(k)}(t)-(1-\lambda_{0})|t-B^{(k)}|,0\\}$.
Combining (36), (33) is obtained.

Now observe that when $B^{(k)}\leq t\leq
B^{(k)}+\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(k)}$, we have

$\displaystyle\max\\{\overline{G}_{1}^{(k)}(B^{(k)},t)-(1-\lambda_{0})|t-B^{(k)}|,0\\}$
$\displaystyle=\overline{G}_{1}^{(k)}(B^{(k)},t)-(1-\lambda_{0})(t-B^{(k)})$
$\displaystyle=\left\\{\begin{array}[]{ll}\lambda_{0}(t-B^{(k)})-\overline{G}_{1}^{(k)}(B^{(k)}),&\text{if}~{}B^{(k)}\leq
t\leq B^{(k)}+\overline{G}_{1}^{(k)},\\\
\overline{G}_{1}^{(k)}-(1-\lambda_{0})(t-B^{(k)})&\\\
~{}~{}~{}~{}-\overline{G}_{1}^{(k)}(B^{(k)}),&\text{if}~{}B^{(k)}+\overline{G}_{1}^{(k)}\leq
t\\\ &~{}~{}~{}~{}\leq
B^{(k)}+\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(k)}.\end{array}\right.$ (41)

∎

######  Proposition 1.

For $n\in\\{1,...,N\\}$, we have

$\begin{split}\Phi_{1}&\geq\frac{\lambda_{0}(R_{1}+Y_{1}+O_{1})^{2}}{2(1-\lambda_{0})U_{1}},\\\
\Psi_{n}&\geq\frac{\lambda_{n}(G_{n}+Y_{n}+O_{n})^{2}}{2(1-\lambda_{n})U_{n}}.\end{split}$
(42)

###### Proof.

Define

$E^{(k)}=\overline{G}_{1}^{(k)}-(1-\lambda_{0})U^{(k)},$

and

$F^{(k)}=\sup_{l\in\\{1,...,k\\}}\sum_{m=l}^{k}E^{(m)},$

and consider $k$ such that $F^{(k)}=0$, i.e., $\sum_{m=l}^{k}E^{(m)}\leq 0$
for all $l\in\\{1,...,k\\}$, implying

$\begin{split}\overline{G}_{1}^{(l)}-(1-\lambda_{0})\sum_{m=l}^{k}U^{(m)}&\leq\sum_{m=l}^{k}\overline{G}_{1}^{(m)}-(1-\lambda_{0})\sum_{m=l}^{k}U^{(m)}\\\
&=\sum_{m=l}^{k}E^{(m)}\leq 0,\end{split}$ (43)

i.e.,

$\overline{G}_{1}^{(l)}\leq(1-\lambda_{0})\sum_{m=l}^{k}U^{(m)},$

and thus

$B^{(l)}+\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(l)}\leq
B^{(l)}+\sum_{m=l}^{k}U^{(m)}=B^{(k+1)}.$

Now consider

$\begin{split}&\int_{t=0}^{B^{(k+1)}}\Phi_{1}(t)dt\\\
&\overset{\eqref{Eqn:Phi1tGeq__}}{\geq}\int_{t=0}^{B^{(k+1)}}\sum_{l=1}^{\kappa(t)}\max\\{\overline{G}_{1}^{(l)}(t)-(1-\lambda_{0})|t-B^{(l)}|,0\\}dt\\\
&=\sum_{l=1}^{\kappa(t)}\int_{t=0}^{B^{(k+1)}}\max\\{\overline{G}_{1}^{(l)}(t)-(1-\lambda_{0})|t-B^{(l)}|,0\\}dt.\end{split}$
(44)

Note that

$\displaystyle\max\\{\overline{G}_{1}^{(l)}(t)-(1-\lambda_{0})|t-B^{(l)}|,0\\}=$
$\displaystyle\begin{cases}0,&\text{if}~{}t\leq B^{(l)},\\\
\lambda_{0}(t-B^{(l)}),&\text{if}~{}B^{(l)}\leq t\leq
B^{(l)}+\overline{G}_{1}^{(l)},\\\
\overline{G}_{1}^{(l)}-(1-\lambda_{0})(t-B^{(l)}),&\text{if}~{}B^{(l)}+\overline{G}_{1}^{(l)}\leq
t\\\ &~{}~{}~{}~{}\leq
B^{(l)}+\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(l)},\\\ 0,&\text{if}~{}t\geq
B^{(l)}+\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(l)}.\end{cases}$ (45)

Thus

$\displaystyle\int_{t=0}^{B^{(k+1)}}\max\\{\overline{G}_{1}^{(l)}(t)-(1-\lambda_{0})t,0\\}$
$\displaystyle=\int_{t=B^{(l)}}^{B^{(l)}+\overline{G}_{1}^{(l)}}\lambda_{0}(t-B^{(l)})dt$
$\displaystyle~{}~{}~{}~{}+\int_{t=B^{(l)}+\overline{G}_{1}^{(l)}}^{B^{(l)}+\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(l)}}[\overline{G}_{1}^{(l)}-(1-\lambda_{0})(t-B^{(l)})]dt$
$\displaystyle=\int_{x=0}^{\overline{G}_{1}^{(l)}}\lambda_{0}xdx+\int_{x=\overline{G}_{1}^{(l)}}^{\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(l)}}[\overline{G}_{1}^{(l)}-(1-\lambda_{0})x]dx$
$\displaystyle=\left[\frac{1}{2}\lambda_{0}x^{2}\right]_{0}^{\overline{G}_{1}^{(l)}}\\!+\\!\frac{\lambda_{0}\left(\overline{G}_{1}^{(l)}\right)^{2}}{1-\lambda_{0}}\\!-\\!\left[\frac{1}{2}(1-\lambda_{0})x^{2}\right]_{\overline{G}_{1}^{(l)}}^{\frac{1}{1-\lambda_{0}}\overline{G}_{1}^{(l)}}$
$\displaystyle=\frac{1}{2}\lambda_{0}\left(\overline{G}_{1}^{(l)}\right)^{2}+\frac{\lambda_{0}\left(\overline{G}_{1}^{(l)}\right)^{2}}{1-\lambda_{0}}-\frac{1}{2}\frac{\left(\overline{G}_{1}^{(l)}\right)^{2}}{1-\lambda_{0}}$
$\displaystyle~{}~{}~{}+\frac{1}{2}(1-\lambda_{0})\left(\overline{G}_{1}^{(l)}\right)^{2}$
$\displaystyle=\frac{\lambda_{0}\left(\overline{G}_{1}^{(l)}\right)^{2}}{2(1-\lambda_{0})}.$
(46)

We obtain that

$\int_{t=0}^{B^{(k+1)}}\Phi_{1}(t)dt\\!\geq\\!\sum_{l=1}^{\kappa(t)}\frac{\lambda_{0}\left(\overline{G}_{1}^{(l)}\right)^{2}}{2(1-\lambda_{0})}\\!=\\!\frac{\lambda_{0}}{2(1-\lambda_{0})}\sum_{l=1}^{\kappa(t)}\left(\overline{G}_{1}^{(l)}\right)^{2}.$

Now observe that

$\displaystyle\lim_{K\to\infty}\frac{1}{K}\sum_{k=1}^{K}E^{(k)}=R_{1}+Y_{1}+O_{1}-(1-\lambda_{0})U_{1}$
$\displaystyle=-G_{1}+\lambda_{0}U_{1}<0,$ (47)

which means that the subsequence of $k$ for which $F^{(k)}=0$ is infinite, so
that

$\displaystyle\Phi_{1}$ $\displaystyle=$
$\displaystyle\lim\sup_{T\to\infty}\frac{1}{T}\int_{t=0}^{T}\Phi_{1}(t)dt$
(48) $\displaystyle\geq$
$\displaystyle\lim\sup_{k\to\infty}\frac{1}{B^{(k+1)}}\int_{t=0}^{B^{(k+1)}}\Phi_{1}(t)dt$
$\displaystyle\geq$
$\displaystyle\lim\sup_{k\to\infty}\frac{1}{B^{(k+1)}}\frac{\lambda_{0}}{2(1-\lambda_{0})}\sum_{l=1}^{k}\left(\overline{G}_{1}^{(l)}\right)^{2}$
$\displaystyle=$
$\displaystyle\lim\sup_{k\to\infty}\frac{1}{\sum_{l=1}^{k}U^{(l)}}\frac{\lambda_{0}}{2(1-\lambda_{0})}\sum_{l=1}^{k}\left(\overline{G}_{1}^{(l)}\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{\lambda_{0}}{2(1-\lambda_{0})}\lim\sup_{k\to\infty}\frac{1}{\frac{1}{k}\sum_{l=1}^{k}U^{(l)}}\frac{1}{k}\sum_{l=1}^{k}\left(\overline{G}_{1}^{(l)}\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{\lambda_{0}}{2(1-\lambda_{0})}\frac{(R_{1}+Y_{1}+O_{1})^{2}}{U_{1}},$

as claimed. ∎

Combining Lemma 1 and Proposition 1, we obtain the lower bounds

$\begin{split}\Phi_{1}&\geq\frac{\lambda_{0}}{2(1-\lambda_{0})}\frac{\lambda_{0}(p_{1}+1)^{2}(Y_{1}+O_{1})}{p_{1}}\\\
&=\frac{\lambda_{0}^{2}(p_{1}+1)^{2}(Y_{1}+O_{1})}{2p_{1}(1-\lambda_{0})},\end{split}$
$\begin{split}\Psi_{n}&\geq\frac{\lambda_{n}}{2(1-\lambda_{n})}\frac{\lambda_{n}(q_{n}+1)^{2}(Y_{n}+O_{n})}{q_{n}}\\\
&=\frac{\lambda_{n}^{2}(q_{n}+1)^{2}(Y_{n}+O_{n})}{2q_{n}(1-\lambda_{n})},\hskip
28.90755ptn\in\\{1,...,N\\},\end{split}$

and conclude that the two inequations are strict unless
$G_{1}=p_{1}(Y_{1}+O_{1})$ and $R_{n}=q_{n}(Y_{n}+O_{n})$, respectively.

We henceforth make an mild assumption that the fixed durations of the yellow
and orange periods are identical at all nodes, i.e., $Y_{n}\equiv Y$ and
$O_{n}\equiv O$ for all $n\in\\{1,...,N\\}$. The above lower bounds are
simplified as

$\displaystyle\Phi_{1}\geq\frac{\lambda_{0}^{2}(p_{1}+1)^{2}(Y+O)}{2p_{1}(1-\lambda_{0})},$
(49)
$\displaystyle\Psi_{n}\geq\frac{\lambda_{n}^{2}(q_{n}+1)^{2}(Y+O)}{2q_{n}(1-\lambda_{n})},$
(50)

which are strict unless $G_{1}=p_{1}(Y_{1}+O_{1})$ and
$R_{n}=q_{n}(Y_{n}+O_{n})$, respectively.

D. Optimality of the “Greenwave” Control Policy

We now consider a greenwave control policy which synchronizes the states
across all the nodes, i.e., uses simultaneous green, orange, red and yellow
periods. Denote by $\lambda_{\max}=\max_{n\in\\{1,...,N\\}}\lambda_{n}$ the
maximum arrival rate over all the cross streets. We select a common length of
the green period

$G_{n}\equiv
G(\delta)=\frac{\lambda_{0}(1+\delta)(Y+O)}{1-\lambda_{0}-\lambda_{\max}},$
(51)

and a common length of the red period

$R_{n}\equiv
R(\delta)=\frac{\lambda_{\max}(1+\delta)(Y+O)}{1-\lambda_{0}-\lambda_{\max}},$
(52)

where $\delta\geq 0$ is a small scalability factor based on the lower bounds
(19) and (20). Then (51) and (52) yield a common control cycle length

$U_{n}\equiv
U(\delta)=\frac{(1+\delta(\lambda_{0}+\lambda_{\max}))(Y+O)}{1-\lambda_{0}-\lambda_{\max}}.$
(53)

The next proposition plays an instrumental role in establishing the optimality
of the greenwave control policy.

######  Proposition 2.

The long-term average queue length under the greenwave control policy is equal
to

$\displaystyle\Phi_{1}(\delta)=\frac{\lambda_{0}(R(\delta)+Y+O)^{2}}{2(1-\lambda_{0})U(\delta)}$
$\displaystyle\overset{\text{\eqref{Eqn:Rdelta}
\eqref{Eqn:Udelta}}}{=}\frac{\lambda_{0}(1-\lambda_{0}+\delta\lambda_{\max})^{2}(Y+O)}{2(1-\lambda_{0})(1-\lambda_{0}-\lambda_{\max})[1+\delta(\lambda_{0}+\lambda_{\max})]},$
(54)
$\displaystyle\Psi_{n}(\delta)=\frac{\lambda_{n}(G(\delta)+Y+O)^{2}}{2(1-\lambda_{n})U(\delta)}$
$\displaystyle\overset{\text{\eqref{Eqn:Gdelta}
\eqref{Eqn:Udelta}}}{=}\frac{\lambda_{n}(1+\delta\lambda_{0}-\lambda_{\max})^{2}(Y+O)}{(1-\lambda_{n})(1-\lambda_{0}-\lambda_{\max})[1+\delta(\lambda_{0}+\lambda_{\max})]},$
(55)

for $n\in\\{1,...,N\\}$, and $\Phi_{n}(\delta)=0$ for all $n\geq 2$.

###### Proof.

Note that $\\{\Phi_{n}\\}_{n\in\\{1,...,N\\}}$ increases by
$\lambda_{0}U(\delta)$ over the course of a cycle, and must have decreased by
$G(\delta)$ over the preceding cycle if it is strictly positive at the end of
a green period. Thus, if $\\{\Phi_{n}\\}_{n\in\\{1,...,N\\}}$ is strictly
positive at the end of a green period, it must decrease at the end of the
preceding green period by

$\begin{split}&\Delta_{\Phi_{n}}=G(\delta)-\lambda_{0}U(\delta)\\\
&\overset{\text{\eqref{Eqn:Gdelta}
\eqref{Eqn:Udelta}}}{=}\frac{\lambda_{0}(1+\delta)(Y+O)}{1-\lambda_{0}-\lambda_{\max}}-\frac{\lambda_{0}[1+\delta(\lambda_{0}+\lambda_{\max})](Y+O)}{1-\lambda_{0}-\lambda_{\max}}\\\
&=\lambda_{0}\delta(Y+O)\\\ &>0.\end{split}$ (56)

We conclude that for any initial state $\\{\Phi_{n}\\}_{n\in\\{1,...,N\\}}$
must eventually become 0 at the end of some green period, say at time $t_{0}$.
Now observe that $\\{\Phi_{n}\\}_{n\in\\{2,...,N\\}}$ can only receive traffic
(at most at unit rate) during a green period, but will also serve traffic at
unit rate during a green period, and hence must remain zero from that point
onward.

$\Phi_{1}$ increases at rate $\lambda_{0}$ from time $t_{0}$ to time
$t_{0}+R(\delta)+Y+O$, and decreases at rate $1-\lambda_{0}$ from time
$t_{0}+R(\delta)+Y+O$ to time
$t_{0}+R(\delta)+Y+O+\frac{\lambda_{0}}{1-\lambda_{0}}\left(R(\delta)+Y+O\right)=t_{0}+\frac{1}{1-\lambda_{0}}\left(R(\delta)+Y+O\right)<t_{0}+U(\delta)$,
to become zero at that point and remain zero until $t_{0}+U(\delta)$. Thus

$\begin{split}&\Phi_{1}(t_{0}+t)=\\\
&\left\\{\begin{array}[]{ll}\lambda_{0}t,&\text{if}~{}t\in[0,R(\delta)+Y+O],\\\
-(1-\lambda_{0})t+R(\delta)&\\\
~{}~{}+Y+O,&\text{if}~{}t\in\left[1,\frac{1}{1-\lambda_{0}}(R(\delta)+Y+O)\right],\\\
0,&\text{if}~{}t\in\left[\frac{1}{1-\lambda_{0}}(G(\delta)+Y+O),U(\delta)\right].\end{array}\right.\end{split}$

We deduce that

$\begin{split}&\Phi_{1}(\delta)=\lim_{T\to\infty}\frac{1}{T}\int_{0}^{T}\Phi_{1}(t)dt=\frac{1}{U(\delta)}\int_{t=t_{0}}^{t_{0}+U(\delta)}\Phi_{1}(t)dt\\\
&=\frac{\lambda_{0}(R(\delta)+Y+O)^{2}}{2(1-\lambda_{0})U(\delta)}\\\
&\overset{\text{\eqref{Eqn:Rdelta}
\eqref{Eqn:Udelta}}}{=}\frac{\lambda_{0}(1-\lambda_{0}+\delta\lambda_{\max})^{2}(Y+O)}{2(1-\lambda_{0})(1-\lambda_{0}-\lambda_{\max})[1+\delta(\lambda_{0}+\lambda_{\max})]}.\end{split}$
(57)

$\displaystyle\Phi_{1}(0)=\frac{\lambda_{0}(1-\lambda_{0})(Y+O)}{2(1-\lambda_{0}-\lambda_{\max})},$
(58)

which has another form if $\lambda_{n}=\lambda_{1}$ for $n\in\\{1,...,N\\}$

$\displaystyle\Phi_{1}(0)=\frac{\lambda_{0}(1-\lambda_{0})(Y+O)}{2(1-\lambda_{0}-\lambda_{1})}.$
(59)

We also obtain that $\\{\Psi_{n}\\}_{n\in\\{1,...,N\\}}$ increases by
$\lambda_{n}[U(\delta)-R(\delta)]$ over the course of a cycle, and must have
decreased by $R(\delta)$ over the preceding cycle if it is strictly positive
at the end of a red period.

$\displaystyle\Delta_{\Psi_{n}}=R(\delta)-\lambda_{n}U(\delta)$
$\displaystyle\overset{\eqref{Eqn:Rdelta}\eqref{Eqn:Udelta}}{=}\\!\frac{\lambda_{\max}(1+\delta)(Y+O)}{1-\lambda_{0}-\lambda_{\max}}\\!-\\!\frac{\lambda_{n}[1+\delta(\lambda_{0}+\lambda_{\max})](Y+O)}{1-\lambda_{0}-\lambda_{\max}}$
$\displaystyle=\frac{(Y+O)[(1+\delta)\lambda_{\max}-\lambda_{n}[1+\delta(\lambda_{0}+\lambda_{\max})]}{1-\lambda_{0}-\lambda_{\max}}$
$\displaystyle>0.$ (60)

Thus, if $\Psi_{n}$ is strictly positive at the end of a red period, it must
be smaller at the end of the preceding red period.

We conclude that for any initial state $\Psi_{n}$ must eventually become 0 at
the end of some red period, say at time $t_{1}$. Then $\Psi_{n}$ increases at
rate $\lambda_{n}$ from time $t_{1}$ to time $t_{1}+G(\delta)+Y+O$, decreases
at rate $1-\lambda_{n}$ from time $t_{1}+G(\delta)+Y+O$ to time
$t_{1}+G(\delta)+Y+O+\frac{\lambda_{n}}{1-\lambda_{n}}\left(G(\delta)+Y+O\right)=t_{1}+\frac{1}{1-\lambda_{n}}\left(G(\delta)+Y+O\right)\leq
t_{1}+U(\delta)$, to become zero at that point and remain zero until
$t_{1}+U(\delta)$. Thus

$\displaystyle\Psi_{n}(t_{1}+t)=$
$\displaystyle\begin{cases}\lambda_{n}t,&\text{if}~{}t\in[0,G(\delta)+Y+O],\\\
-(1-\lambda_{n})t+G(\delta)&\\\
~{}~{}~{}+Y+O,&\text{if}~{}t\in\left[1,\frac{1}{1-\lambda_{n}}\right](G(\delta)+Y+O),\\\
0,&\text{if}~{}t\in\left[\frac{1}{1-\lambda_{n}}(G(\delta)+Y+O),U(\delta)\right].\\\
\end{cases}$ (61)

We deduce that

$\begin{split}&\Psi_{n}(\delta)=\lim_{T\to\infty}\frac{1}{T}\int_{0}^{T}\Psi_{n}(t)dt=\frac{1}{U(\delta)}\int_{t=t_{1}}^{t_{1}+U(\delta)}\Psi_{n}(t)dt\\\
&=\frac{\lambda_{n}(G(\delta)+Y+O)^{2}}{2(1-\lambda_{n})U(\delta)}\\\
&\overset{\text{\eqref{Eqn:Gdelta}
\eqref{Eqn:Udelta}}}{=}\frac{\lambda_{n}(1+\delta\lambda_{0}-\lambda_{\max})^{2}(Y+O)}{2(1-\lambda_{n})(1-\lambda_{0}-\lambda_{\max})[1+\delta(\lambda_{0}+\lambda_{\max})]}.\end{split}$
(62)

$\Psi_{n}(0)=\frac{\lambda_{n}(1-\lambda_{\max})^{2}(Y+O)}{2(1-\lambda_{n})(1-\lambda_{0}-\lambda_{\max})},$
(63)

which has another form if $\lambda_{n}=\lambda_{1}$ for $n\in\\{1,...,N\\}$

$\Psi_{n}(0)=\frac{\lambda_{1}(1-\lambda_{1})(Y+O)}{2(1-\lambda_{0}-\lambda_{1})}.$
(64)

∎

We now use the propositions in IV-D to prove the optimality of the “greenwave”
control policy in a scenario with uniform cross traffic, i.e.,
$\lambda_{n}\equiv\lambda_{1}=\lambda_{\max}$ for all $n\in\\{1,...,N\\}$. We
take one case as an example, i.e., $\lambda_{0}+2\lambda_{1}\geq 1$,
$2\lambda_{0}+\lambda_{1}\geq 1$, and then we obtain

$\displaystyle\Phi_{1}(\delta)=\frac{\lambda_{0}(1-\lambda_{0}+\delta\lambda_{1})^{2}(Y+O)^{2}}{2(1-\lambda_{0})(1-\lambda_{0}-\lambda_{1})^{2}},$
$\displaystyle\Psi_{n}(\delta)=\frac{\lambda_{1}(1+\lambda_{0}\delta-\lambda_{1})^{2}(Y+O)^{2}}{2(1-\lambda_{1})(1-\lambda_{0}-\lambda_{1})^{2}},$

where $n\in\\{1,...,N\\}$. Also,
$p_{1}=\frac{\lambda_{0}}{1-\lambda_{0}-\lambda_{1}}$, and
$q_{1}=\frac{\lambda_{1}}{1-\lambda_{0}-\lambda_{1}}$.

The lower bounds in (49) and (50) reduce to the following

$\displaystyle\Phi_{1}\geq\frac{\lambda_{0}(1-\lambda_{1})^{2}(Y+O)}{2(1-\lambda_{0})(1-\lambda_{0}-\lambda_{1})},$
(65)
$\displaystyle\Psi_{n}\geq\frac{\lambda_{1}(1-\lambda_{0})^{2}(Y+O)}{2(1-\lambda_{1})(1-\lambda_{0}-\lambda_{1})},$
(66)

which are strict unless
$G_{1}=\frac{\lambda_{0}(Y+O)}{1-\lambda_{0}-\lambda_{1}}$ and
$R_{n}=\frac{\lambda_{1}(Y+O)}{1-\lambda_{0}-\lambda_{1}}$, respectively.

It is easily verified that, as $\delta\downarrow 0$, the values of
$\Phi_{1}(\delta)$ and $\Psi_{n}(\delta)$, $n\in\\{1,...,N\\}$, approach the
absolute lower bounds in (65) and (66), respectively. The optimality of the
“greenwave” control policy, in the sense that no other control policy can
achieve lower values for any $\Phi_{n}$ or $\Psi_{n}$ (while maintaining
stability). In fact, the greenwave control policy is essentially the unique
optimal policy in the scenario under consideration.

Indeed, the optimality immediately forces
$G_{n}=G(0)=\frac{\lambda_{0}(Y+O)}{1-\lambda_{0}-\lambda_{1}}$,
$n\in\\{1,...,N\\}$, and
$R_{1}=R(0)=\frac{\lambda_{1}(Y+O)}{1-\lambda_{0}-\lambda_{1}}$, because
otherwise the inequations in (65) and (66) are strict. Also,
$R_{n}=R(0)=\frac{\lambda_{1}(Y+O)}{1-\lambda_{0}-\lambda_{1}}$ is required
for all $n=2,\dots,N$ for stability. Now, we suppose that $R_{n}>R(0)$ for
some $n=2,\dots,N$, or that the non-green periods do not strictly coincide at
all the nodes, and let $W_{n}$ be the average elapsed simultaneous non-green
period at all nodes $\\{1,\dots,n-1\\}$ at the start of a green period at node
$n$. Then there must be at least one node $n$ for which $W_{n}>0$. Now observe
that $\Phi_{n}$ must grow at least at rate $\lambda_{0}$ when all the upstream
nodes $\\{1,\dots,n-1\\}$ are in a green period while node $n$ is not. It may
then be shown that
$\Phi_{n}\geq\frac{\lambda_{0}W_{n}^{2}}{2(1-\lambda_{0})U_{n}}>0$, preventing
the optimality. Therefore, the unique optimality of the greenwave control
policy is proved.