[vstyle =Normal]

# Real-Time Network-Level Traffic Signal Control: An Explicit Multiagent
Coordination Method

Wanyuan Wang, Tianchi Qiao,Jinming Ma,Jiahui Jin,Zhibin Li,Weiwei Wu, and
Yichuan Jiang W. Wang, T. Qiao, J. Jin, W. Wu, and Y. Jiang are with the
School of Computer Science and Engineering, Southeast University, Nanjing,
China (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>yjiang@seu.edu.cn).Z. Li is with the School of
Transportation, Southeast University, Nanjing, China
(e-mail:lizhibin@seu.edu.cn).J. Ma is with the School of Computer Science and
Technology, University of Science and Technology of China, Hefei, China
(e-mail:jinmingm@mail.ustc.edu.cn).Manuscript received Sep. 25, 2022.

###### Abstract

Efficient traffic signal control (TSC) has been one of the most useful ways
for reducing urban road congestion. Key to the challenge of TSC includes 1)
the essential of real-time signal decision, 2) the complexity in traffic
dynamics, and 3) the network-level coordination. Recent efforts that applied
reinforcement learning (RL) methods can query policies by mapping the traffic
state to the signal decision in real-time, however, is inadequate for
unexpected traffic flows. By observing real traffic information, online
planning methods can compute the signal decisions in a responsive manner.
Unfortunately, existing online planning methods such as model-predict control
and schedule driven heuristics, either require high computation complexity or
get stuck in local coordination, and suffer from scalability and efficiency
issues. Against this background, we propose an explicit multiagent
coordination (EMC)-based online planning methods that can satisfy adaptive,
real-time and network-level TSC. By multiagent, we model each intersection as
an autonomous agent, and the coordination efficiency is modeled by a cost
(i.e., congestion index) function between neighbor intersections. By network-
level coordination, each agent exchanges messages with respect to cost
function with its neighbors in a fully decentralized manner. By real-time, the
message passing procedure can interrupt at any time when the real time limit
is reached and agents select the optimal signal decisions according to the
current message. Moreover, we prove our EMC method can guarantee network
stability by borrowing ideas from transportation domain. Finally, we test our
EMC method in both synthetic and real road network datasets. Experimental
results are encouraging: compared to RL and conventional transportation
baselines, our EMC method performs reasonably well in terms of adapting to
real-time traffic dynamics, minimizing vehicle travel time and scalability to
city-scale road networks.

###### Index Terms:

Traffic Signal Control, Multiagent Coordination, Distributed Constraint
Optimization Problem, Message Passing

##  1 Introduction

Nowadays, traffic signal control (TSC) is still dominated by the use of fixed
timing rules such as SCATS [1] and SCOOT [2], which can be pre-defined by
domain experts. However, with the ever-increasing number of vehicles traveling
on urban road networks, these pre-defined TSC rules have become incomplete and
outdated, thereby traffic congestion are becoming the key inconvenience to
drivers. According to the INRIX Global Traffic Scorecard [3], in 2019, an
average driver in the U.S. lost 99 hours a year due to congestion, costing
them nearly $88 billion. Intelligent TSC has the potential to reduce traffic
congestion, energy consumption and CO2 emissions [4, 5, 6]. It is commonly
recognized that modern intelligent TSC should be real-time responsive to
dynamic traffic flows and can scale-up to network-level scenarios [7].

To dynamically adjust TSC decisions according to real traffic, reinforcement
learning (RL) methods can query the learned policy by mapping real traffic
information to the signal decisions [8, 9, 10, 11, 12]. Multiagent RL (MARL)
focuses on coordinating traffic signals, where the individual policy can be
regulated by the global joint state-action critics [13, 14], and temporal and
spatial influences can be learned by deep networks [15, 16, 17, 18]. To scale-
up, hierarchical RL can be applied by decomposing the large-scale road
networks into sub-networks, each sub-network controls its signals in the low-
level, and the centralized upper-level constrains and evaluates the sub-
network policy [19, 20, 10, 21]. Unfortunately, RL based approaches have a
couple of issues that have prevented deployment on real-world TSC: 1) the deep
network-based implicit coordination requires careful implementation and
tedious parameter-tuning, and 2) MARL is trained offline for regular traffic
flows, but is not able to deal with unexpected situations such as emergency
events and disruptions [7, 22, 23].

Category Property | Response Time | Coordination | Parameter | Scalability
---|---|---|---|---
(seconds) | Mechanism | (Based/Free) | # of Intersections
Offline RL | Independent [19, 9, 24, 11] | $\leq$3 | None | Based |  $\sim$ 2500
Coordinated [25, 26, 15, 16, 18] | Local |  $\leq$ 200
Hierarchical [20, 10, 14] | Global |  $\leq$36
Online Planning | Max Pressure [27] |  $\leq$3 | None | Free |  $\sim$2500
Schedule-Driven [28, 7, 29, 30, 23, 31] |  $\leq$3 | Global | Based |  $\leq$25
Centralized MPC [32, 33, 34, 35] |  $\geq$3 | Global | Free |  $\leq$15
Decentralized MPC [36, 37] |  $\geq$80 | Global | Free |  $\leq$34
Our EMC Approach |  $\leq$3 | Global | Free |  $\sim$ 400
TABLE I: Summary of the related TSC methods on response time, coordination
mechanism, parameters-free/based, and the scalability. Parameter-based: in
offline RL, a set of hyper-parameters are necessary for tuning deep networks
and schedule-driven is sensitive to the fine-grained arrival time of each
vehicle.

Online planning methods attempt to search the signal decision for current
traffic flows in real-time and is capable of responsiveness for irregular
traffic flows. For example, by building a traffic prediction model, model-
predictive control (MPC) can plan a sequence of signal actions for the real
traffic [38]. Unfortunately, MPC needs a complex mathematical program to
optimize multiple intersections’ signal sequences [34, 35, 37, 39, 36, 31],
which is inherently susceptible to scalability issues. A recent development in
decentralized online planning that overcomes this scalability issue is
schedule-driven methods [7, 40]. The key idea behind this method is to
formulate TSC problem at each intersection as a machine scheduling problem,
where jobs are represented by clusters of spatially adjacent vehicles [28].
Scalability is ensured by allowing each intersection to use the polynomial
schedule algorithm to search for its own signal plan [29, 30]. Coordination is
achieved by communicating outflows from upstream intersections to downstream
intersections [23]. The success of the schedule-driven approach depends on the
fine-grained sensing information (i.e., the arrival time) of each vehicle,
which is hard to achieve and error-prone in real-world complex traffic
dynamics [12].

To satisfy adaptive, real-time and network-level coordinated TSC, this paper
proposes an explicit multiagent coordination (EMC) approach, which models each
intersection as an autonomous and cooperative agent. By _explicit_ , we
propose a _balance index_ to explicitly characterize the coordination
efficiency among neighbor intersections. The proposed coordination function
can fundamentally align local coordination efficiency with global object of
minimizing average travel time of vehicles. Moreover, EMC only need to access
the number of vehicles waiting at the intersections, which is easier to
achieve than the fine-grained arrival time of each vehicle required in those
schedule-driven online planning methods [27, 24]. Indeed, multiagent
coordination concept has been considered before for TSC, but in a way that
models coordination function as a simple linear weighting of independent
agent’s reward [41, 42, 25, 19] or also models vehicle agents [6]. In
contrast, the proposed EMC only models intersection agents, which can scale to
network-level applications.

In summary, our first contribution of this paper is to propose a novel EMC
framework to model TSC problem, where a coordination function is designed to
regulate signal decisions of neighboring interactions. The second contribution
is to propose a decentralized and anytime message-passing algorithm, which can
optimize the network-level coordination in a real-time manner. By
decentralization, each agent can only exchange messages of coordination
function with neighbors. By anytime, the message passing procedure can
interrupt at any time when the real time limit is reached and each agent
selects the optimal signal decisions by summarizing the current message.
Finally, we conduct comprehensive experiments using both synthetic and real
road network datasets. Experimental results demonstrate the power of EMC
method over traditional transportation heuristics and RL methods with respect
to reduce average travel time of vehicles, especially in city-scale scenarios
with hundreds of intersections.

The remainder of this paper is organized as follows. In Section 2, we give a
brief review of related work on intelligent TSC. In Section 3, we describe the
TSC problem and formulate the TSC as a coordination graph-based EMC problem in
Section 4. We propose an efficient decentralized and anytime message-passing
algorithm in Section 5. In Section 6, we conduct a set of experiments to
evaluate our proposed EMC’s performance. Finally, we conclude our paper and
discuss future work in Section 7.

##  2 Related Work

To address the challenges of dynamic traffic flow, real-time signal control
and network level coordination, there have been multiple threads of research
dedicated to TSC, including offline multiagent reinforcement learning, and
online planning researches such as model-predictive control and conventional
transportation methods. In the following, we review and discuss how related
researches concern on these two domains. Table I gives a brief comparisons of
these researches.

###  2.1 Offline Reinforcement Learning (Offline RL)

Independent RL. Because of the highly dynamic traffic flows, reinforcement
learning (RL), which can directly learn how to take actions in complex and
uncertain environment, has recently been investigated for TSC [43]. In RL,
each intersection/agent interacts with the traffic environment and learns from
rewards to achieve the mapping between the traffic state and the corresponding
signal decisions. Thus, careful reward design is essential to minimize network
travel time of vehicles [44]. Wei et al. [9] weighting multiple factors such
as queue length, delay, waiting time, traffic flow and vehicle speed as the
immediate reward. Inspired by the max-pressure theory proposed in
transportation literature [27], Wei et al. [24] further propose a ”pressure”
reward that has the network flow stability guarantee. In terms of scalability,
independent RL transfers the single agent’s plan to other agents, thereby can
scale up to large-scale applications [45, 11]. However, some intersections are
tightly coupled, without coordination, congestion starts from the upstream
intersections will spread to downstream intersections [41].

Multiagent RL. MARL allows agents to communicate and cooperative with neighbor
agents, has proposed to optimize network-level coordination. For example, Liu
et al. [46] propose a distributed RL method by extending the observable
surroundings of agents with neighbors’ traffic information. Yu et al. [16]
further propose an active communication mechanism where the historical action
and state information is actively communicating to neighbors. The temporal and
spatial influences of other non-neighbor agents to the target agent can also
be learned by the graph attention networks [15, 18]. To improve communication
efficiency, the impact of signal decisions on its neighbors can be explicitly
predicted [17]. In order to coordinate policies in an explicit manner, a
modular $Q$-learning framework is proposed to select the action that can
maximize the sum $Q$ function of each pair of agents [26],and Kuyer et al.
[25] propose a factored $Q$-function to learn the coordination policy between
a pair of connected agents. Using the centralized training and decentralized
execution framework, Chu et al. [13] propose an advantage actor critic (A2C)
mechanism to improve the coordination.

Hierarchical RL. Exploiting the advantage of RL on local connected
intersections, hierarchical RL can be applied by decomposing the network into
sub-networks, where each sub-network controls its signals to maximize the
global performance[20]. For example, Pol and Oliehoek [19] employ the max-plus
mechanism to coordinate local component actions to get the network-level
coordinated policy. The local policy can be better aligned with global
centralized $Q$ function with hybrid loss function [10]. More recently, Ma and
Wu [14] propose a top-down feudal RL where the high-level manager set goals
for their workers, while each lower-level worker controls traffic signals to
fulfill the managerial goals.

Unfortunately, offline RL approaches have multiple issues that have prevented
deployment on real-world TSC: (1) tedious parameter-tuning and an infeasible
amount of simulations are required to learn good policies for multiple
intersections; (2) since the traffic environment will be non-stationary with
multiple agents learning concurrently, deep MARL approaches for TSC are not
stable and may trap into sub-optimal solution; (3) learning-based TSC methods
can be trained efficiently for regular traffic flows, but difficult to apply
in an online manner if traffic flows are changing irregularly (e.g.,unexpected
incidents such as accidents and lane closure happen).

###  2.2 Online Planning

Online methods interleave planning and execution by focusing only on states
that are reachable from the current state, thus is capable of real time
responsiveness for irregular traffic. Max pressure control is an greedy online
planning mechanism, where each intersection independently selects to activate
the next signal with the maximal pressure (i.e., the difference of queue
lengths between upstream and downstream roads) [27]. Such _pressure_ concept
has been used for reward shaping in RL [24]. While max-pressure is simple to
implement, the lack of coordination limits its efficiency in network-level TSC
applications.

Schedule-Driven Method. A recent development in online planning that overcomes
this coordination problem is schedule-driven TSC [7]. By modeling a cluster of
vehicles as indivisible jobs and intersections as machines, the TSC can be
formulated as schedule problems where jobs need to be served within the
minimum delay [28]. The downstream intersection can coordinate with the
upstream neighbors by receiving and responding outflows from its upstream
neighbors. Hu and Smith [23] further extend the basic single direction
coordination mechanism to a bi-directional coordination mechanism. Considering
the impact of the vehicle queue length on traveling delay, a weight is
assigned to each road. For example, Hu and Smith [29] use the link
softpressure as the weight and Wu et al. [31] use the occupancy ratio as the
weight. Given the weight of each road, the signal decision should optimize the
weighted cumulative delay. To tackle with the uncertainty associated with the
vehicle turn movements at intersections,a sample-based constrained
optimization is proposed to minimize expected delay over all vehicles [47].

Despite its scalability and effectiveness, key to schedule-driven approaches
is an ability to sense parameters of clusters $(|c|,arr,dep)$, where $c$ is
the cluster of vehicles, $arr$ (resp. $dep$) is the expected arrival (resp.
departure) time of the first vehicle in the cluster $c$. However, current
point sensors can only provide an inexact estimate of arrival times [30],
where the scheduling efficiency cannot be guaranteed [48]. In contrast, our
proposed EMC approach only requires the expected number of vehicles arriving
at next period, which can be predicted accurately using historical data [49,
50].

Model-Predictive Control (MPC). Equipped with a prediction model describing
the traffic dynamics in a finite-time horizon, MPC approaches focus on the
online long-term traffic optimization problem [38]. By modeling the linear
objective, such as minimizing the queue length of roads, an integer program
can be applied to generate the real-time strategies [33]. In order to optimize
the quadratic objective, such as the balance of queue lengths, quadratic-
program can be used to achieve the exact solution [34], and approximate
dynamic programming is adopted to generate the approximations [32]. On the
other hand, due to the nonlinearity of the prediction model, the mixed-integer
linear program (MILP) is used to reformulate the MPC problem [35]. However,
these centralized MPC solutions to traffic regulation require high
computational time, and create a single point of failure [51]. For example,
Heung et al. [52] propose a centralized coordination mechanisms for
dynamically adjusting offsets, which are inherently susceptible to scalability
issues with tens of intersections. To scale up, Oliveira et al. [36] and Zhou
et al. [37] decompose the centralized MILP into separable formulations, each
can be computed by an independent agent in parallel. For the arterial road
with limited number of intersections, a two-way signal coordination method is
proposed to achieve bandwidth criterion [39].

However, as the situation current stands, MPC approaches are widely believed
not to be able to scale to network-level problems (i.e., take 80 seconds for
34 intersections [37]). The reason for the limited scalability of MPC is the
so-called curse of history: the model prediction behaves like breadth-first
search in the combination action space. Compared with MPC researches, in which
the centralized control is necessary, we propose a fully decentralized control
anytime algorithm that gradually improves the quality of a solution as it runs
and return a solution that is not worse than the previous iteration, thereby
can scale to network-level applications.

Traditional Multiagent Method. In order to understand how the distributed
constraint optimization (DCOP) performs in dynamic changing environments,
Jungers and Bazzan [42] first evaluates DCOP in real-world TSC problems. Kuyer
et al. [25] and Pol and Oliehoek [19] further combine DCOP and RL to optimize
the long-term TSC efficiency. However,the above multiagent methods design a
simple linear weighting of heuristic measures (e.g., queue length, delay,
waiting time, traffic flow and vehicle speed) as the coordination function
between agents, which results in highly sensitive performance [24]. In
contrast, this paper proposes a novel balance index-based coordination
function, which can optimize the ultimate objective of minimizing average
travel time of vehicles directly. Recently, Iwase et al. [6] propose to model
vehicle agents to control the allocation of slots for a particular vehicle,
but only scale-up to small settings with 100 vehicles.

Notation | Description
---|---
$\mathcal{N}=\\{1,\ldots,i,\ldots,n\\}$ | the set of intersections
$\mathcal{N}_{B}\subseteq\mathcal{N}$ | the set of boundary intersections
$\mathcal{L}_{all}=\mathcal{L}\cup\mathcal{L}_{entry}\cup\mathcal{L}_{exist}$ | the set of links/roads
$Neg(i)$ | the neighbors of the intersection $i$
$I(i)$ | the set of links entering $i$
$O(i)$ | the set of links leaving $i$
$l_{ij}$ | the link leaving from $i$ and entering into $j$
$Do_{l}$ | the set of downstream links of $l$
$Up_{l}$ | the set of upstream links of $l$
$(i,h)$ | traffic movement from link $l$ to link $k$
$x(l,h)\in\\{0,1\\}$ | whether the phase $(l,h)$ is actuated
$q(l,h)$ | the queue length of phase $(l,h)$
$f(l,h)$ | the saturation flow of phase $(l,h)$
$r(l,h)\in[0,1]$ | the proportion of vehicles from $l$ to $h$
$d(l)$ | the exogenous flow of entry link $l$
$Q(t)$ | the queue state of road network
$B(t)$ | the balance index of road network
TABLE II: Notation Overview

##  3 The TSC Problem Description

This section presents the TSC problem including the concepts of road network,
movement phases, network state update, and the balance index as well as the
object of TSC. Table II shows the notations used throughout this paper.

Road network. Let $G=\langle\mathcal{N},\mathcal{L}_{all}\rangle$ denote the
road network, where $\mathcal{N}=\\{1,2,\cdots,n\\}$ indicates a set of $n$
signalized intersections, and
$\mathcal{L}_{all}=\mathcal{L}\cup\mathcal{L}_{entry}\cup\mathcal{L}_{exist}$
indicates a set of directed links (i.e., road) in the network. There are three
types of links: an internal link $l\in\mathcal{L}$ goes from its start
intersection $i\in\mathcal{N}$ to its end intersection $j\in\mathcal{N}$; an
entry link $l\in\mathcal{L}_{entry}$ has no start intersection; and an exit
link $l\in\mathcal{L}_{exist}$ has no end intersection. An intersection $j$ is
a neighbor of the intersection $i$, if there exists a link $l$ whose start
(end) and end (start) intersections are $i$ and $j$ respectively. Let $Neg(i)$
denote the neighbors of the intersection $i$. Let $I(i)$ and $O(i)$ denote the
set of links entering into (i.e., input) and leaving from (output) the
intersection $i$, respectively, and $l_{ij}=I(j)\cap O(i)$ indicates the link
leaving from $j$ and entering into $i$. Denoted by the intersection $i$ the
boundary intersection if its input links include entry links, i.e.,
$I(i)\cap\mathcal{L}_{entry}\neq\emptyset$, and by
$\mathcal{N}_{B}\subseteq\mathcal{N}$ the set of boundary intersections. Link
$l$ is upstream (downstream) of link $h$ if $l$ has an end (start)
intersection $i$ and $h$ has an start (end) intersection $i$. Let $Do_{l}$ and
$Up_{l}$ denote the the set of downstream and upstream links of the link $l$,
respectively.

Movement phase. A _traffic movement_ $(l,h)$ is defined as the traffic
traveling across an intersection $i$ from input link $l\in I(i)$ to output
link $h\in O(i)$. The set of movement phases at an intersection $i$ is
$\\{(l,h)\in I(i)\times O(i)\\}$. Conflict-free phases at intersection $i$ can
be simultaneously activated. The signal control at the intersection $i$ can be
represented by $\mathcal{X}_{i}=\\{x_{i}(l,h)\in\\{0,1\\},l\in I(i),h\in
O(i)\\}$, where $x_{i}(l,h)=1$ indicates the green light is activated and the
traffic movement $(l,h)$ is allowed, and $x_{i}(l,h)=0$ indicates the red
light is activated and the traffic movement $(l,h)$ is prohibited. In a
typical intersection as shown in Fig. 1, there are 12 ($4$) traffic movements,
which can be controlled by 4 _movement phases_ : _WE-Straight_ (going straight
from West and East), _SN-Straight_ (going straight from South and North), _WE-
Left_ (turning left from West and East), _SN-Left_ (turning left from South
and North)111It is worth noting that 1) the ”turn right” traffic movement
signal can be always activated and 2) there might be different number of
phases in the real world intersections and four phases model is not a must.

Network State Update. Time is discretized into periods, $t=1,2,\cdots,T$, each
includes a fixed duration of $\tau$ seconds (e.g., 10 seconds). Let $q(l,h)$
denote queue length of movement $(l,h)$, i.e., the number of vehicles waiting
to leave the link $l$ and enter the link $h$. Let $f(l,h)$ denote the
saturation flow of traffic movement $(l,h)$, i.e., if movement $(l,h)$ is
activated at the beginning of the period $t$, there will be at most $f(l,h)$
vehicles traveling from link $l$ to link $h$ at the end of $t$. An inactivated
phase serves zero flow of vehicles. At the beginning of the period $t$, let
$Q(t)=\\{q(l,h)(t)\\}$ denote the queue state of the road network, and
$x(l,h)(t)$ denote whether the phase $(l,h)$ is active (i.e., $x(l,h)(t)=1$)
or not (i.e., $x(l,h)(t)=0$). According to traffic dynamics [27], the queue
state for internal link $l\in\mathcal{L}$ updates as :

$\displaystyle q(l,h)(t+1)=q(l,h)(t)-\overbrace{f(l,h)(t)x(l,h)(t)\wedge
q(l,h)(t)}^{outgoing~{}vehicles}$ $\displaystyle+\overbrace{\sum_{e\in
Up_{l}}\big{[}f(e,l)(t)x(e,l)(t)\wedge
q(e,l)(t)\big{]}r(l,h)(t+1)}^{incoming~{}~{}vehicles}.$ (1)

where the function $x\wedge y=\min\\{x,y\\}$. The second term on the right in
Eq.(3) indicates that the queue length $x(l,h)(t)$ decreases by up to
$f(l,h)(t)$ vehicles during $t$ if $x(l,h)(t)=1$; the third term indicates
that up to $f(e,l)(t)$ vehicles will move from upstream queue $(e,l)$ during
$t$ if $x(e,l)(t)=1$ and they will join queue $(l,h)$ with a probability of
$r(l,h)(t+1)$ at next period $t+1$. This turning proportion parameter
$r(l,h)(t+1)$ indicates the proportion of vehicles leaving from $l$ and
entering to $h$, which are assumed available by prediction from the route
navigation systems [53].

Figure 1: Intersection, movement phases and signal control policy.

The queue update equation for an entry link $l\in\mathcal{L}_{entry}$ is a bit
different since it has no input links but exogenous arrivals:

$\displaystyle q(l,h)(t+1)$
$\displaystyle=q(l,h)(t)-\overbrace{f(l,h)(t)x(l,h)(t)\wedge
q(l,h)(t)}^{{}^{outgoing~{}vehicles}}$
$\displaystyle+\overbrace{d(l)r(l,h)(t+1)}^{incoming~{}~{}vehicles}.$ (2)

where $d(l)$ denote the exogenous flow of vehicles in entry link
$l\in\mathcal{L}_{entry}$, which is also assumed available by estimation, and
$r(l,h)(t+1)$ is the turning proposition.

The Object. The ultimate objective of TSC is to minimize the average travel
time of vehicles. However, the travel time of vehicle is a long-term object
depending on a sequence of signal actions, which cannot be computed until it
has completed its route. Existing researches have investigated short-term
measure such as a weighted combination of queue length, waiting time and delay
[26, 19, 9] or pressure [27, 29, 24] as a proxy for the average travel time.
However, there is no guarantee that existing short-term measures can preserve
the optimal policy. In contrast, this paper proposes a balance index that can
align the short-term measure with the long-term travel time objective, defined
as follows.

######  Definition 1.

The Balance Index. At period $t$, given the queue state, we utilize the
_balance index_ $B_{i}(t)$ to characterize the traffic congestion at the
intersection $i$, which is defined as the sum of squares of all its movements’
queue length, i.e.,

$\displaystyle B_{i}(t)=\sum_{(l,h):l\in I(i),h\in O(i)}[q(l,h)]^{2}.$ (3)

The network-level balance $B(t)$ can be defined as the sum of these
intersections’ balance, i.e., $B(t)=\sum_{i\in\mathcal{N}}B_{i}(t)$.

The intuition behind the balance index is that given a number of vehicles
queuing at an intersection, it will produce the less average waiting time in
the case of these vehicles are distributed at links in a balance manner than
that in the imbalance manner. Moreover, Fig.2 empirically shows the alignment
of the balance index with the average travel time, i.e., the lower value of
the network-level balance index $B(t)$, the less average travel time for
vehicles. In the left of Fig.2, we show the balance index of two methods on
different datasets, i.e., SYN1, SYN2, HZ and JN (the detail description of
these datasets can be seen in experiments), and the right of Fig.2 shows the
average travel time of these methods. By comparison, the balance index can be
used as a proxy measure for system objective (i.e., average travel time).

SYN1SYN2HZJN$1$$1.5$$2$$2.5$Different DatasetsBalance ($\times
10^{3}$)Method1Method2SYN1SYN2HZJN$200$$300$$400$Different DatasetsTravel Time
(s) Figure 2: The efficiency of balance index.LEFT: the balance index of
methods; RIGHT: the average travel time of methods.

Finally, at period $t$, given the current traffic information, including
network state $Q(t)$, exogenous demands $d_{l}(t)$, saturation flow
$f(l,h)(t)$ and turning proportion $r(l,h)$, the optimal online TSC policy
$\vec{x}^{*}(t)=\\{x(l,h)^{*}(t)\\}$ should be selected with the objective of
minimizing the network-level balance at the next period $t+1$, i.e.,

$\displaystyle\vec{x}^{*}(t)=\arg\min_{\vec{x}(t)}B(t+1).$ (4)

where the queue state $Q(t+1)$ is updated by the policy $\vec{x}(t)$ on
current network state $\\{Q(t),f(l,h)(t),d(l)(t),r(l,h)\\}$.

Figure 3: An example of CG formulation for TSC. LEFT: the road network,
MIDDLE: the CG formulation. Each intersection $i$ is modeled as an autonomous
agent $a_{i}$, the internal link balance between intersections $i$ and $j$ is
modeled by the constraint cost $c_{ij}$, and the entry link balance is modeled
by the individual agent cost $c_{i}$,RIGHT:The decentralized message passing
procedure.

##  4 Multiagent Coordination Model for TSC

In this section, we design the congruent multiagent coordination graph to
model the TSC problem, which will be proven to yield the optimal solution.

Coordination Graph (CG). A CG is a 5-tuple
$(\mathcal{A},\mathcal{X},\mathcal{D},\mathcal{E},\mathcal{C})$ such that:

  * •

$\mathcal{A}=\\{a_{1},a_{2},\cdots,a_{n}\\}$ is the set of agents, each agent
has limited computation capacity that can compute and send messages.

  * •

$\mathcal{X}=\\{x_{1},x_{2},\cdots,x_{n}\\}$ is the set of variables, each
takes the value from the finite discrete domain $D_{i}\in\mathcal{D}$. Each
variable $x_{i}$ is controlled by the corresponding agent $a_{i}$. Each agent
can have an individual cost function $c_{i}(x_{i})\in\mathcal{C}$, which only
depends on its own variable $x_{i}$.

  * •

$e_{ij}\in\mathcal{E}$ is the edge connects agents $a_{i}$ and $a_{j}$ if they
interact with each other. The interaction between connected agents $a_{i}$ and
$a_{j}$ is formulated by the local constraint cost function
$c_{ij}(x_{i},x_{j})\in\mathcal{C}$, which is defined as a mapping from the
assignments of the involved binary variables $(x_{i},x_{j})$ to a positive
real, $c_{ij}:D_{i}\times D_{j}\rightarrow\mathbb{R}_{\geq 0}$.

Given a CG, the system cost for the global joint action
$\vec{x}=\\{x_{i}\\}_{a_{i}\in\mathcal{A}}$ is factored as the sum of
individual costs and local edge costs, i.e.,

$\displaystyle
C(\vec{x})=\sum_{a_{i}\in\mathcal{A}}c_{i}(x_{i})+\sum_{e_{ij}\in\mathcal{E}}c_{ij}(x_{i},x_{j}).$
(5)

The objective of a CG is to find the best joint action, $\vec{x}^{*}$, that
minimizes the system cost $C(\vec{x}^{*})$.

The CG Formulation for TSC. The key step toward modeling the TSC problem as a
CG is mapping intersection, movement phase, and objective to the 5 tuples in
the CG model. By capturing the structure of TSC, a straightforward CG
formulation is modeling each agent $a_{i}$ in CG as an intersection $i$ in
TSC222In practice, the intersection signal controller is equipped with
computation unit that can control the traffic light signal [54].. Throughout
this paper, we use agent and intersection interchangeable. Each agent $a_{i}$
holds a decision variable $x_{i}$ determining the movement phase to be
activated. The domain of the variable $x_{i}$ is denoted by
$D_{i}=\\{\emph{WE-Straight},\emph{WE-Left},\emph{SN-Straight},=\emph{SN-
Left}\\}$, which corresponds to four movement phases. For two neighboring
intersections $i$ and $j\in Neg(i)$, there will be an edge
$e_{ij}\in\mathcal{E}$ between agents $a_{i}$ and $a_{j}$.

Mapping Queue Balance to the Constraint Cost. Given a particular variable
assignment $\vec{x}$, one challenge is to construct constraint cost
$\mathcal{C}$ such that when the resulting CG is solved, we obtain a solution
that is congruent to the original TSC problem. Considering different kinds of
links, e.g., entry link and internal link333In this paper, we assume that
vehicles arrive their destination at the exit link, thus the vehicles on the
exit link can be omitted, we model two kinds of constraint cost,

  * •

Mapping the balance of the internal link to the edge cost $c_{ij}$: given two
neighboring agents $a_{i}$ and $a_{j}\in Neg(i)$, we define their local edge
cost $c_{ij}$ as the sum balance of bi-direction links $l_{ij}$ and $l_{ji}$
between them, i.e.,

$\displaystyle c_{ij}(x_{i},x_{j})=\sum_{h\in
O(i)}[q(l_{ij},h)]^{2}+\sum_{h\in O(j)}[q(l_{ji},h)]^{2}.$ (6)

  * •

Mapping the balance of the entry link to the individual agent cost $c_{i}$:
for the entry link $l\in\mathcal{L}_{entry}$, we map its link balance to
individual cost of its downstream boundary intersection. For each boundary
agent $a_{i}\in\mathcal{A}_{B}$, the individual agent cost $c_{i}$ is defined
as sum queue balance of the input entry link, i.e.,

$\displaystyle c_{i}(x_{i})=\sum_{l\in I(i)\cap\mathcal{L}_{entry},h\in
O(i)}[q(l,h)]^{2}.$ (7)

where $\mathcal{A}_{B}$ denote the set of boundary agents (i.e., boundary
intersections $\mathcal{N}_{B}$). For any other non-boundary agent
$a_{i}\notin\mathcal{A}_{B}$, the individual cost $c_{i}$ is set to be zero,
i.e., $c_{i}(x_{i})=0,\forall a_{i}\notin\mathcal{A}_{B},x_{i}\in D_{i}$.

An example in Fig.3(a) and Fig.3(b) show the model. Now we will prove the
equivalence of the constructed CG for TSC with respect to optimal solution.

######  Lemma 1.

The object function of the CG is equivalent to the object function of the
original TSC.

###### Proof.

Given any variable assignment $\vec{x}=(x_{1},x_{2},\cdots,x_{n})$, the object
function of the CG is

$\displaystyle\sum_{a_{i}\in\mathcal{A}_{B}}c_{i}(x_{i})+\sum_{e_{ij}\in\mathcal{E}}c_{ij}(x_{i},x_{j})$
$\displaystyle=\sum_{l\in\mathcal{L}_{entry},h\in
Do(l)}[q(l,h)]^{2}+\sum_{l\in\mathcal{L},h\in Do(l)}[q(l,h)]^{2}$
$\displaystyle=\sum_{l\in\mathcal{L}_{all},h\in
Do_{l}}[q(l,h)]^{2}=\sum_{i\in\mathcal{N}}\sum_{(l,h):l\in I(i),h\in
O(i)}[q(l,h)]^{2}=B.$

∎

##  5 The Online Multiagent Planning Method

The main idea behind online planning method is that give the current network
state $Q(t)$, each agent action selects an action $x_{i}$ that can optimize
the next period network state $Q(t+1)$. Using the CG model, this section
proposes a message passing-based online multiagent planning method for TSC,
which is fully decentralized and real-time. By _decentralization_ , we mean
that each agent can only receive message from and send message to neighbor
agents. By _real-time_ , we mean that each agent can make its signal decision
anytime by summarizing the received message when the time limit is reached.

The proposed online multiagent planning method consists of the following two
stages:

  * •

_network-level coordination_ stage, in which agents coordinate their joint
actions $\vec{x}^{*}=\\{x_{i}^{*}\\}_{a_{i}\in\mathcal{A}}$ to minimize the
network balance $B(t+1)$ at the network period $t+1$;

  * •

_local individual improvement_ stage, in which each agent $a_{i}$ improves the
joint action $x_{i}^{*}$ to reduce its own queue balance $B_{i}(t+1)$.

###  5.1 Network-Level Coordination of Minimizing $B(t+1)$

In message passing procedure, at each iteration, by summarizing the message
received from neighbor agents, each agent sends the message that consists of
the cost value with respect to the action variables to neighbors. The network-
level coordination can be achieved by iteratively message passing between
neighbor agents. Fig.3(c) gives an illustration of the message passing
procedure-based network level coordination.

####  5.1.1 Transforming the CG to the directed acyclic graph (DAG)

In order to avoid the message passing pathology caused by cycles in a CG, we
first select an order on all agents, i.e., transforming a cyclic CG to a DAG
for message passing.

Existing work [55] has constructed the DAG by ordering agents according to the
indices of agents, that is an agent $a_{i}$ is ordered before agent $a_{j}$ if
$i<j$. However, this kind of DAG has an arbitrary diameter, in which the
message passing complexity can be further reduced. In this section, we
transform a given CG to a DAG with the minimum diameter.

The main idea of constructing DAG is that we first determine a sink agent, and
then determine the message passing order of agents according to their distance
to the sink agent. A detailed DAG construction is shown in Algorithm 1, which
consists of two phases.

  * •

Determine the sink agent $a_{s}$. From steps 2-5, we compute the diameter
$dia(a_{i})=\max_{a_{j}\in A}d(a_{i},a_{j})$ of the DAG if the agent $a_{i}$
is determined as the sink agent, where $d(a_{i},a_{j})$ denote the shortest
distance between agents $a_{i}$ and $a_{j}$. The agent $a_{s}$ that has the
shortest diameter $d(a_{s})$ is recorded as the sink agent.

  * •

Determine the message passing order. From steps 6-10, once the sink agent
$a_{s}$ is selected, the message passing order can be selected from _faraway_
agents (i.e., these agents that are far away from the sink agent $a_{s}$) to
_nearby_ agents (i.e., these agents that are close by the sink agent $a_{s}$)
(steps 7-10). For these agents $a_{i}$ and $a_{j}$ that have the same distance
to the sink agent $a_{s}$, the message passing order between $a_{i}$ and
$a_{j}$ is arbitrarily selected.

It should be noted that Algorithm 1 generates the minimum diameter DAG with a
single sink agent.

Input : The coordination graph $CG$.

Output : The message passing order $o$.

1 Initialize $dia=+\infty$, $o=\emptyset$;

2 for  _$a_{i}\in\mathcal{A}$_ do

3 $dia(a_{i})=\max_{a_{j}\in A}d(a_{i},a_{j})$;

4 if  _$dia(a_{i}) <dia$_ then

$dia=dia(a_{i})$, $a_{s}=a_{i}$; // sink agent determination

5

6

7for  _$a_{i},a_{j}\in\mathcal{A}:e_{ij}\in E$_ do

8 if  _$d(a_{s},a_{i})\leq d(a_{s},a_{j})$_ then

9 $o_{ij}=a_{j}\rightarrow a_{i}$;

10 else

11 $o_{ij}=a_{i}\rightarrow a_{j}$;

12

Algorithm 1 Minimum Diameter Directed Acyclic Graph (DAG($o$))

####  5.1.2 Message Passing-based Coordination

To coordinate the global joint action, we would like to employ the Max-
sum_ADVP (Max-Sum through value propagation on an alternating DAG) algorithm,
which has been recently proposed for distributed constraint optimization
problem (DCOP) in multiagent domains [56, 55, 57].

Remarks. Despite the fact that our CG formulation of TSC is compatible with
any complete or incomplete DCOP algorithm, we chose to use Max-Sum_ADVP as it
is one of the fastest and most efficient algorithms in many multiagent
domains. It should be noted that the TSC is actually a minimization problem,
however, we will continue to refer to it as Max-sum since this name is widely
accepted. Compared to traditional Max-sum_ADVP where the model is given, our
main contribution is to taking the DCOP to the real-world TSC problem such as
constraint cost and individual cost modeling, and propose a novel and
efficient algorithm for TSC.

Given a DAG, let $Neg(i)=\\{a_{j}|e_{ij}\in\mathcal{E}\\}$ denote the neighbor
agents of $a_{i}$, $Neg_{foll}(i)\subseteq Neg(i)$ denote the subset of
$a_{i}$’s neighbor agents that are ordered after $a_{i}$, and
$Neg_{prev}(i)\subseteq Neg(i)$ denote the subset of $a_{i}$’s neighbor agents
that are ordered before $a_{i}$. During the message passing process, each
agent $a_{i}$ iteratively collects messages from $Neg_{prev}(i)$ and sends
messages to $Neg_{foll}(i)$. At each iteration, a message $R_{ij}$ sent from
agent $a_{i}$ to the follow agent $a_{j}\in Neg_{foll}(i)$ is a scalar-valued
function of the action space of receiving agent $a_{j}$,

$\displaystyle
R_{ij}(x_{j})=\min_{x_{i}}\\{c_{i}(x_{i})+c_{ij}(x_{i},x_{j})+\sum_{a_{k}\in
Neg_{prev}(i)}R_{ki}(x_{i})\\}.$ (8)

This message for each possible value $x_{j}\in D_{j}$ can be explained as
follows. When agent $a_{j}$ selects the action $x_{j}$, agent $a_{i}$ attempts
to coordinate with $a_{j}$ by selecting his action $x_{i}$ to minimize the sum
of costs incurred by its own cost $c_{i}$, the constraint cost $c_{ij}$ and
that it receives from all previous agents $Neg_{prev}(i)$.

Agents exchange messages until convergence such that the received messages do
not update. Finally, each agent decides its optimal action by summarizing the
messages $R_{ji}$ it receives from its previous agents $a_{j}\in
Neg_{prev}(i)$ in the last iteration. When an agent makes decisions, it
accumulates all costs it receives from previous , and selects an action to
minimize the sum costs. The action selection procedure for each agent $a_{i}$
can be formalized by

$\displaystyle x_{i}^{*}=\arg\max_{x_{i}}\\{c_{i}(x_{i})+\sum_{j\in
Neg_{prev}(i)}R_{ji}(x_{i})\\}.$ (9)

Input : The message passing order $o$.

Output : The joint action
$\vec{x}^{*}=\\{x_{1}^{*},x_{2}^{*},\cdots,x_{n}^{*}\\}$.

1 while  _time budget is remained_ do

2 perform Message-Passing($\langle o,dia(o)\rangle$);

3 $x_{s}^{*}\leftarrow$ current optimal decision by Eq.(9);

4 $o^{\prime}$ $\leftarrow$ reverse($o$);

5 perform Message-Passing($\langle o^{\prime},dia(o^{\prime})\rangle$);

6

7Compute the coordinated action $x_{i}^{*}$ by Eq.(9);

8 Function  _Message-Passing $(\langle o,dia(o)\rangle)$_:

9 for  _$dia(o)$ _iterations__ do

10 for  _$a_{i}\in\mathcal{A}$_ do

11 $Neg_{foll}(i)\leftarrow$ $\\{a_{j}\in Neg(i):a_{j}$ is before $a_{i}$ in
order $o$ $\\}$;

12 $Neg_{prev}(i)\leftarrow Neg(i)\setminus Neg_{foll}(i)$;

13 Collect messages from $Neg_{prev}(i)$;

14 for  _$a_{j}\in Neg_{foll}(i)$_ do

15 send message $R_{ij}$ by Eq.(8) to $a_{j}$;

16

17

18

Algorithm 2 Network-Level Coordination (NL-Coor$(o,dia(o))$)

We formally propose the network-level coordination (NL-Coor) algorithm in
Algorithm 2, which includes two phases of Message-Passing procedure i.e.,
message passing on the forward order $o$ (step 2) and on the reverse order
$o^{\prime}\leftarrow$ reverse($o$) (step 4). The function Message-
Passing$(\langle o,dia(o)\rangle)$ presents a sketch of the message passing
procedure. At each iteration, each agent $a_{i}$ first aggregates the message
received from ”previous” agents $Neg_{prev}(i)$ and sent messages to ”follow”
agents $Neg_{foll}(i)$ according to Eq.(8). In step 7, the message passing
process terminates after $dia(o)$ iterations, where $dia(o)$ denote the
diameter of the message passing order $o$. After Message-Passing converges in
both directions or the time limit is reached (step 1), each agent selects its
own decision $x_{i}^{*}$ according to Eq.(9) (step 5).

######  Lemma 2.

Given the message passing order $o$, after $dia(o)$ iterations of message
passing, the content of the message each agent $a_{i}$ receives does not
change, i.e., the message passing process converges after $dia(o)$ iterations.

At the iteration $t$, the content of messages produced by agents is dependent
only on the content of messages they received last iteration $t-1$ from
previous agents. Starting from the 1st iteration, the boundary agents (that
have no previous agents) will always send the constant messages. Starting from
the 2nd iteration, the agents that are followed immediately by the boundary
agents will always send the constant messages. By induction, after the
$dia(o)$ iterations, the sink agent will receive the constant messages.

######  Lemma 3.

The message passing procedure Message-Passing converges the fastest on the DAG
generated by Algorithm 1.

Derived from the Lemma 2 that Message-Passing procedure converges within
$dia(o)$ iterations. Since Algorithm 1 generates a DAG with the minimum
diameter, we can conclude that Message-Passing procedure will converge with
the minimum iterations.

####  5.1.3 Stability Analysis

In this section, we show the proposed NL-Coor mechanism stabilizes the
network. Stability is an important metric to evaluate the TSC policy in
transportation domain, which is defined as follows.

######  Definition 2.

(Network stability). The network state process $Q(t)=\\{q(l,h)(t)\\}$ is
stable in the mean (and $\vec{x}$ is a stabilizing TSC policy) if for some
$K<\infty$

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\sum_{l,h}\mathbb{E}[q(l,h)(t)]<K,\forall
T.$ (10)

where $\mathbb{E}$ denotes the expectation.

Varaiya [27] has proposed the _MaxPressure_ TSC policy can guarantee the
network stability.

######  Definition 3.

MaxPressure [27]. Given the network state $Q(t)$ at current period $t$, each
agent/intersection selects the action with the maximum pressure:
$\vec{x}^{*}(t)=\arg\max_{\vec{x}(t)}\sum_{(l,h):x(l,h)=1}f(l,h)[q(l,h)-\sum_{p\in
Do_{h}}r(h,p)q(h,p)]$, where $q(l,h)$ is the upstream queue length $\sum_{p\in
Do_{h}}r(h,p)q(h,p)$ is the (average) downstream queue length, the pressure
$q(l,h)-\sum_{p\in Do_{h}}r(h,p)q(h,p)$ of a movement phase is simply the
difference between upstream and downstream queue lengths.

$0$$1$$2$$3$$4$$5$$\cdot 10^{4}$$0$$1{,}000$$2{,}000$$3{,}000$$4{,}000$Time
$t$The Balance index $B(t)$NL-Coor (ours)MaxPressure Figure 4: The balance
index between our NL-Coor and MaxPressure approaches.

(a) A road network with two intersections.

(b) Network-Level Coordinated Policy

(c) Greedy Individual Policy

Figure 5: The drawback of NL-Coor and the advantage of individual action on
reducing travel time of vehicles.

The main idea of MaxPressure policy [27] of stability proof is to guarantee
the sufficient condition

$\displaystyle\mathbb{E}[B(t+1)]-\mathbb{E}[B(t)]\leq
K-\epsilon\mathbb{E}|Q(t)|.$ (11)

where $|Q(t)|=\sum_{(l,h)}q(l.h)$ denote the sum queue length of road network
at the period $t$, $\epsilon>0$ and $K<\infty$.

In the following theorem, we prove that our NL-Coor can stabilize the road
network by satisfying such as sufficient condition Ineq.(11).

######  Theorem 1.

The policy $\vec{x}^{NL-Coor}$ selected by our network-level coordination
algorithm (i.e., Algorithm 2) can stabilize the network queues.

###### Proof.

Given the network state $Q(t)$ at the period $t$, let $\vec{x}^{MP}$ denote
the signal control policy selected by MaxPressure and $\vec{x}^{Opt}$ denote
the optimal policy that minimizes the sum of squares of all the queue lengths
at the next period $t+1$, i.e.,
$\vec{x}^{Opt}=\arg\min_{\vec{x}}\mathbb{E}B(t+1)$. Let
$\mathbb{E}[B^{Opt}(t)]$, $\mathbb{E}[B^{NL-Coor}(t+1)]$ and
$\mathbb{E}[B^{MP}(t+1)]$ denote the sum of squares of all the queue lengths
returned by the optimum, our NL-Coor and the MaxPressure algorithms. On the
one hand, we have that $\mathbb{E}[B^{Opt}(t+1)]\leq\mathbb{E}[B^{MP}(t+1)]$.
On the other hand, in acyclic graphs, NL-Coor algorithm can achieve the
optimum, and in generalized cyclic graphs, NL-Coor algorithm is an adequately
approximation of the optimum [55, 57], i.e., $\mathbb{E}[B^{NL-
Coor}(t+1)]\approx\mathbb{E}[B^{Opt}(t+1)]\leq\mathbb{E}[B^{MP}(t+1)]$. In
Figure 4, by empirical evaluation on real datasets, we further validate that
$\mathbb{E}[B^{NL-Coor}(t+1)]\leq\mathbb{E}[B^{MP}(t+1)]$. Finally, we can
derive that

$\displaystyle\mathbb{E}[B^{NL-Coor}(t+1)]-\mathbb{E}[B(t)]$
$\displaystyle\leq\mathbb{E}[B^{MP}(t+1)]-\mathbb{E}[B(t)]\leq
K-\epsilon\mathbb{E}|Q(t)|$ (12)

which can guarantee our NL-Coor algorithm stabilizes the network queues. ∎

Input : The coordination graph $G$, the network-level coordination policy
$\vec{x}^{NL-Coor}$.

Output : The individual action $\vec{x}=\\{x_{1},x_{2},\cdots,x_{n}\\}$.

1 Initialize the individual action as $\vec{x}(0)=\vec{x}^{NL-Coor}$;

2 while  _time budget is remained_ do

3 for  _each message passing iteration $\tau$_ do

4 for  _$a_{i}\in\mathcal{A}$_ do

5 send current action message $x_{i}(\tau)$ to neighbors $Neg(i)$;

6 $\vec{x}_{Neg(i)}(\tau)$ $\leftarrow$ action messages collected from
$Neg(i)$;

7 Select the optimal action $x_{i}(\tau+1)=\arg\min_{x_{i}\in
D_{i},\vec{x}_{Neg(i)}(\tau)}B_{i}$.

8

9

Algorithm 3 Local Individual Action Improvement(Loc-IAI($\vec{x}^{NL-Coor}$))

###  5.2 Local Greedy Action of Improving $B_{i}$

As shown in Section 5.1, the main object of NL-Coor is to minimize the network
balance $B$. From the network-level perspective, these vehicles traveling
between internal links do not reduce network balance, the proposed NL-Coor
might struggle to drive vehicles to the exit links for network balance
minimization. However, such ”clean” policy might increase the travel time of
other vehicles queuing at the internal links. We take an example to illustrate
this scenario.

Example 1. _Fig. 5(a) shows a simple road network including two intersections
$i$ and $j$, an entry link $l_{1}$, an internal link $l_{2}$ and an exit link
$l_{3}$. Assume that there are four vehicles queuing at the movement phase
$(l_{1},l_{2})$ and two vehicles queuing at the movement phase
$(l_{1},l_{3})$. From the network-level perspective of minimizing the network
balance, NL-Coor will activate the WE-Left movement phase of the intersection
$i$ such that these vehicles on $(l_{1},l_{3})$ can exit the network, and the
vehicles on $(l_{1},l_{2})$ are still waiting for next periods, where the
network queue balance is $4^{2}=16$ (i.e., Fig.5(b)). Otherwise, if the WE-
Straight movement phase is activated, these vehicles queuing at the movement
phase $(l_{1},l_{2})$ will move to internal link $l_{2}$ and the vehicles on
$(l_{1},l_{3})$ are stilling waiting at the the entry link $l_{1}$ (i.e.,
Fig.5(c)), where the network queue balance is $4^{2}+2^{2}=20$. However, we
can find that activate the WE-Straight movement phase will reduce the average
travel time of vehicles since more vehicles (i.e., these vehicles queuing at
the movement phase $(l_{1},l_{2})$) will get closer to their destinations._

To avoid this ”clean” policy caused by NL-Coor mechanism, we propose a local
action improvement procedure from the perspective of each individual agent.
This local action improvement mechanism is also based on message passing, but
is associated only with the action information. After collecting the
neighbors’ actions, each agent $a_{i}$ greedily selects the individual action
with the aim of minimizing its own balance $B_{i}=\sum_{(l,h):l\in I(i),h\in
O(i)}[q(l,h)]^{2}$.

Algorithm 3 formally describes the local individual action improvement (Loc-
IAI) procedure. In steps 5-6, each agents $a_{i}$ sends the action information
to and collect the action information from neighbors $Neg(i)$ (The neighbor
action information can be achieved either in a synchronization or asynchronous
manner [58]). Given the current action vector of neighbors
$\vec{x}_{Neg(i)}(\tau)$ of the current message passing iteration $\tau$, each
agent $a_{i}$ selects the action $x_{i}(\tau+1)$ that can minimize its balance
$B_{i}$ in a best-response manner (step 7). The message passing-based local
individual agent improvement procedure can stop at any time if the time limit
is reached.

Input : The coordination graph $CG$,real-time budget $B^{T}$, the parameter
$\epsilon$.

Output : The action vector $\vec{x}=\\{x_{1},x_{2},\cdots,x_{n}\\}$.

1 $\vec{x}^{NL-Coor}\leftarrow$ NL-Coor($o$,$dia(o)$,$\epsilon B^{T}$);

$\vec{x}\leftarrow$ Loc-IA($\vec{x}^{NL-Coor}$,1-$\epsilon B^{T}$);

Algorithm 4 Explicitly Multiagent Coordination Algorithm (EMC)

###  5.3 Explicitly Multiagent Coordination Algorithm

So far, we have discussed the two phases of network-level coordination
procedure (i.e, NL-Coor) and local action improvement procedure (i.e., Loc-
IAI). In this section we integrate these two phases to propose the explicitly
multiagent coordination algorithm (EMC) with time budget limits. Given the
real-time budget $B^{T}$ (e.g., 3s), in the first coordination phase, NL-Coor
executes with respect to the time budget $\epsilon B^{T}$, where
$\epsilon\in[0,1]$ is the budget allocation parameter, and the remained
$1-\epsilon B^{T}$ time budget is allocated for the second individual action
improvement procedure Loc-IAI. The EMC is formally described in Algorithm 4.

##  6 Experimental Evaluation

###  6.1 Experiment Setup

We evaluate the proposed TSC methods on the Cityflow simulation platform [59]
within real-world and synthetic traffic networks. We estimate queue update of
next period by simulating the real Cityflow and use it as the model input of
our EMC method. The vehicle’s traveling speed is set as a usual of 10m/s. In
each traffic network, each vehicle is described as $(o,t,d)$, where $o$ is the
origin location (i.e., link), $t$ is time, and $d$ is destination location.
Locations $o$ and $d$ are both links of the road network. Unless otherwise
specified, each intersection is set to be a bi-direction four-way
intersection.

Synthetic Road Network. We generate three synthetic datasets, and their detail
statistics are shown in Table III. These large datasets $15\times 15$ (i.e.,
225 intersections) and $20\times 20$ (i.e., 400 intersections) are used to
validate the effectiveness (i.e., real-time) and efficiency (i.e., average
travel time of vehicles) of our EMC method. The vehicles enter the road
network through the boundary intersections and follow a uniform arrival rate.
The traffic flow is simulated for 1 hour (i.e., the duration is 3600s). The
length of the link H-$k$-V-$l$ indicates that the length of the link in the
horizon (H) direction is $k$ meters and the length of link in the vertical (V)
direction is $l$ meters.

Real-World Road Network. Four representative real-world traffic datasets
collected from four cities [15] are used to evaluate the performance of
methods. Detailed descriptions on these datasets are as follows, with data
statistics listed in Table IV.

Dataset | Number of | Arrival Rate | Duration | Length
---|---|---|---|---
Intersections | (vehicles/s) | (s) | of the Lane (m)
syn_4 $\times$ 4 | 16 | 1.76 | 3600 | H-300-V-300
syn_15$\times$ 15 | 225 | 0.80 | 3600 | H-300-V-300
syn_20$\times$ 20 | 400 | 0.77 | 3600 | H-300-V-300
TABLE III: Data statistics of synthetic traffic dataset. Dataset | Number of | Arrival Rate | Duration | Length
---|---|---|---|---
Intersections | (vehicles/s) | (s) | of the Lane (m)
NewYork | 1$\times$16 | 0.80 | 3600 | H-350-V-100
Manhattan | 3$\times$16 | 0.77 | 3600 | H-350-V-100
Jinan | 4$\times$3 | 0.84 | 3600 | H-800-V-400
Hangzhou | 4$\times$4 | 1.76 | 3600 | H-800-V-600
TABLE IV: Data statistics of real-world traffic dataset. Method Dataset | ny_$1\times 16$ | manhattan_$3\times 16$ | jinan_$3\times 4$ | hangzhou_$4\times 4$ | syn_$4\times 4$ | syn_$15\times 15$ | syn_$20\times 20$
---|---|---|---|---|---|---|---
Heuristics | FixedTime | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1
MaxPressure | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1
RL Methods | LIT | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1
PressLight | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1
MA2C | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1
FMA2C | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1 | $<$0.1
EMC (ours) | 0.174 | 0.268 | 0.155 | 0.165 | 0.169 | 1.2765 | 2.013
TABLE V: Performance comparison between methods on computation time (seconds). Each cell is statistically significant at 95% confidence level. Method Dataset | Short Link | Long Link | Medium Link
---|---|---|---
ny_$1\times 16$ | manhattan_$3\times 16$ | jinan_$3\times 4$ | hangzhou_$4\times 4$ | syn_$4\times 4$ | syn_$15\times 15$ | syn_$20\times 20$
Heuristics | FixedTime | 199.5($\pm$0.1) | 292.3($\pm$0.7) | 331.2($\pm$1.1) | 377.5($\pm$1.4) | 232.2($\pm$1.2) | 207.1($\pm$1.0) | 331.9($\pm$1.5)
MaxPressure | 102.8($\pm$0.5) | 180.4($\pm$0.9) | 342.4($\pm$1.3) | 416.7($\pm$1.5) | 196.6($\pm$0.7) | 184.5($\pm$0.6) | 269.2($\pm$1.0)
RL Methods | LIT | 103.1($\pm$0.1) | 295.8($\pm$0.1) | 316.4($\pm$0.1) | 362.2($\pm$0.2) | 184.6($\pm$0.1) | 203.59($\pm$0.2) | 302.0($\pm$0.2)
PressLight | 106.2($\pm$0.1) | 182.4($\pm$0.8) | 301.3($\pm$8.9) | 365.0($\pm$11.4) | 184.8($\pm$3.5) | 206.6($\pm$3.98) | 345.5($\pm$0.8)
MA2C | 115.4($\pm$1.3) | 244.1($\pm$0.5) | 306.4($\pm$0.3) | 364.1($\pm$1.8) | 205.02($\pm$0.5) | 244.8($\pm$0.7) | 330.8($\pm$2.7)
FMA2C | 120.5($\pm$2.5) | 241.2($\pm$1.0) | 304.6($\pm$0.9) | 361.1($\pm$1.3) | 199.6($\pm$0.8) | 241.2($\pm$0.5) | 315.6($\pm$3.0)
EMC (ours) | 104.3($\pm$0.1) | 182.5($\pm$1.4) | 290.9($\pm$0.1) | 355.1($\pm$0.8) | 180.3($\pm$0.2) | 178.6($\pm$0.1) | 251.6($\pm$0.1)
TABLE VI: Performance comparison between methods on average travel time (the
lower the better). The short, medium, and long link indicates the length of
the link is short, medium and long.

  * •

ny_$1\times 16$: Flow data of 16 intersections from 8-th Avenue in New york
City with uni-directional traffic on both the arterial and the side streets.

  * •

manhattan_$3\times 16$: Flow data generated from open-source taxi trip data of
48 intersections in the road network of Manhattan, New York City.

  * •

jinan_$3\times 4$: Flow data collected by roadside cameras from 12
intersections in Dongfeng Sub-district, Jinan, China.

  * •

hangzhou_$4\times 4$: Flow data of 16 intersections in Gudang Sub-district
generated from roadside surveillance cameras.

Comparison Methods. We compare our EMC method with the following two
categories of methods: heuristic methods and RL methods. Heuristic methods
mainly design TSC by expert domain knowledge, while RL methods mainly learn
TSC by interacting with traffic environment.

_Heuristic Methods:_

  * •

FixedTime [1, 2]: The traffic light cycles through a fixed sequence of phases.
The signal sequence is pre-determined by expert rule. Each phase has a fixed
duration of 10 seconds. In this paper, there are four phases, i.e., WE-
Straight, WE-Left, SN-Straight, SN-Left. Due to its simpleness, FixedTime
method has been widely used in practice.

  * •

Maxpressure [27]: Similar to our EMC method, the Maxpressure method is also an
online planning method, which observes real traffic and greedily active the
phase with the maximum pressure. A brief introduction of Maxpressure in shown
in Section 5.1.3.

_RL Methods:_

  * •

PressLight [24]: PressLight method models each intersection as an independent
agent and learns the policy of choosing next phase by vanilla DQN. The state
is set as the queue length on links and reward is set as the negative of the
pressure.

  * •

LIT [60]: LIT method is also an individual deep RL method which uses phase and
vehicles numbers as the state, and the sum of queue length as the reward.
Compared with PressLight, it does not consider the traffic condition from
downstream.

  * •

MA2C [13]: Multi-agent A2C is a mutil-agent RL method, which uses information
of neighborhood policies to enhance the observation of each local agent.

  * •

FMA2C [14]: FMA2C extends MA2C with the feudal hierarchy, where each
intersection is controlled by a worker agent and a each region is controlled
by a manager agent. In the two-level manager-worker framework, managers
coordinate their high-level behaviors and set goals for their workers in the
region, while each lower-level worker controls traffic signals to fulfill the
managerial goals.

Note that all methods are carefully tuned and their best results are reported.
For a fair comparison, all the RL methods are learned without pre-trained
process and the action interval is set as 10 seconds. All RL methods are
trained using 500 episodes.

Performance Metric. We use the computation time (in seconds) of making signal
decisions 444The proposed EMC method is parallelizable and hence the running
time could be reduced substantially using multiple cores. and the average
travel time of vehicles to evaluate the performance of methods. The average
travel time is the widely used measure in TSC literature, which is calculated
as the average travel time of all vehicles spent in the road network.

All computations are performed on a 64-bit workstation with 64 GB RAM and a
16-core 3.5 GHz processor. All records are averaged over 40 instances, and
each record is statistically significant at 95% confidence level unless
otherwise specified.

(a) EMC (ours)

(b) MaxPressure

(c) PressLight

Figure 6: Time-Space Diagram with signal timing plan of our EMC, MaxPressure
and Presslight methods.

###  6.2 Experiment Results

Results on Computation Time. Table V shows the computation time for each TSC
decision phase. From Table V, we can observe traditional methods (i.e., all
methods except our EMC) can select to active a movement phase within 0.1
seconds. This can be explained by the fact that 1) for MaxPressure, each
intersection only need to select one of the four phases with the maximum
pressure, in which the computation time is limited, and 2) for the pre-
determined heuristic FixedTime and learned RL methods, each interaction only
need to query the corresponding policy by using the real traffic as an input,
which is also time-free. The computation time of our EMC method increases with
the size of the road network. Fortunately, even in the large-scale with
$20\times 20$ intersections, each intersection in EMC can decide to activate a
movement phase within 3 seconds. 3 seconds is a reasonable maximum time limit
for traffic signal control since there is always a yellow light (e.g., a fixed
duration of 3 seconds) after each phase for traffic clean. Therefore, during
the yellow light, our EMC can determine next phase in a real-time manner.
Moreover, considering our EMC is an anytime algorithm that can search more
action space given more time budget and can return a best solution under the
existing time, it enables scaling to large-scale TSC problems with hundreds of
intersections.

Results on Travel Time. Table VI shows the average travel time in both real
datasets and synthetic datasets, From which we have the following
observations:

  * •

In synthetic dataset (i.e.,syn_$4\times 4$, syn_$15\times 15$ and
syn_$20\times 20$) with medium link and real dataset with long link (i.e.,
jinan_$3\times 4$ and hangzhou_$4\times 4$), compared with heuristic and RL
baselines, our EMC method generates the least travel time. Especially in the
large-scale synthetic network syn_$20$, our EMC reduce 20% travel time
compared to the best RL method LIT. The potential reason is that for complex
large-scale road networks with hundreds of intersections, it is hard for RL
methods to train desirable coordination solutions. This result is in consist
with the scalability limitations of current multiagent RL methods. In
contrast, our EMC method enables direct modeling of the flow influences
between neighboring intersections and aims to optimize global traffic
pressure. However, MaxPressure only optimizes local pressure of individual
intersection, thus the performance decreases in complex large-scale traffic
situation.

  * •

In the real datasets ny_$1\times 16$ and manhattan_$3\times 16$ with short
link, i.e., the length of the link in the vertical direction is only 100m, the
MaxPressure method produces the least travel time. This is can be explained by
the fact that a vehicle with the speed of 10m/s can pass through the short
link within a decision period (i.e., 10s). Such ”pass through” phenomenon will
make the prediction-based methods (i.e., RL methods) and online lookahead
planning method (i.e., our EMC method) inaccurate in modeling queue state at
the next period state. Maxpressure only considers the current period state,
which will avoid this ”pass through” issue.

  * •

LIT method behaves fairly well in synthetic datasets but does not fit real
data with irregular flow data like manhanttan_$3\times 16$. Presslight shows
good result in these datasets except the large-size synthetic datasets. Such
divergence conforms to the deficiency in RL methods, that it is incapable of
capturing communication between neighboring intersections in large-scale or
complex scenarios. The performance advantage of FMA2C over MA2C corresponds to
the FMA2C method’s optimization effect in serving global coordination.

In summary, for real-world road networks such that no vehicle can pass through
an entire road within each period $t$ (i.e., with medium and long links), our
EMC is a good option for TSC with respect to real-time responsive and average
travel time minimization.

Delay (s) Dataset | 3$\times$3 | 4$\times$ 4 | 15$\times$15 | 20$\times$20
---|---|---|---|---
$\mu$=0 | 0.022 | 0.026 | 0.100 | 0.180
$\mu$=0.01 | 0.616 | 0.629 | 0.719 | 0.792
$\mu$=0.02 | 1.097 | 1.109 | 1.187 | 1.230
TABLE VII: Communication delay (second) of our EMC method.

Results on Communication Delay of our EMC Method. Since our EMC is message
passing-based decentralized method, we also test its communication delay by
Pumba 555https://github.com/alexei-led/pumba, a chaos testing command line
tool for Docker containers. In the simulation, we generate 10 Docker nodes,
each is allocated with a number of agents/intersections. For example, in a
20$\times$20 road network, 40 agents are randomly selected and allocated to
one of the non-configured nodes. Node communicate by the TCP protocol. The
communication delay $X$ (ms) follows the Normal distribution $N(\mu,3^{2})$
where $\mu$ is the expected delay, and 3 (ms) is the standard deviation. The
node ends asynchronously, and the end time of the last node is recorded. Table
VII shows the delay of our EMC method at different road networks. From Table
VII, we can find that in the large-scale dataset $20\times$20, even with the
higher node-to-node communication delay (i.e., 20ms), our EMC takes only 1.2s
to communicate messages. This includes that in real-world large-scale
20$\times$20 scenarios, our EMC takes about 3.2s to return the signal
decision, in which the 2.0s is used for computing the message (which is shown
in Table V) and the remained 1.2s is used for communicating the message.

###  6.3 Case Study in Real-World Jinan Road Network

In this case, we use the time-space diagram to show the trajectory of each
vehicle in the real-world road network Jinan_4$\times$3 in the time range from
1500s to 1800s, and visualize the performance of different methods. In the
time-space diagram of Figure 6, the x-axis is the time and the y-axis is the
distance of the westernmost arterial road from south to north. We mainly show
traffic flows of north (i.e., blue lines) and south (i.e., orange lines)
directions. The flow arrival rate is set as 1.68/s to simulate the peak
scenarios. As it is shown in Fig.6, there are 4 bands with green-yellow-red
colors indicating the signal lights of 4 intersections. We can find that under
MaxPressure (i.e.,Fig.6(b)) and PressLight (i.e., Fig.6(c)), a number of
vehicles might accumulate and wait before the red light. As the traffic
becomes heavier, MaxPressure and PressLight have to keep the red signals for
long periods to make a concession for other directions with high-demand
traffic flows. In comparison, most orange and blue lines are straight under
our EMC (i.e., Fig.6(a)), which indicates few vehicles are waiting before the
red light for long periods. This observation further validate our EMC method
can detect the actual traffic change on each links and optimize the global
pressure in the next period, thereby can feasibly plan short-time green light
phase for incoming vehicles from north and south directions to pass through.

##  7 Conclusion and Future Work

This paper studies the TSC problem of minimizing the average travel time of
vehicles. To achieve the real-time and network-level TSC, an explicit
multiagent coordination (EMC) framework is proposed, which is simple to
implement. In EMC, each intersection is modeled as an autonomous agent, and
the coordination efficiency is formulated as the balance index between
neighbor agents. The balance index is general that can be incorporated in a
number of other TSC methods. To achieve the real-time responsiveness, an
anytime Max-sum_ADVP-based message passing mechanism is proposed to select the
signal plan. The EMC algorithm mainly consists of network-level coordination
and local individual action improvement phases, with the aim of minimizing the
travel time of vehicles. The network-level coordination phase is proved to
guarantee network stability. Experimental results show that on both synthetic
and real datasets, the proposed EMC achieves lower travel time than other
benchmark heuristic and RL methods, and can scale to large-scale scenarios.

One interesting future direction is to extend the EMC from one-step lookahead
to multi-step lookaheads. This extension is non-trivial since the action space
increases exponentially with the number of steps. Decentralized multi-step
coordination requires intolerable communication cost (i.e., message size),
while centralized coordination requires intolerable computation time. We would
like to exploit the interaction structure of EMC (e.g., each agent only
interacts with adjacent neighbor agents), and explore the Monte-Carlo tree
search (MCTS)-based sampling algorithm [61] to search coordinated policy that
can coordinate within multi-steps.

## Acknowledgment

This research is supported by the National Natural Science Foundation of China
(61806053, 61932007 and 62076060), the Key Research and Development Program of
Jiangsu Province of China (BE2022157).

## References

  * [1] P. Lowrie, “Scats: Sydney co-ordinated adaptive traffic system: a traffic responsive method of controlling urban traffic,” 1990.
  * [2] D. Robertson and R. Bretherton, “Optimizing networks of traffic signals in real time-the scoot method,” _IEEE Transactions on Vehicular Technology_ , vol. 40, no. 1, pp. 11–15, 1991.
  * [3] “https://inrix.com/press-releases/2019-traffic-scorecard-us/.”
  * [4] M. Vallati, D. Magazzeni, B. D. Schutter, L. Chrpa, and T. L. McCluskey, “Efficient macroscopic urban traffic models for reducing congestion: A PDDL+ planning approach,” in _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA_ , D. Schuurmans and M. P. Wellman, Eds. AAAI Press, 2016, pp. 3188–3194.
  * [5] F. Zhu, Y. Lv, Y. Chen, X. Wang, G. Xiong, and F.-Y. Wang, “Parallel transportation systems: Toward iot-enabled smart urban traffic control and management,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 10, pp. 4063–4071, 2020.
  * [6] T. Iwase, S. Stein, E. H. Gerding, and A. Chapman, “A polynomial-time decentralised algorithm for coordinated management of multiple intersections,” in _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022_ , L. D. Raedt, Ed., 2022, pp. 3847–3853.
  * [7] S. F. Smith, G. J. Barlow, X. Xie, and Z. B. Rubinstein, “Smart urban signal networks: Initial application of the SURTRAC adaptive traffic signal control system,” in _Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling(ICAPS’13), Rome, Italy, June 10-14, 2013_ , 2013.
  * [8] 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.
  * [9] 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, KDD 2018, London, UK, August 19-23, 2018_, 2018, pp. 2496–2505.
  * [10] Z. Zhang, J. Yang, and H. Zha, “Integrating independent and centralized multi-agent reinforcement learning for traffic signal network optimization,” in _Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS’20, Auckland, New Zealand, May 9-13, 2020_ , 2020, pp. 2083–2085.
  * [11] 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 _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020_ , 2020, pp. 3414–3421.
  * [12] H. Wei, G. Zheng, V. V. Gayah, and Z. Li, “Recent advances in reinforcement learning for traffic signal control: A survey of models and evaluation,” _SIGKDD Explor._ , vol. 22, no. 2, pp. 12–18, 2020.
  * [13] T. Chu, J. Wang, L. Codeca, and Z. Li, “Multi-agent deep reinforcement learning for large-scale traffic signal control,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 3, pp. 1086–1095, 2020.
  * [14] J. Ma and F. Wu, “Feudal multi-agent deep reinforcement learning for traffic signal control,” in _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS ’20. International Foundation for Autonomous Agents and Multiagent Systems, 2020, pp. 816–824.
  * [15] H. Wei, N. Xu, H. Zhang, G. Zheng, X. Zang, C. Chen, W. Zhang, Y. Zhu, K. Xu, and Z. Li, “Colight: Learning network-level cooperation for traffic signal control,” in _Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019_ , 2019, pp. 1913–1922.
  * [16] Z. Yu, S. Liang, L. Wei, Z. Jin, J. Huang, D. Cai, X. He, and X. Hua, “Macar: Urban traffic light control via active multi-agent communication and action rectification,” in _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , 2020, pp. 2491–2497.
  * [17] Q. Jiang, M. Qin, S. Shi, W. Sun, and B. Zheng, “Multi-agent reinforcement learning for traffic signal control through universal communication method,” in _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI’22), Vienna, Austria, 23-29 July 2022_ , 2022, pp. 3854–3860.
  * [18] Y. Wang, T. Xu, X. Niu, C. Tan, E. Chen, and H. Xiong, “STMARL: A spatio-temporal multi-agent reinforcement learning approach for cooperative traffic light control,” _IEEE Trans. Mob. Comput._ , vol. 21, no. 6, pp. 2228–2242, 2022.
  * [19] E. van der Pol and F. Oliehoek, “Coordinated deep reinforcement learners for traffic light control,” in _NIPS-16_ , 2016.
  * [20] 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, 2020\.
  * [21] B. Xu, Y. Wang, Z. Wang, H. Jia, and Z. Lu, “Hierarchically and cooperatively learning traffic signal control,” in _Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9_ , 2021, pp. 669–677.
  * [22] Y. Wang, D. Wang, S. Jin, N. Xiao, Y. Li, and E. Frazzoli, “Iterative tuning with reactive compensation for urban traffic signal control,” _IEEE Transactions on Control Systems Technology_ , vol. 25, no. 6, pp. 2047–2059, 2017\.
  * [23] H. Hu and S. F. Smith, “Using bi-directional information exchange to improve decentralized schedule-driven traffic control,” in _Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS 2018, Berkeley, CA, USA, July 11-15, 2019_ , 2019, pp. 200–208.
  * [24] H. Wei, C. Chen, G. Zheng, K. Wu, V. Gayah, K. Xu, and Z. Li, “Presslight: Learning max pressure control to coordinate traffic signals in arterial network,” in _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , ser. KDD’19, 2019, pp. 1290–1298.
  * [25] L. Kuyer, S. Whiteson, B. Bakker, and N. A. Vlassis, “Multiagent reinforcement learning for urban traffic control using coordination graphs,” in _Machine Learning and Knowledge Discovery in Databases, European Conference, ECML/PKDD 2008, Antwerp, Belgium, September 15-19, 2008, Proceedings, Part I_ , 2008, pp. 656–671.
  * [26] S. El-Tantawy, B. Abdulhai, and H. Abdelgawad, “Multiagent reinforcement learning for integrated network of adaptive traffic signal controllers (MARLIN-ATSC): methodology and large-scale application on downtown toronto,” _IEEE Trans. Intell. Transp. Syst._ , vol. 14, no. 3, pp. 1140–1150, 2013.
  * [27] P. Varaiya, “Max pressure control of a network of signalized intersections,” _Transportation Research Part C: Emerging Technologies_ , vol. 36, pp. 177–195, 2013.
  * [28] X. Xie, S. F. Smith, and G. J. Barlow, “Schedule-driven coordination for real-time traffic network control,” in _Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, ICAPS 2012, Atibaia, São Paulo, Brazil, June 25-19, 2012_ , 2012.
  * [29] H. Hu and S. F. Smith, “Softpressure: A schedule-driven backpressure algorithm for coping with network congestion,” in _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017_ , 2017, pp. 4324–4330.
  * [30] R. Goldstein and S. F. Smith, “Expressive real-time intersection scheduling,” in _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , 2018, pp. 6177–6185.
  * [31] N. Wu, D. Li, and Y. Xi, “Distributed weighted balanced control of traffic signals for urban traffic congestion,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 10, pp. 3710–3720, 2021.
  * [32] C. Cai, C. K. Wong, and B. G. Heydecker, “Adaptive traffic signal control using approximate dynamic programming,” _Transportation Research Part C: Emerging Technologies_ , vol. 17, no. 5, pp. 456–474, 2009.
  * [33] S. Chen and D. J. Sun, “An improved adaptive signal control method for isolated signalized intersection based on dynamic programming,” _IEEE Intelligent Transportation Systems Magazine_ , vol. 8, no. 4, pp. 4–14, 2016.
  * [34] K. Aboudolas, M. Papageorgiou, A. Kouvelas, and E. Kosmatopoulos, “A rolling-horizon quadratic-programming approach to the signal control problem in large-scale congested urban road networks,” _Transportation Research Part C: Emerging Technologies_ , vol. 18, no. 5, pp. 680–694, 2010.
  * [35] S. Lin, B. D. Schutter, Y. Xi, and H. Hellendoorn, “Fast model predictive control for urban road networks via MILP,” _IEEE Trans. Intell. Transp. Syst._ , vol. 12, no. 3, pp. 846–856, 2011.
  * [36] L. B. de Oliveira and E. Camponogara, “Multi-agent model predictive control of signaling split in urban traffic networks,” _Transportation Research Part C: Emerging Technologies_ , vol. 18, no. 1, pp. 120–139, 2010.
  * [37] Z. Zhou, B. D. Schutter, S. Lin, and Y. Xi, “Two-level hierarchical model-based predictive control for large-scale urban traffic networks,” _IEEE Transactions on Control Systems Technology_ , vol. 25, no. 2, pp. 496–508, 2017.
  * [38] B.-L. Ye, W. Wu, K. Ruan, L. Li, T. Chen, H. Gao, and Y. Chen, “A survey of model predictive control methods for traffic signal control,” _IEEE/CAA Journal of Automatica Sinica_ , vol. 6, no. 3, pp. 623–640, 2019.
  * [39] B.-L. Ye, W. Wu, and W. Mao, “A two-way arterial signal coordination method with queueing process considered,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 16, no. 6, pp. 3440–3452, 2015.
  * [40] F. Ahmad, S. A. Mahmud, and F. Z. Yousaf, “Shortest processing time scheduling to reduce traffic congestion in dense urban areas,” _IEEE Trans. Syst. Man Cybern. Syst._ , vol. 47, no. 5, pp. 838–855, 2017.
  * [41] A. L. C. Bazzan, “Opportunities for multiagent systems and multiagent reinforcement learning in traffic control,” _Autonomous Agents and Multi-Agent Systems_ , vol. 18, pp. 342–375, 2009.
  * [42] R. Junges and A. L. C. Bazzan, “Evaluating the performance of DCOP algorithms in a real world, dynamic problem,” in _7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), Estoril, Portugal, May 12-16, 2008, Volume 2_ , 2008, pp. 599–606.
  * [43] B. Scholkopf, J. Platt, and T. Hofmann, _Natural Actor-Critic for Road Traffic Optimisation_ , 2007, pp. 1169–1176.
  * [44] J. Ault, J. P. Hanna, and G. Sharon, “Learning an interpretable traffic signal control policy,” in _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS’20, 2020, pp. 89–96.
  * [45] B. Bakker, S. Whiteson, L. Kester, and F. C. A. Groen, _Traffic Light Control by Multiagent Reinforcement Learning Systems_ , 2010, pp. 475–510.
  * [46] Y. Liu, L. Liu, and W. Chen, “Intelligent traffic light control using distributed multi-agent Q learning,” in _20th IEEE International Conference on Intelligent Transportation Systems, ITSC 2017, Yokohama, Japan, October 16-19, 2017_ , 2017, pp. 1–8.
  * [47] S. Dhamija, A. Gon, P. Varakantham, and W. Yeoh, “Online traffic signal control through sample-based constrained optimization,” in _Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling, Nancy, France, October 26-30, 2020_ , J. C. Beck, O. Buffet, J. Hoffmann, E. Karpas, and S. Sohrabi, Eds., 2020, pp. 366–374.
  * [48] H. Chen, X. Zhu, G. Liu, and W. Pedrycz, “Uncertainty-aware online scheduling for real-time workflows in cloud service environment,” _IEEE Transactions on Services Computing_ , vol. 14, no. 4, pp. 1167–1178, 2021.
  * [49] Y. Lv, Y. Duan, W. Kang, Z. Li, and F. Wang, “Traffic flow prediction with big data: A deep learning approach,” _IEEE Trans. Intell. Transp. Syst._ , vol. 16, no. 2, pp. 865–873, 2015.
  * [50] S. Hui, H. Wang, Z. Wang, X. Yang, Z. Liu, D. Jin, and Y. Li, “Knowledge enhanced gan for iot traffic generation,” in _Proceedings of the ACM Web Conference 2022_ , ser. WWW’22, 2022, pp. 3336–3346.
  * [51] F. Ashtiani, S. A. Fayazi, and A. Vahidi, “Multi-intersection traffic management for autonomous vehicles via distributed mixed integer linear programming,” in _2018 Annual American Control Conference (ACC)_ , 2018, pp. 6341–6346.
  * [52] T. H. Heung, T. Ho, and Y. Fung, “Coordinated road-junction traffic control by dynamic programming,” _IEEE Trans. Intell. Transp. Syst._ , vol. 6, no. 3, pp. 341–350, 2005.
  * [53] P. Mirchandani and L. Head, “A real-time traffic signal control system: architecture, algorithms, and analysis,” _Transportation Research Part C: Emerging Technologies_ , vol. 9, no. 6, pp. 415–432, 2001.
  * [54] B. Torabi, R. Zalila-Wenkstern, R. Saylor, and P. Ryan, “Deployment of a plug-in multi-agent system for traffic signal timing,” in _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS’20, 2020, pp. 1386–1394.
  * [55] R. Zivan and H. Peled, “Max/min-sum distributed constraint optimization through value propagation on an alternating DAG,” in _International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes)_ , 2012, pp. 265–272.
  * [56] N. Vlassis, R. Elhorst, and J. Kok, “Anytime algorithms for multiagent decision making using coordination graphs,” in _2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583)_ , 2004, pp. 953–957.
  * [57] Z. Chen, Y. Deng, and T. Wu, “An iterative refined max-sum_ad algorithm via single-side value propagation and local search,” in _Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017_ , K. Larson, M. Winikoff, S. Das, and E. H. Durfee, Eds., 2017, pp. 195–202.
  * [58] W. Zhang, G. Wang, Z. Xing, and L. Wittenburg, “Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks,” _Artif. Intell._ , vol. 161, no. 1-2, pp. 55–87, 2005.
  * [59] H. Zhang, S. Feng, C. Liu, Y. Ding, Y. Zhu, Z. Zhou, W. Zhang, Y. Yu, H. Jin, and Z. Li, “Cityflow: A multi-agent reinforcement learning environment for large scale city traffic scenario,” in _The World Wide Web Conference_ , ser. WWW ’19, 2019, pp. 3620–3624.
  * [60] G. Zheng, X. Zang, N. Xu, H. Wei, Z. Yu, V. V. Gayah, K. Xu, and Z. Li, “Diagnosing reinforcement learning for traffic signal control,” _CoRR_ , vol. abs/1905.04716, 2019. [Online]. Available: http://arxiv.org/abs/1905.04716
  * [61] S. Choudhury, J. K. Gupta, P. Morales, and M. J. Kochenderfer, “Scalable anytime planning for multi-agent mdps,” in _AAMAS’21_ , 2021, pp. 341–349.

Wanyuan Wang is an associate professor with the School of Computer Science and
Engineering, Southeast University, Nanjing, China. He received his PhD. degree
in computer science from Southeast University, China, 2016. He has published
over 30 articles in refereed journals and conference proceedings, such as the
IEEE Transactions, AAAI, and AAMAS. He won the best student paper award from
ICTAI14. His main research interests include artificial intelligence,
multiagent systems, and optimization.
---
Tianchi Qiao is currently pursuing the M.E. degree with the School of Computer
Science and Engineering, Southeast University. His main research interests
include multiagent systems and distributed constraint optimization.
---
Jinming Ma is currently pursuing the Ph.D. degree with the School of the
Computer Science and Technology, University of Science and Technology of
China. His research interests include reinforcement learning and multi-agent
systems.
---
Jiahui Jin is an associate professor in the School of Computer Science and
Engineering, Southeast University, Nanjing, China. He received his Ph.D.
degree in computer science from Southeast University in 2015. He had been a
visiting Ph.D. student at University of Massachusetts, Amherst, U.S., during
August 2012 to August 2014. His current research interests include large-scale
data processing and urban computing.
---
Zhibin Li received his Ph.D. degree from the School of Transportation at
Southeast University, China, in 2014. He is currently a professor at Southeast
University. From 2015 to 2017, he worked as a postdoctoral researcher at the
University of Washington and the Hong Kong Polytech University. From 2010 to
2012, he was a visiting student at the University of California, Berkeley. His
research interests include Intelligent Transportation, Traffic Control, etc.
He received China National Scholarship twice, and won the Best Doctoral
Dissertation Award by China Intelligent Transportation Systems Association in
2015. He has authored or co-authored over 80 articles in journals.
---
Weiwei Wu received the B.Sc. degree from the South China University of
Technology and the Ph.D. degree from the Department of Computer Science, City
University of Hong Kong (CityU), and University of Science and Technology of
China (USTC) in 2011. He is currently a Professor with the School of Computer
Science and Engineering, Southeast University, China. He went to Nanyang
Technological University (NTU, Mathematical Division, Singapore), for post-
doctoral research in 2012. He has published over 50 peer-reviewed papers in
international conferences/journals, and serves as TPCs and reviewers for
several top international journals and conferences. His research interests
include optimizations and algorithm analysis, reinforcement learning and game
theory.
---
Yichuan Jiang is a full professor with the School of Computer Science and
Engineering, Southeast University, Nanjing, China. He received his PhD degree
in computer science from Fudan University, Shanghai, China, in 2005. His main
research interests include multiagent systems, social computing, and social
networks. He has published more than 90 scientific articles in refereed
journals and conference proceedings, such as the IEEE Transactions on Parallel
and Distributed Systems, IEEE Journal on Selected Areas in Communications,
IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans,
IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and
Reviews, IEEE Transactions on Systems, Man, and Cybernetics: Systems, IEEE
Transactions on Cybernetics, the ACM Transactions on Autonomous and Adaptive
Systems, the Journal of Autonomous Agents and Multi-Agent Systems, the Journal
of Parallel and Distributed Computing, IJCAI, AAAI and AAMAS. He won the best
paper award from PRIMA06 and best student paper awards twice from ICTAI13 and
ICTAI14. He is a senior member of IEEE.
---