IEEE - Aerospace and Electronic Systems - May 2020 - 36

Feature Article:

DOI. No. 10.1109/MAES.2020.2978959

UAVs Formation Approach Using Fast Marching
Square Methods
C. A. Monje, S. Garrido, L. Moreno, C. Balaguer,
Carlos III University of Madrid

INTRODUCTION
Multiagent systems improve the performance, flexibility, and
robustness of the mission [1], including the common applications of exploration [2], search and rescue [3], and surveillance [4], [5], among others. The formation problem requires
us to address important research topics, such as modeling and
control of agents [6], collision avoidance [7], mapping and
state estimation [8], and formation control and planning [9].
Regarding formation control and planning, the main
problem is to provide a group of coordinated agents to
perform specific tasks while keeping certain geometric
configurations. The coordination of the agents is key
research topic. When the operation is performed in limited
spaces or for collaborative tasks, the movements of the
agents have to be planned and coordinated efficiently. As
well, a computationally fast solution is also required so
that the travel speed can be maintained.
There exist several strategies that describe how to control the evolution of a formation. For instance, the multiagent
coordination problem is studied in Ogren et al. [10] under
the framework of Lyapunov control. Other approaches are
based on potential fields, which are combined in order to get
the desired behavior of the formation [11]. In other behavior-based approaches [12], each agent has basic primitive
actions that generate the desired behaviors in response
to sensory inputs. A common solution in the leader-followers approach, is the model predictive controller [13],
which was recently introduced for holonomic robots [14].
Another interesting approach is that by Olfati-Saber on
flocking for multiagent dynamic systems [15], subsequently

Authors' current addresses: C. A. Monje, S. Garrido,
L. Moreno, C. Balaguer, RoboticsLab, Department of
Systems and Automation, Carlos III University of Madrid,
Madrid 28903, Spain (e-mail: sgarrido@ing.uc3m.es).
Manuscript received July 26, 2019, revised November 20,
2019; accepted February 24, 2020, and ready for
publication March 4, 2020.
Review handled by Giancarmine Fasano.
0885-8985/20/$26.00 ß 2020 IEEE
36

adapted by Iovino et al. [16] for UAV swarming with obstacle avoidance capability. This method is based on collective
potentials between alpha agents that are flock members, beta
agents that are used to represent obstacles, and gamma
agents that represent partial objectives.
The main drawbacks of the methods cited before are,
among others, the mathematical complexity needed to
obtain satisfactory results and the existence of local minima during the execution of the algorithms. As demonstrated in Gomez et al. [17], the fast marching square
(FM2 ) approach shows a robust performance when it
comes to these two issues. This is why we have taken a
step toward its application to UAVs formations.
In this article, an approach is presented for the calculation of the trajectories that the UAVs of a formation must
follow when moving toward an objective, based on a
leader-followers scheme. At the same time, the followers
are positioned with respect to the leader according to a geometric shape that can change, within a given range, in order
to face the environment's characteristics [18], [20], [21].
Different from the approach in [17] and [18], referring to
indoor applications for mobile robots, the main contributions
of this article are as follows 1) the FM2 technique is extended
to be applied in 3-D outdoor environments for UAVs formation applications with more restrictive kinematic constraints;
2) the FM2 method is modified to introduce two adjustment
parameters p1 and p2 that allow both changing the smoothness of the paths and setting the flight level in a very intuitive
way and without adding computational complexity to the
approach; 3) the generated paths are optimal in terms of distance cost, safety, and smoothness; 4) the approach can be
equally applied when the number of followers is drastically
increased (two followers have been selected in this article
for the sake of simplicity), and even for swarm configurations (no leader); 5) the planning method do not rely on
either probabilistic techniques or optimization methods (not
proper when it comes to certification issues), which makes it
more suitable for its use in real aviation applications.
The Problem Statement section presents the environment and the mission characteristics. The section on
UAVS Formation Approach presents an approach to

IEEE A&E SYSTEMS MAGAZINE

MAY 2020

IEEE - Aerospace and Electronic Systems - May 2020

Table of Contents for the Digital Edition of IEEE - Aerospace and Electronic Systems - May 2020