Page 173 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 165
2. Since the sequence of the destinations is known, the path of the UAV can
be determined by fixing the heading angles at each of the destinations.
The heading angles are now fixed as follows:
a) Let j =1.
to be the orientation of the line
b) If j is odd and j ≤ n − 1, fix β i j
y )
¯ y(d i j+1 )−¯(d i j
) := arctan [ ].
segment joining d i j to d i j+1 , i.e β(d i j )
¯ x(d i j+1 )−¯x(d i j
to be the orientation of the line seg-
c) If j is odd and j = n,fix β i j
):=
ment joining d i n to the initial position of the vehicle, i.e β(d i j
y(v 1 ,0)−¯(d i n )
y
arctan [ ].
x(v 1 ,0)−¯x(d i n )
).
d) if j is even, fix β(d i j ):= β(d i j−1
,
e) if j = n fix the return angle of the UAV to its initial position, β v 1
) and stop. Else, if j< n, assign j =⇒ j +1 and go to
equal to β(d i n
step (b).
y ),
3. Now construct Dubin’s path from (x(v i , 0),y(v i , 0),α i )to(¯x(d i 1 ), ¯(d i 1
y y )) and
β(d i 1 )) and then from (¯x(d i 1 ), ¯(d i 1 ),β(d i 1 )) to (¯x(d i 2 ), ¯(d i 2 ),β(d i 2
to the initial vehi-
so on. For the last leg of the tour that joins d i n
y )) to
cle location, construct a Dubin’s path from (¯x(d i n ), ¯(d i n ),β(d i n
).
(x(v i , 0),y(v i , 0),β v 1
An example of the alternating algorithm is shown in Fig. 16. The main
result in [26] bounds the length of the Dubin’s path D(p 1 ,p 2 ) that joins p 1 =
(x 1 ,y 1 ,θ 1 )to p 2 =(x 2 ,y 2 ,θ 2 ) in terms of the Euclidean distance E(p 1 ,p 2 )
2 2
between the points, where E(p 1 ,p 2 ):= (x 1 − x 2 ) +(y 1 − y 2 ) . This result
is stated in the following theorem.
Theorem 7. D(p 1 ,p 2 ) ≤ E(p 1 ,p 2 )+ κπr where κ ∈ [2.657, 2.658] and r is
the minimum turning radius of the UAV.
4.4 Approximation Algorithm for the Multiple UAV Case
Rathinam et al. [29] assume that the Euclidean distances between any two
destinations and the Euclidean distance between the initial position of each
UAV and a destination is greater than twice the minimum turning radius
of the UAV. This is a reasonable assumption in the context of unmanned
aerial UAVs which carry sensors that have footprints that are greater
2 2
than 2r. This implies that (¯x(d j ) − ¯x(d k )) +(¯y(d j ) − ¯y(d k )) ≥ 2r and

(x(v i , 0) − ¯x(d j )) +(y(v i , 0) − ¯y(d j )) ≥ 2r, ∀j = k, ∀j, k ∈{1, 2..n}, ∀i
2
2
∈{1, 2..m}.
First, we give a simple algorithm S for the UAV v 1 to find a path to
travel from positions (x(v 1 ),y(v 1 ),α 1 )to(¯x(d j ), ¯y(d j )). Note that the final
approach angle at the position (¯x(d j ), ¯y(d j )) is free to be chosen. Algorithm
S is as follows:
1. Find the distances of two possible paths the UAV could take: RS and LS.
2. Choose the path that has the minimum distance.