Aerospace and Electronic Systems - October 2018 - 40

Feature Article:

DOI. No. 10.1109/MAES.2018.170116

Performance Comparison of Particle Swarm
Optimization and Cuckoo Search for Online Route
Planning
Germán David Góez-Sánchez, Instituto Tecnológico Metropolitano, Medellín,
Colombia
Jorge Alberto Jaramillo-Garzón, Universidad de Caldas, Manizales, Colombia
Ricardo Andrés Velásquez, Universidad de Antioquia, Medellín, Colombia

INTRODUCTION
The popularity of unmanned aerial vehicles (UAV) has been constantly increasing during the last years. After being used as war
tools by armies around the world, UAVs started being used in multiple civil applications. In the near future, hundreds or even thousands of UAVs will share the airspace with civil and commercial
aviation [1]. Hence, UAVs become a new risk factor to consider
in aerial security [2]. In this context, the need for researching and
developing new intelligent systems capable of reducing the risks
is justified. These intelligent systems must be able to optimize and
update their flight trajectories to avoid collisions with buildings,
mountains, or other airships. Therefore, the route planning method
has real-time requirements. It must obtain the UAV orientation in
real time, not only to reach the target but also to avoid collisions.
The problem increases when the environment changes dynamically or when there is not a predefined flight route to follow [3].
A flight route is a set of geographic coordinates that an airship
follows from origin to destination. The route planning method, or
planner for short, is in charge of finding such a set of coordinates.
In general, to travel from a departure coordinate until reaching a
destination coordinate, an unmanned aircraft could follow an infinite number of different routes. The problem of selecting the best
route to follow requires the consideration of flight length, fuel
consumption, security protocols, weather conditions, etc. For this
purpose, the method must consider a restriction set determined by
Authors' current addresses: G. Góez Sánchez, Grupo de Investigación AEyCC, Instituto Tecnológico Metropolitano, Calle
73 No. 76A - 354, Vía al Volador, Medellín, Antioquia, 050035
Colombia, E-mail: (davidgoez@hotmail.com). J. A. JaramilloGarzón, Universidead de Caldas, Sede Principal Calle 65 No
26-10, Manizales, 512120 Colombia. R. A. Velásquez, Universidada de Antioquia, Recepción de correspondencia: calle 70
No. 52 - 21, Medellin, Antioquia, 050035 Colombia.
Manuscript received June 7, 2017, revised November 5, 2017,
January 5, 2018, and ready for publication January 16, 2018.
Review handled by G. Fasano.
0885/8985/18/$26.00 © 2018 IEEE
40

the environment and the particular mission followed by the UAV
[4], [5].
There are two classes of route planning methods: the first class
does the planning before the flight starts, and the second class
plans the flight while it occurs [6], [7]. The former class is known
as offline route planning. The planners in this class are used on
commercial and civil aviation where flight routes are established,
and any deviation of the original flight plan must be approved by
an air controller. However, when the flight environment is partially
or completely unknown, because of lack of information or due to
dynamic changes in the environment, the offline planners' efficacy
is limited.
Typically, the most used methods for the planning of offline
routes are those based on graphs. A graph is a finite number of
nodes generating a connection matrix among the nodes. This allows the identification of paths that join a departure node and a destination node. This concept generates techniques looking to solve
the problem of the travel agent: finding the closest route among
two cities without going through already visited places or paths.
The algorithms based on graphs are widely used when planning
optimal routes looking for the shortest distance and, from these
planning techniques, it is possible to identify methods or behaviors
that shape and give identity to the algorithm [8]. These methods
are classified in nondirected graphs, graphs directed towards a
destination node, and techniques that join the graphs with a heuristic component. It is necessary to know the work environment,
the topography, including all obstacles in the route, before planning routes using graph techniques. It is also necessary to make a
preprocessing stage to generate adjacency matrixes [9]. This is the
reason why route planning using graph techniques is commonly
used as an offline planning method to obtain a reference route.
In [10] a method is proposed based on graphs using the Dijkstra
algorithm in a three-dimensional (3D) environment, or as the authors name it, "Dijkstra Algorithm for Fixed-Wing UAV Motion
Planning Based on Terrain Elevation." The Dijkstra algorithm, also
known as the minimum path algorithm, explores all paths from the
departure vertex leading to the destination vertex, stopping when it
finds the shortest route between the two of them. In robotics, this

IEEE A&E SYSTEMS MAGAZINE

OCTOBER 2018

Aerospace and Electronic Systems - October 2018

Table of Contents for the Digital Edition of Aerospace and Electronic Systems - October 2018