28

TH
INTERNATIONAL CONGRESS OF THE AERONAUTICAL SCIENCES

1


Abstract
A collision avoidance algorithm is described in
the condition that an UAV circumvents
designated targets which have their protected
region. Considering generalized shape of the
protected region, an ellipsoid is adopted to
represent the possible geometries. For the
collision avoidance algorithm, it is assumed that
en route UAVs are linked by real time data
bases like ADS-B and pre-determined
geographical feature information is available.
With the conditions, all UAVs know the
environmental information for their ongoing
path. The information for the other targets
positions and velocities are used to expect a
conflict or collision for one UAV and the UAV
maneuvers not to intrude the other targets
protected region. The avoidance algorithm is
used to generate a reference trajectory between
ongoing position and the instant for the targets
passed away. The possible trajectories between
the points for the start of avoidance and passed
by are tracked. For the case of multiple conflict
targets, determining the priority in accordance
with predicted conflict times for the targets, the
avoidance direction is determined to resolve the
conflict situation sequentially.
1 Introduction
The conception for Free Flight [1] has taken
main issue for UAV mission implementation
and it is popularly generalized these days as the
traffic of UAVs is growing. To realize the
purpose, many preliminary researches are
performed. For the collision detection and
alerting, it is general for aircraft to facilitate
TCAS or GPS-based traffic display system [2-4].
Therein, to alert the traffic condition, ADS-B is
essentially considered to transmit and
correspond to their en route information. The
word conflict can be defined as a predicted
violation of a separation assurance standard [3].
If two vehicles encounter each other where the
conflict has to be resolved, the vehicles are to
maneuver not to intrude certain protected region
for each other. Therefore, for the Free Flight,
it is very essential task to understand geometric
relations between two vehicles in a conflict.
One may determine a conflict condition by
simply calculating CPA(Closest Point of
Approach) and the relative distance at that point
as in [5]. As an extension of the previous studies
described above, our research group has
attempted to propose schemes to resolve the
conflict between aircrafts or UAVs. The
methods are based on the probabilistic motion-
based approach and the geometrical relation-
based approach for the conflict detection and
resolution [6, 7].
On the other hand, an UAV may face
obstacles such as mountain and big structure
during its mission implementation. The
geographical feature or artificial construction is
not dynamic target, but still an obstacle to avoid.
When assuming the protected regions for static
or dynamic obstacles are pre-designated, many
trajectories from starting point to goal position
are generated under the consideration of the
protected region for targets which are on the
possible paths for one UAV.
In this paper, to embody the protected
region for target, a figure of ellipsoid is used
and all targets are summed to have an assurance
standard volume expressed by certain part of an
ellipsoid as their protected region. If an UAV is
on route for task implementation, the UAV
UAV COLLISION AVOIDANCE VIA OPTIMAL
TRAJECTORY GENERATION METHOD
Jung-Woo Park*, Ji-Hoon Kim**, and Min-Jea Tahk*
* Division of Aerospace Engineering, KAIST, Daejeong, Korea,
** Department of Mechanical Engineering, Rice University, Houston, TX, USA
jwpark@fdcl.kaist.ac.kr; jk23@rice.edu; mjtahk@fdcl.kaist.ac.kr

Keywords: collision avoidance, optimal reference trajectory, multiple targets.
Jung-Woo Park, Ji-Hoon Kim, and Min-Jea Tahk
2
accesses the environmental information for
targets position (and velocity for dynamic
target) linked by a real-time data or pre-
provided data related with geographical
information. After recognition of the conflict
situation, the procedure is accomplished to
extract an optimal trajectory to resolve the
violation in an effective way. First of all, the
direction for avoidance is determined and a
reference trajectory to graze the firstly
upcoming target is obtained.
2 Dynamic Modeling
In this paper, it is assumed that all dynamic
targets and our UAV which performs its task
keep their constant velocities and are regarded
as point mass. Of dynamic targets only UAV is
our consideration for target generation. The
dynamics of our UAV is defined as follows.

x =V
H
cos
y =V
H
sin
z =V sinu =V
V
=
g tan|
V
H

(1)
where
H
V ,
V
V , , u , and | are horizontal and
vertical velocities, heading, pitch, and bank
angles respectively. Here, the bank angle and
pitch angle follows 1st order delayed equation
by command.

| =
1
t
|
|
com
|
( )

(2)

u =
1
t
u
u
com
u
( )

(3)
Eq. (2) and (3) implies the actuation
system delay with 1st order lag time constant.
3 Geometric Relation
3.1 Ellipsoid protected region
The protected region is regarded as an ellipsoid
volume. In the previous studies, the protected
region concept is employed to determine an
assurance zone secured [1,3,5,6]. The shapes are
varied with respect to approaches and their
applications. In this paper we assume that the
protected region takes an ellipsoidal volume
such that most of variable volumetric objects are
embodied. The objects can be a target UAV, a
geographical feature, or any kind of artificial
construction.
From the assumption of ellipsoid, an
example scenario on the way of our UAV can
be shown as in Fig. 1. In the scenario, Our UAV
has to resolve a conflict with the target UAV en
route path.


Fig. 1. One possible simulation condition with targets

To formulate the conflict situation in a
geometrical relation, we consider a relative
motion onto the target. If the target ellipsoid
center is located at the origin in the relative
frame, the ellipsoid surface equation is given as
2 2 2
2 2 2
1
x y z
a b c
+ + =

(4)
Here, a , b , and c indicate the ellipsoid
semi-axis lengths, and a vector ( x , y , z ) is
arbitrary position in relative coordinate. To
determine the conflict condition with targets,
relative positions and velocities are required.
From the given relative position and velocity
information, a line equation can be derived.
x x
r
u
r
=
y y
r
v
r
=
z z
r
w
r
= t
rel

(5)
-5000
0
5000
10000
-5000
0
5000
10000
15000
20000
0
2000
4000
6000
8000
X-axis
Y-axis
Z
-
a
x
i
s
St ar t i ng poi nt
of our UAV
Regi on of Mount ai n
Regi on of t ar get UAV

3
UAV COLLISION AVOIDANCE VIA OPTIMAL TRAJECTORY
GENERATION METHOD
where (x
r
, y
r
, z
r
) is relative position from the
target, and (u
r
,v
r
,w
r
) indicates the relative
velocity. On the other hand, if this line passes
through the targets ellipsoid volume, the
surface equation of ellipsoid, Eq. (4), and the
line equation, Eq.(5), have two real number
solutions for t
rel
. Here, t
rel
is the time of
crossings of relative trajectory (Fig. 2).


Fig. 2. Relative motion from a target position

When we consider the conflict where our
UAV go through the target UAVs protected
region as in Fig. 2, the solution for t
rel
is
obtained in the relation below.
u
r
2
a
2
+
v
r
2
b
2
+
w
r
2
c
2
|
\

|
.
|
t
rel
2
+2
u
r
x
r
a
2
+
v
r
y
r
b
2
+
w
r
z
r
c
2
|
\

|
.
|
t
rel
+
x
r
2
a
2
+
y
r
2
b
2
+
z
r
2
c
2
1
|
\

|
.
|
= At
rel
2
+ 2Bt
rel
+C = 0

(6)
Here, B s 0 indicates upcoming condition,
and B
2
AC > 0 means conflict.
3.2 Minimum avoidance direction
To avoid the conflict, our UAV must have a
trajectory not into the target ellipsoid. From the
relation in Eq. (6), the grazing points on targets
ellipsoid can be selected when B
2
AC = 0
which means one real value of t
rel
. And the
possible solution points on the target ellipsoid
via B
2
AC = 0 forms a connected line. The
direction vector from our UAV position to one
of the points yields the grazing trajectory. In this
paper, for efficient maneuver, a point on the
closed line is selected and a reference trajectory
is determined from our UAVs position to that
point so as to make minimum direction
difference between original direction and that of
the reference trajectory. Figure 3 shows the
required straight trajectory for minimum
avoidance direction when a conflict is detected.


Fig. 3. Minimum direction avoidance

The solution shown in Fig. 3 is obtained by
resolving the following optimization problem.
An optimization problem to find minimum
direction vector can be described as follows.

Objective :
To find a velocity vector

V
*
= (u
*
,v
*
,w
*
) such
that it yields a minimum angle avoidance
trajectory which grazes the protected region.

Formulation :
* * *
max ( , , ) ( , , )
r r r
J u v w u v w =

(7)
subject to
2
1 * * *
2 2 2
2 * * *
: 0 for vector ( , , )
: 1 0
C B AC u v w
C u v w
= =
= + + =

(8)
Finding zeros of the J acobian of
Hamiltonian shown in Eq. (9) with five
unknowns u
*
, v
*
, w
*
,
1
,
2
resolves the
optimization problem described in Eqs. (7) and
(8).
* * * 1 1 2 2
( , , ) ( , , )
r r r
H u v w u v w C C = + +
(9)
-5000
0
5000
10000
-5000
0
5000
10000
15000
20000
0
2000
4000
6000
8000
X-axis
Y-axis
Z
-
a
x
i
s
St ar t i ng poi nt
of our UAV
Jung-Woo Park, Ji-Hoon Kim, and Min-Jea Tahk
4
The J acobian matrix of Eq. (9) for the
vector
* * *
( , , ) u v w is given as follows.
1 2
1 2
* * *
1 2
1 2
* * *
1 2
1 2
* * *
0
0
0
r
r
r
C C H
u
u u u
C C H
v
v v v
C C H
w
w w w



c c c
= + + =
c c c
c c c
= + + =
c c c
c c c
= + + =
c c c

(10)
Equation (10) indicates the necessary
condition of optimal solution. Finally, with five
equations within Eq. (8) and (10), the five
unknowns can be solved by any kind of
optimization method. In this paper, the solution
is given by a temporary optimization via an
embedded function of MATLAB optimization
tool.
4 Multiple-Target Avoidance
The scheme for the pairwise conflict
resolution has been shown in section 3. And the
pairwise scheme is extended to the case for
multiple-target avoidance. In this paper, we
suggest a sequential algorithm to resolve the
condition with multiple conflicts. Firstly, we
consider the first two conflicts. The expected
times of all conflicts can be evaluated by
applying Eq. (6) to all targets. Of all conflicts,
the early two conflicts are our first concern.
Here, the direction vector for minimum
avoidance of each conflict is obtained. From
vector sum of them, we can predict the next step
direction of our UAV. As shown in Fig. 4, we
iterate the same procedure to derive the final
direction to avoid the two conflicts. When the
iteration is performed with very short time terms
as our UAV is guided to a recommended
direction vector during the flight, the solution
are converged to the contact point of two
projected ellipses. As a result, we can guide our
UAV to the finally converged optimal point of
avoidance where the optimal point is the contact
point as easily inferred in Fig. 4. However, all
conflict geometries are not resolvable. If the
curvatures of tangent of the projected ellipses
are less than those of corresponding circles with
same radius and the two vectors of the conflicts
are parallel to each other, then the solution from
adding them up is remains in the straight line
(Fig. 5). In this paper, when the solution is
unresolvable, some arbitrary disturbed direction
is preferentially applied and then the algorithm
may be functional.



Fig. 4. Convergence of avoidance direction



Fig. 5. An example of unresolvable geometry

5 Track of Reference Trajectory
When the desired direction is given by
avoidance algorithm, the reference trajectory is
the straight line of the vector.
The track of reference trajectory for UAV
can be performed properly as designing any
kind of controller. The controller calculates
bank/pitch command such that the UAV
maneuvers following the dynamics given in
section 2. Also, the absolute value of the
velocity of the UAV is assumed to be constant
by a velocity hold controller.

5
UAV COLLISION AVOIDANCE VIA OPTIMAL TRAJECTORY
GENERATION METHOD
The procedure of designing the controller
is not differed from general approaches, so it is
omitted in this paper.
6 Numerical Simulation
In this section, two simulation scenarios are
considered. The first one is a pairwise case
where our UAV senses just one conflict with a
target. The second one is the case that our UAV
senses a couple of conflicts and the proposed
algorithm in section 4 is applied to avoid
upcoming targets.
6.1 Pairwise case
For the pairwise case, the target is assumed to
have constant velocity to its goal position
somewhere to the direction of the velocity.
The initial conditions of our UAV and the
target are given as follows.

Initial condition :

<Our UAV >
(10,20,7) ( )
o
X km =

( 70, 130, 115) ( / )
o
V m s =

<Target 1 >
1
(0,0,0) ( )
t
X km =

2
(30,70, 50) ( / )
t
V m s =

Also, the semi-axis dimension of the
protected region of target 1 is given below.

Ellipsoid dimension of target 1 :

<Semi-axes for x, y, z >
( 1, 1, 1) (2.0,1.5,1.0) ( ) a b c km =

From described initial condition and
protected region of target 1, the predicted time
of conflict is about 96 second. And the
simulation results are shown in Figs. 6 and 7.
From the result, it is shown that our UAV
successfully resolve the conflict. The line of
trace shows the path of our UAV. In Fig. 7, the
miss distance from the nearest point of the
surface of the protected region to our UAV is
recorded. From the record, it is inferred that Our
UAV has not intruded targets protected region
and it grazed the surface of it. Also, as avoiding
the target, the time for minimum miss distance
occurs at around 98 sec.

-5
0
5
10
-5
0
5
10
15
20
-8
-6
-4
-2
0
2
4
6
8
X-axis (km)
Y-axis (km)
Z
-
a
x
i
s

(
k
m
)

(a) Initial encounter condition at 0 sec

-5
0
5
10
-5
0
5
10
15
20
-8
-6
-4
-2
0
2
4
6
8
X-axis (km)
Y-axis (km)
Z
-
a
x
i
s

(
k
m
)

(b) Trace of our UAV at 90 sec

-5
0
5
10
-5
0
5
10
15
20
-8
-6
-4
-2
0
2
4
6
8
X-axis (km)
Y-axis (km)
Z
-
a
x
i
s

(
k
m
)

(c) Trace of our UAV at 98 sec
Fig. 6. Trace of our UAV for pairwise case
Jung-Woo Park, Ji-Hoon Kim, and Min-Jea Tahk
6
0 50 100 150
0
5
10
15
20
25
Time (sec)
D
i
s
t
a
n
c
e

(
k
m
)
Miss distance for target No.1

Fig. 7. Miss distance form our UAV to target protected
region (km)

6.2 Conflict with two objects
In this subsection, we consider an additional
target which is stationary with zero velocity.
The initial condition and the dimension of its
protected region are given below.

Initial condition of target 2 :

<Target 2 >
2
(0,15, 60) ( )
t
X km =

2
(0,0,0) ( / )
t
V m s =

Ellipsoid dimension of target 2 :

<Semi-axes for x, y, z >
( 2, 2, 2) (5.0,6.5,3.0) ( ) a b c km =

In this scenario, our UAV predicts a couple
of conflicts and the times of occurrence of
conflicts are about 96 and 104 second
respectively.
The simulation results are shown in Figs.
8-10. Figure 8 lets us know the avoidance is
accomplished successfully and our UAV finally
grazes the second target surface. In this scenario,
our UAV had to change its original flight path
with larger turn angle than the first scenario
only with target 1. Also, form the results in Fig.
9 and 10, to avoidance all conflicts, the
maneuver apparently weights on the second
target avoidance. The minimum miss distance
for target 1 is about 3.8 km at about 93 second
and our UAV passes by target 2 with about 0.03
km at around 145 second.


-5
0
5
10
-5
0
5
10
15
20
-5
0
5
X-axis (km)
Y-axis (km)
Z
-
a
x
i
s

(
k
m
)

(a) Initial encounter condition at 0 sec

-5
0
5
10
-5
0
5
10
15
20
-8
-6
-4
-2
0
2
4
6
8
X-axis (km)
Y-axis (km)
Z
-
a
x
i
s

(
k
m
)

(b) Trace of our UAV at 110 sec

-5
0
5
10
-5
0
5
10
15
20
-5
0
5
X-axis (km)
Y-axis (km)
Z
-
a
x
i
s

(
k
m
)

(c) Trace of our UAV of blue line at 150 sec
Fig. 8. Trace of our UAV for conflicts with two objects



7
UAV COLLISION AVOIDANCE VIA OPTIMAL TRAJECTORY
GENERATION METHOD
0 20 40 60 80 100 120 140 160 180
2
4
6
8
10
12
14
16
18
20
22
Time (sec)
D
i
s
t
a
n
c
e

(
k
m
)
Miss distance for target No.1

Fig. 9. Miss distance form our UAV to the protected
region of target no.1 (km)

0 20 40 60 80 100 120 140 160 180
0
5
10
15
20
25
Time (sec)
D
i
s
t
a
n
c
e

(
k
m
)
Miss distance for target No.2

Fig. 10. Miss distance form our UAV to the protected
region of target no.2 (km)
7 Conclusion
In this paper, an algorithm on the avoidance of
conflict between our UAV and certain kind of
target is presented using geometric relation. The
protected regions of targets are assumed to form
ellipsoidal geometry. Additionally, it is assumed
that our UAV maneuvers defensively to the
targets; it is guided to a direction not to intrude
the protected region. The guidance direction of
our UAV is given as an optimization solution
with minimum avoidance direction angle. Also,
for the multiple-target case, our UAV takes an
action for the first two predicted conflicts,
which is simulated in this paper.

References
[1] Yang L C and Kuchar J K. Prototype Conflict
Alerting System for Free Flight. AIAA meeting paper,
1997.
[2] Krozel J , Peters M E and Hunter G. Conflict
Detection and Resolution for Future Air
Transportation Management, Segull technology, Icn.,
1997.
[3] Kelly W E III, Collins R, Rapids C and Iowa.
Conflict Detection and Alerting for Separation
Assurance Systems. Digital Avionics Systems
Conference, 1999.
[4] Isaacson D R, Erzberger H. Design of a Conflict
Detection Algorithm for the Conter/Tracon
Automation System. NASA Ames Research Center
M.S 210-9, Moffett Field, CA, pp. 9.3-1 9.3-9.
[5] Krozel J and Peters M E. Strategic Conflict Detection
and Resolution for Free Flight, Seagull technology,
Inc., 1997.
[6] Kim K, Park J , Tahk M. A Probabilistic Algorithm
for Multi-aircraft Collision Detection and Resolution
in 3-D. International Journal of Aeronautical and
Space Sciences, Vol. 9, No. 2, pp.1-8, 2008.
[7] Park J , Oh H, Tahk M. UAV Collision Avoidance
Based on Geometric Approach. International Journal
of Aeronautical and Space Sciences, Vol. 10, No. 1,
pp.37-45, 2008.
Copyright Statement
The authors confirm that they, and/or their company or
organization, hold copyright on all of the original material
included in this paper. The authors also confirm that they
have obtained permission, from the copyright holder of
any third party material included in this paper, to publish
it as part of their paper. The authors confirm that they
give permission, or have obtained permission from the
copyright holder of this paper, for the publication and
distribution of this paper as part of the ICAS2012
proceedings or as individual off-prints from the
proceedings.