# Conflict-free Cooperation Method for Connected and Automated Vehicles
at Unsignalized Intersections: Graph-based Modeling and Optimality Analysis

Chaoyi Chen  Qing Xu<EMAIL_ADDRESS>Mengchi Cai  Jiawei Wang
Jianqiang Wang  Biao Xu  Keqiang Li  School of Vehicle and Mobility, Tsinghua
University, Beijing 100084, China  Tsinghua University-Didi Joint Research
Center for Future Mobility, Beijing 100084, China  College of Mechanical and
Vehicle Engineering, Hunan University, Changsha 410012, China.

###### Abstract

Connected and automated vehicles have shown great potential in improving
traffic mobility and reducing emissions, especially at unsignalized
intersections. Previous research has shown that vehicle passing order is the
key influencing factor in improving intersection traffic mobility. In this
paper, we propose a graph-based cooperation method to formalize the conflict-
free scheduling problem at an unsignalized intersection. Based on graphical
analysis, a vehicle’s trajectory conflict relationship is modeled as a
conflict directed graph and a coexisting undirected graph. Then, two graph-
based methods are proposed to find the vehicle passing order. The first is an
improved depth-first spanning tree algorithm, which aims to find the local
optimal passing order vehicle by vehicle. The other novel method is a minimum
clique cover algorithm, which identifies the global optimal solution. Finally,
a distributed control framework and communication topology are presented to
realize the conflict-free cooperation of vehicles. Extensive numerical
simulations are conducted for various numbers of vehicles and traffic volumes,
and the simulation results prove the effectiveness of the proposed algorithms.

###### keywords:

Connected and Automated Vehicle , Unsignalized intersection , Conflict-free
cooperation , Distributed control

††journal: Transportation Research Part C: Emerging Technologies

##  1 Introduction

Intersections are the most common merging points in urban traffic scenarios
[1]. According to the Federal Highway Administration, more than 2.8 million
intersection-related crashes occur in the US each year, accounting for 44% of
all crashes [2]. The rapid development of the V2X technology provides an
opportunity to improve traffic mobility and safety in intersection management
[3]. Through vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I)
communication, a centralized controller is deployed at the intersection to
coordinate the connected and automated vehicles (CAVs) to pass through the
intersection; this guarantees conflict-free vehicle cooperation. Hence, CAVs
have immense potential in improving traffic safety and mobility at
intersections [4, 5].

In a fully autonomous intersection scenario, a hierarchical framework is
frequently used to realize the CAV coordination [6]. First, after collecting
the information of the CAVs in real-time, the centralized controller schedules
the arrival time of the CAVs to improve the traffic efficiency. Then, a
distributed controller is applied to the CAV to implement the determined
arrival plan. Multiple methods have been proposed to address the vehicle
control problem, e.g., fuzzy logic [7, 8], model predictive control [9, 10],
and optimal control [11, 12]. Moreover, the virtual platoon method was
proposed in [13], which projects the CAVs from different lanes into a virtual
lane. Thus, the typical vehicle platoon analysis methods [14] can be used in
the control problem of the CAVs on different lanes as if they are traveling in
the same lane.

The routes of incoming CAVs have complicated conflict relationships at
intersections. Therefore, obtaining a high-efficiency conflict-free arrival
plan is a priority in CAV scheduling. Researchers have also pointed out that
the passing order of the vehicles is the key factor influencing traffic
mobility at intersections [15, 16]. As incoming CAVs approach the intersection
from different directions, the optimal passing order changes constantly and
the solution space increases exponentially, preventing the determination of
the optimal passing order using the brute-force method. This problem is
typically solved using a reservation-based method [17]. The most
straightforward reservation-based solution is the first-in-first-out (FIFO)
strategy, in which vehicles that enter the intersection first are scheduled to
leave it first [6, 11, 18]. However, the FIFO passing order is not likely to
be the optimal solution in most cases. Batch-based strategy is an improved
version of the FIFO strategy, and it processes the vehicles in batches
according to their direction to reduce the traffic delay [19]; however, its
performance has not been fully optimized. Another widely used strategy is the
optimization-based method. After formulating the scheduling problem as an
optimization problem, various methods have been proposed to find the optimal
passing order, e.g., spanning tree [15], Monte Carlo tree search [20], and
dynamic programming [21]. However, the solution space exponentially increases
with the number of the vehicles, making the use of optimization-based methods
unfeasible.

Apart from these specific methods, some researchers have also noticed that
finding the optimal passing order of multiple CAVs is a discrete problem
rather than a continuous problem, and thus graph theory is considered a
promising methodology to describe and solve this problem. Studies have modeled
the problem using graph theory by employing the conflict graph analysis to
optimize the traffic-signal phase plan [22, 23]. However, the scheduling of
multiple CAVs is more difficult than scheduling a limited number of traffic
signal phases because the number of incoming CAVs is much larger than the
number of traffic signal phases. Some methods have been proposed to address
this difficulty. Apart from the depth-first spanning tree (DFST) algorithm
proposed in [13], Petri net [24] and conflict duration graph [25] are also
used in modeling the scheduling problem. However, the discussion on the
optimality of the scheduling problem of multiple CAVs is inadequate.

To tackle the problem of optimality, mathematical modeling, i.e., the
computational reduction of the intersection scheduling problem, is an
essential research aspect. Some researchers have focused on reducing this
problem into typical algorithmic problems, including the job-shop scheduling
problem [26], abstraction-based verification problem [27], and polling system
problem [28]. However, most of these methods mainly focus on the feasibility
of a conflict-free passing order solution. In practice, traffic efficiency is
another critical topic that has not been fully considered in the computational
reduction of this problem.

In this study, we mainly focused on finding the optimal CAV passing order at
unsignalized intersections, i.e., the CAV scheduling problem. Most of the
existing studies have focused on obtaining the passing order through specific
methods without considering the optimality and computational complexity [13,
15, 16, 18, 20]. Some have focused on the feasibility of a conflict-free
solution but neglected traffic efficiency optimization [19, 26, 27, 28, 24,
25]. To address this problem, we introduce a graph-based conflict-free
cooperation method to model the conflict relationship of the vehicles. Based
on this method, we propose two novel methods to obtain the local or global
optimal vehicle passing order. The contributions of our study are as follows:

  1. 1.

An improved DFST method is proposed based on [13] to improve traffic
efficiency. Instead of considering all conflict types as one united conflict
set, we categorized different conflict types to further reduce the overall
depth of the spanning tree, i.e., the evacuation time of vehicles. The
computational complexity of the improved algorithm remains low, and the
passing order solution generated by it is proved to be the local optimum.

  2. 2.

Based on the concise and rigid graphical analysis, we first reduce the CAV
scheduling problem to the minimum clique cover (MCC) problem. Unlike most of
the existing research [11, 13, 18], our reduction of the problem is proposed
without the assumption of the FIFO principle. Hence, the global optimal
passing order solution is obtained by solving the MCC problem. Moreover, we
propose a heuristic method to solve the problem of numerous vehicles with low
computation burden.

  3. 3.

A distributed feedback control method is designed to apply the scheduling
results of the proposed algorithms. In particular, the predecessor–leader
following topology is used as the communication topology to lower the
communication bandwidth requirement. Traffic simulations are conducted for
various numbers of vehicle inputs and traffic volumes. The simulation results
reveal that the proposed algorithms significantly improve both traffic
efficiency and fuel economy.

The remainder of this paper is organized as follows. Section 2 introduces the
scenario addressed in this study. Section 3 presents the conflict analysis,
improved DFST (iDFST) method, MCC method, and distributed control. The
simulation results are presented in Section 4, and Section 5 concludes the
paper.

##  2 Problem Statement

Fig. 1(a) depicts one of the most congested intersections near the Tsinghua
campus. In this scenario, because the number of approaching lanes is higher
than the number of departure lanes, traffic congestion frequently occurs
during rush hour. In this study, we simplified the traffic scenario by
separating the vehicles into different lanes based on their destination. A
hierarchical framework was established to realize the cooperation of the CAVs
[6]. A _central cloud coordinator_ was deployed at the intersection to guide
the CAVs in driving through the intersection. After collecting the positions
and velocities of all the CAVs, the upper coordinator schedules the passing
order of the approaching CAVs, while the lower distributed vehicle controller
controls the vehicle according to the determined passing order. The scheduling
method is presented in Sections 3.1, 3.2, 3.3, and the distributed control is
presented in Section 3.4. First, the following assumptions were devised to
facilitate the design of the strategy.

###### Assumption 1

Similar to most of the existing studies on intersection traffic [11, 13, 20],
lane change behavior was prohibited to guarantee vehicle safety and improve
traffic efficiency.

###### Assumption 2

An ideal communication condition without communication delay or packet loss is
under consideration. CAVs transmit their velocity and position to the central
cloud coordinator through wireless communication, e.g., V2I communication
[29].

###### Assumption 3

The CAVs are capable of fully autonomous driving and are assumed to have
perfect steering performance. Therefore, we only focused on the longitudinal
control of the vehicle.

(a) Intersection Scenario (b) Incoming Vehicles and Conflict Points

Figure 1: One of the most congested intersections near the Tsinghua campus in
Beijing is depicted in 1(a) and the conflict relationship of the traffic
scenario is illustrated in 1(b). Vehicles coming from different lanes are
distinguished by different colors. The red circles, orange squares, and green
arrows represent different potential collision points, which are interpreted
in Section 3.1.

The incoming CAVs are indexed from $1$ to $N$ according to their arrival
sequence at the control zone of length $L_{\mathrm{ctrl}}$ in Fig. 2, i.e.,
only the CAVs in the control zone are under coordination. For each CAV
$i\left(i\leq N,i\in\mathbb{N}^{+}\right)$, the CAV dynamic model is described
in the second-order form as follows:

$\begin{array}[]{l}\dot{\bm{x}}_{i}(t)=\bm{A}\bm{x}_{i}(t)+\bm{B}u_{i}(t),\\\
\bm{x}_{i}(t)=\left[\begin{array}[]{c}-p_{i}\\\ v_{i}\\\
\end{array}\right],\quad\bm{A}=\left[\begin{array}[]{cc}0&1\\\ 0&0\\\
\end{array}\right],\quad\bm{B}=\left[\begin{array}[]{c}0\\\ 1\\\
\end{array}\right],\end{array}$ (1)

where $\bm{x}_{i}$ is the state space of CAV $i$, and ${p}_{i}$, ${v}_{i}$,
and $u_{i}(t)$ denote the remaining distance to the stopping line, velocity,
and control input of CAV $i$ at time $t$. We consider homogeneous vehicle
platoons, and thus a continuous-time linear time-invariant system,
$(\bm{A},\bm{B})$, is used.

There also exist velocity and acceleration constraints of the vehicle.

$\displaystyle 0$ $\displaystyle\leq v_{i}\leq v_{\max},$ (2) $\displaystyle
a_{\min}$ $\displaystyle\leq u_{i}\leq a_{\max},$

where $v_{\max}$ is the maximum velocity limit; $u_{\min}$ and $u_{\max}$ are
the deceleration and acceleration limits, respectively.

As mentioned earlier, we aim to propose a cooperation method to improve both
traffic safety and efficiency, i.e., obtain the collision-free optimal CAV
passing order. Assign $t_{i}^{\mathrm{in}}$ as the time step when vehicle $i$
enters the control zone, and $t_{i}^{\mathrm{out}}$ as the time step when it
arrives at the intersection. Several evaluation indexes have been proposed to
measure the scheduling performance. In this study, we chose the evacuation
time as the priority optimization target, as shown in Definition 1.

######  Definition 1 (Evacuation Time)

The evacuation time of $N$ CAVs is defined as the time when the last CAV
reaches the stopping line; it is expressed as

$t_{\mathrm{evc}}=\max t_{i}^{\mathrm{out}},i\leq N,i\in\mathbb{N}^{+}.$ (3)

Considering $N$ incoming CAVs, $t_{\mathrm{evc}}$ represents the arrival time
of the last CAV at the stopping line. For $N$ CAVs, smaller evacuation time
means these CAVs pass through the intersection in shorter time. Thus, it shows
the overall traffic efficiency performance, i.e.,the overall benefits of the
CAVs.

In addition, the vehicle travels through the control zone in
$t_{i}^{\mathrm{out}}-t_{i}^{\mathrm{in}}$ time, whereas it travels through it
under the free driving condition in ${L_{\mathrm{ctrl}}}/{v_{\max}}$ time.
Accordingly, the average travel time delay (ATTD) is chosen to measure the
average traffic efficiency of the vehicles, as described in Definition 2.

######  Definition 2 (Average Travel Time Delay)

The ATTD is designed to evaluate the average traffic efficiency of $N$ CAVs.
It is expressed as

$t_{\mathrm{ATTD}}=\frac{1}{N}\sum_{i=1}^{N}\left(t_{i}^{\mathrm{out}}-t_{i}^{\mathrm{in}}-\frac{L_{\mathrm{ctrl}}}{v_{\max}}\right),$
(4)

where $L_{\mathrm{ctrl}}$ is the length of the control zone and
$t_{\mathrm{ATTD}}$ represents the average travel delay of the CAVs. Since the
travel time of every CAV is considered in $t_{\mathrm{ATTD}}$, it denotes the
individual benefits of $N$ CAVs, which is the secondary optimization target of
traffic efficiency.

In this study, we mainly focused on finding the optimal CAV passing order to
minimize the evacuation time, as defined in Definition 1. In addition, the
passing order should also satisfy the conflict-free relationship between the
CAVs. Section 3 presents the specific methods used to guarantee safety and
improve traffic efficiency. Moreover, the ATTD defined in Definition 2 is
introduced to evaluate the algorithm performance. The simulation results and
algorithm performance are presented in Section 4.

##  3 Methodology

In [13], a method using a _virtual platoon_ was proposed, which projects the
CAVs from different lanes onto a virtual lane. In this way, the CAVs from
different lanes can drive through the intersection as if they were in the same
lane. The most evident advantage is that the idling of the vehicles at the
stopping line is avoided to improve the traffic efficiency. A DFST method is
then introduced to find the CAV passing order.

Section 3.1 first introduces the graph-based intersection conflict analysis
method. Then, Section 3.2 presents the optimization of the DFST method to
obtain the local optimal passing order solution, termed as the iDFST method.
In Section 3.3, we introduce the MCC method to find the global optimal passing
order solution. Finally, the distributed controller design is presented in
Section 3.4 to undertake the scheduling plan.

###  3.1 Conflict Analysis

In Fig. 1, the CAVs from different lanes form multiple conflict points.
Despite the complicated conflict scenarios, they can be classified into the
following conflict modes. Without loss of generality, several CAVs are
selected in Fig. 2 to illustrate the conflict relationship. First, we
introduce the route conflicts [30], where CAVs have trajectory intersections
on their paths.

Figure 2: All conflict points and illustration of conflict relationship
between the CAVs. Crossing conflicts are plotted as $24$ red circles,
diverging conflicts as $14$ yellow squares, and converging conflicts as $6$
green arrows.

  1. 1)

_Crossing Conflict_ : Vehicles from different lanes have the potential to
collide while crossing the conflict points, indicated by the 24 red circles.
For example, CAV $2$ and CAV $3$ have a crossing conflict point.

  2. 2)

_Diverging Conflict_ : Lane changing and overtaking are not permitted, as
explained in Assumption 1. Thus, vehicles on the same lane cannot pass the
intersection simultaneously, as indicated by the 14 orange squares. For
example, CAV $5$ and CAV $6$ have a diverging conflict point.

  3. 3)

_Converging Conflict_ : Vehicles from different lanes cannot drive into the
same lane simultaneously, as shown by the 6 green arrows. For example, CAV $1$
and CAV $4$ have a converging conflict point.

Apart from the above-mentioned three kinds of conflicts that describe the
route conflict of the CAVs, we claim that there exists another conflict type
caused by the speed and acceleration limitation of the CAVs. For instance in
Fig. 2, CAV $7$ arrives at the control zone when CAV $1$ is about to reach the
stopping line with the designed virtual platoon velocity. In this case, CAV
$7$ cannot catch up with CAV $1$ at the stopping line even if they have no
conflict relationship, because of the limitations on the vehicle speed and
acceleration. Hence, we further introduce the fourth type of CAV conflict,
namely, the _reachability conflict_.

  1. 4.

_Reachability Conflict_ : Even if the CAVs have no route conflict, they cannot
pass the intersection simultaneously because of the acceleration and velocity
constraints. CAV $1$ and CAV $7$ have a reachability conflict.

Expanding equation (1) and (2), we obtain the judging condition as

$\frac{L_{\mathrm{prec}}}{v_{\mathrm{p}}}<\frac{L_{\mathrm{ctrl}}}{v_{\max}}+\frac{v_{\max}}{2a_{\max}},$
(5)

where $L_{\mathrm{prec}}$ is the distance of the preceding CAV from the
stopping line, and $v_{\mathrm{p}}$ is the designed virtual platoon velocity.
In other words, the CAVs that are very close to the intersection should not be
considered in the scheduling of new incoming CAVs. Note that most of the
existing researches assume that the CAVs can reach the stopping line under all
circumstances, i.e., the reachability conflict is ignored.

We define different conflict sets to describe the conflict relationship of the
CAVs. For each CAV $i\left(i\leq N,i\in\mathbb{N}^{+}\right)$, the crossing
set is defined as $\mathcal{C}_{i}$, diverging set as $\mathcal{D}_{i}$,
converging set as $\mathcal{V}_{i}$, and reachability set as
$\mathcal{R}_{i}$. Note that because the conflict sets are determined when the
CAV reaches the control zone, the CAV indexes in the conflict sets are smaller
than those of the ones on the control zone border, i.e., the elements in the
conflict sets satisfy (6).

$i<j,\,\mathrm{if}\
i\in\mathcal{C}_{j}\cup\mathcal{D}_{j}\cup\mathcal{V}_{j}\cup\mathcal{R}_{j}.$
(6)

######  Example 1 (Algorithms for $7$ CAVs)

Consider the example shown in Fig. 2. CAVs $1$ and $2$ are approaching from
the east direction and have two separate destinations. Three CAVs are
traveling straight from the west with $3$ on one lane and $5$, $6$ on another.
CAV $4$ is approaching from the south on the middle lane and CAV $7$ is on the
right lane. Note that CAV $7$ is too far from CAVs $1$ and $2$ to catch up
with them at the stopping line.

Note that in the virtual platoon, there exists a virtual leading vehicle $0$
traveling with a constant velocity in front of the CAVs that are closest to
the intersection. Thus, the leading CAVs in the real world maintain a typical
platooning behavior. Accordingly, CAV $0$ is added to the diverging set of the
CAV closest to the intersection on each lane; therefore, in Example 1,
$\mathcal{D}_{k}=\\{0\\},k=\\{1,2,3,4,5,7\\}$. The remaining conflict sets are
shown in Table 1.

$\mathbf{i}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---
$\mathcal{C}_{i}$ | $\varnothing$ | $\varnothing$ | $\\{2\\}$ | $\\{2,3\\}$ | $\\{2,4\\}$ | $\\{2,4\\}$ | $\varnothing$
$\mathcal{D}_{i}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{5\\}$ | $\\{0\\}$
$\mathcal{V}_{i}$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\\{1\\}$ | $\varnothing$ | $\varnothing$ | $\\{5,6\\}$
$\mathcal{R}_{i}$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\\{1,2\\}$
Table 1: Conflict Analysis of Example 1.

###  3.2 Improved DFST Method

(a) Conflict Directed Graph (b) Coexisting Undirected Graph

Figure 3: Fig. 3(a) is the conflict directed graph (CDG). The black
unidirectional edges represent the diverging conflicts and reachability
conflicts, whereas the red bidirectional edges represent the crossing
conflicts and converging conflicts. Fig 3(b) is the Coexisting Undirected
Graph (CUG), which is the complement graph of the CDG (exclude node $0$), and
describes the coexistence relationship of the vehicles.

Based on the conflict set analysis in Section 3.1, we further define the
conflict directed graph (CDG) $\mathcal{G}_{N+1}$ to represent the conflict
relationship between the CAVs.

######  Definition 3 (Conflict Directed Graph)

The CDG is denoted as
$\mathcal{G}_{N+1}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}\right)$. If there
are $N$ CAVs in the control zone, we have the node set
$\mathcal{V}_{N+1}=\\{0,1,2,\dots,N\\}$ (node $0$ denotes the virtual leading
vehicle). The unidirectional edge set is defined as
$\mathcal{E}_{N+1}^{u}=\\{(i,j)\mid
i\in\mathcal{D}_{j}\cup\mathcal{R}_{j}\\}$, and bidirectional edge set is
defined as $\mathcal{E}_{N+1}^{b}=\\{(i,j)\mid
i\in\mathcal{C}_{j}\cup\mathcal{V}_{j}\\}$. The edge set is the union of these
two sets as
$\mathcal{E}_{N+1}=\mathcal{E}_{N+1}^{u}\cup\mathcal{E}_{N+1}^{b}$.

The CDG of the case scenario in Fig. 2 is drawn in Fig. 3(a). The nodes in the
CDG represent the CAVs in the control zone. The black unidirectional edges
represent the diverging conflicts and reachability conflicts. The existence of
a unidirectional edge $(i,j)$ implies that CAV $j$ is not allowed to overtake
CAV $i$ because of Assumption 1 or CAV $j$ is not able to catch up to CAV $i$
because it satisfies (5). Thus, CAV $j$ cannot reach the intersection earlier
than CAV $i$. The red bidirectional edges denote the crossing conflict and
converging conflict, which means that the arrival sequence of the CAVs $i$ and
$j$’s can be exchanged. Note that in the DFST method, the crossing conflict
$\mathcal{C}_{i}$, diverging conflict $\mathcal{D}_{i}$, and converging
conflict $\mathcal{V}_{i}$ are treated as one union unidirectional-edge
conflict. In the following paragraph, we will interpret the separation of
these conflict sets to improve the performance of the original DFST algorithm.

It is straightforward that the CDG describes all the conflict relationships of
the CAVs. Previous researches have proved that the CDG in the DFST method
possesses a DFST, as shown in Lemma 1. Because this conclusion is drawn with
only unidirectional edges in the CDG, it can be applied to our iDFST method.

######  Lemma 1 ([13])

A CDG has a DFST with root node $0$, i.e., the virtual leading vehicle.

Because the CDG describes all the conflict relationships of the CAVs, and the
edges specifically describe the conflict type, a feasible passing order
solution can be obtained by building a spanning tree from the CDG. Similar to
the general graph theory, the depth of each node in the spanning tree is
calculated based on its distance to the root node $0$. Specifically, the depth
of the nodes represents the passing order of the CAVs, i.e., the CAVs at the
same depth shall pass the intersection simultaneously. [13] has proved that if
the spanning tree is built by the DFST method, the CAVs of the same depth have
a conflict-free attribute, i.e., a feasible spanning tree, which has been
proved in Lemma 2.

######  Lemma 2 ([13])

Consider a virtual platoon characterized by the spanning tree
$\mathcal{G}_{N+1}^{\prime}$, which is built from the CDG $\mathcal{G}_{N+1}$.
The trajectories of two CAVs at the same depth in $\mathcal{G}_{N+1}^{\prime}$
have no conflict relationship with each other.

Hence, it is evident that for a group of CAVs in the control zone, a passing
order solution is related to the DFST. It can be inferred that the depth of
the spanning tree is related to the traffic mobility at the intersection.
_Evacuation time_ represents the overall time cost for all the CAVs to pass
the intersection, i.e., the arrival time of the last CAV. It also represents
the largest depth of the spanning tree nodes, denoted as $d_{\mathrm{all}}$.
Thus, minimizing the evacuation time is equivalent to finding the smallest
possible $d_{\mathrm{all}}$ in all the feasible spanning trees. Formally, we
describe this problem as

$\text{SMALLEST-
DEPTH}=\left\\{<\mathcal{G}_{N+1},\mathcal{G}_{N+1}^{\prime},k>:\mathcal{G}_{N+1}\text{
has a feasible spanning tree }\mathcal{G}_{N+1}^{\prime}\text{ with
}d_{\mathrm{all}}=k\right\\}.$ (7)

We propose the iDFST method in Algorithm 1 and 2 to generate a DFST. For each
node $i$, we first find all its parent nodes in $\mathcal{G}_{N+1}$ in Lines 5
and 6 of Algorithm 1. Note that both the original DFST method and iDFST method
are based on the FIFO principle. Even though there are bidirectional edges in
the CDG, the passing order is decided according to the arrival sequence of the
CAVs. Thus, the larger-index CAVs should not be considered in the passing-
order optimization process of the smaller-index CAVs. This also implies that
only the smaller-index CAVs are selected as the parent node candidates,
corresponding to the conflict definition in (6).

Algorithm 1 Improved Depth-first Spanning Tree Method

1:Conflict Directed Graph
$\mathcal{G}_{N+1}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}\right)$

2:Improved Depth-first Spanning Tree
$\mathcal{G}_{N+1}^{\prime}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right)$

3:initialize: Set the depth of node $0$’s layer $d_{0}=0$

4:for $i=1,2,...,N$ do

5: $P_{u}=\\{m\in\mathcal{V}_{N+1}\mid(m,i)\in\mathcal{E}_{N+1}^{u}\\}$

6: $P_{b}=\\{n\in\mathcal{V}_{N+1}\mid(n,i)\in\mathcal{E}_{N+1}^{b}\\}$

7: $k$ = FIND-OPT-PARENT($\mathcal{G}_{N+1}^{\prime}$, $P_{u}$, $P_{b}$)

8: Set node $k$ as the parent node of $i$ in the graph
$\mathcal{G}_{N+1}^{\prime}$, add a node $i$ and an edge $(k,i)$ to the graph
$\mathcal{G}_{N+1}^{\prime}$, and set the depth of the node $i$ to $d_{k}+1$

9:end for

Algorithm 2 FIND-OPT-PARENT

1:$\mathcal{G}_{N+1}^{\prime}$, $P_{u}$, $P_{b}$

2:Optimal Parent node $k$

3:$l_{u}=\max d_{m},\mathrm{s.t.}\;m\in P_{u}$

4:$L_{b}=\\{d_{n}\mid n\in P_{b}\\}$

5:Find $\min{d_{k}},\mathrm{s.t.}\;\\{k\in P_{u}\cup P_{b}\mid
d_{k}+1>l_{u},\mathrm{and}\;(d_{k}+1)\cap L_{b}=\varnothing\\}$

6:return $k$

Then, in Line 7 of Algorithm 1, i.e., Algorithm 2, we treat the conflict types
differently. If the parent node $j$ is in the diverging or reachability
conflict set of CAV $i$, i.e., $j\in\mathcal{D}_{i}\cup\mathcal{R}_{i}$, $i$
cannot surpass $j$ because of the overtaking restriction or acceleration
limitation. In this case, we find the largest depth $l_{u}$ of the
unidirectional edge parents, because the target depth of CAV $i$ should not
surpass that of any of these CAVs. In other cases, the parent node $j$ is in
the crossing conflict set $\mathcal{C}_{i}$ or converging set
$\mathcal{V}_{i}$ of CAV $i$. It means CAVs $i$ and $j$ cannot arrive at the
intersection simultaneously, but their arrival order can be exchanged. Either
CAV $i$ or CAV $j$ can pass the intersection first; therefore, we find the
union depth set of the crossing conflict parents $L_{b}$. To find the optimal
parent $k$, we should select the proper depth of CAV $i$. Because the depth of
the parent $k$ is $d_{k}$, the depth of CAV $i$ is $d_{k}+1$. As mentioned
before, $d_{k}+1$ should be neither smaller than $l_{u}$ nor have an
intersection with the set $L_{b}$. Considering traffic efficiency, the depth
$d_{k}$ should be as small as possible, as shown in Line 5 in Algorithm 2. The
application of the iDFST method in Example 1 is shown in Table 2 and the
output iDFST is plotted in Fig. 4(b).

(a) DFST Spanning Tree (b) iDFST Spanning Tree (c) MCC Spanning Tree

Figure 4: Comparison of spanning tree results of three different methods. The DFST method yields $d_{\mathrm{all}}=5$, iDFST yields $d_{\mathrm{all}}=4$, and the MCC method yields $d_{\mathrm{all}}=3$. Candidate Node $\mathbf{i}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---
$P_{u}=\mathcal{D}_{i}\cup\mathcal{R}_{i}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{0\\}$ | $\\{5\\}$ | $\\{0,1,2\\}$
$P_{b}=\mathcal{C}_{i}\cup\mathcal{V}_{i}$ | $\varnothing$ | $\varnothing$ | $\\{2\\}$ | $\\{1,2,3\\}$ | $\\{2,4\\}$ | $\\{2,4\\}$ | $\\{5,6\\}$
$l_{u}$ | $0$ | $0$ | $0$ | $0$ | $0$ | $4$ | $1$
$L_{b}$ | $\varnothing$ | $\varnothing$ | $\\{1\\}$ | $\\{1,2\\}$ | $\\{1,3\\}$ | $\\{1,3\\}$ | $\\{4,5\\}$
Selected Parent Node $\mathbf{k}$ | 0 | 0 | 1 | 3 | 4 | 5 | 2
$d_{i}$ | $1$ | $1$ | $2$ | $3$ | $4$ | $5$ | $2$
$d_{\mathrm{all}}$ | $1$ | $1$ | $2$ | $3$ | $4$ | $5$ | $5$
Table 2: Application of the iDFST method to the CDG in Fig. 3(a), resulting in
Fig. 4(b).

The main improvement of the iDFST method is in Algorithm 2. In [13], the
conflict parent nodes are treated as one union conflict set $P=P_{u}\cup
P_{b}$. Therefore, the largest depth $d_{k}$ of all the parent nodes $P$ are
found in the same way. For instance, in the DFST method, the parent nodes of
CAV $7$ are the nodes $\\{0,1,2,5,6\\}$, which causes the largest depth
$d_{k}$ of the parent nodes to be $d_{6}=5$; therefore, the DFST method has
$d_{7}=6$, as shown in Fig. 4(a). On the contrary, in the iDFST method, the
conflict nodes are separated into two sets $P_{u},P_{b}$. By distinguishing
whether the parent nodes can be surpassed or not, the smaller
$d_{\mathrm{all}}$, i.e., the locally optimal solution is obtained. As shown
in Fig. 4(b), CAV $7$ is ranked $d_{7}=2$ in the iDFST method. Therefore, the
total depth of the $7$ CAVs is $d_{\mathrm{all}}=6$ in the DFST method whereas
the iDFST method optimizes it to $d_{\mathrm{all}}=5$.

###### Remark 1

We conclude that the DFST method focuses on the feasibility of the passing
order problem. The proposed iDFST method additionally considers the
optimality, i.e., finds the smallest depth for each CAV, but the solution is
still found CAV by CAV, i.e., based on the FIFO principle. In other words, the
iDFST solution is locally optimal in arranging each CAV. Because each CAV
needs to check all the conflict relationships of the parent nodes, the
computational complexity is $O(N^{2})$.

###  3.3 Minimum Clique Covering Method

As mentioned before, we aim to minimize the overall depth $d_{\mathrm{all}}$
of the spanning tree, which corresponds to the evacuation time of all the
CAVs. If we reconsider the traffic scenario in Fig. 1, a maximum number of six
CAVs can pass the intersection simultaneously. In other words, because there
is a limited number of CAVs in the control zone, the overall depth of the
spanning tree can be minimized by maximizing the CAV groups that can drive
through the intersection at the same time. From this point of view, another
method to describe the conflict relationships of the CAV is to describe their
coexistence relationships.

######  Definition 4 (Coexisting Undirected Graph)

The CUG is defined as the complement graph of the CDG $\mathcal{G}_{N+1}$,
excluding node $0$. Thus,
$\overline{\mathcal{G}}_{N}=\left(\overline{\mathcal{V}}_{N},\overline{\mathcal{E}}_{N}\right)$,
where $\overline{\mathcal{V}}_{N}=\mathcal{V}_{N+1}-\\{0\\}$,
$\overline{\mathcal{E}}_{N}=\\{(i,j)\mid
i,j\in\overline{\mathcal{V}}_{N},i\neq j,\mathrm{and}\
(i,j)\notin\mathcal{E}_{N+1}\\}$.

In Example 1, the CDG is drawn in Fig. 3(a) and the CUG in Fig. 3(b). Because
the CDG edge $\mathcal{E}_{N+1}$ implies that two CAVs have conflicts and the
CUG is the complement graph of the CDG, the CUG edge
$\overline{\mathcal{V}}_{N}$ implies that the two CAVs are conflict-free,
i.e., they can pass through the intersection simultaneously.

Recall that we aim to minimize the overall depth $d_{\mathrm{all}}$ of the
spanning tree. Because the total number of CAVs, i.e., the node number
$\left|\overline{\mathcal{V}}_{N}\right|$, is a constant value $N$, minimizing
the overall depth of the spanning tree is equivalent to widening its average
width. Thus, solving the optimal passing solution is equivalent to finding the
minimum number of groups of the combinations of coexisting CAVs in the CUG.
Note that this conclusion corresponds to common sense. The maximum groups of
the coexisting CAVs represent the maximizing of the time utility of the
intersection, which minimizes the overall evacuation time.

In graph theory, the clique is suitable for describing the coexistence
relationship of the CAVs. The definition of the clique is shown in Definition
5, and the cliques of sizes $3,4,5,6$ are plotted in Fig. 5.

Figure 5: Cliques of sizes $2,3,4,5,6$.

######  Definition 5 (Clique[31])

A clique $C$ in an undirected graph $G=(V,E)$ is a subset of the nodes,
$C\subseteq V,$ such that every two distinct nodes are adjacent. This is
equivalent to the condition that the subgraph of $G$ induced by $C$ is a
complete graph.

The clique $C$ is the aforementioned group. Because the edges are selected
from the CUG $\overline{\mathcal{G}}_{N}$, the CAVs in one clique can pass
through the intersection simultaneously in a conflict-free manner. In Fig.
3(b), $C=\\{1,2\\}$ is a clique, but it is not the maximum clique because
cliques of larger sizes exist, e.g., $\\{1,3,5\\}$. The maximum clique of a
graph $G$ is a clique with the maximum number of nodes. Particularly, the
number of nodes in the maximum clique in $G$ is called the clique number,
denoted as $\omega(G)$. In Fig. 3(b), $\omega(\overline{\mathcal{G}}_{N})=3$,
which corresponds to the traffic scenario in Example 1, where a maximum number
of $3$ CAVs can pass through the intersection simultaneously. Note that in the
overall intersection scenario Fig. 1, $\omega(\overline{\mathcal{G}}_{N})=6$
as long as there is an adequate number of CAVs on the coexisting lanes.

Recall that our target is to find the minimum number of groups in the CUG,
i.e., the minimum number of cliques covering all the nodes in the CUG
$\overline{\mathcal{G}}_{N}$. Therefore, we define the MCC problem as follows.

######  Definition 6 (Minimum Clique Cover (MCC) [32])

A clique cover of a graph $G=(V,E)$ is a partition of $V$ into $k$ disjoint
subsets $V_{1},V_{2},\dots,V_{k}$, such that for $1\leq i\leq k$, the subgraph
induced by $V_{i}$ is a clique, i.e., a complete graph. The MCC number of $G$
is the minimum number of subsets in a clique cover of $G$, denoted as
$\theta(G)$.

The MCC number $\theta(\overline{\mathcal{G}}_{N})$ of the CUG represents the
minimum number of cliques covering the CUG. Because the cliques in the CUG
represent the CAVs that can pass through the intersection simultaneously,
these CAVs in the same clique can be scheduled to drive through the
intersection at the same time, i.e., be scheduled at the same depth of the
spanning tree. Note that the MCC does not lead to the maximum clique and vice
versa. For example, considering the CUG in Fig. 3(b), the MCC number
$\theta(\overline{\mathcal{G}}_{N})=4$ and the corresponding cliques are
listed in Table 3. The maximum cliques $\\{1,3,5\\}$ and $\\{1,3,6\\}$ appear
in solution $1$ and solution $2$ but not in the subsequent solutions. We
conclude that for an arbitrary intersection scenario, the coexistence
relationship of the incoming CAVs is perfectly depicted in the CUG
$\overline{\mathcal{G}}_{N}$. The clique number
$\omega(\overline{\mathcal{G}}_{N})$ of the CUG represents the maximum number
of CAVs that can simultaneously pass through the intersection, whereas the MCC
number $\theta(\overline{\mathcal{G}}_{N})$ represents the possible minimum
passing order solution.

Solutions Subsets | ${V}_{1}$ | ${V}_{2}$ | ${V}_{3}$ | ${V}_{4}$
---|---|---|---|---
1 | $\\{1,3,5\\}$ | $\\{4,7\\}$ | $\\{2\\}$ | $\\{6\\}$
2 | $\\{1,3,6\\}$ | $\\{4,7\\}$ | $\\{2\\}$ | $\\{5\\}$
3 | $\\{1,2\\}$ | $\\{3,5\\}$ | $\\{4,7\\}$ | $\\{6\\}$
4 | $\\{1,2\\}$ | $\\{3,6\\}$ | $\\{4,7\\}$ | $\\{5\\}$
5 | $\\{1,5\\}$ | $\\{3,6\\}$ | $\\{4,7\\}$ | $\\{2\\}$
6 | $\\{1,6\\}$ | $\\{3,5\\}$ | $\\{4,7\\}$ | $\\{2\\}$
Table 3: Possible minimum clique cover solutions of Fig. 3(b). Note that
$\theta(\overline{\mathcal{G}}_{N})=4$ in this graph.

Note that $\theta(\overline{\mathcal{G}}_{N})=4$ in the CUG Fig. 3(b), which
means the spanning tree generated by the MCC solutions are in
$d_{\mathrm{all}}=4$. It also means that the theoretical evacuation times of
these solutions are the same, i.e., the theoretical values of
$t_{\mathrm{evac}}$ are the same. Thus, the evaluation index of
$t_{\mathrm{evac}}$ in (3) corresponds to
$\theta(\overline{\mathcal{G}}_{N})$, which is the global optimal passing
order considering the evacuation time. In addition, we further consider the
ATTD among these solutions as a secondary index. The definition of
$t_{\mathrm{ATTD}}$ in (4) can be rewritten in graphical terms as

$\displaystyle\min$
$\displaystyle\sum_{i=1}^{k}d_{i}|V_{i}|,\,i\in\mathbb{N}^{+}$ (8)
$\displaystyle\mathrm{subject\;to:}$ $\displaystyle\sum_{i=1}^{k}V_{i}=N,$

where $d_{i}$ is the spanning tree depth of the CAV nodes in $V_{i}$, as
defined in Section 3.2.

In this circumstance, it is evident that the subsets $V_{i}$ should be
arranged in the descending order to decrease the average $d_{i}$ of $N$ CAVs
in (8). Because of the same reason, we prefer to choose the solutions with the
maximum cliques when they have the same $\theta(\overline{\mathcal{G}}_{N})$.
For example, in Table 3, we tend to choose the Solution $1$, and the
corresponding optimized spanning tree is scheduled as
$\\{1,3,5\\}\rightarrow\\{4,7\\}\rightarrow\\{2\\}\rightarrow\\{6\\}$, as
shown in Fig. 4(c).

The CUG $\overline{\mathcal{G}}_{N}$ only contains the coexistence information
of the CAVs, whereas the passing order of the CAVs on the same lane should be
strictly according to their relative positions because of Assumption 1. The
MCC method can generate solutions that cannot be directly executed, e.g.,
Solution $2$ in Table 3. The spanning tree is formed as
$\\{1,3,6\\}\rightarrow\\{4,7\\}\rightarrow\\{2\\}\rightarrow\\{5\\}$.
However, this solution is not feasible because CAV $5$ is in front of CAV $6$.
We prove that this can be solved by exchanging the unfeasible sequence, as
shown in Proposition 1.

###### Proposition 1

If the MCC method leads to an unfeasible solution, where the CAVs $i$ and $j$
have conflicting trajectories, exchanging the positions of $i$ and $j$ solves
the conflict. The new solution is also an MCC solution.

Because the unfeasible solution is related to CAVs on the same lane, it is
self-evident that exchanging the conflicted CAVs solves the conflict.
Meanwhile, the CAVs on the same lane have identical edges in the CUG to those
of the other CAVs. Therefore, permutation and combination of $n$ CAVs on the
same lane result in $n!$ similar MCC solutions, where only one is the feasible
solution.

Algorithm 3 Minimum Clique Cover Method

1:Coexisting Undirected Graph
$\overline{\mathcal{G}}_{N}=\left(\overline{\mathcal{V}}_{N},\overline{\mathcal{E}}_{N}\right)$

2:Spanning Tree
$\mathcal{G}_{N+1}^{\prime}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right)$

3:Calculate the complement graph
$\overline{\overline{\mathcal{G}}}_{N}=\mathcal{G}_{N}$

4:Find the breadth-first search sequence $K=(v_{1},v_{2},\dots,v_{N})$ of the
nodes in $\mathcal{G}_{N}$

5:for each node $v_{i}$ of $\mathcal{G}_{N}$ in the sequence $K$ do

6: assign node $v_{i}$ the smallest possible clique index

7:end for

8:Rank $V_{1},V_{2},\dots,V_{k}$ in the descending order and obtain the
spanning $\mathcal{G}_{N+1}^{\prime}$

9:Exchange the conflicting CAVs of $\mathcal{G}_{N+1}^{\prime}$ in the same
lane if necessary

10:return $\mathcal{G}_{N+1}^{\prime}$

After introducing the MCC problem, we describe the formal complexity of the
original SMALLEST-DEPTH problem in Theorem 1.

###### Theorem 1

SMALLEST-DEPTH problem is NP-complete.

###### Proof 1

First, we prove that $\text{SMALLEST-DEPTH}\in\text{NP}$. Assume we have a CDG
$\mathcal{G}_{N+1}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}\right)$, a
spanning tree
$\mathcal{G}_{N+1}^{\prime}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right)$,
and an integral $k$. The certificate we choose is $k=|\mathcal{V}_{N+1}|$. The
verification algorithm consists of two procedures, i.e., whether the spanning
tree $\mathcal{G}_{N+1}^{\prime}$ is feasible and $d_{\mathrm{all}}$ of the
spanning tree is $k$. Checking the edge connections of $\mathcal{E}_{N+1}$ and
the depth of each node of $\mathcal{V}_{N+1}$ can be evidently accomplished in
polynomial time.

Secondly, we prove that the SMALLEST-DEPTH problem defined in (7) is NP-hard
by showing that it can be reduced to the MINIMUM-CLIQUE-COVER problem [32]
defined in Definition 6, i.e., SMALLEST-DEPTH $\leq_{p}$ MINIMUM-CLIQUE-COVER.
As mentioned before, given a CDG
$\mathcal{G}_{N+1}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}\right)$, we
define the corresponding CUG as
$\overline{\mathcal{G}}_{N}=\left(\overline{\mathcal{V}}_{N},\overline{\mathcal{E}}_{N}\right)$,
where $\overline{\mathcal{V}}_{N}=\mathcal{V}_{N+1}-\\{0\\}$,
$\overline{\mathcal{E}}_{N}=\\{(i,j)\mid
i,j\in\overline{\mathcal{V}}_{N},i\neq j,\mathrm{and}\
(i,j)\notin\mathcal{E}_{N+1}\\}$. The transformation of the CDG into CUG is
easily achieved in polynomial time.

If the CDG $\mathcal{G}_{N+1}$ has a feasible spanning tree
$\mathcal{G}_{N+1}^{\prime}$ with $d_{\mathrm{all}}=k$, we claim that the
corresponding CUG $\overline{\mathcal{G}}_{N}$ has
$\overline{\mathcal{V}}_{N}$ partitioned into $k$ disjoint cliques. Because
$\mathcal{G}_{N+1}^{\prime}$ is a feasible spanning tree, if $i,j$ are the
nodes of same depth, they should not have a conflicting relationship, i.e.,
$(i,j)\notin\mathcal{E}_{N+1}$. Because the CUG is the complement graph of the
CDG, it is evident that $(i,j)\in\overline{\mathcal{E}}_{N}$. Thus, the nodes
of the same depth in the spanning tree $\mathcal{G}_{N+1}^{\prime}$ are
connected with each other, i.e., they form cliques in
$\overline{\mathcal{G}}_{N}$. The overall depth of the spanning tree $k$
corresponds to the clique cover number of $\overline{\mathcal{G}}_{N}$.

On the contrary, we assume the the CUG $\overline{\mathcal{G}}_{N}$ has
$\overline{\mathcal{V}}_{N}$ partitioned into $k$ disjoint cliques. From
Proposition 1, we know that $k$ disjoint cliques lead to a feasible passing
order, that is, the CDG $\mathcal{G}_{N+1}$ has a feasible spanning tree
$\mathcal{G}_{N+1}^{\prime}$ with $d_{\mathrm{all}}=k$.

We have proven that the SMALLEST-DEPTH problem can be reduced to the MCC
problem, which implies that the MCC number
$\theta(\overline{\mathcal{G}}_{N})$ of the CUG is the smallest possible
$d_{\mathrm{all}}$ of the spanning tree solutions, i.e., the global optimal
solution. However, solving the NP-hard problem is a difficult task in real
deployment. In the simulation, for a small number of vehicles, we applied the
brute-force method to find the MCC number, i.e., the strictly global optimal
solution. In the previous work, we have shown that when the traffic scenario
is simple, i.e., a maximum number of two vehicles are allowed to pass the
intersection simultaneously, the CAV scheduling problem is reduced to a
maximum matching problem [33]. In this case, the global optimal solution is
obtained in $O(n^{4})$ time.

For a large number of vehicles and complicated intersection scenarios, the
dimensional explosion makes the brute-force method impossible to deploy.
Therefore, we apply a practical approach to solve the problem heuristically,
as shown in Line 3 to 7 of Algorithm 3. The MCC problem of $G$ is proved to be
reduced to the graph coloring problem of $\overline{G}$ [34], and there are
numerous heuristic methods to solve the graph coloring problem. Recall that we
intend to find the solutions with larger cliques. Thus, we first generate a
node sequence $K=(v_{1},v_{2},\dots,v_{N})$ by breadth-first search (BFS).
Then, we greedily assign node $v_{i}$ the smallest possible color, i.e., the
clique index according to the node sequence $K$, forming the subset cliques
$V_{1},\dots,V_{k}$. Line 8 is the spanning process, which arranges the
cliques into a spanning tree and has a constant calculation time.

###### Remark 2

The BFS sequence generation needs
$O(\left|{\mathcal{E}_{N}}\right|+\left|{\mathcal{V}_{N}}\right|)$.
Afterwards, the MCC is solved greedily in $O(\left|{\mathcal{V}_{N}}\right|)$
and the ranking of the spanning tree requires a constant time. Hence, the
overall computational complexity of the heuristically solved MCC method, i.e.,
Algorithm 3 is
$O(\left|{\mathcal{E}_{N}}\right|+2\left|{\mathcal{V}_{N}}\right|+1)=O(N)$,
which is lower than $O(N^{2})$ of the DFST and iDFST methods. In the
simulation, we will show that even if the heuristically solved MCC method is
not the strictly globally optimal solution, it outperforms the other two
methods.

###  3.4 Distributed Control

In the ideal communication condition, every CAV obtains driving information,
e.g., position and velocity, from the other CAVs in real-time. However, the
communication resource, e.g., the bandwidth, is always limited around an
intersection. Therefore, we design a hierarchical framework to lower the
communication burden. In the upper level, the central coordinator collects the
information of the CAVs and assigns the scheduled arrival plans to them. In
the lower level, a CAV executes its arrival time through distributed control.
Similar to the virtual platoon analysis in [13], we design the distributed
control as follows.

####  3.4.1 Geometric Topology

As mentioned in Section 3, all the three methods, i.e., DFST, iDFST, and MCC,
lead to a feasible spanning tree
$\mathcal{G}_{N+1}^{\prime}=\left(\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right)$,
as shown in Fig. 4, which forms the geometric topology of the virtual platoon.
Because each node $\mathcal{V}_{i}$ in $\mathcal{G}_{N+1}^{\prime}$ represents
a CAV $i$ and the edge $\mathcal{E}_{i}^{\prime}=(j,i)$ represents the virtual
preceding CAV $j$, the CAV can always follow its parent node CAV
$\mathcal{V}_{j}$. In other words, CAV $i$ and its parent CAV $j$ intend to
maintain a constant desired car-following distance $D_{\mathrm{des}}$ and the
same velocity $v_{\mathrm{des}}$.

$\left\\{\begin{array}[]{l}\displaystyle\lim_{t\rightarrow\infty}\left\|v_{i}(t)-v_{j}(t)\right\|=0\\\
\displaystyle\lim_{t\rightarrow\infty}\left(p_{j}(t)-p_{i}(t)-D_{\mathrm{des}}\right)=0\end{array},i\in\mathbb{N}^{+},\right.$
(9)

where $v_{i}(t),v_{j}(t)$ and $p_{i}(t),p_{j}(t)$ denote the velocity and
position of the CAVs $i$ and $j$.

Lemma 2 has proven that the CAVs at the same depth have no conflict
relationship. Therefore, if CAVs $i$ and $j$ are of the same depth,

$\displaystyle\lim_{t\rightarrow\infty}\left(p_{i}(t)-p_{j}(t)\right)=0.$ (10)

####  3.4.2 Communication Topology

(a) iDFST (b) MCC

Figure 6: Predecessor–leader following (PLF) communication topology
illustration of the iDFST and MCC methods. Red edges represent the geometric
topology of the virtual platoon, which is the result of different scheduling
methods, as shown in Fig. 4. The black edges represent the PLF communication
topology of the virtual platoon, where each CAV collects information from the
virtual preceding vehicle and the virtual leading vehicle.

The communication topology represents the information exchange route among the
CAVs. Various communication topologies have been studied in the field of
vehicle platoon control [35]. For simplicity, we use the predecessor–leader
following (PLF) topology, where each CAV communicates with its preceding
vehicle in the virtual platoon and the virtual leading vehicle. Similar to the
topology analysis in [13, 14], we introduce
$\overline{\mathcal{G}}_{N+1}^{\prime}=\left\\{\overline{\mathcal{V}}_{N+1},\overline{\mathcal{E}}_{N+1}\right\\}$
as the communication graph of the spanning tree
$\mathcal{G}_{N+1}^{\prime}=\left\\{\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right\\}$.
The nodes still represent the CAVs; thus,
$\overline{\mathcal{V}}_{N+1}=\mathcal{V}_{N+1}$. Meanwhile, the edges
$\overline{\mathcal{E}}_{N+1}$ represent the information exchange among the
CAVs. The communication topologies of the iDFST and MCC spanning trees are
shown in Fig. 6. Specifically, the CAVs collect information from the following
two types of CAVs.

  1. 1)

_Virtual leading vehicle_ : because the CAV obtains its target layer in the
scheduled spanning tree, every CAV in the spanning tree communicates with the
virtual leading vehicle $0$.

$\left\\{(0,j)\mid j\in\overline{\mathcal{V}}_{N+1},\,j\neq
0\right\\}\in\overline{\mathcal{E}}_{N+1}.$ (11)

  2. 2)

_Virtual preceding vehicle_ : the second type is the virtual preceding vehicle
in the spanning tree
$\mathcal{G}_{N+1}^{\prime}=\left\\{\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right\\}$.
This term is used to help the CAVs maintain a safe distance from the upper
layer in the spanning tree. Note that the preceding vehicle in the spanning
tree does not symbolize the preceding vehicle of the same lane in the
simulation and vice versa. The CAVs $2$ and $3$ are the preceding vehicles of
CAV $7$ in the iDFST and MCC spanning trees. respectively.

$\left\\{(i,j)\mid(i,j)\in\mathcal{E}_{N+1}^{\prime},\,i,j\neq
0\right\\}\in\overline{\mathcal{E}}_{N+1}.$ (12)

The adjacency matrix $\bm{A}=\left[a_{ij}\right]\in\mathbb{R}^{N\times N}$ and
pinning matrix $\bm{Q}=\left[q_{ij}\right]\in\mathbb{R}^{N\times N}$ are
further introduced to represent the communication topology.

$a_{ij}=\left\\{\begin{array}[]{rl}1,&\mathrm{if}\,(i,j)\in\overline{\mathcal{E}}_{N+1}\\\
0,&\mathrm{else}\end{array}\right.,\,i,j\in\mathbb{N}^{+},$ (13)

where $a_{ij}=1$ indicates that CAV $i$ receives information from CAV $j$.

$q_{ij}=\left\\{\begin{array}[]{rl}1,&\mathrm{if}\,i=j,(0,j)\in\overline{\mathcal{E}}_{N+1}\\\
0,&\mathrm{else}\end{array}\right.,\,i,j\in\mathbb{N}^{+},$ (14)

where $q_{ij}=1$ indicates that CAV $i$ receives information from the virtual
leading vehicle $0$, forming a diagonal matrix $\bm{Q}$.

Further, a Laplacian matrix $\bm{L}=\left[l_{ij}\right]\in\mathbb{R}^{N\times
N}$ is also introduced as

$l_{ij}=\left\\{\begin{array}[]{ll}-a_{ij},&i\neq j\\\
\sum_{k=1}^{N}a_{ik},&i=j\end{array}\right.,\,i,j\in\mathbb{N}^{+}.$ (15)

Note that we assume the information exchange is bidirectional; thus,
$a_{ij}=a_{ji}$. Hence, both $\bm{A}$, $\bm{Q}$ and $\bm{L}$ are symmetric
matrices.

###### Remark 3

The communication topology graph
$\overline{\mathcal{G}}_{N+1}^{\prime}=\left\\{\overline{\mathcal{V}}_{N+1},\overline{\mathcal{E}}_{N+1}\right\\}$
is designed based on the geometric topology graph of the spanning tree
$\mathcal{G}_{N+1}^{\prime}=\left\\{\mathcal{V}_{N+1},\mathcal{E}_{N+1}^{\prime}\right\\}$.
Because the geometric topology represents the feasibility and optimality of an
arrival plan, the communication topology represents the communication
realization of the arrival plan. [13] does not specify the communication
topology. However, in this paper, we use PLF to simplify the communication
topology and demonstrate the effectiveness of the algorithm. Topologies with
greater complexity will be addressed in future research.

####  3.4.3 Controller Design

The control input of CAV $i$ is calculated according to the communication
topology. The car-following distance in the virtual platooning is defined as
in (9). Meanwhile, to align the CAVs at the same depth to arrive at the
stopping line, (10) is indirectly guaranteed by the virtual leading vehicle
control feedback. Hence, the virtual platoon controller is designed as
follows.

Firstly, a union set $\mathbb{I}_{i}$ is defined to describe the information
exchange of CAV $i$, as follows:

$\mathbb{I}_{i}=\left\\{j\mid a_{ij}=1\right\\}\cup\left\\{0\mid
q_{ii}=1\right\\}.$ (16)

The distance and velocity errors are defined as

$\begin{array}[]{l}\delta_{\mathrm{p}}^{(i,j)}=p_{j}(t)-p_{i}(t)-D_{\mathrm{des}}\left(d_{j}-d_{i}\right)\\\
\delta_{\mathrm{v}}^{(i,j)}=v_{i}(t)-v_{j}(t)\end{array},\,j\in\mathbb{I}_{i},$
(17)

where $\delta_{\mathrm{p}}^{(i,j)}$ is the car-following distance error of CAV
$i$, and $\delta_{\mathrm{v}}^{(i,j)}$ is the car-following velocity error
considering all the CAVs in $\mathbb{I}_{i}$.

A linear feedback controller is designed as follows:

$\displaystyle u_{i}$
$\displaystyle=-\sum_{j\in\mathbb{I}_{i}}k_{p}\delta_{\mathrm{p}}^{(i,j)}-\sum_{j\in\mathbb{I}_{i}}k_{v}\delta_{\mathrm{v}}^{(i,j)}$
(18)
$\displaystyle=-k_{p}\sum_{j\in\mathbb{I}_{i}}a_{ij}\left(p_{j}(t)-p_{i}(t)-D_{\mathrm{des}}\left(d_{j}-d_{i}\right)\right)-k_{p}q_{ii}\left(p_{0}(t)-p_{i}(t)-D_{\mathrm{des}}\left(d_{0}-d_{i}\right)\right)$
$\displaystyle-
k_{v}\sum_{j\in\mathbb{I}_{i}}a_{ij}\left(v_{i}-v_{j}\right)-k_{v}q_{ii}\left(v_{i}-v_{0}\right),$

where $k_{p}$ and $k_{v}$ are the feedback gains of the distance and velocity
errors of CAV $i$. Because we consider a homogeneous scenario, the same gains
are set for all the CAVs.

As mentioned before, we consider a second-order vehicle dynamics as shown in
(1). We define the car following errors as the new vehicle state.

$\bar{\bm{x}}_{i}=\left[\begin{array}[]{c}\bar{x}_{i,1}\\\ \bar{x}_{i,2}\\\
\end{array}\right]=\left[\begin{array}[]{c}p_{0}-p_{i}-D_{\mathrm{des}}\left(d_{0}-d_{i}\right)\\\
v_{i}-v_{0}\\\ \end{array}\right],i\in\mathbb{N}^{+}.$ (19)

The vehicle input remains the same, i.e., $\bar{u}_{i}=u_{i}$.

Therefore, the car-following vehicle dynamic model is

$\dot{\bar{\bm{x}}}_{i}=\bm{A}\bar{\bm{x}}_{i}+\bm{B}\bar{u}_{i},\,i\in\mathbb{N}^{+}.$
(20)

The linear feedback controller is simplified to

$\bar{u}_{i}=-k_{p}\sum_{j}\left(l_{ij}+q_{ij}\right)\bar{x}_{j,1}-k_{v}\sum_{j}\left(l_{ij}+q_{ij}\right)\bar{x}_{j,2},\,j\in\mathbb{I}_{i}.$
(21)

Defining $\bm{k}=\left[k_{p},k_{i}\right]^{T}$, we have

$\bar{u}_{i}=-\sum_{j}\left(l_{ij}+q_{ij}\right)\bm{k}^{T}\bar{\bm{x}}_{i},\,i\in\mathbb{N}^{+}.$
(22)

##  4 Simulation

###  4.1 Simulation Environment and Evaluation Index

Types | Parameter | Symbol | Value
---|---|---|---
Simulation Parameters | Simulation step | - | 0.1 s
Initial vehicle speed | - | 2 m/s
Control zone length | $L_{\mathrm{ctrl}}$ | 900 m
Controller Parameters | Feedback gain of distance error | $k_{p}$ | 0.1
Feedback gain of velocity error | $k_{i}$ | 0.3
Desired velocity of the virtual leading vehicle | $v_{0}$ | 10 m/s
Desired car-following distance of the virtual platoon | $D_{\mathrm{des}}$ | 30 m
Maximum acceleration | $a_{\max}$ | 5 m/s2
Minimum acceleration | $a_{\min}$ | -6 m/s2
Maximum velocity | $v_{\max}$ | 25 m/s
Minimum velocity | $v_{\min}$ | 0 m/s
Table 4: Key Parameters.

The traffic simulation was conducted in SUMO, which is widely used in traffic
researches[36]. The simulation was run on an Intel Core i7-7700 3.6 GHz
processor. The intersection scenario and lane direction settings are the same
as shown in Fig. 1, and the control zone length $R_{c}=1000m$. The CAV arrival
is assumed to be a Poisson distributed flow, given by

$P(X=k)=\frac{\lambda^{k}}{k!}e^{-\lambda},k=0,1,\cdots,$ (23)

where $X$ represents the vehicle’s arrival at the control zone. $\lambda$ is
the expected value as well as the variance of the Poisson distribution.

Traffic efficiency is the main consideration in our scheduling algorithm. For
the overall traffic efficiency, the evacuation time is as defined in
Definition 1. In terms of individual benefits, the ATTD is considered as
defined in Definition 2. Other key simulation parameters are shown in Table 4.

###  4.2 Case Study of Algorithm Comparison

(a) Conflict Directed Graph (b) Coexisting Undirected Graph

(c) DFST Method Spanning Tree (d) iDFST Method Spanning Tree

(e) MCC Method Spanning Tree

Figure 7: A case study of $30$ CAVs. CDG and CUG are presented in Fig. 7(a)
and Fig. 7(b), respectively, to describe the conflict and coexistence
relationship of the CAVs. DFST arranges the CAVs as shown in Fig .7(c) with
the maximum layer of $d_{\mathrm{all}}=14$. iDFST, which is an improvement of
DFST, utilizes some nodes (red ones) to optimize the overall depth, as shown
in Fig. 7(d), resulting in $d_{\mathrm{all}}=11$. The MCC method finds the
minimum group of CAVs that can pass through the intersection simultaneously
(nodes of the same color), resulting in $d_{\mathrm{all}}=10$, as shown in
Fig. 7(e). The complete simulation video is available at
https://github.com/CeroChen/GraphBashedCoordination

.

We demonstrate a case study in Example 2 to show the effectiveness of the
proposed algorithms. The benchmark algorithm is the DFST method proposed in
[13]. Based on DFST, the first algorithm is the iDFST presented in Section
3.2. The MCC algorithm has been explained in Section 3.3, which applies a
heuristic algorithm to solve the MCC problem.

######  Example 2 (A case study of $30$ CAVs)

The traffic scenario remains the same as shown in Fig 1(b). A total number of
$30$ vehicles arrive at the intersection with $\lambda=3$ Poisson
distribution. The vehicle arrivals are generated randomly and remain identical
among the three algorithms.

As mentioned before, CDG and CUG are employed to describe the conflict
relationship of the vehicles. The CDG is plotted in Fig. 7(a) as explained in
Definition 3. The red dashed edges are the crossing conflicts and converging
conflicts, whereas the black solid edges are the diverging and reachability
conflicts. Fig. 7(b) depicts the CUG defined in Definition 4, which is the
complement graph of the CDG. The edges are the coexisting relationships, i.e.,
the conflict-free vehicles.

Although identical vehicle arrivals are set for the three algorithms,
different spanning trees, i.e., passing order solutions, are obtained. The
spanning trees are carried out by scheduling the vehicles in the same layer to
pass the intersection simultaneously. Thus, the overall depth
$d_{\mathrm{all}}$ of the spanning tree represents the evacuation time of the
solution. First, the spanning trees of the DFST and iDFST methods are shown in
Fig 7(c) and Fig. 7(d), which are derived from Fig. 7(a). Both the DFST and
iDFST methods are based on the FIFO principle, i.e., obtaining the spanning
tree vehicle by vehicle. Because the DFST has limited optimization of vehicle
scheduling, it is a feasible solution with $d_{\mathrm{all}}=14$. In contrast,
iDFST separates the conflict types to find the optimal place for each vehicle
and obtains a locally optimal solution. Hence, the overall depth of the iDFST
method is $d_{\mathrm{all}}=11$. Note that the red nodes are the vehicles that
are brought forward when compared with the DFST method. Fig 7(e) depicts the
solution derived from Fig. 7(b) by using the MCC method. The nodes of the same
color represent the vehicles in the same clique, i.e., the vehicles that are
scheduled to pass the intersection at the same time. The same cliques and the
corresponding colors are drawn in Fig. 7(b) to show the MCC result with
$d_{\mathrm{all}}=10$. Moreover, because the cliques can be arranged in the
descending order, the average travel time of the vehicles in the MCC method is
also better than that in the former algorithms. A detailed discussion is
presented in the following simulations.

###  4.3 Algorithm Validation with Small Number of Vehicles

Figure 8: The maximum depth of the spanning tree obtained by different
algorithms. Simulation is conducted $200$ times for each algorithm and $9$
vehicles are generated randomly in each simulation. The orange lines are the
median values of the results and the green triangles are the average values.

Next, we focus on the optimality of the three algorithms in general cases. In
this section, we introduce the MCC-BruteForce algorithm. It enumerates all the
possible combinations of the cliques, i.e., solves the MCC problem by using
the brute force method. Although MCC-BruteForce provides us the theoretical
global optimal solution, the huge calculation burden makes it impossible to
apply it to a large number of vehicles. Thus, $9$ is set as the number of
input vehicles.

Because the vehicle scheduling problem is strongly related to the vehicle
arrival time, conducting a small number of simulations is insufficient. Hence,
$200$ repetitions of the simulation were conducted for each algorithm. It is
worth mentioning that these $200$ instances of vehicle arrival input are
randomly generated by Poisson distribution, as shown in (23), and they are
identical across all four algorithms.

We use the box plot to illustrate the maximum depth of the spanning tree,
i.e., the overall traffic efficiency, as shown in Fig. 8. The red lines are
the median values of the corresponding simulation results, whereas the green
triangles represent the average values. Compared with the DFST method, both
the iDFST and MCC algorithms can reduce the maximum depth. The first quartile
value, median value, and third quartile value are $3,4,5$, respectively.
However, the average values of the results are not the same. The iDFST method
attained an average value of $4.08$, whereas the average value in the MCC
method was $4.035$ and that of MCC-BruteForce was $4.015$. Recall that the
vehicle arrivals were identical for these algorithms; therefore, it can be
inferred that the MCC-BruteForce method obtains the global optimal solution.
Because of the heuristic MCC method introduced in Section 3.3, the MCC method
cannot obtain the global optimal solution. Nevertheless, it achieves better
result than the iDFST method, which obtains the locally optimal solution.

###  4.4 Simulation Results for Various Numbers of Input Vehicles

(a) Evacuation time (b) Average travel time delay (c) Fuel consumption

Figure 9:  Comparison of traffic efficiency and fuel consumption of three
algorithms for various numbers of input vehicles. For each algorithm, $10$
repetitions of the simulation were conducted for each number of input
vehicles. The red lines are the median values and the triangles are the
average values. As the number of vehicles increases, MCC shows better
performance than the other two algorithms in improving the traffic efficiency
and reducing the fuel consumption.

For conducting the simulation on a larger scale, we extended the number of
input vehicles from $10$ to $50$ and further compared the algorithms.
$\lambda=3$ was set as the input for the Poisson distribution of the vehicle
arrival. We used the evacuation time and ATTD to evaluate the traffic
efficiency. In terms of fuel consumption, the HBEFA3 model was used to
evaluate the fuel consumption of the CAVs, which was integrated with SUMO
[37]. As shown in Fig 9, the red lines in the box plot are the median value
and the triangles are the average values. Ten repetitions of the simulation
were conducted for each number of vehicles, and the vehicle arrivals were
identical across the three algorithms.

In terms of the overall traffic efficiency evaluation, both the iDFST and MCC
methods reduce the evacuation time significantly when compared with DFST. As
shown in Fig 9(a), the average value of the evacuation time in DFST for the
number of input vehicles of $50$ is $69.9\,s$, whereas those in iDFST and MCC
are $46.2\,s$ and $46.05\,s$, respectively. The two proposed algorithms save
approximately $33\%$ of the evacuation time because of the improved scheduling
method. Similar results are observed in the ATTD in Fig. 9(b), where iDFST and
MCC save approximately $18\%$ of the ATTD for $50$ input vehicles. Although
the MCC method prioritizes the overall efficiency, i.e., the evacuation time
in the scheduling, the re-ordering of the cliques minimizes the ATTD (line 8
in the MCC algorithm). In other words, the MCC method heuristically finds the
MCC groups to minimize the evacuation time. Then, it obtains a spanning tree
from the MCC groups to minimize the ATTD. This also helps to interpret the
outstanding fuel consumption performance of the MCC, as shown in Fig. 9(c).
Better scheduling also helps to avoid the deceleration and idling of the CAVs
in the control zone. iDFST and MCC saves $20\%$ and $27\%$ of the fuel
consumption, respectively, for $50$ input vehicles.

###  4.5 Simulation Results at Various Traffic Volumes

(a) Evacuation time (b) Average travel time delay (c) Fuel consumption

Figure 10: Comparison of traffic efficiency and fuel consumption of three
algorithms for various vehicle volumes. Ten repetitions of the simulation were
conducted for each vehicle volume number. The red lines are the median values
and the triangles are the average values. MCC shows better performance than
the other two algorithms, especially when the intersection is rather crowded,
i.e., $\lambda<3$.

The previous simulations were conducted with $\lambda=3$, i.e., a constant
Poisson distribution. In the last simulation, we examined the influence of the
traffic volume on the algorithm performance. Because the vehicle arrival
follows the Poisson distribution as shown in (23), we varied the $\lambda$
value to change the traffic volumes on each lane. As before, $10$ repetitions
of the simulation were conducted for each number of vehicles, and the vehicle
arrivals were identical across the three algorithms. The simulation results
are plotted in Fig 10.

$\lambda$ is the expected value of the Poisson distribution, which represents
the average gap in the vehicle arrival time on each lane. As shown in Fig.
10(a), the evacuation times obtained with the three algorithms show limited
fluctuations with increase in $\lambda$. The proposed two algorithms, i.e.,
iDFST and MCC, reduce the evacuation time obtained with DFST by approximately
$30\%$. Note that MCC has better performance when $\lambda<3$. Recall that in
Table 4, we designed the car following distance of the virtual platoon as
$D_{\mathrm{des}}=30\,m$ and the speed of the virtual leading vehicle as
$v_{0}=10\,m/s$. Thus, the theoretical vehicle output of the intersection is
bounded as ${D_{\mathrm{des}}}/{v_{0}}=3\,s$ per layer. In other words, if the
average input vehicle gap $\lambda<3$, the accumulation and queuing of the
vehicles is inevitable. Under this circumstance, MCC shows better performance
than iDFST because of its better usage of the intersection space. Fig. 10(b)
shows the ATTD performance of the algorithms. As the traffic volume increases,
the vehicle is more likely to be stuck behind other preceding vehicles. Thus,
the vehicle travel time is positively correlated with the traffic volume,
i.e., the ATTD decreases as the vehicle arrival gap increases. Similar to the
evacuation time, MCC shows better performance when $\lambda<3$. Because of the
abovementioned reason for the MCC to show better utilization of the
intersection space, idling behavior and fuel consumption performance are
greatly improved. As shown in Fig. 10(c), iDFST saves at most $15\%$ and MCC
saves $26\%$ of the fuel consumption when compared with DFST.

##  5 Conclusion

In this paper, a graph-based cooperation method was proposed to formulate the
conflict-free scheduling problem at unsignalized intersections. Based on the
graphical description of the conflict relationships among the CAVs, an iDFST
method was introduced to obtain the local optimal solution. After concise and
rigid graphical analysis, we reduced the CAV scheduling problem to the MCC
problem, which yielded the global optimal solution. Because the MCC problem
was proven to be an NP-hard problem, a heuristic method was also proposed to
solve this problem with low computation complexity in the case of large number
of vehicles. Furthermore, a distributed control framework and communication
topology were designed to realize the conflict-free cooperation of the
vehicles. Traffic simulations proved the effectiveness of the proposed
algorithms.

A future direction of our research is to permit the lane-changing behavior,
i.e., the CAVs are allowed to change lanes while approaching the intersection.
Several practical methods [38, 39] have been proposed to apply the lane
changing behavior of multiple CAVs. It is interesting to combine these works
to further extend the intersection scenario, which will be considered in our
future research. Another interesting topic is the communication topology of
the virtual platoon. In this study, we designed a PLF communication topology
to realize the scheduling plan. The problem of identifying the best topology
is yet to be addressed. Finally, field experiments are needed for further
validation of the proposed algorithm.

## Acknowledgments

This work was supported by the National Key Research and Development Program
of China under Grant
2018YFE0204302, National Natural Science Foundation of China under Grant
52072212, Key Algorithms in Intelligent and Connected Cloud Control System for
China Intelligent and Connected Vehicles Research Institute (CICV), and
Tsinghua University-Didi Joint Research Center for Future Mobility.

## References

  * Xu et al. [2021] Q. Xu, M. Cai, K. Li, B. Xu, J. Wang, X. Wu,  Coordinated formation control for intelligent and connected vehicles in multiple traffic scenarios,  IET Intelligent Transport Systems 15 (2021) 159–173.
  * Azimi et al. [2014] R. Azimi, G. Bhatia, R. R. Rajkumar, P. Mudalige,  Stip: Spatio-temporal intersection protocols for autonomous vehicles,  in: 2014 ACM/IEEE international conference on cyber-physical systems (ICCPS), IEEE, 2014, pp. 1–12.
  * Contreras-Castillo et al. [2017] J. Contreras-Castillo, S. Zeadally, J. A. Guerrero-Ibañez,  Internet of vehicles: architecture, protocols, and security,  IEEE Internet of Things Journal 5 (2017) 3701–3709.
  * Zheng et al. [2020] Y. Zheng, J. Wang, K. Li,  Smoothing traffic flow via control of autonomous vehicles,  IEEE Internet of Things Journal 7 (2020) 3882–3896.
  * Chen et al. [2021] C. Chen, J. Wang, Q. Xu, J. Wang, K. Li,  Mixed platoon control of automated and human-driven vehicles at a signalized intersection: dynamical analysis and optimal control,  Transportation Research Part C: Emerging Technologies 127 (2021) 103138\.
  * Xu et al. [2017] B. Xu, X. J. Ban, Y. Bian, J. Wang, K. Li,  V2I based cooperation between traffic signal and approaching automated vehicles,  in: 2017 IEEE Intelligent Vehicles Symposium (IV), IEEE, California, USA, 2017, pp. 1658–1664.
  * Milanés et al. [2010] V. Milanés, J. Pérez, E. Onieva, C. González,  Controller for urban intersections based on wireless communications and fuzzy logic,  IEEE Transactions on Intelligent Transportation Systems 11 (2010) 243–248.
  * Onieva et al. [2012] E. Onieva, V. Milanés, J. Villagra, J. Pérez, J. Godoy,  Genetic optimization of a vehicle fuzzy decision system for intersections,  Expert Systems with Applications 39 (2012) 13148–13157.
  * Zheng et al. [2017] Y. Zheng, L. Jin, Y. Jiang, F. Wang, X. Guan, S. Ji, J. Xu,  Research on cooperative vehicle intersection control scheme without using traffic lights under the connected vehicles environment,  Advances in Mechanical Engineering 9 (2017) 1687814017719219.
  * He et al. [2015] X. He, H. X. Liu, X. Liu,  Optimal vehicle speed trajectory on a signalized arterial with consideration of queue,  Transportation Research Part C: Emerging Technologies 61 (2015) 106–120.
  * Malikopoulos et al. [2018] A. A. Malikopoulos, C. G. Cassandras, Y. J. Zhang,  A decentralized energy-optimal control framework for connected automated vehicles at signal-free intersections,  Automatica 93 (2018) 244–256.
  * Zhang et al. [2017] Y. Zhang, A. A. Malikopoulos, C. G. Cassandras,  Decentralized optimal control for connected automated vehicles at intersections including left and right turns,  in: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), IEEE, Melbourne, Australia, 2017, pp. 4428–4433.
  * Xu et al. [2018] B. Xu, S. E. Li, Y. Bian, S. Li, X. J. Ban, J. Wang, K. Li,  Distributed conflict-free cooperation for multiple connected vehicles at unsignalized intersections,  Transportation Research Part C: Emerging Technologies 93 (2018) 322–334.
  * Zheng et al. [2015] Y. Zheng, S. E. Li, K. Li, L.-Y. Wang,  Stability margin improvement of vehicular platoon considering undirected topology and asymmetric control,  IEEE Transactions on Control Systems Technology 24 (2015) 1253–1265.
  * Li and Wang [2006] L. Li, F.-Y. Wang,  Cooperative driving at blind crossings using intervehicle communication,  IEEE Transactions on Vehicular technology 55 (2006) 1712–1724.
  * Meng et al. [2017] Y. Meng, L. Li, F.-Y. Wang, K. Li, Z. Li,  Analysis of cooperative driving strategies for nonsignalized intersections,  IEEE Transactions on Vehicular Technology 67 (2017) 2900–2911.
  * Dresner and Stone [2004] K. Dresner, P. Stone,  Multiagent traffic management: A reservation-based intersection control mechanism,  in: Autonomous Agents and Multiagent Systems, International Joint Conference on, volume 3, IEEE Computer Society, 2004, pp. 530–537.
  * Dresner and Stone [2008] K. Dresner, P. Stone,  A multiagent approach to autonomous intersection management,  Journal of artificial intelligence research 31 (2008) 591–656.
  * Tachet et al. [2016] R. Tachet, P. Santi, S. Sobolevsky, L. I. Reyes-Castro, E. Frazzoli, D. Helbing, C. Ratti,  Revisiting street intersections using slot-based systems,  PloS one 11 (2016) e0149607.
  * Xu et al. [2019] H. Xu, Y. Zhang, L. Li, W. Li,  Cooperative driving at unsignalized intersections using tree search,  IEEE Transactions on Intelligent Transportation Systems 21 (2019) 4563–4571.
  * Yan et al. [2009] F. Yan, M. Dridi, A. El Moudni,  Autonomous vehicle sequencing algorithm at isolated intersections,  in: 2009 12th International IEEE conference on intelligent transportation systems, IEEE, 2009, pp. 1–6.
  * Pandit et al. [2013] K. Pandit, D. Ghosal, H. M. Zhang, C.-N. Chuah,  Adaptive traffic signal control with vehicular ad hoc networks,  IEEE Transactions on Vehicular Technology 62 (2013) 1459–1471.
  * Dey and Pal [2013] A. Dey, A. Pal,  Fuzzy graph coloring technique to classify the accidental zone of a traffic control,  Annals of Pure and Applied Mathematics 3 (2013) 169–178.
  * Lin et al. [2019] Y.-T. Lin, H. Hsu, S.-C. Lin, C.-W. Lin, I. H.-R. Jiang, C. Liu,  Graph-based modeling, scheduling, and verification for intersection management of intelligent vehicles,  ACM Transactions on Embedded Computing Systems (TECS) 18 (2019) 1–21.
  * Deng et al. [2020] Z. Deng, Y. Shi, Q. Han, L. Lv, W. Shen,  A conflict duration graph-based coordination method for connected and automated vehicles at signal-free intersections,  Applied Sciences 10 (2020) 6223.
  * Ahn and Del Vecchio [2017] H. Ahn, D. Del Vecchio,  Safety verification and control for collision avoidance at road intersections,  IEEE Transactions on Automatic Control 63 (2017) 630–642.
  * Ahn and Colombo [2019] H. Ahn, A. Colombo,  Abstraction-based safety verification and control of cooperative vehicles at road intersections,  IEEE Transactions on Automatic Control (2019).
  * Miculescu and Karaman [2019] D. Miculescu, S. Karaman,  Polling-systems-based autonomous vehicle coordination in traffic intersections with no traffic signals,  IEEE Transactions on Automatic Control 65 (2019) 680–694.
  * Gerla et al. [2014] M. Gerla, E.-K. Lee, G. Pau, U. Lee,  Internet of vehicles: From intelligent grid to autonomous cars and vehicular clouds,  in: 2014 IEEE world forum on internet of things (WF-IoT), IEEE, 2014, pp. 241–246.
  * Roess et al. [2004] R. P. Roess, E. S. Prassas, W. R. McShane, Traffic engineering, Pearson/Prentice Hall, 2004.
  * Luce and Perry [1949] R. D. Luce, A. D. Perry,  A method of matrix analysis of group structure,  Psychometrika 14 (1949) 95–116.
  * Karp [1972] R. M. Karp,  Reducibility among combinatorial problems,  in: Complexity of computer computations, Springer, 1972, pp. 85–103.
  * Chen et al. [2021] C. Chen, Q. Xu, M. Cai, J. Wang, B. Xu, X. Wu, J. Wang, K. Li, C. Qi,  A graph-based conflict-free cooperation method for intelligent electric vehicles at unsignalized intersections,  arXiv preprint arXiv:2103.14290 (2021).
  * Garey [1979] M. R. Garey,  A guide to the theory of np-completeness,  Computers and intractability (1979).
  * Zheng et al. [2015] Y. Zheng, S. E. Li, J. Wang, D. Cao, K. Li,  Stability and scalability of homogeneous vehicular platoon: Study on the influence of information flow topologies,  IEEE Transactions on intelligent transportation systems 17 (2015) 14–26.
  * Lopez et al. [2018] P. A. Lopez, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y.-P. Flötteröd, R. Hilbrich, L. Lücken, J. Rummel, P. Wagner, E. Wießner,  Microscopic traffic simulation using sumo,  in: 2018 21st International Conference on Intelligent Transportation Systems (ITSC), IEEE, 2018, pp. 2575–2582.
  * Keller et al. [2010] M. Keller, S. Hausberger, C. Matzer, P. Wüthrich, B. Notter, Handbook of emission factors for road transport (HBEFA) 3.1, Technical Report, quick reference. Technical report, INFRAS, 2010.
  * Cai et al. [2021] M. Cai, C. Chen, J. Wang, Q. Xu, K. Li, J. Wang, X. Wu,  Formation control with lane preference for connected and automated vehicles in multi-lane scenarios,  arXiv preprint arXiv:2106.11763 (2021).
  * Chouhan et al. [2020] A. P. Chouhan, G. Banda, K. Jothibasu,  A cooperative algorithm for lane sorting of autonomous vehicles,  IEEE Access 8 (2020) 88759–88768.