Safe and Efficient Intersection Control of Connected and

arXiv:1801.09361v1 [] 29 Jan 2018

Autonomous Intersection Traffic

A DISSERTATION
Presented to
the Faculty of the Daniel Felix Ritchie School of Engineering and
Computer Science
University of Denver

in Partial Fulfillment
of the Requirements for the Degree
of Doctor of Philosophy

by
Qiang Lu
Januray, 2018
Advisor: Mohammad H. Mahoor
Co-Advisor: Kyoung-Dae Kim

c Copyright by Qiang Lu 2018.
All Rights Reserved

Author: Qiang Lu
Title: Safe and Efficient Intersection Control of Connected and Autonomous Intersection Traffic
Advisor: Mohammad H. Mahoor
Co-Advisor: Kyoung-Dae Kim
Degree Date: Januray, 2018

Abstract

In this dissertation, we address a problem of safe and efficient intersection crossing traffic management of autonomous and connected ground traffic. Toward this
objective, an algorithm that is called the Discrete-time occupancies trajectory based
Intersection traffic Coordination Algorithm (DICA) is proposed. All vehicles in
the system are Connected and Autonomous Vehicles (CAVs) and capable of wireless Vehicle-to-Intersection communication. The main advantage of the proposed
DTOT-based intersection management is that it enables us to utilize the space
within an intersection more efficiently resulting in less delay for vehicles to cross the
intersection. In the proposed framework, an intersection coordinates the motions of
CAVs based on their proposed DTOTs to let them cross the intersection efficiently
while avoiding collisions. In case when there is a collision between vehicles’ DTOTs,
the intersection modifies conflicting DTOTs to avoid the collision and requests CAVs
to approach and cross the intersection according to the modified DTOTs. We then
prove that the basic DICA is deadlock free and also starvation free. We also show
that the basic DICA has a computational complexity of O(n2 L3m ) where n is the
number of vehicles granted to cross an intersection and Lm is the maximum length

ii

of intersection crossing routes. To improve the overall computational efficiency of
the algorithm, the basic DICA is enhanced by several computational approaches.
The enhanced algorithm has the computational complexity of O(n2 Lm log2 Lm ).
Next we addressed the problem of evacuating emergency vehicles as quickly as
possible through autonomous and connected intersection traffic in this dissertation.
The proposed intersection control algorithm Reactive DICA aims to determine an
efficient vehicle-passing sequence which allows the emergency vehicle to cross an
intersection as soon as possible while the travel times of other vehicles are minimally affected. When there are no emergency vehicles within the intersection area,
the vehicles are controlled by DICA. When there are emergency vehicles entering
communication range, we prioritize emergency vehicles through optimal ordering of
vehicles. Since the number of possible vehicle-passing sequences increases rapidly
with the number of vehicles, finding an efficient sequence of vehicles in a short time
is the main challenge of the study. A genetic algorithm is proposed to solve the optimization problem which finds the optimal vehicle sequence that gives the emergency
vehicles the highest priority.
We verify the efficiency of the proposed approaches through simulations using
an open-source traffic simulator, called the Simulation of Urban Mobility (SUMO).
The simulation results show that DICA performs better than another existing intersection management scheme: Concurrent Algorithm in [1]. The overall throughput
as well as the computational efficiency of the computationally enhanced DICA are
also compared with those of an optimized traffic light control. The efficiency of
the proposed Reactive DICA is validated through comparisons with DICA and a
reactive traffic light algorithm. The results show that Reactive DICA is able to
decrease the travel times of emergency vehicles significantly in light and medium
traffic volumes without causing any noticeable performance degradation of normal
vehicles.

iii

Acknowledgements
First of all, I would like to extend my sincere gratitude to my advisor Dr. Mohammad H. Mahoor, and co-advisor Dr. Kyoung-Dae Kim for their instructive advices
and useful suggestions on my thesis. I am deeply grateful of their help in the completion of this thesis. I learned a lot knowledge from their excellent performance in
teaching and research capabilities as well as high motivation and responsibility to
students.
I am also deeply indebted to all the other professors and staff like Dr. Jun Jason
Zhang, Dr. Kimon P. Valavanis, Dr. Amin Khodaei and Molly Dunn, etc. for their
direct and indirect help to me.
Special thanks should go to my friends Huaiguang Jiang, Qiao Li, etc. who have
helped me a lot during my PhD.
Finally, I am indebted to my parents, my sister and my girlfriend for their
continuous support and encouragement.

iv

Contents
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 Introduction
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . .
2 Literature Review
2.1 Control of Highway Systems . . . . . . . . . . . . . . . .
2.1.1 Vehicle Platooning . . . . . . . . . . . . . . . . .
2.1.2 Algorithms and Protocols for Individual Vehicles
2.2 Autonomous Intersection Control . . . . . . . . . . . . .
2.2.1 Centralized Control . . . . . . . . . . . . . . . .
2.2.2 Decentralized Control . . . . . . . . . . . . . . .
2.2.3 Optimization Approaches . . . . . . . . . . . . .
2.2.4 Emergency Vehicle Handling . . . . . . . . . . .

1
1
7

.
.
.
.
.
.
.
.

8
8
9
9
11
11
12
14
15

.
.
.
.
.
.
.
.
.
.
.

16
16
18
20
23
24
26
27
30
30
32
34

4 Computational Complexity Improvements of DICA
4.1 Computational Complexity Analysis . . . . . . . . . . . . . . . . . .
4.2 Algorithm Improvements . . . . . . . . . . . . . . . . . . . . . . . . .

36
36
41

3 DTOT-based Intersection Traffic Management
3.1 Assumptions . . . . . . . . . . . . . . . . . . . .
3.2 Interaction between ICA and a CAV . . . . . . .
3.3 DTOT-based Intersection Traffic Coordination .
3.3.1 Collision Avoidance with Front Vehicles .
3.3.2 Vehicles for Collision Avoidance . . . . .
3.3.3 DTOT Update . . . . . . . . . . . . . . .
3.4 Liveness Analysis . . . . . . . . . . . . . . . . . .
3.5 Simulation . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Simulation Setup . . . . . . . . . . . . . .
3.5.2 Simulation Results . . . . . . . . . . . . .
3.6 Summary . . . . . . . . . . . . . . . . . . . . . .

v

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

4.3

4.4

4.2.1 Reduced Number of Vehicles for Space-Time Conflict Check
4.2.2 Efficient Space Conflict Check . . . . . . . . . . . . . . . . .
4.2.3 Approximate Occupancy Time Interval Calculation . . . . .
4.2.4 Efficient Occupancies Comparison . . . . . . . . . . . . . .
Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . .
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.

41
42
42
44
47
47
50
58

5 Reactive DICA: an Approach for Expedited Crossing of Emergency
Vehicles
5.1 Reactive DICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Genetic Algorithm for Vehicle Ordering . . . . . . . . . . . . . . . .
5.2.1 Chromosome Encoding and Feasibility Check . . . . . . . . .
5.2.2 Crossover and Mutation . . . . . . . . . . . . . . . . . . . . .
5.2.3 Fitness and Generating New Generation . . . . . . . . . . . .
5.2.4 Stopping Criterion . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Reactive Traffic Light . . . . . . . . . . . . . . . . . . . . . .
5.3.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59
59
64
67
69
70
71
71
71
74
74
79

6 Conclusion and Future Work
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80
80
81

References

83

vi

List of Tables
3.1

Simulation results comparison. . . . . . . . . . . . . . . . . . . . . .

4.1

Parameters used for various traffic volumes and patterns. (∗ Expected
number of vehicles per 10 minutes.) . . . . . . . . . . . . . . . . . . .

4.2

52

Average trip time comparison between major roads and minor roads
in an unbalanced traffic . . . . . . . . . . . . . . . . . . . . . . . . .

5.1

49

Computation time comparison between enhanced DICA and optimized traffic light . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3

31

53

Parameters used for various traffic volumes and patterns. (∗ Expected
number of vehicles per 10 minutes.) . . . . . . . . . . . . . . . . . . .

73

5.2

Computation time comparison between ES and GA . . . . . . . . . .

76

5.3

Comparison of maximum trip times of normal vehicles between DICA
and R-DICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

79

List of Figures
3.1

DTOTs of two conflicting vehicles . . . . . . . . . . . . . . . . . . .

17

3.2

Interaction between a CAV and ICA. . . . . . . . . . . . . . . . . . .

19

3.3

Example situations of front vehicles

23

3.4

A screenshot of simulation which illustrates a situation when vehicles

. . . . . . . . . . . . . . . . . .

with conflicting routes cross the intersection simultaneously. . . . . .

32

3.5

The histogram of Trip Times of crossed vehicles in a simulation. . .

34

3.6

Comparison of Trip Times of 3 different cases between DICA and
Concurrent Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1

Two different cases for shortest intersection crossing time (Tm ) calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2

34

40

Approximate occupancy time interval calculation for a vehicle with
through route.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.3

Computation times comparison . . . . . . . . . . . . . . . . . . . . .

50

4.4

The number of vehicles which wait to cross the intersection over time. 53

4.5

Histogram of the inter-vehicle distance within the intersection. . . .

viii

54

4.6

Performance comparison between enhanced DICA and optimized traffic light . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4.7

Flow rate ratio when traffic volume changes from 100 to 500. . . . .

57

5.1

Three different situations for separation time. . . . . . . . . . . . . .

61

5.2

Control flow diagram of ICA in R-DICA. . . . . . . . . . . . . . . .

65

5.3

An example of the permutation encoding scheme, the left-most vehicle
has the highest priority while the right-most one has the lowest priority. 67

5.4

Example situation of vehicles whose sequence to be optimized in intersection space, note: vehicles on EV’s lane are: v 1 , v 3 , EV . . . . .

5.5

68

An example of one-point crossover. Relative ordering of parents is
preserved when the chromosomes are adjusted due to the existence
of same bits. Feasibility is checked for the two children based on
vehicles’ sequence on EV’s lane and adjustments are made. . . . . .

5.6

70

An example of mutation. Feasibility is checked for the mutated chromosome based on vehicles’ sequence on EV’s lane and adjustment is
made. v 2 and EV are randomly chosen to swap to perform mutation.
EV is swapped with v 3 to conform vehicles’ sequence on EV’s lane. .

70

5.7

Reactive traffic light diagram. . . . . . . . . . . . . . . . . . . . . . .

73

5.8

A series of screenshots of simulation . . . . . . . . . . . . . . . . . .

75

5.9

Performance comparison of EVs . . . . . . . . . . . . . . . . . . . . .

77

5.10 Performance comparison of normal vehicles . . . . . . . . . . . . . .

78

ix

Chapter 1

Introduction
1.1

Introduction

Recent years, due to the rapidly increasing demand for transportation from the
larger and larger population, roads have become more and more congested. Careful
city planning can usually alleviate such transportation problems, but the unexpected growth of population and vehicle usage leads to persistent congestions. As
efficient ways to address congestion problems, self-driving vehicles and autonomous
transportation systems have attracted a lot of research and development efforts from
academia, industry, and government. For example, during the mid-1990s the California PATH (Partners for Advanced Transportation Technology) launched the Automated Highway System (AHS) program [2] and the US DARPA (Defense Advanced
Research Projects Agency) held a series of autonomous vehicle challenges during
the 2000s [3] to take advantages in sensing and computation technologies. Also,
many companies have already made decisions to hugely invest in developing their
own self-driving vehicles or vehicles with advanced driving assistance systems [4].
However, despite many recent successful road testing results of several self-driving
cars such as Google driverless car [5], it is hard to argue that the overall system-wide

1

traffic safety, as well as throughput, will be improved substantially when we have
a few Connected and Autonomous Vehicles (CAVs) among all other conventional
vehicles. In fact, the potential of autonomous vehicles in terms of the traffic efficiency and safety will be unleashed when most cars on roads are autonomous and
connected [6]. Thus, in addition to many efforts to make today’s traffic more efficient by improving utilization of traditional traffic infrastructure such as the work
presented in [7], we believe that it is also very important to develop traffic control algorithms that take advantages of connectivity and autonomy of autonomous
vehicles to prepare for the next generation transportation system. However, while
there have been many efforts toward this direction, the development of safe and
efficient autonomous transportation systems is still at its early stage. In this paper,
among many research problems like vehicle path planning [8], autonomous parking
control [9], collision avoidance [10, 11], relation between occupant experience and
intersection capacity [12], intersection management of mixed traffic [13], traffic coordination with power [14], etc. that should be addressed toward this objective,
we are particularly interested in addressing a problem of safe and efficient intersection crossing traffic management of autonomous connected traffic. Compared with
highways, road intersections are more complicated places where accidents are more
likely to happen and become the bottleneck of traffic performance improvement.
In literature, there are a number of notable results for autonomous intersection
crossing traffic management. In reference [15], a scheme that consists of a time-slot
allocation intersection crossing algorithm, and an algorithm for updating failsafe
maneuvers of each vehicle so as to avoid collisions while crossing an intersection
was proposed. In [16], Lee et al. proposed an algorithm, called the Cooperative
Vehicle Intersection Control (CVIC), which manipulates every individual vehicle’s
driving motion by providing them proper acceleration or deceleration rate so that
vehicles can cross the intersection safely. Wu et al. [17] introduced a new intersection

2

traffic management framework that is formulated as a combinatorial optimization
problem and solved the problem approximately using the ant colony system algorithm [18]. Fei Yan et al. [19] combined vehicles whose routes are compatible with
each other into mini groups and obtained an efficient vehicle passing sequence by
their proposed genetic algorithm. A nonlinear programming formulation for autonomous intersection control was developed in [20] where the nonlinear constraints
were relaxed by a set of linear inequalities. Kyoung-Dae Kim and P.R. Kumar [1]
developed a Model Predictive Control (MPC) framework which dynamically generates a sequence of collision-free motions. Their paper considered two algorithms, a
simple First In First Out (FIFO) Crossing algorithm and a Concurrent Algorithm,
and shown the corresponding system-wide safety and crossing traffic liveness. A
polling-systems-based algorithm was proposed in [21] with provable guarantees on
safety and performance. In the algorithm, a rigorous upper bound is provided for
the expected wait time. Most of them are centralized approaches in which control
decisions are made typically by a central agent. Decentralized intersection control
approaches have also been proposed in literature. For example, [22] formulated
a decentralized framework whereby each autonomous vehicle minimizes its energy
consumption under the throughput-maximizing timing constraints and hard safety
constraints to avoid rear-end and lateral collisions. A complete analytical solution
of the decentralized problems was presented in the paper. These approaches are
similar in that they all ensure safety within an intersection by preventing vehicles
with conflicting intersection crossing routes from being inside the intersection at the
same time.
To further improve the overall intersection control performance, some researchers
studied algorithms that allow conflicting vehicles exist inside an intersection simultaneously. To achieve this objective, most approaches discretized the intersection
space into grid cells so that vehicles of conflicting routes can exist at the same

3

time within an intersection but not within a same cell. Kurt Dresner and Peter
Stone [23] presented a reservation-based approach Autonomous Intersection Management (AIM) which treats vehicles and intersections as autonomous agents in a
multiagent system. In AIM, vehicles request and receive time slots from the intersection during which they may pass. However, no global coordination is made for
crossing vehicles to obtain optimal traffic flow. Following AIM, similar researches
and improved approaches were proposed like expediting the crossing of emergency
vehicles [24], determining the priority of requests using auctions [25, 26], etc. To
improve previous AIM models, Levin et al. [27] studied the approach to choose the
optimal subset of vehicles to move at every time step by formulating an Integer
Program (IP). Arbitrary objective functions can be admitted by the IP so a more
general class of policies can be applied to optimize the order of vehicles to cross
the intersection. Representative centralized approaches also include auction-based
intersection managements proposed in [25, 26]. A series of decentralized approaches
only based on vehicle-to-vehicle (V2V) communications were proposed in [28–31]
by Reza Azimi et al. In their papers, the intersection area is considered as a grid
which is divided into small cells. Each cell in the intersection grid is associated with
a unique identifier. One of their advanced intersection protocols named AMP-IP
(Advanced Maximum Progression Intersection Protocol) allows the lower-priority
vehicle to go ahead and cross the conflicting cell before the arrival of the higherpriority vehicle if there is enough time for lower-priority vehicle to clear the cell.
Roughly speaking, these approaches are all based on the grid cell partitioning of an
intersection space. In [23], the effect of the grid cell granularity on the computational efficiency of an intersection traffic management framework such as AIM was
studied. Clearly, higher granularity gives more flexibility for better traffic throughput. However, the computational complexity increases proportionally to the square
of the granularity. On the other hand, when the cell size becomes large for better

4

computational efficiency, one can see that the intersection space is not utilized efficiently resulting in lower traffic throughput. Therefore, to overcome this trade-off
issue between the granularity and computational efficiency of an algorithm, it might
be a good alternative approach to utilize each vehicle’s actual occupancy instead
of grid cells to improve the overall traffic throughput. And this has motivated our
research on this topic.
As an approach to address the above-mentioned granularity issue, we propose
a novel intersection traffic management scheme based on the idea of the DiscreteTime Occupancies Trajectory (DTOT). Conceptually, a DTOT is a discrete-time
sequence of a vehicle’s actual occupancy within an intersection space. The proposed
DTOT-based Intersection Control Algorithm (DICA) allows the flexibility that each
vehicle can choose its path as well as motions along the path that a CAV wants to
take to cross an intersection. A CAV who is approaching an intersection will check
whether it is the Head Vehicle on its lane. If it is, the CAV will propose its request
to the intersection. From the request, a vehicle’s enter time and exit time to the
intersection, route and other detailed information of passing the intersection can
be found. Then the intersection responds with a DTOT to the vehicle to avoid
collisions and improve the overall intersection throughput. The DTOT corresponds
to a trajectory with achievable speed and acceleration for the CAV. If the CAV is
not the Head Vehicle, it will just follow other cars. Thus, the management scheme is
only dealing with head vehicles which reduces largely the communication needs for
vehicles and the computational complexity of the central control agent. It is assumed
that a CAV always want to go through an intersection as quickly as possible. So
CAVs in our algorithm always try their best to reach maximum allowed speed within
the intersection.
Then, we provide an in-depth analysis of the original DTOT-based Intersection
Coordination Algorithm (DICA) to show that it satisfies the liveness property in

5

terms of deadlock as well as starvation issues and also to derive the overall computational complexity of the algorithm. Another contribution is that we propose
several computational approaches to improve the overall computational efficiency of
the DICA and also enhance the algorithm accordingly so that it can be operated in
real-time for autonomous and connected intersection crossing traffic management.
We also present simulation results that show the improved computational efficiency
of the enhanced algorithm and the overall throughput performance in comparison
with that of an optimized traffic light control.
Human lives and the amount of financial loss highly depend on the response
time (from the time the emergency service is called to the time help is offered) of
emergency vehicles. The travel time of emergency vehicles to the accident scene is
critical to the response time. So it is very useful and helpful to reduce travel time
of emergency vehicles on roads, especially on intersections where congestions are
more likely to happen. The survival chance of injured people in an accident falls
sharply if they reach the operating table later than 60 minutes after the accident [32].
Hence, shortening the travel times of crossing intersections for emergency vehicles
will help to save lives. In reality, the current way to handle emergency vehicles is
similar to using Vehicle-to-Vehicle (V2V) communication (siren and lights) to warn
non-emergency vehicles on roads to yield to the emergency vehicle. Some drivers
cannot respond quickly to the warnings which may result in additional time delay
for emergency vehicles and even serious accidents. In most of existing approches
[24,33,34] for emergency vehicles, the travel times of non-emergency vehicles will be
affected significantly and the advantages of autonomous vehicles are not fully taken.
Following computationally enhancing DICA, we extend DICA approach to include emergency vehicles in the traffic to be controlled. Our goal of intersection
control is to let emergency vehicles cross intersections as fast as possible while maintaining adequate traffic performance. In this dissertation, we assume that emergency

6

vehicles are taking normal routes which means that they will not travel in a wrong
lane. A genetic algorithm is proposed to find the optimal passing sequence of vehicles whose trajectories can be rearranged. This optimal sequence aims to make
the emergency vehicles cross the intersection in the fastest way. When there is no
emergency vehicle inside the communication region, vehicles are controlled by DICA.
Thus, the proposed algorithm is called Reactive DICA. Among many sequence forming approaches [19, 25, 35, 36] in literature, [19] is the most similar approach with
ours which also proposed a genetic algorithm to form vehicle sequences. However,
unlike the approach proposed in this dissertation, they are essentially not allowing
vehicles with conflicting routes to be inside the intersection at the same time.

1.2

Organization of the Dissertation

The remainder of this dissertation is organized into five chapters. In Chapter 2,
we review literature on autonomous transportation especially on autonomous intersection control. In Chapter 3, we introduce the assumptions and interactions
between vehicle and intersection in DICA. Then we explain the functions in DICA
in detail and analyze the liveness of DICA. Finally, DICA is simulated and compared with Concurrent Algorithm [1] to validate its performance. In Chapter 4, we
analyze the computational complexity of DICA in detail first and then proposed
several computational techniques to improve overall computational efficiency. The
improved performance is validated through comparisons with original DICA and
an optimized traffic light control algorithm. Chapter 5 describes Reactive DICA
especially the proposed genetic algorithm in detail. Simulation results of Reactive
DICA are compared with a reactive traffic light algorithm to show its performance.
Finally, Chapter 6 draws the conclusion of the dissertation and provides potential
future work.

7

Chapter 2

Literature Review
2.1

Control of Highway Systems

Highway congestion has brought intolerable burdens to many urban residents. Governments have made many attempts including building more roads and raising tolls
or other related taxes, promoting public transportation or better vehicle occupany
(carpooling) and developing a high-speed communications network that in many
ways to reduce travel demand [37]. In the meantime, researches of Intelligent Vehicle/Highway System (IVHS) provide new ways to ease the congestion on highways.
There are mainly two types of methods to increase highway capacity while ensure
safety, 1. vehicle platooning, represented by the AHS which had been deeply developed at the University of California Partners for PATH program, in cooperation
with the State of California Department of Transportation (Caltrans) and the United
States Federal Highway Administration (FHWA) since 1989 [2, 37]. 2. algorithms
and protocols for each individual vehicle to drive fast and safely, represented by
references [38, 39].

8

2.1.1

Vehicle Platooning

Organizing traffic into platoons which are groups of up to 20 tightly spaced cars
can increase highway capactiy greatly. 8000 vehicles per hour per lane could be
achieved while today’s highways with manually controlled vehicles only have 2000
capacity [2]. Platooning also has a benefit of reducing aerodynamic drag because
vehicles are tightly spaced. People cannot react quickly enough to drive safely with
such small headways, so every vehicle in a platoon should be automated. A car
joins a platoon when it enters the AHS and exits as a one-car platoon or part of an
exiting platoon when it approaches its destination. Inside AHS, the car is controlled
automatically by computers and a series of maneuvers [37] are executed by the car
including splitting from and joining platoons and lane changing to navigate through
the highway network.
Reference [37] introduces the finite state machine method which is used for the
execution of maneuvers. Join control law, platoon leader control law and other laws
are given in [2] to ensure collision avoidance of AHS. What is noteworthy is that
the on-board vehicle control system is a hybrid control system which consists of
a discrete event dynamical system (the coordination layer) and a continuous-time
dynamical system (the regulation and physical layers).
The platoon concept is useful but does not take full advantage of the microscope
centralized possibilities because it does not consider the interaction of all vehicles
[39]. In a platoon, only leaders (and free agents) can initiate maneuvers, while
followers maintain platoon formation at all times [2].

2.1.2

Algorithms and Protocols for Individual Vehicles

For an individual autonomous vehicle, many algorithms and protocols have been
proposed for its longitudinal and lateral motion on a highway system while the
vehicle’s safety is ensured.
9

Longitudinal Control
The longitudinal control of a vehicle is to control the vehicle’s speed and its adaptation to road features by adjusting the throttle [40] and the brake pedal as needed [41].
A longitudinal control system will handle issues like nonlinear vehicle dynamics,
operations of vehicles from high-speed cruising to a complete full-stop, and other
operations under the communication constraints [42]. Following we describe several
different controllers that are designed to ensure safety of longitudinal motion of each
vehicle.
Reference [15] gives the theorem for perpetual safety of two cars on a lane that if
each car makes worst-case assumption about the car immediately in front of it, then
the safety of multiple cars on a lane can be guaranteed. Reference [43] uses a simple
discrete-time kinematic model to represent the longitudinal motion of a vehicle,
xt+h = f (xt , vt ) = xt + vt h, where xt , vt , h correspond to x-axis (forward direction)
position, linear velocity of a vehicle at time t, and sampling period respectively.
The paper formulated an MPC problem for the vehicle to ensure the generation of
safety-guaranteed motions.

Lateral Control
Typically lane changing provides a maneuver for a fast vehicle to pass a slow vehicle,
which can be observed everywhere on the highway [44]. A framework of lane change
decision-making under typical urban driving conditions was proposed by Gipps [45],
which includes the effects of traffic lights, obstacles and types of surrounding vehicles.
Taking into account the potential conflict objectives and assuming logical driver
behavior, the model focuses on the decision-making process.
Reference [43] constructs the MPC problem for Lane Change of a vehicle on a
multi-lane traffic and introduces the Lane Change Protocol that a vehicle can initiate
its lane change action only when its state satisfies certain relations with neighboring
10

vehicles. The paper also proposes the Yield Protocol which is incorporated into
the MPC motion planning framework to ensure the liveness of Lane Change. A
novel MPC-based approach for active steering control design is presented in [38].
Experimental results showed that a vehicle under MPC feedback policy is capable
of stabilizing with a speed up to 21 m/s on slippery surfaces such as snow covered
or icy roads. The paper designed and experimentally tested three types of MPC
controllers including a nonlinear MPC, an LTV MPC, and an LTV MPC controller
of low order.

2.2

Autonomous Intersection Control

Intersection traffic control is more of importance since it is more likely to have
accidents at intersections compared with highways. Besides accidents, the trip delays
from the impact of intersections also lead to waste of human and natural resources.
To tackle intersection control problems, many solutions have been proposed in the
literature. The main problem is to provide an intersection control algorithm with
guaranteed safety and improved efficiency.

2.2.1

Centralized Control

Kyoung-Dae Kim [43] proposes a framework for intersection management that integrates decisions made by the intersection in the discrete domain for vehicle ordering with decisions made by each vehicle in the continuous domain for its safetyguaranteed motion. The proposed intersection control algorithms (FIFO and Concurrent Algorithm) and protocols ensure that the intersection is safe and live.
Reference [15] designs smart intersections where vehicles negotiate the intersection crossings through an interaction of centralized and distributed decision making.
The route that was taken by a car i is described by an ordered pair R(i)=(O(i),D(i)),
of origin and destination, respectively. A scheme is proposed that consists of a time11

slot allocation intersection crossing algorithm, and an algorithm for updating failsafe
maneuvers of each vehicle so as to avoid collisions while crossing an intersection.
An interesting result about collision avoidance at intersection is shown in [11],
that it is an NP-hard problem to check the membership in the maximal controlled
invariant set, which is the largest set of states for which there exists a control that
avoids collisions. An algorithm with provable error bounds is proposed to solve
such a problem approximately in polynomial running time. The paper provides and
proves a tight bound on the approximated solution.
The most existing evasion plans are not dealt with the vehicles already in the
intersection which suddenly stops because of tire blowout or other mechanical failures. [46] provides appropriate plans for such situations. According to the width of
the intersection, two ways to avoid collisions are offered for the vehicles in intersection. And the paper proves the validity of the methods by empirical study.

2.2.2

Decentralized Control

Since 2011, researcher Reza Azimi has proposed a series of reliable intersection protocols that use only vehicle-to-vehicle (V2V) communications. The installation of a
centralized infrastructure at each intersection is impractical due to the high overall
system cost. Azimi advocates the use of V2V communications and distributed intersection algorithms that runs in each vehicle. He designed the vehicular network protocols that integrate mobile wireless communications standards such as Dedicated
Short Range Communications (DSRC) and Wireless Access in a Vehicular Environment (WAVE). Collision Detection Algorithm for Intersections (CDAI) which uses
a priority-based policy, Stop-Sign Protocol (SSP), Throughput Enhancement Protocol (TEP) and Throughput Enhancement Protocol with Agreement (TEPA) are
proposed in [28]. SSP is similar to actual stop-sign situation that every vehicle must
stop before an intersection when there is a stop-sign. Using TEP, vehicles stop at

12

the intersection only if the CDAI predicts a collision and assigns a lower priority to
them based on the message it receives from all vehicles at the intersection. TEPA
is built on TEP and is explicitly designed to handle lost V2V messages.
In [29], Azimi et al. define an intersection as a perfect square box that pre-defines
the entry and exit points for each lane to which it is connected. The intersection
area is discretized as grid cells and each cell is associated with a unique identifier.
More advanced protocols CC-IP (Concurrent Crossing-Intersection Protocol) and
MP-IP (Maximum Progression-Intersection Protocol) which are improved from [28]
are proposed. In CC-IP, CROSS message is broadcasted when a vehicle enters the
intersection area, other vehicles can simultaneously pass through the intersection if
they detect no potential collision with the vehicle already crossing the intersection,
otherwise the vehicle stop before the intersection area. However, in MP-IP, the
vehicle which has the lower priority uses CDAI and finds out the first common cell
(trajectory intersecting cell, abbreviated as TIC) with the crossing higher-priority
vehicle. Then, instead of not entering the intersection as in CC-IP, the vehicle stops
at the cell just before entering the TIC.
Reference [30] illustrates more advanced protocols about intersection using vehicular networks based on the work of [28, 29]. After detailed describing of MP-IP
and AMP-IP (Advanced Maximum Progression Intersection Protocol), the paper
proves that these protocols avoid deadlock situations inside the intersection area.
The improvement of AMP-IP is that, the protocol allows lower priority vehicles to
advance and cross the conflicting cell before the higher priority vehicle arrives. A
Safety Time Interval of 2s is used to help lower-priority vehicles decide whether
they can go through the conflicting cell safely. Simulation results show that the
latest V2V intersection protocol AMP-IP yields over 85% overall performance improvement over the common traffic light models. In [47], Azimi also investigates the
use of their proposed V2V-intersection protocols for autonomous driving at round-

13

abouts. The improvement in safety and throughput when the intersection protocols
are used to traverse roundabouts is also quantified.

2.2.3

Optimization Approaches

Machine learning is an emerging aspect in traffic management and control, which
also show its capability in different areas such as power system [48, 49], medical
science [50], renewable energy [51–61]. Similarly, considering the optimization, the
convex optimization also illustrate its capability in different areas [62–66].
In recent years, many researches have been done to improve intersection control
performance by using optimization approaches. Reference [20] developed a novel
linear programming formulation for autonomous intersection control in which the
nonlinear constraints were relaxed by a set of linear inequalities. While the objective function of the optimization problem in [20] involves the travel time, other
studies [67, 68] are trying to solve similar control problem using an objective function with multiple criteria like safe speeds and accelerations while avoiding collisions.
Compared with centralized control approaches, infrastructure support is not needed
in decentralized control. In the approach [69] proposed by Wu et al., the estimated
arrival time is shared wirelessly among vehicles to obtain the best passing sequence.
The problem of coordinating online a continuous flow of connected and autonomous
vehicles crossing two adjacent intersections was formulated as a decentralized optimal control problem in [70]. The solution gives the optimal acceleration/deceleration
for each vehicle at any time to minimize fuel consumption. Some researchers also
studied the control mechanism when there is only part of the traffic are autonomous
vehicles [71].

14

2.2.4

Emergency Vehicle Handling

Many studies have been done to allow emergency vehicles to have a faster travel
across intersections. Based on MAS (Multi-Agent System), [33] introduced a state
machine for the intersection controller to change traffic signal status according to
lane occupation when an emergency vehicle is approaching. Some researchers have
explored the priority evacuation of emergency vehicles under an autonomous and
connected traffic environment. Wantanee Viriyasitavat and Ozan K. Tonguz proposed an intersection control system that only uses Vehicle-to-Vehicle (V2V) communication to give emergency vehicles priority of crossing [34]. The paper proposed
that at an intersection, a leader should be elected from all approaching vehicles
to serve as the temporary traffic light infrastructure and stop at the intersection
to coordinate the traffic. The green signal is always given to the lane of detected
emergency vehicles and through coordination “green-wave” signals are displayed for
the emergency vehicles to let them move at a faster speed. Kurt Dresner and Peter
Stone proposed a simple way to deal with emergency vehicles under their intersection control framework AIM (Autonomous Intersection Management) [24]. Their
algorithm only grants reservations to vehicles in the lanes that have approaching
emergency vehicles which allow the emergency vehicle to continue on its way relatively unhindered.

15

Chapter 3

DTOT-based Intersection
Traffic Management
As introduced in Chapter 1, DTOT is the abbreviation of Discrete-Time Occupancy
Trajectory which is a sequence of a vehicle’s actual occupancy within an intersection
space. Based on the concept of DTOT, we propose a novel intersection control
algorithm named DICA (DTOT-based Intersection traffic Coordination Algorithm)
in this chapter.

3.1

Assumptions

In this section, we introduce the basic idea and algorithm of DICA that is developed for autonomous and connected intersection crossing traffic in which all vehicles
are Connected and Autonomous Vehicles (CAVs) and capable of wireless vehicular
communication. We assume that an intersection has the wireless communication
capability as well as a computation unit so that it can exchange information with
vehicles and perform necessary computations to coordinate vehicles to cross the intersection safely. In DICA, there is no traffic light that controls the intersection

16

Vehicle vj
O

j
3

O

j
2

j
1

O

O4j

Vehicle vi
O1i

O2i

O5j O i

3

O4i

O5i

O6i

O6j

The enter line of
the lane vehicle
vi is in

O7j

Detectors

Intersection region

Communication region

Figure 3.1: DTOTs of two conflicting vehicles. (Oqp represents the q-th occupancy
in a vehicle v p ’s DTOT. Note that occupancies in this figure are intentionally made
very sparse for clear illustration purpose. DTOT starts with the occupancy in which
the vehicle’s front bumper first contacts the enter line of its lane of an intersection,
and ends with the occupancy that the vehicle is completely out of the intersection
region.)
crossing traffic. Instead, each vehicle communicates with the Intersection Control
Agent (ICA), to get permission to access the intersection. As shown in Figure 3.1,
an intersection consists of two regions. The bigger region in the figure, which we call
the communication region, is defined by the wireless vehicular communication range.
The smaller region in the figure, which we call the intersection region, is the area
within an intersection that is shared by all roads connected to the intersection. We
also assume that each vehicle is equipped with an RFID (Radio Frequency IDentification) chip and there are detectors installed at the entrance of the communication
region so that ICA can detect each vehicle’s VIN (Vehicle Identification Number),

17

the lane on which a vehicle is approaching an intersection, and the time when a
vehicle enters the communication region. Since all vehicles are autonomous, we assume that each vehicle can obtain its position, speed, and the relative distance to an
intersection precisely and also can avoid collisions with other vehicles autonomously
when it is approaching an intersection. With regard to wireless vehicular connectivity, we only require information exchange between CAVs and ICA. Thus, there
is no V2V communication.

3.2

Interaction between ICA and a CAV

A CAV is considered a head vehicle in its lane if there are no vehicles in front of it
or the vehicle which is immediately in front of it has begun to enter the intersection
region. As shown in Figure 3.2, the interaction between a CAV and ICA is initiated
from the CAV, when it becomes a head vehicle, by sending a REQUEST message to
reserve a sequence of spaces and times to cross the intersection. ICA knows whether
a vehicle is a head vehicle or not according to the list of vehicles for each lane. Thus,
a REQUEST message not from a head vehicle will be neglected by ICA. The list can
be constructed in ICA since, as explained earlier, ICA knows each vehicle’s VIN,
the lane on which the vehicle is approaching, and the time when a vehicle passes a
detector installed at the boundary of the communication region of an intersection.
Each REQUEST message contains information that is necessary to reserve the space
and time within the intersection region to cross the intersection such as (i) the VIN,
(ii) the Vehicle Size (VS), and (iii) the Timed State Sequence (TSS). The VS is
simply the length and width of the vehicle and the TSS is the discrete time state
trajectory of the vehicle starting from the entering moment of an intersection region
to the moment when the vehicle crosses the intersection region completely. Note
that it is implicitly assumed that each discrete time state of a vehicle in TSS is
also timed. This means that if a vehicle state xt is given, then we can say that a
18

vehicle possesses the state x at time t. For simplicity of our discussion, we assume
that the state x of a vehicle consists of the (x, y) coordinate of the vehicle’s location
and the orientation θ. We also assume that, while it is possible that each vehicle
can have different sampling period to generate its TSS, all vehicles use the same
sampling period which is small enough to generate a close approximation of the
vehicle’s actual continuous motion within an intersection.
Inside communication region

DICA
Yes: send REQUEST
Become a head vehicle ?

Convert TSS to
DTOT
Adjust DTOT if
needed

No: follow traffic
Send RESPONSE

Follow confirmed DTOT

Confirm DTOT

Out of intersection region
CAV

ICA

Figure 3.2: Interaction between a CAV and ICA.
ICA converts the TSS to the corresponding DTOT using the VS information
which is also contained in the received REQUEST message. The DTOT is simply
a sequence of timed rectangular spaces that a vehicle needs to occupy within an
intersection region to cross the intersection. Now, ICA uses all confirmed DTOTs
to adjust the requested DTOT to avoid collisions if needed. ICA then converts the
collision-free DTOT to TSS and sends it back to the vehicle using a RESPONSE
message which contains (i) the VIN and (ii) TSS so that the vehicle can follow
the confirmed DTOT to cross the intersection. More detailed explanation on how
to process the requested TSS to generate a confirmed DTOT is presented in the
following section. In the sequel, we say that a vehicle is a confirmed vehicle if it

19

has received a confirmed DTOT from ICA. And we assume that every vehicle is
able to follow the confirmed DTOT precisely. In practice vehicles will have tracking
errors to follow a given DTOT. To avoid potential collisions with other vehicles,
we can increase the size of every occupancy in the DTOT by the upper bound
of tracking errors. Since the focus of this chapter is to develop an algorithm for
ICA for safer and higher throughput intersection crossing traffic, we simply assume
that we have an ideal wireless vehicular communication performance such that all
REQUEST and RESPONSE messages are exchanged correctly and timely. However,
it is important to note that, despite such an ideal communication assumption, our
DTOT-based algorithm can still be applicable in practice with small modifications
of the algorithm to take into account the communication unreliability. For instance,
typically we may face two problems (i.e. package delay and lost) to handle the
imperfect communications existing between CAVs and ICA in real situations. We
could use the upper bound of the package delay to extend every occupancy in a
DTOT which is safe for vehicles but a little bit conservative. For package lost
problem, an ACK message can be added to confirm the delivery of REQUEST and
RESPONSE messages whose details can be found in next Section. A CAV will
send REQUEST again if it does not receive the ACK message from ICA. The same
strategy could be applied to ICA and RESPONSE message.

3.3

DTOT-based Intersection Traffic Coordination

ICA processes a REQUEST message from a head vehicle according to the procedures shown in Algorithm 1 which we call the DTOT-based Intersection traffic
Coordination Algorithm (DICA). As shown in the algorithm, we use TSS(v) and
DTOT(v) to denote the TSS and DTOT for a vehicle v respectively. We also use S
to denote the set of vehicles which have already been confirmed at the time when
a REQUEST message is being processed. We say that two vehicles are space-time
20

Algorithm 1 DICA (DTOT-based Intersection traffic Coordination Algorithm)
1: Let S be the set of confirmed vehicles and n = |S|.
2: Let v i be the vehicle to be considered for confirmation.
3: Convert T SS(v i ) to DT OT (v i )
4: Call checkFV(S, DT OT (v i )) → DT OT (v i )
5: Call getCV(S, DT OT (v i )) → C
6: while C 6= ∅ do
7:
Pop the first vehicle in C → v j
8:
Call updateDTOT(DT OT (v i ), DT OT (v j )) → DT OT (v i )
9:
Call getCV(S, DT OT (v i )) → C
10: end while
11: Store DT OT (v i ) for vehicle v i
12: Convert DT OT (v i ) to T SS(v i )
13: Send T SS(v i ) to vehicle v i

conflicting if their trajectories are conflicting not only in space but also in time.
More precisely, two vehicles are considered to be in space-time conflict in our algorithm when their DTOTs have at least one pair of occupancies that conflict in
both space and time. We use another set C in Algorithm 1 to represent the subset
of S which contains the set of vehicles whose confirmed DTOTs have space-time
conflict with the DTOT of the vehicle that is currently being processed for confirmation. Vehicles in C are ordered in ascending order of a certain attribute of
their confirmed DTOTs. To explain this attribute more clearly, let us consider a
situation when DICA processes a vehicle v i ’s DTOT and there are two vehicles v j
and v k in the set C. Now let us suppose that DTOT(v j ) starts to space-time conflict with DTOT(v i ) from its n-th occupancy and DTOT(v k ) starts to space-time
conflict with DTOT(v i ) from its m-th occupancy. If we use Oqp to denote the q-th
occupancy within DTOT(v p ) and τ (Oqp ) be the time when the vehicle v p occupies
Oqp , then we say that, in this particular situation, τ (Onj ) is the first time at which
k ) is the time at which v k starts to
v j starts to collide with v i . Similarly, τ (Om

collide with v i . In the sequel, this specific time instant for each vehicle in C is represented by the variable ‘firstTimeAtCollision’. In this particular situation, τ (Onj )

21

k ) are denoted by v j .f irstT imeAtCollision and v k .f irstT imeAtCollision,
and τ (Om

respectively. Vehicles in the set C are ordered according to this variable. Specifically,
if v j .f irstT imeAtCollision is earlier than v k .f irstT imeAtCollision, then v j gets
higher priority than v k and vice versa. To see more clearly how the ‘firstTimeAtCollision’ is determined, we can consider an illustrative example shown in Figure
3.1. In the figure, DTOT(v i ) and DTOT(v j ) have space conflicts in {O2i , O3i } and
{O5j , O6j ,}. If we assume that these occupancies are also conflicting in time, then
v j .f irstT imeAtCollision with respect to the vehicle v i is τ (O5j ).
As shown in Algorithm 1, when ICA receives a REQUEST message from a head
vehicle v i , it first converts the TSS(v i ) into the corresponding DTOT(v i ) using
the vehicle’s VS. Then ICA calls the function checkFV() to determine if there
exist front vehicles (See Section 3.3.1 for more details about front vehicles.) that
affect the vehicle v i ’s motion and also to adjust v i ’s DTOT if needed. Then the
function getCV() is called to determine the set C which is the set of vehicles whose
DTOTs are space-time conflicting with DTOT(v i ). The updateDTOT() function
adjusts DTOT(v i ) appropriately so that DTOT(v i ) avoids space-time conflict with
other vehicle’s DTOT. These two functions are iteratively called within the while
loop until the set C becomes empty, which indicates that no vehicles in the set
C will collide with the vehicle v i . After DTOT(v i ) is appropriately adjusted and
confirmed that there is no space-time conflict with all other confirmed vehicles,
then the confirmed DTOT(v i ) is converted into TSS(v i ). Finally, ICA sends the
confirmed TSS(v i ) back to the vehicle v i so that the vehicle can cross the intersection
safely by following the confirmed DTOT. In the following sections, we provide more
detailed explanation on the subfunctions called within DICA.

22

Vehicle vi

Vehicle vi
(a)

(b)

Figure 3.3: Example situations of front vehicles: (a) vehicles with different routes
but same exit lane, and (b) vehicles with same intersection crossing routes.

3.3.1

Collision Avoidance with Front Vehicles

As shown in Figure 3.3, there are two types of front vehicles when a vehicle v i is
approaching and crossing an intersection. In DICA, a vehicle is considered as a
front vehicle of v i if the vehicle comes from another lane but has the same exit
lane as vehicle v i or the vehicle is immediately in front of v i and has the exact
same intersection crossing route as that of v i . For a vehicle v i , if there is another
confirmed vehicle whose exit lane is the same as that of vehicle v i and will exit the
intersection earlier, then they may collide immediately after crossing the intersection
if the speed of vehicle v i is higher than that of the other confirmed vehicle. To address
this problem, AIM [23] adopted a simple strategy which gives one second separation
time between these two vehicles. However, it is important to note that the separation
time should depend on the speeds of the two vehicles. Hence, instead of using a fixed
separation time approach, we use an approach that restricts the maximum speed of
a following vehicle by the speed of the front vehicle. In the example situation (a)
shown in Figure 3.3, the vehicle v i ’s maximum allowed speed within an intersection
is restricted by the front vehicle’s exit speed. If there is another confirmed vehicle
that has the same intersection crossing route as vehicle v i , we adjust v i ’s speed to
23

leave adequate distance between them. In Algorithm 1, the function checkFV()
looks for the existence of above mentioned front vehicles from all confirmed vehicles
and delay the new head vehicle to avoid potential collisions if needed.

3.3.2

Vehicles for Collision Avoidance

Algorithm 2 getCV(S, DT OT (v i ))
1: C = ∅
2: for v j in S do
3:
for Okj j in DT OT (v j ) do
4:
if v j not in C then
5:
for Oki i in DT OT (v i ) do
6:
if Okj j ∩ Oki i 6= ∅ then
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

Call getOTI(Okj j ) → I(Okj j ) := [τlb (Okj j ), τub (Okj j )]
Call getOTI(Oki i ) → I(Oki i ) := [τlb (Oki i ), τub (Oki i )]
if I(Okj j ) ∩ I(Oki i ) 6= ∅ then
Assign τlb (Okj j ) → v j .f irstT imeAtCollision
Push v j into C
Sort C in ascending order of firstTimeAtCollision
end if
end if
end for
end if
end for
end for

The function getCV() returns the set C that contains vehicles which will cause
potential collisions inside the intersection with vehicle v i . To better understand the
operation of function getCV(), it is necessary to introduce the way we check the
space-time conflict between two occupancies from DTOTs of two vehicles. For every
individual occupancy in a DTOT of a vehicle, we define the entrance time (τlb ) and
the exit time (τub ) of the occupancy as the times when the vehicle first contacts and
is totally out of the occupancy. These two times can be estimated by taking the
times of the previous and next occupancies which are the closest to the occupancy

24

while having no overlapping area. As an example, for the occupancy O4j of the
vehicle v j in Figure 3.1, the entrance time τlb (O4j ) and the exit time τub (O4j ) of that
occupancy can be determined by τ (O2j ) and τ (O6j ), respectively. Note that a DTOT
for a vehicle consists of many more numbers of occupancies in practice. Hence, the
entrance times and exit times determined in this way can be very close to the actual
entrance and exit times of the occupancy. For the first several occupancies in a
DTOT, there may not be a previous occupancy that has no overlapping area with
themselves. For these occupancies, we simply take the first occupancy’s time in the
DTOT as these occupancies’ entrance time. As an example shown in Figure 3.1,
we use τ (O1j ) as the entrance time τlb (O2j ) for the occupancy O2j . Similarly, we take
the last occupancy’s time as the exit time τub for the last several occupancies in a
DTOT.
As shown in Algorithm 2, the function getCV() determines the set C by checkj
ing space-time conflict for every pair of occupancies (Oni , Om
) for all n, m, and j

in the set S. Since an occupancy in a DTOT is represented as a rectangle, it is
relatively straightforward to do a space conflict checking. For this, Algorithm 2
simply checks if two rectangles have a non-empty intersection or not. If a pair
j
of occupancies (Oni , Om
) are space-conflicting, then the function continues to in-

vestigate these occupancies to determine if they are in time-conflict as well. The
above-explained entrance and exit times of an occupancy are used for this purpose.
For a given occupancy O, the function getOTI() calculates these entrance τlb (O)
and exit τub (O) times for that occupancy and returns a corresponding time interval
I(O) := [τlb (O), τub (O)] which we call the occupancy time interval in the sequel.
Then the two occupancy time intervals for the pair of space-conflicting occupancies
are compared to determine if these occupancies are also occupied around the same
j
time. If a pair of occupancies (Oni , Om
) are conflicting in both space and time, then

the vehicle v j is included in the set C and the corresponding firstTimeAtCollision is

25

determined so that the vehicle v j is appropriately ordered within the set C.

3.3.3

DTOT Update

The first vehicle v in the set C is the earliest vehicle that is space-time conflicting
with vehicle v i . Then, in line 8 of Algorithm 1, the function updateDTOT() modifies
vehicle v i ’s DTOT to avoid collision with vehicle v based on space-time conflicting
occupancies between vehicles v i and v. However, it is still uncertain whether C will
be empty or not after this update of avoiding collision with vehicle v. In fact, it
is still possible that the modified DTOT of vehicle v i will be in space-time conflict
with DTOTs of other confirmed vehicles. Hence, to ensure that vehicle v i avoids
collision with all other confirmed vehicles, it is necessary to construct C based on
the updated vehicle v i ’s DTOT and update the DTOT again to avoid collision with
the first vehicle in the set. This process is repeated in the while loop in Algorithm 1
until the set C becomes empty which means that vehicle v i is not conflicting with any
confirmed vehicles. When a vehicle proposes its DTOT to ICA, we assume that it
prefers to select the fastest way to pass the intersection which means the vehicle will
try to use the maximum allowed speed to cross. Our current strategy for updating
a vehicle’s DTOT is to delay the vehicle until other confirmed vehicles cross an
intersection safely. While it is an interesting future research problem to develop more
sophisticated approaches to improve the overall performance, the current simple
delay strategy is still very effective to ensure collision-free intersection traffic. Note
that, since the times of occupancies in a vehicle’s DTOT are always delayed whenever
the vehicle’s DTOT is updated, it is guaranteed that the vehicle can always meet
the updated DTOT by simply decelerating to experience a long time before entering
the intersection. The worst case is that a vehicle may need to stop and wait for some
time before an intersection to meet the given confirmed TSS from ICA.

26

3.4

Liveness Analysis

A deadlock is a situation where two or more processes are unable to proceed and
each process is waiting for another one to finish because they are competing for
shared resources. In an intersection crossing traffic, a deadlock could happen when
several vehicles are trying to cross the intersection at the same time. For example,
if the coordination between vehicles who want to cross an intersection is not done
appropriately, then a deadlock may occur between two vehicles on a same lane.
As discussed in [23], it is possible that even when the vehicle in front cannot get
confirmed due to the conflict of its intersection crossing route with those of other
vehicles which are already confirmed to enter and cross an intersection, the vehicle in
the back may get confirmed because its intersection crossing route is not conflicting
with other confirmed vehicles’ crossing routes. And the vehicle successfully reserves
the space for its intersection crossing route within an intersection. In this situation,
the front vehicle cannot get confirmed since some part of the intersection crossing
route of it conflicts with that of the behind vehicle which is already confirmed
and also the behind vehicle cannot proceed to cross the intersection due to the
unconfirmed front vehicle. A deadlock situation may also occur when several vehicles
from different directions want to cross an intersection at the same time. This type of
deadlock situation is discussed in detail in [72] for the case of four vehicles in which
none of the vehicles can progress inside the intersection because each of the vehicles’
next occupancies are already occupied by other vehicles. Now we show that DICA
shown in Algorithm 1 are free from these deadlock situations.
Proposition 1. DICA is deadlock free.
Proof. Let Sk denote the set of confirmed vehicles at the k-th time step of DICA.
Then, we show that the set Sk is deadlock free for all k = 0, 1, 2, · · · by induction.
First, at time step k = 0, it is easy to see that there is no deadlock in S0 since no
27

vehicle is confirmed yet, i.e., |S0 | = 0 where | · | denotes the cardinality of a set.
Then, at time step k > 0, let us suppose that Sk is deadlock free and a new head
vehicle v i is under consideration for confirmation. Note that, as discussed in Section
3.1, a vehicle is considered by DICA for confirmation only if it is the head vehicle on
its lane. Hence, it is trivial to see that there won’t be a deadlock situation between
0

0

the vehicle v i and other vehicle v i which is behind v i since v i 6∈ Sk . Next, let us
note that once a vehicle v j is in Sk , then the vehicle’s DTOT will not be changed
while and after a new vehicle v i is processed to be confirmed by DICA. Hence, it is
easy to see that any vehicle which is in Sk at time step k remains deadlock free at
the next time step (k + 1). Now suppose that the new vehicle v i has been confirmed
by DICA at time step k and included in the set of confirmed vehicle at time step
(k + 1), i.e., v i ∈ Sk+1 = Sk ∪ {v i }. Since all vehicles in Sk ⊂ Sk+1 are deadlock
free, if the new vehicle v i is deadlock free, then we know that Sk+1 is deadlock free
and this proves the deadlock free property of DICA. In fact, it is straightforward
to see that v i is also deadlock free after its DTOT is updated and confirmed by
DICA. First, note that modification of the vehicle v i ’s DTOT is not affected by
any vehicle v 6∈ Sk . Instead, it is affected only by vehicles which are already in
the Sk . Since all vehicles in Sk are deadlock free and eventually proceed to cross
and exit the intersection, the vehicle v i ’s DTOT is also updated so that the vehicle
v i will eventually enter and cross the intersection while all vehicles in Sk cross the
intersection safely. Thus, the vehicle v i is also deadlock free at time step (k + 1)
and this concludes the proof of this proposition.
In an intersection crossing traffic, a starvation situation may occur when vehicles
from a certain direction are waiting for a very long time or even indefinitely to
be allowed to enter and cross an intersection while vehicles from other directions
are continuously allowed to cross the intersection. Now we show that a starvation
situation will not occur in an intersection crossing traffic that is coordinated by
28

DICA.
Proposition 2. DICA is starvation free.
Proof. First, let us recall that, as discussed in Section 3.1, DICA considers a vehicle
for confirmation only when the vehicle becomes the head vehicle on its lane. Now let
σ(v) be the vehicle v’s entrance time to the communication region of an intersection,
H be the set of head vehicles which is ordered by σ(v) for all v ∈ H, and H− be the
set of vehicles which are approaching to cross an intersection but not included in the
set H. Clearly, |H| is bounded by the number of all lanes from which vehicles are
approaching an intersection to cross and |H− | is also bounded by both the number
of lanes and the length of lanes within the communication region of an intersection.
Note that DICA processes vehicles in H for confirmation according to the order of
vehicles in H. Once the first vehicle in H is processed and gets confirmed, then the
vehicle is removed from H. Note that if DICA is not starvation free, then there
must exist at least one vehicle v ∈ H such that the vehicle v will never (or at least
take an unnecessarily very long time to) become the first element in the ordered set
H. Thus, to prove the starvation free property of DICA, it suffices to show that,
for any vehicle v ∈ H, the vehicle v will be removed from H in finite time. To show
this, we can consider the last vehicle vlast in the ordered set H. If σ(vlast ) ≤ σ(v)
for all v ∈ H− , then the vehicle vlast will be cleared right after all other vehicles in
H are confirmed and this is the earliest time for vlast to be removed from H. On the
other hand, if σ(vlast ) > σ(v) for all v ∈ H− as the worst situation for vlast , then
the vehicle vlast might need to wait until all (|H| + |H− |) vehicles get confirmed to
be considered for confirmation. Thus, it is clear that the vehicle vlast will be cleared
from H in finite time.

29

3.5

Simulation

In this section, we present simulation results of DICA and the Concurrent Algorithm [1] under same configurations. Compared with Concurrent Algorithm, DICA
provides a more efficient way of coordinating vehicles to avoid unnecessary delay.

3.5.1

Simulation Setup

Traffic simulation is performed by the microscopic road traffic simulation package
SUMO (Simulation of Urban MObility) [73]. This simulator is widely used in the
research community, which makes it easy to compare performance of different algorithms. Our intelligent intersection management algorithm is implemented by the
Traffic Control Interface (TraCI) in SUMO.
The simulated scenario in our simulation is the traffic of a typical isolated four
way intersection with two incoming lanes and one outgoing lane on each road.
vm = 70 km/h is set as the maximum allowed speed for incoming roads. We generate
vehicles with random velocity within the range of 40% ∗ vm and vm when they enter
the communication region. To simulate intersection traffic as real as possible, we
use different maximum allowed speeds for vehicles with different routes. Although
there are not specific speed limits for vehicles who are turning left or right, people
are still using some lower speed to feel comfortable and maintain safety. We choose
conservative speed limits for turning based on experience from driving in daily life.
We use 25 km/h for right turning and 35 km/h for left turning. For vehicles with
through route, 65 km/h is set as the speed limit. The time step we used in simulation is 0.05 s. The maximum acceleration and deceleration rates are 2 m/s2 and
4.5 m/s2 . Vehicles have a size of 5 meters length and 1.8 meters width. Since, in
some cases, a vehicle may need to stop just before the entrance line of the intersection region to avoid collisions with other vehicles, the distance from the entrance line
of the communication region to the entrance line of the intersection region should
30

be long enough so that a vehicle can stop from its maximum speed vm . Thus, from
the value used for vm = 70 km/h the maximum deceleration rate amin = 4.5 m/s2 ,
2 /(2a
we need at least vm
min ) ≈ 42.03 m. So, we use 50 m for the distance from the

entrance line of the communication region to the entrance line of the intersection region. We evaluate the performance of our algorithm in situations where vehicles are
spawned randomly from each direction at different probabilities. In our simulation,
we consider three different traffic volumes. For each traffic volume, through different
traffic generation time and randomly generated vehicles’ routes, we test each case
for twelve different traffic patterns. Average data of twelve different traffic patterns
are used as the result for that case. Each simulation run is terminated when a certain time limit (10 min) has been reached. Fig 5.8 shows a screenshot of simulation
in SUMO when vehicles of different routes appears within the intersection simultaneously without occurrence of collision. Inside the intersection, the straight going
vehicle from East goes inside the intersection shortly after the vehicle from North
to South clears the conflicting space. Vehicles whose DTOTs is not conflicting with
these two can pass the intersection at the same time, for example the right-turning
vehicle from South in the figure.
Table 3.1: Simulation results comparison.
Crossed Vehicles
Volume

ρ

Concurrent

Volume 1
Volume 2
Volume 3

DICA

Volume 1
Volume 2
Volume 3

τ̄e

τ̄

στ

η

93.99%
60.24%
30.91%

13.98
89.08
125.09

8.58
40.91
48.33

51.74%
95.34%
97.17%

14.85
150.77
408.90

95.11%
91.09%
57.09%

7.21
20.47
50.60

2.97
15.54
32.87

10.13 %
55.86%
84.37 %

7.57
22.53
88.92

31

Figure 3.4: A screenshot of simulation which illustrates a situation when vehicles
with conflicting routes cross the intersection simultaneously.

3.5.2

Simulation Results

Performance improvement has been validated through extensive simulations of DICA
and Concurrent Algorithm. Simulation results of different volumes are shown in Table 3.1. To evaluate and compare the performance, we define several performance
measures. Trip time (τ ) is the difference between actual exit time of the intersection
and the time the vehicle enters the intersection communication range. Average trip
time (τ̄ ) is the average value of trip times of all crossed vehicles. Standard deviation (στ ) is computed based on the trip times of all crossed vehicles. Throughput
(ρ) is defined as the percentage of crossed vehicles against total generated vehicles.
Stopped rate (η) is obtained through dividing stopped vehicles number by crossed
vehicles number.
However, note that neither the average trip time nor the throughput alone is
sufficient to correctly evaluate the performance of an algorithm. In some cases,
it could be possible that one algorithm shows better performance on average trip

32

time while another algorithm performs better on throughput. Thus, both of the
two measures should be considered together to correctly compare and evaluate the
performances of different intersection control algorithms. We calculated the ratio
of average trip time to throughput, which is called effective average trip time (τ̄e )
and believe it could show the performance of an algorithm more comprehensively,
i.e. τ̄e = τ̄ /ρ.
Compared with Concurrent Algorithm, DICA increases the throughput and
largely decreases the average trip time. As shown in Table 3.1, both algorithms
have less and less throughput with the increase of traffic volume. Also, larger
decrease of throughput is shown in Concurrent Algorithm compared with DICA.
DICA’s smaller values of standard deviation imply that DICA is fairer than Concurrent Algorithm. Stopped rate shows that less vehicles experience a stop at the
intersection enter line for our DICA algorithm thus saves energy. Effective average
trip time could tell us comprehensive information about the performance of an intersection control algorithm. Efficiency and fairness of an algorithm are integrated
in this measure. With more vehicles crossed and less average trip time, DICA has
much less value of effective average trip time than that of Concurrent Algorithm.
The histogram of trip times of crossed vehicles in one simulation run from case 1
and one particular traffic pattern is shown in Figure 3.5. From the figure we can see
that under the same traffic setting, for the crossed vehicles, DICA results in less and
concentrated trip times. On the other side, Concurrent Algorithm leads to much
longer and wider distributed trip times. Compared with Concurrent Algorithm,
DICA is fairer and much efficient for crossed vehicles.
Figure 3.6 shows the maximum, average and minimum trip time for both algorithms under three different volumes. With heavier traffic volume, both algorithms
have large maximum trip times and average trip times. However, DICA always
performs better than Concurrent Algorithm in all three volumes.

33

Concurrent Algorithm
Number of vehicles

40
30
20
10
0

0

20

40

60
Trip time(s)

80

100

120

80

100

120

DICA
Number of vehicles

40
30
20
10
0

0

20

40

60
Trip time(s)

Figure 3.5: The histogram of Trip Times of crossed vehicles in a simulation.
Concurrent Algorithm
200
Trip time(s)

Average Trip Time
150
100
50
0

Volume 1

Volume 2

Volume 3

DICA
Trip time(s)

200
150

Average Trip Time

100
50
0

Volume 1

Volume 2

Volume 3

Figure 3.6: Comparison of Trip Times of 3 different cases between DICA and Concurrent Algorithm.

3.6

Summary

In this chapter, we have developed an intelligent intersection control algorithm DICA
employing the concept DTOT. V2I interaction protocol has been established for
34

interactions between vehicles and intersection. DICA is able to manage limited
intersection space at a more accurate and efficient way. Simulation results show that
our algorithm achieves less effective average trip time compared with Concurrent
Algorithm proposed by [1].

35

Chapter 4

Computational Complexity
Improvements of DICA
In this chapter, we analyze the overall computational complexity of DICA and improve it in several computational technical approaches. We also enhance the algorithm accordingly so that it is possible to operate the algorithm in real-time for
autonomous and connected intersection traffic management.

4.1

Computational Complexity Analysis

In this section, we analyze the computational complexity of DICA shown in Algorithm 1. Recall that S is the set of vehicles within the communication region of
an intersection that has been confirmed to cross. Let us assume that there are n
vehicles in S, i.e., |S| = n. Then we have the following result on the computational
complexity analysis of DICA.
Proposition 3. DICA has O(n2 L3m ) computational complexity where Lm is the
maximum length of intersection crossing routes in an intersection.
Proof. Let v i be the vehicle which is currently being processed by ICA for intersec36

tion crossing confirmation. Also let Nm := maxk∈S 0 N k where S 0 = S ∪ {vi } and N k
is the number of occupancies in the vehicle k’s DTOT. Then, in line 3 (Algorithm
1), it is easy to see that creating DTOT from the TSS and vehicle size information
in the vehicle v i ’s REQUEST message involves only O(Nm ) computational complexity. In line 4 (Algorithm 1), as explained in Section 3.1, the front vehicle checking
function checkFV() does a simple comparison with every confirmed vehicle in S to
see if there are any vehicles which might affect the vehicle v i ’s DTOT and modifies
the DTOT if it is necessary to ensure enough separation time and distance between
the vehicle v i and other vehicles in front. And this process requires O(nNm ) computational complexity. Then, in line 5 (Algorithm 1), the function getCV() is called
to identify the set C of vehicles in S whose DTOTs might be in space-time conflict
with the vehicle v i ’s DTOT. (Note that, as shown in Algorithm 2, C is an ordered set
according to time of collision and it is clearly C ⊆ S.) Thus, to return the set C from
the set S, this function performs n times of space-time conflict checking between the
vehicle v i and vehicles in S. If a non-empty set C is returned in line 5 (Algorithm
1), then, in lines 6 ∼ 10 (Algorithm 1), the vehicle v i ’s DTOT is iteratively updated
until the set C becomes empty within the while loop. (As one can see in Algorithms
1 and 2, these steps are indeed the main part of the DICA algorithm and involve
some computationally expensive operations. Hence, we describe the computational
complexity of steps within the while loop separately in the next paragraph.) After
the while loop, as the last steps in Algorithm 1 in lines from 11 to 13, the spacetime conflict free DTOT for the vehicle v i is stored, converted into TSS, and then
sent to v i so that the vehicle can cross the intersection according to the DTOT.
Clearly, these steps are fairly simple in terms of computation and in fact require
O(1) complexity. Next, we analyze the computational complexity of steps within
the while loop.
Space-time conflict checking steps: As described in Section 3.1, space-time con-

37

flict checking in getCV() is done using DTOTs of vehicles. Specifically, the two
nested if blocks from line 6 to line 14 in Algorithm 2 perform this operation. For
space conflict checking, it is checked if there exist non-empty intersections between
two occupancies: one from DTOT of the vehicle v i and another from DTOT of
one of the vehicles in the set S. This is done in the outer if block and requires
2 times of iteration in the worst case. If two vehicles have a space conflict,
n · Nm

then Algorithm 2 proceeds to check for time conflict. To check time overlapping
between two space conflicting occupancies, the function needs to calculate time intervals for these occupancies during which each vehicle occupies its occupancy. This
can be done easily by comparing occupancy time between occupancies within the
same DTOT. As an example, for a given occupancy Oki which is the k-th occupancy
within the vehicle v i ’s DTOT, the lower and upper bounds for the occupancy time
can be determined by space overlapping checking between the occupancies Oki and
Oki 0 for k 0 = {1, · · · , Nm } \ k. Thus, the two function calls to getOTI() within the
if block involve the computational complexity of O(Nm ). Once the occupancy time
intervals are determined, it is a straightforward calculation to check time overlapping as shown in line 9 of Algorithm 2 and it takes O(1) computational complexity.
After identifying all space-time conflicting vehicles from the set S and storing them
to the set C, Algorithm 2 then sorts the set C according to the ascending order
of occupancy times of space-time conflicting occupancies and returns the set. Note
that |C| ≤ n and n  Nm in general. Hence, this sorting operation can be done with
O(nlog2 Nm ) computational complexity. If we consider all these calculation steps in
the getCV() function, then one can see that the overall computational complexity
3 ).
for space-time conflict checking steps in getCV() is O(nNm

DTOT adjustment for collision avoidance: Once the set C is returned from the
function getCV(), the DICA algorithm updates the vehicle v i ’s DTOT to avoid
space-time conflict with DTOTs of the vehicles in the set C. In line 7 (Algorithm

38

1), it is shown that the first vehicle v j in the set C is considered for updating the
vehicle v i ’s DTOT. As described in Section 3.1, our update strategy to avoid spacetime conflicts is to make the vehicle v i enter the intersection area a little bit late so
as to give enough time for vehicle v j to cross the intersection safely. For this, the
DICA algorithm first needs to compute the delay time needed to avoid the spacetime conflict with the vehicle v j . Since the occupancy time interval I(Okj ) for the
vehicle v j ’s earliest space-time conflicting occupancy has already been determined
from the function getCV(), it is easy to calculate this delay time in this update
process. Once the delay time is determined, then the remaining step is simply to
change the occupancy times of all the occupancies in the vehicle v i ’s DTOT to be
delayed and this results in O(Nm ) computational complexity.
As described above, the number of vehicles in the set S is n when the function
getCV() is called for the first time in line 5 (Algorithm 1). Then, within the while
loop, the function updateDTOT() adjusts the vehicle v i ’s DTOT to avoid collision
with the first vehicle in the set C and this step reduces the number of vehicles in
the set C that can potentially collide with the vehicle v i at least by one. Thus,
in the worst case, the number of vehicles in the set C returned by the second call
of getCV() within the while loop is (n − 1). If we assume the worst case for all
following iterations within the while loop until the set C becomes empty, then it
is easy to see that the functions getCV() and updateDTOT() are called n times
within the while loop. This implies that since the computational complexity of the
function updateDTOT() is significantly lower than that of the function getCV(), the
3 ).
overall computational complexity of the while loop can be considered as O(n2 Nm

Note that the maximum number of occupancies Nm depends on both the time
that it takes for a vehicle to cross the intersection and the discrete time step used to
construct the DTOT by ICA. If we let h be the discrete time step used by ICA and
Tm be the time it takes for a vehicle to completely cross an intersection when the

39

v
case 2

vm
case 1

0

tm

tm

t

Figure 4.1: Two different cases for shortest intersection crossing time (Tm ) calculation. (Case 1 is the situation when Lm is too short to reach vm and case 2 is
the situation when Lm is long enough to reach vm while a vehicle is crossing an
intersection.)
vehicle starts from rest and accelerates to cross the intersection as quickly as possible,
then we have N̄m := Tm /h as an upper bound for Nm . Note that Tm depends on the
length of an intersection crossing route that a vehicle takes to cross an intersection.
If we let Lm be the maximum length out of all intersection crossing routes for an
intersection, then N̄m can be expressed in terms of Lm instead of Tm . Specifically,
if Lm is long enough so that a vehicle can reach its maximum allowed speed vm
within an intersection before it completely crosses the intersection, then it can be
2 )/(2a v h) where a is the maximum acceleration
shown that N̄m = (2am Lm + vm
m m
m

rate of a vehicle. On the other hand, if Lm is not long enough for a vehicle to reach
vm while crossing an intersection, then it is also relatively straightforward to show
p
that N̄m = ( 2Lm /am )/h. (These two different cases are illustrated in Figure 4.1.)
If we fix values for h, vm , and am , then one can see that N̄m for the former case is
proportional to Lm while, for the latter case, N̄m is proportional to the square root of
3)
Lm . Hence, if we substitute Lm for Nm in the computational complexity O(n2 Nm

that we derived above, then we finally have O(n2 L3m ) as the overall computational
complexity of DICA.

40

4.2

Algorithm Improvements

According to the computational complexity analysis result described in the previous
section, it is true that the original DICA algorithm that is shown in Algorithms 1 and
2 is somewhat conservative in terms of computational cost to be used in practice. In
this section, we present several approaches that can be used to improve the overall
computational efficiency of the algorithm.

4.2.1

Reduced Number of Vehicles for Space-Time Conflict Check

As shown in Algorithm 2, all confirmed vehicles in the set S are examined to obtain the set of space-time conflicting vehicles C for a new unconfirmed head vehicle
v i . However, we see that this computation process can be improved by excluding
vehicles that cannot be in space-time conflict with the vehicle v i under any circumstances from the set S. For example, a confirmed vehicle v j ∈ S who has an
intersection crossing time interval that is not overlapping with the vehicle v i ’s intersection crossing time interval can be excluded. Note that the intersection crossing
time interval of a confirmed vehicle can be easily determined by the lower bound of
the occupancy time τlb (Of irst ) of the vehicle’s first occupancy Of irst and the upper
bound of the occupancy time τub (Olast ) of the vehicle’s last occupancy Olast in the
vehicle’s confirmed DTOT. In addition to these vehicles, vehicles in the set S whose
intersection crossing routes are compatible with that of vehicle v i can also be excluded. Hence, if we let S ∗ be the subset of all confirmed vehicles in set S that can
be obtained after excluding all above-mentioned vehicles in determining the set C,
then the resulting computational complexity for the space-time conflict checking in
3 ) where α := ñ/n, ñ = |S ∗ |, n = |S|, and N
function getCV() becomes O(α1 nNm
1
m

is the maximum number of occupancies of all vehicles that are in the set S and also
41

the vehicle that is currently under consideration for confirmation. (See the proof of
Proposition 3 for the precise definition of Nm .)

4.2.2

Efficient Space Conflict Check

Note that, for any two vehicles coming from different directions, they can collide
with each other only within some parts of their intersection crossing routes. Thus,
not all occupancies of a vehicle’s DTOT needs to be checked for space conflict with
another vehicle’s DTOT. For example, the two vehicles v i and v j in Figure 3.1 have
very short ranges of intersection crossing routes that are space conflicting with each
other. Thus, the occupancies to be checked can be reduced to {O2i , O3i } and {O5j , O6j }
from their entire DTOTs. Since the number of occupancies in a DTOT is very large
in general, this can improve computational speed considerably. Note that, since the
intersection crossing routes are fixed for a specific intersection, we can predetermine
these space conflicting short ranges offline only one time for all pairs of incompatible
intersection crossing routes. Hence, this extra preparation process does not incur
an additional computational cost during the online operation of DICA. If we use
DTOT∗ to denote the subset of the original DTOT for a vehicle that can be obtained
from this approach, then the computational complexity of the function getCV() in
3 ) where α := Ñ /N
Algorithm 2 can be expressed as O(α23 nNm
2
m
m and Ñm is the

maximum number of occupancies of all vehicles that are in the set S ∗ and the vehicle
that is currently under consideration for confirmation.

4.2.3

Approximate Occupancy Time Interval Calculation

As explained in Section 3, ICA checks if an occupancy of a vehicle is conflicting
in time with another vehicle’s occupancy using occupancy time intervals that can
be obtained from each vehicle’s DTOT. However, the way to obtain an occupancy
time interval presented in the proof of Proposition 3 is somewhat naive in the sense

42

of computational complexity. In fact, as analyzed in the proof, such an exhaustive
search involves a computational complexity of O(Nm ). To simplify this computation
process, we propose to estimate the occupancy time interval for a certain occupancy
based on the vehicle’s speed, length, and acceleration rate instead of performing the
exhaustive search. To clarify this idea, let us consider an example. For simplicity
of explanation, we consider a case when a vehicle is moving in a straight line as
shown in Figure 4.2. Let Oki be the occupancy for which the DICA algorithm needs
to determine the occupancy time interval I(Oki ) = [τlb (Oki ), τub (Oki )], L(v i ) be the
vehicle length of the vehicle v i , h be the sampling time interval, xk be the center
position of the Oki along the straight line. Then the algorithm first estimates the
vehicle’s speed and acceleration rate around the occupancy Oki from xk , xk−1 , xk+1 ,
and h. Occupancies at xk−1 , xk+1 are very close to the occupancy Oki and are not
shown in Figure 4.2 for simplicity. Specifically, if we let Vk− (v i ) and Vk+ (v i ) be the
i
i
respectively, then
to Oki and from Oki to Ok+1
speed of the vehicle v i from Ok−1

these speeds can be approximated as follows:

Vk− (v i ) ≈

xk − xk−1
,
h

Vk+ (v i ) ≈

xk+1 − xk
h

(4.1)

From these speeds, we now approximate the acceleration rate of the vehicle as
follows:
Ak (v i ) ≈

Vk+ (v i ) − Vk− (v i )
h

(4.2)

where Ak (v i ) denotes the acceleration of the vehicle v i at the occupancy Oki . If
we take the average of the speeds around Oki , then we can also approximate Vk (v i )
which is the speed of the vehicle v i at Oki . Note that since the length of a vehicle
L(v i ) is just a few meters in general, the actual motion of the vehicle v i within the
occupancy Oki can be approximated fairly accurately by Vk (v i ) and Ak (v i ).
Now, since it is a straightforward process to estimate τlb (Oki ) and τub (Oki ) from

43

Vk (v i ), Ak (v i )
L (v i )

xk
O

i
k

t
i
k

t lb (O )

i
k

t (O )

i
k

t ub (O )

Figure 4.2: Approximate occupancy time interval calculation for a vehicle with
through route.
L(v i ), Vk (v i ), and Ak (v i ), we omit the details of these calculations. For the case
when the vehicle is moving on a curved path, we can still use the same method
to approximate Vk (v i ) and Ak (v i ). But, in this case, we may need to add a short
extra distance to the L(v i ) to estimate τlb (Oki ) and τub (Oki ) more accurately. Such
an extra distance can be simply determined by the curvature of the path that is
represented by the DTOT of a vehicle. Finally, if we apply this approximation
method for an occupancy time interval calculation in the getOTI() function, then
3 ) to
the computational complexity of the function getCV() improves from O(n2 Nm
2 ).
O(n2 Nm

4.2.4

Efficient Occupancies Comparison

In addition to all the techniques described above, the overall computational complexity of Algorithm 1 can be improved further if we employ an efficient searching
method such as the bisection method in the process of time-conflict checking between two DTOT∗ s. If we employ this bisection approach for time-conflict checking
as shown in Algorithm 3, then the computational complexity of the function getCV()
3 ) to O(n2 N 2 log N ).
can be improved significantly from O(n2 Nm
2 m
m

All of the improvement techniques discussed in this section are incorporated into
the function getCV() to improve the overall computational complexity of the space44

Algorithm 3 enhanced getCV(S ∗ , DT OT (v i ))
1: Let S ∗ be the reduced set of S.
2: Let DT OT ∗ be the reduced DT OT .
3: C = ∅
4: for v j in S ∗ do
5:
for Okj j in DT OT ∗ (v j ) do
6:
if v j not in C then
7:
high = |DT OT ∗ (v i )| − 1
8:
low = 0
9:
while low 6= high do
10:
middle = (high + low)/2
11:
Call getEstOTI(Okj j ) → I(Okj j )
i
i
12:
Call getEstOTI(Omiddle
) → I(Omiddle
)
j
i
13:
if I(Okj ) ∩ I(Omiddle ) 6= ∅ then
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

Assign τlb (Okj j ) → v j .f irstT imeAtCollision
Push v j into C
Sort C in ascending order of firstTimeAtCollision
i
) then
else if τ (Okj j ) > τ (Omiddle
low = middle
i
) then
else if τ (Okj j ) < τ (Omiddle
high = middle
end if
end while
end if
end for
end for

time conflict checking process. Algorithm 3 shows this modified getCV() function
which is now called enhanced_getCV(). In Algorithm 3, S ∗ represents the set of
already confirmed vehicles that is obtained from the process in Section 4.2.1 and
DTOT∗ represents the subset of original DTOT for a vehicle that can be obtained
from the approach in Section 4.2.2. The function getOTI() within the while loop
is now replaced by the new function getEstOTI() that calculates the occupancy
time interval approximately as described in Section 4.2.3. Lastly, the approach for
efficient time conflict checking that is presented in Section 4.2.4 is implemented
throughout the while loop of the DICA algorithm.

45

Proposition 4. Enhanced DICA has O(αn2 Lm log2 Lm ) computational complexity
where α := α12 α2  1, n is the number of vehicles already confirmed to cross an
intersection, and Lm is the maximum length of intersection crossing routes in an
intersection.
Proof. First, note that the only part in Algorithm 1 that is affected by this proposed enhancement is that the number of confirmed vehicles to be considered for
a space-time conflict check is reduced from n = |S| to ñ = |S ∗ | where ñ = α1 n
and α1 ∈ (0, 1].

Thus, in Algorithm 1, the functions enhanced_getCV() and

updateDTOT() are now called α1 n times. Next, we also note that, since nothing
is changed due to this improvement in the updateDTOT() function whose computational complexity is already significantly lower than that of the function getCV(), it
suffices to analyze the computational complexity of the function enhanced_getCV()
presented in Algorithm 3 for the overall computational complexity of the enhanced
DICA.
Now, as one can see in Algorithm 3, the entire block within the outer for loop
is executed for α1 n times since the number of confirmed vehicles to be checked for a
space-time conflict with the vehicle v i is reduced from n to α1 n due to the approach
discussed in Section 4.2.1. Then, within the for loop, for each vehicle v j in the
set S ∗ , occupancies from each vehicle’s DTOT are evaluated for space and time
2 times occupancy comparison operation where
conflict which typically requires Nm

Nm is the maximum number of occupancies in a vehicle’s DTOT. However, in the
enhanced_getCV() function, we first note that the maximum number of occupancies for each vehicle’s DTOT to be tested for space-time conflict is reduced from Nm
to Ñm where Ñm = α2 Nm and α2 ∈ (0, 1] due to the approach presented in Section
4.2.2. Another important improvement is that the computational complexity for the
occupancy time interval calculation is improved from O(Nm ) to O(1) within another
enhanced function getEstOTI() as discussed in Section 4.2.3. Therefore, the overall
46

2 ).
computational complexity of the outer for loop can be estimated as O(α1 α22 nNm

However, note that this is the case when we use the same occupancies comparison method as used in the original getCV() function. As shown in Algorithm 3,
the process of occupancies comparison is now performed based on the bisection
search method. Roughly speaking, for given n and Nm , this efficient search method
2 ) to
improves the overall computational complexity of the function from O(nNm

O(nNm log2 Nm ) as discussed in Section 4.2.4. If we combine this and others discussed above for the overall computational complexity of the enhanced_getCV()
function, then we have O(α1 α2 nNm log2 Nm ). Recall that the enhanced_getCV()
function is called at α1 n times in the main while loop as discussed above, we have
O(α12 α2 n2 Nm log2 Nm ) as the overall computational complexity of DICA.
As we have analyzed already in the proof of Proposition 3, Nm is linearly proportional to the maximum length of intersection crossing routes Lm . Hence, if we
substitute Lm for Nm , then we finally have O(αn2 Lm log2 Lm ) as the overall computational complexity of enhanced DICA where α := α12 α2  1.

4.3

Simulation

In this section, we present simulation results that demonstrate the improved performance of the enhanced DICA over the original algorithm. The performance of
the enhanced algorithm is also compared with that of an optimized traffic light
intersection control.

4.3.1

Simulation Setup

To evaluate the performance of the original DICA and the enhanced DICA, we
implemented both algorithms in SUMO [73], and performed extensive intersection
traffic simulations. The simulated situation is an intersection crossing traffic on a
typical isolated four-way intersection with three incoming lanes, one of which is a
47

dedicated lane for left-turning vehicles, and two outgoing lanes on each road. We
set 70 km/h as the maximum allowed speed vm for all incoming vehicles. We let
vehicles approach an intersection with different speeds when they enter into the
communication region of the intersection to make the simulation more realistic.
Specifically, when a new vehicle is spawned outside of the communication region, we
assign the initial speed of the vehicle randomly within the range from 40% to 100%
of the maximum allowed speed vm . Thus, a vehicle keeps this random initial speed
until it enters the communication region and then it either follows another vehicle
or is confirmed by ICA with a feasible DTOT. The maximum acceleration (amax )
and deceleration (amin ) rates for vehicles that are used in simulations are 2 m/s2
and 4.5 m/s2 , respectively. The size of a vehicle used in simulations is 5 meters
long and 1.8 meters wide. The distance from the enter line of the communication
region to that of the intersection region is set as 50 m. The time step that is used
in simulations is 0.05 seconds. In most cases, a simulation terminates when the
simulation time reaches 10 minutes.
In our simulations, vehicles are spawned according to several random variables in
order to generate various traffic volumes as well as traffic patterns. Specifically, pV is
the probability that a vehicle is spawned. pL , pS , pR are the probabilities for this new
vehicle to have a route of left-turning, through or right-turning. Thus, by adjusting
pV , we can generate various traffic volumes. As shown in Table 4.1, we set pL = 0.2,
pS = 0.6, and pR = 0.2 for all traffic volume cases to generate 20% of all incoming
vehicles for left turing, 60% for going straight, and the other 20% for right turning.
We use three random seeds to generate three different intersection traffic patterns
for each traffic volume. Thus, to obtain simulation data for each traffic volume, we
run three simulations with different traffic patterns for each simulation and then use
the averages of these simulation results as the result for each traffic volume case.
The intersection crossing traffics generated in most of our simulations are balanced

48

Table 4.1: Parameters used for various traffic volumes and patterns. (∗ Expected
number of vehicles per 10 minutes.)
Parameter
Traffic volumes∗
pV
pL
pS
pR
Random seeds

Value
100 / 200 / 300 / 400 / 500
0.03 / 0.06 / 0.08 / 0.11 / 0.14
0.20
0.60
0.20
12 / 21 / 66

traffics in the sense that the numbers of vehicles generated in each incoming road
are about the same. However, for a simulation to show the starvation free property
of the proposed DICA algorithm, the intersection traffic is purposely designed to
be unbalanced where the number of vehicles for minor approaching roads is roughly
30% of the vehicles on major roads.
In the following discussion on our simulation results, simulation time means the
simulated time used in simulation program and computation time, which will be
discussed later in Section 4.3.2, means the actual elapsed time that it takes for a
computer to run a simulation. Also, in Section 4.3.2, the traffic control performance
of the enhanced DICA is compared with that of a traffic light algorithm with fixed
cycles. To have a comparable traffic light program, we computed the optimal signal
cycles for different traffic volume cases by using the exponential cycle length model
C0 = 1.5Le1.8Y from [74]. In the model, L represents the total lost time within
the cycle. The lost time for each phase is assumed to be 4 seconds [75]. Thus,
L = 4 × 4 s = 16 s. Y is the sum of critical phase flow ratios. The duration of the
yellow light of each phase is 3 seconds.
All simulations were run on a 64bit Windows computer, and its processor is Intel(R) Core(TM) i7-4770 CPU @ 3.40 GHz with 8 GB RAM. The interface programs
with SUMO were coded in Python.

49

4.3.2

Simulation Results

Computation times and performances of three different traffic patterns for all five
volume cases are recorded from simulations.

Computation Time
Figure 4.3 (a) compares the computation times of the original DICA, the enhanced
DICA, and the optimized traffic light algorithm. Figure 4.3 (b) shows how much
computational improvement was made through each computational improvement
technique discussed in Sections 4.2.1, 4.2.2, 4.2.3, and 4.2.4. Note that since the
computational improvement technique in Section 4.2.4 is implemented based on the
computational improvement technique in Section 4.2.2, we had to combine techniques from both Sections 4.2.4 and 4.2.2 to show the improvement due to the
technique in Section 4.2.4 indirectly. Here, we show the computation times comparison for only one traffic volume case with 300 vehicles per 10 minutes since the
10

10

Original DICA
3.2.1
3.2.2
3.2.3
3.2.4 + 3.2.2

Original DICA

Optimized Traffic Light

1

0.1

Computation Time (log h)

Computation Time (log h)

Enhanced DICA

1

0.1

0.01

300
Traffic Volume
(number of vehicles per 10 minutes)

300
Traffic Volume
(number of vehicles per 10 minutes)

(a)

(b)

Figure 4.3: Computation times comparison for traffic volume with 300 vehicles per
10 minutes. (The symbol 3.2.x represents the improvement technique in Section
4.2.x where x = { 1, 2, 3, 4 }.) (a) original DICA with different algorithms (b)
original DICA with different improvement techniques

50

trends for other volume cases are similar. The vertical axis in Figure 4.3 is the
computation time in hour unit which is represented in logarithmic scale. As shown
in Figure 4.3 (a), the enhanced DICA that implements all improvements discussed
in Section 4.2 takes significantly less computation time, i.e. only 0.4% computation
time of the original algorithm. When we apply each computational improvement
technique individually, our result shows that it takes about 11% of the computation time of the original DICA with the technique in Section 4.2.1, 59% with the
technique in Section 4.2.2, 13% with the technique in Section 4.2.3, and 6% with
techniques in Sections 4.2.2 and Section 4.2.4 together. If we combine all of these
individual improvements altogether to estimate the collective improvement, then we
have about 0.45% computation time of the original DICA which is similar to the
computation time result with the enhanced DICA in which all these techniques are
implemented.
Table 4.2 compares the computation times between the enhanced DICA and the
optimized traffic light algorithm for all five traffic volume cases. From the results
shown in the table, we note that the computation time for the optimized traffic light
algorithm gradually increases as the traffic volume increases. However, since the optimized traffic light algorithm has O(1) computational complexity, its computation
time cannot be affected by the number of vehicles around an intersection. Thus,
roughly speaking, one can say that the computation time of the optimized traffic
light for a particular traffic volume case is in fact the time required for the simulation
software SUMO to run a simulation with the number of vehicles for that particular
traffic volume case. Therefore, the actual computation time of the enhanced DICA
for a particular traffic volume case can be roughly approximated by subtracting the
computation time of the optimized traffic light for the case from the computation
time of the enhanced DICA presented in the table. For example, for the traffic volume with 500 vehicles, the actual computation time for the enhanced DICA can be

51

Table 4.2: Computation time comparison between enhanced DICA and optimized
traffic light
Traffic volume
(Number of vehicles per 10 minutes)

100

200

300

400

500

Optimized Traffic light (h)
Enhanced DICA (h)

0.014
0.011

0.017
0.024

0.020
0.026

0.024
0.042

0.027
0.058

approximated as 0.031(= 0.058 − 0.027) hours which is 1.86 minutes. Note that this
1.86 minutes is the computation time taken by the algorithm to handle 500 vehicles.
Thus this in turn implies that it takes only 0.2232 seconds to handle each vehicle.
An exception to this approximation is the case with 100 vehicles traffic volume case
where the computation time for optimized traffic light takes longer time than that
of the enhanced DICA. The reason for this result can be understood by considering
the fact that, in such a low traffic volume situation, the average number of vehicles
to be simulated by SUMO at each simulation time step is smaller in the enhanced
DICA case since vehicles are crossing an intersection much faster without waiting at
an intersection under the enhanced DICA than the optimized traffic light as shown
in Section 4.3.2.

Liveness and Safety
Although we have theoretically showed the liveness of DICA, it is better to have
simulation results that support the theory. Since the simulation in this section is only
a verification, we run a simulation with 10, 000 vehicles instead of giving a restriction
on the simulation time. The simulation ends after all 10, 000 vehicles have exited
the simulation scene. We recorded the number of vehicles that are waiting to cross
the intersection at each simulation time step and plot the number profile in Figure
4.4. As shown in the figure, the number of vehicles drops to zero in almost a linear
way within a finite time which demonstrates that every vehicle was able to cross
the intersection eventually which proves the proposition 1 in Section 4.1. We also

52

10000
9000
8000

Number of Vehicles

7000
6000
5000
4000
3000
2000
1000
0

0

2000

4000

6000
8000
Simulation Time (s)

10000

12000

Figure 4.4: The number of vehicles which wait to cross the intersection over time.
performed a set of simulations for the case of unbalanced traffic situation where the
number of vehicles on minor roads is only 30% of that of major roads to demonstrate
the fairness of DICA. To show the fairness of the algorithm, we recorded the average
trip times for major roads and minor roads respectively for every traffic volumes.
As shown in Table 4.3, one can find that the average trip time of the minor roads
is about the same as that of the major roads. This shows that there is not a case
that some vehicles cannot get confirmation or will experience a very long time to be
confirmed which demonstrates that DICA is starvation free.
To validate the safety property (i.e., collision freeness) of DICA through simulation, we computed the inter-vehicle distance between every pair of vehicles within an
intersection at every second in simulation time. Since each vehicle is represented as

Table 4.3: Average trip time comparison between major roads and minor roads in
an unbalanced traffic
Traffic volume
100 200 300 400 500
(Number of vehicles per 10 minutes)
Average trip time on major roads (s)
Average trip time on minor roads (s)

53

6.17
6.21

6.60
6.57

7.38
7.38

8.15
7.90

10.15
9.63

a polygon, a 5 m long and 1.8 m wide rectangle more precisely, we obtained this data
based on an algorithm of the shortest distance calculation between two polygons.
A histogram of the recorded inter-vehicle distances is shown in Figure 4.5. Clearly,
the inter-vehicle distance must be less than or equal to zero if two vehicles are in a
collision and must be positive otherwise. As one can see from the figure, there is no
instance observed throughout the entire simulation with less than 1m inter-vehicle
distance, which is a clear indication that there is no collision inside the intersection.
Note that Figure 4.5 is demonstrating the safety of the DICA algorithm, the safety
problem that vehicles cannot follow confirmed DTOT correctly pertaining to the
robustness of DICA will be studied in our future work.

Control Performance
The overall traffic control performance of the enhanced DICA is also evaluated and
compared with that of the optimized traffic light algorithm based on the following
performance measures. For each vehicle, we recorded the trip time that is the time
taken for a vehicle from the moment when it enters into the communication region

Number of Instances*

600
500

400
300
200
100
0
0-1

1-2
2-3
3-4
4-5
Inter-Vehicle Distance (m)

Above 5

Figure 4.5: Histogram of the inter-vehicle distance within the intersection. (* An
instance means the situation when a pair of vehicles are separated by the calculated
inter-vehicle distance.)
54

Optimized Traffic Light

25

Enhanced DICA

20

Throughput

Average Trip Time (s)

30

15
10
5
0
100

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%

Optimized Traffic Light
Enhanced DICA

100

500

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

(b)
Standard Deviation of Trip Time
(s)

Effective Average Trip Time (s)

(a)
30

Optimized Traffic Light

25

Enhanced DICA

20
15
10
5
0
100

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

500

500

18
16
14
12
10
8
6
4
2
0

Optimized Traffic Light
Enhanced DICA

100

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

500

(d)

(c)

Figure 4.6: Performance comparison between enhanced DICA and optimized traffic light. (a) average trip time (b) throughput (c) effective average trip time (d)
standard deviation of trip time
of an intersection until the vehicle completely crosses the intersection region. From
the recorded trip time data for all crossed vehicles, we calculated several related
statistic information which is the average trip time and the standard deviation of
trip time. Besides these trip time related performance measures, we also calculated
the percentage of all crossed vehicles’ number against the total number of generated
vehicles, which we call the throughput. However, note that neither the average trip
time nor the throughput alone is sufficient to correctly evaluate the performance
of an algorithm. In fact, both of these measures should be considered together
to correctly compare and evaluate the performances of different intersection traffic
control algorithms. For this reason, we calculated the ratio of average trip time
to throughput, which we call the effective average trip time, and believe that this
could show the performance of an algorithm better. Comparison of the performance

55

between the enhanced DICA and the optimized traffic light control algorithm is
shown in Figure 4.6. From this result, we can see that, since the throughputs of
the two algorithms are always similar, the profiles of average trip time and effective
average trip time also show similar trends. The enhanced DICA always performs
better than the optimized traffic light for the first four traffic volume cases. In the
case of the traffic volume with 500 vehicles, the average trip time performance of
the enhanced DICA becomes closer to that of the optimized traffic light. Also, the
enhanced DICA has a bit larger standard deviation of trip time than the optimized
traffic light. In short, the enhanced DICA performs much better than the optimized
traffic light from low to medium traffic volume cases while its performance becomes
worse and closer to the performance of the optimized traffic light for heavy traffic
volumes.
We note that this result is mainly due to the fundamental difference between
individual vehicle based traffic coordination algorithms and traffic flow based coordination algorithms. To see this, we can consider a heavy traffic situation when all
incoming roads are congested. In such a situation, we know that most vehicles start
to cross an intersection at rest when they are allowed to cross the intersection either by green light under traffic light algorithm or confirmation under the proposed
DICA. Under a traffic light control, if a vehicle is crossing an intersection, then it
is highly likely that a few more following vehicles can also cross the intersection
without being stopped. However, in the case when vehicles are controlled by an individual vehicle based coordination algorithm like our enhanced DICA, it is possible
to have a situation where vehicles from different roads are permitted alternatively to
cross an intersection, which inevitably results in more frequent stops than the case
of traffic light control. This is the reason why the enhanced DICA is performing
worse and closer to the optimized traffic light in the heavy traffic volume situation.
In fact, this result reveals an important point that to achieve the best throughput

56

performance, it is necessary to combine both strategies: an individual vehicle based
coordination in normal traffic volume and a traffic flow based coordination in a congested situation. According to this result, we are currently developing algorithms
that incorporate the advantage of traffic flow based algorithms when congested into
the proposed enhanced DICA.
Another simulation was performed to validate the transient traffic control performance of DICA when the traffic volume is changing. We run a simulation with
20 minutes long simulation time during which the traffic volume increases from the
case of 100 vehicles to 500 vehicles per 10 minutes. At each simulation time step,
the ratio of the vehicle number generated to the number of vehicles that have exited the intersection, which we call the flow rate ratio, was calculated to see how
much congestion can occur and also how long it takes to address the congestion.
The flow rate ratio measured during the simulation time is plotted in Figure 4.7.
In this figure, if the flow rate ratio is close to 1, then it means that all vehicles
approached an intersection have already crossed the intersection and there are no
vehicles waiting to cross at that time. The simulation time starts from 300 s in the

1.5
Optimized Traffic Light
Enhanced DICA

1.45
1.4

Flow Rate Ratio

1.35
1.3
1.25
1.2
1.15
1.1
1.05
1
300

400

500

600

700
800
900
Simulation Time (s)

1000

1100

1200

Figure 4.7: Flow rate ratio when traffic volume changes from 100 to 500.

57

figure since the flow rate ratio needs some time to be stable. From the figure, we
can also see that before the increase of the traffic volume, the flow rate ratios of the
two algorithms are very similar. After 600 s at when the traffic volume is changed
to the 500 vehicles case, the flow rate ratio of the optimized traffic light increased
a lot. Figure 4.7 shows that DICA is more resilient to the change of traffic volume
than the optimized traffic light.

4.4

Conclusion

In this chapter, We analyzed the computational complexity of the original DICA
and enhanced the algorithm so that it can have better overall computational efficiency. Simulation results show that the computational efficiency of the algorithm
is improved significantly after the enhancement and the properties of starvation free
and safety are guaranteed. We also validated that the overall throughput performance of our enhanced DICA is better than that of an optimized traffic light control
mechanism in the case when the traffic is not congested.

58

Chapter 5

Reactive DICA: an Approach
for Expedited Crossing of
Emergency Vehicles
The problem of evacuating emergency vehicles as quickly as possible through autonomous and connected intersection traffic is addressed in this chapter. DICA
is augmented to allow emergency vehicles cross intersections faster and keep the
influence on other vehicles’ travel as minimum as possible.

5.1

Reactive DICA

The problem we want to solve is that how to let EVs which are driven autonomously
cross an intersection as soon as possible under the connected and autonomous traffic
environment. In the mean time, we aims to keep all other vehicles having similar
travel times as when there are no EVs in the traffic. In short, our objective is to
evacuate EVs through an intersection as quickly as possible while other vehicles’
travel times are minimally affected. Note that for simplicity the term emergency

59

vehicle in this dissertation means a vehicle in an emergency status (i.e. with siren
and the lights on). Same assumptions with our previous work [76, 77] are employed
in this problem. Overtaking and lane-changing inside the communication region
are not allowed which means that vehicles on each lane will keep its lane once it
enters the communication region. As an approach to give preference to EVs in
autonomous traffic, we give priority to EVs in an intersection crossing traffic by
optimizing the sequence of crossing vehicles. Also, since we are augmenting the
original DTOT-based intersection control algorithm, the new algorithm will only be
used to coordinate vehicles when there is an EV within the communication region
of an intersection while the crossing traffic is controlled the same way as before
when all vehicles are normal vehicles inside the communication region. Thus, the
entering of an EV activates the new algorithm, so we call the augmented DICA
the Reactive DICA (R-DICA). DICA is only taking care of head vehicles which
reduces computational complexity and communication load of ICA a lot. However,
unlike in DICA, more vehicles are needed to be considered in R-DICA in order
to allow EVs to cross an intersection as fast as possible. Specifically, all vehicles
on the lane of an EV which are ahead of the EV should be included in the set of
vehicles whose intersection crossing order are to be optimized. In the sequel, we
call all those vehicles as vehicles on EV’s lane. Thus, the set of vehicles that we
need to consider for vehicle ordering are all unconfirmed vehicles on EV’s lane and
also all confirmed vehicles which are not on EV’s lane. All these vehicles can be
divided into two types: vehicles whose DTOTs cannot be modified (vehicles who
have already entered the intersection or cannot make a stop at the enter line even
with maximum deceleration), and vehicles whose DTOTs could be changed (vehicles
who are stopping at the enter line of the intersection or are able to make a stop at
the enter line, or unconfirmed vehicles who are ahead of the EV). The sequence of
vehicles of the latter type is what we can optimize to expedite the crossing of EVs.

60

We define the set of these vehicles as S ∗ .
Roughly speaking, our approach for fast crossing of emergency vehicles is to
assign the highest priority to them and delay confirmation for all other normal
vehicles. Thus, incorporating a priority based ordering of vehicles into the basic
DICA framework would achieve this goal. To find such an optimal vehicle ordering,
we formulate an optimization problem based on the entrance time of vehicles which
is the time a vehicle enters the line of an intersection. Let P(S ∗ ) be the set of
ordered vehicle sequences (or simply called a sequence in the sequel) from the set
of vehicles in S ∗ . Then, if we use Tev to represent entrance time of vehicle v, a
reasonable objective function for our optimization problem would be:

min TeEV

(5.1)

P(S ∗ )

where TeEV is the entrance time of an EV at an intersection. Thus, to solve this
optimization problem, we first need to introduce an approach that determines the
entrance time of an EV.

(a)

(b)

(c)

Figure 5.1: Three different situations for separation time.
First, we note that some sequences in P(S ∗ ) can be eliminated if we impose some

61

constraints for optimal vehicle ordering. For example, the order of vehicles on EV’s
lane cannot be altered and hence should be preserved. Also, since all confirmed
vehicles S ∗ are able to stop before the enter line of an intersection, we can allocate
higher priorities for vehicles on EV’s lane than those in other lanes. We use P̄(S ∗ )
to denote the set of ordered sequences of vehicles satisfying these constraints. Now,
let us consider a sequence s in the set P̄(S ∗ ). Then, if we consider the first vehicle v
in the sequence s, then it is easy to see that the vehicle is always a head vehicle on
EV’s lane and has a confirmed DTOT. Hence the entrance time of this vehicle v can
be determined simply by its τ (O1v ) which is the time when the vehicle v occupies the
first occupancy of its DTOT. For any other vehicles which are not the first vehicle
in the sequence s, the way to compute its entrance times is a bit different. We need
a time interval between any two successive vehicle in a sequence to ensure safety.
This time interval is called separation time τs . In this chapter, as shown in Figure
5.1, we define three separation times for different situations between two vehicles.

τs =

where symbols





δc




δs






0

vi ⊗ vj Figure 5.1 (a), or
vi ≺ vj or vj ≺ vi Figure 5.1 (b), or
vi

(5.2)

vj Figure 5.1 (c)

and ⊗ are used to represent two vehicles’ routes are compatible

and conflicting respectively. vi ≺ vj represents that vehicles vi and vj are on a
same lane and vi is following vj . The separation time’s value depends on pavement
conditions, vehicle mechanical errors and weather conditions. The focus of this
chapter is proposing a coordination algorithm not the determination of these values.
Thus, we just approximate the values from current empirical estimations which is
widely accepted [78]. Then the expression to compute the entrance time of v j which
is not the first vehicle v 1 in the sequence is:

62

Tej = max{Taj , Tei + τs }

(5.3)

where v i is the immediate predecessor of v j in the sequence, Taj is the predicted
arrival time of the vehicle v j which is the shortest time for the vehicle to arrive at
the enter line of an intersection under the constraints of maximum acceleration and
speed without considering other vehicles in a traffic. Tei is v i ’s entrance time and
τs is the separation time between v i and v j . Starting from the second vehicle in
sequence, this equation is iteratively used to compute the entrance time of of each
vehicle in the sequence until the entrance time of the emergency vehicle is computed.
Now the complete form of an optimization problem for optimal vehicle ordering
to minimize the entrance time of the EV is formulated as follows: Given predicted
arrival times Tavi for all vi ∈ S ∗ , find s∗ such that
s∗

=

min TeEV

(5.4)

s∈P̄(S ∗ )

s.t. |Tei − Tej | ≥

Tev ≥ Tav





0




δc






δs

vi

vj

vi ⊗ vj
vi ≺ vj or vj ≺ vi

∀v ∈ S ∗

A naive approach to solve the optimization problem in (5.4) is an exhaustive
search in all possible sequences that can be generated from the set S ∗ . If we suppose
that there are n numbers of vehicles in S ∗ (i.e. n = |S ∗ |) and there are nEV numbers
of vehicles on EV’s lane, then there are n!/nEV ! numbers of sequences in P(S ∗ ).
However, if n is becoming large, then the computational time and resources required
to solve the optimization problem are increasing significantly. Hence it might not
be an efficient approach to use an exhaustive search method when we want to solve

63

the problem (5.4) with many vehicles. Such computation issues of the problem
present the need to seek heuristic approaches which are good at solving complex
problems in a very short time compared with exhaustive search. Several heuristic
optimization approaches like genetic algorithm, ant colony system, artificial neural
networks exist in literature. [79] used permutation encoding scheme and solved the
flowshop scheduling problem with an objective of minimizing the makespan. [19]
proposed a genetic algorithm to optimize the groups of compatible vehicles in a
very short time. [80] and [81] reviewed many researches that genetic algorithms can
be used to solve job scheduling problems which can meet our requirements. Thus,
we also choose to use genetic algorithm (GA) to obtain optimal sequence of vehicles.
The high level architecture of R-DICA combining GA and DICA is shown in Figure 5.2. R-DICA activates GA when ICA detects an EV. Then ICA stop accepting
any confirmation of new vehicles which are detected after the EV. All vehicles who
belong to S ∗ are rearranged to obtain the optimal sequence for the EV’s crossing by
GA. Then ICA only confirms vehicles who are already included in the set S ∗ until
the EV exits the intersection. Once the EV is complete out of intersection, ICA
switchs back to use DICA to manage normal intersection crossing traffic.

5.2

Genetic Algorithm for Vehicle Ordering

In this section, we discuss the details of how GA is used to find the optimal vehicle
sequence in (5.4).
Genetic Algorithms, which have been widely used to solve problems in computer science, artificial intelligence, information technology and engineering, are
techniques of self-organized and self-adapting artificial intelligence mimicking the
evolutionary process of creatures in nature [80, 82]. A solution in GA is called an
individual which is encoded compactly to facilitate the processes of crossover and
mutation that are essential in a genetic algorithm. A group of individuals is called
64

a population in which some individuals are selected as parents to generate offspring
through crossover and mutation. Based on some features of each individual, some
individuals survive and others die among all the original population and new individuals. Individuals who correspond or near correct solution have a better chance
to survive during evolving since they have high objective values which is called fitness. Fitness function should be defined properly to evaluate each individual. As
introduced above, solutions in GA evolve to adapt the objective problem. Optimal
or near-optimal solutions are expected to be obtained after a certain number of
generations. In this chapter, we propose a GA to solve the complex traffic control
problem for emergency vehicles in a short time. Permutation encoding scheme is
used in the algorithm. And crossover and mutation operators suitable for permutation encoding scheme are devised. The proposed GA for vehicle ordering is shown
in Algorithm 4. Detailed discussion for permutation scheme, crossover, mutation,
etc. of the proposed GA are given in the following sections.

Detect a new vehicle

Yes

EV?

No

GA

DICA

Stop confirmation of new vehicles;
Confirm vehicles based on the optimal
order from GA.
No

Yes

EV exited?

Figure 5.2: Control flow diagram of ICA in R-DICA.

65

Algorithm 4 Genetic Algorithm for Vehicle Ordering
1: Generate Npop different individuals randomly for n vehicles in S ∗ → I
2: f easibilityCheck(I) → I
3: k = 0
4: j = 0
5: f itness best last = 0
6:

while k < Nmax and j < NnoChange do
crossOver(Pc , I) → I
9:
f easibilityCheck(I) → I
10:
mutation(Pm , I) → I
11:
f easibilityCheck(I) → I
7:

8:

12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

f itness best, individual best = f itness(I)
if f itness best > f itness best last then
j=0
else
j =j+1
end if
top Npop individuals → I
k =k+1
end while
Decode individual best
In the proposed GA, we first generate a random population I that contains Npop

individuals which are encoded by permutation scheme. The function f easibilityCheck()
takes a set of individuals and makes modification to the infeasible individuals. Feasible individual corresponds to a sequence of vehicles that does not violate the order
of vehicles on EV’s lane. After proper modification, the function returns a set containing individuals which are all feasible. The function crossOver() then perform
crossover on randomly selected pairs of individuals from the population I with a
probability Pc to generate new offspring. Then the feasibility of the offspring is
checked. Notice that after crossover, the number of individuals is larger than Npop .
Mutation on the produced offspring with probability of Pm is done by function
mutation(). The mutated individuals also need to be checked for feasibility and
modified if needed. Based on given conditions, each individual in I is evaluated by

66

a fitness function f itness() which computes the reciprocal of the entrance time of
the emergency vehicle in that individual. The highest fitness value and the corresponding individual are recorded. Notice that the fitness can also be obtained by
using other metrics like the exit time of the EV, or the trip time of the EV, etc.
These metrics will give us similar results. We choose the entrance time because we
have the predicted arrival time for each vehicle. Thus, it is easy to implement the
algorithm. Then we use the top Npop individuals from the original population and
offspring to form the new population. If any of the stopping criteria (maximum
number of iterations or the best solution is not updated for a certain number of generations) are met, then the algorithm terminates. Otherwise the algorithm repeats
the steps inside the while loop.

5.2.1

Chromosome Encoding and Feasibility Check

v1

v2

v3

v4

v7

EV

v5

v6

Figure 5.3: An example of the permutation encoding scheme, the left-most vehicle
has the highest priority while the right-most one has the lowest priority.
Instead of using the popular binary encoding scheme for genetic algorithms, we
choose to use permutation encoding scheme which is more suitable to find an optimal
sequence for vehicle ordering. As shown in Figure 5.3, the individual corresponds to
a sequence of vehicles which is {v 1 , v 2 , v 3 , v 4 , v 7 , EV, v 5 , v 6 } with v 1 on the leftmost
is the first and the rightmost vehicle v 6 is the last one. Different chromosomes denote
different sequences of vehicles. Once an individual is created, it is not always true
that the corresponding sequence is a feasible one since vehicles’ order on EV’s lane
cannot be altered. Every new generated individual should be checked against the
sub-sequence of vehicles on EV’s lane for feasibility. Figure 5.4 is provided to have
a visual impression of the situation when vehicles’ sequence needs to be optimized.
67

v4
v7

v1

v3

EV

v2

v6

v5

Intersection region

Communication region

Figure 5.4: Example situation of vehicles whose sequence to be optimized in intersection space, note: vehicles on EV’s lane are: v 1 , v 3 , EV
In the figure, v 1 , v 3 and EV are the vehicles on EV’s lane whose order could not be
altered. And note that except vehicles on EV’s lane, all other vehicles who are not
a head vehicle are not part of the sequence. The vehicles from South and West who
are not head vehicles are such vehicles that will be confirmed only after EV exits. If
an individual is not feasible, the corresponding bits of vehicles on EV’s lane should
be changed to conform the correct relative order. The function f easibilityCheck()
is making the corresponding modifications on an infeasible individual. An example
of adjustment according to the sequence of vehicles who are ahead of the EV on the
same lane is shown in Figure 5.5.

68

5.2.2

Crossover and Mutation

Two individuals perform crossover to generate offspring if they are selected to be
parents. The offspring inherit features (i.e. gene structures) from their parents.
Different encoding scheme has different crossover operator since they have different
gene structures. For the most popular binary encoding scheme, it is easy to do
crossover and mutation since a chromosome only contains binary bits. For our
permutation encoding scheme, we choose to apply one-point crossover [82] which is
implemented in the function crossOver(). As shown in Figure 5.5, the same bits
may exist in one chromosome after the parts behind the randomly chosen position
are swapped. In the second step in the figure, the two children have same bits
{v 2 , v 3 } and {v 5 , v 6 } respectively. To generate correct chromosomes, we adjust
the chromosome of one child by swapping those same bits from another child’s
chromosome while preserving the relative ordering of parents. Note that the new
chromosomes may also not be feasible since the order of vehicles on EV’s lane in a
chromosome may not be the same as the actual order. If this happens, since the
order of the vehicles on EV’s lane cannot be changed, we manually adjust the relative
order of vehicles to be the correct order to have a feasible chromosome. For example
in Figure 5.5, we adjust the order of v 1 and v 3 for the second child in the last step.
Feasibility check and adjustment are done by the function f easibilityCheck().
Similar to probabilistically selecting two individuals for crossover, we apply
mutation on produced chromosomes based on a given probability by the function
mutation(). Different with binary encoding scheme’s mutation which could be done
by simply changing the value of a randomly selected bit from 1 to 0 or 0 to 1, our
permutation encoding scheme exchanges the bits on two randomly chosen positions
to obtain a new chromosome. As shown in Figure 5.6, positions of v 2 and EV are
randomly chosen to exchange values and feasibility check based on vehicles’ order
on EV’s lane is performed after mutation.
69

Vehicles’ sequence on EV’s lane:

v1

v3

Adjust if same bits exist

EV

Parents:

Children:

v1

v2

v3

v4

v7

EV

v5

v6

v1

v5

v6

v2

v7

v4

v3

EV

v6

v5

v1

v2

v7

v4

v3

EV

v2

v3

v1

v4

v7

EV

v5

v6

v1
6

v

v2
5

v

Feasibility check and
adjustment

Swap the second part

Children:
v3
1

v

v24
4

v

v7

EV
v4

7

v

EV

v35

Children:

v6
EV

5

v1

v5

v6

v2

v7

v4

v3

EV

v2

v1

v3

v4

v7

EV

v5

v6

6

v

v

Figure 5.5: An example of one-point crossover. Relative ordering of parents is
preserved when the chromosomes are adjusted due to the existence of same bits.
Feasibility is checked for the two children based on vehicles’ sequence on EV’s lane
and adjustments are made.
Vehicles’ sequence on EV’s lane:
v1

v1

v2

v3

v3

EV

v7

v4

EV

v5

v6

v5

v6

Mutation
v1

EV

v3

v4

v7

v2

Feasibility check
and adjustment

v1

v3

EV

v4

v7

v2

v5

v6

Figure 5.6: An example of mutation. Feasibility is checked for the mutated chromosome based on vehicles’ sequence on EV’s lane and adjustment is made. v 2 and
EV are randomly chosen to swap to perform mutation. EV is swapped with v 3 to
conform vehicles’ sequence on EV’s lane.

5.2.3

Fitness and Generating New Generation

The reciprocal of the entrance time of the emergency vehicle is defined as the fitness
of an individual in our proposed GA. The entrance time of the emergency vehicle
70

can be determined as discussed in Section 5.1. For an individual in a population,
the higher the fitness is, the closer the corresponding solution is to the optimal
solution. Among all individuals in the population and the offspring produced, the
top Npop individuals with respect to the fitness values are selected to form the next
generation.

5.2.4

Stopping Criterion

The constant Nmax represents the number of maximum generations and NnoChange
represents the number of continuous generations that solutions are not changed. As
shown in In Algorithm 4, if the best solution is not updated after NnoChange generations or the Nmax th generation has been reached, then the algorithm terminates
and stops searching a better solution.

5.3

Simulation

The performance of the proposed optimization approach for EVs is evaluated against
the DICA and a reactive traffic light algorithm which is explained below. All simulations are implemented in an open-source traffic simulator SUMO (Simulation of
Urban MObility) [83]. The default traffic management for intersections in SUMO is
not used and the control algorithms are programmed as Python applications. The
TraCI is used for the interaction between the Python applications and SUMO. Configurations for intersections in the simulation and corresponding results are described
in this section, followed by discussions on obtained results.

5.3.1

Simulation Setup

Extensive simulations of different traffic volumes are performed on an isolated perfect 4-way intersection where each approach has three incoming lanes and two exit
lanes. Similar to real intersections in the United States, among the three incoming
71

lanes, the left-most lane is dedicated for left-turn vehicles, and through vehicles can
use the other two lanes. The right-most lane can also be used by right-turn vehicles.
All roads have the speed limit of vm = 70km/h. The maximal acceleration (amax )
and deceleration (amin ) for all vehicles are set to be 2m/s2 and −4.5m/s2 . In the
simulation, for simplicity we used the same size for normal vehicles and EVs that
they both have 5 meters length and 1.8 meters width. We let vehicles approach an
intersection with different speeds when they enter into the communication region of
the intersection to make the simulation more realistic. In detail, when a new vehicle
is spawned outside of the communication region, the speed of the vehicle is set with
a random value within the range from 40% to 100% of the maximum allowed speed
vm . In those cases where vehicles need to stop just before the enter line of the
intersection region to avoid potential collisions with other confirmed vehicles, the
distance between the enter line of the communication region and the enter line of
the intersection region should be long enough for a vehicle to be able to stop from
maximum allowed speed vm . Thus, it is easy to conclude that the distance should
2 /(2a
be at least −vm
min ) ≈ 42.01m. So, in simulation, we set the distance between

the enter lines of the communication region and the intersection region as 50m.
Vehicles are generated randomly on each road with a randomly assigned intersection route. Every generated vehicle has the probability of pEV to be an EV,
otherwise it will be a normal vehicle. In our simulation, an emergency vehicle is
generated only when there is no such vehicle inside the communication region. To
create variations on the traffic pattern, we use several different random seed numbers to generate different traffic patterns and make the simulations reproducible.
Table 5.1 summarizes the parameters used for various traffic volumes and patterns
that were employed in many of our simulations where pV corresponds to traffic
volumes, pL , pS and pR are the probabilities for a generated vehicle to take Left,
Straight, and Right routes respectively. For every traffic volume, we run three sim-

72

Table 5.1: Parameters used for various traffic volumes and patterns. (∗ Expected
number of vehicles per 10 minutes.)
Parameter

Value

Traffic volumes∗
pV
pL
pS
pR
pEV
Random seeds

100 / 200 / 300 / 400 / 500
0.03 / 0.06 / 0.08 / 0.11 / 0.14
0.20
0.60
0.20
0.02
12 / 21 / 66

ulations with different traffic patterns and then use the averages of these simulation
results as the result for each traffic volume case. For the genetic algorithm, we set
Npop = 100, NnoChange = 10, Pc = 0.85, Pm = 0.05 and Nmax = 100.
Simulations were run by 0.05s time step. We terminate each simulation when
the simulation time reaches one hour. The simulation time here represents the
simulated time in simulation programs. And the computation time which will be
used in the following discussion is the time that a computer takes to run a simulation
program. All simulations were run on a 64bit Windows computer, and its processor
is Intel(R) Core(TM) i7-4770 CPU @ 3.40 GHz with 8 GB RAM.

If an EV exists

Lights for conflicting
lanes set to yellow
If an EV exists

Green

Yellow

Red

If an EV exists

Figure 5.7: Reactive traffic light diagram.

73

5.3.2

Reactive Traffic Light

To show the effectiveness of the proposed R-DICA for emergency vehicles, a reactive
traffic light algorithm for emergency vehicles is implemented and tested. As shown
in Figure 5.7, the traffic light for the lane of an EV changes to green as quickly
as possible when an EV is detected on the boundary of communication region.
Arrows with single line represent the state transitions (i.e. conventional traffic light
algorithm) when there is no EV inside the communication region while arrows with
double lines show the actions the algorithm will perform if an EV exists. The
conventional traffic light algorithm we used is the default traffic light implemented
in SUMO which has 31, 13 and 83 seconds durations for green, yellow and red
light phases respectively. As shown in Figure 5.7, if the current status is yellow
or green when an EV is detected, the algorithm changes the light back to green or
just extends the green light for a fixed amount of time respectively. If the current
status of the lane is red when an EV enters the communication region, the algorithm
immediately sets the green lights of conflicting lanes to yellow and then the lane of
the EV will have green light after the yellow phase of the conflicting lanes. This
augmentation of reactive mechanism in traditional traffic light system certainly help
an EV to cross an intersection as quickly as possible.

5.3.3

Simulation Results

Performances of three different traffic patterns for all five volume cases are recorded
from simulations. Figure 5.8 shows a series of screenshots of simulation employing
R-DICA in SUMO when an EV (the vehicle in red) is crossing the intersection
from South. In the simulation, normal vehicles in yellow are not confirmed by
ICA while green normal vehicles are the confirmed ones. In Figure 5.8 (a), we
can see that R-DICA activated GA algorithm which establishes an optimal order
of vehicles to expedite the crossing of the EV. As one can note that in Figure 5.8
74

(a) and (b) the head vehicle on the right lane of West road is not confirmed which
means that this vehicle has a lower priority than the EV. All vehicles whose DTOTs
cannot be modified are confirmed vehicles. And head vehicles who have a higher

(a)

(b)

(c)

(d)

Figure 5.8: A series of screenshots of simulation which illustrates a situation when
an EV is crossing the intersection.

75

priority than the EV are confirmed. Figure 5.8 (b) and (c) show that the EV is
crossing the intersection unhindered while lower priority vehicles are waiting before
the intersection. As shown in Figure 5.8, as soon as the EV exits the intersection, all
head vehicles get confirmed which means R-DICA operates the same way as DICA.
The optimal vehicle-passing sequence from the genetic algorithm ensures the fast
crossing an intersection for the EV.

Computation Time
To show the computational efficiency of R-DICA using GA, we implemented RDICA in two different versions: One with GA and the other one with the Exhaustive Search (ES) method to solve the optimization problem. Computation times of
different volume cases are recorded for both methods. Simulation results are shown
in Table 5.2 where ‘N/A’ means that the computer was not able to complete the
simulation due to memory errors.
Table 5.2: Computation time comparison between ES and GA
Traffic volume
(Number of vehicles per 10 minutes)

100

200

300

400

500

Computation time of ES (h)
Computation time of GA (h)

0.05
0.05

0.52
0.15

N/A
0.35

N/A
0.65

N/A
0.72

From the result, we can see that R-DICA with GA has definite advantages over
R-DICA with ES in terms of computational efficiency. As shown in the table, the
exhaustive search method only works for light traffic volumes while it has memory
issues for traffics of higher volumes.

Performance of EVs
The following performance measures are obtained to compare the performance of
R-DICA with DICA and the reactive traffic light: a vehicle’s trip time (τ ) is defined
as the time taken for a vehicle from the moment when it enters into the communi76

cation region of an intersection until the vehicle exits the intersection. Based on the
measurement of τ for all crossed vehicles, we obtained the average trip time (τ̄ ) and
the maximum trip time (τm ) which show the performance of the crossed vehicles.
Besides these performance measures, we also calculated throughput (ρ) which is the
percentage of all crossed vehicles against total number of generated vehicles. We
calculated the rate of average trip time to throughput, which we call the effective
average trip time (τ̄e ). Detailed explanation for this metric can be found in [76].
As shown in Figure 5.9, the average trip times of EVs in all three algorithms:
DICA, R-DICA and the reactive traffic light are compared. For traffic volumes
from 100 to 400, R-DICA has least average trip time of EVs than the other two
algorithms. Especially in light traffic volumes, R-DICA reduces the EVs’ average
travel time by more than 50% from the reactive traffic light. However, the algorithm
has a bit longer average trip time for EVs than that of reactive traffic light in 500
traffic volume. The worst case for EVs’ travels is illustrated by the maximum trip
time of EVs in (b) of Figure 5.9. The maximum trip time of R-DICA increases
and becomes greater than that of the reactive traffic light. Both average trip time
and maximum trip time of EVs for DICA are increasing along the volumes. One

Average Trip Time of EVs (s)

40

Maximum Trip Time of EVs (s)

may note that the average trip time and the maximum trip time of the reactive

DICA

35

R-DICA

30

Reactive Traffic Light

25
20
15
10
5
0
100

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

500

120

DICA

100

R-DICA
Reactive Traffic Light

80
60
40
20
0
100

(a)

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

500

(b)

Figure 5.9: Performance comparison of EVs for DICA, R-DICA, and the reactive
traffic light: (a) average trip time, (b) maximum trip time

77

Effective Average Trip Time
of Normal Vehicles (s)

Throughput of Normal Vehicles

99.50%
99.00%
DICA
R-DICA
Reactive Traffic Light

98.50%
98.00%
97.50%
97.00%
100

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

50
45
40
35
30
25
20
15
10
5
0

DICA
R-DICA
Reactive Traffic Light

100

500

(a)

200

300
400
Traffic Volume
(number of vehicles per 10 minutes)

500

(b)

Figure 5.10: Performance comparison of normal vehicles for DICA, R-DICA, and
the reactive traffic light: (a) throughput, (b) effective average trip time
traffic light keep almost the same with the increase of the traffic volume. Through
observation of the simulations, part of this is because too many vehicles accumulate
before the intersection when the lane of the EV is under red light. At this situation,
the EV is not detected and is stopping outside the communication region. When
the light for the lane of the EV turns green, the EV accelerates from rest to enter
the communication region which results in a higher speed for the EV. Thus, for
the heavier traffic volumes, EVs always have a higher speed when detected and are
expedited to cross by preference. The trip time within the communication region is
then reduced compared with R-DICA.

Performance of Normal Vehicles
Comparison of the performance for normal vehicles for all three algorithms is shown
in Figure 5.10. From this result, we can see that the throughput and effective
average trip time of R-DICA are nearly the same as those of DICA which shows
that the performance of normal vehicles is minimally affected by EVs. Both the
throughput and effective average trip time of normal vehicles become worse with
the increase of traffic volumes. This is consistent with the result in our previous
work [76, 77]. Also, one can see from Figure 5.10 that the reactive traffic light has
steady and worse performance for normal vehicles than the other two algorithms.
78

To investigate more about the negative effect of prioritizing EVs on other normal
vehicles, we compare the maximum trip time of normal vehicles for DICA and RDICA in Table 5.3. The maximum trip time of R-DICA is very close to that of
DICA and their difference increases with traffic volumes. This shows that it will
bring more negative effect on normal vehicles to evacuate an EV in congested traffic.
Table 5.3: Comparison of maximum trip times of normal vehicles between DICA
and R-DICA
Traffic volume
(Number of vehicles per 10 minutes)
Maximum trip time of
normal vehicles: DICA (s)
Maximum trip time of
normal vehicles: R-DICA (s)

5.4

100

200

300

400

500

17.88

35.80

55.37

89.47

132.90

18.62

38.52

61.68

99.15

150.00

Summary

In this chapter, we have shown that the DICA algorithm can be augmented to allow
emergency vehicles to cross intersections faster. A genetic algorithm based approach
is proposed as part of the augmented algorithm, called R-DICA, to optimize the
sequence of vehicles which gives the emergency vehicle the highest priority and keeps
the influence on other vehicles’ travel times as minimum as possible. The R-DICA
operates the same way as DICA if there is no EV inside the communication region
and optimizes vehicle-passing sequence if an EV enters the communication region. A
reactive traffic light and DICA algorithms are also implemented for simulation and
their results are compared with R-DICA to evaluate the performance of R-DICA.
Simulation results show that R-DICA is effective to reduce travel times of EVs
and has better performance than the reactive traffic light for normal vehicles. We
conclude that the performance of normal vehicles is not noticeably affected based
on the simulation results of DICA and R-DICA.

79

Chapter 6

Conclusion and Future Work
This dissertation has presented several control algorithms for connected and autonomous intersection traffic. All algorithms are validated through extensive simulations. This chapter summarizes the dissertation briefly and gives potential future
work.

6.1

Conclusion

In Chapter 3, we developed an intelligent intersection control algorithm DICA employing the concept DTOT. V2I interaction protocol has been established for interactions between vehicles and intersection. The chapter introduced the concept of
DTOT by which ICA is able to manage limited intersection space at a more accurate
and efficient way. Theoretical analysis shows that DICA is free from deadlocks and
starvation problems. Simulation results show that our algorithm achieves less Effective Average Trip Time compared with concurrent intersection control algorithms.
In Chapter 4, we analyzed the computational complexity of the original DICA
and enhanced the algorithm so that it can have better overall computational efficiency. The enhancement was done through several computational techniques like
determining conflicting spaces offline, employing bisection method in time-conflict
80

checking, etc. Simulation results show that the computational efficiency of the algorithm is improved significantly after the enhancement and the properties of starvation free and safety are guaranteed. We also validated that the overall throughput
performance of our enhanced DICA is better than that of an optimized traffic light
control mechanism in the case when the traffic is not congested.
In Chapter 5, we have shown that the DICA algorithm can be augmented to allow
emergency vehicles to cross intersections faster. A genetic algorithm based approach
is proposed as part of the augmented algorithm, called R-DICA, to optimize the
sequence of vehicles which gives the emergency vehicle the highest priority and keeps
the influence on other vehicles’ travel times as minimum as possible. The R-DICA
operates the same way as DICA if there is no EV inside the communication region
and optimizes vehicle-passing sequence if an EV enters the communication region. A
reactive traffic light and DICA algorithms are also implemented for simulation and
their results are compared with R-DICA to evaluate the performance of R-DICA.
Simulation results show that R-DICA is effective to reduce travel times of EVs
and has better performance than the reactive traffic light for normal vehicles.We
conclude that the performance of normal vehicles is not noticeably affected based
on the simulation results of DICA and R-DICA.

6.2

Future Work

In the future, assumptions like perfect communication, accurate prediction of DTOT
can be relaxed and methods to deal with car failures will be studied to make the
algorithm more applicable to real situations.
In addition to giving priority to special vehicles e.g. emergency vehicles by
forming optimal sequence like R-DICA, R-DICA can be enhanced to allow special
vehicles’ faster crossings through efficient usage of intersection space. For example,
ICA may modify both occupancies positions and times of a vehicles DTOT in order
81

to form a passage for special vehicles.
We will study algorithms based on DICA on a network of intersections to have
a global optimal performance on a city level. Also, we will work to integrate the
grouping strategy used in traffic flow based intersection control algorithms into our
DICA to achieve better performances in more congested situations. DICA can
be generalized to work with mixed traffic where autonomous vehicles and humandriven vehicles coexist. More interesting and difficult problem could be including
pedestrians in the intersection traffic.

82

References
[1] K.-D. Kim and P. R. Kumar, “An mpc-based approach to provable systemwide safety and liveness of autonomous ground traffic,” IEEE Transactions on
Automatic Control, vol. 59, no. 12, pp. 3341–3356, 2014.
[2] R. Horowitz and P. Varaiya, “Control design of an automated highway system,”
Proceedings of the IEEE, vol. 88, no. 7, pp. 913–925, 2000.
[3] DARPA,

“The

darpa

urban

challenge,”

2007.

[Online].

Available:

http://archive.darpa.mil/grandchallenge/
[4] K. Bengler, K. Dietmayer, B. Farber, M. Maurer, C. Stiller, and H. Winner,
“Three decades of driver assistance systems: Review and future perspectives,”
IEEE Intelligent Transportation Systems Magazine, vol. 6, no. 4, pp. 6–22,
2014.
[5] J. Markoff, “Google cars drive themselves, in traffic,” The New York Times,
vol. 10, no. A1, p. 9, 2010.
[6] P. Tientrakool, Y.-C. Ho, and N. F. Maxemchuk, “Highway capacity benefits
from using vehicle-to-vehicle communication and sensors for collision avoidance.”

IEEE, 2011.

[7] L. W. Chen and C. C. Chang, “Cooperative traffic control with green wave
coordination for multiple intersections based on the internet of vehicles,” IEEE
83

Transactions on Systems, Man, and Cybernetics: Systems, vol. PP, no. 99, pp.
1–15, 2016.
[8] A. Konar, I. G. Chakraborty, S. J. Singh, L. C. Jain, and A. K. Nagar, “A
deterministic improved q-learning for path planning of a mobile robot,” IEEE
Transactions on Systems, Man, and Cybernetics: Systems, vol. 43, no. 5, pp.
1141–1153, Sept 2013.
[9] T.-H. Li and S.-J. Chang, “Autonomous fuzzy parking control of a car-like
mobile robot,” IEEE Transactions on Systems, Man, and Cybernetics-Part A:
Systems and Humans, vol. 33, no. 4, pp. 451–465, 2003.
[10] A. Mammeri, D. Zhou, and A. Boukerche, “Animal-vehicle collision mitigation
system for automated vehicles,” IEEE Transactions on Systems, Man, and
Cybernetics: Systems, vol. 46, no. 9, pp. 1287–1299, Sept 2016.
[11] A. Colombo and D. Del Vecchio, “Efficient algorithms for collision avoidance
at intersections,” in Proceedings of the 15th ACM international conference on
Hybrid Systems: Computation and Control.

ACM, 2012, pp. 145–154.

[12] S. Le Vine, A. Zolfaghari, and J. Polak, “Autonomous cars: The tension between occupant experience and intersection capacity,” Transportation Research
Part C: Emerging Technologies, vol. 52, pp. 1–14, 2015.
[13] E. Onieva, U. Hernández-Jayo, E. Osaba, A. Perallos, and X. Zhang, “A multiobjective evolutionary algorithm for the tuning of fuzzy rule bases for uncoordinated intersections in autonomous driving,” Information Sciences, vol. 321,
pp. 14–30, 2015.
[14] H. Jiang, Y. Zhang, Y. Chen, C. Zhao, and J. Tan, “Power-traffic coordinated
operation for bi-peak shaving and bi-ramp smoothing-a hierarchical data-driven
approach,” arXiv preprint arXiv:1712.00211, 2017.
84

[15] H. Kowshik, D. Caveney, and P. Kumar, “Provable systemwide safety in intelligent intersections,” IEEE transactions on vehicular technology, vol. 60, no. 3,
pp. 804–818, 2011.
[16] J. Lee and B. Park, “Development and evaluation of a cooperative vehicle intersection control algorithm under the connected vehicles environment,” IEEE
Transactions on Intelligent Transportation Systems, vol. 13, no. 1, pp. 81–90,
2012.
[17] J. Wu, A. Abbas-Turki, and A. El Moudni, “Cooperative driving: an ant colony
system for autonomous intersection management,” Applied Intelligence, vol. 37,
no. 2, pp. 207–222, 2012.
[18] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony
of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics,
Part B (Cybernetics), vol. 26, no. 1, pp. 29–41, 1996.
[19] F. Yan, M. Dridi, and A. El Moudni, “An autonomous vehicle sequencing
problem at intersections: A genetic algorithm approach,” International Journal
of Applied Mathematics and Computer Science, vol. 23, no. 1, pp. 183–200,
2013.
[20] F. Zhu and S. V. Ukkusuri, “A linear programming formulation for autonomous
intersection control within a dynamic traffic assignment and connected vehicle
environment,” Transportation Research Part C: Emerging Technologies, vol. 55,
pp. 363–378, 2015.
[21] D. Miculescu and S. Karaman, “Polling-systems-based autonomous vehicle
coordination in traffic intersections with no traffic signals,” arXiv preprint
arXiv:1607.07896, 2016.

85

[22] A. A. Malikopoulos and C. G. Cassandras, “Decentralized optimal control
for connected and automated vehicles at an intersection,” arXiv preprint
arXiv:1602.03786, 2016.
[23] K. Dresner and P. Stone, “A multiagent approach to autonomous intersection
management,” Journal of artificial intelligence research, vol. 31, pp. 591–656,
2008.
[24] ——, “Human-usable and emergency vehicle-aware control policies for autonomous intersection management,” in Fourth International Workshop on
Agents in Traffic and Transportation (ATT), Hakodate, Japan, 2006.
[25] D. Carlino, S. D. Boyles, and P. Stone, “Auction-based autonomous intersection management,” in 16th International IEEE Conference on Intelligent
Transportation Systems (ITSC 2013).

IEEE, 2013, pp. 529–534.

[26] M. Vasirani and S. Ossowski, “A market-inspired approach for intersection
management in urban road traffic networks,” Journal of Artificial Intelligence
Research, vol. 43, pp. 621–659, 2012.
[27] M. W. Levin, H. Fritz, and S. D. Boyles, “On optimizing reservation-based intersection controls,” IEEE Transactions on Intelligent Transportation Systems,
vol. 18, no. 3, pp. 505–515, 2017.
[28] S. R. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “Vehicular networks for
collision avoidance at intersections,” in SAE 2011 world congress and exhibition,
2011.
[29] R. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “Intersection management
using vehicular networks,” SAE Technical Paper, Tech. Rep., 2012.

86

[30] S. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “Reliable intersection
protocols using vehicular networks,” in Cyber-Physical Systems (ICCPS), 2013
ACM/IEEE International Conference on.

IEEE, 2013, pp. 1–10.

[31] R. Azimi, G. Bhatia, R. R. Rajkumar, and P. Mudalige, “Stip: Spatio-temporal
intersection protocols for autonomous vehicles,” in ICCPS’14: ACM/IEEE 5th
International Conference on Cyber-Physical Systems (with CPS Week 2014).
IEEE Computer Society, 2014, pp. 1–12.
[32] F. J. Martinez, C.-K. Toh, J.-C. Cano, C. T. Calafate, and P. Manzoni, “Emergency services in future intelligent transportation systems based on vehicular
communication networks,” IEEE Intelligent Transportation Systems Magazine,
vol. 2, no. 2, pp. 6–20, 2010.
[33] E. Oliveira and N. Duarte, “Making way for emergency vehicles,” in Proceedings
of the 2005 European Simulation and Modelling Conference, vol. 128. Citeseer,
2005, p. 135.
[34] W. Viriyasitavat and O. K. Tonguz, “Priority management of emergency vehicles at intersections using self-organized traffic control,” in Vehicular Technology
Conference (VTC Fall), 2012 IEEE.

IEEE, 2012, pp. 1–4.

[35] X. Qian, J. Gregoire, F. Moutarde, and A. De La Fortelle, “Priority-based
coordination of autonomous and legacy vehicles at intersection,” in 17th International IEEE Conference on Intelligent Transportation Systems (ITSC).
IEEE, 2014, pp. 1166–1171.
[36] J. Wu, A. Abbas-Turki, and A. El Moudni, “Cooperative driving: an ant colony
system for autonomous intersection management,” Applied Intelligence, vol. 37,
no. 2, pp. 207–222, 2012.

87

[37] P. Varaiya, “Smart cars on smart roads: problems of control,” IEEE Transactions on automatic control, vol. 38, no. 2, pp. 195–207, 1993.
[38] P. Falcone, F. Borrelli, J. Asgari, H. E. Tseng, and D. Hrovat, “Predictive
active steering control for autonomous vehicle systems,” IEEE Transactions on
control systems technology, vol. 15, no. 3, pp. 566–580, 2007.
[39] R. Reghelin and L. V. R. de Arruda, “Using a centralized controller to optimize
the traffic of intelligent vehicles in a single lane highway provided with a suicide
lane,” in Intelligent Transportation Systems (ITSC), 2012 15th International
IEEE Conference on.

IEEE, 2012, pp. 1049–1054.

[40] J. Ruan, M. Fu, Y. Li, and J. Huang, “Study on throttle control of intelligent
vehicle longitudinal motion,” in Vehicular Electronics and Safety, 2005. IEEE
International Conference on.

IEEE, 2005, pp. 176–181.

[41] J. E. Naranjo, J. Reviejo, C. González, R. Garcı́a, and T. de Pedro, “A throttle and brake fuzzy controller: towards the automatic car,” in International
Conference on Computer Aided Systems Theory. Springer, 2003, pp. 291–301.
[42] R. Rajamani, H.-S. Tan, B. K. Law, and W.-B. Zhang, “Demonstration of integrated longitudinal and lateral control for the operation of automated vehicles
in platoons,” IEEE Transactions on Control Systems Technology, vol. 8, no. 4,
pp. 695–708, 2000.
[43] K.-D. Kim, “Collision free autonomous ground traffic: A model predictive control approach,” in Cyber-Physical Systems (ICCPS), 2013 ACM/IEEE International Conference on.

IEEE, 2013, pp. 51–60.

[44] N. M. Enache, M. Netto, S. Mammar, and B. Lusetti, “Driver steering assistance for lane departure avoidance,” Control engineering practice, vol. 17, no. 6,
pp. 642–651, 2009.
88

[45] P. G. Gipps, “A model for the structure of lane-changing decisions,” Transportation Research Part B: Methodological, vol. 20, no. 5, pp. 403–414, 1986.
[46] M. ZHU, “Approach to collision avoidance for autonomous vehicles at intersection,” Journal of Computational Information Systems, vol. 9, no. 24, pp.
10 013–10 020, 2013.
[47] R. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “V2v-intersection management at roundabouts,” SAE International Journal of Passenger CarsMechanical Systems, vol. 6, no. 2013-01-0722, pp. 681–690, 2013.
[48] Y. Gu, H. Jiang, Y. Zhang, and D. W. Gao, “Statistical scheduling of economic
dispatch and energy reserves of hybrid power systems with high renewable
energy penetration,” in 2014 48th Asilomar Conference on Signals, Systems
and Computers.

IEEE, 2014, pp. 530–534.

[49] H. Jiang, J. J. Zhang, D. W. Gao, Y. Zhang, and E. Muljadi, “Synchrophasor
based auxiliary controller to enhance power system transient voltage stability
in a high penetration renewable energy scenario,” in , 2014 IEEE Symposium
Power Electronics and Machines for Wind and Water Applications (PEMWA).
IEEE, 2014, pp. 1–7.
[50] H. Jiang, J. J. Zhang, A. Hebb, and M. H. Mahoor, “Time-frequency analysis
of brain electrical signals for behvior recognition in patients with parkinson’s
disease,” in 2013 Asilomar Conference on Signals, Systems and Computers.
IEEE, 2013, pp. 1843–1847.
[51] H. Jiang, J. J. Zhang, and D. W. Gao, “Fault localization in smart grid using wavelet analysis and unsupervised learning,” in 2012 Conference Record
of the Forty Sixth Asilomar Conference on Signals, Systems and Computers
(ASILOMAR).

IEEE, 2012, pp. 386–390.
89

[52] H. Jiang, J. J. Zhang, W. Gao, and Z. Wu, “Fault detection, identification, and
location in smart grid based on data-driven computational methods,” IEEE
Transactions on Smart Grid, vol. 5, no. 6, pp. 2947–2956, 2014.
[53] H. Jiang, L. Huang, J. J. Zhang, Y. Zhang, and D. W. Gao, “Spatial-temporal
characterization of synchrophasor measurement systemsa big data approach for
smart grid system situational awareness,” in 2014 48th Asilomar Conference
on Signals, Systems and Computers.

IEEE, 2014, pp. 750–754.

[54] H. Jiang, Y. Zhang, E. Muljadi, J. Zhang, and W. Gao, “A short-term and highresolution distribution system load forecasting approach using support vector
regression with hybrid parameters optimization,” IEEE Transactions on Smart
Grid, 2016.
[55] H. Jiang and Y. Zhang, “Short-term distribution system state forecast based
on optimal synchrophasor sensor placement and extreme learning machine,” in
2016 Power and Energy Society General Meeting (PESGM). IEEE, 2016, pp.
1–5.
[56] Y. Gu, H. Jiang, Y. Zhang, J. J. Zhang, T. Gao, and E. Muljadi, “Knowledge
discovery for smart grid operation, control, and situation awarenessa big data
visualization platform,” in 2016 North American Power Symposium (NAPS).
IEEE, 2016, pp. 1–6.
[57] F. Ding, H. Jiang, and J. Tan, “Automatic distribution network reconfiguration: An event-driven approach,” in Power and Energy Society General Meeting
(PESGM), 2016.

IEEE, 2016, pp. 1–5.

[58] R. Yang, H. Jiang, and Y. Zhang, “Short-term state forecasting-based optimal
voltage regulation in distribution systems: Preprint,” NREL (National Renew-

90

able Energy Laboratory (NREL), Golden, CO (United States)), Tech. Rep.,
2017.
[59] H. Jiang, Y. Li, Y. Zhang, J. J. Zhang, D. W. Gao, E. Muljadi, and Y. Gu,
“Big data-based approach to detect, locate, and enhance the stability of an
unplanned microgrid islanding,” Journal of Energy Engineering, vol. 143, no. 5,
p. 04017045, 2017.
[60] H. Jiang, F. Ding, and Y. Zhang, “Short-term load forecasting based automatic
distribution network reconfiguration: Preprint,” National Renewable Energy
Laboratory (NREL), Golden, CO (United States), Tech. Rep., 2017.
[61] Y. Zhang, R. Yang, K. Zhang, H. Jiang, and J. J. Zhang, “Consumption behavior analytics-aided energy forecasting and dispatch,” IEEE Intelligent Systems,
vol. 32, no. 4, pp. 59–63, 2017.
[62] Y. Gu, H. Jiang, J. J. Zhang, Y. Zhang, E. Muljadi, and F. J. Solis, “Load forecasting based distribution system network reconfiguration-a distributed datadriven approach,” arXiv preprint arXiv:1711.10690, 2017.
[63] ——, “Chance-constrained day-ahead hourly scheduling in distribution system
operation,” arXiv preprint arXiv:1711.10687, 2017.
[64] H. Jiang, Y. Zhang, J. J. Zhang, D. W. Gao, and E. Muljadi, “Synchrophasorbased auxiliary controller to enhance the voltage stability of a distribution
system with high renewable energy penetration,” IEEE Transactions on Smart
Grid, vol. 6, no. 4, pp. 2107–2115, 2015.
[65] M. K. Banavar, J. J. Zhang, B. Chakraborty, H. Kwon, Y. Li, H. Jiang,
A. Spanias, C. Tepedelenlioglu, C. Chakrabarti, and A. PapandreouSuppappola, “An overview of recent advances on distributed and agile sensing

91

algorithms and implementation,” Digital Signal Processing, vol. 39, pp. 1–14,
2015.
[66] H. Jiang, Y. Zhang, J. J. Zhang, and E. Muljadi, “PMU-aided voltage security
assessment for a wind power plant,” in 2015 IEEE Power & Energy Society
General Meeting.

IEEE, 2015, pp. 1–5.

[67] P. Dai, K. Liu, Q. Zhuge, E. H.-M. Sha, V. C. S. Lee, and S. H. Son, “Qualityof-experience-oriented autonomous intersection control in vehicular networks,”
IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 7, pp.
1956–1967, 2016.
[68] M. A. S. Kamal, J.-i. Imura, T. Hayakawa, A. Ohata, and K. Aihara, “A vehicleintersection coordination scheme for smooth flows of traffic without using traffic
lights,” IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 3,
pp. 1136–1147, 2015.
[69] W. Wu, J. Zhang, A. Luo, and J. Cao, “Distributed mutual exclusion algorithms
for intersection traffic control,” IEEE Transactions on Parallel and Distributed
Systems, vol. 26, no. 1, pp. 65–74, 2015.
[70] Y. J. Zhang, A. A. Malikopoulos, and C. G. Cassandras, “Optimal control
and coordination of connected and automated vehicles at urban traffic intersections,” in American Control Conference (ACC), 2016.

IEEE, 2016, pp.

6227–6232.
[71] S. I. Guler, M. Menendez, and L. Meier, “Using connected vehicle technology
to improve the efficiency of intersections,” Transportation Research Part C:
Emerging Technologies, vol. 46, pp. 121–131, 2014.

92

[72] S. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “Reliable intersection
protocols using vehicular networks,” in Cyber-Physical Systems (ICCPS), 2013
ACM/IEEE International Conference on.

IEEE, 2013, pp. 1–10.

[73] D. Krajzewicz, J. Erdmann, M. Behrisch, and L. Bieker, “Recent development
and applications of sumo–simulation of urban mobility,” International Journal
On Advances in Systems and Measurements, vol. 5, no. 3&4, 2012.
[74] D. Cheng, Z. Z. Tian, and C. J. Messer, “Development of an improved cycle
length model over the highway capacity manual 2000 quick estimation method,”
Journal of transportation engineering, vol. 131, no. 12, pp. 890–897, 2005.
[75] T. R. Board, Highway Capacity Manual, National Academy of Sciences, Transportation Research Board, Washington, DC, 2000.
[76] Q. Lu and K.-D. Kim, “Intelligent intersection management of autonomous traffic using discrete-time occupancies trajectory,” Journal of Traffic and Logistics
Engineering Vol, vol. 4, no. 1, pp. 1–6, 2016.
[77] ——, “Autonomous and connected intersection crossing traffic management
using discrete-time occupancies trajectory,” arXiv preprint arXiv:1705.05231,
2017.
[78] X. Chen, L. Li, and Y. Zhang, “A markov model for headway/spacing distribution of road traffic,” IEEE Transactions on Intelligent Transportation Systems,
vol. 11, no. 4, pp. 773–785, 2010.
[79] T. Murata, H. Ishibuchi, and H. Tanaka, “Genetic algorithms for flowshop
scheduling problems,” Computers & Industrial Engineering, vol. 30, no. 4, pp.
1061–1071, 1996.
[80] E. Hart, P. Ross, and D. Corne, “Evolutionary scheduling: A review,” Genetic
Programming and Evolvable Machines, vol. 6, no. 2, pp. 191–220, 2005.
93

[81] F. Werner, “Genetic algorithms for shop scheduling problems: a survey,”
Preprint, vol. 11, p. 31, 2011.
[82] K. Dahal, K. C. Tan, and P. I. Cowling, Evolutionary scheduling.

Springer

Science & Business Media, 2007, vol. 49.
[83] K. Daniel, E. Jakob, B. Michael, and B. Laura, “Recent development and
applications of sumo - simulation of urban mobility,” International Journal
On Advances in Systems and Measurements, vol. 5, no. 3&4, pp. 128–138,
December 2012.

94

