1

Autonomous and Connected Intersection
Crossing Traffic Management using
arXiv:1705.05231v1 [cs.SY] 12 May 2017

Discrete-Time Occupancies Trajectory
Qiang Lu, and Kyoung-Dae Kim, Member, IEEE

Abstract
In this paper, we address a problem of safe and efficient intersection crossing traffic management of
autonomous and connected ground traffic. Toward this objective, we propose an algorithm that is called
the Discrete-time occupancies trajectory based Intersection traffic Coordination Algorithm (DICA). We
first prove that the basic DICA is deadlock free and also starvation free. Then, we 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 of intersection crossing routes. To improve the
overall computational efficiency of the algorithm, the basic DICA is enhanced by several computational
approaches that are proposed in this paper. The enhanced algorithm has the computational complexity
of O(n2 Lm log2 Lm ). The improved computational efficiency of the enhanced algorithm is validated
through simulation using an open source traffic simulator, called the Simulation of Urban MObility
(SUMO). The overall throughput as well as the computational efficiency of the enhanced algorithm are
also compared with those of an optimized traffic light control.
Index Terms
Autonomous Vehicles, Intelligent Intersection Management, Discrete-Time Occupancies Trajectory
(DTOT), Computational Complexity

Qiang Lu and Kyoung-Dae Kim are with the Department of Electrical and Computer Engineering, University of Denver,
Denver, CO, 80210 USA e-mails: qiang.lu@du.edu, kyoung-dae.kim@du.edu.

May 16, 2017

DRAFT

2

L IST

OF

F IGURES

1

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

6

2

Interaction between an AV and the ICA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3

Example situations of front vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4

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

5

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

6

A screenshot of simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

7

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

8

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

9

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

10

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

11

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

May 16, 2017

DRAFT

3

I. I NTRODUCTION
Over the past decades, the vision for autonomous vehicles and autonomous ground traffic systems
has indeed attracted a lot of attention and has catalyzed unprecedented research and development efforts
from academia, industry, government, etc. Some examples are the California PATH Automated Highway
System (AHS) program [1] during the mid of 1990s and also the series of DARPA (Defense Advanced
Research Projects Agency) Challenges [2] that have happened during the 2000s. Many automobile
companies are also investing huge amounts of money in developing their own self-driving vehicles or
vehicles with many advanced driving assistance systems [3]. However, despite many recent successful
road testing results of several self-driving cars such as Google driverless car [4], it is hard to argue that
the overall system-wide traffic safety as well as throughput will be improved substantially when we have
a few autonomous vehicles 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. 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 [5], 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 [6], autonomous parking control [7], collision avoidance [8], [9], relation between occupant
experience and intersection capacity [10], intersection management of mixed traffic [11] 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 since intersections are
certainly the most critical traffic environments from the perspective of safety as well as throughput.
In literature, there are a number of notable results for autonomous intersection crossing traffic management. In [12], 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. [13] introduced a new
intersection traffic management framework that is formulated as a combinatorial optimization problem
and solved the problem approximately using the ant colony system algorithm [14]. 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, [15] formulated a
decentralized framework whereby each autonomous vehicle minimizes its energy consumption under

May 16, 2017

DRAFT

4

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 crossing traffic throughput, some researchers eliminated this
conservative restriction by discretizing an intersection space so that vehicles can exist simultaneously
within an intersection but not within a same discretized space within the intersection. The representative
approach is the reservation-based approach AIM (Autonomous Intersection Management) proposed in
[16]. In AIM, cars request and receive time slots from the intersection during which they may pass.
Similar and improved approaches [17], [18], [19] were also proposed afterwards. For example, [17]
proposed ASL (Advance Stop Location) concept which is a predefined advance stop location other
than the traditional stop line at the entrance of an intersection for a vehicle with rejected reservation.
The slow-reservation-speed issue which increases the total traversal time within the intersection could
be improved by the ASL. Representative centralized approaches also include auction-based intersection
managements proposed in [20], [21]. A decentralized approach based on a vehicle-to-vehicle (V2V)
coordination protocol was proposed in [22]. Roughly speaking, these approaches are all based on the
grid cell partitioning of an intersection space. In [16], 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 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. Some other research works on autonomous intersection management
can be found in [13], [23], [24].
As an approach to address the above mentioned granularity issue, we proposed a novel intersection
traffic management scheme in our earlier work [25] based on the idea of the Discrete-Time Occupancies
Trajectory (DTOT). Conceptually, a DTOT is a discrete-time sequence of a vehicle’s actual occupancy
within an intersection space. Hence, a DTOT-based intersection management scheme can utilize the
intersection area much more efficiently than other grid partition based approaches. Furthermore, the
proposed interaction mechanism between an intersection and vehicles allows the flexibility that each
vehicle can choose its path as well as motions along the path that a vehicle wants to take to cross

May 16, 2017

DRAFT

5

an intersection. 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. In this
paper, we provide an in-depth analysis of the original DTOT-based Intersection Coordination Algorithm
(DICA) to show that it satisfies the liveness property in terms of deadlock as well as starvation issues and
also to derive the overall computational complexity of the algorithm. Another contribution of this paper 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.
The rest of this paper is organized as follows: In Section II, we introduce the main ideas, concepts,
assumptions, notations, and also the basic algorithm, called DICA in short, developed for the DTOTbased intersection crossing traffic management. In Section III, we show that the basic DICA is deadlock
and also starvation free. In this section, we also discuss in detail about the computational complexity of
the algorithm. Several approaches to improve the overall computational efficiency of the algorithm are
discussed in Section IV. The overall computational efficiency as well as the throughput performance of
the enhanced algorithm are evaluated through simulations in Section V. Finally, Section VI concludes
this paper.
II. DTOT- BASED I NTERSECTION T RAFFIC M ANAGEMENT
In this section, we introduce the basic idea and algorithm of the DTOT-based intersection management
scheme that is developed for autonomous and connected intersection crossing traffic in which all vehicles
are autonomous vehicles (AVs) and capable of wireless vehicular communication. We assume that an
intersection is also equipped with 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. At an intersection, there is no traffic light that controls the intersection
crossing traffic. Instead, each vehicle communicates with the intersection, which we call the Intersection
Control Agent (ICA) from now on, to get permission to access the intersection. As shown in Figure 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

May 16, 2017

DRAFT

6

Vehicle vj
O2j

O3j

O

Vehicle vi
O1i

O2i

O5j O i

3

O

O1j

j
4

O4i

O5i

O6i

j
6

O7j

The enter line of
the lane vehicle
vi is in

Communication region

Intersection region

Figure 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.)

each vehicle’s identification number (VIN), 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 AVs and
ICA. Thus, there is no V2V communication. Since the focus of this paper 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 data packages 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 thanks to the above mentioned information collection

May 16, 2017

DRAFT

7

mechanism through detectors.
A. Interaction between ICA and AV
In the autonomous and connected intersection traffic considered in this paper, an AV and ICA start to
interact with each other by exchanging some messages through vehicular wireless communication when
the AV enters into the communication range of ICA. As shown in Figure 2, an AV and ICA exchange
some specific types of messages for their intersection crossing coordination. The interaction is initiated
from an AV by sending a message, called a REQUEST, to reserve a sequence of space and time to
cross the intersection. Each REQUEST message contains information that is necessary for a vehicle’s
space-time reservation for its intersection crossing such as (i) the VIN, (ii) the Vehicle Size (VS) that
is simply a vehicle’s length and width, and (iii) a vehicle’s discrete time state trajectory, which we call
the Timed State Sequence (TSS), starting from the entrance 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 vehicle possesses the state x at time t. For simplicity of our discussion, we simply
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

Follow the traffic
Become a head
vehicle

Send REQUEST

Follow the traffic

DICA
Convert TSS to
DTOT
Adjust DTOT if
needed

Send RESPONSE
Follow confirmed
DTOT

Confirm DTOT

Out of intersection region
AV

ICA

Figure 2: Interaction between an AV and the ICA.

May 16, 2017

DRAFT

8

As shown in Figure 2, an AV will send REQUEST message to ICA only when it becomes a head
vehicle. A vehicle is considered a head vehicle on its lane if either 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. Note that ICA also
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. To respond to a REQUEST message from a head vehicle, ICA first converts the TSS to
the corresponding DTOT using the VS information which is also contained in the received REQUEST
message. Based on the length and width of a vehicle consisted in the VS, a 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 DTOT to determine whether the requested DTOT can be accepted or not.
If ICA finds any potential risk of collision with the request, then it adjusts the requested DTOT slightly
in order to eliminate collisions. And then ICA confirms the adjusted collision-free DTOT and sends it
back to the vehicle using a RESPONSE message so that the vehicle can follow the confirmed DTOT to
cross the intersection. Note that when ICA sends a RESPONSE message to a vehicle, it actually sends
the confirmed TSS not the confirmed DTOT. 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 has received a confirmed DTOT from ICA. And we assume that every
vehicle is able to follow the confirmed DTOT precisely.
B. 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, DICA uses a few sets and notations. We use TSS(v ) to denote a TSS and
DTOT(v ) to denote a 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 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 are 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

May 16, 2017

DRAFT

9

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

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 spacetime 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
k ) is
particular situation, τ (Onj ) is the first time at which v j starts to collide with v i . Similarly, τ (Om

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

are denoted by v j .f irstT imeAtCollision and v k .f irstT imeAtCollision, 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 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

May 16, 2017

DRAFT

10

the function checkFV() to determine if there exist front vehicles (See Section II-B1 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 several functions called within DICA.
1) Collision Avoidance with Front Vehicles: As shown in Figure 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 [16]
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,
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 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.
2) Vehicles for Collision Avoidance: 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

May 16, 2017

DRAFT

11

Vehicle vi

Vehicle vi
(a)

(b)

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

by taking the times of the previous and next occupancies which are the closest to the occupancy while
having no overlapping area. As an example, for the occupancy O4j of the vehicle v j in Figure 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 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 checking space-time conflict
j
) for all n, m, and j in the set S . Since an occupancy in a DTOT is
for every pair of occupancies (Oni , Om

represented as a rectangle, it is relatively straightforward to do space conflict checking. For this, Algorithm
j
2 simply checks if two rectangles have non-empty intersection or not. If a pair of occupancies (Oni , Om
)

are space-conflicting, then the function continues to investigate 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

May 16, 2017

DRAFT

12

j
around the same 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 determined so that
the vehicle v j is appropriately ordered within the set C .
Algorithm 2 getCV(S, DT OT (v i ))
1: C = ∅
2:
3:
4:

for v j in S do
for Okj j in DT OT (v j ) do
if v j not in C then
for Oki i in DT OT (v i ) do

5:

if Okj j ∩ Oki i 6= ∅ then

6:
7:

Call getOTI(Okj j ) → I(Okj j ) := [τlb (Okj j ), τub (Okj j )]

8:

Call getOTI(Oki i ) → I(Oki i ) := [τlb (Oki i ), τub (Oki i )]

9:

if I(Okj j ) ∩ I(Oki i ) 6= ∅ then

10:

Assign τlb (Okj j ) → v j .f irstT imeAtCollision

11:

Push v j into C

12:

Sort C in ascending order of firstTimeAtCollision
end if

13:

end if

14:

end for

15:
16:
17:
18:

end if
end for
end for

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. Our current strategy for updating a vehicle’s DTOT is

May 16, 2017

DRAFT

13

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 longer 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.
III. A NALYSIS
A. Liveness
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 [16], 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 [22] 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 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

May 16, 2017

DRAFT

14

head vehicle v i is under consideration for confirmation. Note that, as discussed in Section II, 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 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 DICA.
Proposition 2. DICA is starvation free.
Proof. First, let us recall that, as discussed in Section II, 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

May 16, 2017

DRAFT

15

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.
B. Computational Complexity
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 intersection crossing confirmation. Also let Nm := maxk∈S ′ N k where S ′ = 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 II, 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 computational complexities O(nNm ). Then, in line 5 (Algorithm 1), the function
getCV() is called to identify the set of vehicles C 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 nonempty 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,

May 16, 2017

DRAFT

16

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 space-time 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 II, space-time conflict 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 exists nonempty
intersections between two occupancies: one from DTOT of the vehicle v i and another from DTOT of
2 times of iteration
one of the vehicles in the set S . This is done in the outer if block and requires n · Nm

in the worst case. If two vehicles have a space conflict, 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 ′ for k′ = {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
3)
the overall computational complexity 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 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 II, our update strategy to avoid space-time
conflict 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

May 16, 2017

DRAFT

17

delay time needed to avoid the space-time 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 every 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(),
3 ).
the 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 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 shown that
2 )/(2a v h) where a
N̄m = (2am Lm + vm
m m
m is the maximum acceleration 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
p
is also relatively straightforward to show that N̄m = ( 2Lm /am )/h. (These two different cases are
illustrated in Figure 4.) 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 Lm . Hence, if
3 ) that we derived above, then we
we substitute Lm for Nm in the computational complexity O(n2 Nm

finally have O(n2 L3m ) as the overall computational complexity of DICA.

May 16, 2017

DRAFT

18

v
case 2

vm
case 1

0

tm

tm

t

Figure 4: 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.)

IV. A LGORITHM I MPROVEMENTS
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 complexity of the algorithm.

A. 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 spacetime 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 is the maximum
function getCV() becomes O(α1 nNm
1
m

May 16, 2017

DRAFT

19

number of occupancies of all vehicles that are in the set S and also the vehicle that is currently under
consideration for confirmation. (See the proof of Proposition 3 for the precise definition of Nm .)
B. 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 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
3)
computational complexity of the function getCV() in Algorithm 2 can be expressed as O(α32 nNm

where α2 := Ñm /Nm 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.

C. 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 of computational complexity. In fact, as analyzed in the proof, such an
exhaustive search involves 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 5. 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

May 16, 2017

DRAFT

20

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

xk
O

i
k

t
i
k

i
k

t (O )

t lb (O )

i
k

t ub (O )

Figure 5: Approximate occupancy time interval calculation for a vehicle with the through route

not shown in Figure 5 for simplicity. Specifically, if we let Vk− (v i ) and Vk+ (v i ) be the speed of the
i
i
respectively, then these speeds can be approximated
to Oki and from Oki to Ok+1
vehicle v i from Ok−1

as follows:
Vk− (v i ) ≈

xk − xk−1
,
h

Vk+ (v i ) ≈

xk+1 − xk
h

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

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

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 L(v i ), Vk (v i ), and
Ak (v i ), we omit the details of these calculations in this paper. 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 the computational complexity of the function getCV()
3 ) to O(n2 N 2 ).
improves from O(n2 Nm
m

D. Efficient Occupancies Comparison
In addition to all the techniques described above, the overall computational complexity of the Algorithm
1 can be improved further if we employ an efficient searching method such as the bisection method in the

May 16, 2017

DRAFT

21

process of time-conflict checking between two DTOT∗ s. If we employ this bisection approach for timeconflict 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 space-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 IV-A

and DTOT∗ represents the subset of original DTOT for a vehicle that can be obtained from the approach
in Section IV-B. 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 IV-C.
Lastly, the approach for efficient time conflict checking that is presented in Section IV-D is implemented
throughout the while loop of the DICA algorithm.
Proposition 4. Enhanced DICA has O(αn2 Lm log2 Lm ) computational complexity where α := α21 α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 IV-A. 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 N is the maximum
conflict which typically requires Nm
m

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 IV-B. Another important improvement is that the computational complexity for the occupancy time

May 16, 2017

DRAFT

22

Algorithm 3 enhanced getCV(S ∗ , DT OT (v i ))
1: C = ∅
2:
3:
4:

for v j in S ∗ do
for Okj j in DT OT ∗ (v j ) do
if v j not in C then

5:

high = |DT OT ∗ (v i )| − 1

6:

low = 0

7:

while low 6= high do

8:

middle = (high + low)/2

9:

Call getEstOTI(Okj j ) → I(Okj j ) := [τlb (Okj j ), τub (Okj j )]

10:

i
i
i
i
)]
), τub (Omiddle
) := [τlb (Omiddle
) → I(Omiddle
Call getEstOTI(Omiddle

11:

i
) 6= ∅ then
if I(Okj j ) ∩ I(Omiddle

12:

Assign τlb (Okj j ) → v j .f irstT imeAtCollision

13:

Push v j into C

14:

Sort C in ascending order of firstTimeAtCollision
i
else if τ (Okj j ) > τ (Omiddle
) then

15:

low = middle

16:

i
) then
else if τ (Okj j ) < τ (Omiddle

17:

high = middle

18:
19:

end if

20:

end while

21:
22:
23:

end if
end for
end for

interval calculation is improved from O(Nm ) to O(1) within another enhanced function getEstOTI()
as discussed in Section IV-C. Therefore, the overall computational complexity of the outer for loop can
2 ). However, note that this is the case when we use the same occupancies
be estimated as O(α1 α22 nNm

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 improves the overall computational complexity of the
2 ) to O(nN log N ) as discussed in Section IV-D. If we combine this and others
function from O(nNm
m
2 m

May 16, 2017

DRAFT

23

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(α21 α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 α := α21 α2 ≪
1.

V. S IMULATION
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.

A. Simulation Setup
To evaluate the performance of the original DICA and the enhanced DICA, we implemented both
algorithms in a microscopic road traffic simulation software, called the Simulation of Urban MObility
(SUMO) [26], and performed extensive intersection traffic simulations. In our simulation, the simulated
situation is an intersection crossing traffic on a typical isolated four way intersection with three incoming
lanes, one of which is a dedicated lane for left-turning vehicles, and two outgoing lanes on each road
as shown in Figure 6. We set 70km/h as the maximum allowed speed vm for all incoming vehicles.
To make the simulation more realistic, we let vehicles approach an intersection with different speeds
when they enter into the communication region of the intersection. 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 2m/s2 and 4.5m/s2 , respectively. The size of a vehicle
used in simulations is 5 meters long and 1.8 meters wide. 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 be long enough so that a vehicle can stop from its maximum speed vm . Thus, from the
value used for vm = 70km/h and the maximum deceleration rate amin = 4.5m/s2 , we need at least

May 16, 2017

DRAFT

24

2 /(2a
vm
min ) ≈ 42.03m. So, we use 50m for the distance from the entrance line of the communication

region to the entrance line of the intersection region. The time step that is used in simulation 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, a Bernoulli random variable XV is used to
spawn a vehicle at each simulation time step on each incoming road. In particular, a vehicle is spawned
if XV = 1 and not spawned if XV = 0 with P r(XV = 1) = pV where P r(E) is the probability
of an event E and 0 ≤ pV ≤ 1 is the probability that a vehicle is spawned. Thus, by adjusting pV ,
we can generate various traffic volumes. In addition to this traffic volume variation, we also assign the
probabilities for each vehicle to have different routes. We use a three-states random variable XP to assign
an intersection route to a vehicle probabilistically when the vehicle is generated. Three states of the random
variable XP are {Lef t, Straight, Right} with P r(XP = Lef t) = pL , P r(XP = Straight) = pS , and
P r(XP = Right) = pR being the probability of turning left, going straight, and turning right to cross an

intersection, respectively. As shown in Table I, 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. To create variations on the traffic pattern with this random variable XP , we
generate a random number at each simulation time step from the range [0, 1] with uniform distribution.
However, a random number generated in programming languages is not completely random in general due
to its dependency on the seed number used for random number generation. For example, if we generate a
random number with a fixed random seed number, the random number generated at simulation time step
t will be the same whenever we run a simulation. Thus, we use several different random seed numbers to

generate different traffic patterns. Table I summarizes the parameters used for various traffic volumes and
patterns that were used in many of our simulations. As shown in the table, 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 traffics in the sense that
the number 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 in 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 V-B1, means the

May 16, 2017

DRAFT

25

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

Value

Traffic volumes∗

100 / 200 / 300 / 400 / 500

pV

0.03 / 0.06 / 0.08 / 0.11 / 0.14

pL

0.20

pS

0.60

pR

0.20

Random seeds

12 / 21 / 66

actual elapsed time that it takes for a computer to run a simulation. Also, in Section V-B3, 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 [27]. In the
model, L represents the total lost time within the cycle. The lost time for each phase is assumed to be 4
seconds [28]. Thus, L = 4 × 4s = 16s. Y is the sum of critical phase flow ratios. The duration for the
yellow light of each phase is 3 seconds.
All simulations were run on a Core i7 computer with 3.40GHz, 8GB RAM and Windows system. The
interface programs with SUMO were coded in Python.

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

May 16, 2017

DRAFT

26

B. Simulation Results
Computation times and performances of three different traffic patterns for all five volume cases are
recorded from simulations. Figure 6 shows a screenshot of simulation in SUMO when vehicles of different
routes are crossing an intersection simultaneously without occurrence of collisions. In this situation, the
through vehicle from North goes inside the intersection shortly after the vehicle from West to East clears
the conflicting space and the through vehicle from East starts to enter the intersection although the route
of the vehicle is conflicting with that of the vehicle from North. Vehicles whose DTOTs are not conflicting
with these two can pass the intersection at the same time. For example, the right-turning vehicle from
South also crosses the intersection at the same time as the other vehicles in Figure 6.
1) Computation Time: Figure 7 (a) compares the computation times of the original DICA, the enhanced
DICA, and the optimized traffic light algorithm. Figure 7 (b) shows how much computational improvement
was made through each computational improvement technique discussed in Sections IV-A, IV-B, IV-C,
and IV-D. Note that since the computational improvement technique in SectionIV-D is implemented based
on the computational improvement technique in Section IV-B, we had to combine techniques from both
Sections IV-D and IV-B to show the improvement due to the technique in Section IV-D indirectly. Here,
we show the computation times comparison for only one traffic volume case with 300 vehicles per 10
minutes since the trends for other volume cases are similar. The vertical axis in Figure 7 is the computation
time in hour unit which is represented in logarithmic scale. As shown in Figure 7, the enhanced DICA
that implements all improvements discussed in Section IV 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 IV-A, 59% with the technique in Section IV-B, 13% with the
technique in Section IV-C, and 6% with techniques in Sections IV-B and Section IV-D together. If we
combine all of these individual improvement 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 II 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

May 16, 2017

DRAFT

27

10

10
Original DICA
IV-A
IV-B
IV-C
IV-D + IV-B

Original DICA

Optimized Traffic Light
1

0.1

0.01

Computation Time (log h)

Computation Time (log h)

Enhanced DICA

1

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

(a)

300
Traffic Volume
(number of vehicles per 10 minutes)

(b)

Figure 7: Computation times comparison for traffic volume with 300 vehicles per 10 minutes: (a) original
DICA with different algorithms, (b) original DICA with different improvement techniques. (The symbol
IV-x represents the improvement technique in Section IV-x where x = { A, B, C, D }.)

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 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 V-B3.
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,

May 16, 2017

DRAFT

28

Table II: Computation time comparison between enhanced DICA and optimized traffic light
Traffic vsolume

100

200

300

400

500

Optimized Traffic light (h)

0.014

0.017

0.020

0.024

0.027

Enhanced DICA (h)

0.011

0.024

0.026

0.042

0.058

10000

12000

(Number of vehicles per 10 minutes)

10000
9000
8000

Number of Vehicles

7000
6000
5000
4000
3000
2000
1000
0

0

2000

4000

6000
8000
Simulation Time (s)

Figure 8: The number of vehicles which wait to cross the intersection over time.

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 8. 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 III-A. We also 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 III, 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 the proposition 2 in Section III-A.
Table III: Average trip time comparison between major roads and minor roads in an unbalanced traffic
Traffic volume
(Number of vehicles per 10 minutes)

May 16, 2017

100

200

300

400

500

Average trip time on major roads (s)

6.17

6.60

7.38

8.15

10.15

Average trip time on minor roads (s)

6.21

6.57

7.38

7.90

9.63

DRAFT

29

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 9: 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.)

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 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 9. 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 9 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.
3) 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 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 are 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 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

May 16, 2017

DRAFT

30

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%

500

Optimized Traffic Light
Enhanced DICA

100

200

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

(b)

Optimized Traffic Light

25

Enhanced DICA

20
15
10
5
0
100

200

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

(c)

500

Standard Deviation of Trip Time
(s)

Effective Average Trip Time (s)

(a)
30

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)

Figure 10: 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.

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 performance of an algorithm better. Comparison of the performance
between the enhanced DICA and the optimized traffic light control algorithm are shown in Figure 10.
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 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 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

May 16, 2017

DRAFT

31

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 performance, it
is necessary to combine both strategies: an individual vehicle based coordination in normal traffic volume
and a traffic flow based coordination in 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 11. In this figure, if the flow rate ratio is close to 1, then it means that all vehicles
approached to an intersection have already crossed the intersection and there are no vehicles waiting to
cross at that time. The simulation time starts from 300s in the 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 600s 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 11 shows
that DICA is more resilient to the change of traffic volume than the optimized traffic light.
VI. C ONCLUSION
In this paper, we first introduced our algorithm developed for autonomous and connected intersection
traffic management, which is called the discrete-time occupancies trajectory (DTOT) based intersection
traffic coordination algorithm (DICA). Subsequently, we showed that the original DICA is deadlock

May 16, 2017

DRAFT

32

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 11: Flow rate ratio when traffic volume changes from 100 to 500.

free and also starvation free. We then 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 case when the traffic is not congested. Currently, it is in-progress to integrate the grouping strategy
used in traffic flow based intersection control mechanisms into our DICA to achieve the best throughput
performance in all traffic volume situations. We are also working on enhancing the algorithm to deal with
sudden emergence of special vehicles such as emergency ambulances or police cars that have the highest
priority in real traffic through efficient usage of intersection space. In the future, assumptions like perfect
communication, accurate prediction of DTOT will be relaxed and methods to deal with car failures will
be studied to make the algorithm more applicable to real situations. As one of future works, DICA will
be generalized to work with mixed traffic where autonomous vehicles and human-driven vehicles coexist.
R EFERENCES
[1] R. Horowitz and P. Varaiya, “Control design of an automated highway system,” Proceedings of the IEEE, vol. 88, no. 7,
pp. 913–925, 2000.
[2] DARPA, “The darpa urban challenge,” 2007. [Online]. Available: http://archive.darpa.mil/grandchallenge/
[3] 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.
[4] J. Markoff, “Google cars drive themselves, in traffic,” The New York Times, vol. 10, no. A1, p. 9, 2010.

May 16, 2017

DRAFT

33

[5] L. W. Chen and C. C. Chang, “Cooperative traffic control with green wave coordination for multiple intersections based
on the internet of vehicles,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. PP, no. 99, pp. 1–15,
2016.
[6] 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.
[7] 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.
[8] 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.
[9] 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.

[10] 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.
[11] E. Onieva, U. Hernández-Jayo, E. Osaba, A. Perallos, and X. Zhang, “A multi-objective evolutionary algorithm for the
tuning of fuzzy rule bases for uncoordinated intersections in autonomous driving,” Information Sciences, vol. 321, pp.
14–30, 2015.
[12] 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.
[13] 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.
[14] 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.
[15] A. A. Malikopoulos and C. G. Cassandras, “Decentralized optimal control for connected and automated vehicles at an
intersection,” arXiv preprint arXiv:1602.03786, 2016.
[16] K. Dresner and P. Stone, “A multiagent approach to autonomous intersection management,” Journal of artificial intelligence
research, vol. 31, pp. 591–656, 2008.
[17] Z. Li, M. Chitturi, D. Zheng, A. Bill, and D. Noyce, “Modeling reservation-based autonomous intersection control in
vissim,” Transportation Research Record: Journal of the Transportation Research Board, no. 2381, pp. 81–90, 2013.
[18] Q. Jin, G. Wu, K. Boriboonsomsin, and M. Barth, “Advanced intersection management for connected vehicles using a
multi-agent systems approach,” in Intelligent Vehicles Symposium (IV), 2012 IEEE. IEEE, 2012, pp. 932–937.
[19] C. Wuthishuwong, A. Traechtler, and T. Bruns, “Safe trajectory planning for autonomous intersection management by using
vehicle to infrastructure communication,” EURASIP Journal on Wireless Communications and Networking, vol. 2015, no. 1,
pp. 1–12, 2015.
[20] 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.

[21] 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.
[22] S. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “Reliable intersection protocols using vehicular networks,” in CyberPhysical Systems (ICCPS), 2013 ACM/IEEE International Conference on.

May 16, 2017

IEEE, 2013, pp. 1–10.

DRAFT

34

[23] K.-D. Kim and P. R. Kumar, “An mpc-based approach to provable system-wide safety and liveness of autonomous ground
traffic,” IEEE Transactions on Automatic Control, vol. 59, no. 12, pp. 3341–3356, 2014.
[24] 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.
[25] 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.
[26] 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.
[27] 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.
[28] T. R. Board, Highway Capacity Manual, National Academy of Sciences, Transportation Research Board, Washington, DC,
2000.

May 16, 2017

DRAFT

