Safe Platooning of Unmanned Aerial Vehicles via Reachability

arXiv:1503.07253v2 [] 21 Mar 2016

Mo Chen, Qie Hu, Casey Mackin, Jaime F. Fisac, and Claire J. Tomlin

Abstract— Recently, there has been immense interest in using
unmanned aerial vehicles (UAVs) for civilian operations such
as package delivery, firefighting, and fast disaster response.
As a result, UAV traffic management systems are needed to
support potentially thousands of UAVs flying simultaneously
in the airspace, in order to ensure their liveness and safety
requirements are met. Hamilton-Jacobi (HJ) reachability is a
powerful framework for providing conditions under which these
requirements can be met, and for synthesizing the optimal
controller for meeting them. However, due to the curse of
dimensionality, HJ reachability is only tractable for a small
number of vehicles if their set of maneuvers is unrestricted.
In this paper, we define a platoon to be a group of UAVs
in a single-file formation. We model each vehicle as a hybrid
system with modes corresponding to its role in the platoon, and
specify the set of allowed maneuvers in each mode to make
the analysis tractable. We propose several liveness controllers
based on HJ reachability, and wrap a safety controller, also
based on HJ reachability, around the liveness controllers. For
a single altitude range, our approach guarantees safety for one
safety breach; in the unlikely event of multiple safety breaches,
safety can be guaranteed over multiple altitude ranges. We
demonstrate the satisfaction of liveness and safety requirements
through simulations of three common scenarios.

I. I NTRODUCTION
Unmanned aerial vehicle (UAV) systems have in the past
been mainly used for military operations [1]. Recently,
however, there has been an immense surge of interest in
using UAVs for civil applications through projects such
as Amazon Prime Air and Google Project Wing [2], [3],
[4]. As a result, government agencies such as the Federal
Aviation Administration (FAA) and National Aeronautics
and Space Administration (NASA) of the United States are
also investigating air traffic control for autonomous vehicles
to prevent collisions among potentially numerous UAVs [5].
Optimal control and game theory are powerful tools for
providing liveness and safety guarantees to controlled dynamical systems, and various formulations [6], [7], [8] have
been successfully used to analyze problems involving a small
number of vehicles [9], [10], [11]. These formulations are
based on Hamilton-Jacobi (HJ) reachability, which computes
the backwards reachable set, defined as the set of states from
which a system is guaranteed to have a control strategy
This work is supported in part by NSF under CPS:ActionWebs (CNS0931843) and CPS:FORCES (CNS1239166), by NASA under grants
NNX12AR18A and UCSCMCA-14-022 (UARC), by ONR under grants
N00014-12-1-0609, N000141310341 (Embedded Humans MURI), and
MIT 5710002646 (SMARTS MURI), and by AFOSR under grants UPennFA9550-10-1-0567 (CHASE MURI) and the SURE project. The research
of M. Chen has received funding from the “NSERC PGS-D” Program. The
research of J.F. Fisac has received funding from the “la Caixa” Foundation.
All authors are with the Department of Electrical Engineering
and Computer Sciences, University of California, Berkeley.
{mochen72,qiehu,cmackin,jfisac,tomlin}@berkeley.edu

to reach a target set of states. Reachability is powerful
because it can be used for synthesizing both controllers that
steer the system towards a goal (liveness controllers), and
controllers that steer the system away from danger (safety
controllers). Furthermore, HJ formulations are flexible in
terms of system dynamics, enabling the analysis of nonlinear
systems. The power and success of HJ reachability analysis
in previous applications is evident, especially since numerical
tools are readily available to solve the associated HJ Partial Differential Equation (PDE) [12], [13], [14]. However,
the computation is done on a grid, making the problem
complexity scale exponentially with the number of states,
and therefore with the number of vehicles. This makes the
computation intractable for large numbers of vehicles.
A considerable body of work has been done on the
platooning of vehicles [15]. For example, [16] investigated
the feasibility of vehicle platooning in terms of tracking
errors in the presence of disturbances, taking into account
complex nonlinear dynamics of each vehicle. [17] explored
several control techniques for performing various platoon
maneuvers such as lane changes, merge procedures, and
split procedures. In [18], the authors modeled vehicles in
platoons as hybrid systems, synthesized safety controllers,
and analyzed throughput. Finally, reachability analysis was
used in [19] to analyze a platoon of two trucks in order
to reduce drag by minimizing the following distance while
maintaining collision avoidance safety guarantees.
Previous analyses of a large number of vehicles typically
do not provide liveness and safety guarantees to the extent
that HJ reachability does; however, HJ reachability typically cannot be used to tractably analyze a large number
of vehicles. In this paper, we attempt to reconciliate this
trade-off by assuming a single-file platoon, which provides
structure that allows pairwise safety guarantees from HJ
reachability to translate to safety guarantees for the whole
platoon. We first propose a hybrid systems model of UAVs
in platoons to capture this structure. Then, we show how HJ
reachability can be used to synthesize liveness controllers
that enable vehicles to reach a set of desired states, and
wrap safety controllers around the liveness controllers to
prevent dangerous configurations such as collisions. Finally,
we show simulation results of quadrotors forming a platoon,
a platoon responding to a malfunctioning member, and a
platoon responding to an outside intruder to illustrate the
behavior of vehicles in these scenarios and demonstrate the
guarantees provided by HJ reachability.

II. P ROBLEM F ORMULATION

Follow highway

Leave highway

A. Vehicle Dynamics
Leader

Consider a UAV whose dynamics are given by
ẋ = f (x, u)

(1)

n

nu

where x ∈ R represents the state, and u ∈ R represents
the control action. In this paper, we will assume that each
vehicle has a simple kinematics model of a quadrotor:
ṗx = vx ,

ṗy = vy

v̇x = ux ,

v̇y = uy ,

|ux |, |uy | ≤ umax

B. Relative Dynamics and Augmented Relative Dynamics
Besides (6), we will also consider the relative dynamics
between two quadrotors Qi , Qj . These dynamics can be
obtained by defining the relative variables
py,r = py,i − py,j

vx,r = vx,i − vx,j ,

vy,r = vy,i − vy,j

(3)

We treat Qi as Player 1, the evader who wishes to avoid
collision, and we treat Qj as Player 2, the pursuer, or
disturbance, that wishes to cause a collision. In terms of the
relative variables given in (3), we have
ṗx,r = vx,r ,

ṗy,r = vy,r

v̇x,r = ux,i − ux,j ,

v̇y,r = uy,i − uy,j

(4)

We also augment (3) with the velocity of Qi to impose a
velocity limit when performing the avoidance maneuver.
ṗx,r = vx,r ,

ṗy,r = vy,r

v̇x,r = ux,i − ux,j ,

v̇y,r = uy,i − uy,j

v̇x,i = ux,i ,

v̇y,i = uy,i

Merge onto
highway

Free:
• Vehicle not in a
platoon or on a
highway

Follower

Join platoon
Leave highway

• Member of
platoon

• Descends after a
duration of 𝑡internal

Fig. 1: Hybrid modes for vehicles in platoons.

maintain a separation distance of b. In order to allow for close
proximity of the quadrotors and the ability to resolve multiple
simultaneous safety breaches, we assume that in the event of
a malfunction, a quadrotor will be able to exit the altitude
range of the highway within a duration of tinternal = 1.5.
Such a requirement may be implemented practically as an
emergency landing procedure to which the quadrotors revert
when a malfunction is detected. Each quadrotor must be
capable of performing a number of essential cooperative
maneuvers. In this paper, we consider the following:
•
•
•
•
•
•

safely merging onto an air highway;
safely joining a platoon;
reacting to a malfunctioning vehicle in the platoon;
reacting to an intruder vehicle;
following the highway, a curve defined in space at
constant altitude, at a specified speed;
maintaining a constant relative position and velocity
with the leader of a platoon.

D. Vehicles as Hybrid Systems
A UAV in general may be in a number of modes of
operations, depending on whether it is part of a platoon, and
in the affirmative case, whether it is a leader or a follower.
Therefore, it is natural to model vehicles as hybrid systems
[18], [20]. In this paper, we restrict the available maneuvers
of each quadrotor depending on the mode. We assume that
each quadrotor in the airspace has the following modes:
•

(5)
•

C. Quadrotors in a Platoon
We consider a platoon of quadrotors to be a group of M
quadrotors QP1 , . . . , QPM in a single-file formation. Not all
of the N quadrotors need to be in a platoon: {Pj }M
j=1 ⊆
{i}N
.
Q
is
the
leader
of
the
platoon,
and
Q
,
.
.
.
, QPM
P1
P2
i=1
are the followers. We will assume that the quadrotors in a
platoon travel along an air highway, which is defined by
as a path inside a pre-defined altitude range. The quadrotors

Follow platoon

Merge with
platoon in front

Faulty

(2)

where the state (at a fixed altitude) x = (px , vx , py , vy ) ∈
R4 represents the quadrotor’s position in the x direction, its
velocity in the x direction, and its position and velocity in the
y direction, respectively. For convenience, we will denote the
position and velocity p = (px , py ), v = (vx , vy ), respectively.
We will consider a group of N quadrotors Qi , i = 1 . . . , N .
In general, the problem of collision avoidance among N
vehicles cannot be tractably solved using traditional dynamic
programming approaches because the computation complexity of these approaches scales exponentially with the number
of vehicles. Thus, in our present work, we will consider the
situation where N quadrotors form a platoon. The structure
imposed by the platoon enables us to analyze the liveness
and safety of the quadrotors in a tractable manner.

px,r = px,i − px,j ,

Create
new
platoon

• Leader of
platoon

•
•

Free: Vehicle not in a platoon. Available maneuvers:
merge onto a highway, join a platoon on a highway.
Leader: Leader of platoon (could be by itself). Available
maneuvers: travel along the highway at a pre-specified
speed, merge current platoon with a platoon in front,
leave the highway.
Follower: Vehicle following the platoon leader. Available maneuvers: follow a platoon, create a new platoon.
Faulty: Malfunctioned vehicle in a platoon: reverts to
default behavior and descends after a duration of tinternal .

The available maneuvers and associated mode transitions
are shown in Figure 1.

E. Objectives

of the following terminal value Hamilton-Jacobi-Isaacs (HJI)
PDE:

Using the previously-mentioned modeling assumptions,
we would like to address the following questions:
1) How can vehicles effectively form platoons?
2) How can the safety of the vehicles be ensured during
normal operation and when there is a malfunctioning
vehicle within the platoon?
3) How can the platoon respond to intruders such as
unresponsive UAVs, birds, or other aerial objects?
The answers to these questions can be broken down into
the maneuvers listed in Section II-C. In general, the control
strategies of each vehicle have a liveness component, which
specifies a set of states towards which the vehicle aims to
reach, and a safety component, which specifies a set of states
that it must avoid. In this paper, we address both the liveness
and safety component using reachability analysis.

In the special case where there is only one player (Player
2 does not exist), we obtain an optimal control problem for
a system with dynamics

III. H AMILTON -JACOBI R EACHABILITY

ẋ = f (x, u), t ∈ [−T, 0], u ∈ U.

A. General Framework
Consider a differential game between two players described by the system
ẋ = f (x, u1 , u2 ), for almost every t ∈ [−T, 0]

(6)

Dt V + min{0, max min Dx V · f (x, u1 , u2 )} = 0,
u1 ∈U1 u2 ∈U2

from which we obtain V(t) = {x ∈ Rn | V (t, x) ≤ 0}.
From the solution V (t, x), we can also obtain the optimal
controls for both players via the following:
u∗1 (t, x) = arg max min Dx V (t, x) · f (x, u1 , u2 )
u1 ∈U1 u2 ∈U2

u∗2 (t, x) = arg min Dx V (t, x) · f (x, u∗1 , u2 )

γ ∈ Γ := {N : U1 → U2 | u1 (r) = û1 (r)
for almost every r ∈ [t, s] ⇒ N [u1 ](r)

(7)

= N [û1 ](r) for almost every r ∈ [t, s]}
In our differential game, the goal of Player 2 is to drive
the system into some target set L, and the goal of Player 1
is to drive the system away from it. The set L is represented
as the zero sublevel set of a bounded, Lipschitz continuous
function l : Rn → R. We call l(·) the implicit surface
function representing the set L = {x ∈ Rn | l(x) ≤ 0}.
Given the dynamics (6) and the target set L, we would
like to compute the backwards reachable set, V(t):
V(t) := {x ∈ Rn | ∃γ ∈ Γ such that ∀u1 (·) ∈ U1 ,
∃s ∈ [t, 0], ξf (s; t, x, u1 (·), γ[u1 ](·)) ∈ L}

(8)

where ξf is the trajectory of the system satisfying initial
conditions ξf (t; x, t, u1 (·), u2 (·)) = x and the following
differential equation almost everywhere on [−t, 0]:
d
ξf (s; x, t, u1 (·), u2 (·))
ds
= f (ξf (s; x, t, u1 (·), u2 (·)), u1 (s), u2 (s))

(9)

For this paper, we use the HJ formulation in [7], which has
shown that the backwards reachable set V(t) can be obtained
as the zero sublevel set of the viscosity solution [23] V (t, x)

(11)

u2 ∈U2

(12)

The reachable set in this case would be given by the
Hamilton-Jacobi-Bellman (HJB) PDE
Dt V (t, x) + min{0, min Dx V (t, x) · f (x, u)} = 0
u∈U

(13)
V (0, x) = l(x)

n

where x ∈ R is the system state, u1 ∈ U1 is the control
of Player 1, and u2 ∈ U2 is the control of Player 2. We
assume f : Rn × U1 × U2 → Rn is uniformly continuous,
bounded, and Lipschitz continuous in x for fixed u1 , u2 , and
the control functions u1 (·) ∈ U1 , u2 (·) ∈ U2 are drawn from
the set of measurable functions. Player 2 is allowed to use
nonanticipative strategies [21], [22] γ, defined by

(10)

V (0, x) = l(x)

where the optimal control is given by
u∗ (t, x) = arg min Dx V (t, x) · f (x, u)
u∈U

(14)

For our application, we will use a several decoupled
system models and utilize the decoupled HJ formulation in
[24], which enables real time 4D reachable set computations
and tractable 6D reachable set computations.
IV. L IVENESS C ONTROLLERS
A. Merging onto a Highway
We model the merging of a vehicle onto an air highway as
a path planning problem, where we specify a target position
and velocity along the highway. Thus, a vehicle would aim
to drive the system (6) to a state x̄H = (p̄x , v̄x , p̄y , v̄y ), or a
small range of states defined by the set
LH = {x : |px − p̄x | ≤ rpx , |vx − v̄x | ≤ rvx ,
|py − p̄y | ≤ rpy , |vy − v̄y | ≤ rvy }.

(15)

In this reachability problem, LH is the target set, represented by the zero sublevel set of the function lH (x), which
specifies the terminal condition of the HJB PDE to be solved.
The solution we obtain, VH (t, x), is the implicit surface
function representing the reachable set VH (t); VH (−T, x) ≤
0, then, specifies the reachable set VH (T ), the set of states
from which the system can be driven to the target LH within
a duration of T . This gives the algorithm for merging onto
the highway:
1) Move towards x̄H in a straight line until VH (−T, x) ≤
0. This simple controller is chosen heuristically.
2) Apply the optimal control extracted from VH (−T, x)
according to (14) until LH is reached.

V. S AFETY C ONTROLLERS

B. Merging into a Platoon
We again pose the merging of a vehicle into a platoon
on an air highway as a reachability problem. Here, we
would like quadrotor Qi to merge onto the highway and
follow another vehicle Qj in a platoon. Thus, we would
like to drive the system given by (5) to a specific x̄P =
(p̄x,r , v̄x,r , p̄y,r , v̄y,r ), or a small range of relative states
defined by the set
LP = {x : |px,r − p̄x,r | ≤ rpx , |vx,r − v̄x,r | ≤ rvx ,
|py,r − p̄y,r | ≤ rpy , |vy,r − v̄y,r | ≤ rvy }

(16)

The target set LP is represented by the implicit surface
function lP (x), which specifies the terminal condition of the
HJI PDE (10). The zero sublevel set of the solution to (10),
VP (−T, x), gives us the set of relative states from which
Qi can reach the target and join the platoon following Qj
within a duration of T . We assume that Qj moves along the
highway at constant speed, so that uj (t) = 0. The following
is a suitable algorithm for a vehicle merging onto a highway
and joining a platoon to follow Qj :
1) Move towards x̄P in a straight line until VP (−T, x) ≤
0.
2) Apply the optimal control extracted from VP (−T, x)
according to (11) until LP is reached.
C. Other Quadrotor Maneuvers
For the simpler maneuvers of traveling along a highway
and following a platoon, we resort to simpler controllers
described below.
1) Traveling along a highway: We use a model-predictive
controller (MPC) for traveling along a highway at a prespecified speed. Here, a leader quadrotor tracks a constantaltitude path, defined as a curve p̄(s) parametrized by
s ∈ [0, 1] in p = (px , py ) space (position space), while
maintaining a velocity v̄(s) that corresponds to constant
speed in the direction of the highway.
2) Following a Platoon: Follower vehicles use a feedback
control law tracking a nominal position and velocity in the
platoon, with an additional feed-forward term given by the
leader’s acceleration input.
The i-th member of the platoon, QPi , is expected to track
a relative position in the platoon ri = (rxi , ryi ) with respect
to the leader’s position pP1 , and the leader’s velocity vP1 at
all times. The resulting control law has the form:




ui (t) = kp pP1 (t)+ri (t)−pi (t) +kv vP1 (t)−v i (t) +uP1 (t)
(17)
for some kp , kv > 0. A simple rule for determining ri (t) in
a single-file platoon is given for QPi as:
ri (t) = −(i − 1)b

vP1
kvP1 k2

(18)

where b is the spacing between vehicles along the platoon.
v
and kvPP1k2 is the platoon leader’s direction of travel.
1

A. Wrapping Reachability Around Existing Controllers
A quadrotor can use a liveness controller when it is not in
any danger of collision with other quadrotors or obstacles.
If the quadrotor could potentially be involved in a collision
within the next short period of time, it must switch to a
safety controller. In this section, we will demonstrate how
HJ reachability can be used to both detect imminent danger
and synthesize a controller that guarantees safety within a
specified time horizon. For our safety analysis, we will use
the model in (5).
We begin by defining the target set LS , which characterizes configurations in relative coordinates for which vehicles
Qi , Qj are considered to be in collision:
LS = {x :|px,r |, |py,r | ≤ d ∨ |vx,i | ≥ vmax ∨ |vy,i | ≥ vmax }
(19)
With this definition, Qi is considered to be unsafe if Qi
and Qj are within a distance d in both x and y directions
simultaneously, or if Qi has exceeded some maximum speed
vmax in either x or y direction. For illustration purposes, we
choose d = 2 meters, and vmax = 5 m/s.
We can now define the implicit surface function lS (x)
corresponding to LS , and solve the HJI PDE (10) using lS (x)
as the terminal condition. As before, the zero sublevel set of
the solution VS (t, x) specifies the reachable set VS (t), which
characterizes the states in the augmented relative coordinates,
as defined in (5), from which Qi cannot avoid LS for a
time period of t, if Qj uses the worst case control. To avoid
collisions, Qi must apply the safety controller according to
(11) on the boundary of the reachable set in order to avoid
going into the reachable set. The following algorithm wraps
our safety controller around liveness controllers:
1) For a specified time horizon t, evaluateVS (−t, xi −xj )
for all j ∈ Q(i).
Q(i) is the set of quadrotors with which quadrotor i
checks safety against. We discuss Q(i) in Section V-B.
2) Use the safety or liveness controller depending on the
values VS (−t, xi − xj ), j ∈ Q(i):
If ∃j ∈ Q(i), VS (−t, xi − xj ) ≤ 0, then Qi , Qj are in
potential conflict, and Qi must use a safety controller;
otherwise Qi uses a liveness controller.
B. Platoon Safety Guarantees
Under normal operations in a single platoon, each follower
quadrotor QPi , i > 1 checks whether it is in the safety
reachable set with respect to QPi−1 and QPi+1 . So Q(i) =
{Pi+1 , Pi−1 } for i = P2 , . . . , PN −1 . Assuming there are no
nearby quadrotors outside of the platoon, the platoon leader
QP1 checks safety against QP2 , and the platoon trailer QPN
checks safety against QPN −1 . So Q(P1 ) = {P2 }, Q(PN ) =
{PN −1 }. No pair of quadrotors should be in an unsafe
configuration if the liveness controllers are well-designed.
Occasionally, a quadrotor Qk may behave unexpectedly due
to faults, which may lead to an unsafe configuration.

With our choice of Q(i) and the assumption that the
platoon is in a single-file formation, some quadrotor Qi
would get into an unsafe configuration with Qk , where Qk
is likely to be the quadrotor in front or behind of Qi . In this
case, a “safety breach” occurs. Our synthesis of the safety
controller guarantees that between every pair of quadrotors
Qi , Qk , as long as VS (−t, xi −xk ) > 0, ∃ui to keep Qi from
colliding with Qk for a desired time horizon t, despite the
worst case (an adversarial) control from Qk . Therefore, as
long as the number of “safety breaches” is at most one, Qi
can simply use the optimal control ui to avoid collision with
Qk for the time horizon of t. Since by assumption, vehicles
in platoons are able to exit the current altitude range within
a duration of tinternal , if we choose t = tinternal , the safety
breach would always end before any collision can occur.
Within a duration of tinternal , there is a small chance that
additional safety breaches may occur. However, as long as
the total number of safety breaches does not exceed the
number of affected quadrotors, collision avoidance of all
the quadrotors can be guaranteed for the duration tinternal .
However, as our simulation results show, putting quadrotors
in single-file platoons makes the likelihood of multiple safety
breaches low during a quadrotor malfunction and during the
presence of one intruder vehicle.
In the event that multiple safety breaches occur for some
of the quadrotors due to a malfunctioning quadrotor within
the platoon or an intruding quadrotor outside of the platoon,
those quadrotors with more than one safety breach still
have the option of exiting the highway altitude range in
order to avoid collisions. Every extra altitude range reduces
the number of simultaneous safety breaches by 1, so K
simultaneous safety breaches can be resolved using K − 1
different altitude ranges.
Given that quadrotors within a platoon are safe with
respect to each other, each platoon can be treated as a single
vehicle, and perform collision avoidance with other platoons.
By treating each platoon as a single unit, we reduce the
number of individual quadrotors that need to check for safety
against each other, reducing overall computation burden.
VI. S CENARIO C ASE S TUDY
In this section, we consider several situations that quadrotors in a platoon on an air highway may commonly encounter, and show via simulations the behaviors that emerge
from the controllers we defined in Sections IV and V.
A. Forming a Platoon
We first consider the scenario in which some quadrotors
are trying to merge onto an initially unoccupied highway. In
order to do this, each quadrotor first checks for safety with
respect to the other quadrotors, and uses the safety controller
if necessary, according to Section V. Otherwise, the quadrotor uses the liveness controller described in Section IV.
For the simulation example, the highway is specified by
the line py = 0.5px , the point of entry on the highway is
chosen to be (p̄x , p̄y ) = (4, 2), and the target velocity is
such that the quadrotors travel at a speed v̄ = 3 along the

direction of the highway. This forms the target state x̄H =
(p̄x , v̄x , p̄y , v̄y ), from which we define the target set LH as
in Section IV-A.
The first quadrotor that completes merging onto the empty
highway creates a platoon and becomes its leader, while
subsequent quadrotors form a platoon behind the leader in
a pre-specified order according to the process described in
Section IV-B. Here, we choose (p̄x,r , p̄y,r ) to be a distance
b behind the last quadrotor in the platoon, and (v̄x,r , v̄y,r ) =
(0, 0). This gives us the target set LP .
Figures 2 and 3 show the simulation results. Since the
liveness reachable sets are in 4D and the safety reachable
sets are in 6D, we compute and plot their 2D slices based
on the quadrotors’ velocities and relative velocities.
Figure 2 illustrates the use of liveness and safety reachable
sets using just two quadrotors to reduce visual clutter. The
first quadrotor Q1 (red disk) first travels in a straight line
towards the highway merging point x̄ (red circle) at t = 1.5,
because it is not yet in the liveness reachable set for merging
onto the highway (red dotted boundary). When it is within
the liveness reachable set boundary at t = 2.8, it is “lockedin” to the target state x̄H , and follows the optimal control
in (14) to x̄H . During the entire time, Q1 checks whether
it may collide with Q2 within a time horizon of texternal ; we
chose texternal = 3 > tinternal .
After Q1 has reached x̄H , it forms a platoon, becomes the
platoon leader, and continues to travel along the highway.
Q2 (blue disk), at t = 7, begins joining the platoon behind
Q1 , by moving towards the target x̄P relative to the position
of Q1 . When Q2 moves inside the liveness reachable set
boundary for joining the platoon (blue dotted boundary), it
is “locked-in” to the target relative state x̄P , and begins
following the optimal control in (11) towards the target
whenever it is outside the safety reachable set (blue dashed
boundary).
Figure 3 shows the behavior of all 5 quadrotors which
eventually form a platoon and travel along the highway
together. The liveness controllers allow the quadrotors to
optimally and smoothly enter the highway and join platoons,
while the safety controllers prevent collisions from occurring.
B. Malfunctioning Vehicle in Platoon
We now consider a scenario where a quadrotor in a platoon
of five malfunctions while the platoon is traveling along
a highway. To best demonstrate the behavior of the other
quadrotors in the platoon, this simulation assumes that QP3 ,
the middle quadrotor, malfunctions and reverses direction.
When this happens, all of the other quadrotors in the platoon
begin checking safety against it. In addition, QP3 is removed
from the platoon, causing the other quadrotors to treat it as
an intruder. Trailing quadrotors must leave the highway to
avoid colliding with the faulty quadrotor.
Figure 4 shows the platoon of quadrotors, Qi , i = 1, ..., 5
with Pi = i, traveling along the highway. At t = 0, Q3
malfunctions and begins to track the highway in reverse.
Once Q3 malfunctions, it is removed from the platoon
and treated as an intruder. The platoon is then restructured

t=1.5

t=0.1

t=2.8

40

40

30

30

20

20

10

10

0

0

-10

-10

-20

-20

-30

30

20

20

10
10

10
20

30

0

20

40

-20

0

20

40

t=12
40

30

30

20

20

y

t=7
40

0

-10

-10

-20

-20

-30
0

20

40

20

20

10

10

0

0

-10

-10

-20

-20

-30

30

40

0

20

40

-20

t=7

0

20

40

30

20

20

10

10

20

40

y

40

30

0

0

-10

-10

-20

-20

-30

-30
-20

0

20

x

40

60

10

20

30

40

60

Safety reachable set

-20

0

In this particular case, the safety breach is resolved even
without any altitude change.
C. Intruder Vehicle

t=10

40

50

Fig. 4: Reachable sets used by trailing quadrotors to avoid
colliding with the faulty quadrotor.

-30
-20

50

10
20

40

t=4

20

60

Position and velocity

t=1

20

50

Trajectories

0

Fig. 2: Reachable sets used to merge onto a highway to form
a platoon (top subplots) and to join a platoon on the highway
(bottom subplots).

30

40

Highway

Highway
Target location
Position and velocity
Liveness reachable set
Safety reachable set

30

30

t=4.5

20

x

40

20

x

-20

40

10

30

-30
-20

60

10

y

10

0

50

30

10

10

40

t=2.1

-30
-20

t=1

30

Highway
Trajectory
Position and velocity

Fig. 3: Five quadrotors merging onto a highway.

with the faulty quadrotor removed (QPi = Qi+1 for i =
3, 4). After avoiding Q3 , the trailing quadrotors Q4 and Q5
accelerate to reach their new platoon positions. Q1 and Q2
are unaffected by the malfunctioning quadrotor.
Figure 4 also shows the safe reachable set of Q4 with
respect to Q3 (green dashed line), and the safe reachable set
of Q5 with respect to Q4 and Q3 (purple dashed lines).
At t = 1, Q4 applies the safe controller to avoid entering
the safe reachable set with respect to Q3 . During Q4 ’s
avoidance maneuver, Q5 simply follows Q4 , and does not
come across any safety breaches, as shown by the t = 1
and t = 2.1 subplots. The safety breach ends soon after,
and by t = 4.5, Q4 begins merging back onto the highway,
followed by Q5 , in order to continue to follow the platoon.

We now consider the scenario in which a platoon of
quadrotors encounters an intruder vehicle. To avoid collision,
each quadrotor checks for safety with respect to the intruder
and any quadrotor in front and behind in the platoon.
If necessary, each quadrotor switches to using the safety
controller.
Figure 5 shows the simulation result. At t = 0, a platoon
of 4 quadrotors, QPi , i = 1, . . . , 4 with Pi = i, travel along
the highway. An intruder vehicle Q0 (red disk) starts from
position (40, 30) and heads toward bottom-left of the grid.
The platoon leader QP1 ’s (black disk) safety is unaffected
by the intruder. Followers QP2 (blue disk), QP3 (green disk)
and QP4 (pink disk), on the other hand, must use the safety
controller in order to avoid collision with the intruder (t =
3.3, 6.2). This causes their paths to deviate off the highway.
Once each quadrotor is safe relative to the intruder, they
rejoin the original platoon (t = 12.4). Figure 6 illustrates
the use of safety reachable sets in this scenario using only
QP2 as an example. The safety reachable sets of QP2 with
respect to the intruder Q0 , QP1 and QP3 (red, black, green
dashed lines) are shown.
Initially, QP2 (P2 = 2) is a follower outside all 3 safety
reachable sets. At t = 0.6, Q2 comes to the boundary of the
safety set with respect to the intruder and must apply the
safety control law to avoid potential future collision. Thus
it splits from the original platoon and becomes the leader
of a new platoon consisting of itself, Q3 and Q4 . Q2 keeps
using the safety controller until it is safe with respect to the
intruder again at t = 3. After t = 3, Q2 is safe to use the
liveness controller again to merge back onto the highway and
join the original platoon. Note that during the entire time, Q2
maintains safety against the intruder, Q1 and Q3 by always
staying outside of all three safety reachable sets.

t = 0.1

t = 3.3

70

70

60

60

50

50

40

40

30

30

20

20

10

R EFERENCES

10

0

0
0

20

40

60

0

20

t = 6.2

40

60

t = 12.4
70

60

60

50

50

40

40

30

30

20

20

10

10

y

70

0

0
0

20

40

60

0

20

40

60

x
Highway
Trajectory
Position and velocity

Fig. 5: Reaction of a platoon of 4 quadrotors on a highway
to an intruder.
t = 0.6

t = 2.0

50

50

45

45

40

40

35

35

30

30

25

25

20

20

15
10
10

15
20

30

40

50

10
10

20

t = 3.0
50

45

45

40

40

35

35

30

30

25

25

20

20

15

15
20

30

40

50

40

50

t = 3.5

50

10
10

30

40

50

10
10

20

30

Highway
Trajectory
Position and velocity
Safety reachable set

Fig. 6: Reachable sets used by quadrotor Q2 to avoid
collision with respect to the intruder and quadrotors Q1 and
Q3 in front and behind it respectively.

VII. C ONCLUSIONS AND F UTURE W ORK
We considered single-file platoons of UAVs modeled by
hybrid systems traveling along air highways. Using HJ
reachability, we proposed liveness controllers and built a
safety controller around them to ensure no collision can
occur from a single safety breach. Additional safety breaches
can be handled by multiple altitude ranges in the airspace.
Our simulations show that by putting vehicles into single-file
platoons, the likelihood of having multiple safety breaches
is low, and conflicts involving a single malfunctioning UAV
or intruder can be resolved in a single altitude level.

[1] B. P. Tice, “Unmanned aerial vehicles – the force multiplier of the
1990s,” Airpower Journal, 1991.
[2] Amazon.com, Inc. (2014) Amazon prime air. [Online]. Available:
http://www.amazon.com/b?node=8037720011
[3] J. Stewart. (2014) Google tests drone deliveries in Project Wing trials.
[Online]. Available: http://www.bbc.com/news/technology-28964260
[4] W. M. Debusk, “Unmanned aerial vehicle systems for disaster relief:
Tornado alley,” in Infotech@Aerospace Conferences, 2010.
[5] Jointed Planning and Development Office (JPDO), “Unmanned aircraft
systems (UAS) comprehensive plan – a report on the nation’s UAS
path forward,” Federal Aviation Administration, Tech. Rep., 2013.
[6] O. Bokanowski, N. Forcadel, and H. Zidani, “Reachability and minimal times for state constrained nonlinear problems without any controllability assumption,” SIAM Journal on Control and Optimization,
pp. 1–24, 2010.
[7] I. Mitchell, A. Bayen, and C. Tomlin, “A time-dependent HamiltonJacobi formulation of reachable sets for continuous dynamic games,”
IEEE Transactions on Automatic Control, vol. 50, no. 7, pp. 947–957,
2005.
[8] E. Barron and H. Ishii, “The Bellman equation for minimizing the
maximum cost,” Nonlinear Analysis: Theory, Methods & Applications,
1989.
[9] J. F. Fisac, M. Chen, C. J. Tomlin, and S. S. Sastry, “Reach-Avoid
Problems with Time-Varying Dynamics, Targets and Constraints.” in
18th International Conference on Hybrid Systems: Computation and
Controls, 2015.
[10] M. Chen, Z. Zhou, and C. Tomlin, “Multiplayer reach-avoid games via
low dimensional solutions and maximum matching,” in Proceedings
of the American Control Conference, 2014.
[11] J. Ding, J. Sprinkle, S. S. Sastry, and C. J. Tomlin, “Reachability
calculations for automated aerial refueling,” in IEEE Conference on
Decision and Control, Cancun, Mexico, 2008.
[12] I. Mitchell, A Toolbox of Level Set Methods, 2009, http://people.cs.
ubc.ca/∼mitchell/ToolboxLS/index.html.
[13] S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit
Surfaces. Springer-Verlag, 2002, ISBN: 978-0-387-95482-0.
[14] J. A. Sethian, “A fast marching level set method for monotonically
advancing fronts,” Proceedings of the National Academy of Sciences,
vol. 93, no. 4, pp. 1591–1595, 1996.
[15] P. Kavathekar and Y. Chen, “Vehicle platooning: A brief survey and
categorization,” vol. 3, pp. 829–845, 2011.
[16] D. McMahon, J. Hedrick, and S. Shladover, “Vehicle modelling
and control for automated highway systems,” in American Control
Conference, 1990, May 1990, pp. 297–303.
[17] J. Hedrick, G. Zhang, V. Narendran, K. Chang, and Partners for
Advanced Transit and Highways (Calif.) and University of California,
Berkeley. Institute of Transportation Studies, Transitional Platoon
Maneuvers in an Automated Highway System.
California PATH
Program, Institute of Transportation Studies, University of California
at Berkeley, 1992.
[18] J. Lygeros, D. Godbole, and S. Sastry, “Verified hybrid controllers
for automated vehicles,” Automatic Control, IEEE Transactions on,
vol. 43, no. 4, pp. 522–539, Apr 1998.
[19] A. Alam, A. Gattami, K. H. Johansson, and C. J. Tomlin, “Establishing safety for heavy duty vehicle platooning: A game theoretical
approach,” in 18th IFAC World Congress, Milan, Italy, August 2011.
[20] J. Lygeros, S. Sastry, and C. Tomlin, Hybrid Systems: Foundations,
advanced topics and applications. Springer Verlag, 2012.
[21] L. C. Evans and P. E. Souganidis, “Differential games and representation formulas for solutions of Hamilton-Jacobi-Isaacs equations,”
Indiana University Mathematics Journal, vol. 33, no. 5, pp. 773–797,
1984.
[22] P. Varaiya, “On the existence of solutions to a differential game,” SIAM
Journal on Control, vol. 5, no. 1, pp. 153–162, 1967.
[23] M. G. Crandall, L. C. Evans, and P. L. Lions, “Some properties of
viscosity solutions of hamilton-jacobi equations,” Transactions of the
American Mathematical Society, vol. 282, no. 2, p. 487, Apr. 1984.
[24] M. Chen and C. J. Tomlin, “Exact and efficient hamilton-jacobi reachability for decoupled systems,” 54th IEEE Conference on Decision and
Control, 2015.

