UAV Collision Avoidance using A* Algorithm
by
Tingsheng Liao
A thesis submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Master of Science
Auburn, Alabama
May 7, 2012
Keywords: UAV, collision avoidance, A* algorithm, heuristic
Copyright 2012 by Tingsheng Liao
Approved by
Thaddeus Roppel, Co-Chair, Associate Professor of Electrical and Computer Engineering
Saad Biaz, Co-Chair, Associate Professor of Computer Sicence and Software Engineering
John Hung, Professor of Electrical and Computer Engineering
Abstract
Collision avoidance is the essential requirement for unmanned aerial vehicles (UAVs) to
become fully autonomous. Several algorithms have been proposed to do the path planning
in a simulated environment, but only few can make them e ectively survive in a dynamic
environment. This issue keeps UAVs from commercial and other applications because when
the UAVs  y autonomously, the inability to reliably sense and avoid other aircraft in the air
can cause serious hazards.
In this thesis, we review several approaches including A algorithm, total  eld sensing
approach, and Markov decision process. Then, a modi cation of A algorithm is proposed.
Typically, A algorithm is implemented in a mobile robot system for the path planning in
a static environment. We introduce some approaches to allow us using A algorithm in
a dynamic environment. The evaluation of this algorithm is based on the simulation of
di erent scenarios, and the comparison between two heuristic functions will be detailed. We
discuss the performance of our approach, the suitable condition for it to work reliably, and
what issues could a ect its performance. We also investigate the limitation of our approach
in the extreme scenarios to provide useful suggestions for improvement.
ii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Geometric Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Free Flight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Point of Closest Approach . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Stochastic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Markov Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Linear Programming Approach . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Mixed Integer Linear Programming . . . . . . . . . . . . . . . . . . . 8
2.4 Potential Fields Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.1 Total Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.2 Force Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Grid-based Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.1 Search Trees Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5.3 A Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 UAVs Collision Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Easy Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Con ict Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.1 Intruder Awareness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
iii
3.2.2 Con ict Determination . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Collision Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.1 A algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Dangerous Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.3 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1 The Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Simulation in a 500 m 500 m  eld . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Simulation in a 1000 m 1000 m  eld . . . . . . . . . . . . . . . . . . . . . 34
4.4 Relation Between Number of UAVs and Metrics . . . . . . . . . . . . . . . . 36
4.5 Extreme cases for UAVs collision avoidance . . . . . . . . . . . . . . . . . . . 39
4.6 Comparison with Other Algorithms . . . . . . . . . . . . . . . . . . . . . . . 40
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
iv
List of Figures
2.1 Illustration of free  ight protected and alert zones. [24] . . . . . . . . . . . . . . 4
2.2 Illustration for Point of Closest Approach method. [32] . . . . . . . . . . . . . . 5
2.3 Magnetic  ux density around a magnetic dipole [38] . . . . . . . . . . . . . . . 10
2.4 (a) Surrounding  eld along the x-axis (b) Surrounding  eld along the y-axis [38] 10
2.5 Shakey, the mobile robot system. 1966 through 1972 [1](Photograph courtesy of
SRI International.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6 Illustration of Shakey?s navigation problem[31](Original image from SRI Interna-
tional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7 A path search around an obstacle.[40] . . . . . . . . . . . . . . . . . . . . . . . 16
3.1 Easy Star, the Unmanned Aerial Vehicle . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Illustration of intruder awareness. . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Classi cation of protected zones, including Tra c Advisory Zone, Resolution
Advisory Zone, and Autonomous Avoidance Zone. . . . . . . . . . . . . . . . . 21
3.4 Collision avoidance architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.5 Illustration of A path  nding algorithm.[27] . . . . . . . . . . . . . . . . . . . 23
3.6 The dangerous grids changes with the di erent time step. . . . . . . . . . . . . 25
v
3.7 (a) Path  nding using classic A method (b) Path  nding using fudge method [29] 26
4.1 Cumulative density function(CDF) plot of con icts in a 500 m 500 m  eld . . 31
4.2 CDF plot of deviation ratio in a 500 m 500 m  eld . . . . . . . . . . . . . . . 32
4.3 CDF plot of crash in a 500 m 500 m  eld . . . . . . . . . . . . . . . . . . . . 33
4.4 CDF plot of con icts in a 1000 m 1000 m  eld . . . . . . . . . . . . . . . . . 34
4.5 CDF plot of deviation ratio in a 1000 m 1000 m  eld . . . . . . . . . . . . . 35
4.6 CDF plot of crash in a 1000 m 1000 m  eld . . . . . . . . . . . . . . . . . . . 36
4.7 Number of con icts by number of UAVs . . . . . . . . . . . . . . . . . . . . . . 37
4.8 Number of crashes by number of UAVs . . . . . . . . . . . . . . . . . . . . . . . 37
4.9 Deviation ratio by number of UAVs . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.10 Trajectories of UAVs in one simulation in which a crash occurs. . . . . . . . . . 40
4.11 Average survival rate in a 500 m 500 m  eld [17] . . . . . . . . . . . . . . . . 41
4.12 Average survival rate in a 1000 m 1000 m  eld [17] . . . . . . . . . . . . . . . 41
4.13 Average survival rate of our approach . . . . . . . . . . . . . . . . . . . . . . . 42
vi
Chapter 1
Introduction
Unmanned Aerial Vehicles (UAVs) are aircraft with no human pilot on board. They
are either remotely controlled by human pilots or pre-programmed to  y autonomously. A
UAV could be a  xed-wing airplane, a helicopter, a robotic bird or any vehicle moving in the
air. Initially, UAVs were designed and used for military purposes such as reconnaissance and
attack missions. In recent con icts, UAVs executed numerous spying and combat missions.
Their growing capabilities and successes are drawing increasing attention for potential com-
mercial applications in agriculture, land surveying, and oil pipeline inspection among many
others.
However, there is one issue which keeps UAVs from spread commercial deployment:
the Federal Aviation Administration ( FAA) strictly requires that for UAVs to be inte-
grated into the national airspace, they must be at least as competent (capable of operating
safely) as an equivalent human pilot without cooperative communication (such as commands
from a human controller or information from neighboring aircraft) [15]. When UAVs  y
autonomously, their inability to reliably sense and avoid other aircraft are a main concern
and exclude them from commercial applications. UAVs must avoid collisions.
There are numerous existing approaches to solve the UAV collision avoidance problem.
For example, Park [32] applied the point of closest approach method to achieve UAV con-
 icts detection and collision resolution. Some research groups used grid-based approaches to
achieve collision avoidance: Tooren [40] adapted A algorithm to avoid dynamic obstacles.
The A (pronounced "A star") algorithm is a grid-based approach, and it was originally
1
designed for terrestrial robots that can speed up, slow down, stop, sharply turn, or even
back up along  xed obstacles. In this study, we will adapt the A algorithm for UAVs path
planning so that it is capable of avoiding other UAVs.
In this work, we assume that the UAVs  y at a constant speed, do not change altitude,
and turn by 22o per second at most. Constant speed and altitude optimize energy e ciency
and stealth. Although the A algorithm is frequently used to solve the UAVs path planning,
only a few researchers apply it to achieve collision avoidance. Those previous works using
the A algorithm for collision avoidance did not discuss much about the relation between
heuristics and environmental parameters (  eld size, number of UAVs, etc. ). We wonder:
How does the performance di er by manipulating the heuristic function of the A* algorithm
and environmental conditions in the UAVs collision avoidance problem?
In this study, we want to answer this question by performing simulations with several
scenarios. All of the data are simulated under C++ and Matlab programming environment.
As a result, we are able to determine the limitations for the A algorithm using di erent
heuristic functions. For example, we will show how far the UAVs have to deviate in order to
keep in the safety path, and how many UAVs in a certain  eld will cause unsolvable collision.
In this thesis, we  rst review the related works with di erent approaches. Our model will
then be proposed to demonstrate how do we solve the dynamic collision avoidance problem.
Next, we will perform several simulations in di erent scenarios to evaluate our approach.
Finally, we propose our conclusion and suggestion for the future work.
2
Chapter 2
Literature Review
Numerous approaches have been proposed to address collisions avoidance for UAVs. We
review the geometric, stochastic, linear programming , arti cial potential  elds(APF), and
grid-based approaches. For each approach, we review the representative method.
2.1 Geometric Approach
In this approach, each UAV is considered as a point mass, its future path can be pre-
dicted based on its most recent trajectory, current speed and bearing. A representative
algorithm is the Point of Closest approach (PCA)[32]. Given the predicted paths of all
UAVs, PCA method computes the mutual distances between UAVs. Should the distance
be smaller than some safety threshold distance, evading strategies are enacted to avoid the
collisions.
2.1.1 Free Flight
In 1991, International Civil Aviation Organization created the Future Air Navigation
System Panel. The concept of \user de ne trajectory" was proposed and became known as
\free  ight" [24] [4] by the mid-1990s. The concept of free  ight is to replace the current air
tra c management methods by the use of growing technology nowadays. The ultimate goal
of free  ight is not to use centralized control ( such as ground station), but automatically  y
in a distributed way using computer communication to ensure the Alert Zone of air  ights
will not be violated. Once the Alert Zone is violated, air tra c controllers will intervene to
assist in con ict avoidance to prevent the violation of Protected Airspace Zone. Fig. 2.1
3
illustrates the Alert Zone and Protected Airspace Zone. This concept motivated numerous
research group to develop autonomous con ict detection and resolution methods. In 1997,
Krozel and Peters proposed an economic model for con ict detection and resolution using
PCA method. [24]
Fig. 2.1: Illustration of free  ight protected and alert zones. [24]
2.1.2 Point of Closest Approach
Krozel and Peters [24] considered two UAVs  ying without sideslip which are going
to have an encounter with each other as shown in Fig. 2.2. In order to predict whether a
collision will happen or not, they use geometry method to calculate the minimum distance
of these two UAVs passing by each other. In other word, they use PCA method to get the
miss distance.
The miss distance vector ~r is de ned:
~rm = ^c (~r ^c) (2.1)
where ~r is the relative distance vector of UAV?B? with respect to UAV?A?, and ^c is the
unit vector in the direction of the relative velocity vector ~c:
4
Fig. 2.2: Illustration for Point of Closest Approach method. [32]
~c = ~VB ~VA (2.2)
By the de nition of miss distance vector ~r, we can naturally know that the miss vector
~r and the relative velocity vector ~c are orthogonal:
~rm ~c = 0 (2.3)
The relative motion from UAV?B? to UAV?A? will follow along the direction of ~c, and
after the time of closest approach  , the relative motion will be located at the vector location
~rm :
~rm = ~r +~c (2.4)
with Eq.2.3 and 2.4, we can calculate the time of closest approach  :
 =   ~c~c ~c (2.5)
5
In 1958, Morrel [30] used simply range divided by range rate as the predicted time-to-collision
criteria. The time of closest approach  di ers from Morrel?s criteria, the time of closest
approach is more reliable and e ective to judge weather a collision will occur or not. In the
example above, the altitude is  xed so that the UAVs can only  y in a horizontal plane.
Krozel and Peters? also described the full 3D con ict detection analysis was described in [23].
Park [32] indicated that from Eq. 2.5, the time of closest approach  will be a positive
value when two of UAVs are getting closer, and  will be negative when two of UAVs are
getting further. Based on this inference, they check the chance for the occurrence of con-
 icts only when  < 0. In order to determine are the UAVs in a con ict condition, they
set a safety threshold distance rsafe. When the magnitude of ~rm is smaller than the thresh-
old distance rsafe, there is a predicted con ict between two UAVs. As long as there is a
con ict, a con ict resolution maneuvering should be accomplished. We can intuitively know
which direction each UAV should choose to avoid con icts in Fig. 2.2 and solve this problem.
2.2 Stochastic Approach
In this approach, the collision avoidance problem is formulated as the optimal control of
a stochastic system. The Markov Decision Process (MDP) is a representative such approach
by Temizer, Kochenderfer, and Kaelbling [39].
2.2.1 Markov Decision Process
MDP is named after Russian mathematician Andrey Markov who is best known for his
e ort on theory of stochastic process. In 1950s, the concept of MDP began to be discussed [7].
After Howard [18] published his book Dynamic Programming and Markov Processes in 1960,
6
numerous research about MDP was spawned [33] [28] [19].
MDP is an extension of Markov Chain, it introduce additional concepts such as actions
(allowing choice) and rewards (giving motivation). MDP is a discrete stochastic dynamic
programming process where the state of the system changes randomly according to the cur-
rent state and action. An MDP is de ned as tuple (S;A;Pass0;Rass0; ), where S is the state
space, A is the action space. By taking action a from state s, there is a probability of
Pass0 to transit to state s0 and receiving reward ;Rass0. Finally,  2 [0;1] is the discount fac-
tor used to prioritize early rewards against future rewards and the value is typically close to 1.
MDP seeks the automatic generation of collision avoidance algorithms given models of
aircraft dynamics, sensor performance, and intruder behavior. By formulating the prob-
lem of collision avoidance as a Markov Decision Process for sensors that provide precise
localization of the intruder aircraft, or a Partially Observable Markov Decision Process
(POMDP) for sensors that have positional uncertainty or limited  eld-of-view constraints,
generic MDP/POMDP solvers can be used to generate avoidance strategies that optimize a
cost function that balances  ight-plan deviation with collision. However, the computational
time can be heavy. Moving to full three-dimensional motion in a discretized formulation will
take the size of the state space beyond the range of existing solvers. Other representations
for the state space and new types of solvers are currently investigated [39].
2.3 Linear Programming Approach
Linear programming is a mathematical method for the optimization of a linear objective
function. In 1939, Leonid Kantorovich [20] developed the  rst linear programming problem
to plan expenditures and returns during World War II. In 1990s, Bemporad [9] and Paul [42]
proposed the same idea that the linear programming problem can be expressed as linear
7
constraints upon a mixture of continuous and integer variables.
2.3.1 Mixed Integer Linear Programming
Here, the collision avoidance problem is formulated as a linear programming problem.
The Mixed Integer Linear Programming (MILP) is one representative technique to solve
the problem of UAV collision avoidance using linear programming. MILP has proven to
be e ective [34][37]. MILP provides a best outcome for a given mathematical model con-
taining a set of linear constraints. To begin, a number of constraints must be speci ed to
model the UAV?s motion dynamics; additionally, constraints related to collision avoidance
such as minimum separation distance must be provided. These constraints are then fed to
commercial MILP solvers such as APML and MATLAB, which develop a best path for the
UAV. Each aircraft?s path is optimized based on the expected paths of the other competing
but cooperative UAVs; therefore, an uncooperative UAV can wreak havoc on the carefully
planned system.
MILP is computationally expensive. If the optimal solution takes too much time, MILP
can solve the problem and provide less optimal solutions over a prescribed allocated time.
As the allocated time increases, MILP provides better and better optimal solutions. In order
to decrease the computational cost, a technique derived from model predictive control known
as receding horizon is used [25]. Using a receding horizon approach, the UAV path is broken
down into small chunks where the MILP model is solved for N time steps, which serve as
input for the next N time steps and so on until the process is  nished. While this approach
minimizes the computational burden, since the program is solved in smaller blocks, obsta-
cles outside one time block distance from the UAV will have no e ect on the path of the
UAV; therefore, when paths for the next time block need to be computed, the UAVs may be
too close to avoid collision. Thus, when using the MILP approach, the goal is to minimize
8
computation time while increasing the size of the time blocks used in computation.
2.4 Potential Fields Approach
This approach was proposed for the  rst time in 1986 by Khatib [22]. This method
assigns magnetic or electrical charges of the same sign to UAVs and the opposite charges to
destinations: based on physics laws, particles with the same charges will repel each other
while being attracted by the destinations (opposite charge). [14] [26]
2.4.1 Total Field
Sigurd and How[38] investigated the feasibility to apply potential  elds such that UAVs
do not necessarily need to know the positions of all other aircrafts. The repulsive force be-
tween magnetic  eld generated by each UAVs allow them to avoid each other spontaneously.
An additional magnetic sensor and local magnetic  eld generator are required on board in
this approach. Therefore, each UAV can be treated as a magnetic dipole. The magnetic  ux
density BjBj in the xy-plane around a magnetic dipole is shown in Fig. 2.3. By generating
local  eld, sensing total  eld, and subtracting own  eld, they are able to  nd a set of angles
where the UAV?s own  eld is orthogonal to the x-axis or y-axis in the UAVs reference frame;
these angles are shown in Fig. 2.4
9
Fig. 2.3: Magnetic  ux density around a magnetic dipole [38]
(a) (b)
Fig. 2.4: (a) Surrounding  eld along the x-axis (b) Surrounding  eld along the y-axis [38]
10
2.4.2 Force Field
Liu, Wang, and Dissanayakes [41] present research on arti cial force  elds in robot
collision avoidance. They solved the path  nding problem for an omnidirectional class of
vehicles. By modeling goal waypoints as positive charges and other robots in the project
space as negative charges, optimal routes were found by calculating a total force from the
attractive force of the robots towards their destination and repulsive force away from other
vehicles operating in the area. One particularly important innovation is the use of the
elliptical potential  elds, which results in less e ort for the robot to continue forward since
the arti cial  eld generated by a robot extends further into the space ahead of it. Another
important innovation includes the use of the expanding force  elds; as a robot moves closer
to its goal waypoint, the arti cial  eld increases in size to ward o other robots in the area.
2.5 Grid-based Approach
As the name suggests, grid-based approach discretized the air by dividing it into discrete
square or cubic cells of uniform size. The collection of cells are represented by a weighted
graph in which vertices are the cells and the edges connect adjacent cells. On a plane, a
vertex has eight edges: orthogonal (north, west, south, and east) and diagonal (northwest,
southeast, south east, and northeast). Weights of high (or in nite value) on the edges can
be used indicate an obstacle. Such a graph representation allows the use of short path
algorithms such as Dijkstra?s [10] or Bell-Ford [8] [13].
2.5.1 Search Trees Problem
In 1959, Dijkstra discussed the minimum cost problems in connection with graphs. Con-
sidering n nodes, and there are branches connecting them with given lengths. Assuming one
node has at least one path to any other nodes,the path with minimum length between given
two nodes P and Q can be found by the following step:
11
1) Create three sets for the branches:I;II;III, and three sets for the nodes:A;B;C.
2) Place all the nodes in set C, and all branches in set III.
3) Move the starting node P to the set A, and set this node as current node.
4) Consider all branches r connecting the current node with nodesR. If the ith node Ri
belongs to set B, we consider does the use of branch ri provides a shorter distance than
the use of corresponding branch in set II. If it does, branch ri replaces the branch in
set II. Otherwise, the branch ri is rejected and transfered to set III.
5) If the ith node Ri does not belong to set B, we transfer the nodes Ri to the set B and
the branch ri to the set II.
6) If we follow the rule that we must use branches from set I and one branch from set II,
then every node in set B can connect to node P in only one way. Therefore, we can
compute the distance between node P with each node in set B. We transfer the node
with minimum distance from P to set A and the corresponding branch to set I. Make
this node as current node.
7) Return to step 4 and repeat the process until node Q is transfered to set I, then the
nodes in set A is the solution.
Dijkstra?s algorithm is capable to solve problems which can be reduced to the minimum
path  nding in a weighted graph. The graph does not necessarily need to assign the same
weight (length of a branch) for the branches. Moreover, the weight can vary with di erent
direction in which it is traversed. One restriction for Dijkstra?s algorithm is that it does
not work on a graph with negative weights. An algorithm with similar structure named
Bell-Ford algorithm [8] [13] is considered when there are negative weights in graphs.
Although Dijkstra?s algorithm has great capability to solve the minimum cost problem,
given the large number of nodes, the computation can get prohibitive. A few years later,
12
a generalization of Dijkstra?s algorithm was proposed to reduce the nodes that must be
explored.
2.5.2 Heuristics
In 1966, the research for the actual construction of a mobile robot nicknamed \Shakey" [1]
was conducted by SRI International (then Stanford Research Institute). Fig. 2.5 is a picture
of Shakey, there is a television camera onboard so that Shakey is capable to capture images
around it to detect those obstacles. The method for the navigation is to plan a sequence of
way points so that Shakey can follow these way points from one place to another.
Fig. 2.5: Shakey, the mobile robot system. 1966 through 1972 [1](Photograph courtesy of
SRI International.)
Shakey stored the positions of obstacles and itself in a \grid model" as shown in Fig. 2.6.
They used smaller cells near the obstacles in order to describe positions more accurately.
13
Nilsson, a member of Shakey?s research group, stated \This could be one of the  rst ap-
plication of adaptive cell decomposition in robot motion planning and is now a commonly
used technique." [31]. Shakey?s navigation problems can be reduced to a search problem in
a weighted graph, and numerous approaches for searching graphs were proposed during that
period including Dijkstra?s algorithm and Bell-Ford algorithm we mentioned before. These
approaches were capable of solving Shakey?s navigation problem and guaranteed the shortest
path. However, they could be ine cient for the computation with complicated problem such
as large number of nodes.
Fig. 2.6: Illustration of Shakey?s navigation problem[31](Original image from SRI Interna-
tional)
Inspired by Doran and Michie?s Experiments with the Graph Traverser program [11],
where they de ne heuristic functions to assign costs based on the estimated di culty to
reach the destination to deal with the eight-piece, sliding-tile puzzle problem, Nilsson [31]
14
reasoned that for a mobile robot navigation problem, a good heuristic function to estimate
di culty to reach the destination (before actually searching nodes) could be the airline
distance, which means the length of path ignoring any intervening obstacles to reach the
destination. Nilsson suggested to use this heuristic function as the weights of corresponding
nodes in the search tree.
Raphael, the director of Shakey at that time, provide an improvement for Nilsson?s idea
for Shakey?s navigation problem. Instead of only using the heuristic function as the weights
of corresponding nodes in the search tree, Raphael suggested to combine the heuristic func-
tion Nilsson proposed with the distance robot already traveled so far from the initial position
as the total weight of nodes. [36]
Hart, another member of Nilsson and Raphael?s group at SRI, considered Nilsson and
Raphael?s algorithm, and indicated that if the remaining distance the heuristic function es-
timated was never larger than the actual remaining distance, then the path their algorithm
 nd would be the optimal solution in this problem. Moreover, Hart believed their algorithm
would be the most e cient procedures in the search tree problem comparing with other
existing approaches that also guaranteed to  nd the optimal solution.
2.5.3 A Algorithm
In 1968, Hart, Nilsson, and Raphael [16] proposed a proven optimization of Dijkstra?s
algorithm dubbed A (after multiple earlier version A1, A2, etc)). A is an informed search
algorithm: it  rst searches the routes that appear to most likely lead to the destination. For
this, A uses a distance-plus-cost heuristic to determine the order in which to visit potential
nodes on the route.A greatly improves the time of Dijkstra?s algorithm and works well for
path planning for robots navigating around  xed obstacles.
15
For collision avoidance for UAVs, other UAVs are the moving obstacles. Tooren, Heni,
Knoll, and Beck[40] adapted and implemented A for UAVs as a search over nodes of motion
primitives that are short trajectory segments. Each of these motion primitives is chosen such
that it generates a  yable, smooth trajectory valid for the current state and the performance
limits of the aircraft. Fig. 2.7 illustrates some expanded nodes resulting from typical motion
primitives with their [G / H] cost noted in the attached boxes where G is the cost from the
starting point to the current point and H is the perceived (heuristic) cost from the current
point to the destination. Note that for simplicity, not all possible segments are shown, and
the least cost path is drawn as a solid line. The set of possible elements includes typical
 ight elements such as linear segments, curve segments but also more complicated elements
like (3D) Dubins sets [12]. The computational time varies greatly as the possible airspace
changes. As the possible airspace grows, it is clear the computational complexity increases
greatly. On the other hand, if the airspace is broken into fewer, larger cells, there might not
be enough detail to plan e cient non-colliding paths.
Fig. 2.7: A path search around an obstacle.[40]
16
2.6 Conclusion
In a dynamic environment, the computational time is critical. The computational time
of A varies greatly as the possible airspace varies (overall  eld size and cell size). The
complexity of A can be reduced by designing a good heuristic function so that A has more
 exibility to adapt di erent scenarios. The advantage of A is that it can be  exible by
allowing di erent heuristic functions to handle di erent situations. A is a good candidate
to perform real time path planning.
17
Chapter 3
UAVs Collision Avoidance
Fig. 3.1: Easy Star, the Unmanned Aerial Vehicle
3.1 Easy Star
The approach we will propose in this chapter will be implemented on the UAV platform
named Easy Star (see Fig. 3.1). Easy Star is a  xed-wing UAV, consisting of the body,
a wing, a rudder, an elevator, a motor, and carving layout hosting the electronics such as
Arduino [2] on board. Where as the motor controls the speed of Easy Star, rubber, eleva-
tor, and wing control the  ying direction. Arduino on board is capable of transmitting and
receiving information with the ground station (such as a laptop) or other UAVs.
18
3.2 Con ict Detection
A con ict can be de ned as a predicted violation of a separation assurance standard.
Under this de nition, a con ict exists as long as two aircraft will encounter within the safety
distance at some time in the future [21]. In our approach, we predict the positions of UAVs
in the coming future and use these information to avoid con icts by applying them in the
heuristic function of A algorithm. Then, we can achieve intruder awareness.
3.2.1 Intruder Awareness
We call intruder awareness the estimated danger we consider in the heuristic function.
Fig. 3.2 illustrates for how to achieve this objective of intruder awareness.
First we consider the di erence of the x coordinates of the UAV and the intruder:
x01 = x1 x0 (3.1)
Where the sign of x12 tells whether the intruder is on the right or the left of the UAV. In
Fig. 3.2, we can see the sign of x01 is positive, so the intruder is on the right of the UAV.
Second , the velocity of UAVs can be calculated by di erentiating the movements. As
long as the velocity is known, the UAV bearing is also known. Then, we can tell whether the
intruder is approaching or leaving along the x-axis by checking the sign of x-axis velocity.
Finally, we multiple the relative x-axis position and velocity: if the product is negative, then
the intruder is approaching along the x-axis direction. In other words, the UAV is \in front
of" the intruder. Applying the same process on the y direction, we can tell from which y
direction the intruder is approaching.
19
Fig. 3.2: Illustration of intruder awareness.
Third , given the predicted positions of the UAV and n number of intruders, we are
able to estimate the danger in the future with the equation:
nX
i=1
j(Xi X0)j+j(Yi Y0)j (3.2)
The reason of using absolute value of x;y di erence instead of the actual distance is that it
makes more sense to the grid-based approach like A algorithm. Because every unit of the
x,y di erence can be treated as moving one grid. The intruder awareness will be applied in
the heuristic function which is discussed in section 3.3.3.
3.2.2 Con ict Determination
In order to detect con icts and advise the pilot to avoid potential collision, a Tra c
Alert and Collision Avoidance System (TCAS) [3] is commonly used in air tra c manage-
ment administration including FAA. A TCAS de ned di erent level of potential collision
20
zones that should be protected around aircraft as shown in Fig. 3.3. FAA required all com-
mercial turbine-powered transport aircraft with more than 30 passenger seats (or maximum
take o weight above 33,000 lb/15,000 kg) to equip TCAS II since 1993. In our case for
Easy Star, we refer to the de nition of TCAS and the distance that UAVs can reach within
35 seconds as a threshold distance to activate the collision avoidance function. In our simu-
lation, we assume the UAVs  y 5 meters per second so that the safety distance is 175 meters.
Fig. 3.3: Classi cation of protected zones, including Tra c Advisory Zone, Resolution Ad-
visory Zone, and Autonomous Avoidance Zone.
3.3 Collision Avoidance
Once the potential con ict is detected, we activate A algorithm to plan a safe path to
avoid intruders. Fig. 3.4 illustrates the architecture of the collision avoidance model. This
model includes the ArduPilot, the collision detection function, and the A algorithm. The
ArduPilot is an open source software that takes care of  ying the UAV: given a waypoint,
the ArduPilot  ies the AUV to it. Our team designed the software to upload in  ight new
waypoints to the ArduPilot.
The collision detection function continually monitors all UAVs to detect an imminent
con ict. Given the positions and the bearing of all UAVs, this function derives the velocities
21
Fig. 3.4: Collision avoidance architecture
of all UAVs and can predict an imminent con ict or a collision. If a con ict/collision is
predicted, the collision detection function activates A and provides to it the positions of
the UAVs who may collide. The future positions of all UAVs are continuously computed
35 seconds ahead. The 35 seconds correspond to the responding time proposed by TCAS.
However, the responding time can be modi ed based on the speed of UAVs.
When A starts, the collision detection function is stopped for 35 seconds. After 35
seconds, the collision detection function is reactivated again to update the positions and
bearings to eliminate the discrepancies between A algorithm and the ArduPilot. As long as
UAVs are too close (in the distance that UAVs can reach within 35 seconds), the A algorithm
remains active. Concurrently, the predicted positions of intruders( intruder awareness) are
fed to the A algorithm as the dynamic obstacles. Based on the most recent update, the A 
algorithm computes the new path to avoid collisions.
22
3.3.1 A algorithm
One feature of the A algorithm is the high  exibility of cost function. The equation of
total cost is
F = G+H (3.3)
where G is to the cost from the starting point to current (visited) one, and H is the heuristic
function estimating the cost from the current point to the destination. Therefore, the design
of G and H will determine the total cost F which can greatly a ect the path A  nds.
Fig. 3.5: Illustration of A path  nding algorithm.[27]
Once there is an obstacle that makes the current path cost more than other available
path, A will go back to the new node of lowest cost and expands its neighbors. After re-
peating this  nding process, A will  nally  nd a path that cost least once it expands to the
destination. As shown in Fig. 3.5, the A algorithm starts expanding nodes from A to the
23
goal B, and the grids with cross marks are the obstacles.
Each expanded grid contains the information: F at the top left, G at the bottom left,
H at the bottom right, and the arrow pointing its parent. In this example, the heuristic
function is the Manhattan method:
The Manhattan method [6] calculates the total vertical and horizontal distance between
the current cell and the destination, ignoring obstacles and discarding any diagonal move-
ment. In fact, this is what we used to estimate the danger in intruder awareness (section
3.2.1) .
3.3.2 Dangerous Grids
In order to deal with dynamic environment, we extended A algorithm with one ap-
proach we called dangerous grids as shown in Fig. 3.6.
The concept of dangerous grids is to predict the positions of UAVs which we already did
in the intruder awareness, and reconstruct the map in a discrete time system. In Fig. 3.6,
the UAV and intruder is approaching each other by the increasing time step. Those colored
grids indicate that the additional costs of heuristic function will be assigned in that time
step when the colored grid is expanded by A . Therefore, A is capable to construct the
map with dynamic obstacles and avoid those grids with higher cost.
3.3.3 Heuristics
The heuristic function H is critical to determine the performance of the A algorithm.
By using di erent heuristic functions, the result can be completely di erent. Fig. 3.7 shows
how the paths di er by using two di erent heuristic functions.
24
Fig. 3.6: The dangerous grids changes with the di erent time step.
In order to implement A algorithm in a UAVs path planning problem, we made some
modi cation. First, normally there should not be any obstacle in the sky so that every grid
is theoretically walkable in our problem. Instead, we have other aircrafts in the air as moving
obstacles in our problem. Second, except the Manhattan method, the heuristic function has
to be improved to assign the costs to those paths which are too close to intruders. Therefore,
in this study the cost estimation includes the Manhattan distance and intruder awareness.
This study introduces two di erent types of heuristic functions. The  rst is conservative
heuristics: it respects rules of the air [5] to ensure aircraft?s safety. The second is aggressive
heuristics: it takes risks to pass through intruders in order to arrive destination faster. Both
conservative and aggressive heuristic functions are based on the combination of Manhattan
method and intruders awareness.
25
(a) (b)
Fig. 3.7: (a) Path  nding using classic A method (b) Path  nding using fudge method [29]
In the conservative heuristic function, we assign di erent costs to follow some safety
rules. For example when a con ict(the distance that UAVs can reach within 6 seconds) is
detected, the path approaching the intruders should cost more than the path leaving the
intruders. Also, in order to reduce the potential con ict after the avoidance, we assign lower
cost for the path passing behind the intruders to encourage the UAVs to choose a safer path.
Recall that in the intruder awareness section, we used a mathematical method to judge a
intruder is approaching or leaving and which direction does it come from. Now, we can apply
this method to conservative heuristic function:
H(t) =
nX
i=1
 1(jX0 Xgj+jY0 Ygj) + 1(  j(Xi X0)j+j(Yi Y0)j) (3.4)
WherejX0 Xgj+jY0 Ygjis the Manhattan method,  ; and  are constants. The current
(visited) grid is X0;Y0, and the destination is Xg;Yg. Finally, Xi;Yi is the intruder. If the
intruder is approaching, assign more penalty for those grids moving toward the intruder by
increasing the value of  ; , in the heuristic function, then the cost will be larger. Oth-
erwise, if the intruder is approaching but the current grid is moving away from it, assign
26
smaller penalty. Other conditions are also considered by adjusting suitable  ; . No mat-
ter in what situation,  remains the same so that when the intruder is approaching, where
j(Xi X0)j+j(Yi Y0)j gets smaller, the total cost will get larger. The value of  should
be alway larger than  because Manhattan method contributes the remaining length of the
path, and we should weight it to assure A is searching toward to the destination. Otherwise,
the path may be trapped when there are too many intruders in the way to destination.
In the aggressive heuristic function, we try to  nd the path is most e cient and maybe
a little more dangerous. Therefore, we only consider the distance between UAVs to ensure
the minimum requirement of safety. The aggressive heuristic function
H(t) = 2 fieldsize 
nX
i=1
j(Xi X0)j+j(Yi Y0)j+ (jX0 Xgj+jY0 Ygj) (3.5)
Where X0 and Y0 is the position of our UAV,Xi and Yi are the positions of intruders. Simi-
larly, when the distance between UAVs is getting closer, the summation part in the equation
is getting smaller, and the cost function H(t) is getting larger. The cost of heuristic func-
tion increases when the value intruder awareness decreases. Therefore, intruder awareness
provides information about how far are the intruders and whether they are approaching or
leaving.
Note that for the conservative heuristic function, we consider every intruder indepen-
dently and compute the cost respecting to each intruder. Then, we sum up all the cost. In
this way, we carefully consider each intruder?s position and movement. For the aggressive
heuristic function, we consider all intruders at one time so that as long as the path is not
too close to the intruders, it is acceptable.
27
A is often implemented as a search over a grid space. However, this is not necessary
for A and in the case of con ict avoidance for aircraft it is actually more convenient to
implement it as a search over nodes of motion primitives, - namely, the short trajectory
segments [35]. We should not consider the grid space as the only way to implement A .
However, using a grid space is more convenient to program because a grid space describes
more easily the map, especially in the two-dimensional case. For example, when we use a
grid space to search over, we can easily treat one UAV as one grid so that as long as we make
sure the path does not pass through that grid, we can guarantee con ict avoidance. Other-
wise, when we use  oating points to describe the UAVs, we need to work more accurately
and consider the shape of UAVs to determine what points should be left to pass through.
28
Chapter 4
Simulation
In this chapter, we will investigate the performance of both conservative and aggressive
heuristic functions of A* algorithm in the UAVs collision avoidance problem. We will show
the simulation results and discuss the in uences by using di erent heuristics.
4.1 The Simulation Setup
We consider the following metrics to evaluate A ?s performance:
a) Deviation ratio = ActualDistanceMinimalAchievableDistance: The minimal achievable distance is
the length of the shortest path that UAVs can travel when there is no obstacle in their
way. In other words, the shortest path is the straight line between start point and
the destination. The actual distance means the total length of the path that the A*
algorithm proposes to avoid obstacles in the air.
b) Number of con icts. This is the number of pairs of planes within 6 grids. The way
we count the con icts is to see how long have the UAVs been within con ict distance(
6 grids). Therefore, if two UAVs keep  ying within 6 grids, the number of con icts
will keep counting with time until the con ict is over.
c) Number of crashes. This is the number of pairs of planes within thrice the wingspan
of a plane. In our simulation, we de ne there is a crash when two or more UAVs? paths
are in the same grid at the same time step. Once a crash occurs, the UAVs involved in
the crash are eliminated, and the simulation will continue with the remaining UAVs.
29
We assume that it takes the UAV one second to traverse a 5 m 5 m grid. By our def-
inition of con icts, a con ict occurs when two UAVs are within 6 seconds from each others.
Therefore, We have at least 3 seconds to avoid a collision.
To evaluate A , we consider di erent con gurations. A con guration consists of a  xed
number of UAVs (2, 4, 8, or 16) and the size of the  eld (500 m 500 m and 1000 m 1000 m).
We randomly create 100 di erent scenarios. Each scenario consists of four randomly picked
waypoints per UAV. Each UAV must visit these four waypoints in a predetermined order.
To generate random waypoints, we pick a random point in the  eld as the start point, then
we use a certain radius 50 meters and 7 random directions to create the next waypoint. In
this way, we can make sure that each UAV will travel at least 200 meters in the simulations.
Given the same scenario, we simulate it on di erent con guration (number of UAVs,  led
size) to evaluate A algorithm. We compare two di erent heuristic functions: conservative
heuristic function and aggressive heuristic function. The conservative heuristic function
assigns additional cost when the path of UAV cuts o intruders so that we expect the path
to be circuitous to keep intruders in distance. The aggressive heuristic function only consider
the length of path and the positions of intruders, so we expect it to try to  nd a feasible
path around the intruders in order to reach the destination faster.
4.2 Simulation in a 500 m 500 m  eld
As shown in Fig. 4.1:(a), the cumulative distribution function(CDF) describes the prob-
ability that the number of con icts is equal to or less than a certain value. For example, if
we consider a straight line that the number of con icts equals to 100, we can tell that the
probability of 100 con icts or less is 100% for 4 UAVs, about 96% for 8 UAVs, and only 1%
for 16 UAVs. Comparing this with Fig. 4.1:(b), the CDF are similar for 4 UAVs and 8 UAVs.
According to this observation, we consider that the abilities of avoiding con icts are almost
30
the same between these two heuristic functions when the number of UAVs is smaller than 8.
In the scenarios of 16 UAVs, we observe that aggressive heuristics encounter more con icts
than conservative heuristics if we compare the CDF when number of con icts equals to 200.
0 100 200 300 400 500 600 700 8000
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Conflicts
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(a) conservative heuristics
0 100 200 300 400 500 600 700 8000
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Conflicts
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(b) aggressive heuristics
Fig. 4.1: Cumulative density function(CDF) plot of con icts in a 500 m 500 m  eld
In our expectation, the deviation ratio of aggressive heuristic function should be smaller
than the conservative one since it is supposed to  nd a shorter path. In Fig. 4.2, we can
see that deviation ratios of aggressive heuristic function are approximately 1.5 times smaller
than the conservative one when  ying 4 UAVs or 8 UAVS. For the scenarios of 16 UAVs,
when the probability reaches to 99%, the deviation ratio equals to 3.5 while using the ag-
gressive heuristics and equals to 4.1 while using conservative heuristics. Comparing the
di erence between  ying 8 UAVs with  ying 16 UAVs, when we  y UAVs in a  eld with
higher density ( 16UAVs500 m 500 m  eld ), the advantage of aggressive heuristics with smaller
31
1 1.5 2 2.5 3 3.5 4 4.50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Deviation Ratio
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(a) conservative heuristics
1 1.5 2 2.5 3 3.5 4 4.50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Deviation Ratio
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(b) aggressive heuristics
Fig. 4.2: CDF plot of deviation ratio in a 500 m 500 m  eld
deviation ratio becomes unapparent.
Although the aggressive heuristics has higher probability to encounter con icts, it usu-
ally have higher capability to  nd a shorter path. Because of the way we count con icts is
to see how long have UAVs been within con ict distance, it is possible for the aggressive
heuristics to reduce the con icts by shorten UAVs?  ight duration in the air. Also, we ob-
serve in Fig. 4.2 that the average deviation ratio of aggressive heuristics is smaller in this
con guration. However, in the scenarios of  ying 8 UAVs, the maximum deviation ratio of
aggressive heuristics is almost 1.5 times the ratio of conservative heuristics, this implies that
in some extreme cases the path aggressive heuristic found is somehow much more ine cient
than the path conservative heuristics found.We will make a further discussion for the reasons
32
causing this unexpected phenomenon at the later part of this chapter.
0 1 2 3 4 5 6 70
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Crash
Probability
Empirical CDF
(a) conservative heuristics
0 1 2 3 4 5 6 70
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Crash
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(b) aggressive heuristics
Fig. 4.3: CDF plot of crash in a 500 m 500 m  eld
Fig. 4.3 shows that the ability of avoiding crash is similar to the ability of avoiding
con icts. When the number of UAVs is smaller than 8, the crashes are lower than 4 in 100
simulations. Actually, over half of the simulations result with no crash. However, when the
number of UAVs is larger than 8, the crash increases gradually. In the worst case there are
only 3 UAVs survived. The performances of conservative heuristics and aggressive heuristics
are similar when the number of UAVs is smaller than 8. Once the number of UAVs is over
8, the aggressive heuristics tends to cause more crashes in this con guration.
33
4.3 Simulation in a 1000 m 1000 m  eld
In this section, we use a square  eld with 200 200 grids to simulate 2, 4, 8, or 16 UAVs
 y at the same time. As a result, the performance of avoiding con icts is better than the
simulation in a 500 m 500 m  eld, especially when the number of UAVs is 16 as shown in
Fig. 4.4. When  ying with 16 UAVs, the con icts are greatly reduced in this con guration
no matter which heuristics we use because the bigger  eld provides UAVs more spaces to
avoid con icts.
0 50 100 150 200 2500
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Conflicts
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(a) conservative heuristics
0 50 100 150 200 2500
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Conflicts
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(b) aggressive heuristics
Fig. 4.4: CDF plot of con icts in a 1000 m 1000 m  eld
The performance of deviation ratio is also better in the simulation in a 500 m 500 m
 eld as shown in Fig. 4.5, except the scenario of 8 UAVs using aggressive heuristics. In our
expectation, the aggressive heuristics should propose a path with lower deviation ratio, in
this scenario we can see that even though the average deviation ratio is still smaller than
34
conservative heuristics, in some cases the deviation ratio is as large as 6. Note that in the
simulation of 500 m 500 m  eld, the deviation ratio of aggressive heuristics also has some
unexpected behavior in the scenarios of 1 UAVs. This phenomenon raises one question: Why
does this occur exclusively in the scenarios of 8 UAVs? To answer this, we need to review
the relation between number of UAVs and the evaluation metrics. In the following section,
we will discuss this issue with some  gures to support our argument.
1 2 3 4 5 6 70
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Deviation Ratio
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(a) conservative heuristics
1 2 3 4 5 6 70
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Deviation Ratio
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(b) aggressive heuristics
Fig. 4.5: CDF plot of deviation ratio in a 1000 m 1000 m  eld
The number of crashes in a 1000 m 1000 m  eld does not change a lot in the scenarios
of 4 or 8 UAVs. However, in the case of 16 UAVs, both heuristics achieve a much smaller
number of crashes as shown in Fig. 4.6 because the UAVs can avoid each other more easily
in a bigger  eld. Also, it is not obvious but the crashes of aggressive heuristics are slightly
more than for conservative heuristics as we expected.
35
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Crash
Probability
Empirical CDF
 
 
4UVs8UAVs
16UAVs
(a) conservative heuristics
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Crash
Probability
Empirical CDF
 
 
4UAVs8UAVs
16UAVs
(b) aggressive heuristics
Fig. 4.6: CDF plot of crash in a 1000 m 1000 m  eld
4.4 Relation Between Number of UAVs and Metrics
In the scenario of 8 UAVs, we found that the aggressive heuristics may fail in some
extreme cases. In order to con rm our thought, we review the relation between number of
UAVs and metrics to compare these two heuristics as shown in Fig. 4.7 and Fig. 4.8. After
the number of UAVs is larger than 8, the number of con icts and crashes using aggressive
heuristics increase considerably. No matter what size of the  eld is, we can observe that there
are more con icts and crashes by using aggressive heuristics. However, this still doesn?t an-
swer why the extreme cases only occur in the scenarios of 8 UAVs. We need to review the
relation between number of UAVs and the deviation ratio.
The deviation ratio have interesting changes when the number of UAVs increase as
shown in Fig. 4.9. The ratios of conservative heuristics does not have signi cant di erence,
and the ratios of aggressive heuristics have trends to decrease from 2 UAVs to 8 UAVs. The
36
2 4 8 160
0.5
1
1.5
2
2.5
3
3.5
4x 104
Number of UAVs (logscale to base 2)
Number of Conflicts
 
 Conservative 500x500
Conservative 1000x1000Aggressive 500x500
Aggressive 1000x1000
Fig. 4.7: Number of con icts by number of UAVs
2 4 8 160
100
200
300
400
500
600
700
Number of UAVs(logscale to base 2)
Number of Crashes
 
 
Conservative 1000x1000Conservative 500x500
Aggressive 500x500Aggressive 1000x1000
Fig. 4.8: Number of crashes by number of UAVs
reason may be the A over-reacts to the intruder because the aggressive heuristics assign
higher costs to the path getting closer to the intruders. When there is only one intruder,
only the direction toward to the intruder has higher costs so that the UAV may deviate too
much. When there are more intruders from more than one direction, the deviation ratio
becomes smaller because the A does not over-react to one certain direction.
Fig. 4.9 also presents the maximum and minimum deviation ratio in 100 simulations.
We can see that the deviation ratio of aggressive heuristics does not change much for 2
or 4 UAVs. The scenarios with higher deviation ratio is usually due to the extreme cases.
Therefore, the extreme cases with 2 or 4 UAVs may not have signi cant in uences on the
aggressive heuristics because they are more capable of  nding feasible path when the  eld is
37
Fig. 4.9: Deviation ratio by number of UAVs
sparse.
When the number of UAVs is smaller than 8, aggressive heuristics always have lower
deviation ratio. However, in the scenario of 16 UAVs, the ratio of aggressive heuristic be-
comes close to the ratio of conservative heuristics whether in a 500 m 500 m  eld or
1000 m 1000 m  eld. As a result, the aggressive heuristics lose its competitiveness in
the scenarios of 16 UAVs. Both performances of number of con icts and deviation ratio
are worse than conservative heuristics. This raises another question: Why does aggressive
heuristics fail in the scenarios of 16 UAVs?
Before answering this question, we have to discuss the previous issue about the extreme
cases in the scenarios of 8 UAVs. From Fig. 4.9, 8 UAVs is a breaking point while the de-
viation ratio of aggressive heuristics increases. Thus the extreme cases in the scenarios of 8
UAVs may be treated as a portent of aggressive heuristics? poor performance in the scenarios
of 16 UAVs. The reason of the exclusive occurrence with high deviation ratio in scenarios
of 8 UAVs relates to the number of crashes. From Fig. 4.8, the crashes are much more in
scenarios of 16 UAVs so that in these scenarios the UAVs don?t even have a chance to avoid
collision but crash. In the scenarios of 8 UAVs, it happens to have enough space for UAVs
38
to avoid each other even with a huge deviation in some extreme cases. This explanation also
implies the answer for the second question.
The aggressive heuristics fails in the scenarios of 16 UAVs because there is not enough
space for collision avoidance. Note that the aggressive heuristics only consider the positions
of intruders, it does not have the strategy like rules in the air [5] to avoid them. Therefore,
when the air is crowed by too many UAVs, the aggressive heuristics loses its ability to plan
a better path either by avoiding collision or by moving to the destination. It not only results
in more con icts and crashes, but also increases the deviation ratio.
4.5 Extreme cases for UAVs collision avoidance
After reviewing numerous simulations, we found some extreme cases that the UAVs may
su er in  nding feasible path. By investigating these cases, we may be able to  nd some
boundaries or limitations for the evaluation metrics of the UAVs.
One of the tough situations for collision avoidance is UAVs  ying in parallel lines. In
this case the path of UAV in the middle will be blocked by the other two UAVs from both
sides. In general, the A algorithm can handle this situation by assigning di erent costs for
left turn and right turn. However, in the example of Fig. 4.10, there are three UAVs parallel
with each other at the beginning. Also, the initial position of the UAVs at the top are close
to the boundary of the  eld so that there is no enough space for them to avoid each other.
Moreover, the UAV from right also goes to the same line in order to avoid the UAV at the
bottom. Even though the UAVs enter the same line at the top at di erent times, some of
them fail to exit the line in time so that the crash occurs eventually.
39
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
Fig. 4.10: Trajectories of UAVs in one simulation in which a crash occurs.
4.6 Comparison with Other Algorithms
In this chapter, we presented simulations with di erent numbers of UAVs and sizes of
the  eld. Now, we want to compare our approach with other algorithms. In James? work [17],
he compared the performances between three di erent algorithm: Mixed Integer Linear Pro-
gramming (MILP), Arti cial Potential Field (APF), and Dynamic Sparse A Search (DSAS).
Here, we select our algorithm with highest survival rate to compare with James? result as
shown in Fig. 4.11 and Fig. 4.12.
40
Fig. 4.11: Average survival rate in a 500 m 500 m  eld [17]
Fig. 4.12: Average survival rate in a 1000 m 1000 m  eld [17]
Notes that the A in Fig. 4.11 and Fig. 4.12 is DSAS, and the Conservative A is the
algorithm we use in this study. The survival rate of our approach can be calculated from
Fig. 4.8 as shown in Fig. 4.13. Considering the survival rate, the conservative heuristic has a
better result in most cases. In Comparison, for the scenarios with 16 UAVs in a 500 m 500 m
 eld, the survival rate of conservative heuristic is slightly higher than the MILP which is
the best result in Fig. 4.11. For the scenarios in a 1000 m 1000 m  eld, the survival
rates of both aggressive and conservative heuristics are larger than 90% which is similar
to the performance of the A in Fig. 4.12. Moreover, both MILP and APF have obvious
41
strength and weakness. For instance, the APF has the highest survival rate in the scenarios
on a  eld with lower density. However, the survival rate drops greatly in the scenario on a
500 m 500 m  eld when the number of UAVs is larger than 16. Therefore, even though
our approach does not have 100% survival rate in most cases, it is still competitive when
number of UAVs is smaller than 16 because it provides stably good survival rate under
various con gurations.
2 4 8 16 320%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Number of UAVs
Survival Rate
 
 
Aggressive 1000m X 1000mAggressive 500m X 500m
Conservative 500m X 500mConservative 1000m X 1000m
Fig. 4.13: Average survival rate of our approach
42
Chapter 5
Conclusion
In order to enable UAVs to  y autonomously, a reliable collision avoidance system is
necessary. In Chapter 2, we reviewed several representative approaches to solve the UAV col-
lision avoidance problem. Some of them have weaknesses such as computationally expensive
algorithm [39], requirement of accurate sensor[24], requirement of additional equipment[38].
Then, we concluded that A is  exible by allowing di erent heuristic functions to handle
di erent situations so that we can modify the original A to deal with dynamic obstacles.
Therefore, A is a good candidate to perform the real time path planning.
Heuristics
Our main strategy of conservative heuristics is \do not pass through in front of the intruder".
This strategy can at least avoid the imminent approach of other intruders. If we consider
more situations of con icts, the heuristics can possibly be improved. For example, we can
consider the situation of parallel  ying, instead of solving this situation, we can try to assign
additional costs to prevent the occurrence of parallel  ying. However, every time we add a
new heuristic, we have to adjust the proportion of cost between path length ( Manhattan
method and safety ( conservative or aggressive heuristics). In order to keep the safety and
path length in an acceptable range, we choose a suitable proportion which is about 5 : 1 for
conservative heuristics and about 1 : 1 for aggressive heuristics.
Future Works
According to the result of our study, we believe using two alternative heuristic functions in
the A algorithm could achieve the best performance. Since aggressive heuristics work well
43
when the number of UAVs is smaller than 8, we should use it for lower density condition.
Once the number of UAVs is larger than 8, we can switch it to conservative heuristics to
ensure the safety. We can also add more heuristics to consider a more complicated scenarios.
However, as we mentioned above, we should be aware of the proportion between di erent
heuristics while adding a new one.
Bene ts to Robotics
The simulation result shows that the collision avoidance using A is reliable when the den-
sity(number of UAVs over the area of the  eld) is less than 8 UAVs/1,000,000 m2. The
relation between density and the performance of A may not be linear because  ying more
UAVs at the same time requires more complicated computations for their paths. This study
investigated the application of A algorithm for path planning in a dynamic environment,
and this is a common issue for mobile robots. Therefore, our study of A algorithm can be
usefully adapted for other mobile robots.
44
References
[1] Online copies of SRI?s proposals for the automaton project, subsequent progress reports,
and related papers can be found at http://www.ai.sri.com/shakey/.
[2] Main site of Arduino team http://arduino.cc/en/.
[3] Introduction to TCAS II Version 7.1 http://www.faa.gov/documentLibrary/media/
Advisory_Circular/TCAS%20II%20V7.1%20Intro%20booklet.pdf,.
[4] Final report of rtca task force 3, free  ight implementation, November 1994.
[5] ICAO Annex 2. Rules of the air, 2006.
[6] Philippe Ballard and Fran cois Vacherand. The manhattan method: A fast cartesian
elevation map reconstruction from range data. In ICRA (3), pages 143{148, 1993.
[7] Richard Bellman. A markovian decision process. Indiana Univ. Math. J., 6:679{684,
1957.
[8] Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87{
90, 1958.
[9] A. Bemporad and M. Morari. Control of systems integrating logic, dynamics, and
constraints. Automatica, 35(3):407{427, March 1999.
[10] Edsger. W. Dijkstra. A note on two problems in connexion with graphs. Numerische
Mathematik, 1:269{271, 1959.
[11] J. E. Doran and D. Michie. Experiments with the graph traverser program. Proceed-
ings of the Royal Society of London. Series A, Mathematical and Physical Sciences,
294(1437):pp. 235{259, 1966.
[12] L. E. Dubins. On curves of minimal length with a constraint on average curvature,
and with prescribed initial and terminal positions and tangents. American Journal of
Mathematics, 79:497{516, 1957.
[13] L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
[14] Veysel Gazi and Kevin M. Passino. Stability analysis of swarms. IEEE Transactions
on Automatic Control, 48:692{697, 2003.
45
[15] Christopher M Geyer, Sanjiv Singh, and Lyle J. Chamberlain. Avoiding collisions be-
tween aircraft: State of the art and requirements for uavs operating in civilian airspace.
Technical Report CMU-RI-TR-08-03, Robotics Institute, Pittsburgh, PA, March 2008.
[16] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination
of minimum cost paths, 1968.
[17] James Holt. Comparison of aerial collision avoidance algorithms in a simulated envi-
ronment, 2012.
[18] R.A. Howard. Dynamic programming and Markov processes. Technology Press of Mas-
sachusetts Institute of Technology, 1960.
[19] Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and
acting in partially observable stochastic domains. ARTIFICIAL INTELLIGENCE,
101:99{134, 1998.
[20] L.V. Kantorovich. A new method of solving some classes of extremal problems, 1940.
[21] III Kelly, W.E. Con ict detection and alerting for separation assurance systems. In
Digital Avionics Systems Conference, 1999. Proceedings. 18th, volume 2, pages 6.D.1{1
{6.D.1{8 vol.2, 1999.
[22] O. Khatib. Real-time obstacle avoidance for manipulators and mobile robots. The
International Journal of Robotics Research, 5(1):90{98, Spring 1986.
[23] J. Krozel and M. Peters. Con ict Detection and Resolution for Free Flight. 1997.
[24] J. Krozel and M. Peters. Strategic con ict detection and resolution for free  ight. In
Decision and Control, 1997., Proceedings of the 36th IEEE Conference on, volume 2,
pages 1822 {1828 vol.2, dec 1997.
[25] W.H. Kwon, A.M. Bruckstein, and T. Kailath. Stabilizing state-feedback design via the
moving horizon method, 1983.
[26] N.E. Leonard and E. Fiorelli. Virtual leaders, arti cial potentials and coordinated con-
trol of groups. In Decision and Control, 2001. Proceedings of the 40th IEEE Conference
on, volume 3, pages 2968 {2973 vol.3, 2001.
[27] Patrick Lester. A* path nding for beginners. http://www.policyalmanac.org/games/
aStarTutorial.htm, 2005. This is an electronic document. Date of publication: [Date
unavailable]. Date retrieved: July 22, 2011. Date last modi ed: July 18, 2005.
[28] Michael L. Littman, Thomas L. Dean, and Leslie P. Kaelbling. On the complexity of
solving Markov decision problems. In Proceedings of the Eleventh Annual Conference
on Uncertainty in Arti cial Intelligence (UAI{95), pages 394{402, Montreal, Qu ebec,
Canada, 1995.
46
[29] James Macgill. A* demonstration. http://www.vision.ee.ethz.ch/~cvcourse/
astar/AStar.html, 1999. This is an electronic document. Date of publication: [Date
unavailable]. Date retrieved: Oct 11, 2011. Last Updated January 18 1999.
[30] J. S. Morrel. The mathematics of collision avoidance in the air. journal of navigation.
11:18{28, 1958.
[31] N.J. Nilsson. The quest for arti cial intelligence: a history of ideas and achievements.
Cambridge University Press, 2010.
[32] J W Park, H D Oh, and M J Tahk. Uav collision avoidance based on geometric approach.
2008 Proceedings of Sice Annual Conference Vols 17, pages 2039{2043 3382, 2008.
[33] M.L. Puterman. Markov decision processes: discrete stochastic dynamic programming.
Wiley series in probability and mathematical statistics: Applied probability and statis-
tics. John Wiley & Sons, 1994.
[34] A. Richards and J.P. How. Aircraft trajectory planning with collision avoidance using
mixed integer linear programming. In Proceedings of American Control Conference,
volume 3, pages 1936{1941, 2002.
[35] N.D. Richards, M. Sharma, and D.G. Ward. A hybrid a*/automation approach to
on-line path planning with obstacle avoidance, 2004.
[36] C. A. Rosen and N. J. Nilsson. Application of intelligent automata to reconnaissance.
Technical report, Stanford Research Institute, November 1966. Project 5953 Interim
Report 1 From the Nilsson archives SHAKEY papers.
[37] Tom Schouwenaars, Bart DeMoor, Eric Feron, and Jonathan How. Mixed integer pro-
gramming for multi-vehicle path planning. In In European Control Conference 2001,
pages 2603{2608, 2001.
[38] Karin Sigurd and Jonathan How. Uav trajectory design using total  eld collision avoid-
ance, 2003.
[39] Selim Temizer, Mykel J. Kochenderfer, Leslie P. Kaelbling, Tomas Lozano-P erez, and
James K. Kuchar. Collision avoidance for unmanned aircraft using Markov decision
processes. In AIAA Guidance, Navigation, and Control Conference, Toronto, Canada,
2010.
[40] J. van Tooren, M. Heni, A. Knoll, and J. Beck. Development of an autonomous avoidance
algorithm for uavs in general airspace, 2007.
[41] Dalong Wang, Dikai Liu, and Gamini Dissanayake. A variable speed force  eld method
for multi-robot collaboration. In IROS, pages 2697{2702, 2006.
[42] H. Paul Williams and Sally C. Brailsford. Computational logic and integer programming,
pages 249{281. Oxford University Press, Inc., New York, NY, USA, 1996.
47