arXiv:1510.07026v1 [cs.SY] 23 Oct 2015

Semi-autonomous Intersection Collision Avoidance
through Job-shop Scheduling
Heejin Ahn

Domitilla Del Vecchio

Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA, 02139

Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA, 02139

hjahn@mit.edu

ddv@mit.edu

ABSTRACT
In this paper, we design a supervisor to prevent vehicle collisions at intersections. An intersection is modeled as an
area containing multiple conflict points where vehicle paths
cross in the future. At every time step, the supervisor determines whether there will be more than one vehicle in the
vicinity of a conflict point at the same time. If there is,
then an impending collision is detected, and the supervisor
overrides the drivers to avoid collision. A major challenge
in the design of a supervisor as opposed to an autonomous
vehicle controller is to verify whether future collisions will
occur based on the current drivers choices. This verification
problem is particularly hard due to the large number of vehicles often involved in intersection collision, to the multitude
of conflict points, and to the vehicles dynamics. In order
to solve the verification problem, we translate the problem
to a job-shop scheduling problem that yields equivalent answers. The job-shop scheduling problem can, in turn, be
transformed into a mixed-integer linear program when the
vehicle dynamics are first-order dynamics, and can thus be
solved by using a commercial solver.

Categories and Subject Descriptors
I.2.8 [Artificial Intelligence]: Problem Solving, Control
Methods, and Search—Control theory, Scheduling; I.2.9 [
Artificial Intelligence]: Robotics—Autonomous vehicles

General Terms
Theory, Algorithms

Figure 1: General intersection scenario, taken from
[24] to encompass the most dangerous intersections
in Massachusetts, USA. This intersection contains
forty eight conflict areas (small red circles). The
supervisor designed in this paper can prevent collisions at the conflict areas by minimally overriding
the vehicles.

Keywords
Intersection collision avoidance, multi-vehicle control, supervisory control, collision detection, verification, scheduling

1.

INTRODUCTION

In the United States, 33,561 people lost their lives in vehicle crashes in 2012, and 26 % of them occurred at or near

Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$15.00.

intersections [25]. This raises the need for improved safety
systems that actively prevent collisions at intersections. For
example, a centralized controller could be implemented on
the infrastructure to coordinate vehicles near an intersection
so as to prevent collisions. However, since a large number of
vehicles are often involved in intersection collisions and vehicles are dynamic agents, the design of such systems faces
challenges in terms of computational complexity. An additional substantial complication is that the system should
override the drivers only when their driving will certainly
cause a collision. That is, override actions should be minimally restrictive. This allows drivers to be in control of the
vehicle unless unable to handle a dangerous situation. This
supervisor can also be used as a safety guard for future fully
autonomous vehicles driving in complex environment.
In this paper, we design a supervisor, which can be imple-

mented on an infrastructure, communicating with humandriven vehicles near an intersection as shown in Figure 1.
The most important and challenging part in the design is
to determine whether vehicles’ current driving will cause
collisions at some future time. This is important because
the exact collision detection, called the verification problem, makes the supervisor least restrictive. This problem
is not scalable with respect to the number of vehicles near
an intersection yet their future safety must be verified every τ seconds, where τ is usually 100 ms [20]. To solve the
verification problem in real-time, we formulate a job-shop
scheduling problem, and prove that this is equivalent to the
former problem. Although the job-shop scheduling problem
is NP-hard [15], we can solve this problem using a commercial solver by converting it into a mixed-integer linear
programming problem.
Mixed integer programming can handle both discrete and
continuous aspects of a system. For example, collision avoidance can be formulated using discrete variables while the dynamic behaviors of vehicles, such as position and speed, are
represented by continuous variables. Thus, mixed-integer
programming has been employed in various collision avoidance applications such as air traffic control [27, 4, 9] and
multi-robot control [13, 17]. Since the decision variables of
these works are control inputs, for example, velocity, acceleration, or heading angle, at each time step within a finite time
horizon, the discrete-time dynamics of vehicles are considered. As the number of time steps increases, the discretization error is diminished whereas the problem becomes larger
and more difficult to solve. Because of this computational
complexity, real-time verification is usually not feasible and
hence not considered. Moreover, these works are cast in an
autonomous framework in which if one input that satisfies
the constraints is found, then it is applied. In contrast, in
a semi-autonomous framework, such as ours, all admissible
inputs need to be examined to determine if at least one feasible input exists.
In collision avoidance confined to an intersection, complexity can be mitigated by exploiting the fact that vehicles
tend to follow predetermined paths. Given this, the intersection can be considered as a resource that all vehicles share.
In [22, 23, 7], vehicles are assigned time slots during which
they can be inside the intersection without conflict. Since
the decision variables are the times at which each vehicle enters the intersection, the continuous dynamics are employed
to compute these times. Notice that this approach considers
n decision variables if n is the number of vehicles, whereas
the approach in the previous paragraph considers at least
n ∗ N decision variables if N is the number of time steps on
a finite time horizon. Because of the significantly smaller
number of decision variables, the scheduling approach is
computationally more efficient. The above works also assume full autonomy, which is not applicable to the scenarios
considered in this paper. A detailed review of autonomous
intersection management can be found in [8].
A semi-autonomous framework with the scheduling approach is considered in [10, 11] by proving the equivalence
between the verification problem and the scheduling problem. In these works, the authors design a least restrictive supervisor and restrict their attention to a special intersection
scenario where all paths of vehicles intersect at one conflict
area as indicated by the dashed region in Figure 2. While
maintaining the same structure of the supervisor as in [10,

2

2

1

3

3

1

Figure 2: Example of three vehicles with three conflict areas. The dashed circle represents the intersection model used in [10, 11]. In this paper, the
intersection is modeled as multiple conflict areas as
represented by the three shaded circles.

11], we formulate a job-shop scheduling problem to account
for general scenarios of an intersection, where the paths of
vehicles intersect at multiple points as in Figure 1. Considering multiple conflict points enables us to design a less
conservative verification problem, but makes it more difficult to translate the problem to a job-shop scheduling problem. In this paper, we prove that our job-shop scheduling
problem is equivalent to the verification problem with multiple conflict points. By virtue of this proof, we can solve
the verification problem by solving the job-shop scheduling
problem, which is computationally tractable. The job-shop
scheduling problem is then transformed into a mixed-integer
linear programming problem by assuming the single integrator dynamics of vehicles. Although a mixed-integer linear
programming problem is NP-hard [15], it can be solved by
commercial solvers such as CPLEX [21] or Gurobi [18].
The rest of this paper is organized as follows. In Section 2,
we introduce the intersection model and the dynamic model
of vehicles. In Section 3, we formally state the verification
problem and the supervisor-design problem. The verification problem can be solved by formulating and solving a
job-shop scheduling problem, which plays the most important role in the design of the supervisor. We then transform
the job-shop scheduling problem into a mixed-integer linear programming problem to solve the job-shop scheduling
problem using a commercial solver. These solutions will be
given in Section 4. We conclude this paper by presenting the
results of computer simulations in Section 5 and conclusions
in Section 6.

2. SYSTEM DEFINITION
Let us consider n vehicles approaching an intersection.
The vehicles follow their predetermined paths, and a point
at which at least two of the paths intersect is defined as a
conflict point. Around a conflict point, we define a conflict
area to account for the size of vehicles. The intersection
is modeled as a set of m conflict areas as in Figures 1 and

2. Throughout this paper, vehicles and conflict areas are
distinguished by integer indexes 1, . . . , n and 1, . . . , m, respectively. In order to focus only on intersection collision,
we assume that there is only one vehicle per road.
To model the longitudinal dynamics of vehicles, let xj ∈
Xj be the dynamic state of vehicle j. Let uj ∈ Uj ⊂ R the
control input of vehicle j. Then, the longitudinal dynamics
are as follows:
ẋj = fj (xj , uj ),

yj = hj (xj ).

PROBLEM STATEMENT

Let (αij , βij ) ⊂ R denote the location of conflict area i
along the longitudinal path of vehicle j. A conflict area is
defined around a conflict point such that a collision occurs
if more than one vehicle stay in a conflict area at the same
time. That is, a collision occurs if y ∈ B where
B := {y ∈ Y : for some j and j ′ ,
yj ∈ (αi,j , βi,j ) and yj ′ ∈ (αi,j ′ , βi,j ′ )}.

y(t, u, x(τ, ukdriver , x(kτ ))) ∈
/ B,
or returns uksaf e ∈ U otherwise. Here, uksaf e is defined as the safe input that guarantees the existence
of u′ ∈ U such that for all t ≥ 0,
y(t, u′ , x(τ, uksaf e , x(kτ ))) ∈
/ B.

(1)

The output of the system is the position yj ∈ Yj along
the path. Here, uj is in a compact set, i.e., uj ∈ Uj :=
[uj,min , uj,max ]. We assume that the output yj continuously
depends on the input uj . With abuse of notation, let uj
denote the input signal as well as the input value in R.
The input signal uj ∈ Uj is a function of time defined as
{uj (t) : uj (t) ∈ Uj for t ≥ 0}.
Let xj (t, uj , xj (0)) denote the state reached after time
t with input signal uj starting from xj (0). Similarly, let
yj (t, uj , xj (0)) denote the position reached after time t with
input signal uj starting from xj (0). The aggregate state,
output, input, and input signal are denoted by x ∈ X, y ∈
Y, u ∈ U, and u ∈ U, respectively.
One of the most important properties of the dynamic
model (1) is the order-preserving property. That is, for
uj (t) ≤ u′j (t) for all t, we have xj (t, uj , xj (0)) ≤ xj (t, u′j , xj (0))
and yj (t, uj , xj (0)) ≤ yj (t, u′j , xj (0)) for all t ≥ 0. We will
exploit this property in the design of the supervisor, particularly in formulating the job-shop scheduling problem.

3.

Spec 1. For time [kτ, (k + 1)τ ), it returns ukdriver if there
exists u ∈ U such that for all t ≥ 0

(2)

This subset of output B is called the bad set, and if y(t) ∈
/B
for all t ≥ 0, we consider the system safe.
The verification problem is to determine if collisions at
an intersection can be prevented at all future time given an
initial state. We formally state this problem using the bad
set (2) as follows.
Problem 1 (Verification). Given x(0), determine if
there exists u ∈ U such that y(t, u, x(0)) ∈
/ B for all t ≥ 0.
Now, we design a supervisor as follows. Every time τ , the
supervisor receives the measurements of current states of vehicles and drivers’ inputs. Based on the measurements, the
supervisor determines whether it must override the vehicles
at this time step because otherwise there will be no admissible input to avoid collisions at the next time step. This
decision can be made by solving the verification problem.
The supervisor-design problem is formulated as follows.
Problem 2 (Supervisor-design). At time kτ , given
state x(kτ ) and drivers’ input ukdriver ∈ U , design a supervisor that satisfies the following specifications.

(3)

Spec 2. It is non-blocking, that is, uksaf e must exist for any
k > 0 if u0saf e exists.
In Problem 2, Spec 1 guarantees that the supervisor is
least restrictive, and Spec 2 guarantees that the supervisor
always has an input to override vehicles to ensure safety.

4. PROBLEM SOLUTION
In this section, we solve the two problems: the verification problem (Problem 1) and the supervisor-design problem (Problem 2). As a main result, we formulate a job-shop
scheduling problem and prove that this problem is equivalent to Problem 1. Before formulating the job-shop scheduling problem in Section 4.2, we introduce classical job-shop
scheduling in Section 4.1. In Section 4.2, we also convert
the job-shop scheduling problem into a mixed-integer linear programming problem with the assumption of first-order
vehicle dynamics. In Section 4.3, the supervisor algorithm
satisfying the specifications of Problem 2 is given.

4.1 Classical job-shop scheduling
In classical job-shop scheduling [26], n jobs are processed
on m machines subject to the constraints that (a) each job
has its own prescribed sequence of machines to follow, and
(b) each machine can process at most one job at a time.
This can be represented by a disjunctive graph with a set of
nodes N and two sets of arcs C and D. Here, the sets are
defined as follows.
N := {(i, j) : (i, j) is the process of job j on machine i
for all j ∈ {1, . . . , n}},
′

C := {(i, j) → (i , j) : job j is must be processed on machine i
and then on machine i′ for all j ∈ {1, . . . , n}},
D := {(i, j) ↔ (i, j ′ ) : two jobs j and j ′ are to be processed
on machine i for all i ∈ {1, . . . , m}}.
The arcs in C, called the conjunctive arcs, represent the
routes of the jobs, and the arcs in D, called the disjunctive
arcs, connect two operations processed on a same machine.
Let F ⊆ N denote a set of the first operations of jobs,
and L ⊆ N denote a set of the last operations of jobs. If
each job has only one operation on its route, N = F = L.
The scenario in Section 2 can be described in job-shop
scheduling by considering vehicles as jobs and conflict areas as machines. For instance, each vehicle in Figure 2 has
its own prescribed route. Vehicle 1 crosses conflict area 1
first and then conflict area 3. At most one vehicle can be
inside each conflict area at a time, because otherwise collisions occur. The corresponding disjunctive graph is shown
in Figure 3.

1,1

3,1

2,2

1,2

3,3

2,3

Figure 3: Disjunctive graph of the example in Figure 2. The black solid lines are the conjunctive arcs,
and the red dotted lines are the disjunctive arcs.
Example 1. The disjunctive graph in Figure 3 consists of
the set of nodes
N = {(1, 1), (3, 1), (2, 2), (1, 2), (3, 3), (2, 3)},
and the sets of conjunctive and disjunctive arcs
C = {(1, 1) → (3, 1), (2, 2) → (1, 2), (3, 3) → (2, 3)},
D = {(1, 1) ↔ (1, 2), (2, 2) ↔ (2, 3), (3, 3) ↔ (3, 1)},
respectively.
The sets of the first and the last operations are F =
{(1, 1), (2, 2), (3, 3)} and L = {(3, 1), (1, 2), (2, 3)}, respectively.
In [3], as a variant of job-shop scheduling, release times
and deadlines are considered such that jobs must start after
given release times and be finished before given deadlines.
The release time rj and the deadline dj are defined for each
job j, not for each operation (i, j). The process time pj
is a constant for all operations of job j independent of the
machines. Then, the classical job-shop scheduling problem
with deadline is formulated as follows.
Problem 3 (Classical job-shop). Given the release
times rj , the deadlines dj , and the process time pj , determine if there exists the operation starting times tij for all
(i, j) ∈ N such that
for all (i, j) ∈ F,
for all (i, j) ∈ L,

rj ≤ tij ,
tij + pj ≤ dj ,

for all (i, j) → (i′ , j) ∈ C,

tij + pj ≤ ti′ j ,

for all (i, j) ↔ (i, j ′ ) ∈ D,

tij ≤ tij ′ ⇒ tij + pj ≤ tij ′ .

In the next section, a new job-shop scheduling problem
similar to Problem 3 is formulated to solve Problem 1.

4.2 Solution of Problem 1
4.2.1 Job-shop scheduling
In contrast to classical job-shop scheduling, our problem
must account for the dynamic model of vehicles (1). Thus,
process times, release times, and deadlines are not initially
given and not constant with operation starting times. Also,
they are defined for each operation, that is, depending on
the jobs and the machines as follows.
Definition 1. Given initial condition x(0) and schedule
T := {Tij ∈ R : yj (Tij , uj , xj (0)) = αij for some uj ∈
Uj , ∀(i, j) ∈ N }, process time Pij is defined for operation
(i, j) ∈ N as follows.

Figure 4: Process time, release time, and deadline
of vehicle 1 in the example in Figure 2. The thick
blue line represents the position of vehicle 1 on its
longitudinal path with the schedules T11 and T31 . For
(1, 1) ∈
/ L, P11 is a function of T11 and T31 , while for
(3, 1) ∈ L, P31 is a function of T31 only. Also, for
(3, 1) ∈
/ F, R31 and D31 are functions of T11 .

• If (i, j) ∈ L, for yj (0) < αij ,
Pij := min {t : yj (t, uj , xj (0)) = βij
uj ∈Uj

(4)

with constraint yj (Tij , uj , xj (0)) = αij }.
For αij ≤ yj (0) < βij , set Pij := minuj {t : yj (t, uj , xj (0)) =
βij }. For βij ≤ yj (0), set Pij = 0. If the constraint is
not satisfied, set Pij = ∞.
• If (i, j) ∈
/ L, that is, ∃(i′ , j) such that (i, j) → (i′ , j) ∈
C, for yj (0) < αij ,
Pij := min {t : yj (t, uj , xj (0)) = βij
uj ∈Uj

with constraint yj (Tij , uj , xj (0)) = αij
and yj (Ti′ j , uj , xj (0)) = αi′ j }.
(5)
For αij ≤ yj (0) < βij , set Pij := minuj {t : yj (t, uj , yj (0)) =
βij with constraint yj (Ti′ j , uj , xj (0)) = αi′ j }. For βij ≤
yj (0), set Pij = 0. If the constraints are not satisfied,
set Pij = ∞.
By the above definition, process time Pij is the earliest time
at which vehicle j can exit conflict area i.
Definition 2. Given initial condition x(0) and schedule
T := {Tij ∈ R : yj (Tij , uj , xj (0)) = αij for some uj ∈
Uj , ∀(i, j) ∈ N }, release time Rij and deadline Dij are
defined for operation (i, j) ∈ N as follows.
• If (i, j) ∈ F, for yj (0) < αij ,
Rij := min {t : yj (t, uj , xj (0)) = αij },
uj ∈Uj

Dij := max {t : yj (t, uj , xj (0)) = αij }.

(6)

uj ∈Uj

For αij ≤ yj (0), set Rij = 0 and Dij = 0.
• If (i, j) ∈
/ F, that is, ∃(i′ , j) such that (i′ , j) → (i, j) ∈

C, for yj (0) < αij ,
Rij := min {t : yj (t, uj , xj (0)) = αij
uj ∈Uj

Dij

with constraint yj (Ti′ j , uj , xj (0)) = αi′ j },
:= max {t : yj (t, uj , xj (0)) = αij
uj ∈Uj

with constraint yj (Ti′ j , uj , xj (0)) = αi′ j }.
(7)
For αij ≤ yj (0), set Rij = 0 and Dij = 0. If the constraint cannot be satisfied by any uj ∈ Uj , set Rij = ∞
and Dij = −∞.
By definition, release time Rij is the earliest time at which
vehicle j can enter conflict area i, and deadline Dij is the
latest such time.
If an intersection is modeled as a single conflict point as
in [10, 11], the process time is defined by (4), and the release
time and deadline by (6). This is because each vehicle has
a single operation so that F = L = N . As for multiple
conflict points, we have to include the effect of preceding
and succeeding operations in the definition. Notice that the
process time Pij in (5) depends on the schedules Tij and
Ti′ j where (i′ , j) is the succeeding operation of (i, j), and
the release time Rij and deadline Dij in (7) depend on Ti′ j
where (i, j) is the preceding operation of (i, j). An example
of these definitions is illustrated in Figure 4.
Using the above definitions, we formulate the job-shop
scheduling problem as follows.
Problem 4 (Job-shop Scheduling). Given x(0), determine the existence of a schedule T := {Tij : (i, j) ∈ N } ∈
|N |
R+ that satisfies the following constraints.
for all (i, j) ∈ N ,
′

for all (i, j) ↔ (i, j ) ∈ D,

Rij ≤ Tij ≤ Dij ,

(8)

Tij ≤ Tij ′ ⇒ Pij ≤ Tij ′ .

(9)

Constraint (9) implies avoidance of intersection collisions
between vehicles j and j ′ by ensuring that vehicle j must
exit conflict area i before vehicle j ′ enters it.
We now prove that Problem 1 is equivalent to Problem 4.
Before this, we introduce the formal definition of the equivalence between two problems, and prove a lemma that relates Constraint (8) to the existence of an input uj such
that yj (Tij , uj , xj (0)) = αij and yj (Pij , uj , xj (0)) = βij for
(i, j) ∈ N .
Definition 3. [12] An instance IA of Problem A is the information required to solve the problem. If IA satisfies Problem A, we write IA ∈ Problem A.
Problem A is reducible to Problem B if for any instance
IA of Problem A, an instance IB of Problem B can be constructed in polynomial time, and IA ∈ Problem A if and only
if IB ∈ Problem B. If Problem A is reducible to Problem B,
and Problem B is reducible to Problem A, then Problem A
is equivalent to Problem B.
Lemma 1. If Rij ≤ Tij ≤ Dij for all (i, j) ∈ N with
yj (0) < αij , there exists uj ∈ Uj such that yj (Tij , uj , xj (0)) =
αij and yj (Pij , uj , xj (0)) = βij .
Proof. By the definitions of Rij and Dij in (6), for the
first operation (i1 , j) on the route of vehicle j, there exists
an input signal uj such that yj (Ti1 j , uj , xj (0)) = αi1 j . This
is because the input space is path-connected, and the output

yj continuously depends on uj . Then, for the next operation
(i2 , j), that is, (i1 , j) → (i2 , j) ∈ C, since the constraint in
definition (7) is satisfied by the input signal uj , there is
an input signal uj such that yj (Ti2 j , uj , xj (0)) = αi2 j . By
induction on the sequence of operations, for all (i, j) ∈ N ,
there exists an input signal uj such that yj (Tij , uj , yj (0)) =
αij .
This input signal uj satisfies the constraints in the definition of Pij in (4) and (5). Since there exists at least one
input signal that satisfies the constraints, an input signal uj
exists such that yj (Pij , uj , xj (0)) = βij for all (i, j) ∈ N .
Theorem 1. Problem 1 is equivalent to Problem 4.
Proof. An instance of Problem 1 is {x(0), Θ}, where
Θ = {{αij , βij : ∀(i, j) ∈ N }, d, X, Y, U, U, N , F, L, C, D}.
Notice that an instance of Problem 4 is {x(0), Θ}, which is
identical to an instance of Problem 1. Thus, the construction of an instance takes O(1) time. All we have to show
is that given I = {x(0), Θ}, I ∈ Problem 1 if and only if
I ∈ Problem 4.
Suppose I ∈ Problem 1. Then, there exists ũ ∈ U such
that y(t, ũ, x(0)) ∈
/ B for all t ≥ 0. In this proof, we
assume yj (0) < αij . For all (i, j) ∈ N , let T̃ij = {t :
yj (t, ũj , xj (0)) = αij } and P̃ij = {t : yj (t, ũj , xj (0)) = βij }.
We will show that {T̃ij : (i, j) ∈ N } satisfies the constraints
in Problem 4 so that {x(0), Θ} ∈ Problem 4.
By the definitions of Rij and Dij , we have Rij ≤ T̃ij ≤ Dij
(Constraint (8)). For all (i, j) ↔ (i, j ′ ) ∈ D, assume without
loss of generality vehicle j enters conflict area i before vehicle
j ′ . Then we know that at t = P̃ij , since yj (t, ũj , xj (0)) =
βij , we have yj ′ (t, ũj , xj (0)) ≤ αij ′ . That is, P̃ij ≤ T̃ij ′ .
Since ũj satisfies all the constraints given in the definitions
of Pij , we have Pij ≤ P̃ij . Therefore, Pij ≤ T̃ij ′ (Constraint (9)).
Suppose I ∈ Problem 4. Then, there exists T̂ satisfying
the constraints in Problem 4. By Lemma 1, there exists û
that satisfies yj (T̂ij , ûj , xj (0)) = αij and yj (Pij , ûj , xj (0)) =
βij for all (i, j) ∈ N . In Constraint (9), for all (i, j) ↔
(i, j ′ ) ∈ D, we have Pij ≤ T̂ij ′ if T̂ij ≤ T̂ij ′ . Then, at t =
Pij ′ , we have yj (t, ûj , xj (0)) = βij while yj ′ (t, ûj ′ , xj ′ (0)) ≤
αi′ j . This implies that any two vehicles never meet inside a
conflict area, that is, y(t, û, x(0)) ∈
/ B for all t ≥ 0.
Therefore, there exists û such that y(t, û, x(0)) ∈
/ B for
all t ≥ 0.
By Theorem 1, we can solve Problem 1 by solving Problem 4. One may notice that Problem 4 is similar to the classical job-shop scheduling problem (Problem 3) if Dij = dj −pj
and Pij = tij +pj . However, in Problem 4, the release times,
deadlines, and process times are defined for each operation
as functions of the schedules. The fact that they vary depending on the schedules significantly complicates the problem. We thus cannot directly employ the solutions from
the scheduling literature. Instead, we have to formulate a
mixed-integer linear programming problem, which is proved
to yield the equivalent answers to Problem 4 by assuming
that the vehicle dynamics are single integrator dynamics.

4.2.2 Mixed-integer programming
Problem 4 can be transformed into a mixed-integer programming problem, which is an optimization problem subject to equality and inequality constraints in the presence of
continuous and discrete variables. Notice that Constraint (8)

is already an inequality constraint. However, Constraint (9)
contains a disjunctive constraint, which can be converted
into linear inequalities by introducing a binary variable kijj ′ ∈
{0, 1} and using the big-M method [16]. In particular, define


1 if vehicle j crosses conflict area i
kijj ′ :=
before vehicle j ′ ,

0 otherwise.

Also, let M be a large positive constant in R. Then Constraint (9) can be rewritten as follows:
for all (i, j) ↔ (i, j ′ ) ∈ D,
kijj ′ + kij ′ j = 1, kijj ′ , kij ′ j ∈ {0, 1}
Pij ≤ Tij ′ + M (1 − kijj ′ ),
Pij ′ ≤ Tij + M (1 − kij ′ j ),

(10)

for M sufficiently larger than Tij and Pij for all (i, j) ∈ N . If
kijj ′ = 1 and kij ′ j = 0, vehicle j crosses conflict area i before
vehicle j ′ so that Tij ≤ Tij ′ . Then, Pij ≤ Tij ′ is imposed
while Pij ′ ≤ Tij + M is automatically satisfied because of a
sufficiently large M . Thus, (10) encodes the same constraint
as (9).
Notice that because Rij , Dij , and Pij are functions of variable Tij , Problem 4 with Constraint (8) and (10) is a general
mixed-integer program (MIP). Due to its high complexity,
this formulation is usually difficult to solve [6]. If the constraints can be expressed in a linear function of variables, the
problem becomes a mixed-integer linear program (MILP).
Although MILP are combinatorial, several algorithmic approaches are available to solve medium to large size application problems [14].
To this end, we assume that the longitudinal dynamics of
vehicles are modeled as a single integrator as follows. For
vehicle j,
ẋj = uj ,

yj = x j .

(11)

Notice that the dynamic state xj ∈ Xj ⊆ R is the position,
and the control input uj ∈ Uj is the speed. Since vehicles
do not go in reverse, we let uj,min > 0.
With the first order dynamic model (11), we can transform
Problem 4 into a mixed-integer linear programming problem. Let us write Pij = Tij + minuj {t : yj (t, uj , αij ) = βij }
so that the constraint that yj (Tij , uj , xj (0)) = αij is automatically satisfied. By defining
pij := {t : yj (t, uj , αij ) = βij },
pij corresponds to the time spent inside conflict area i, independent of Tij . Then, the variables for the mixed-integer
linear programming problem are as follows:
• Tij for (i, j) ∈ N , continuous variables,
• pij for (i, j) ∈
/ L, continuous variables,
• kijj ′ and kij ′ j for (i, j) ↔ (i, j ′ ) ∈ D, binary variables.
Notice that pij for (i, j) ∈ L is excluded from the variables
because we can set pij = (βij − αij )/umax . This is possible because Pij = Tij + (βij − αij )/umax by definition (4),
and the minimum pij is most likely to satisfy the problem
formulated in the following paragraph.
Given the single integrator dynamics, we formulate the
mixed-integer linear programming problem as follows.

Problem 5. Given x(0), determine if there exists a feasible solution subject to the following constraints.
A. If (i, j) ∈ F, for yj (0) < αij
αij − yj (0)
αij − yj (0)
≤ Tij ≤
.
uj,max
uj,min
For αij ≤ yj (0), consider Tij = 0.
B. If (i, j) ∈
/ F, that is ∃(i′ , j) such that (i′ , j) → (i, j) ∈ C,
Ti′ j + pi′ j +

αij − βi′ j
αij − βi′ j
≤ Tij ≤ Ti′ j + pi′ j +
.
uj,max
uj,min

C. If (i, j) ∈
/ L, for yj (0) < αij ,
βij − αij
βij − αij
≤ pij ≤
.
uj,max
uj,min
For αij ≤ yj (0), consider instead

βij −yj (0)
uj,max

≤ pij ≤

βij −yj (0)
.
uj,min

If βij ≤ yj (0), the schedule of operation (i, j)
is not of interest.
D. For all (i, j) ↔ (i, j ′ ) ∈ D, with a large number M ∈ R+ ,
Tij + pij ≤ Tij ′ + M (1 − kijj ′ ),
Tij ′ + pij ′ ≤ Tij + M (1 − kij ′ j ),
kijj ′ + kij ′ j = 1.

We now prove that this problem yields equivalent answers
to the job-shop scheduling problem (Problem 4) with the
first-order dynamics.
Theorem 2. If the vehicle dynamics (1) are modeled as
(11), Problem 4 is equivalent to Problem 5.
Proof. Problem 4 and Problem 5 have an identical instance I = {x(0), Θ}. Thus, we need to show that I ∈ Problem 4 if and only if I ∈ Problem 5. We will prove that
I ∈ Problem 4 if I ∈ Problem 5, and I ∈
/ Problem 4 if
I∈
/ Problem 5.
Suppose I ∈ Problem 5. Then there exist a feasible solution (T̃, p̃, k̃) where T̃ = {T̃ij : ∀(i, j) ∈ N }, p̃ = {p̃ij :
∀(i, j) ∈
/ L}, and k̃ = {k̃ijj ′ , k̃ij ′ j : ∀(i, j) ↔ (i, j ′ ) ∈ D}.
For (i, j) ∈ F, Rij = (αij − yj (0))/uj,max and Dij =
(αij − yj (0))/uj,min by definition (6). For (i, j) ∈
/ F, that is,
∃(i′ , j) → (i, j) ∈ C, there is the constraint in definition (7)
that yj (T̃i′ j ) = αi′ j . Thus, Rij and Dij are as follows.
αij − αi′ j
αij − βi′ j
= T̃i′ j + p̃i′ j +
,
uj,max
uj,max
αij − βi′ j
αij − αi′ j
= T̃i′ j + p̃i′ j +
.
+
uj,min
uj,min

Rij = T̃i′ j +
Dij = T̃i′ j

The second equalities in both equations result from Constraint C. Therefore, Constrains A and B imply Rij ≤ T̃ij ≤
Dij for all (i, j) ∈ N (Constraint (8)).
In Constraint D, we have Pij ≤ T̃ij + p̃ij because Pij is
the minimum time to reach βij . Therefore, we have Pij ≤
T̃ij + p̃ij ≤ T̃ij ′ + M (1 − k̃ijj ′ ). Similarly, Pij ′ ≤ T̃ij ′ + p̃ij ′ ≤
T̃ij + M (1 − k̃ij ′ j ) (Constraint (10)).
Thus, T̃ satisfies the constraints in Problem 4. That is,
I ∈ Problem 4.

Suppose I ∈
/ Problem 5. Notice that if Constraint C is ignored and let pij = 0, the problem is always feasible because
for (i1 , j) ∈ F and (i1 , j) → (i2 , j), . . . , (id−1 , j) → (id , j) ∈
C,
Ti1 ,j =

αi j − βi1 j
αi1 j − yj (0)
, Ti2 j = Ti1 j + 2
,
uj,max
uj,max
αi j − βid−1 j
. . . , Tid j = Tid−1 j + d
uj,max

becomes a feasible solution for any j. Constraint D is also
satisfied because either Tij ≤ Ti′ j or Ti′ j ≤ Tij is always
true. We can thus find the maximum process time that is a
feasible solution for the problem without Constraint C. Since
I ∈
/ Problem 5, this solution violates Constraint C. Thus,
there is no pij ≥ (βij − αij )/uj,max for any (i, j) ∈
/ L such
that Constraints A, B, and D are satisfied. This, in turn,
implies that given the definition Pij = Tij + min pij , there is
no Pij ≥ Tij + (βij − αij )/uj,max such that the constraints
in Problem 4 are satisfied. Since Pij is not feasible, neither
/ Problem 4.
are Tij and kijj ′ . Thus, I ∈
We solve Problem 5 using CPLEX. The procedure that
solves Problem 5 given an instance I = {x(0), Θ} is referred
to as Jobshop(I). If I ∈ Problem 5, that is, I ∈ Problem 1
by Theorems 1 and 2, Jobshop(I) returns {T, p, yes}. Otherwise, it returns {∅, ∅, no}.

4.3 Solution of Problem 2
The supervisor runs in discrete time with a time step τ .
At time kτ where k > 0, it receives the measurements of the
states x(kτ ) and drivers’ inputs ukdriver ∈ U of the vehicles
near an intersection. By assuming that ukdriver is constant
for time [kτ, (k + 1)τ ), we predict a state at the next time
step, called a state prediction and denoted by x̂(ukdriver ), as
follows.
x̂(ukdriver ) = x(τ, ukdriver , x(kτ )).
Notice that Jobshop(x̂(ukdriver ), Θ) determines whether or
not collisions can be avoided at all future time given the
state prediction. If it returns {T, p, yes}, then the supervisor allows the vehicles to drive with input ukdriver for time
[kτ, (k + 1)τ ). The schedule T and the process time p
are used to generate a safe input signal uk+1,∞
saf e , defined
on time [(k + 1)τ, ∞). We define a safe input operator
σ(x̂(ukdriver ), T, p) as follows.
σ(x̂(ukdriver ), T, p)
∈ {(u1 , . . . , un ) ∈ U : yj (Tij , uj , x̂j (ukdriver,j )) = αij
and yj (pij , uj , αij ) = βij ∀(i, j) ∈ N },
(12)
where ukdriver,j is the j th entry of ukdriver , and x̂j (ukdriver,j )
is the j th entry of x̂(ukdriver ). This safe input signal is stored
for possible uses at the next time step.
If Jobshop(x̂(ukdriver ), Θ) returns {∅, ∅, no}, then the supervisor overrides the vehicles using the safe input signal
k,∞
stored at the previous step, uk,∞
saf e . Since usaf e is defined
k,∞
k
on time [kτ, ∞), let usaf e ∈ U be usaf e restricted to time
[kτ, (k + 1)τ ). The supervisor blocks the drivers’ inputs
ukdriver and returns the safe input uksaf e for time [kτ, (k+1)τ )
to prevent future collisions.
This procedure is written as an algorithm as follows.

Algorithm 1 Supervisor(x(kτ ), ukdriver )
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

{T1 , p1 , answer1 } = Jobshop(x̂(ukdriver ), Θ)
if answer1 = yes then
uk+1,∞ ← σ(x̂(ukdriver ), T1 , p1 )
k+1,∞
uk+1
(t) for t ∈ [(k + 1)τ, (k + 2)τ )
saf e ← u
k
return udriver
else
{T2 , p2 , answer2 } = Jobshop(x̂(uksaf e ), Θ)
uk+1,∞ ← σ(x̂(uksaf e ), T2 , p2 )
k+1,∞
uk+1
(t) for t ∈ [(k + 1)τ, (k + 2)τ )
saf e ← u
k
return usaf e
end if

If answer1 = yes, then the supervisor generates and stores
the safe input uk+1
saf e in lines 3-4, and does not intervene in
line 5. If answer1 = no, the supervisor solves the verification problem in line 7 given the state predicted with the
safe input uksaf e . It will be proved in the following theorem
that answer2 is always yes, which implies the non-blocking
property of the supervisor. Based on T2 and p2 , the supervisor generates and stores the safe input uk+1
saf e in lines 8-9,
and overrides the vehicles in line 10.
Theorem 3. Algorithm 1 solves Problem 2.
Proof. To prove that Algorithm 1 is a solution of Problem 2, we check if the algorithm satisfies the specifications
in Problem 2.
Specification 1 is met by the design of the algorithm. If
there exists u ∈ U such that y(t, u, x̂(ukdriver )) ∈
/ B for all
t ≥ 0, then Jobshop(x̂(ukdriver ), Θ) returns yes. In this case,
the supervisor returns ukdriver . Otherwise, it returns uksaf e ∈
U. The fact that this input makes Jobshop(x̂(uksaf e ), Θ)
return yes will be clear in the proof of the non-blocking
property.
To prove the non-blocking property, we use mathematical
induction on k where t = kτ . At t = 0, we assume u0saf e 6= ∅.
At t = (k − 1)τ , suppose there exists uk−1
saf e . That is, by
definition, there exists u′ ∈ U such that y(t, u′ , x̂(uk−1
/
saf e )) ∈
B for all t ≥ 0. If Jobshop(x̂(uk−1
),
Θ)
returns
yes,
then
driver
then there exists u ∈ U such that y(t, u, x̂(uk−1
/ B for
driver )) ∈
all t ≥ 0 by Problem 1.
Now at t = kτ , we want to prove that there exists uksaf e .
k−1
Notice that x(kτ ) is either x̂(uk−1
driver ) or x̂(usaf e ). In the
k
former case, let u be u restricted to time [kτ, (k + 1)τ ),
and uk+1,∞ be u restricted to time [(k + 1)τ, ∞). Then, we
have
y(t, uk+1,∞ , x(τ, uk , x̂(uk−1
/ B.
driver ))) ∈
Thus there exists uksaf e = uk . Similarly for the latter case,
let u′k be u′ restricted to time [kτ, (k + 1)τ ), and u′k+1,∞
be u′ restricted to time [(k + 1)τ, ∞). Then, we have
y(t, u′k+1,∞ , x(τ, u′k , x̂(uk−1
/ B.
saf e ))) ∈
Thus there exists uksaf e = u′k . Therefore, in any case, there
exists a safe input uksaf e .
If u0saf e exists, there exists uksaf e for any k > 0. The
supervisor is thus, non-blocking.

5. SIMULATION RESULTS

(a) Bad set

(b) Capture set

Figure 5: Position space of the three vehicles in the scenario of Figure 2. Subfigure (a) shows the bad set
defined in (2), and subfigure (b) shows the resulting capture set defined in (13). In (b), the black line is
the trajectory of the system, and the blue thick line highlights the positions at times when the supervisor
overrides the vehicles. Notice that the supervisor prevents them from entering the capture set, thereby
averting collision.

This section presents simulation results of the supervisor. In particular, considering the intersection scenarios illustrated in Figures 1 and 2, we validate that the supervisor
prevents impending collisions by minimally overridng vehicles. Also, the simulations illustrate that for a system with
a large number of vehicles, the computation time required
for the supervisor algorithm (Algorithm 1) at each step is
within the allotted 100 ms.
We implement Algorithm 1 using MATLAB, in which
mixed-integer programming in Problem 5 is solved by using CPLEX. To speed up the process of generating the constraints of the problem, MATLAB CoderTM [28] is used to
replace the code written in MATLAB with the C code and
compile it into a MATLAB executable function. Simulations
are performed on a personal computer, which runs Windows
7 Home Premium and consists of an Intel Core i7-3770s processor at 3.10 GHz and 8 GB random-access memory.
Consider first Figure 2, in which three vehicles are approaching the intersection containing three conflict points.
The parameters used in the simulations are τ =0.1, Uj =
[0.1, 0.3] for all j ∈ {1, . . . , n}, (αij , βij ) =(10,20) for (i, j) ∈
F, and (αij , βij ) = (αi′ j + 22, αij + 10) for (i, j) ∈
/ F, where
(i′ , j) → (i, j) ∈ C.
To solve the verification problem (Problem 1), the work
in [19] considers the set of initial states such that no input
exists to avoid a collision. This subset of the state space is
called the capture set and defined as follows.
CS := {x ∈ X : ∀u ∈ U, ∃t such that y(t, u, x) ∈ B}.
(13)
The capture set resulting from the bad set in Figure 5(a) is
shown in Figure 5(b). Given an instance I = {x(0), Θ} of
Problem 1, I ∈
/ Problem 1 if and only if x(0) ∈ CS by defi-

nition. By Theorems 1 and 2, if x(0) ∈ CS, I ∈
/ Problems 4
and 5.
In Figure 5(b), the black line represents the trajectory
of the system given an initial condition x(0) =(-2.8,-3.7,1.2). When the supervisor overrides the vehicles, the trajectory is shown in blue. The drivers’ inputs are set to be
ukdriver = (0.15, 0.11, 0.25) and constant for all k ≥ 0 where
t = kτ , so that without override actions of the supervisor,
the trajectory would enter the bad set in Figure 5(a). Notice that the supervisor overrides the vehicles right before
the trajectory enters the capture set and makes the trajectory ride on the boundary of the capture set. The drivers
regain the control of their vehicles once the dangerous situation is resolved. This confirms that the supervisor is least
restrictive because it intervenes only when the state prediction x̂(ukdriver ) enters the capture set. The computation of
the supervisor algorithm (Algorithm 1) takes less than 4 ms
per iteration in the worst case.
We then run Algorithm 1 for the intersection instance
shown in Figure 1, which contains twenty vehicles and forty
eight conflict points. Then, we inserted additional vehicles
per road (far enough so to ensure that rear-end collsions do
not occur) to determine how many vehicles the supervisor
can handle within the 100 ms. In Figure 6, the computation time required for one iteration of Algorithm 1 is shown
with respect to the number of vehicles. Notice that as the
number of vehicles increases, the computation time increases
exponentially. Although the problem is not scalable, about
twenty five vehicles can be managed by the supervisor within
the 100 ms even in the complicated intersection scenario.
The intersection scenario of Figure 1 is created from the
top 20 crash intersection locations in the report of the Massachusetts Department of Transportation [24] such that it
can represent each intersection topology by removing or com-

measurement and process uncertainty and the presence of
unequipped vehicles will be investigated in future work. Undetermined routes of vehicles will also be investigated by
considering possible decisions of steering inputs.

500
450

computation time (ms)

400
350

7. ACKNOWLEDGMENTS

300

The authors would like to thank Alessandro Colombo and
Gabriel Campos at Politecnico di Milano for the helpful discussions and suggestions. This work was in part supported
by NSF CPS Award No. 1239182.

250
200
150

8. REFERENCES

100
50
0
0

10

20

30

40

50

60

n

Figure 6: Computation time for one iteration of Algorithm 1 in the worst case with respect to the number of vehicles.
bining its lanes. That is, this intersection scenario consisting
of twenty lanes and forty eight conflict points is more complicated than the twenty most dangerous intersections in
Massachusetts. If we do not consider rear-end collisions and
assume that there is only one vehicle per road, the number
of vehicles in typical intersection scenarios usually does not
exceed twenty. We can thus conclude that this supervisor
is practical for typical intersection scenarios. How accounting for rear-end collisions affects computational complexity
will be investigated in future work. It is shown in [11] that
additional vehicles on the same lane increase computational
complexity less than those on different lanes due to precedence constraints. Since in Figure 6, we did not consider
these precedence constraints, we expect that the computation time will be lower than that shown in Figure 6.

6.

CONCLUSIONS

We have designed a supervisor that overrides human-driven
vehicles only when a future collision is detected and has
a non-blocking property. To this end, we have formulated
the verification problem and the job-shop scheduling problem and proved that they are equivalent. To solve the jobshop scheduling problem, we have converted it into a mixedinteger linear programming problem by assuming the single
integrator vehicle dynamics. The computer simulations confirm that the supervisor guarantees safety while overriding
vehicles only when a future collision is unavoidable otherwise. Also, the computational studies show that despite the
combinatorial complexity of the verification problem, the supervisor can deal with a complicated intersection scenario as
in Figure 1 within the allotted 100 ms per iteration.
While this paper considers a general intersection model in
terms of conflict areas, the inclusion of rear-end collisions in
the scenario makes it more practical. Moreover, to account
for more realistic dynamic behaviors of vehicles, a nonlinear second-order model will be considered. In particular,
for second-order linear dynamics, the job-shop scheduling
problem may be reformulated as a mixed-integer quadratic
programming problem. Also, as considered in [5, 1, 2] in
which an intersection is modeled as a single conflict area,

[1] H. Ahn, A. Colombo, and D. Del Vecchio. Supervisory
control for intersection collision avoidance in the
presence of uncontrolled vehicles. In American Control
Conference (ACC), June 2014.
[2] H. Ahn, A. Rizzi, A. Colombo, and D. Del Vecchio.
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),
2015.
[3] E. Balas, G. Lancia, P. Serafini, and A. Vazacopoulos.
Job shop scheduling with deadlines. Journal of
Combinatorial Optimization, 1(4):329–353, Dec. 1998.
[4] F. Borrelli, D. Subramanian, A. Raghunathan, and
L. Biegler. MILP and NLP techniques for centralized
trajectory planning of multiple unmanned air vehicles.
In American Control Conference (ACC), June 2006.
[5] L. Bruni, A. Colombo, and D. Del Vecchio. Robust
multi-agent collision avoidance through scheduling. In
IEEE Conference on Decision and Control (CDC),
Dec. 2013.
[6] M. R. Bussieck and S. Vigerske. MINLP Solver
Software. In Wiley Encyclopedia of Operations
Research and Management Science. John Wiley &
Sons, Inc., 2010.
[7] G. Campos, P. Falcone, H. Wymeersch, R. Hult, and
J. Sjoberg. Cooperative receding horizon conflict
resolution at traffic intersections. In IEEE Conference
on Decision and Control (CDC), Dec. 2014.
[8] L. Chen and C. Englund. Cooperative Intersection
Management: A survey. IEEE Transactions on
Intelligent Transportation Systems, 2015.
[9] M. Christodoulou and S. Kodaxakis. Automatic
commercial aircraft-collision avoidance in free flight:
the three-dimensional problem. IEEE Transactions on
Intelligent Transportation Systems, 7(2):242–249,
2006.
[10] A. Colombo and D. Del Vecchio. Efficient algorithms
for collision avoidance at intersections. In Hybrid
Systems: Computation and Control (HSCC), 2012.
[11] A. Colombo and D. Del Vecchio. Least restrictive
supervisors for intersection collision avoidance: A
scheduling approach. IEEE Transactions on
Automatic Control, 2014.
[12] T. H. Cormen. Introduction to algorithms. MIT Press,
2009.
[13] M. Earl and R. D’Andrea. Modeling and control of a
multi-agent system using mixed integer linear
programming. In IEEE Conference on Decision and
Control (CDC), Dec. 2002.

[14] C. A. Floudas. Nonlinear and mixed-integer
optimization: fundamentals and applications. Oxford
University Press, 1995.
[15] M. R. Garey and D. S. Johnson. Computers and
Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman and Company, San
Francisco, 1979.
[16] I. E. Grossmann and J. P. Ruiz. Generalized
disjunctive programming: A framework for
formulation and alternative algorithms for MINLP
optimization. In Mixed Integer Nonlinear
Programming, volume 154 of The IMA Volumes in
Mathematics and its Applications, pages 93–115.
Springer New York, 2012.
[17] E. I. Grotli and T. A. Johansen. Path planning for
UAVs under communication constraints using SPLAT!
and MILP. Journal of Intelligent and Robotic Systems,
65(1-4):265–282, 2011.
[18] Gurobi Optimization, Inc. Gurobi optimizer reference
manual.
http://www.gurobi.com/documentation/6.0/refman/,
2014.
[19] M. Hafner, D. Cunningham, L. Caminiti, and
D. Del Vecchio. Cooperative Collision Avoidance at
Intersections: Algorithms and Experiments. IEEE
Transactions on Intelligent Transportation Systems,
14(3):1162–1175, 2013.
[20] Intellient Tranportation Systems, Joint Program
Office, U.S. Department of Transportation. ITS
Strategic plan 2015-2019.
http://www.its.dot.gov/strategicplan.pdf, 2014.
[21] International Business Machines Corporation. IBM

[22]

[23]

[24]

[25]

[26]
[27]

[28]

ILOG CPLEX V12.1: Users manual for CPLEX.
ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optim
2009.
H. Kowshik, D. Caveney, and P. Kumar. Provable
systemwide safety in intelligent intersections. IEEE
Transactions on Vehicular Technology, 60(3):804–818,
2011.
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,
13(1):81–90, 2012.
Massachusetts Department of Transportation. 2012
Top Crash Locations Report.
https://www.massdot.state.ma.us/Portals/8/docs/traffic/Cras
2014.
National Highway Traffic Safety Administration, U.S.
Department of Transportation. 2012 Motor Vehicle
Crashes: Overview, Traffic Safety Facts.
http://www-nrd.nhtsa.dot.gov/Pubs/811856.pdf,
2013.
M. Pinedo. Scheduling theory, algorithms, and
systems. Springer, 4th edition, 2012.
A. Richards, T. Schouwenaars, J. P. How, and
E. Feron. Spacecraft trajectory planning with
avoidance constraints using mixed-integer linear
programming. Journal of Guidance, Control, and
Dynamics, 25(4):755–764, 2002.
The MathWorks, Inc. MATLAB CoderTM User’s Guide.
http://de.mathworks.com/help/pdf_doc/coder/coder_ug.pdf,
2015.

