IEEE - Aerospace and Electronic Systems - May 2020 - 41

Monje et al.
the two followers and then applying the FMM using
as initial points all the black ones.
 The partial goals Pdðxg;j , yg;j , zg;j ) for each follower
are calculated from the position of the leader. These
partial goals indicate the desired next position for
each follower; when that position is calculated, the
obstacles of the environment (including the rest of
UAVs) are taken into account. For this purpose, the
gray level of each partial goal's position is calculated, thus modifying the distances (edges) of the
triangle shape. This method works as a repulsive
force with the obstacles of the environment. Figure 4
shows how the geometry of the formation is
affected and how the next partial goals are calculated, where the triangular shape distances for follower 1 and follower 2 are given by following:
Pdf1;i ¼ Pl;i À 2 Á d1 Á v þ Bf1;iþ1 Á d2 Á u
Pdf2;i ¼ Pl;i À 2 Á d1 Á v À Bf2;iþ1 Á d2 Á u:

(1)

In these equations, Pl;i is the position of the
leader, Pdf1;i and Pdf2;i are the desired positions
of the followers, d1 and d2 are the safety distances
in the direction of the leader and in perpendicular
direction between the UAVs, shown in Figure 4
and Bf1;iþ1 and Bf2;iþ1 are 2 À Witþ1 , where
Witþ1 is the gray level of the follower's current
position (level of proximity to obstacles)
Bf1;tþ1 ¼ 2 À W1tþ1
Bf2;tþ1 ¼ 2 À W1tþ1 :

(2)

The generalization for regular polygons of n
sides, with the leader as fist vertex and radius r
(distance from the center to the vertices) is




 
2kp
2kp
; sin
;0
Pdfk;i ¼ Pl;i þ r Ã Bfk;tþ1 Ã cos
n
n

where Pl;i is the position of the leader and Pdfk;i is
the position of the follower k. The term Bfk;tþ1
represents the safety margin in perpendicular
direction.
As has been noted, the distances are only modified
in the plane x À y; this means that the flight level
for the followers is the same as that of the leader.
For the case when a flight level is fixed, the flight
level of each follower is stipulated by the terrain.
 The second potential map Tit is obtained applying
the FMM into Wit . Figure 5(d) shows how the FMM
is applied taking into account the followers as
obstacles.
MAY 2020

 The gradient descent is applied into Tit obtaining the
path for each UAVi from its current position until
its partial goal.
 Each follower moves forward following the generated path until a new iteration is completed. The
low computational cost of the FM2 method allows
an adequate refresh rate. All this process is summarized in Figure 6.
Regarding the execution of follower cycles, each
cycle is executed with the minimum time span possible
between cycles, and this time spam depends on the
planning algorithm computational cost and the number
of followers. Once the partial paths are calculated for
each UAV in a cycle, the next cycle starts immediately. Table 1 has been computed in order to show the
computation time required for each cycle depending on
the number of followers. The number of followers has
been increased from two to four, the computation time
being around 2.5 s, and showing a linear growth with
the number of UAVs.

PATH PLANNING WITH FLIGHT-LEVEL CONSTRAINT
The characteristic that makes the FM2 method so interesting is that by modifying the gray levels of matrix W , it is
possible to generate the desired trajectories.

Algorithm 1. Introduction of the flight level in the
method.
Require: The velocities map W of a gridmap G of size m
x n x l.
Require: Flight level Lw with respect to the ground.
Require: Adjustment parameters p1 and p2 .
Ensure: The velocities map W with the clarified flight
level cells.
1: for k to l do
2: for j to n do
3:
for i to m do
4:
SurfaceValue
Surfaceði; jÞ
5:
if k = (Lw þ SurfaceValueÞ then
6:
wi;j;k
ðwi;j;k Þp1
7:
else
ðwi;j;k Þp2
8:
wi;j;k
9:
end if
10:
end for
11: end for
12: end for
In many cases there are restrictions on an absolute
flight level, or on the surface of the terrain. The restrictions refer to the trajectory with the exception of the start
and end points.
As the fast marching wave front propagates more rapidly through the lighter areas, it is necessary to impose

IEEE A&E SYSTEMS MAGAZINE

41
IEEE - Aerospace and Electronic Systems - May 2020

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