Learning Scalable Multi-Agent Coordination by Spatial Differentiation for Traffic Signal Control
^††thanks:

The existing traffic signal control (TSC) methods can be divided into two categories: rule-based methods and learning-based methods. The former transforms the problem into a rule-based optimization problem; the later one seeks control strategy from the traffic flow data.

For the rule-based methods, such as Webster[9], GreenWave[10] and Max-pressure[5], a traffic signal optimization problem is usually solved under some assumptions like a preset period or fixed cycle-based phase sequence[4]. Webster is used for an isolated intersection and is a widely-used method in TSC. It assumes that the traffic flow is uniform during a certain period and constructs a closed-form equation to generate the optimal cycle length and phase split for a single intersection that minimizes the travel time of all vehicles passing the intersection. GreenWave is a classical method in the transportation field to implement coordination, which aims to optimize the offsets to reduce the number of stops for vehicles travelling along one specific direction. Max-pressure aims to reduce the risk of over-saturation by balancing queue length between adjacent intersections and minimizing the “pressure” of the phases for an intersection. However, the unpractical assumptions in these methods might not lead to excellent performance.

Recently, the DRL technique, as a popular learning-based method, has been proposed to control traffic signals due to its capability of online optimization without prior knowledge about the given environment. At present, DRL has been successfully applied to the single-intersection regulation of traffic signal [3] by regarding the intersection as an agent. The results of various state-of-the-art DRL algorithms are compared in [11], showing that Deep Q-Networks algorithm is more suitable for the solution of TSC tasks. However, the problem with multiple intersections is still a frontier.

Existing MARL algorithms focus on collaboration among agents and can be divided into centralized and decentralized setting according to various information structures[7]. Independent reinforcement learning (IRL), as a fully decentralized setting, directly perform a DRL algorithm for each agent with neither explicit nor implicit information exchange with each other. This method has been applied in multi-intersection TSC problem[12][13]. However, the environment is shared in MARL, and it changes with the policy and state of each agent[14]. For one of the agents, the environment is dynamic and non-stationary, leads to convergence problems. Tan et.al.[15] compares IRL with Value Decomposition Networks (VDN) and illustrates the disadvantages of IRL. As a centralized method, there exists a central controller in VDN which integrates the value function of each agent to obtain a joint action-value function. The integration strategy is to add them directly. Moreover, QMIX[16], as a extend of VDN, uses state information and integrates them in a nonlinear way and gets a stronger approximation ability than VDN. Both QMIX and VDN are typical centralized MARL algorithms with communication, and this joint-action idea has been already used in TSC[17].

Based on these centralized methods, recent TSC studies condense the global scope into a smaller neighborhood[8][18][19] and use graph convolution network (GCN) to achieve coordination. Colight[8] introduces the concept of attention mechanism and realized cooperation by integrating observations in a neighborhood implicitly into a hidden state. However, as mentioned in Colight, the neighborhood scope is a constant, so the traffic information among intersections cannot be utilized to determine the range of the neighborhood. Due to the usage of GCN and Multi-head Attention techniques, these methods still need to gather information for centralized computing and betray the intention of distribution.

In fact, such a central controller does not exist in many applications, apart from those that can easily have a global perspective, like video games[7]. Considering the demand for the scalability in TSC, setting a central controller is impractical. Therefore, we need to seek a compromise solution which is both convergent and scalable. This setting is referred to as a decentralized one with networked agents[7].

In this paper, we first regard each intersection as a DRL agent and transform the TSC problem into a Markov Decision Process (MDP). Unlike existing work, this paper is aiming at improving method scalability while ensuring a SOTA performance. To achieve this goal, we introduce a structural prior about road networks as an inductive bias and extend the Markov Chain theory to the temporal-spatial domain for the coordination.

The change of future states and rewards from distant intersections is multiplied by the spatial discount rate $\gamma$ (Note that it represents the temporal-spatial discount on multi-agent information, not the ordinary meaning used in temporal difference, and it will be distinguished in detail later) and taken into account when learning the current intersection policy. This information is used as a penalty to correct the calculation of current rewards so that the agents have the ability to collaborate. Due to the various traffic volume of each road, the influence of surrounding intersections may be different. Therefore, the attention mechanism is introduced in this paper to correct the influence weight of surroundings on the current intersection.

To summarize, our main contributions are as follows:

• •

  We propose a coordination framework, defined as $\gamma$-Reward, which can communicate with adjacent intersections and even further in a scalable way by sharing future states and rewards and achieve global optimal control of the TSC problem.

• •

  Instead of Multi-head Attention, the spatial differentiation method is proposed to collect the temporal-spatial information in a decentralized way and amend the current reward by recursion.

• •

  We just use attention in the neighborhood for distinguishing various significance, and update the attention score parameters in spatial differentiation formula by imitating the idea of the target network.

• •

  It is found in the test results of various road networks that the $\gamma$-Reward series, including original $\gamma$-Reward and $\gamma$-Attention-Reward, maintain a SOTA performance while achieving a better scalability.

• •

  Lane: Lane is part of a roadway that is designated to be used by a single line of vehicles [20]. There are two kinds of lanes: entering lane and exiting lane[21]. Each intersection consists of multiple lanes.

• •

  Phase: A phase is a combination of movement signals[4]. Figure 1(a) shows eight main directions of vehicles at the intersection. Note that the direction of turning right is usually ignored in these problems since it can execute every time without caring for the traffic signal. The directions in the same phase need not be a conflict which is shown in Figure 1(b). Phase is the unit of TSC, and only one phase can turn green at a time.

• •

  Neighbor intersection: The intersections which directly connect to the current intersection. In an informal road network, each intersection usually has at most four neighbors.

• •

  Waiting vehicle: If a vehicle on an entering lane has a speed lower than a threshold, then we define it as a waiting vehicle, which means it is slowing down to wait for the red light.

By using DRL, we regard the TSC problem as MDP. An individual DRL agent controls one of the intersections. They need to observe part of the environmental state $\mathcal{O}$ and get actions $\mathcal{A}$ according to these observations to determine which phase in the intersection needs to turn green. The effect of control is fed back from the environment in the form of reward $\mathcal{R}$. The goal of the DRL agent is to maximize the reward function by continuously exploring and exploiting based on constant interaction with the environment. In this paper, the problem requests to reduce the length of the queue $q_{l}$ or the travel time $T_{w}$ in the road network. To make this problem more suitable for DRL, we can first abstract it into these parts $\mathcal{<O,A,P,R,\pi,\gamma>}$:

• •

  Observation $o_{t}^{i}$ : $\boldsymbol{o}_{t}^{i}=\left(o_{1}^{i},\ldots,o_{t}^{i}\right)$, where $\boldsymbol{o}_{t}^{i}\in\boldsymbol{\mathcal{O}_{t}}^{i}$. Every agent observes the length of the vehicle queue on entering lanes of their intersection. Moreover, to cater to the design of the proposed $\gamma$-Reward algorithm, we also need to observe the number of vehicle on the exiting lanes which connect to neighbor intersections.

• •

  Action $a_{t}^{i}$: $\boldsymbol{a}_{t}^{i}=\left(a_{1}^{i},\ldots,a_{t}^{i}\right)$, where $\boldsymbol{a}_{t}^{i}\in\boldsymbol{\mathcal{A}_{t}}^{i}$. Action can be easily set as the serial number of phase which is chosen to be green.

• •

  Transition probability $\mathcal{P}$: $\mathcal{P}{(o_{t+1}}^{i}|{o_{t}}^{i},{a_{t}}^{i})$ describes the probability from state ${o}_{t}^{i}$ to the next potential state ${o_{t+1}}^{i}$.

• •

  Reward $r_{t}^{i}$: After executing each action $a_{t}^{i}$, we can get a return information to judge whether $a_{t}^{i}$ is good enough for $o_{t}^{i}$. We use the number of waiting vehicle on the entering lanes as a raw reward. For amendatory reward, we use $R_{t}^{i}$ as a representation.

• •

  Policy $\pi$: Policy is what agents need to learn in DRL. It represents the goal of reducing travel time and increasing average speed. For a single agent, $\pi^{i}:{\mathcal{O}_{t}}^{i}\mapsto\mathcal{A}_{t}^{i}$.

• •

  Discount rate $\gamma^{\prime}$: This factor is the common meaning used in Temporal-Difference (see Appendix A.1). To avoid confusion with $\gamma$-Reward , we use $\gamma^{\prime}$ here to replace the original symbol $\gamma$.

By using the Bellman equation, the relationship among these parameters can be formulated. We can gain the optimal phases after iterating these equations:

Coordination among agents plays a critical role in MARL algorithms, either centralized or decentralized. In this paper, we propose a coordination mechanism among distributed agents. Each agent is based on Dueling-Double-Deep Q Network (D3QN)[22][23][24], which is one of the best Q value-based model until now[25]. A detailed description of it can be found in Appendix A. We found that some studies already use D3QN directly on the TSC problem [26], but it can only be used as an independent Q-learning (IQL) method in the multi-intersection problem. For the TSC problem, the idea of distributed agents is wise and what we need is an appropriate decentralized coordination mechanism. Therefore, we propose $\gamma$-Reward framework for coordination (Figure 3).

The basic theory of DRL inspires the main idea of this article. For the TSC problem, not only the temporal decision should be regarded as MDP, the road network itself is more like a Markov Chain since the decision of the current intersection will affect other intersections in the future. So it should consider not only the TD-error (see Appendix A.1) in time, but also a “TD-error” in space which is defined as the spatial differentiation.

Figure 4 shows a diagram of multi-intersection road network with $3\times 3$ intersections. Since the decision of intersection $I_{22}$ at time $t$ will affect the next intersection $I_{23}$ at time $t+n$, the result of intersection $I_{22}$ at time $t$ should be affected not only by the current intersection reward $r^{I_{22}}_{t}$, but also by the reward $r^{j}_{t+n}$ of the surrounding intersections at time $t+n$, where $j\in{I_{12},I_{21},I_{23},I_{32}}$. The formula of spatial differentiation is as follows:

Where $\mathcal{N}_{I_{22}}=\{I_{12},I_{21},I_{23},I_{32}\}$ represents the four intersections around intersection $I_{22}$. The parameter $n$ is called delay span which represents the time span of most vehicles reach the next intersection after current action $a_{t}$. It is related to the length of the road, the average velocity on the exiting lane and sample interval. The whole formula can also be treated as value function of reward, thus it is a spatial differentiation of reward-value function.

In Equation 2, ${R^{j}_{t+n}}/{r^{j}_{t}}$ shows the change of traffic capacity at intersection $j$ between time $t$ and $t+n$. If ${R^{j}_{t+n}}/{r^{j}_{t}}$ is greater than threshold $c$, it indicates that the traffic capacity of the intersection $j$ is deteriorated, in other words, the decision of the intersection $I_{22}$ at the time $t$ will cause the adjacent intersection $j$ to be more congested; conversely, ${R^{j}_{t+n}}/{r^{j}_{t}}$ less than $c$ indicates that the capacity of intersection $j$ is improved, and the decision of the intersection $I_{22}$ at time $t$ is good for $j$. Through some region transformations, the differential item is served as a penalty. It finally multiplies by a spatial discount factor $\gamma$ as an amendment to reward. Since the training goal of DRL is to maximize the reward function, the existence of the penalty item forces the agent to pay attention to the situation around the intersection while improving its own policy.

This equation is also in line with the idea of MARL with networked agents which dates back to Varshavskaya et al. [27]. $\mathcal{QD}$-learning[28] further gives a convergence proof of this kind of MARL algorithm. It incorporates the idea of consensus + innovation to the standard Q-learning algorithm and has the following Q-value update equation:

where the term after $\alpha_{t,o,a}$ denotes a local innovation potential that incorporates newly obtained observations, and the term after $\beta_{t,o,a}$ is a consensus potential (agent collaboration) which captures the difference of Q-value estimates from its neighbors.

Analogously, our Q-value update equation can be changed as follows:

The spatial differentiation term denotes the consensus like $\mathcal{QD}$-learning and we further construct the communication in the temporal domain and the spatial domain at the same time. Although Equation 2 uses future information which sounds contrary to the causality, it is achievable in the programming. Since we use Q-learning as a basic model which is off-policy, it saves the trajectory of state-action pair and the obtained reward into a replay buffer. In this way, the raw reward $r^{i}_{t}$ is saved first and then corrected after $n$ steps. Therefore the calculation process can be realized (see Appendix B for pseudocode).

The spatial differentiation formula proposed in the previous section is based on the fact that each intersection in the road network has the same situation. In other words, the levels of them are equal. But in reality, the levels of the intersections in the road network are different, some have only one or two lanes, and others may have four to six. Imagine if the intersection $I_{22}$ in Figure 4 is a two-way road which has eight lanes, the intersection $I_{23}$ is same as $I_{22}$, while on the other side, the intersection $I_{32}$ is a two-way which only has two lanes. The decision of intersection $I_{22}$ in $I_{22}\Rightarrow I_{23}$ and $I_{22}\Rightarrow I_{32}$ is inevitably different. The discharge of intersection $I_{22}$ can easily lead to excessive congestion at intersection $I_{32}$, but it may not be very serious for intersection $I_{23}$. In addition to the number of lanes at the intersection, the length between each intersection is different, which means that the maximum congestion length each intersection can accept is also different. In summary, when using a spatial differentiation formula correction at an intersection, there are different influence weights for different intersections.

The problems mentioned above can indeed be solved by setting different thresholds to get weights, like [29]. However, the actual road network situation is very complicated. There is no way to include all parameters into consideration. Therefore, we can learn the rules from the traffic data. In this respect, the attention mechanism gives us a good solution.

Attention mechanism [30][31][32] is an algorithm first proposed to solve “seq2seq” translation problem in NLP. Attention can be interpreted broadly as a vector of importance weights: To predict an element, such as a word in a sentence, attention vector can be used to estimate how strongly it is related to other elements, and the sum of its values can be used as an approximation of the target. It breaks the limits of Euclidean distance between data, captures long-range dependencies in the sentences, and provides smoother translations.

In addition to sequence data, Attention can also be used for other types of problems. In the graphics world, the GCN [33] tells us that combining local graph structures with node features can achieve good performances in node classification tasks. However, the way GCN combines the characteristics of neighboring nodes is closely related to the structure of the graph, which limits the generalization ability of the trained model on other graph structures. The GAT [34] proposes a weighted summation of neighboring node features using the attention mechanism. The weights of the neighboring node feature depend entirely on the node characteristics and are independent of the graph structure.

Recent research has begun to introduce the idea of Attention to MARL algorithms. A Multi-Agent Actor-Critic (MAAC) algorithm has been proposed that combines attention mechanism[35]. MAAC encodes the state of the surrounding agents and obtains the contribution value of the surrounding agents to the current agent through the attention network, together with $(o,a)$ of the current agent as an input, the Q value is obtained through an MLP. While the Q network is updated in reverse, the attention network is updated, and the attention scores of the surrounding agents for the current agent are also corrected. Colight applied attention mechanism to the TSC problem of the large-scale road network, it encodes the state and directly obtains the Q value through the Multi-head Attention network.

First, we give the proof of stationarity. Unless the MDP is stationary, the model cannot guarantee convergence to the optimal.

For a stochastic game with multi-agent, the optimal point of the whole system is a Nash equilibrium point which is declared in Definition III.3. $\nu^{i}(s|\pi_{*}^{1},\ldots,\pi_{*}^{m})$ can be interpreted as the discounted except reward $\mathcal{G}$. According to previous two theorems, we can draw the following conclusions.

In the experiment, we use both synthetic data and real-world data. We share the same real-world dataset with Colight for convenience. The datasets mainly include two parts, roadnet and flow. Roadnet describes the number of intersections in the road network, the coordinates, and the number of lanes owned by each intersection. Flow is based on vehicles and lists thousands of vehicles, each vehicle has its own property, such as length, width, max of accuracy, max of speed and, most importantly, trajectory. The experiment used the real-world data of Hangzhou, Jinan in China, and also New York in the USA. Meanwhile, we used two kinds of synthetic data, arterial and grid type. We counted their characteristics and presented them in Table I. $Grid_{3\times 3}uni$ is one-way traffic, and $Grid_{3\times 3}bi$ is two-way with the same road network.

In Chapter II, we have already introduced methods for TSC, including traditional rule-based methods and learning-based methods. The most primitive rule-based methods are still the most common methods nowadays. As a mature rule-based method, Max-Pressure can be used as a representative.

Learning-based methods have been prosperous under the development of deep learning and data science in recent years. They are characterized by the use of large-scale data to approximate optimal strategies through iterative learning. We have chosen several methods as the baseline:

• •

  IQL: Since $\gamma$-Reward is based on the decoupling idea of IQL, and introduces a coordination mechanism so that it can demonstrate the impact of coordination mechanism compared to IQL. Here we use original D3QN, like [26], for comparison.

• •

  QMIX: This is a sophisticated MARL algorithm, which integrates all agents into the same model and concentrates on the learning of joint action reward functions. As a typical one-model method, comparing it with $\gamma$-Reward can effectively observe the advantages and disadvantages of joint learning and independent learning for coordination.

• •

  Colight: Unlike $\gamma$-Reward, Colight is more like QMIX, but not learns a joint action. It uses Attention layers to train the surrounding observation code to replace the observation of the current intersection. Due to its full collection of observation, it can apply Multi-head Attention. By this way, the coordination between agents is realized. $\gamma$-Attention-Reward has made some improvements on this basis. The method of Replay Buffer Amendment is employed to introduce the effect of the current intersection on the surrounding intersection, replacing the hyperparameter $\left|\mathcal{N}_{i}\right|$ in Colight and adding consideration of the impact of actions on both time and space.

Figure 6 and Table II shows the performance comparison between $\gamma$-Reward and the more comprehensive $\gamma$-Attention-Reward and baselines. Each model has trained 100 iterations, and each iteration run 3600 time steps in the simulator. Each action in them lasts at least 10 seconds for avoiding rapid switching phase impracticably. Delay span $n=10s$ and threshold $c=0.8$.

We use the average transit time of the vehicle to evaluate the performance of the model, which is the standard evaluation method in the field of TSC.

The performance of learning-based methods is significantly better than rule-based Max-Pressure (Table II), which is widely proved in many researches.

Among the independent learning DRL model, the performance of $\gamma$-Reward series far exceeds the IQL model. This demonstrates the importance of coordination between agents for global performance improvement.

It is worth noting that, in all road network, the independent learning DRL model shows a stronger astringency than one-model QMIX. That is probably because for a single model, excessive dimensions can make the policy more difficult to learn. However, Colight does not show divergence while achieved excellent results. This may benefit from that it does not make joint decisions through the joint action function, but by sharing network parameters, so that all agents generate independent actions. Since the agents share the model parameters, they will undoubtedly ignore individual differences and sacrifice some performance. Compared to the proposed model, intense oscillations sometimes occur in Colight during training. This is also a result of sharing parameters. Once the model iterating in the wrong direction, it will mislead all agents and lead to horrible congestion in the whole road network. The performance of proposed methods is even better than Colight, which means sharing sensation is not the only way to realize coordination. Sharing results can also help to focus on the whole road network for a single intersection.

In real-world road networks, $\gamma$-Reward and $\gamma$-Attention-Reward do not show gigantic difference. The reason is that all real-world road networks we used are two-way road. We will introduce the study about the attention score later and can be shown in Figure 9 and Figure 10. It has shown its effect in specifically synthetic road networks. Compared $Grid_{6\times 6}bi$ and $Grid_{6\times 6}uni$ in Figure 6, Attention layers distinguish one-way and two-way, and assist agents to achieve a better performance. This will also describe later by revealing the detail of Attention layers.

We use $Arterial_{1\times 6}$ road network to study the impact of different $\gamma$ value. We have chosen [0.1, 0.3, 0.5, 0.7, 0.9] five $\gamma$ values and compared the results. As shown in Figure 7, 0.5 may be a balance point of the penalty item. So for the hyperparameter $\gamma$, we all set it to 0.5.

The core idea of the $\gamma$-Reward algorithm is to correct the reward in the replay buffer. In this section, we use the $Arterial_{1\times 6}$ road network as an example to show how the reward values between different intersections affect each other. Compare the $Grid_{3\times 3}uni$ and $Grid_{3\times 3}bi$ road networks to demonstrate the role of the attention mechanism in the $\gamma$-Reward algorithm improvement.

Scalability is an important standard to evaluate whether a TSC method is meaningful. The proposed methods in this paper are both decentralized, each D3QN agent can be deployed on the embedding device in each intersection respectively. Either the training time or the inference time of our methods is not related to the number of intersections. Besides, the message transmission among neighboring intersections just takes tolerable time and all of the intersections communicate in parallel. Due to the limitation of computing capacity, experiments of larger scale are not able to conduct. Instead, we analyze the scalability by collecting the training time on datasets with different scales which is listed in Figure 11. As the number of intersections increased, the time cost of Colight is significantly larger. In contrast, our methods remain a shorter training time due to the parallel computation. Another advantage is when the road network structure is changed, we only need to train the newly added intersections separately and there is a tiny impact on existing intersections. Therefore, the proposed methods are believed to be scalable.

Real-time traffic communication may have problems like communication delay, information security, and risk of packet loss[44]. Therefore, it is necessary to decouple the calculation of the whole road network. Decentralization is becoming the trend of solutions in TSC problem[29][45]. Colight, while using Multi-head Attention technology and sharing parameter, summarizes the relationship of the global road network and reduces the time complexity and space complexity of training. However, if we apply it to the practice, the global road network information in real-time is first needed to transmit to the central server for calculation, and then the server needs to dispense the resulting actions to each intersection. Note that it is not just transmitting actions of each traffic signal, but also their sensor observations! In contrast, communication in our methods occurs in a small neighborhood, and the messages they need are only several bits. These attributes help the intersections keep in touch in real-time.

The coordination mechanism in this paper can be expended to other multi-agent tasks which face the problem of scalability and real-time. For instance, the power dispatching of power networks can be described as the same as the TSC problem. Power transmission is similar to the traffic flow between two neighboring intersections. Furthermore, the control of a multi-joint tandem robot may be regarded as a multi-agent task. Actions from the joint which nears the base have a consequence on other joints and the end-effecter. We can use the coordination mechanism to consider this effect on neighboring agents or joints and achieve a global optimal performance. There are already broad applications using this kind of coordination mechanism in engineering systems like sensor networks[46], smart grid[47] and robotics[48].