Robust Supervisors for Intersection
Collision Avoidance in the Presence of
Uncontrolled Vehicles

Journal Title
XX(X):1–21
c The Author(s) 2016
Reprints and permission:
sagepub.co.uk/journalsPermissions.nav
DOI: 10.1177/ToBeAssigned
www.sagepub.com/

arXiv:1603.03916v2 [] 15 Mar 2016

Heejin Ahn1 , Andrea Rizzi2 , Alessandro Colombo3 , and Domitilla Del Vecchio1

Abstract
We present the design and validation of a centralized controller, called a supervisor, for collision avoidance of multiple
human-driven vehicles at a road intersection, considering measurement errors, unmodeled dynamics, and uncontrolled
vehicles. We design the supervisor to be least restrictive, that is, to minimize its interferences with human drivers.
This performance metric is given a precise mathematical form by splitting the design process into two subproblems:
verification problem and supervisor-design problem. The verification problem determines whether an input signal
exists that makes controlled vehicles avoid collisions at all future times. The supervisor is designed such that if the
verification problem returns yes, it allows the drivers’ desired inputs; otherwise, it overrides controlled vehicles to
prevent collisions. As a result, we propose exact and efficient supervisors. The exact supervisor solves the verification
problem exactly but with combinatorial complexity. In contrast, the efficient supervisor solves the verification problem
within a quantified approximation bound in polynomially bounded time with the number of controlled vehicles. We
validate the performances of both supervisors through simulation and experimental testing.

1

Introduction

Autonomous robots have drawn attention in various
applications, such as exploring unknown environment
(Maimone et al. (2007)), moving materials in warehouses
(Wurman et al. (2008)), and collecting data on ocean
conditions (Smith et al. (2010)). Recently, there has been
extensive research on autonomous vehicles from academic,
industrial, and governmental sectors for the purpose of
reducing the number of traffic accidents. Research has
focused on developing fully autonomous vehicles as well
as improving safety of human-driven vehicles by means of
newly available automation, sensing, and communication
capabilities. A major obstacle to the development of
collision avoidance architecture for large traffic networks is
computational complexity.
In general, there have been several approaches to reduce
computational complexity in collision avoidance for multiple
vehicles. In a decentralized framework, each vehicle makes
its own decision to avoid collisions with its neighboring
vehicles, thereby dividing a large problem into smaller
local problems. To design a decentralized control law,
Hoffmann and Tomlin (2008) and Gillula et al. (2011) used
reachability analysis for hybrid systems, and Mastellone et al.
(2008) defined a potential function. While computationally
efficient, this framework is usually more conservative
and unable to prevent a deadlock, where no further
Prepared using sagej.cls [Version: 2015/06/09 v1.01]

control input exists to terminate processes (Cassandras
and Lafortune (2008)). A centralized framework considers
a whole system and thus can be less conservative, but
computationally demanding. Collision avoidance problems
were formulated into mixed integer linear programming
(MILP) by assuming discrete-time linear vehicle dynamic
models (Richards et al. (2002); Borrelli et al. (2006)) and
considering geometric construction of collisions with vehicle
models of instantaneous speed or angle changes (Pallottino
et al. (2002); Alonso-Ayuso et al. (2011)). These MILP
formulations are then solved by commercially available
software. In this paper, we present a centralized controller,
in which the collision avoidance problem is translated
into a scheduling problem and then solved by solving this

1 Department of Mechanical Engineering, Massachusetts Institute of
Technology, Cambridge, MA, USA
2 Tri-Institutional Program in Computational Biology and Medicine, Weill
Cornell Medical College, New York, NY, USA
3 Dipartimento di Elettronica Informazione e Bioingegneria, Politecnico
di Milano, Milano, Italy

Corresponding author:
Heejin Ahn, Department of Mechanical Engineering, Massachusetts
Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA
02139, USA.
Email: hjahn@mit.edu

2

Journal Title XX(X)

scheduling problem. Moreover, we provide an approximate
solution of this problem.

mixed-traffic scenario where unequipped vehicles still travel
on roads.
To design a supervisor, we formulate two problems:
In collision avoidance problems at road intersections, the
verification problem and supervisor-design problem. The
complexity can be mitigated to some extent by exploiting
verification problem determines the existence of an input
the fact that vehicles follow predefined paths, and sidesignal that makes controlled vehicles avoid all future
impacts can be avoided by approximately scheduling
collisions. We prove that this problem is equivalent to
their time of occupancy of the shared intersection (Peng
an Inserted Idle-Time (IIT) scheduling problem, where
and Akella (2005a,b)). Based on this concept, several
an inserted idle-time represents a set of time intervals
autonomous intersection management schemes have been
during which uncontrolled vehicles can occupy the
studied. Kowshik et al. (2011) proposed a hybrid architecture
intersection. This formulation was introduced in Ahn et al.
comprising an interplay between centralized coordination
(2014) to account for uncontrolled vehicles under perfect
and distributed agents. Centralized coordination assigns time
measurement and dynamic models. The supervisor is
slots to agents, and distributed agents determine if they
designed to override the drivers of controlled vehicles only
can cross an intersection within allocated time slots while
when the verification problem determines that there will be
avoiding rear-end collisions. Wu et al. (2012) employed
no input signal to avoid collisions.
an ant colony algorithm as an approximate solution for
In order to study the trade-off between exactness and
finding an optimal sequences of vehicles to improve traffic
computational efficiency, we propose exact and efficient
efficiency. Collision avoidance problems were formulated
supervisors. The exact supervisor solves the verification
into nonlinear constrained optimization to eliminate overlaps
problem exactly, and thus, overrides drivers only when
of given trajectories inside an intersection (Lee and Park
strictly necessary. However, since the verification problem
(2012)) and to minimize the risk of collision (Kamal et al.
has combinatorial complexity, this supervisor is not scalable
(2014)). These works consider fully autonomous vehicles
with the number of controlled vehicles. To improve
and can solve collision avoidance problems by finding one
the computational efficiency, the efficient supervisor is
safe input. However, when human operators drive vehicles,
designed to solve the verification problem within a
a controller needs to be least-restrictive, that is, override
quantified approximation bound in polynomially bounded
human drivers only when they can cause a collision.
time. We validate the supervisors by performing computer
To ensure least restrictiveness, all possible inputs simulations and lab-based experimental testing. Some of
must be taken into account, usually at expense of these experimental results were presented in Ahn et al.
computational cost. Moreover, this exhaustive evaluation (2015).
This paper is organized as follows. In Section 2, we define
must be done frequently because controllers must keep
monitoring vehicles’ safety and intervene only when an intersection model and a vehicle dynamic model. In
drivers are unable to prevent collisions. In Hafner and Section 3, we formulate two problems: verification problem
Del Vecchio (2011); Hafner et al. (2013), a safety control and supervisor-design problem, which are solved exactly in
was designed for two vehicles. Their controller was validated Section 4 and approximately in Section 5. The simulation
in laboratory experiments (Hafner and Del Vecchio (2011)) results are given in Section 6, and the experimental results
and field experiments (Hafner et al. (2013)). Colombo in Section 7.
and Del Vecchio (2012) translated a collision detection
problem to a scheduling problem and employed a scheduling
2 System Definition
algorithm to design a safety control for multiple vehicles.
Rear-end collisions as well as intersection collisions were In this section, we introduce an intersection model and the
vehicle dynamics.
considered in Colombo and Del Vecchio (2014).
In this paper, we propose a least-restrictive controller,
called a supervisor, that prevents intersection collisions 2.1 Intersection model
among human-driven vehicles. Our work extends the result Consider n human-driven vehicles approaching an
of Colombo and Del Vecchio (2012) in that 1) we consider intersection along n different paths. As shown in Figure
sources of uncertainty, including measurement errors, 1, the intersection is modeled as an area containing the
unmodeled dynamics, and uncontrolled vehicles, and 2) we points at which these paths intersect. An open interval
perform a lab-based experiment to validate the supervisor (αi , βi ) ⊂ R denotes the location of this conflict area on
in a setting subject to many sources of uncertainty. Here, the longitudinal path of vehicle i. Among n vehicles,
controlled vehicles communicate with and are controlled by nc vehicles are communicating with a supervisor, which
the supervisor, whereas uncontrolled vehicles are not. The takes control of these vehicles when potential crashes are
inclusion of uncontrolled vehicles accounts for a realistic detected and returns control back to the drivers when there
Prepared using sagej.cls

Supervisors for Intersection Collision Avoidance

3

Let uj (·) ∈ Uj and wγ (·) ∈ Wγ denote an input signal
to controlled vehicle j ∈ C and a driver-input signal
¯ respectively. Let di (·) =
to uncontrolled vehicle γ ∈ C,
2
3
(dy,i (·), dv,i (·)) ∈ Di denote a disturbance signal of vehicle
¯ We say uj (·) ≤ u0 (·) if uj (t) ≤ u0 (t) for all t.
i ∈ C ∪ C.
3
j
j
1
Similarly, wγ (·) ≤ wγ0 (·) if wγ (t) ≤ wγ0 (t) for all t, and
1
di (·) ≤ d0i (·) if dy,i (t) ≤ d0y,i (t) and dv,i (t) ≤ d0v,i (t) for
all t.
Let xj (t, uj (·), dj (·), xj (0)) denote the state of controlled
vehicle j at time t with an input signal uj (·) and a
disturbance signal dj (·) starting at an initial state xj (0).
Figure 1. Road intersection (left) and its simplified model
(right). We assume that the vehicles follow the prescribed paths, Similarly, let xγ (t, wγ (·), dγ (·), xγ (0)) denote the state of
which intersect at one point. An intersection is modeled as an
uncontrolled vehicle γ at time t with a driver-input signal
area containing this point (the shaded area), and its location is
wγ (·) and a disturbance signal dγ (·) starting at xγ (0).
denoted by an open interval (αi , βi ) along the path of vehicle i. Unless the input signals and initial state are important, we
write xi (t) and xγ (t). We say xi (t) ≤ x0i (t) if yi (t) ≤ yi0 (t)
and vi (t) ≤ vi0 (t) for all t for i ∈ C ∪ C¯ and make the
is no more threat. The other nc̄ = n − nc vehicles are
following assumptions.
not communicating with, and can never be controlled by
the supervisor. The supervisor however can measure their Assumption 1. The functions Fj and Fγ in (1) are orderpositions and speeds and use these measurements to predict preserving. That is, if uj (·) ≤ u0j (·), we have
their possible future behaviors. We define a controlled set
xj (t, uj (·), dj (·), xj (0)) ≤ xj (t, u0j (·), dj (·), xj (0)).
C as a set of controlled vehicles and an uncontrolled set C¯
as a set of uncontrolled vehicles. For notational simplicity, Similarly, if dj (·) ≤ d0j (·), we have
we number the vehicles such that C = {1, 2, . . . , nc } and
xj (t, uj (·), dj (·), xj (0)) ≤ xj (t, uj (·), d0j (·), xj (0)).
C¯ = {nc + 1, nc + 2, . . . , n}.
Furthermore, if xj (0) ≤ x0j (0), we have

2

2.2

Vehicle model

xj (t, uj (·), dj (·), xj (0)) ≤ xj (t, uj (·), dj (·), x0j (0)).

To describe the longitudinal dynamics of vehicle i ∈ The same relations hold for the state of uncontrolled vehicle
¯ we introduce a state xi (t) = (yi (t), vi (t)) ∈ Xi ⊂
C ∪ C,
γ.
2
R , where yi (t) ∈ Yi ⊆ R and vi (t) ∈ [vi,min , vi,max ] ⊂
¯ ẏi (t) ≥ 0 for all
R are the position and the speed along the longitudinal Assumption 2. For all i ∈ C ∪ C,
2
t.
Thus,
the
outputs
y
(t,
u
(·),
dj (·), xj (0)) and
j
j
path. Let di (t) = (dy,i (t), dv,i (t)) ∈ R denote a distury
(t,
w
(·),
d
(·),
x
(0))
are
non-decreasing
in t.
γ
γ
γ
γ
bance, where dy,i (t) ∈ [dy,i,min , dy,i,max ] and dv,i (t) ∈
[dv,i,min , dv,i,max ] account for unmodeled dynamics of Assumption 3. For all j ∈ C, xj (t, uj (·), dj (·), xj (0)) is
yi (t) and vi (t), respectively. The longitudinal dynamics of continuously dependent on uj (·) ∈ Uj , and the input signal
controlled vehicle j ∈ C and uncontrolled vehicle γ ∈ C¯ are space Uj is path-connected.
modeled as
Let x(t, u(·), w(·), d(·), x(0)) denote the aggregate state
with
u(·) ∈ U, w(·) ∈ W, and d(·) ∈ D. This can also be
ẋj = Fj (xj , uj , dj ),
ẋγ = Fγ (xγ , wγ , dγ ),
(1)
written as x(t) if the other arguments are not important.
Notice that the vehicle dynamics (1) are subject to
where uj ∈ Uj := [uj,min , uj,max ] ⊂ R is a throttle or
brake input to controlled vehicle j applied by a supervisor, uncertainty originated from disturbances dj and dγ and
and wγ ∈ [wγ,min , wγ,max ] ⊂ R is a driver-input to an unknown driver-input wγ . In addition to these, we
consider a measurement noise δi := (δy,i , δv,i ) for i ∈ C ∪
uncontrolled vehicle γ.
¯ where δy,i ∈ R and δv,i ∈ R are noises on the position
C,
The parallel composition of (1) is denoted as follows:
measurement ym,i (t) and the speed measurement vm,i (t)
at some time t, respectively. Then, the actual state xi (t) =
ẋ = F(x, u, w, d),
(yi (t), vi (t)) satisfies the following equation:
where
x = (x1 , . . . , xnc , xnc +1 , . . . , xn ) ∈ X,
u=
yi (t) = ym,i (t) + δy,i , vi (t) = vm,i (t) + δv,i . (2)
w = (wnc +1 , wnc +2 , . . . , wn ),
(u1 , u2 , . . . , unc ) ∈ U,
and d = (d1 , . . . , dnc , dnc +1 , . . . , dn ). The output of Let xm,i (t) = (ym,i (t), vm,i (t)) denote the state measurethe system is the position of all vehicles, denoted by ment. Then, (2) can be rewritten as xi (t) = xm,i (t) + δi .
y = (y1 , . . . , ync , ync +1 , . . . , yn ) ∈ Y.
We make an assumption as follows.
Prepared using sagej.cls

4

Journal Title XX(X)

Assumption 4. The measurement noise is bounded, that is,
δi ∈ [δi,min , δi,max ].
The aggregate state measurement is denoted by xm (t),
and then, x(t) = xm (t) + δ, where δ ∈ ∆ := [δmin , δmax ]
is the aggregated measurement noise.

2.3

The state estimation

We define a set of states [xa (t), xb (t)], called the state
estimation, that provides a lower and upper bound of the
exact state, that is, x(t) ∈ [xa (t), xb (t)] for all t. At t = 0,
the state estimation is defined as xa (0) = xm (0) + δmin
and xb (0) = xm (0) + δmax , so that x(0) ∈ [xa (0), xb (0)]
because of (2) and Assumption 4. Given the intial state
estimation [xa (0), xb (0)] and an input signal u(·), the state
estimation [xa (t, u(·), xa (0)), xb (t, u(·), xb (0))] at time t
is defined as follows: for j ∈ C,

3

Problem Statement

Let us define an intersection collision. Since an intersection
is modeled as a single conflict area, we consider a collision
occurs if at least two vehicles are simultaneously inside
the intersection. The output configurations corresponding
to collisions belong to the Bad set, denoted by B ⊂ Y . The
Bad set is defined as follows:
B := {y ∈ Y : yi ∈ (αi , βi ) and yj ∈ (αj , βj )
for some i 6= j such that i ∈ C ∪ C¯ and j ∈ C}.

Throughout this paper, we assume that uncontrolled vehicles
do not crash among themselves. This assumption enables
us to focus on preventing collisions in which at least one
controlled vehicle is involved.
A supervisor runs in discrete time with a time step
τ . At time kτ where k is a nonnegative integer, a
xj (t, uj (·), dj (·), xj (0)), desired input ukdesire ∈ U and a state xm (kτ ) ∈ X are
xaj (t, uj (·), xaj (0)) :=
min
dj (·)∈Dj ,xj (0)
measured. Then, a state estimation [xa (kτ ), xb (kτ )] is
b
∈[xa
j (0),xj (0)]
updated to satisfy x(kτ ) ∈ [xa (kτ ), xb (kτ )] ⊆ [xm (kτ ) +
xj (t, uj (·), dj (·), xj (0)). δmin , xm (kτ ) + δmax ]. The desired input uk
xbj (t, uj (·), xbj (0)) :=
max
desire is a vector
dj (·)∈Dj ,xj (0)
b
of
current
inputs
of
controlled
vehicles’
drivers
at time kτ .
(0),x
(0)]
∈[xa
j
j
input signals
(3) Ask illustrated in Figure 2, we define desired k,∞
udesire (·) ∈ U on time [kτ, (k + 1)τ ) and udesire (·) ∈ U
¯
For γ ∈ C,
on time [kτ, ∞) such that
xaγ (t) :=
xbγ (t) :=

min
wγ (·)∈Wγ ,dγ (·)∈Dγ ,
b
xγ (0)∈[xa
γ (0),xγ (0)]

max
wγ (·)∈Wγ ,dγ (·)∈Dγ ,
b
xγ (0)∈[xa
γ (0),xγ (0)]

xγ (t, wγ (·), dγ (·), xγ (0)),
xγ (t, wγ (·), dγ (·), xγ (0)).
(4)

The
state
estimation
is
denoted
by
[xa (t, u(·), xa (0)), xb (t, u(·), xb (0))] or [xa (t), xb (t)]
if the omitted arguments are not necessary.
By these definitions, the state estimation guarantees that
given an initial state estimation [xa (0), xb (0)] and an input
signal u(·),
x(t, u(·),w(·), d(·), x(0))
a

a

b

b

∈ [x (t, u(·), x (0)), x (t, u(·), x (0))],

(5)

k
ukdesire (t) = uk,∞
desire (t) = udesire for t ∈ [kτ, (k + 1)τ ).
(6)
Also, we define a safe input signal uk,∞
(·)
on
time
[kτ,
∞)
saf e
such that

∀w(·) ∈ W, d(·) ∈ D, x(kτ ) ∈ [xa (kτ ), xb (kτ )],
y(t, uk,∞
/ B for all t.
saf e (·), w(·), d(·), x(kτ )) ∈

(7)

Let uksaf e (·) be uk,∞
saf e (·) restricted to time [kτ, (k + 1)τ ).
The supervisor s([xa (kτ ), xb (kτ )], ukdesire ) is designed
according to the following problem, which is illustrated in
Figure 3.
Problem 1. (Supervisor-design). Design a supervisor
s([xa (kτ ), xb (kτ )], ukdesire ) such that for any w(·), d(·),
and x(kτ ) ∈ [xa (kτ ), xb (kτ )], it returns

k,∞
k

udesire (·) if ∃udesire (·) : for all t ≥ 0
y(t, uk,∞
/B
desire (·), w(·), d(·), x(kτ )) ∈

 k
usaf e (·)
otherwise,

for all t for any w(·) ∈ W and d(·) ∈ D for any x(0) ∈
[xa (0), xb (0)].
Notice that xaj (t, uj (·), xaj (0)) and xbj (t, uj (·), xbj (0))
satisfy the inequalities in Assumption 1. We
can define the position estimation, denoted by
[ya (t, u(·), xa (0)), yb (t, u(·), xb (0)))]
by
letting and it is non-blocking, that is, if s([xa ((k − 1)τ ), xb ((k −
¯
xai (t) = (yia (t), ·) and xbi (t) = (yib (t), ·) for all i ∈ C ∪ C.
1)τ )], uk−1 ) 6= ∅, then for any ukdesire ∈ U, we have
Throughout this paper, we use ‘·’ in a vector if specifying s([xa (kτdesire
), xb (kτ )], ukdesire ) 6= ∅.
the entry is not important. The position estimation also
inherits the order-preserving property from y(t). Later in
The supervisor in Problem 1 is least restrictive in the sense
Section 4.2, this estimation can be updated using the state that overrides are activated only when the desired input of
measurement.
controlled vehicles’ drivers would lead to collisions at some
Prepared using sagej.cls

Supervisors for Intersection Collision Avoidance

5

k,∞
k
Figure 2. uk,∞
desire (·) is an artificially constructed signal that equals to udesire for time [kτ, (k + 1)τ ) as in (6). usaf e (·) is an safe
input signal that makes the system avoid the Bad set as in (7).

supervisor
Does

exist such that for all

for any

and

yes
?

no
Figure 3. Illustration of the supervisor. At time kτ , the supervisor takes the desired input of controlled vehicles’ drivers ukdesire and
the state estimation [xa (kτ ), xb (kτ )]. Depending on the existence of uk,∞
desire (·) that prevents all the vehicles from entering the Bad
set for all t for any w(·) ∈ W, d(·) ∈ D, and x(kτ ) ∈ [xa (kτ ), xb (kτ )], the supervisor either allows the drivers to travel with their
desired input ukdesire (·) or overrides them with the safe input uksaf e (·).

future times. To distinguish between safe and unsafe inputs,
the supervisor needs to verify that the state reached using
the desired input is compatible with a safe evolution of the
system. This introduces the following problem.
Problem 2. (Verification). Given an initial state estimation
[xa (0), xb (0)], determine if there exists an input signal u(·)
that guarantees y(t, u(·), w(·), d(·), x(0)) ∈
/ B for all t ≥ 0
for any w(·) ∈ W, d(·) ∈ D, and x(0) ∈ [xa (0), xb (0)].
By solving Problem 2, the supervisor determines if an
override is necessary. If the desired input leads to a set
of states at which Problem 2 returns no, the supervisor
overrides controlled vehicles with a safe input signal. The
two above problems are solved exactly in the next section,
and approximately in Section 5.

4

Exact solutions

In this section, we provide the solutions of the verification
problem (Problem 2) and the supervisor-design problem
(Problem 1). To solve Problem 2, we formulate an
Inserted Idle-Time scheduling problem, which is solved
straightforwardly, and prove that this problem is equivalent
to Problem 2. We then propose a solution to Problem 1.

4.1

Inserted Idle-Time scheduling problem

Problem 2 can be translated into a scheduling problem,
considering the intersection as a resource that all vehicles
must share. The schedule represents a sequence of the times
Prepared using sagej.cls

at which each controlled vehicle enters an intersection, and
the idle-times represent the sets of times during which an
intersection is potentially occupied by uncontrolled vehicles.
This analogy is characterized mathematically using the
concept of decision problem equivalence.
Definition 1. (Cormen et al. (2009)) Consider two decision
problems A and B. The input to a particular problem is
called an instance of that problem. Then, A is reducible
to B if there is a procedure that transforms any instance α
of A into some instance β of B in polynomial time, and
the answer for α is “yes”, denoted by α ∈ A, if and only if
the answer for β is “yes”, denoted by β ∈ B. We say A is
equivalent to B if and only if A is reducible to B and B is
reducible to A.
An
instance
I
of
Problem
2
is
described
by
([xa (0), xb (0)], S)
where
S :=
¯ α1 , . . . , αn , β1 , . . . , βn ).
(F, X, Y, U, W, D, C, C,
To formulate the IIT scheduling problem, we define
scheduling parameters.
Definition 2. Given an initial state estimation
[xa (0), xb (0)], release times Rj , deadlines Dj , and
process times Pj (Tj ) are defined for controlled vehicles.
For j ∈ C, if yjb (0) < αj ,
Rj :=

min {t ≥ 0 : yjb (t, uj (·), xbj (0)) = αj },

uj (·)∈Uj

Dj := max {t ≥ 0 : yjb (t, uj (·), xbj (0)) = αj }.
uj (·)∈Uj

6

Journal Title XX(X)
distance

distance

time

time

Figure 4. Scheduling parameters in Definition 2. Referring to Figure 1, (αj , βj ) is the location of an intersection along the route of
vehicle j .

¯
for all j ∈ C and γ ∈ C,

Given a real number Tj > 0,
Pj (Tj ) := min {t − Tj ≥ 0 :

(Tj , Tj + Pj (Tj )) ∩ (R̄γ , P̄γ ) = ∅.

uj (·)∈Uj

(10)

yia (t, uj (·), xaj (0)) = βj

Notice that Tj and Pj (Tj ) are defined such that
for some uj (·), yjb (Tj , uj (·), xbj (0)) = αj and yja (Tj +
with constraint
= αj }.
Pj (Tj ), uj (·), xaj (0)) = βj . Condition (8) represents the
If yjb (0) ≥ αj , then Rj = 0, Dj = 0, and Pj (Tj ) = constraint induced on the schedule by the bounded
minuj (·)∈Uj {t : yja (t, uj (·), xaj (0)) = βj }. If yja (0) ≥ βj , input signals. By condition (9), the times during which
then set Rj = 0, Dj = 0, and Pj (Tj ) = 0. If the constraint controlled vehicles i and j occupy the intersection for any
disturbance do not overlap. This implies that a collision
is not satisfied, set Pj (Tj ) = ∞.
Idle-times (R̄γ , P̄γ ) are defined for uncontrolled vehicles. between controlled vehicles i and j is averted. Similarly,
condition (10) implies that vehicle j does not occupy
¯ if yγb (0) < αγ ,
For γ ∈ C,
the intersection during the idle-time, thereby preventing
a collision between controlled vehicle j and uncontrolled
R̄γ := {t ≥ 0 : yγb (t) = αγ },
vehicle γ. Thus, a schedule satisfying the above conditions is
a
P̄γ := {t ≥ 0 : yγ (t) = βγ }.
related to an input signal that can prevent any future collision.
This is the essence of the proof of the following theorem.
b
a
If yγ (0) ≥ αγ , set R̄γ = 0 and P̄γ = {t : yγ (t) = βγ }. If
Theorem 1. Problem 2 and Problem 3 are equivalent.
yγa (0) ≥ βγ , set R̄γ = 0 and P̄γ = 0.
yjb (Tj , uj (·), xbj (0))

In this definition, release time Rj is the earliest that
controlled vehicle j can enter an intersection while deadline
Dj is the latest. Given that controlled vehicle j enters the
intersection no earlier than time Tj , process time Pj (Tj ) is
the earliest that it can cross the intersection. Uncontrolled
vehicle γ enters and exits the intersection within the idletime (R̄γ , P̄γ ) regardless of its driver-input and disturbance
signals. These parameters are illustrated in Figure 4.
The Inserted Idle-time (IIT) scheduling problem is
formulated as follows.

Proof. By Definition 1, we need to show two things:
Problem 2 is reducible to Problem 3, and Problem 3
is reducible to Problem 2. Notice that an instance I of
Problem 3 is also described by ([xa (0), xb (0)], S), which
is the same as an instance of Problem 2. Thus, the
transformation between the instances of these problems takes
constant time. Now, the following relation is left to prove
the equivalence.

Problem 3. (IIT scheduling). Given an initial state
estimation [xa (0), xb (0)], determine whether there exists a
schedule T = (T1 , . . . , Tnc ) ∈ Rn+c such that for all j ∈ C,

(⇒) Given an initial state estimation [xa (0), xb (0)],
there is an input signal ũ(·) ∈ U such that
y(t, ũ(·), w(·), d(·), x(0)) ∈
/ B for all t for any w(·) ∈ W
and d(·) ∈ D for any x(0) ∈ [xa (0), xb (0)].
Using ũj (·) for j ∈ C, which denotes the j-th element
of ũ(·), let T̃j be the time at which yjb (t, ũj (·), xbj (0)) = αj
if yjb (0) < αj . If yjb (0) ≥ αj , set T̃j = 0. This satisfies the
constraint of Pj (T̃j ) in Definition 2. Let T̃j + P̃j (T̃j ) be the

Rj ≤ Tj ≤ Dj ,

(8)

(Ti , Ti + Pi (Ti )) ∩ (Tj , Tj + Pj (Tj )) = ∅,

(9)

for all i 6= j ∈ C,

Prepared using sagej.cls

I ∈ Problem 2 ⇔ I ∈ Problem 3.

Supervisors for Intersection Collision Avoidance

7

time at which yja (t, ũj (·), xaj (0)) = βj . Set P̃j (T̃j ) = 0 if
We now provide an algorithm that solves Problem 3,
yja (0) ≥ βj .
which, in turn, solves Problem 2 by Theorem 1. This
By the definitions of Rj and Dj , condition (8) is satisfied. algorithm contains two procedures. The first procedure,
Suppose without loss of generality, T̃i ≤ T̃j . At t = T̃j , S CHEDULING, generates a schedule T given a sequence
we have yjb (t, ũj (·), xbj (0)) = αj . Since ũi (·) and ũj (·) π such that Tπi ≤ Tπj if i < j, and evaluates whether T
guarantee that at most one vehicle is inside an intersection, satisfies conditions (8)-(10). Here, πi denotes the i-th entry
we must have yia (t, ũi (·), xai (0)) ≥ βi . Because yja (t) is of π and Tπi the πi -entry of T. The second procedure,
non-decreasing in time, T̃i + P̃i (T̃i ) ≤ t. By the definition E XACT, inspects all possible sequences until a sequence
of Pi (T̃i ), we have T̃i + Pi (T̃i ) ≤ T̃i + P̃i (T̃i ) ≤ t = T̃j , with a feasible schedule is found. If a feasible schedule is
which concludes (T̃i , T̃i + Pi (T̃i )) ∩ (T̃j , T̃j + Pj (T̃j )) = found, the answer of Problem 2 is yes, and otherwise, the
answer is no.
∅ (condition (9)).
Algorithm 1 focuses on vehicles before an intersection.
In order to avoid the Bad set, vehicle γ ∈ C¯ is
The
set of such vehicles is denoted by M := {j ∈
not inside an intersection during [T̃j , T̃j + P̃ (T̃j )] for
b
b
a
b
C
:
y
j (0) < αj }. For simplicity, let yj (0) < αj for j ∈
any wγ (·) ∈ Wγ , dγ (·) ∈ Dγ , and xγ (0) ∈ [xγ (0), xγ (0)].
b
Since yγb (R̄γ ) = αγ and yγa (P̄γ ) = βγ by Definition 2, we {1, . . . , |M|} and yj (0) ≥ αj for j ∈ {|M| + 1, . . . , nc }.
Let P be a set of all permutations of M. Its cardinality
have (T̃j , T̃j + P̃j (T̃j )) ∩ (R̄γ , P̄γ ) = ∅. By the definition
is (|M|)! = 1 × 2 × . . . × |M|. Let π ∈ R|M| be a vector
of Pj (T̃j ), we have (T̃j , T̃j + Pj (T̃j )) ⊂ (T̃j , T̃j + P̃j (T̃j )).
in P. Let π̄ ∈ Rnc̄ be a vector of γ ∈ C¯ in an increasing
Thus, (T̃j , T̃j + Pj (T̃j )) ∩ (R̄γ , P̄γ ) = ∅. (condition (10)). order of R̄ , that is, R̄ ≤ R̄ for j ≤ j 0 . Let π and π̄
γ
π̄j
π̄j 0
0,j
j
This proves that there exists the schedule T̃ that satisfies denote the j-th entry of π0 and π̄, respectively.
conditions (8), (9), and (10).
(⇐) Given an initial state estimation [xa (0), xb (0)], there
exists a schedule T̃ ∈ Rnc that satisfies the conditions of
Problem 3.
For j ∈ C, define ũj (·) such that yjb (T̃j , ũj (·), xbj (0)) =
αj if yjb (0) < αj . If yjb (0) ≥ αj and yja (0) ≤ βj , define
ũj (·) such that yja (T̃j + Pj (T̃j ), ũj (·), xaj (0)) = βj . If
yja (0) > βj , we do not consider vehicle j because it has
already crossed the intersection. Since yja (t, uj (·), xaj (0))
depends continuously on uj (·) ∈ Uj and Uj is path
connected by Assumption 3, condition (8) implies that such
an input signal exists, i.e., ũj (·) ∈ Uj .
Consider ũi (·) and ũj (·) for i 6= j ∈ C where T̃i ≤
T̃j . Condition (9) says T̃i + Pi (T̃i ) ≤ T̃j . At time t ∈
[T̃i + Pi (T̃i ), T̃j ], we have yia (t, ũi (·), xai (0)) ≥ βi and
yjb (t, ũj (·), xbj (0)) ≤ αj . Thus, for any disturbance and
initial condition, vehicle j enters the intersection after
vehicle i leaves it.
¯ condition (10) implies
For j ∈ C and γ ∈ C,
either P̄γ ≤ Tj or T̃j + Pj (T̃j ) ≤ R̄γ . In the first
case, at any time t ∈ [P̄γ , Tj ], we have yγa (t) ≥ βγ
and yjb (t, ũj (·), xbj (0)) ≤ αj
so that for any
wγ (·) ∈ Wγ , dγ (·) ∈ Dγ , xγ (0) ∈ [xaγ (0), xbγ (0)]
and
for any dj (·) ∈ Dj , xj (0) ∈ [xaj (0), xbj (0)], after vehicle
γ exits the intersection, vehicle j enters it. In the
second case, at any time t ∈ [T̃j + Pj (T̃j ), R̄γ ], we have
yja (t, ũj (·), xaj (0)) ≥ βj and yγb (t) ≤ αγ . This means
after vehicle j exits the intersection for any dj (·) ∈ Dj
and xj (0) ∈ [xaj (0), xbj (0)], vehicle γ enters it for any
wγ (·) ∈ Wγ , dγ (·) ∈ Dγ , and xγ (0) ∈ [xaγ (0), xbγ (0)].
Therefore, the schedule T̃ ensures that there exists an
input signal ũ(·) which prevents entering the Bad set.
Prepared using sagej.cls

Algorithm 1 Exact Solution of Problem 3
1: procedure S CHEDULING (π0 , [xa (0), xb (0)], S)
2:
for all j ∈ C do calculate Rj , Dj
3:
for all γ ∈ C¯ do calculate R̄γ , P̄γ
4:
M = {j ∈ C : yjb (0) < αj } and M̄ = C \ M
5:
Tj = 0 ∀ j ∈ M̄ and Pmax = maxj∈M̄ Pj (Tj )
6:
π = (π0,j : π0,j ∈ M for j = 1 to |π0 |)
7:
for i = 1 to |M| do
8:
if i = 1 then Tπ1 = max(Rπ1 , Pmax )
9:
else if i ≥ 2 then
10:
Tπi = max(Rπi , Tπi−1 + Pπi−1 (Tπi−1 ))
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

for j = 1 to nc̄ do
if Tπi ≥ R̄π̄j then
Tπi = max(Tπi , P̄π̄j )
else if Tπi + Pπi (Tπi ) > R̄π̄j then
Tπi = P̄π̄j
if Tj ≤ Dj for all j ∈ C then return (T, yes)
return (∅, no)
procedure E XACT([xa (0), xb (0)], S)
if [ya (0), yb (0)] ∩ B 6= ∅ then return (∅, no)
M = {j ∈ C : yjb (0) < αj } and M̄ = C \ M
if |M| = 0 then return (∅, yes)
for all π ∈ P do
(T, ans) = S CHEDULING(π, [xa (0), xb (0)], S)
if ans = yes then return (T, yes)
return (∅, no)

Procedure S CHEDULING in Algorithm 1 works as follows.
In lines 2-3, the scheduling parameters in Definition 2 are

8

Journal Title XX(X)

Correction of
state estimation

State prediction
using

(eq. (12))

(eqs. (9), (10))

supervisor
yes

Verification
no

store

Safe input
generator
(eq. (13))

State prediction
using
(eqs. (9), (10))

Figure 5. Schematic of the supervisor at time kτ . Using the state measurement xm (kτ ) and the previous step’s state prediction
a
b
a
b
Xpred (uk−1
out (·)), the state estimation is corrected to [x (kτ ), x (kτ )]. The supervisor takes [x (kτ ), x (kτ )] and the current
desired input ukdesire and returns either ukdesire (·) or uksaf e (·) depending on the answer of the verification problem. When the
answer is no, the state prediction Xpred (uksaf e (·)) guarantees the existence of a feasible schedule T2 , thereby ensuring the
non-blocking property of the supervisor. At each step, a safe input signal uk+1
saf e (·) is generated using a feasible schedule and
stored for a possible use at the next step.

evaluating all permutations in P, an empty set and answer
no are returned in line 25.
The running time of procedure E XACT is determined
by the for loops of lines 22-24. For the worst case, all
permutations in P must be evaluated. As the number of
controlled vehicles increases, the computation time increases
exponentially. Indeed, a scheduling problem is known
to be NP-hard (Colombo and Del Vecchio (2012)). To
avoid this computational complexity issue, we devise an
In a given sequence π, vehicle πi−1 crosses the
approximate algorithm to solve the IIT scheduling problem
intersection earlier than vehicle πi . Given this sequence π,
with the guarantee of a quantified approximation bound. This
procedure S CHEDULING finds the earliest possible schedule.
approximate algorithm is provided in Section 5.1.
In the for loop of lines 11-15, uncontrolled vehicle π̄j is
considered. If line 12 is true, then line 13 ensures that
Tπi ≥ P̄π̄j so that condition (10) is satisfied. Otherwise, if 4.2 Exact supervisor
line 14 is true, meaning that Tπi < R̄π̄j < Tπi + Pπi (Tπi ), In this section, we solve Problem 1 by providing an
then Tπi is delayed to P̄π̄j in line 15 so that condition (10) algorithm implementing the exact supervisor.
becomes satisfied. The schedule Tπi takes P̄π̄j , which is the
The schematic of a supervisor at time kτ is illustrated in
earliest possible value. Otherwise, Tπi + Pπi (Tπi ) ≤ R̄π̄j
Figure 5. The state prediction computed at the previous
so that condition (10) is guaranteed. Lastly, in line 16, the
k−1
step Xpred (uk−1
out (·)) is known, where uout (·) is the
right inequality of condition (8) is checked. If line 16 is true,
output that the supervisor returns at the previous step,
this procedure returns a feasible schedule and answer yes. If
that is, controlled vehicles traveled with uk−1
out (·) for time
Tj > Dj for some j, since the schedule T is constructed so
[(k − 1)τ, kτ ). Also, the state measurement xm (kτ ) is
that it is the earliest possible value, there cannot be another
received. These state prediction and measurement are used
schedule T̃ such that T̃j ≤ Dj . Thus, no feasible schedule
to update the state estimation [xa (kτ ), xb (kτ )]. This state
can be found in this sequence π, and the procedure returns
estimation and the desired input ukdesire are the inputs to
no.
the supervisor and used to predict the state at the next
Procedure E XACT in Algorithm 1 solves Problem 3 by time step, denoted by Xpred (ukdesire (·)). Given this state
inspecting all permutations in P until a feasible schedule prediction, the verification problem is solved. If the answer
is found as noted in lines 22-24. In line 19, if a given is yes, the supervisor allows the controlled vehicles to
initial position estimation is already inside the Bad set, travel with the desired input for time [kτ, (k + 1)τ ). A
the procedure returns no. In line 21, if yjb (0) ≥ αj for all safe input signal uk+1
saf e (·) is generated using a feasible
j ∈ C, then it returns yes since all controlled vehicles have schedule T1 and stored for a possible use at the next
entered the intersection. If no feasible schedule is found after time step. If the answer is no, a safe input signal uksaf e (·)

computed given an initial state estimation. In lines 4 and 5,
if yjb (0) ≥ αj , Tj = 0 because Rj = Dj = 0 and Pmax is
the time at which all vehicles j ∈ M̄ exit the intersection.
The input argument π0 is the vector of the indexes of all
vehicles controlled by the supervisor. The assignment at
line 6 extracts from π0 the sub-vector π of vehicles which
have not yet reached the intersection. The schedule needs
only be computed for the sub-vector π.

Prepared using sagej.cls

Supervisors for Intersection Collision Avoidance

9

stored at the previous step is used to override the controlled
vehicles. It will be proved in this section that the state
prediction Xpred (uksaf e (·)) always has a feasible schedule
T2 , that is, Xpred (uksaf e (·)) ∈ Problem 2. A safe input
signal uk+1
saf e (·) is generated using T2 and stored. The
k
output uout (·) is either ukdesire (·) or uksaf e (·), and the state
prediction Xpred (ukout (·)) will be used at the next step to
correct the state estimation with a new state measurement.
In the last section, we presented Algorithm 1 that
solves the verification problem. This section describes
the remaining components: state prediction, correction of
the state estimation, and a safe input generator. Also, an
algorithm to implement the supervisor is presented with the
proof that this supervisor is the solution of Problem 1.

then y(t, uk,∞
/ B for all t for any
desire (·), w(·), d(·), x(kτ )) ∈
w(·) and d(·) for any x(kτ ) ∈ [xa (kτ ), xb (kτ )].

4.2.1 State prediction. Using the dynamic model (1),

xa (kτ ) = max(min Xpred (uk−1
out (·)), xm (kτ ) + δmin ),

this function predicts the state reached at the next time
step with a given input signal starting from a set of states.
Suppose that at time kτ , we have the state estimation
[xa (kτ ), xb (kτ )] and the input uk (·) ∈ U defined on time
[kτ, (k + 1)τ ). The state prediction Xpred (uk (·)) =
[min Xpred (uk (·)), max Xpred (uk (·))] ⊂ X
is
a set of possible states at the next time step.
Its i-th set is denoted by Xpred,i (uki (·)) =
[min Xpred,i (uki (·)), max Xpred,i (uki (·))].
The
state
prediction is defined as follows: for j ∈ C,

xb (kτ ) = min(max Xpred (uk−1
out (·)), xm (kτ ) + δmax ).
(14)

min Xpred,j (ukj (·)) =

min xj (τ, ukj (·), dj (·), xaj (kτ )),

dj (·)∈Dj

max Xpred,j (ukj (·)) = max xj (τ, ukj (·), dj (·), xbj (kτ )).
dj (·)∈Dj

(11)

max Xpred,γ =

min
wγ (·)∈Wγ ,
dγ (·)∈Dγ

xγ (τ, wγ (·), dγ (·), xaγ (kτ )),

max
wγ (·)∈Wγ ,
dγ (·)∈Dγ

xγ (τ, wγ (·), dγ (·), xbγ (kτ )).
(12)

By definition, min Xpred (uk (·)) is the smallest state
propagated from xa (kτ ) for time τ with the input uk (·)
for any disturbance and any driver-input of uncontrolled
vehicles, and max Xpred (uk (·)) is the largest.
Notice that E XACT(Xpred (ukdesire (·)), S) in Algorithm 1
determines the existence of an input signal uk+1,∞
saf e (·)
that satisfies y(t, uk+1,∞
/B
saf e (·), w(·), d(·), x((k + 1)τ )) ∈
for all t for any w(·) and d(·) for any x((k + 1)τ ) ∈
Xpred (ukdesire ). If we define uk,∞
desire (·) as
(
ukdesire
for t ∈ [kτ, (k + 1)τ ),
k,∞
udesire (t) =
(13)
k+1,∞
usaf e (t) for t ∈ [(k + 1)τ, ∞),
Prepared using sagej.cls

state measurement is received, this function restricts the state
estimation so that it is compatible with the state measurement
and the state prediction computed at the previous step.
Suppose the supervisor returns uk−1
out (·) at time (k − 1)τ .
Then, at time kτ , we have x(kτ ) ∈ Xpred (uk−1
out (·)) by
definitions (11) and (12). Also, a new state measurement
xm (kτ ) is received, which implies x(kτ ) ∈ [xm (kτ ) +
δmin , xm (kτ ) + δmax ]. Thus, we make a correction of
the state estimation [xa (kτ ), xb (kτ )] at time kτ as the
intersection of these two intervals. That is,

Notice that this correction still guarantees x(kτ ) ∈
[xa (kτ ), xb (kτ )]. The supervisor takes this corrected state
estimation as an input as shown in Figure 5.
4.2.3 Safe input generator. Given a feasible schedule,

this function generates a corresponding safe input signal.
This is possible because the existence of a feasible schedule
implies the existence of a safe input signal by Theorem 1.
We define a safe input generator σ(Xpred (uk (·)), T) to
compute uk+1,∞
saf e (·), where T is the schedule returned by
E XACT(Xpred (uk (·)), S). For j ∈ C, if Tj > 0,
σj (Xpred,j (ukj (·)), Tj ) := uk+1,∞
saf e,j (·)

¯
For γ ∈ C,
min Xpred,γ =

4.2.2 Correction of the state estimation. Once a new

∈ {uj (·) ∈ Uj :
yja (Tj + Pj (Tj ), uj (·), min Xpred,j (ukj (·))) = βj
and yjb (Tj , uj (·), max Xpred,j (ukj (·))) = αj },
(15)
where σj (Xpred,j (ukj (·)), Tj ) is the j-th entry of
σ(Xpred (uk (·)), T). If Tj = 0, then let uk+1,∞
saf e,j (t) =
uj,max for t ∈ [(k + 1)τ, ∞). The safe input signal
uk+1,∞
saf e,j (·) makes controlled vehicle j enter the intersection
no earlier that Tj and exit it no later than Tj + Pj (Tj ).
If E XACT(Xpred (ukdesire ), S) finds a feasible schedule
T, the supervisor computes a safe input signal uk+1
saf e (·),
which is uk+1,∞
saf e (t) restricted to t ∈ [(k + 1)τ, (k + 2)τ ).
The supervisor stores this safe input signal for a possible use
at the next time step.
4.2.4 Solution of Problem 1 The supervisor is imple-

mented in procedure S UPERVISOR in Algorithm 2.

10

Journal Title XX(X)

Algorithm 2 Implementation of the supervisor
procedure S UPERVISOR([xa (kτ ), xb (kτ )], ukdesire )
(T1 , ans) = E XACT(Xpred (ukdesire (·)), S)
if ans = yes and for all t ∈ [0, τ ), B ∩
[xa (t, ukdesire (·), xa (kτ )), xb (t, ukdesire (·), xb (kτ ))] =
∅ then
k
4:
uk+1,∞
saf e (·) = σ(Xpred (udesire (·)), T1 )
1:
2:
3:

k+1,∞
uk+1
saf e (·) = usaf e (t) for t ∈ [(k + 1)τ, (k +

5:

2)τ )
6:
7:
8:
9:

ukdesire (·)

return
else
(T2 , ·) = E XACT(Xpred (uksaf e (·)), S)
k
uk+1,∞
saf e (·) = σ(Xpred (usaf e (·)), T2 )
uk+1
saf e (·)

10:

=

uk+1,∞
saf e (t)

for t ∈ [(k + 1)τ, (k +

2)τ )
11:

return uksaf e (·)

To initiate the procedure, it is assumed that initial
state estimation [xa (0), xb (0)] and initial desired input
u0desire do not cause collisions at any future time. That
is, E XACT(Xpred (u0desire ), S) must return yes so that
S UPERVISOR([xa (0), xb (0)], u0desire ) 6= ∅.
Theorem 2. Procedure S UPERVISOR in Algorithm 2
implements the supervisor s designed in Problem 1.
Proof. Procedure S UPERVISOR returns ukdesire (·) in line 6
k+1,∞
if ans1 is yes. This implies that there exists usaf
e (·),

in line 11. In either case, ukout (·) 6= ∅. In the former
case, ans = yes and T1 exists, which implies by
Theorem 1 that there exists an input signal guaranteeing
the avoidance of the Bad set for any uncertainty. Thus,
k
uk+1,∞
saf e (·) = σ(Xpred (udesire ), T1 ) is well-defined on
time [(k + 1)τ, ∞). In the latter case, we consider
E XACT(Xpred (uksaf e (·)), S). Here, uksaf e (·) is uk,∞
saf e (·)
restricted to time [kτ, (k + 1)τ ). If let uk+1,∞
saf e (·) be
uk,∞
saf e (·) restricted to time [(k + 1)τ, ∞), we can rewrite
(16) as
∀x((k + 1)τ ) ∈ [xa (τ, uksaf e (·), min Xpred (uk−1
out (·))),
xb (τ, uksaf e (·), max Xpred (uk−1
out (·)))],
y(t, uk+1,∞
/ B.
saf e (·),w(·), d(·), x((k + 1)τ )) ∈

(17)

Since by (14), [xa (kτ ), xb (kτ )] ⊆ Xpred (uk−1
out (·)),
the state prediction Xpred (uksaf e (·)), which denotes
[xa (τ, uksaf e (·), xa (kτ )), xb (τ, uksaf e (·), xb (kτ ))], satisfies
Xpred (uksaf e (·)) ⊆ [xa (τ, uksaf e (·), min Xpred (uk−1
out (·))),
xb (τ, uksaf e (·), max Xpred (uk−1
out (·)))],
(18)
due to the order-preserving property with respect to an initial
state in Assumption 1. Thus, (17) is still satisfied for any
x((k + 1)τ ) ∈ Xpred (uksaf e (·)). That is, T2 in line 8 exists,
k
and uk+1,∞
saf e (·) = σ(Xpred (usaf e ), T2 ) is well-defined.
Therefore, the supervisor is non-blocking.

which in turn, implies by (13) that there exists uk,∞
desire (·)
k,∞
that satisfies y(t, udesire (·), w(·), d(·), x(kτ )) ∈
/ B for all
t for any w(·) and d(·) for any x(kτ ) ∈ [xa (kτ ), xb (kτ )].
5 Approximate solutions
Otherwise, it returns uksaf e (·) in line 11. This structure
corresponds to the supervisor design in Problem 1.
5.1 Efficient Verification
We prove the non-blocking property by mathematical
While scheduling problems on a single machine with
induction on time step k. For the base case, it
arbitrary release times, deadlines, and process times are
is assumed that S UPERVISOR([xa (0), xb (0)], u0desire ) =
known to be NP-hard, Garey et al. (1981) proved that the
u0out (·) 6= ∅ where u0out (·) is defined on time [0, τ ),
complexity can be reduced to O(n log n) if process times
1,∞
1,∞
and usaf e (·) is well-defined. We say usaf e (·) is wellof all jobs are identical. This was done using “forbidden
defined if there exists a schedule T that defines
regions” and the “earliest deadline scheduling (EDD)”
1,∞
usaf e (·) as σ(Xpred (u0desire (·)), T). Suppose at t =
rule. Forbidden regions are time intervals during which
(k − 1)τ , we have S UPERVISOR([xa ((k − 1)τ ), xb ((k − no feasible job is allowed to start, and can be computed
k,∞
k−1
1)τ )], uk−1
desire ) = uout (·) 6= ∅ and usaf e (·) is well-defined. in O(n log n) time. Once forbidden regions are computed,
EDD can be used to solve the scheduling problem in
That is, there exists uk,∞
saf e (·) that for all t ≥ 0 for any w(·)
O(n log n) time.
and d(·),
We design Algorithm 3 by modifying Garey’s result
∀x(kτ ) ∈Xpred (uk−1
out (·)),
to
handle inserted idle-times. We define initial forbidden
(16)
regions
F0 to account for the idle-times and set them as
y(t, uk,∞
(·),
w(·),
d(·),
x(kτ
))
∈
/
B.
saf e
inputs of Algorithm 3. In Garey’s result, forbidden regions
Then, at t = kτ , we need to show that ukout (·) 6= ∅ no matter are initially declared empty and not taken as inputs.
what ukdesire is applied, and uk+1,∞
In the procedure in Algorithm 3, rj , dj , and tj denote
saf e (·) is well-defined.
In Algorithm 2, S UPERVISOR([xa (kτ ), xb (kτ )], ukdesire ) the j-th entry of r, d, and t, respectively, and F0,γ the γ-th
assigns ukout (·) either ukdesire (·) in line 6 or uksaf e (·) interval of F0 so that F0 = ∪γ F0,γ . Critical time c is the
Prepared using sagej.cls

Supervisors for Intersection Collision Avoidance

11

latest time at which a job can start at each iteration. A set A
contains jobs that have not been scheduled but are ready to
be scheduled at time s, which means their release times are
smaller than or equal to s. A set B contains all jobs that have
not been yet scheduled. Initially, B = {1, . . . , |r|} where |r|
is the cardinality of r.

The proof of Lemma 1 is provided in Appendix B.
To use Algorithm 3, we assign a time interval of equal
length to cross the intersection to all vehicles, and formulate
a relaxed IIT scheduling problem. The identical process time
θmax is defined as follows:
θmax := max

max

j∈C Rj ≤Tj ≤Dj

Pj (Tj ).

(22)

Algorithm 3 Modified version of the result of Garey et al.
(1981)
Here, θmax is the maximum time that any controlled vehicle
spends crossing an intersection, so that θmax ≥ Pj (Tj )
1: procedure P OLYNOMIAL (r, d, F0 )
Let σ be a vector of indexes in an increasing order of for all j ∈ C for any Tj ∈ [Rj , Dj ]. In other words, all
2:
controlled vehicles are guaranteed to cross the intersection
r and F = F0 .
3:
for i = |r| to 1 do . Forbidden Region Declaration within θmax .
By replacing Pj (Tj ) in Problem 3 with θmax , the relaxed
4:
for j ∈ {j : dj ≥ dσi } do
IIT scheduling problem is formulated as follows.
5:
if cj undefined then cj = dj
6:
else cj = cj − 1
Problem 5. (Relaxed IIT scheduling). Given an initial state
7:
if cj ∈ Fγ for some γ then cj = inf Fγ
estimation [xa (0), xb (0)], determine whether there exists a
8:
if σi = 1 or rσi−1 < rσi then
schedule T = (T1 , . . . , Tnc ) ∈ Rn+c such that for all j ∈ C,
9:
c = min{cj : cj defined}
Rj ≤ Tj ≤ Dj ,
(23)
10:
if c < rσi then ans = no
11:
if rσi ≤ c < rσi + 1 then F = F ∪ (c − 1, rσi )
for all i 6= j ∈ C if Ti , Tj > 0,
12:
s = 0, A = ∅, B = {1, . . . , |r|}
. Schedule
Generation
(Ti , Ti + θmax ) ∩ (Tj , Tj + θmax ) = ∅,
(24)
13:
while B 6= ∅ do
14:
if s ∈ Fγ for some γ then s = sup Fγ
for all j ∈ C and γ ∈ C¯ if Tj > 0,
15:
if A = ∅ then j = arg minj∈B rj and tj = rj
(Tj , Tj + θmax ) ∩ (R̄γ , P̄γ ) = ∅.
(25)
16:
else j = arg minj∈A dj and tj = s
s = s + 1, B = B \ {j} and A = {k ∈ B : rk ≥

17:

s}
18:
19:
20:
21:

π ∗ = a vector of indexes in an increasing order of t
if ans = no then
return (∅, π ∗ , no)
else return (t, π ∗ , yes)

In the following lemma, we prove that procedure
P OLYNOMIAL in Algorithm 3 solves the IIT scheduling
problem with unit process times. This problem is formulated
as follows.
Problem 4. Given r, d, r̄, p̄, determine the existence of a
schedule t satisfying
for all j,

tj ∈ [rj , dj ],

(19)

for all i 6= j,

(ti , ti + 1) ∩ (tj , tj + 1) = ∅,

(20)

for all j and γ,

(tj , tj + 1) ∩ (r̄γ , p̄γ ) = ∅,

(21)

where (r̄γ , p̄γ ) denotes the γ-th inserted idle-time.
Lemma 1. Procedure P OLYNOMIAL in Algorithm 3 solves
the IIT scheduling problem with unit process times and finds
a feasible schedule if exists.
Prepared using sagej.cls

If Tj = 0, (0, Pj (0)) replaces (Tj , Tj + θmax ) in conditions (24) and (25).
The following algorithm solves this problem by
employing P OLYNOMIAL. This is an exact solution for
Problem 5 by Lemma 1. At line 7, we call 0 the zero vector
in Rnc .
Algorithm 4 Exact Solution of Problem 5
1: procedure RELAXEDEXACT([xa (0), xb (0)], S)
2:
if [ya (0), yb (0)] ∩ B 6= ∅ then return (∅, ∅, no)
3:
for all j ∈ C do calculate Rj , Dj , θmax
4:
for all γ ∈ C¯ do calculate R̄γ , P̄γ
5:
Fγ = (max(R̄γ /θmax − 1, 0), P̄γ /θmax )
6:
M = {j ∈ C : yjb (0) < αj } and M̄ = C \ M
7:
if |M| = 0 then return (∅, 0, yes)
8:
Tj = 0 for all j ∈ M̄ and Pmax = maxj∈M̄ Pj (Tj )
9:
for all j ∈ M do
10:
rj = max(Rj , Pmax )/θmax and dj = Dj /θmax
11:
(t, π ∗ , ans) = P OLYNOMIAL(r, d, F)
12:
if ans = yes then Tj = tj θmax , ∀j ∈ M
13:
return (T, π ∗ , yes)
14:
else return (∅, π ∗ , no)

12

Journal Title XX(X)

In this procedure, all parameters are normalized by θmax
because procedure P OLYNOMIAL assumes unit process
times. In line 5, the idle-time (R̄γ , P̄γ ) is translated into
an initial set of forbidden regions Fγ so that condition (25)
is equivalent to tj ∈
/ Fγ . If tj ∈ Fγ , then Tj ∈ (max(R̄γ −
θmax , 0), P̄γ ) so that either Tj ∈ (R̄γ , P̄γ ) or Tj + θmax ∈
(R̄γ , P̄γ ).
The running time of procedure RELAXEDEXACT is
dominated by P OLYNOMIAL in line 11, which has an
asymptotic running time of O(n2c ).
By exploiting procedure RELAXEDEXACT in Algorithm 4,
we design a new procedure, called A PPROX, that solves
Problem 2 within an approximation bound. This procedure
schedules vehicles according to a sequence returned by
procedure RELAXEDEXACT, thereby inheriting computational
efficiency. This sequence is denoted by π ∗ in the following
algorithm.
Algorithm 5 Approximate Solution of Problem 3
procedure A PPROX([xa (0), xb (0)], S)
if [ya (0), yb (0)] ∩ B 6= ∅ then return (∅, no)
3:
if yjb (0) ≥ αj for all j ∈ C then return (∅, yes)
1:
2:

4:
5:

(·, π ∗ , ·) = RELAXEDEXACT([xa (0), xb (0)], S)
(T, ans) = S CHEDULING(π ∗ , [xa (0), xb (0)], S)

Procedure A PPROX in Algorithm 5 trades exactness for
computational efficiency. We will prove that procedure
A PPROX is more conservative than procedure E XACT, that
is, there exists an instance I = ([xa (0), xb (0)], S) such that
A PPROX(I) returns no while E XACT(I) returns yes. In
order to quantify the degree of conservatism, we prove
two theorems. The first theorem states that if procedure
A PPROX returns yes, then there exists an input signal to
avoid the Bad set. In the second theorem, if procedure
A PPROX returns no, then there does not exist an input
signal to avoid an inflated Bad set, which accounts for the
conservatism.

Problem 2, procedure A PPROX can return no. To consider
these instances, we introduce an inflated Bad set.
The IIT scheduling problem finds a schedule satisfying
yjb (Tj ) = αj and yja (Tj + Pj (Tj )) = βj for j ∈ C. In
contrast, the relaxed IIT scheduling problem finds a schedule
satisfying yjb (Tj ) = αj and yja (Tj + θmax ) ≥ βj . Given
that the farthest distance that controlled vehicle j can
travel during θmax is θmax vj,max , we define an “inflated”
intersection (αj , β̂j ) such that β̂j := αj + θmax vj,max .
Notice that βj ≤ β̂j . Because the process times are only
¯ Thus,
defined for controlled vehicles, β̂γ = βγ for γ ∈ C.
inflated Bad set B̂ is defined as follows:
B̂ := {y ∈ Y : yi ∈ (αi , β̂i ) and yj ∈ (αj , β̂j )
for some i 6= j such that i ∈ C ∪ C¯ and j ∈ C}.
(26)
By replacing Bad set B in Problem 2 with inflated Bad
set B̂, we can formulate the relaxed verification problem.
The following theorem is a key result that shows the
approximation bound of procedure A PPROX.
Lemma 2. If A PPROX([xa (0), xb (0)], S) = (T, yes),
and
RELAXEDEXACT([xa (0), xb (0)], S) = (T̄, π ∗ , yes),
then Tj ≤ T̄j for all j ∈ C.
Lemma 3. If A PPROX([xa (0), xb (0)], S) = (∅, no), then
RELAXEDEXACT([xa (0), xb (0)], S) = (∅, π ∗ , no).
The proofs of Lemmas 2 and 3 can be found in Appendix
B.
Theorem 4. If A PPROX([xa (0), xb (0)], S) = (∅, no),
then there is no input signal u(·) that guarantees
y(t, u(·), w(·), d(·), x(0)) ∈
/ B̂ for all t ≥ 0 for any
w(·) ∈ W, d(·) ∈ D, and x(0) ∈ [xa (0), xb (0)].

Proof. By Lemma 3, A PPROX([xa (0), xb (0)], S) = (∅, no)
means that RELAXEDEXACT returns no. Thus, we will prove
that if there is no schedule satisfying conditions (23)-(25),
Theorem 3. If A PPROX([xa (0), xb (0)], S) = (T, yes), there is no input signal to avoid the inflated Bad set for any
uncertainty. For ease of proof, we prove the contrapositive
then ([xa (0), xb (0)], S) ∈ Problem 2.
statement. That is, assume that there is an input signal
Proof. By Theorem 1, we only need to show that ũ(·) ∈ U such that y(t, ũ(·), w(·), d(·), x(0)) ∈
/ B̂ for all
([xa (0), xb (0)], S) ∈ Problem 3. Notice that procedure t for any w(·) ∈ W, d(·) ∈ D, and x(0) ∈ [xa (0), xb (0)].
A PPROX of Algorithm 5 returns yes in the case of line 3. Then, there exists schedule T̃ satisfying conditions (23)In this case, ([xa (0), xb (0)], S) ∈ Problem 3 since all (25). This proof is similar to the first part of the proof of
vehicles have already crossed the intersection. The procedure Theorem 1.
also returns yes when procedure S CHEDULING given a
For all j ∈ C, define T̃j as yjb (T̃j , ũj (·), xbj (0)) = αj
sequence π ∗ returns yes in line 5. Since π ∗ ∈ P, where if y b (0) < α , and 0 otherwise, and K̃
as
j
j
j
P is a set of all permutations, and π ∗ yields a feasible
a
a
a
schedule, we know E XACT([xa (0), xb (0)], S) returns yes. yj (K̃j , ũj (·), xj (0)) = β̂j if yj (0) < β̂j , and 0
otherwise. For i 6= j ∈ C, since yi (t, ũi (·), di (·), xi (0))
Thus, ([xa (0), xb (0)], S) ∈ Problem 3.
and yj (t, ũj (·), dj (·), xj (0)) avoid the inflated Bad
However, the converse of Theorem 3 is not true. That set for any d(·) ∈ D and x(0) ∈ [xa (0), xb (0)],
is, for some instances such that ([xa (0), xb (0)], S) ∈ (T̃i , K̃i ) ∩ (T̃j , K̃j ) = ∅. Since the inflated intersection
Prepared using sagej.cls

Supervisors for Intersection Collision Avoidance

13

Algorithm 6 Implementation of se
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

procedure E FF S UPERVISOR([xa (kτ ), xb (kτ )], ukdesire )
(T1 , ans1 ) = A PPROX(Xpred (ukdesire (·)), S)
if ans1 = yes and for all t ∈ [0, τ ), B ∩ [xa (t, ukdesire (·), xa (kτ )), xb (t, ukdesire (·), xb (kτ ))] = ∅ then
π k = a vector of indexes in the increasing order of nonzero entries of T1
k
uk+1,∞
saf e (·) = σ(Xpred (udesire (·)), T1 )
k+1,∞
uk+1
saf e (·) = usaf e (t) for t ∈ [(k + 1)τ, (k + 2)τ )
return ukdesire (·)
else
(T2 , ans2 ) = A PPROX(Xpred (uksaf e (·)), S)
if ans2 = no then
(T2 , ans3 ) = S CHEDULING(π k−1 , Xpred (uksaf e (·)), S)

π k = a vector of indexes in the increasing order of nonzero entries of T2
k
uk+1,∞
saf e (·) = σ(Xpred (usaf e (·)), T2 )
k+1,∞
uk+1
saf e (·) = usaf e (t) for t ∈ [(k + 1)τ, (k + 2)τ )
return uksaf e (·)

takes account of the maximum driving distance during ŝ([xa (kτ ), xb (kτ )], ukdesire ) defined as follows:
θmax , we have yja (T̃j + θmax , ũj (·), xa (0)) ≤ β̂j .

k,∞
k

This implies T̃j + θmax ≤ K̃j
for all j ∈ C
udesire (·) if ∃udesire (·) : for all t ≥ 0
a
because yj (t) is non-decreasing in t. Thus, ŝ =
y(t, uk,∞
/ B̂
desire (·), w(·), d(·), x(kτ )) ∈

 k
(T̃i , T̃i + θmax ) ∩ (T̃j , T̃j + θmax ) = ∅ (condition (24)).
usaf e (·)
otherwise.
¯ define (R̄γ , P̄γ ) as in Definition 2. Then, for
For γ ∈ C,
any wγ (·) ∈ Wγ , dγ (·) ∈ Dγ , and xγ (0) ∈ [xaγ (0), xbγ (0)], The only difference from the exact supervisor s is that the
uncontrolled vehicle γ enters the intersection no earlier Bad set B is replaced by the inflated Bad set B̂.
than R̄γ and exits it no later than P̄γ . In order for ũj (·)
Instead of implementing ŝ, we consider a procedure
to guarantee that yj (t, ũj (·), dj (·), xj (0)) and yγ (t) never implementing another supervisor, se , by using procedure
meet inside the intersection for any uncertainty, (T̃j , K̃j ) ∩ A PPROX to verify whether or not to override drivers. We call
(R̄γ , P̄γ ) = ∅. Since T̃j + θmax ≤ K̃j , we have (T̃j , T̃j + this procedure E FF S UPERVISOR in Algorithm 6.
θmax ) ∩ (R̄γ , P̄γ ) = ∅ (condition (25)).
Notice that this procedure stores the feasible sequence of
Condition (23) is satisfied by the definitions of Rj and vehicles crossing the intersection at every time step (lines 4
Dj .
and 12). This is because when the sequence considered in
line 9 does not yield a feasible schedule, the previous step’s
sequence π k−1 can be used to generate one. This is where
In summary, Theorem 3 states that if procedure in procedure S CHEDULING in Algorithm 1, |π0 | can be
A PPROX returns yes, there exists an input signal to avoid different from |π|, where π0 = π k−1 and π ∈ R|M| . This
the Bad set B for any uncertainty. As stated in Theorem 4, is because M is a set of vehicles that have not entered an
if the procedure returns no, there does not exist an input intersection at the current step, whereas π k−1 is a sequence
signal to avoid the inflated Bad set B̂ for any uncertainty. of vehicles that had not entered an intersection at the
Thus, the difference between B and B̂ is a measure of the previous step.
approximation bound of procedure A PPROX.
The fact that the previous step’s sequence leads to a
feasible schedule ensures the non-blocking property of
the supervisor and is proved in the next theorem. Bruni
5.2 Efficient supervisor
et al. (2013) proposed an efficient supervisor considering
In order for a supervisor to run in real time, the verification measurement errors and unmodeled dynamics with all
problem must be solved within the time step τ . However, vehicles controlled. Their supervisor cannot find a feasible
if a large number of controlled vehicles is considered, schedule at every step and thus uses the previous schedule
the problem becomes intractable. Thus, we employ the until a new feasible schedule is found. This ignores the
results in Section 5.1 to design efficient supervisors. The correction of the state estimation during the open-loop
simplest solution would be to implement a supervisor control, thereby being more conservative than our efficient
Prepared using sagej.cls

14

supervisor, which updates the schedule based on the most
current state estimation.
Procedure E FF S UPERVISOR takes polynomial computation time, and guarantees avoiding the Bad set B because
such a safe input exists if procedure A PPROX returns yes by
Theorem 3. Most importantly, we will prove in the following
theorem that se is less restrictive than ŝ, in the sense that ŝ
overrides controlled vehicles more frequently than se .

Journal Title XX(X)

1)τ ). Then, the j-th entry of Tk−1 is as follows:
k−1
Tjk−1 := {t : yjb (t, uk,∞
saf e,j (·), max Xpred,j (uout,j (·))) = αj }

= {t : yjb (t, uk+1,∞
saf e,j (·),
xb (τ, uksaf e,j (·), max Xpred,j (uk−1
out,j (·))) = αj } + τ
b
k
b
≤ {t : yjb (t, uk+1,∞
saf e,j (·), x (τ, usaf e,j (·), x (kτ ))) = αj } + τ

:= T̃j + τ.

(27)

a
b
Theorem 5. The supervisor se is less restrictive than ŝ: The inequality is due to [xj (kτ ), xj (kτ )] ⊆
k−1
if E FF S UPERVISOR([xa (kτ ), xb (kτ )], ukdesire ) = uksaf e (·), Xpred,j (uout,j (·)) by (14) and the order-preserving
in Assumption 1. Similarly, its process time
then ŝ([xa (kτ ), xb (kτ )], ukdesire ) = uksaf e (·). Moreover, se property
k−1
k−1
T
+
P
(Tjk−1 ) is as follows:
j
j
is non-blocking.

Tjk−1 + Pjk−1 (Tjk−1 )
k−1
:= {t : yja (t, uk,∞
saf e,j (·), min Xpred,j (uout,j (·))) = βj }

Proof. E FF S UPERVISOR([xa (kτ ), xb (kτ )], ukdesire ) =
uksaf e (·) when A PPROX(Xpred (ukdesire (·)), S) returns no.
By Theorem 4, there is no input signal uk,∞
desire (·) ∈ U
that can prevent entering the inflated Bad set for some
uncertainties. Thus, ŝ(Xpred (ukdesire ), S) returns uksaf e (·).
This proves that se is less restrictive than ŝ.
The non-blocking property is proved by mathematical
induction on time step k. For the base case, it is assumed
that E FF S UPERVISOR([xa (0), xb (0)], u0desire ) = u0out (·) 6=
∅ where u0out (·) is defined on time [0, τ ), and u1,∞
saf e (·) is
well-defined, that is, there exists a schedule T that defines
0
u1,∞
saf e (·) as σ(Xpred (udesire (·)), T). Suppose at t = (k −
1)τ , we have E FF S UPERVISOR([xa ((k − 1)τ ), xb ((k −
k,∞
k−1
1)τ )], uk−1
desire ) = uout (·) 6= ∅ and usaf e (·) is well-defined,

= {t : yja (t, uk+1,∞
saf e,j (·),
xa (τ, uksaf e,j (·), min Xpred,j (uk−1
out,j (·))) = βj } + τ
a
k
a
≥ {t : yja (t, uk+1,∞
saf e,j (·), x (τ, usaf e,j (·), x (kτ ))) = βj } + τ

:= T̃j + P̃j (T̃j ) + τ.

(28)

¯ let (R̄k−1 , P̄ k−1 ) denote the idle-time given
For γ ∈ C,
γ
γ
k−1
Xpred (uout (·)).
We now show that the schedule T̃ := (T̃j : j ∈ C) is a feasible schedule of S CHEDULING(π k−1 , Xpred (uksaf e (·)), S).
The release time and deadline of this procedure for j ∈ C is
by definition,
Rj =

min {t : yjb (t, uj (·), max Xpred,j (uksaf e,j (·))) = αj },

uj (·)∈Uj

which satisfies y(t, uk,∞
/ B for Dj = max {t : yjb (t, uj (·), max Xpred,j (uksaf e,j (·))) = αj }.
saf e (·), w(·), d(·), x(kτ )) ∈
uj (·)∈Uj
any w(·) ∈ W, d(·) ∈ D, and x(kτ ) ∈ Xpred (uk−1
out (·)).
Since xb (τ, uksaf e (·), xb (kτ )) = max Xpred (uksaf e (·)) in
Now, we need to prove that ukout (·) 6= ∅, and uk+1,∞
saf e (·) is
well-defined.
(11), we have T̃j ∈ [Rj , Dj ].
Since Tk−1 is feasible, (Tjk−1 , Tjk−1 + Pjk−1 (Tjk−1 )) ∩
In Algorithm 6, if ans1 = yes in line 2 or ans2 = yes in
line 9, by Theorem 3, there exists an input signal that makes (Tik−1 , Tik−1 + Pik−1 (Tik−1 )) = ∅ for i 6= j ∈ C. Because
the vehicle trajectories avoid entering the Bad set. Thus, of (27) and (28),
k+1,∞
usaf
e (·) is well-defined on time [(k + 1)τ, ∞) in lines 5
(T̃j , T̃j + P̃j (T̃j )) ⊆ (Tjk−1 , Tjk−1 + Pjk−1 (Tjk−1 )) − τ,
and 13. Also, ukout (·) = ∅ because ukout (·) = uk,∞
(·)
or
desire
ukout (·) = uksaf e (·).
for all j ∈ C. Thus, (T̃j , T̃j + P̃j (T̃j )) ∩ (T̃j , T̃i +
Suppose that ans1 = no and ans2 = no. Then, given P̃i (T̃i )) = ∅.
¯ it is not difficult to see that
Similarly for γ ∈ C,
π k−1 , we need to prove that ans3 = yes and T2 exists
k−1
in line 11. Notice that π
is a vector of indexed in the idle-time of S CHEDULING(π k−1 , Xpred (uksaf e (·)), S)
the increasing order of the nonzero entries of a feasible denoted by (R̄γ , P̄γ ) becomes a subset of (R̄γk−1 , P̄γk−1 ) −
schedule Tk−1 of the previous step. That is, at the τ . Since (T k−1 , T k−1 + P k−1 (T k−1 )) ∩ (R̄k−1 , P̄ k−1 ) =
γ
γ
j
j
j
j
previous step, S CHEDULING(π k−1 , Xpred (uk−1
out (·)), S) =
∅, we have (T̃j , T̃j + P̃j (T̃j )) ∩ (R̄γ , P̄γ ) = ∅.
k−1
k−1
(T
, yes). We will show that the existence of T
Thus, T̃ is feasible, thereby implying ans3 = yes in
implies that of T2 .
line
11 of Algorithm 6. Since T2 = T̃ exists, uk+1,∞
saf e (·)
k+1,∞
k,∞
Let usaf
(·)
be
u
(·)
restricted
to
time
[(k
+
e
saf e
is well-defined.
1)τ, ∞) and uksaf e (·) be uk,∞
Therefore, the supervisor is non-blocking.
saf e (·) restricted to time [kτ, (k +
Prepared using sagej.cls

15

10

10

0

0

-10

-10

distance

distance

Supervisors for Intersection Collision Avoidance

-20
-30
controlled vehicles
uncontrolled vehicles

-40

-20
-30
-40

position estimations
time steps of override

-50

-50
-60

-60
0

2

4

6

8

10

12

14

0

16

(a)

2

4

6

8

10

12

14

16

time

time

(b)

Figure 6. Simulation of the exact supervisor s in (a) and the efficient supervisor se in (b). The dotted lines at distance 0 and 5
represent the location of the intersection. The solid black lines and the dotted red lines are the exact trajectories of the controlled
and uncontrolled vehicles, respectively, and the shading around the lines represent the position estimation. The blue boxes on the
bottom are the time steps at which the supervisor overrides the controlled vehicles. The initial exact state is y(0) =(-42, -50, -55,
-60, -60, -65) and v(0) =(10, 9, 8, 8, 10, 8).

In summary, the efficient supervisors ŝ and se are more
restrictive than the exact supervisor s, and ŝ is more
restrictive than se by Theorem 5.

and uj,max = 2.5, and the driver-input wγ by
wγ,min = −0.5 and wγ,max = 0.5. In the simulation,
the disturbances and the driver-inputs of uncontrolled
vehicles are randomly chosen within their bounds.
At each time step τ = 0.1, the supervisors determine
6 Simulations
whether there are impending collisions at an intersection
In this section, we present simulation results of the exact and located at (α , β ) = (0, 5) for all i ∈ C ∪ C.
¯ The states of
i
i
efficient supervisors, s and se , in two scenarios by running all vehicles are measured subject to noises, δ ∈ [−3, 3]
y,i
Algorithms 2 and 6. These are implemented using MATLAB and δ ∈ [−0.05, 0.05]. For the sake of simplicity, in the
v,i
on a personal computer with an 3.10 GHz Intel Core i7- simulation, we let uk
j,desire = 1 for all vehicles at all times.
3770s processor with 8 GB RAM.
In the first scenario, four controlled and two uncontrolled
With the dynamic states xj = (yj , vj ) and xγ = (yγ , vγ )
¯ the vehicle dynamics considered in the vehicles are approaching an intersection as in Figure 6,
for j ∈ C and γ ∈ C,
which illustrates the position trajectories of the vehicles
simulation are as follows:
in time.
The simulation result of the exact supervisor s is shown
ẏj = vj + dy,j ,

in Figure 6a, and that of the efficient supervisor se is shown
2

max(0, uj − bvj + dv,j ) if (vj = vj,min ),
in Figure 6b. Though we said in Section 5.2 that se is more
v̇j = min(0, uj − bvj2 + dv,j ) if (vj = vj,max ),
conservative than s – in the sense that given the same initial


uj − bvj2 + dv,j
otherwise,
condition, s evaluates more inputs to find one guaranteeing
avoiding the Bad set than se – comparison of the override
and
time steps (blue boxes) in Figures 6a and 6b indicates that
se does not override the drivers more than s. It takes 0.067 s
ẏγ = vγ + dy,γ ,
and 0.011 s per iteration to execute s (Algorithm 2) and se

2

max(0,
w
−
bv
+
d
)
if
(v
=
v
),
(Algorithm
6), respectively, in the worst case. This validates
γ
v,γ
γ
γ,min
γ

2
that
the
computation
of the efficient supervisor is faster
v̇γ = min(0, wγ − bvγ + dv,γ ) if (vγ = vγ,max ),


than
that
of
the
exact
supervisor. In both simulations, the
wγ − bvγ2 + dv,γ
otherwise,
intersection at distance (0, 5) is occupied by one vehicle at a
where b = 0.001 is a drag coefficient, and time.
dy,j , dy,γ , dv,i , dv,γ
are disturbances representing
The second scenario considers twelve controlled and two
unmodeled dynamics bounded by −0.05 and 0.05. The uncontrolled vehicles. Due to the large number of controlled
speeds vj , vγ are bounded by vj,min = vγ,min = 1.39 and vehicles involved, the exact supervisor cannot solve the
vj,max = vγ,max = 13.9, the input uj by uj,min = −2.5 verification problem within one time step. Thus, the only
Prepared using sagej.cls

16

Journal Title XX(X)

10
0

distance

-10
-20
-30
-40
-50
-60
0

5

10

15

20

25

30

time

Figure 7. Simulation of the efficient supervisor se . The initial
exact state is y(0) =(-25, -30, -35, -40, -45, -50, -55, -60, -65,
-65, -70, -75, -80, -85) and v(0) =(6,9, 9, 8, 8, 8, 8, 8, 8, 9.5, 8,
8, 8, 8).

option to resolve conflict in this scenario is to implement
the efficient supervisor (Algorithm 6). As shown in Figure 7,
the efficient supervisor assists the vehicles to prevent any
collision at the intersection. In the worst case, it takes 0.033 s
per iteration.

7

Experiments

In this section, we describe the experimental validation of
the exact supervisor on an intersection testbed. First, we
introduce the laboratory apparatus. Then, we describe the
dynamic model of the RC cars used in the experiment and
the techniques adopted to reduce disturbances. The results
of the experiment are provided at the end of this section.

7.1

Experimental setup

The cars used for this experiment are each built onto a
Tamiya scaled RC car chassis equipped with a DC motor.
A micro-controller (Acroname Moto 1.0) is used to control
the steering servo and the motor through two separate PWM
channels. An on-board computer (Mini-ITX running Fedora)
runs the C programs, which provide the functionalities
required to communicate with the centralized supervisor and
to control the micro-controller. The system is powered by
two batteries (Tenergy Li-Ion 14.8 V 4400 mAh) connected
to a capacitor (Aluminium Electrolytic Capacitor 12000 uF
25 V) through a power relay (Omron G5SB). A power
amplifier (Acroname 3 A Back EMF H-bridge) connected
to the batteries through a switch provides necessary power
to the motor.
During the experiment, three cars follow distinct paths
intersecting at a single point on a 6 m × 6 m testbed as
shown in Figure 8b. Each path is stored as sequential points
on the coordinate system illustrated in the figure. Cars 1
and 2 are controlled by the exact supervisor when necessary,
while car 3 is not controllable. We program cars 1 and 2
to maintain constant motor input, which corresponds to the
desired input, while car 3 is driven by a human operator.
Each car has access to its own wheel speed through a
quadrature encoder mounted on the rear axle. The position
and direction of the cars are measured by an over-head vision
system, which comprises six cameras on the ceiling and three
computers processing images taken by the cameras. Each
car is identified by a symbol attached to its roof as shown in
Figure 8a. The measurement of the speeds, positions, and
directions of all cars are collected by an external computer
via a wireless connection of the 802.11b standard using
UDP/IP. Then, the computer distributes these measurements
to the controlled cars, together with other information such
as the desired inputs of the controlled vehicles and model
parameters discussed in the next section.

7.2

O

Car dynamics model

1

3

2

(a)

(b)

Figure 8. (a) The RC cars used in the experiment. The camera
system detects their symbols to identify each car and measure
its position. (b) The paths of the cars on the testbed. Cars 1
and 2 are controlled by the supervisor while car 3 is not. A car
is considered to be occupying the intersection when its position
is within the shaded circle.

Prepared using sagej.cls

Figure 9. Block diagram of the RC car model. The model
includes the measurement disturbances δy,i and δv,i on the car
position and speed, respectively.

A block diagram in Figure 9 represents the car dynamics.
In this section, we design a compensating input to reduce
the effects of the disturbances dproj,i , dpower,i , dslope,i , and
dsteer,i .

Supervisors for Intersection Collision Avoidance

Before compensating for the disturbances, the dynamics
of the RC cars are as follows: for car i ∈ C ∪ C¯ where
C = {1, 2} and C¯ = {3},
ẏi = vi + dproj,i ,
v̇i = ai vi + bi + fi ui + dpower,i + dslope,i + dsteer,i
(29)
where yi is the longitudinal position of car i along the
path, vi is its wheel speed, and ui is the motor input
with model parameters ai , bi , and fi . The disturbances
dproj,i , dpower,i , dslope,i , and dsteer,i are explained below
and compensated to reduce their effects.

17

disturbances as a path-dependent function dpath,i (y) :=
dsteer,i (y) + dslope,i (y). This function is different for each
path and estimated by running the car multiple times and
curve fitting of the obtained data.
Eliminating the effects of these disturbances is critical
because otherwise it is difficult to initiate Algorithm 2 with a
feasible initial condition, especially in a spatially constrained
environment, such as a laboratory testbed. To this end, we
introduce a compensating term ci (t, yi ) to the motor input so
that ui = u0i + ci (t, yi ), where u0i is the input signal returned
by the supervisor for car i. By employing the model and
estimation of the disturbances explained above, we obtain
the following compensating input:
ci (t, yi ) = −

i
j
(a)

(b)

Figure 10. Cases when dproj,i 6= 0. Imperfect path following
contributes to the discrepancy between the longitudinal speed
ẏi and the wheel speed vi .

gi e−t/hi u0i + dpath,i (yi )
.
gi e−t/hi + fi

This, in turn, simplifies (29) as ẏi = vi + dproj,i and v̇i =
ai vi + bi + fi u0i . Eventually with the compensation, we
consider the following car dynamics in the experiment. For
¯
i ∈ C ∪ C,
ẏi = vi + dy,i ,

0

max(0, ai vi + bi + fi ui + dv,i ) if (vi = vi,min ),
v̇i = min(0, ai vi + bi + fi u0i + dv,i ) if (vi = vi,max ),


ai vi + bi + fi u0i + dv,i
otherwise,
where dv,i represents an error from the compensation and
an unpredicted source of disturbance.

Notice that vi is the car’s wheel speed while y˙i is the
projected speed on the longitudinal path of car i. It is possible
that y˙i 6= vi when the car does not follow its path exactly, 7.3 Results
and this discrepancy is represented by the term dproj,i . The on-board computers on cars 1 and 2 run Algorithm 2.
Figure 10 shows two cases in which ẏi 6= vi . In Figure Since the same algorithm is run with the same measurement
10a, the direction of car i differs from the tangent of the updated every τ = 0.1s, the outputs are the same, thereby
longitudinal path (black line) so that vi 6= ẏi . In Figure 10b, working as centralized control.
two cars follow the same path with the same wheel speed v
The parameters are as follows: a =(-0.53, -0.30, but with slight deviation from the path, causing ẏi > v > ẏj . 0.43) s−1 , b =(-84.68, -66.43, -49.64) cm/s2 , g =(0.99,
This dynamic model (29) includes three different 0.44, 0.95), and h =(9.17, 6.84, 5.95) s. The gain fi (t)
disturbances on the acceleration. The disturbance dpower,i for all i is a time-varying parameter, estimated at every
describes the first-order dynamic behavior empirically time step. The bounds of the speed are vmin =(10.5, 10.5,
observed in the motor as a consequence of the power 13) cm/s and vmax =(17, 16.5, 15) cm/s, and those of
connection. By running the cars in a circle with constant the motor input (PWM) are umin = (105, 105, 130) and
motor input for several minutes, we can model dpower,i = umax =(170,165,150). The bounds of the measurement
gi e−t/hi u0i , where gi is the gain and hi the time constant. noises are empirically chosen by ignoring long tails as
The car-specific parameters gi and hi are estimated by δy,i,min = -25 cm, δy,i,max = 25 cm, δv,i,min = -25 cm/s,
analyzing the collected data using the least square method and δv,i,max = 16 cm/s for all i. The bounds of the
(see Rizzi (2014) for the data).
experimental disturbance are dy,min =(-5, -3, -3) cm/s,
The disturbance dslope,i is introduced to model the slope dy,max =(3, 4, 3) cm/s, dv,min =(-4, -2, -3) cm/s2 , and
of the testbed, which is not completely flat and has non- dv,max =(2, 3, 2.5) cm/s2 .
negligible effects on the car speed. The disturbance dsteer,i
Figure 11 depicts two experimental results obtained
takes into account the fact that the steering and motor by implementing the exact supervisor. The intersection is
dynamics are coupled (Verma et al. (2008)). Since the located at (0, 65) cm for all cars. The intersection is an
testbed slope and the steering input are approximately the area containing the point at which the paths intersect, as in
same at the same point of the path, we estimate these two Figure 8b.
Prepared using sagej.cls

18

Journal Title XX(X)

1

100

0

0

-100

-100

distance (cm)

distance (cm)

100

-200
-300

2

-400

-200

-400
-500

-600

-600

0

5

10

15

-700

20

2

-300

-500

-700

1

0

5

time (s)

(a)

10

15

20

time (s)

(b)

Figure 11. The results of implementing the exact supervisor (see also Extension 1). The intersection is represented by the dotted
lines located at (0, 65) cm. The solid black lines represent the position measurement of the controlled cars, cars 1 and 2, and the
dotted red line represents the position measurement of the uncontrolled car, car 3. These figures demonstrate that the cars are not
inside the intersection at the same time.

In Figure 11a, in picture 1, the uncontrolled car (dotted
red circle) approaches the intersection earlier than the other
cars. The supervisor overrides the controlled cars (solid blue
circles) to decelerate them until their desired inputs do not
cause conflict. In picture 2, the conflict is resolved, and
one controlled car crosses the intersection alone without
overrides. In Figure 11b, in picture 1, one controlled car
approaches the intersection first. The supervisor lets this car
accelerate and the other controlled car decelerate so that the
uncontrolled car safely crosses the intersection, as shown
in picture 2. Notice that the upper bound of the last car’s
position enters the intersection right after the lower bound
of the uncontrolled car’s position has exited, indicating that
the override was applied because it is deemed necessary to
avoid the collision. In both cases, intersection collisions are
averted.

sometimes be incompatible. This truncation is necessary
in the confined laboratory because otherwise a feasible
initial condition may not always exist. The existence of a
feasible initial condition is a necessary condition to initiate
procedure S UPERVISOR in Algorithm 2.

8

Conclusions

We have designed exact and efficient supervisors that
override controlled vehicles when collisions are imminent.
The sources of uncertainty, such as measurement errors,
unmodeled dynamics, and the presence of uncontrolled
vehicles are taken into account in the design of the
supervisors. The exact supervisor determines the existence
of safe inputs (verification problem) by solving the Inserted
Idle-Time (IIT) scheduling problem, which is proven to yield
Figure 12 depicts 509 trajectories (semitransparent black equivalent answers to the verification problem. To address
lines) near the Bad set (red blocks). The trajectories are the computational complexity issue, we also design the
indicated in blue when the supervisor intervenes. From efficient supervisor that solves the IIT scheduling problem
the 2D projections (figures on the right-hand side), we can with a quantified approximation bound. The simulation
confirm that none of the trajectories enters the Bad set. Since results show that the efficient supervisor prevents collisions
cars 1 and 2 are programmed to maintain constant speeds without substantial conservatism, compared to the exact one.
and car 3 does not change its speed quickly, the trajectories The experiment using RC cars on an intersection testbed
in the projections should be straight lines without overrides. validated that collisions at an intersection are successfully
We can see that the supervisor overrides cars 1 and 2 when averted by the exact supervisor.
the trajectories would enter the Bad set if the trajectories
Although this paper deals only with decision problems to
were linear. We observed in 15 trajectories that the cars were focus on safety, there is no barrier to incorporate objective
forced to stop before the Bad set because the supervisor functions to address other issues such as fuel consumption
could not find a safe input. This was because we had to or traffic congestion. The intersection considered in this
truncate the tails of the distributions of disturbances, and paper is modeled as a single conflict area so that vehicles
thus the state measurement and the state estimation can are required to occupy the intersection one at a time. This
Prepared using sagej.cls

Supervisors for Intersection Collision Avoidance

assumption may make the system very conservative in that,
for example, two vehicles turning right on different lanes
are geometrically unable to collide while the supervisors
do not let them inside the intersection at the same time. We
are currently investigating the design of supervisors with
a more general intersection model, which includes multiconflict points. The result with simple first-order vehicle
dynamics can be found in Ahn and Del Vecchio (2016, To
appear). Other remaining issues include preventing rearend collisions (Colombo and Del Vecchio (2014)) and
considering unknown routes of vehicles.
Funding
This work was in part supported by NSF Award #1239182.
Alessandro Colombo was in part supported by grant AD14VARI02
- Sottomisura B.

References
Ahn H, Colombo A and Del Vecchio D (2014) Supervisory
control for intersection collision avoidance in the presence
of uncontrolled vehicles. In: American Control Conference
(ACC). pp. 867–873.
Ahn H and Del Vecchio D (2016, To appear) Semi-autonomous
intersection collision avoidance through job-shop scheduling.
In: the 19th ACM international conference on Hybrid Systems:
Computation and Control.
Ahn H, Rizzi A, Colombo A and Del Vecchio D (2015)
Experimental testing of a semi-autonomous multi-vehicle
collision avoidance algorithm at an intersection testbed. In:
IEEE/RSJ International Conference on Intelligent Robots and
Systems (IROS). pp. 4834–4839.
Alonso-Ayuso A, Escudero L and Martn-Campo F (2011) Collision
Avoidance in Air Traffic Management: A Mixed-Integer Linear
Optimization Approach. IEEE Transactions on Intelligent
Transportation Systems 12(1): 47–57.
Borrelli F, Subramanian D, Raghunathan A and Biegler L (2006)
MILP and NLP Techniques for centralized trajectory planning
of multiple unmanned air vehicles. In: American Control
Conference.
Bruni L, Colombo A and Del Vecchio D (2013) Robust multi-agent
collision avoidance through scheduling. In: IEEE Conference
on Decision and Control (CDC). pp. 3944–3950.
Cassandras CG and Lafortune S (eds.) (2008) Introduction to
Discrete Event Systems. Boston, MA: Springer US.
Colombo A and Del Vecchio D (2012) Efficient algorithms
for collision avoidance at intersections. In: the 15th ACM
international conference on Hybrid Systems: Computation and
Control. pp. 145–154.
Colombo A and Del Vecchio D (2014) Least Restrictive Supervisors for Intersection Collision Avoidance: A Scheduling
Approach. IEEE Transactions on Automatic Control DOI:
10.1109/TAC.2014.2381453.

Prepared using sagej.cls

19

Cormen TH, Leiserson CE, Rivest RL and Stein C (2009)
Introduction to Algorithms. 3rd edition edition. Cambridge:
The MIT Press. ISBN 9780262033848.
Garey MR, Johnson DS, Simons BB and Tarjan RE (1981)
Scheduling UnitTime tasks with arbitrary release times and
deadlines. SIAM Journal on Computing 10: 256–269.
Gillula JH, Hoffmann GM, Huang H, Vitus MP and Tomlin CJ
(2011) Applications of hybrid reachability analysis to robotic
aerial vehicles. The International Journal of Robotics Research
30(3): 335–354.
Hafner M, Cunningham D, Caminiti L and Del Vecchio D
(2013) Cooperative Collision Avoidance at Intersections:
Algorithms and Experiments. IEEE Transactions on Intelligent
Transportation Systems 14(3): 1162–1175.
Hafner MR and Del Vecchio D (2011) Computational tools for the
safety control of a class of piecewise continuous systems with
imperfect information on a partial order. SIAM Journal on
Control and Optimization 49: 2463–2493.
Hoffmann G and Tomlin C (2008) Decentralized cooperative
collision avoidance for acceleration constrained vehicles. In:
IEEE Conference on Decision and Control (CDC). pp. 4357–
4363.
Kamal M, Imura J, Hayakawa T, Ohata A and Aihara K (2014) A
Vehicle-Intersection Coordination Scheme for Smooth Flows
of Traffic Without Using Traffic Lights. IEEE Transactions on
Intelligent Transportation Systems DOI:10.1109/TITS.2014.
2354380.
Kowshik H, Caveney D and Kumar P (2011) Provable systemwide
safety in intelligent intersections. IEEE Transactions on
Vehicular Technology 60: 804–818.
Lee J and Park B (2012) Development and evaluation of a
cooperative vehicle intersection control algorithm under the
connected vehicles environment. IEEE Transactions on
Intelligent Transportation Systems 13: 81–90.
Maimone M, Cheng Y and Matthies L (2007) Two years of Visual
Odometry on the Mars Exploration Rovers. Journal of Field
Robotics 24(3): 169–186. DOI:10.1002/rob.20184.
Mastellone S, Stipanovi DM, Graunke CR, Intlekofer KA
and Spong MW (2008) Formation Control and Collision
Avoidance for Multi-agent Non-holonomic Systems: Theory
and Experiments. The International Journal of Robotics
Research 27(1): 107–126.
Pallottino L, Feron E and Bicchi A (2002) Conflict resolution
problems for air traffic management systems solved with
mixed integer programming. IEEE Transactions on Intelligent
Transportation Systems 3(1): 3–11.
Peng J and Akella S (2005a) Coordinating Multiple Double
Integrator Robots on a Roadmap: Convexity and Global
Optimality. In: IEEE International Conference on Robotics
and Automation (ICRA). pp. 2751–2758.
Peng J and Akella S (2005b) Coordinating Multiple Robots
with Kinodynamic Constraints Along Specified Paths. The

20

Journal Title XX(X)

International Journal of Robotics Research 24(4): 295–310.
Richards A, Schouwenaars T, How JP and Feron E (2002)
Spacecraft Trajectory Planning with Avoidance Constraints
Using Mixed-Integer Linear Programming. Journal of
Guidance, Control, and Dynamics 25(4): 755–764.
Rizzi A (2014) Analysis and optimization of an experimental apparatus to test active safety systems in vehicles.
URL https://www.politesi.polimi.it/
handle/10589/92232.
Smith RN, Chao Y, Li PP, Caron DA, Jones BH and Sukhatme
GS (2010) Planning and Implementing Trajectories for
Autonomous Underwater Vehicles to Track Evolving Ocean
Processes Based on Predictions from a Regional Ocean Model.
The International Journal of Robotics Research 29(12): 1475–
1497.
Verma R, Del Vecchio D and Fathy H (2008) Development of a
Scaled Vehicle With Longitudinal Dynamics of an HMMWV
for an ITS Testbed. IEEE/ASME Transactions on Mechatronics
13(1): 46–57. DOI:10.1109/TMECH.2008.915820.
Wu J, Abbas-Turki A and ElMoudni A (2012) Cooperative driving:
an ant colony system for autonomous intersection management.
Applied Intelligence 37: 207–222.
Wurman PR, D’Andrea R and Mountz M (2008) Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses.
AI Magazine 29(1): 9–19.

Appendix A: Index to Multimedia
Extensions
Extension
1

Media type
Video

Description
This video contains experiments of the exact supervisor
presented in Section 7.

Appendix B
We provide the proofs of Lemmas 1-3 in this section.
Lemma 1. Procedure P OLYNOMIAL in Algorithm 3 solves
the IIT scheduling problem with unit process times and finds
a feasible schedule if exists.
Proof. To account for inserted idle-times, we define an
initial set of forbidden regions as F0,γ = (r̄γ − 1, p̄γ ) for
all γ. If tj ∈
/ F0,γ for some j, then we have (tj , tj + 1) ∩
(r̄γ , p̄γ ) = ∅, thereby satisfying condition (21).
Forbidden Region Declaration in lines 3-11 of procedure
P OLYNOMIAL solves Problem 4. The key idea is critical time
c, which is the latest start time of job σi . If job σi starts later
than critical time c, at least one of the subsequent jobs cannot
be scheduled before its deadline. That is, if a job cannot
start before the critical time (line 10), there is no schedule
satisfying conditions (19)-(21). Otherwise, there will be a
Prepared using sagej.cls

schedule satisfying all the conditions. This relation between
critical time and the existence of a feasible schedule was
proved in Garey et al. (1981) with initially empty forbidden
regions. Since initially non-empty forbidden regions do not
affect the fact that critical time is the latest start time, this
analysis of critical time can determine the existence of a
schedule with non-empty initial forbidden regions.
With the forbidden regions declared, the EDD rule finds a
schedule in lines 12-17. Time s is assigned to each job as a
schedule. In line 14, s avoids the forbidden regions so that
condition (21) is satisfied. If there is no ready job (line 15),
a job with the minimum release time among unscheduled
jobs is scheduled, and otherwise (line 16), a job with the
earliest deadline among ready jobs is scheduled. After a job
is scheduled, line 17 updates s to s + 1 so that condition (20)
is satisfied. This schedule cannot satisfy condition (19) if
ans has been no in line 10. Otherwise, this schedule satisfies
conditions (19)-(21).
Lemma 2. If A PPROX([xa (0), xb (0)], S) = (T, yes), and
RELAXEDEXACT([xa (0), xb (0)], S) = (T̄, π ∗ , yes), then
Tj ≤ T̄j for all j ∈ C.
Proof. We will show by induction on j that Tπj∗ ≤ T̄πj∗ for
all πj∗ ∈ M. Notice that Ti = T̄i = 0 for all i ∈ M̄. The
schedule T is generated by procedure S CHEDULING in
Algorithm 1. For the base case, Tπ1∗ = max(Rπ1∗ , Pmax )
in line 8 of Algorithm 1. Since T̄π1∗ is a feasible solution
of Problem 5 by Lemma 1, it satisfies Rπ1∗ ≤ T̄π1∗ from
condition (23) and (0, Pi (0)) ∩ (T̄π1∗ , T̄π1∗ + θmax ) = ∅ for
all i ∈ M̄ from condition (24). Thus, max(Rπ1∗ , Pmax ) =
∗
∗
Tπ1∗ ≤ T̄π1∗ . Now, suppose Tπk−1
≤ T̄πk−1
. Then, for j = k,
we need to show that Tπk∗ ≤ T̄πk∗ .
∗
In line 10 of Algorithm 1, Tπk∗ = max(Rπk∗ , Tπk−1
+
∗
∗
∗
∗
∗
Pπk−1 (Tπk−1 )). If Tπk = Rπk , we have Tπk ≤ T̄πk∗
∗
because T̄πk∗ satisfies condition (23). If Tπk∗ = Tπk−1
+
∗
∗
∗
Pπk−1
(Tπk−1
), we have Tπk∗ ≤ T̄πk−1
+ θmax because
∗
∗
∗
∗
Tπk−1
≤ T̄πk−1
and Pπk−1
(Tπk−1
) ≤ θmax by (22). Since
∗
T̄πk∗ satisfies condition (24), T̄πk−1
+ θmax ≤ T̄πk∗ . Therefore, Tπk∗ ≤ T̄πk∗ . In lines 13 and 15 of Algorithm 1, the
schedule can increase so that Tπ∗ = P̄γ for some γ ∈ C¯
k

if Tπk∗ ≥ R̄γ or Tπk∗ + Pπk∗ (Tπk∗ ) > R̄γ . Since T̄πk∗ satisfies
condition (25), if T̄πk∗ ≥ R̄γ or T̄πk∗ + θmax > R̄γ , then
it must be T̄πk∗ ≥ P̄γ . Therefore, in either case, Tπk∗ ≤
T̄πk∗ .
Lemma 3. If A PPROX([xa (0), xb (0)], S) = (∅, no), then
RELAXEDEXACT([xa (0), xb (0)], S) = (∅, π ∗ , no).
Proof. In Algorithm 5, procedure A PPROX returns
no if [ya (0), yb (0)] ∩ B 6= ∅ in line 2 or procedure
S CHEDULING with π ∗ returns no in line 5. In the former
case, procedure RELAXEDEXACT also returns no as in line 2

Supervisors for Intersection Collision Avoidance

of Algorithm 4. The latter case implies that Tπj∗ > Dπj∗ for
some πj∗ ∈ C. By Lemma 2, we have T̄πj∗ ≥ Tπj∗ if a feasible
solution T̄ of Problem 5 exists. Such a schedule cannot be
feasible because T̄πj∗ ≥ Tπj∗ > Dπj∗ , which does not satisfy
condition (23). Thus, procedure RELAXEDEXACT returns
(∅, π ∗ , no).

Prepared using sagej.cls

21

22

Journal Title XX(X)

Figure 12. Trajectories (semitransparent black lines) in the output space. There are 509 trajectories, which are indicated in blue
when the supervisor intervenes. The three figures on the right-hand side are the 2D projections. These confirm that all of the
trajectories avoid the Bad set.

Prepared using sagej.cls

