Traffic State Prediction and Traffic Control Strategy for Intelligent Transportation Systems

Abstract

The recent development of V2V (Vehicle-to-Vehicle), V2I (Vehicle-to-Infrastructure), V2X (Vehicle-to-Everything) and vehicle automation technologies have enabled the concept of Connected and Automated Vehicles (CAVs) to be tested and explored in practice. Traffic state prediction and control are two key modules for CAV systems. Traffic state prediction is important for CAVs because adaptive decisions, control strategies such as adjustment of traffic signals, turning left or right, stopping or accelerating and decision-making of vehicle motion rely on the completeness and accuracy of traffic data. For a given traffic state and input action, the future traffic states can be predicted via data-driven approaches such as deep learning models. RL (Reinforcement Learning) - based approaches gain the most popularity in developing optimum control and decision-making strategies because they can maximize the long-term award in a complex system via interaction with the environment. However, RL technique still has some drawbacks such as a slow convergence rate for high-dimensional states, etc., which need to be overcome in future research. This chapter aims to provide a comprehensive survey of the state-of-the-art solutions for traffic state prediction and traffic control strategies.

1. Introduction

Connected and Automated Vehicles (CAVs) are nowadays the area of extensive research and there are premises to suspect that the introduction CAVs may revolutionize the whole transportation area [1]. There is no lack of predictions stating that CAVs will solve many of the current problems experienced on roads today, such as congestion, traffic accidents and lost time [2].

Traffic state prediction and traffic control are two key modules in transportation systems with CAVs [3]. Traffic states such as flow, speed, congestion, etc., plays vital roles in traffic management, public service and traffic control [4]. By predicting the evolution of traffic state timely and accurately, decision-maker and traffic controller can make effective policy and control input to avoid traffic congestion ahead of time and thus ITS (Intelligent Transportation Systems), advanced traffic management systems and traveler information systems rely on real-time traffic state prediction. Traffic control can be divided into a decision-making module and a vehicle control module. The former is used to optimize the mobility, safety and energy consumption by using the vehicle trajectory prediction results to calculate vehicle platoon sizes, speed, flow, density, traffic merging, diverging flow and traffic signals, while the latter is used for vehicle path control, vehicle fleet control and steering wheel, throttle, brake, and other actuator control by using onboard units based on the control commands [3]. How to timely and accurately predict the future traffic state and deliver an effective traffic control strategy are fundamental issues in ITS.

Traffic state prediction approaches can be broadly divided into two parts: parametric and non-parametric approaches [5]. Parametric approaches utilize parametric models that capture all the information about its predictions within a finite set of parameters. The popular techniques in parametric approaches include ARIMA (Autoregressive Integrated Moving Average) [6, 7, 8, 9], linear regression [10] and Kalman Filter (KF) based method [11], which are linear models and able to have high accuracy with linear characteristics of traffic data. ARIMA model is based on the assumption that the future data will resemble the past and widely used in time series analysis, which can be made to be stationary by differencing. It can be specified three values that represent the order of autoregressive (p), the degree of differencing (d) and the order of moving average (q). The model order can be selected by Akaike’s Information Criterion (AIC) combined with the likelihood of the historical data while the model parameters can be estimated by maximizing the log likelihood function. The extension of the ARIMA time series model into the spatial domain results in the STARIMA (Space–Time Autoregressive Integrated Moving Average) model, which can deliver more accurate prediction results in traffic prediction because of spatio-temporal correlation of traffic data. To capture the spatial correlation, the STARIMA model adds the spatial matrix comprising spatial adjacency and weight structure, and the number of spatial lags for STAR and STMA models. The drawback of the ARIMA model for traffic prediction is the strong assumption that traffic data can become stationary by differencing, which is difficult to be fulfilled because of the non-stationary characteristics of traffic data. By assuming the linear relationship between the input variables and the single output variable, the linear regression model aims to estimate the regression coefficients by using the historical traffic data. KF based methods allow a unified approach for the prediction of all processes that can be given a state space representation. Although, EKF (Extended Kalman Filtering) can be used to deal with the non-linearity of traffic data, it is difficult to have an accurate approximation of most non-linear functions and thus it can lead to relatively large error.

Non-parametric models such as DL (Deep Learning) outperform parametric models because of stochastic, indeterministic, non-linear and multidimensional characteristics of traffic data [5]. DL is a subset of machine learning (ML) which is based on the concept of deep neural network (DNN) and it has been widely used for data classification, natural language processing (NLP) and object recognition [5]. The most popular DL models used for traffic state prediction includes Convolution Neural Network (CNN) [12, 13, 14], Deep Belief Network (DBN) [15, 16], Recurrent Neural Network (RNN) [17, 18, 19] and Autoencoder (AE) [20] etc. CNN is useful for traffic prediction because of the two-dimensional characteristics of traffic data and its ability to extract the spatial feature. CNN is only connected to a smaller subset of input and thus decreases the computational complexity of the training process. DBN is a stacking of multiple RBMs (Restricted Boltzmann Machines), which can be used to estimate the probability distribution of the input traffic data. LSTM is the special type of RNN, which can capture the temporal feature of traffic data, and LSTM can overcome the gradient vanishing problem caused by the standard RNN.

Traffic control strategies can be generally divided into classical methods and learning-based methods. Classical methods develop traffic controller based on control theory or optimization-based techniques, which include dynamic traffic assignment based nonlinear controller [21], standard proportional-integral (PI) controller [22, 23], robust PI controller [24], model-based predictive control (MPC) [25, 26], linear quadratic controller [27], mixed-integer non-linear programming (MINLP) [28], multi-objective optimization based decision-making model [29]. Learning-based methods refer to the utilization of artificial intelligence technologies to achieve decision-making and control for CAVs, which can be further divided into three categories: statistic learning-based method, deep learning-based (DL) method and reinforcement learning-based (RL) method. The RL-based method is currently one of the most commonly used learning-based techniques for traffic control and decision-making because RL can solve complex control problems by using the Markov decision process (MDP) to describe the interaction states of agent and environment [4]. The most popular RL-based methods include Q-learning for adaptive traffic signal control [30, 31], multi-agent RL approaches [32, 33, 34, 35], Nash Q-learning strategy [36]. Many other RL-based approaches are also available in the literature. Q-learning based traffic signal control aims to minimize the average accumulated travel time by greedily selecting action at each iteration. Multi-agent RL approaches are more popularly used in network signal optimization and can be generally divided into centralized RL and decentralized RL, while the former considers the whole system as a single agent and the latter distributes the global control to each agent. Nash Q-learning strategy is a decentralized multi-agent RL strategy, which performs iterated updates based on assuming Nash equilibrium behavior over the current Q-values. It can be shown that traffic signal control using the Nash Q-learning strategy can converge to at least one Nash equilibrium for stationary control policies. However, Nash Q-learning is unable to achieve the Pareto Optimality without consideration of cooperation among different agents.

This chapter provides a comprehensive survey about state-of-the-art traffic state prediction and traffic control techniques. It is organized as follows: In Section 2, we firstly introduce the fundamental structure and main characteristics of two important DL models: CNN and LSTM (Long Short-Term Memory), as well as their advantages in traffic state prediction, then we introduce how to realize hybrid traffic state prediction by combining two models to achieve better accuracy. In Section 3, we detail RL fundamentals and introduce how it can be applied in traffic control and decision-making. We focus on multi-agent RL approaches. Pros and cons are discussed. Section 4 gives the summary of this chapter.

2. DL-based traffic state prediction approaches

In this section, we first briefly overview the machine learning and deep learning concept. Then, we focus on introducing the architectures of two DL models: CNN and LSTM, which show good performance in processing high-dimensional and temporal correlated data. Finally, a hybrid model of CNN and LSTM is described and the research potential is about how to improve the prediction accuracy by incorporating spatio-temporal correlation.

2.1 Overview of deep learning

ML approaches are broadly classified into two categories, i.e., Supervised Learning and Unsupervised Learning [5]. Supervised Learning requires input data to be clearly labeled. It involves a function $y=f\left(x\right)$ that maps input x to output y [5]. It aims to perform two tasks: regression and classification. In contrast to supervised learning, unsupervised learning aims to perform data clustering by extracting the data pattern. Some popularly used supervised learning approaches mainly include Random Forest (RF), Support Vector Machine (SVM), Bayesian methods, Artificial Neural Network (ANN), etc., whereas unsupervised learning approaches mainly include Autoencoder, Principal Component Analysis (PCA), Deep Belief Network (DBN), etc. To perform prediction tasks by supervised learning approaches, a model needs to be trained firstly by a training dataset with a certain amount of samples. Then, new predictions can be obtained by inputting the feature vector of new samples to the trained model. Cross-validation is usually used to validate the prediction performance by performing the following procedures for each k-th fold: (i) the whole dataset is divided into K folds; (ii) a model is trained by using $K-1$ folds as training data; (iii) the resulting model is validated by the k-th fold.

DL is a branch of ML which aims to construct a computational model with multiple processing layers to support high-level data abstraction. It can automatically extract the feature from data, without any human interference to explore hidden data relationships among different attributes of the dataset [37]. Concepts of DL are inspired by the thinking process of the human brain. Hence, the majority of DL architectures are using the framework of Artificial Neural Network (ANN), which consists of input, hidden and output layers with nonlinear computational elements (neurons and processing units). The network depth (the number of layers) can be adjusted according to the feature dimensions and complexity of the data. The number of neurons at the input layer is equal to the number of independent variables, while the number of neurons at the output layer is equal to the number of dependent variables, which can be single or multiple. Neurons of two successive layers are connected by weights which are updated while training the model. The neurons at each layer receive the output from the previous layer, which is generated by a weighted summation over inputs and then passed to an activation function (Figure 1).

Figure 1.

(left) ANN with one input layer, two hidden layers and one output layer, W, V, $\mathit{\theta }$: Weighting matrices between IL and HL1, HL1 and HL2, HL2 and OL; (right) an illustration of an output generation.

Let us take the four-layer ANN in Figure 2 for example. During the training process, the value of k-th neuron at the output layer can be calculated by

Figure 2.

CNN structure.

$$o_k=f\left(\sum _{j=1}^J{\theta }_{k,j}{z}_j+b_k\right)$$E1

$$z_j=f\left(\sum _{m=1}^M{v}_{j,m}{y}_m+b_j\right)$$E2

$$y_m=f\left(\sum _{n=1}^N{w}_{m,n}{x}_n+b_m\right)$$E3

where f is the activation function, $x_n$ is the independent variable at the n-th neurons of the input layer, $b_k$, $b_j$ and $b_m$ are bias values, N, M and J are the numbers of neurons at the input layer, hidden layer 1 and hidden layer 2, respectively. Then, the unknown parameters W, V, $\mathit{\theta }$are adjusted to minimize loss function such as MSE (Mean Squared Error) by back propagation algorithms [38, 39].

2.2 Fundamental structure of CNN and LSTM

In this section, we examine two popular DL architectures: CNN and LSTM, which are used popularly for multidimensional and time sequential dataset. CNNs have been extensively applied in various fields, including traffic flow prediction [14, 40, 41], computer vision [42], Face Recognition [43], etc., while LSTMs are special kinds of RNNs, which are mainly applied in the area of temporal data processing, such as traffic state prediction [34, 44], speech processing [45] and NLP (Natural Language Processing) contexts [46], etc.

The significant difference between fully connected ANN and CNN is that CNN neurons are only connected to a smaller subset of input which decreases the total parameters in the network [47]. CNNs have the ability to extract important and distinctive features from multidimensional by making use of filtering operations. A commonly used type of CNNs, which is similar to multi-layer perception (MLP), consists of numerous convolution layers preceding pooling layers and fully connected layers. CNN structure is illustrated in Figure 2, where it consists of the input layer, convolution layer, pooling layer and fully connected layer. Convolution layer outputs higher abstraction of the feature. Each convolution layer uses several filters, which are designed to have a distinct set of weights. Filters used by the convolution layer have the smaller dimensions compared to the data size. In the training phase, filter weights are automatically determined according to an assigned task. The filters of each convolution layer are applied through the input layer by computing the sum of the product of input and filter, leading to a feature map of each filter. Each feature map detects a distinct high-level feature which is then processed by a pooling layer and a fully connected layer. ReLU activation function is applied to remove all negative values in the feature map.

The benefits of CNNs over other statistical learning methods and DL methods are listed followings [48]:

1. CNNs have the weight sharing feature, which reduces the number of trainable network parameters and in turn helps the network speed up the training process and avoid overfitting.

2. Concurrently learning the feature extraction layers and the classification layer causes the model output to be both highly organized and highly reliant on the extracted features.

3. Large-scale network implementation is much easier with CNN than with other neural networks.

CNN and other kinds of ANNs such has MLP are not designed for sequences and time series data because they do not have memory element. In such cases, RNN can deliver more accurate results. RNNs are widely used in traffic state prediction because traffic data has spatiotemporal characteristics, which cannot be captured by CNN or other kinds of ANNs. RNN structure is illustrated in Figure 3, where RNNs involve an internal memory element that memorizes the previous output. The current output $h_t$ is not only based upon present input $x_t$, but also on previous output $h_{t-1}$, which can be expressed by

Figure 3.

RNN structure.

$${\mathit{h}}_{\mathit{t}}=f_h\left({\mathit{W}}_{\mathit{i}}{\mathit{x}}_{\mathit{t}}+{\mathit{W}}_{\mathit{r}}{\mathit{h}}_{\mathit{t}-1}+{\mathit{b}}_{\mathit{h}}\right)$$E4

$${\mathit{y}}_{\mathit{t}}=f_t\left({\mathit{W}}_{\mathit{o}}{\mathit{h}}_{\mathit{t}}+{\mathit{b}}_{\mathit{y}}\right)$$E5

where ${\mathit{W}}_{\mathit{i}}$, ${\mathit{W}}_{\mathit{r}}$ and ${\mathit{W}}_{\mathit{o}}$ are respectively the weighting matrices for the current input vector ${\mathit{x}}_{\mathit{t}}$, previous output vector ${\mathit{h}}_{\mathit{t}-\mathbf{1}}$ and current output vector ${\mathit{h}}_{\mathit{t}}$, ${\mathit{b}}_{\mathit{h}}$ and ${\mathit{b}}_{\mathit{y}}$ are the bias vectors, $f_h$ and $f_t$ are the activation functions.

LSTM is firstly proposed in [49] to overcome the gradient vanishing problems generated by other RNNs. A typical LSTM network consists of an input layer, a recursive hidden layer and an output layer. In the recursive hidden layer, each neuron is made up of four structures: a forget gate, an input gate, an output gate and a memory block. The state of the memory cell reflects the features of the input, while the three gates can read, update and delete features stored in the cell. The LSTM structure is illustrated in Figure 4.

Figure 4.

LSTM structure.

The past information carried by the cell state ${\mathit{c}}_{\mathit{t}\mathit{-}\mathbf{1}}$ can be regulated by the current input state ${\mathit{x}}_{\mathit{t}}$, the previous output ${\mathit{h}}_{\mathit{t}\mathit{-}\mathbf{1}}$ and the gate $\mathit{\sigma }$, which is usually composed of a sigmoid neural network layer and a pointwise multiplication operation. From Figure 4, the forget gate ${\mathit{f}}_{\mathit{t}}$, input gate ${\mathit{i}}_{\mathit{t}}$, cell state ${\mathit{c}}_{\mathit{t}}$, output gate ${\mathit{o}}_{\mathit{t}}$, and hidden state ${\mathit{h}}_{\mathit{t}}$ at t-th time instant can be expressed by

$$\begin{array}{l}{\mathit{f}}_{\mathit{t}}=\mathit{\sigma }\left({\mathit{W}}_{\mathit{f}}\left[{\mathit{h}}_{\mathit{t}-1},{\mathit{x}}_{\mathit{t}}\right]+{\mathit{b}}_{\mathit{f}}\right)\\ {\mathit{i}}_{\mathit{t}}=\mathit{\sigma }\left({\mathit{W}}_{\mathit{i}}\left[{\mathit{h}}_{\mathit{t}-1},{\mathit{x}}_{\mathit{t}}\right]+{\mathit{b}}_{\mathit{i}}\right)\\ {\mathit{c}}_{\mathit{t}}={\mathit{f}}_{\mathit{t}}\odot {\mathit{c}}_{\mathit{t}-1}+{\mathit{i}}_{\mathit{t}}\odot \mathit{tanh}\left({\mathit{W}}_{\mathit{c}}\left[{\mathit{h}}_{\mathit{t}-1},{\mathit{x}}_{\mathit{t}}\right]+{\mathit{b}}_{\mathit{c}}\right)\\ {\mathit{o}}_{\mathit{t}}=\mathit{\sigma }\left({\mathit{W}}_{\mathit{o}}\left[{\mathit{h}}_{\mathit{t}-1},{\mathit{x}}_{\mathit{t}}\right]+{\mathit{b}}_{\mathit{o}}\right)\\ {\mathit{h}}_{\mathit{t}}={\mathit{o}}_{\mathit{t}}\odot \mathit{tanh}\left({\mathit{c}}_{\mathit{t}}\right)\end{array}$$E6

where ${\mathit{W}}_{\mathit{.}}$ and ${\mathit{b}}_{\mathit{.}}$ are respectively weighting matrix and bias vector and $.$ denotes the subscripts including f, i, c and o, $\odot$is point-wise multiplication. The forget gate decides which information needs attention and which can be ignored. The information from the current state ${\mathit{x}}_{\mathit{t}}$ and hidden state ${\mathit{h}}_{\mathit{t}-\mathbf{1}}$ are passed through the sigmoid function. Sigmoid generated values between 0 and 1. It concludes whether the part of the old output is necessary. The input gate updates the cell state by the following operations: first, values between 0 and 1 are generated by passing the current state ${\mathit{x}}_{\mathit{t}}$ and previous hidden state ${\mathit{h}}_{\mathit{t}-\mathbf{1}}$ into the second sigmoid function. Then, the same information of the hidden state and current state will be passed through the tanh function to generate values regulated by the first operation. Finally, the current cell state ${\mathit{c}}_{\mathit{t}}$ is updated by weighted summation of the generated values and past cell state ${\mathit{c}}_{\mathit{t}\mathit{-}\mathbf{1}}$. The output gate determines the value of next hidden state. First, the values of the current state ${\mathit{x}}_{\mathit{t}}$ and previous hidden state ${\mathit{h}}_{\mathit{t}-\mathbf{1}}$ are passed into the third sigmoid function. Then, the new cell state generated from the cell state is passed through the tanh function. Based on the final value, the network decides which information the hidden state should carry.

Generally, LSTM can address the vanishing gradient problem that makes network training difficult for a long-sequence temporal data. The long-term dependencies in the data can be learned to improve the prediction accuracy.

2.3 Traffic state prediction with hybrid DL models

Although, CNN and LSTM have advantages in dealing with traffic data with spatiotemporal dependencies, due to the complex and non-linear models of traffic data, it is hard to predict accurate results by using a single model [5]. Some literature proposed that prediction accuracy can be improved by hybrid modeling such as combining CNN and LSTM [50, 51, 52, 53].

The spatial and temporal features can be fully extracted by hybrid models, where CNN in this model is used to capture spatial features of traffic data whereas LSTM is used to extract temporal features. Suppose that we have traffic state data of K locations $\left\{s_{i=1}^K\right\}$ in $\left(t-N,t-1\right)$ are used as inputs to predict the traffic states at $\left(t,t+1,\cdots ,t+h\right)$. The real-time measured data can be arranged into a matrix:

$$\mathit{S}=\left[\begin{array}{c}{\mathit{s}}_1\\ {\mathit{s}}_2\\ ⋮\\ {\mathit{s}}_K\end{array}\right]=\left[\begin{array}{cccc}{s}_{1,t-N}& s_{1,t-N+1}& \cdots & s_{1,t-1}\\ s_{2,t-N}& s_{2,t-N+1}& \cdots & s_{2,t-1}\\ ⋮& ⋮& \ddots & ⋮\\ s_{K,t-N}& s_{K,t-N+1}& \cdots & s_{K,t-1}\end{array}\right]$$E7

Note that $s_{k,t}$ in the matrix can also be a vector which may include flow, speed, position, etc. Traffic state such as traffic flow depicts spatio-temporal characteristics, that is, the traffic state on each location at a certain time instant depends on that of neighboring locations at current or different time instant.

There are mainly two hybridization manners: the first one is to extract spatio-temporal features by concatenating CNN and LSTM, that is, each column of $\mathit{S}$ is firstly input into a CNN model to obtain the high-level spatial feature map, which is then input into a LSTM.

model to capture the temporal features; the second one is to parallelize CNN and LSTM modeling process by considering the extracted spatial and temporal features are of the same importance, that is, the same traffic state data is input into two models, the final prediction is obtained by passing the output of two models through a FC (Fully Connected) layer. The structure of the two hybridizations is illustrated as follows (Figure 5).

Figure 5.

(left) concatenated hybrid model; (right) parallelized hybrid model.

For concatenated hybrid models, the real-time measured data matrix $\mathit{S}$ is firstly parallelized in the time domain; then, a one-dimensional CNN is used to capture high-level spatial features for each channel; finally, the high-level spatial feature map is input into LSTM models to generate the final prediction.

The high-level spatial feature map output by the one-dimensional CNN can be expressed by

$$\mathit{X}=\left[\begin{array}{c}{\mathit{x}}_1\\ {\mathit{x}}_2\\ ⋮\\ {\mathit{x}}_L\end{array}\right]=\left[\begin{array}{cccc}{x}_{1,t-N}& x_{1,t-N+1}& \cdots & x_{1,t-1}\\ x_{2,t-N}& x_{2,t-N+1}& \cdots & x_{2,t-1}\\ ⋮& ⋮& \ddots & ⋮\\ x_{L,t-N}& x_{L,t-N+1}& \cdots & x_{L,t-1}\end{array}\right]$$E8

where $x_{l,t}$ is the l-th high-level feature at the t-th time instant and can be obtained as follows

$$x_{l,t}=f_l\left({\mathit{w}}_t\otimes {\mathit{S}}_t+{\mathit{b}}_{\mathit{t}}\right)$$E9

where ${\mathit{w}}_t$ is the one-dimensional filter with $K-L+1$ coefficients, $\otimes$ is the convolution operation, ${\mathit{S}}_t$ is the t-th column of $\mathit{S}$, ${\mathit{b}}_{\mathit{t}}$ is the bias, $f_l$ denotes the l-th activation function. For simplicity, only one convolution layer in Eq. (9) is displayed. In practice, multiple convolutions and pooling layers can be used to satisfy the demand according to the data size.

To extract the temporal features, the high-level spatial feature vector for single or multiple time instants will be selected for the input of each LSTM, which is denoted as

$$\mathit{F}=\left[{\mathit{F}}_0{\mathit{F}}_1\cdots {\mathit{F}}_{N-1}\right]$$E10

where ${\mathit{F}}_n$ is the high-level spatial feature map for the n-th LSTM network denoted as

$${\mathit{F}}_n=\left[\begin{array}{cccc}{x}_{1,t+n-N}& x_{1,t+n-N+1}& \cdots & x_{1,t+n-N+M-1}\\ x_{2,t+n-N}& x_{2,t+n-N+1}& \cdots & x_{2,t+n-N+M-1}\\ ⋮& ⋮& \ddots & ⋮\\ x_{L,t+n-N}& x_{1,t+n-N+1}& \cdots & x_{L,t+n-N+M-1}\end{array}\right]$$E11

where M is the adjustable input window size. The spatio-temporal features output by LSTM are denoted as $\mathit{H}=\left[\begin{array}{cccc}{\mathit{H}}_0& {\mathit{H}}_1& \cdots & {\mathit{H}}_{N-1}\end{array}\right]$, ${\mathit{H}}_n$ is a $K\times T$ matrix, where T is the adjustable output window size with $M+T\le N$. Combining with Figure 4 and Eq. (6), the generated spatio-temporal features are iteratively determined by

$$\begin{array}{l}{\mathbf{f}}_{\mathbf{n}}=\mathbf{\sigma }\left({\mathbf{W}}_{f,\mathrm{F}}\mathrm{vec}\left({\mathbf{F}}_n\right)+{\mathbf{W}}_{f,\mathrm{H}}\mathrm{vec}\left({\mathbf{H}}_{n-1}\right)+{\mathbf{b}}_{\mathbf{f}}\right)\\ {\mathbf{i}}_{\mathbf{n}}=\mathbf{\sigma }\left({\mathbf{W}}_{i,\mathrm{F}}\mathrm{vec}\left({\mathbf{F}}_n\right)+{\mathbf{W}}_{i,\mathrm{H}}\mathrm{vec}\left({\mathbf{H}}_{n-1}\right)+{\mathbf{b}}_{\mathbf{i}}\right)\\ {\mathbf{c}}_{\mathbf{n}}={\mathbf{f}}_{\mathbf{n}}\odot {\mathbf{c}}_{\mathbf{n}-1}+{\mathbf{i}}_{\mathbf{n}}\odot tanh\left({\mathbf{W}}_{c,\mathrm{F}}\mathrm{vec}\left({\mathbf{F}}_n\right)+{\mathbf{W}}_{c,\mathrm{H}}\mathrm{vec}\left({\mathbf{H}}_{n-1}\right)+{\mathbf{b}}_{\mathbf{c}}\right)\\ {\mathbf{o}}_{\mathbf{n}}=\mathbf{\sigma }\left({\mathbf{W}}_{o,\mathrm{F}}\mathrm{vec}\left({\mathbf{F}}_n\right)+{\mathbf{W}}_{o,\mathrm{H}}\mathrm{vec}\left({\mathbf{H}}_{n-1}\right)+{\mathbf{b}}_{\mathbf{o}}\right)\\ {\mathbf{H}}_n={\mathbf{o}}_{\mathbf{n}}\odot tanh\left({\mathbf{c}}_{\mathbf{n}}\right)\end{array}$$E12

where ${\mathit{W}}_{\ast ,F}$ and ${\mathit{W}}_{\ast ,H}$ are respectively the weighting matrices for the current input high-level spatial feature matrix and previous spatio-temporal feature matrix, $\mathrm{vec}\left(\right)$ is used for vectorization due to different size of ${\mathit{F}}_n$ and ${\mathit{H}}_{n-1}$, $\mathit{\sigma }$ and $\mathit{tanh}$are respectively the sigmoid function and hyperbolic function with vector input.

Concatenated hybrid models utilize a one-dimensional CNN to obtain a smaller range of spatial features, in addition, they do not contain a fully connected layer at the output of LSTM models, and thus concatenated hybrid models are with low learning complexity. However, the temporal features delivered by LSTM have a strong correlation with the spatial features output by CNN, which needs some special assumptions about the raw data.

For parallelized hybrid models, the historical data matrix $\mathit{S}$ need not be parallelized in the time domain, rather it is input into a CNN and LSTM simultaneously to extract the high-level spatial and temporal feature map independently. Then, the final prediction is generated by merging the high-level spatial and temporal features via a fully-connected layer. The high-level spatial feature map can be obtained by filtering $\mathit{S}$ via two-dimensional CNNs. Suppose that we utilize a CNN with L convolution layers, the spatial filter for the l-th layer is denoted as $w_{i,j}^l,i=0,1,\cdots ,I-1;j=0,1,\cdots ,J-1$, where I and J are the size of the spatial filter. Given the historical data matrix S in (7), the output of the l-th layer of the n-th CNN is obtained by

$$\begin{array}{l}{o}_{i,j,n}^{0,c}=s_{i,j+n}\\ o_{i,j,n}^{l,c}=\sigma \left(\sum _{i\prime =0}^{I-1}\sum _{j\prime =0}^{J-1}{w}_{i\prime ,j\prime }^l{o}_{i+i\prime ,j+j\prime ,n}^{l-1,c}+b_{i,j}^l\right)\\ i=0,1,\cdots ,I-1;j=0,1,\cdots ,J-1,n=0,1,\cdots ,N-1\end{array}$$E13

where $o_{i,j,n}^{l,c}$ represents the $\left(i,j\right)$-th output of the l-th layer of the n-th CNN, $\sigma$ is the activation function and $b_{i,j}^l$ is the $\left(i,j\right)$-th bias of the l-th layer of CNN.

A LSTM is utilized to obtain the high-level temporal feature map. The output of the n-th LSTM can be obtained by Eq. (12) with the input of ${\mathit{S}}_{\mathit{n}}$, which can be denoted as

$$\begin{array}{l}{\mathit{S}}_{\mathit{n}}=\left[\begin{array}{cccc}{s}_{1,t-N+n}& s_{1,t-N+n+1}& \cdots & s_{1,t-N+n+M-1}\\ s_{2,t-N+n}& s_{2,t-N+n+1}& \cdots & s_{2,t-N+n+M-1}\\ ⋮& ⋮& \ddots & ⋮\\ s_{K,t-N+n}& s_{K,t-N+n+1}& \cdots & s_{K,t-N+n+M-1}\end{array}\right]\\ {\mathit{o}}_{\mathit{n}}^L=\mathrm{vec}\left({\mathit{H}}_n\right)={\left[\begin{array}{cccc}{o}_{0,n}^L& o_{1,n}^L& \cdots & o_{\mathit{KT}-1,n}^L\end{array}\right]}^T\\ n=0,1,\cdots ,N-1\end{array}$$E14

By posing a fully connected layer to the output of the L-th CNN layer ${\mathit{o}}^{\mathit{L},c}$ and the output of the n-th LSTM ${\mathit{o}}_{\mathit{n}}^L$, the n-th final prediction can be obtained by

$${\mathit{o}}_{\mathit{n}}^F=\sigma \left({\mathit{W}}^F{\left[{\mathit{o}}_{\mathit{n}}^{\mathit{L},\mathrm{c},\mathrm{T}},{\mathit{o}}_{\mathit{n}}^{\mathrm{L},\mathrm{T}}\right]}^T+{\mathit{b}}^F\right)={\left[\begin{array}{cccc}{o}_{0,n}^F& o_{1,n}^F& \cdots & o_{\mathit{KT}-1,n}^F\end{array}\right]}^T$$E15

where ${\mathit{W}}^F$ and ${\mathit{b}}^F$ are the weighting matrix and bias vector for the fully connected layer, respectively.

In parallelized hybrid models, the spatial and temporal feature maps are considered to be of the same importance, and thus are extracted independently. The fully connected layer merges the output of CNN and LSTM without any special assumptions about the high-level spatial and temporal features.

Traffic state has strong periodic features because people get used to repeating some similar or same behaviors on the same time period of different days or the same day of different weeks, e.g., most people routinely go to work in the morning and go home in the evening during the peak hour [53]; most people routinely go for shopping on weekends rather than weekdays, etc. The periodic features can be used as supplementary information to predict the future traffic state. For the short-term traffic state prediction, the real-time data only contains the data before the prediction time instant, but the historical data on previous days or weeks contain the full data of that period, that means, traffic state information after the inspected time instant on previous days or weeks can be utilized to get the prediction about that on the inspected time instant. Suppose we use parallelized hybrid models, the complete prediction structure should contain CNN and LSTM for the real-time data, CNN and bidirectional LSTM for the historical data, which are connected by using a fully connected layer.

The bidirectional LSTM is composed of two independent forward and backward LSTMs, whose inputs are the time series before and after the inspected time instant. The final prediction of bidirectional LSTM is obtained by concatenating the forward and backward LSTMs. The structure of bidirectional LSTM is depicted in Figure 6.

Figure 6.

Bidirectional LSTM structure.

Suppose that additionally, we have historical traffic state data ${\mathit{S}}_{\mathit{d}}$ on the d-th day, which is denoted as

$$\begin{array}{ll}{\mathit{S}}_{\mathit{d}}& =\left[\begin{array}{ccccc}{\mathit{s}}_{\mathit{t}-\mathit{N},\mathit{d}}& \cdots & {\mathit{s}}_{\mathit{t}-\mathbf{1},\mathit{d}}& \cdots & {\mathit{s}}_{\mathit{t}+\mathit{N},\mathit{d}}\end{array}\right]\\ & =\left[\begin{array}{cccc}{s}_{1,t-N,d}& s_{1,t-N+1,d}& \cdots & s_{1,t+N,d}\\ s_{2,t-N,d}& s_{2,t-N,d}& \cdots & s_{2,t+N,d}\\ ⋮& ⋮& \ddots & ⋮\\ s_{K,t-N,d}& s_{K,t-N,d}& \cdots & s_{K,t+N,d}\end{array}\right]\\ d& =1,2,\cdots ,D\end{array}$$E16

where D is the number of previous days. We assume each previous day has data at $2N+1$ time instants available for prediction. The input and output of the forward LSTM are given by Eqs. (14) and (15), and the input of the backward LSTM is given by

$${\mathit{S}}_{\mathit{n},\mathit{d},\mathit{BL}}=\left[\begin{array}{cccc}{s}_{1,t+N-n-M+1,d}& s_{1,t+N-n-M+2,d}& \cdots & s_{1,t+N-n,d}\\ s_{2,t+N-n-M+1,d}& s_{2,t+N-n-M+2,d}& \cdots & s_{2,t+N-n,d}\\ ⋮& ⋮& \ddots & ⋮\\ s_{K,t+N-n-M+1,d}& s_{K,t+N-n-M+2,d}& \cdots & s_{K,t+N-n,d}\end{array}\right]$$E17

Using Eq. (12), the output of the n-th backward LSTM can be obtained by

$${\mathit{o}}_{\mathit{n}}^{\mathrm{BL}}=\mathrm{vec}\left({\mathit{H}}_n^{\mathrm{BL}}\right)={\left[\begin{array}{cccc}{o}_{0,n}^{\mathrm{BL}}& o_{1,n}^{\mathrm{BL}}& \cdots & o_{\mathit{KT}-1,n}^{\mathrm{BL}}\end{array}\right]}^T$$E18

Then, the n-th temporal feature can be obtained by concatenating ${\mathit{o}}_{\mathit{n}}^L$ and ${\mathit{o}}_{\mathit{n}}^{\mathrm{BL}}$.

3. Reinforcement learning based traffic signal control

An accurate and efficient traffic state prediction can provide continuous and precise traffic status and vehicle states based on past information. How to utilize the current and predicted traffic states to make a real-time optimum decision is the main task of the traffic signal control module in ITS. The objectives of traffic signal control include minimizing the average waiting time at multiple intersections, reducing traffic congestion and maximizing network capacity. There exist real-time linear feedback control approaches and MPC (Model-based Predictive Control) that are specifically designed for traffic signal control systems to achieve the targets. The drawback of linear feedback control techniques that have been tried is that the system should always remain in the linear region at all times for the controller. Although, MPC has some advantages such as imposing constraints, the main shortcoming is it needs an accurate dynamic model, which is difficult to be obtained for traffic control systems. Data-driven approaches such as DRL (Deep Reinforcement Learning) based traffic control techniques are widely presented for ITS in recent years because RL can solve complex control problems and deep learning helps to approximate highly nonlinear functions from the complex datasets. In this section, we firstly briefly review the fundamental principles of RL. Then, we focus on multi-agent DRL based traffic signal control techniques such as decentralized multi-agent advantage actor-critic, which can converge to the local optimum and overcome the scalability issue by considering the non-stationarity of MDP transition caused by policy update of the neighborhood; and Nash Q-learning strategy, which can converge to Nash equilibrium by only considering the competition among agents.

3.1 Overview of reinforcement learning

Reinforcement Learning (RL) is a promising data-driven approach for decision-making and control in complex dynamic systems. RL methodology formally comes from a Markov Decision Process (MDP), which is a general mathematical framework sequential decision-making algorithms, and consists of five elements [54]:

• A set of states $\mathit{S}$, which contains all possible states the system can be in;

• A set of actions $\mathit{{\rm A}}$, which contains all possible actions the system can respond;

• Transition probability $T\left(\left.s_{t+1}\right|s_t,a_t\right)$, which maps a state-action pair for each time t to a distribution of next state $s_{t+1}$;

• Reward function $r\left(s_t,a_t,s_{t+1}\right)$ which gives the instantaneous reward for taking action $a_t$ from the state $s_t$ when transitioning to the next state $s_{t+1}$;

• The discount factor $\gamma$ between 0 and 1 for future rewards.

RL aims to maximize a numerically defined reward by interacting with the environment to learn how to behave in an environment without any prior knowledge by learning. In traffic signal control systems, RL is used to find the best control policy ${\pi }^{\ast }$that maximizes the expected cumulative reward $E\left[\left.R_t\right|s,\pi \right]$ for each state s and cumulative discounted reward

$$R_t=\sum _{i=0}^{T-1}{\gamma }^i{r}_{t+i}$$E19

where $\gamma$ is the discount factor that reflects the importance of future rewards, $r_t$ is the t-th instantaneous reward. Choosing a larger$\gamma$ means that the agent’s actions have a higher dependency on future reward, whereas a smaller $\gamma$ results in actions that mostly care about $r_t$.

RL generally can be classified into model-based RL which knows or learns the transition model from state $s_t$ to $s_{t+1}$, and model-free RL which explores the environment without knowing or learning a transition model. Model-based RL emphasizes planning, that is, agents can keep track of all the routes in future time instants by predicting the next state and reward. Model-free RL can estimate the optimal policy without using or estimating the dynamics of the environments. In practice, model-free RL either estimates a value function or the policy by interacting with the environment and observing the responses. Model-free RL can be classified into value-based RL and policy-based RL. Value-based RL is mostly used for the cases that control problems have discrete state-action space. Q-learning and SARSA are two main value-based RL techniques, where the values of state-action pairs (Q-value) are stored in a Q-table, and are learned via the recursive nature of Bellman equations utilizing the Markov property [54]:

$$Q^{\pi }\left(s_t,a_t\right)=E_{\pi }\left[r_t+\gamma Q^{\pi }\left(s_{t+1},\pi \left(s_{t+1}\right)\right)\right]$$E20

where $\pi \left(\left.a\right|s\right)$ is the probability of the action a is selected by given s, $Q$ is the expected accumulative reward given by an action a and a state s

$$Q^{\pi }\left(s,a\right)=E\left[\left.R_t\right|s,a,\pi \right]$$E21

The stochasticity in Eq. (21) comes from the control policy $\pi$ and the transition probability from $s_t$ to $s_{t+1}$ . Value-based RL updates the $Q^{\pi }$ with a learning rate $0<\alpha <1$ by

$$Q^{\pi ,u}\left(s_t,a_t\right)=Q^{\pi }\left(s_t,a_t\right)+\alpha \left(y_t-Q^{\pi }\left(s_t,a_t\right)\right)$$E22

where $y_t$ is the Temporal Difference (TD) target for $Q^{\pi }\left(s_t,a_t\right)$ and can be determined by

$$\begin{array}{l}{y}_t^{q-\mathit{\text{learning}}}=R_t^{\left(n\right)}+{\gamma }^n\underset{a_{t+n}}{\mathit{max}}{Q}^{\pi }\left(s_{t+n},a_{t+n}\right)\\ y_t^{\mathit{\text{sarsa}}}=R_t^{\left(n\right)}+{\gamma }^n{Q}^{\pi }\left(s_{t+n},a_{t+n}\right)\\ R_t^{\left(n\right)}=\sum _{i=0}^{n-1}{\gamma }^i{r}_{t+i}\end{array}$$E23

The learning rate $\alpha$ controls the speed at which $Q^{\pi }\left(s_t,a_t\right)$ updates, a lager $\alpha$ allows a fast update but may oscillate over training epochs while a smaller $\alpha$ tends to reserve the old $Q^{\pi }\left(s_t,a_t\right)$ and thus may take longer time to train.

Value-based RL does not work well for continuous control problems with infinite-dimensional action space or high-dimensional problems because it is difficult to explore all the states in a large and continuous space and store them in a table. In such a case, policy-based RL can provide better solutions than value-based RL. By treating the policy ${\pi }_{\theta }$ as a probability distribution over state-action pairs parameterized by $\theta$, policy parameters $\theta$ are updated to maximize the objective function $J\left(\theta \right)$, which can be

$$J\left(\theta \right)=E_{{\pi }_{\theta }}\left[\left.Q^{{\pi }_{\theta }}\left(s,a\right)\right|\theta \right]={\iint }_{s\in S,a\in A}{\pi }_{\theta }\left(\left.a\right|s\right)Q^{{\pi }_{\theta }}\left(s,a\right)\mathit{\text{dsda}}$$E24

The optimum policy parameters $\theta$ are selected to maximize $J\left(\theta \right)$, with

$${\theta }_{\mathrm{opt}}=\underset{\theta }{\mathit{\text{argmax}}}J\left(\theta \right)$$E25

Policy-based RL tries to select the optimum actions by using the gradient of the objective function with respect to $\theta$, which can be written as

$$\begin{array}{ll}{\nabla }_{\theta }J\left(\theta \right)& ={\iint }_{s\in S,a\in A}{Q}^{{\pi }_{\theta }}\left(s,a\right){\nabla }_{\theta }{\pi }_{\theta }\left(\left.a\right|s\right)\mathit{\text{dsda}}\\ & ={\iint }_{s\in S,a\in A}{\pi }_{\theta }\left(\left.a\right|s\right)Q^{{\pi }_{\theta }}\left(s,a\right){\nabla }_{\theta }\mathit{log}{\pi }_{\theta }\left(\left.a\right|s\right)\mathit{\text{dsda}}\\ & =E_{{\pi }_{\theta }}\left[Q^{{\pi }_{\theta }}\left(s,a\right){\nabla }_{\theta }\mathit{log}{\pi }_{\theta }\left(\left.a\right|s\right)\right]\end{array}$$E26

where $Q^{{\pi }_{\theta }}\left(s,a\right)$ cannot be determined directly and thus Monto-Carlo method is used to sample $Q^{{\pi }_{\theta }}\left(s,a\right)$ from M trajectories and take the empirical average

$${\nabla }_{\theta }J\left(\theta \right)\approx \frac{1}{M}\sum _{m=1}^M{R}_{t_m}{\nabla }_{\theta }\mathit{log}{\pi }_{\theta }\left(\left.a\right|s\right)={\nabla }_{\theta }\left[\frac{1}{M}\sum _{m=1}^M{R}_{t_m}\mathit{log}{\pi }_{\theta }\left(\left.a\right|s\right)\right]$$E27

where $R_{t_m}$ is given by Eq. (19). No analytical solution can be provided for Eq. (27), thus, the optimum solution of Eq. (25) can be obtained by stochastic gradient descent algorithms with

$${\theta }_{t+1}={\theta }_t+\alpha R_t{\nabla }_{\theta }\mathit{log}{\pi }_{\theta }\left(\left.a\right|s\right)$$E28

where $R_t$ is an estimator of the mean of the reward function. Eq. (28) shows that policy gradient can learn a stochastic policy by the update of the parameters $\theta$ at each iteration. Thus, policy-based RL does not need to implement an exploration and exploitation trade off. A stochastic policy allows the agent to explore the state space without always taking the same action. However, policy-based RL typically converges to a local optimum rather than a global optimum.

Actor-critic RL combines the characteristics of policy-based methods and value-based methods, in which an actor is used to control the agent’s behaviors based on policy, critic evaluates the taken action based on value function. From Eq. (27), the objective function can be rewritten as

$$J\left(\theta \right)\approx \frac{1}{M}\sum _{m=1}^M{R}_{t_m}\mathit{log}{\pi }_{\theta }\left(\left.a_{t_m}\right|s_{t_m}\right)$$E29

The loss function for policy and value updating can be respectively defined as

$$\begin{array}{c}L\left(\theta \right)=-\frac{1}{M}\sum _{m=1}^M{R}_{t_m}\mathit{log}{\pi }_{\theta }\left(\left.a_{t_m}\right|s_{t_m}\right)\\ L\left(w\right)=\frac{1}{M}\sum _{m=1}^M{\left(R_{t_m}-V_w\left(s_{t_m}\right)\right)}^2\end{array}$$E30

where $V_w\left(s_{t_m}\right)$ is the approximation function for $Q^{{\pi }_{\theta }}\left(s_{t_m},a_{t_m}\right)$ and $w$ is its parameter. Actor-critic RL aims to iteratively find the optimum $\theta$ and $w$ to minimize the objective functions in (30).

Recall that $R_{t_m}$is obtained by taking T samples from the stored minibatch with $R_{t_m}={\sum }_{i=0}^{T-1}{\gamma }^i{r}_{t_m+i}$, thus it may have a relatively large bias and variance. Advantage Actor-Critic (A2C) aims to solve the problem by learning the Advantage values $A_{t_m}$ instead of $R_{t_m}$, which is defined by

$$A_{t_m}=R_{t_m}+{\gamma }^T{V}_{w^{-}}\left(s_{t_m+T}\right)-V_{w^{-}}\left(s_{t_m}\right)$$E31

where $w^{-}$ is the parameter of the approximation function for the last iteration. Then, the loss function for policy updating can be rewritten by

$$L\left(\theta \right)=-\frac{1}{M}\sum _{m=1}^M{A}_{t_m}\mathit{log}{\pi }_{\theta }\left(\left.a_{t_m}\right|s_{t_m}\right)$$E32

3.2 Multi-agent deep reinforcement learning based traffic signal control

A real traffic network consists of multiple signalized intersections, each of which can be considered as an agent. The states for the i–th agent (intersection) such as the total number of approaching vehicles, position and speed of each vehicle, the vehicle flow and density of the links, etc. are not only determined by the i-th action (adjustment of green-time proportion) but also influenced by other agents’ actions. Hence, traffic signal control can be modeled as a cooperative and competitive game, where the learning process requires considering other agents’ actions to reach a globally optimum solution. When multiple agents are presented, the standard MDP is no longer suitable for describing the environment because actions from other agents can influence the state dynamics. In such a case, a Markov game can be defined by the tuple $\left(N,{\left\{{\mathit{S}}_{\mathit{i}}\right\}}_{\mathit{i}\in \mathit{N}},{\left\{{\mathit{A}}_{\mathit{i}}\right\}}_{\mathit{i}\in \mathit{N}},T,{\left\{{\pi }_{{\theta }_i}\right\}}_{i\in N},{\left\{r_i\right\}}_{i\in N},\gamma \right)$, where

• N is the number of agents with $N>1$;

• A set of states space of the i-th agent ${\mathit{S}}_{\mathit{i}}$, which contains all possible states the i-th agent can be in and $\mathit{S}={\mathit{S}}_1\times {\mathit{S}}_2\times \cdots \times {\mathit{S}}_{\mathit{N}}$ is called the joint state space;

• A set of action space of the i-th agent ${\mathit{A}}_{\mathit{i}}$ and $\mathit{A}={\mathit{A}}_1\times {\mathit{A}}_2\times \cdots \times {\mathit{A}}_{\mathit{N}}$ is called the joint action space;

• Transition probability $T\left(\left.s_{t+1,i}\right|s_{t,i},a_{t,1},a_{t,2},\cdots ,a_{t,N}\right)$ of the i-th agent: the probability transiting from $s_{t,i}$ to $s_{t+1,i}$ by a joint action $\mathit{a}=\left[\begin{array}{cccc}{a}_{t,1}& a_{t,2}& \cdots & a_{t,N}\end{array}\right]\in \mathit{A}$;

• Control policy of the i-th agent ${\pi }_{{\theta }_i}$: the probability selecting an action by a given state and ${\mathit{\pi }}_{\mathit{\theta }}=\left[\begin{array}{cccc}{\pi }_{{\theta }_1}& {\pi }_{{\theta }_2}& \cdots & {\pi }_{{\theta }_N}\end{array}\right]$ is global control policy;

• The instantaneous reward function of the i-th agent $r_i$;

• $\gamma \in \left[0,1\right]$ is the discount factor.

The centralized multi-agent RL considers the multi-agent systems as a single-agent system with joint state space $\mathit{S}$ and action space $\mathit{A}$ and thus it can achieve the global optimum. However, it is infeasible for large-scale traffic control systems because of the extremely high dimension of joint state-action space [32]. Decentralized Multi-Agent deep RL (MARL) can overcome the scalability issue by distributing the global control to each local agent, which is controlled based on the local observed states and communicated states and actions from other agents.

Suppose we have a multi-intersection traffic network, which can be modeled as $G\left(V,E\right)$. The size of the graph is the number of intersections denoted by N, and $e_{\mathit{ij}}=1$ if vertices $v_i$ and $v_j$ are neighbors. The neighborhood of $v_i$ can be manually selected within a certain coverage limit, denoted by ${\mathit{\Omega }}_{\mathit{i}}$ and thus the local region is defined by ${\mathit{L}}_{\mathit{i}}={\mathit{\Omega }}_{\mathit{i}}\cup v_i$. Thanks to the advancement in communication technologies for ITS, it is possible to share the instantaneous rewards ${\left\{r_i\right\}}_{i\in N}$, states ${\left\{s_{t,i}\right\}}_{i\in N}$, actions ${\left\{a_{t,i}\right\}}_{i\in N}$ and policies ${\left\{{\pi }_{{\theta }_i}\right\}}_{i\in N}$ among agents. The objective of MARL is to maximize the total reward function $Q^{{\pi }_{\theta }}\approx {\sum }_{i=1}^N{Q}_i^{{\pi }_{\theta }}$, where $Q_i^{{\pi }_{\theta }}$ is the local reward of the i-th agent by given global control policy and can be expressed by

$$\begin{array}{c}{Q}_i\left(s_{t,i},a_{t,i},{\pi }_{{\theta }_i,t},s_{t,j=1,\cdots ,N,j\ne i},{\pi }_{{\theta }_j,t,j=1,\cdots ,N,j\ne i}\right)=E\left[\left.\sum _{t=0}^{T-1}{\gamma }^t{r}_{t,i}\right|{\mathit{s}}_{\mathit{t}},{\mathit{\pi }}_{\mathit{\theta },\mathit{t}}\right]\\ =E\left[\left.\sum _{t=0}^{T-1}{\gamma }^t{r}_{t,i}\right|\underset{\text{localstateandpolicy}}{\underbrace{s_{t,i},a_{t,i},{\pi }_{{\theta }_i,t}}},\underset{\text{communicatedstatesandpolicies}}{\underbrace{s_{t,j=1,\cdots ,N,j\ne i},{\pi }_{{\theta }_j,t,j=1,\cdots ,N,j\ne i}}}\right]\\ =E\left[r_{t,i}+\gamma Q_i\left(s_{t+1,i},{\pi }_{{\theta }_i}\left(s_{t+1,i}\right),s_{t+1,j=1,\cdots ,N,j\ne i},{\pi }_{{\theta }_j,t+1,j=1,\cdots ,N,j\ne i}\right)\right]\end{array}$$E33

where the global states and policies can be communicated from all other agents in the system as well as the neighborhood ${\mathit{L}}_{\mathit{i}}$. In multi-agent traffic signal control problems, the summation of each local reward can only be used to approximate $Q^{{\pi }_{\theta }}$ because of competitiveness among different intersections, i.e., a decrease of the average vehicle waiting time at the i-th intersection may cause waiting time increase at the neighboring intersections. Hence, the objective of decentralized MARL can be approximated to be the maximization of each local reward function with consideration of states and policies from the neighborhood, which can be expressed by

$${\mathit{\theta }}_{\mathit{i}}^{\ast }=\underset{{\mathit{\theta }}_{\mathit{i}}}{\mathit{\text{argmax}}}\left[Q_i\left(s_{t,i},a_{t,i},{\pi }_{{\mathit{\theta }}_{\mathit{i}},t},s_{t,j=1,\cdots ,N,j\ne i},{\pi }_{{\theta }_j,t,j=1,\cdots ,N,j\ne i}\right)\right]$$E34

We assume Eq. (33) has continuous state-action space and thus multi-agent A2C can be applied to search the optimum policy parameter. From Eq. (31), the Advantage value for the i-th intersection can be expressed by

$$\begin{array}{c}{A}_{t_m,i}=R_{t_m,i}+{\gamma }^T{V}_{w_i^{-}}\left(\left.s_{t_m+T}\right|{\pi }_{{\theta }_i^{-}},{\pi }_{{\theta }_j^{-},j=1,\cdots ,N,j\ne i}\right)-V_{w_i^{-}}\left(\left.s_{t_m}\right|{\pi }_{{\theta }_i^{-}},{\pi }_{{\theta }_j^{-},j=1,\cdots ,N,j\ne i}\right)\\ =R_{t_m,i}+{\gamma }^T{V}_{w_i^{-}}\left(s_{t_m+T,{\mathit{L}}_{\mathit{i}}}\right)-V_{w_i^{-}}\left(s_{t_m,{\mathit{L}}_{\mathit{i}}}\right)\end{array}$$E35

where $R_{t_m,i}$ is the weighted sum of T samples from the minibatch, $V_{w_i^{-}}\left(\left.s_{t_m}\right|{\pi }_{{\theta }_i^{-}},{\pi }_{{\theta }_j^{-},j=1,\cdots ,N,j\ne i}\right)$ is the approximation of the value function for the input sample $s_{t_m}$ with the function parameter of last time iteration, $T+1$ samples are obtained from the same stationary policy $\left[{\pi }_{{\theta }_i^{-}},{\pi }_{{\theta }_j^{-},j=1,\cdots ,N,j\ne i}\right]$ which respectively represents the control policies for the i-th intersection and neighboring intersections at last time iteration, $s_{t_m,{\mathit{L}}_{\mathit{i}}}≔{\left\{s_{t_m,j}\right\}}_{j\in {\mathit{L}}_{\mathit{i}}}$ represents the states for all neighbors of the i-th intersection at $t_m$. We assume that agents are synchronized, that is, the policy and value updating for all agents happen simultaneously at end of each episode, and the delay for information exchange among agents is ignored. Therefore, within each episode, the dynamic system can be considered to be stationary although the trajectory for each agent is influenced by multiple policies $\left[{\pi }_{{\theta }_i^{-}},{\pi }_{{\theta }_j^{-},j=1,\cdots ,N,j\ne i}\right]$. Then, the loss function for policy and value updating can be obtained as

$$L\left({\theta }_i\right)=-\frac{1}{M}\sum _{m=1}^M{A}_{t_m,i}\mathit{log}{\pi }_{{\theta }_i}\left(\left.a_{t_m,i}\right|s_{t_m,{\mathit{L}}_{\mathit{i}}}\right)L\left(w_i\right)=\frac{1}{M}\sum _{m=1}^M{\left(R_{t_m,i}-V_{w_i}\left(s_{t_m,{\mathit{L}}_{\mathit{i}}}\right)\right)}^2$$E36

If each agent follows Eqs. (35) and (36) in a decentralized manner, a local optimum policy ${\pi }_{{\theta }_i^{\ast }}$can be achieved if other agents can achieve the optimum policy ${\pi }_{{\theta }_j^{\ast },j=1,\cdots ,N,j\ne i}$ within the same episode. However, if ${\theta }_j^{\ast },j=1,\cdots ,N,j\ne i$ cannot be achieved or ${\theta }_j,j=1,\cdots ,N,j\ne i$ are updated within the same episode, the policy gradient may be inconsistent across minibatch and thus the convergence to a local optimum cannot be guaranteed, since $A_{t_m,i}$ is conditioned on the changing $\left[{\pi }_{{\theta }_i},{\pi }_{{\theta }_j,j=1,\cdots ,N,j\ne i}\right]$.

In practice, the information exchange among multiple intersections may not be synchronized and communication delay should be considered, which causes policy changing within the same episode and thus leads to non-stationarity. There is some research that try to stabilize convergence and relieve non-stationarity. Tesauro proposes a “Hyper-Q” learning, in which values of mixed strategies rather than base actions are learned and other agents’ strategies are estimated from observed actions via Bayesian inference [55]. Foerster et al. include low-dimensional fingerprints, such as $\epsilon$ of $\epsilon$-greedy exploration and the number of updates.

To relieve non-stationarity, the key is to keep policies from neighboring agents fixed within one episode. We can apply a DNN network to approximate the local policy ${\pi }_{{\theta }_i,t_m}\left(\left.\cdot \right|s_{t_m,{\mathit{L}}_{\mathit{i}}}\right)$ when size of ${\mathit{L}}_{\mathit{i}}$ is relatively large. If we consider the sampled latest policies from neighbors to be additional input of the DNN network, besides the current state from ${\mathit{L}}_{\mathit{i}}$, the local policy can be rewritten by

$$\begin{array}{l}{\pi }_{{\theta }_i,t_m}={\pi }_{{\theta }_i}\left(\left.\cdot \right|s_{t_m,{\mathit{L}}_{\mathit{i}}},{\pi }_{{\theta }_j^{-},t_m-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)\\ i=1,2,\cdots ,N\end{array}$$E37

Then, the loss function for policy updating can be rewritten by

$$L\left({\theta }_i\right)=-\frac{1}{M}\sum _{m=1}^M{A}_{t_m,i}\mathit{log}{\pi }_{{\theta }_i}\left(\left.a_{t_m,i}\right|s_{t_m,{\mathit{L}}_{\mathit{i}}},{\pi }_{\underset{j}{\overset{-}{\theta }},t_m-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)$$E38

Even if the policies from the neighbors are fixed and are considered to be additional input, it is still difficult to approximate $A_{t_m,i}$ given by Eq. (35) and thus convergence to a local optimum cannot be guaranteed. Recall that the total reward function can be approximated as the summation of local reward functions. Thus, a decomposable global reward with a spatial discount factor can be proposed to solve the problem.

$${\stackrel{\sim }{r}}_{t_m,i}=\sum _{\left.j\in {\mathit{L}}_{\mathit{i}}\right|d\left(i,j\right)=d}{\alpha }^d{r}_{t_m,j}$$E39

where $\alpha$ is the spatial discount factor with $0\le \alpha \le 1$, d is the distance between the i-th agent and j-th agent. The spatial discount factor scales down the reward in spatial order to emphasize the role played by the policy of the local agent. Compared to sharing the same weights across agents, the spatial discounted factor is more flexible for the trade-off between greedy control ($\alpha =0$) and cooperative control ($\alpha =1$), and is more relevant for estimating the advantage of local policy. By applying the spatial discount factor to neighboring states, we have

$${\stackrel{\sim }{s}}_{t_m,{\mathit{L}}_{\mathit{i}}}=s_{t_m,i}\cup \alpha {\left[s_{t_m,j}\right]}_{j\in {\mathit{L}}_{\mathit{i}}}$$E40

Then, the cumulative discounted reward can be obtained by

$${\widehat{R}}_{t_m,i}=\sum _{t_m=0}^{T-1}{\gamma }^t{\stackrel{\sim }{r}}_{t_m,i}$$E41

and the local return and Advantage value $A_{t_m,i}$ for the i-th agent can be expressed by

$$\begin{array}{c}{\stackrel{\sim }{R}}_{t_m,i}={\widehat{R}}_{t_m,i}+{\gamma }^T{V}_{w_i^{-}}\left({\stackrel{\sim }{s}}_{T,{\mathit{L}}_{\mathit{i}}},{\pi }_{{\theta }_j^{-},T-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)\\ A_{t_m,i}={\stackrel{\sim }{R}}_{t_m,i}-V_{w_i^{-}}\left({\stackrel{\sim }{s}}_{t_m,{\mathit{L}}_{\mathit{i}}},{\pi }_{{\theta }_j^{-},t_m-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)\end{array}$$E42

and Eq. (38) can be rewritten as

$$\begin{array}{c}L\left({\theta }_i\right)=-\frac{1}{M}{\sum }_{m=1}^M\left[{\stackrel{\sim }{R}}_{t_m,i}-V_{w_i^{-}}\left({\stackrel{\sim }{s}}_{t_m,{\mathit{L}}_{\mathit{i}}},{\pi }_{{\theta }_j^{-},t_m-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)\right]\\ \times \mathit{log}{\pi }_{{\theta }_i}\left(\left.a_{t_m,i}\right|s_{t_m,{\mathit{L}}_{\mathit{i}}},{\pi }_{{\theta }_j^{-},t_m-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)\end{array}$$E43

The loss function for value updating can be expressed as

$$L\left(w_i\right)=\frac{1}{M}{\sum }_{m=1}^M{\left({\stackrel{\sim }{R}}_{t_m,i}-V_{w_i}\left({\stackrel{\sim }{s}}_{t_m,{\mathit{L}}_{\mathit{i}}},{\pi }_{{\theta }_j^{-},t_m-1,j=1,\cdots ,\left|{\mathit{L}}_{\mathit{i}}\right|,j\ne i}\right)\right)}^2$$E44

The decreolized MA2C can overcome the scalability issue and achieve local optimum (Pareto Optimality). How to achieve the global optimum using a decentralized approach when the global reward function is non-convex in the future research direction.

Compared to decentralized MA2C, Nash Q-learning does not consider cooperation among agents and thus it has lower computational complexity but can only achieve the Nash equilibrium. Nash Q-learning aims to find the optimal global control policy ${\mathit{\pi }}_{\mathit{\theta }}$ by iteratively updating agents’ actions to maximize their Q functions based on assuming Nash equilibrium behavior, that is:

$$\begin{array}{l}{Q}_{t+1,i}\left(s_{t,i},a_{t,1},\cdots ,a_{t,N}\right)=\left(1-\alpha \right)Q_{t,i}\left(s_{t,i},a_{t,1},\cdots ,a_{t,N}\right)+\\ \alpha \left[r_{t,i}+\gamma Q_{t,i}\left(\left.s_{t+1,i},a_{t+1,1}^{\ast },\cdots ,a_{t+1,N}^{\ast }\right|{\mathit{\pi }}_{\mathit{\theta },\mathit{t}}^{\ast }\right)\right]\\ a_{t,n}\leftarrow a_{t+1,n}^{\ast },t\leftarrow t+1\end{array}$$E45

where $Q_{t,i}\left(s_{t,i},a_{t,1},\cdots ,a_{t,N}\right)$ is the Nash Q function at the t-th iteration for the i-th agent, ${\mathit{\pi }}_{\mathit{\theta },\mathit{t}}^{\ast }$ is the joint Nash equilibrium strategy at the t-th iteration. Under the joint Nash equilibrium strategy, the following relation should be fulfilled:

$$\begin{array}{l}{Q}_{t,i}\left(\left.s_{t+1,i},a_{t+1,1}^{\ast },\cdots ,a_{t+1,N}^{\ast }\right|{\mathit{\pi }}_{\mathit{\theta },\mathit{t}+1}^{\ast }\right)\ge \\ Q_{t,i}\left(\left.s_{t+1,i},a_{t+1,1}^{\ast },\cdots ,a_{t+1,N}^{\ast }\right|{\pi }_{{\theta }_1,t+1}^{\ast },\cdots ,{\pi }_{{\theta }_{i-1},t+1}^{\ast },{\pi }_{{\theta }_i,t+1},{\pi }_{{\theta }_{i+1},t+1}^{\ast },\cdots ,{\pi }_{{\theta }_N,t+1}^{\ast }\right)\\ \mathit{\text{for i}}=1,2,\cdots ,N\end{array}$$E46

Eqs. (45) and (46) show that at each iteration t, agent i observes its current state $s_{t,i}$ and takes action to maximize its Q function based on $s_{t,i}$ and other agents’ actions. The update of i-th action will cause the update of actions of agents $-i$, which represents all agents excluding the agent i. The t-th joint Nash equilibrium strategy will not be obtained until the convergence of the joint Nash equilibrium action is reached.

In traffic signal control application, the state space $\mathit{S}$ can be the number of vehicles, positions, speeds and lane order of vehicles, phase duration, etc., for the specific intersections, the action space $\mathit{A}$ can be phase switch, phase duration or phase percentage, etc., the reward $r$ can be queue length, average waiting time, cumulative time delay, network capacity etc. The objective of the multi-agent RL strategy is to minimize the accumulated average waiting for time or queue length etc.

By conducting a simulation on SUMO for a two-intersection case, we can observe in Figure 7 that the centralized DQN outperform the centralized Q-learning in terms of reward value (Average Waiting Time/s) and convergence rate (the Number of Iterations). When the number of agents is small (two, in this case), by using the centralized methods, the average waiting time can converge to the local optimum, which is more optimal than the Nash equilibrium delivered by Nash Q learning. However, the convergence rate of Nash Q learning is higher than that of centralized methods.

Figure 7.

Comparison of different multi-agent RL methods for traffic signal control.

4. Summary

In this chapter, we introduced deep learning-based traffic state prediction technique, which can provide accurate future information for traffic control and decision making. The traffic state data depicts a strong correlation in the spatial and temporal domain, which can be utilized by applying CNN and LSTM techniques to improve the prediction accuracy. CNN technique is used to capture high-level spatial features while LSTM can provide excellent performance in dealing with time-sequential data by extracting high-level temporal features. We firstly reviewed the fundamentals of deep learning and presented the architecture of CNN and LSTM. Then, we introduced how to combine these two models to form concatenated hybrid models and parallelized hybrid models. Finally, we proposed bidirectional LSTM models to enhance prediction performance by learning additional high-level temporal features from the historical data in previous days.

Furthermore, we introduced the decentralized multi-agent advantage Actor-Critic technique and Nash Q learning for traffic signal control applications. We firstly briefly review the fundamental principles of RL. Then, we focus on multi-agent DRL-based traffic signal control techniques such as decentralized multi-agent advantage actor-critic, which can converge to the local optimum and overcome the scalability issue by considering the non-stationarity of MDP transition caused by policy update of the neighborhood.

The main contribution of this chapter can be summarized as followings:

• We reviewed the state-of-the-art technique in traffic state prediction and traffic control strategies, and provide readers with a clear framework for understanding how to apply deep learning models to traffic state prediction and how to deal with multi-agent traffic control by using RL strategies.

• We proposed the hybrid prediction models, which can utilize CNN and LSTM to capture the spatio-temporal feature of traffic data.

• We proposed a multi-agent deep RL (MARL) strategy, which conducts in a decentralized manner and considers the cooperation among agents and thus can overcome the scalability issue and achieve local optimum.

• We compared the centralized RL Q-learning, DQN to the Nash Q-learning strategy in terms of the reward value and convergence rate.