Page 171 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 163
where, v o denotes the speed, ω represents the bound on the yaw rate and
r = v o is the minimum turning radius of each UAV.
ω
. Assigning a path for UAV
Let the sequence P i for UAV v i be d i 1 , ...d i k
v i through its sequence P i of destinations also implies assigning the angles of
at which
approach β d i at each destination and assigning the angle of return β v i
the UAV comes back to its initial position (x(v i , 0),y(v i , 0)). For example, the
y
i th UAV moves from (x(v i , 0),y(v i , 0),α i )to(¯x(d i 1 ), ¯(d i 1 ),β(d i 1 )), and then
y y )) and so on. After reaching
from (¯x(d i 1 ), ¯(d i 1 ),β(d i 1 )) to (¯x(d i 2 ), ¯(d i 2 ),β(d i 2
.
d i k , it comes back to its initial position (x(v i , 0),y(v i , 0)) at an angle β v i
n

The objective is to minimize Cost(P i ), where Cost(P i ) is the total
i=1
distance travelled by the i th UAV.
The above problem is called as the RAP(m), i.e, Resource Allocation
Problem for m UAVs.
4.2 Literature Review
Significant interest in the potential of realizing a mission in battle field envi-
ronments using a collection of small autonomous UAVs was the main motiva-
tion that lead to the formulation of problems such as RAP(m). Resource allo-
cation problems concerning UAVs has received considerable attention in the
last 7 years [15], [16], [17], [18], [19],[20], [21], [22], [23]. A more general version
of RAP(m) with each destination requiring multiple tasks was formulated
in [24]. Yang et al. [25] consider path planning for an UAV with kinematic
constraints given fixed initial and final positions in the presence of obsta-
cles. The UAV in their work is required to visit a destination and then
reach a final position avoiding threats and other obstacles. This is related
to RAP(1) in the absence of obstacles when there is one destination on the
tour. The single vehicle problem (RAP(1)) has been addressed by several
authors [26], [27], [29], [30]. In [26], Savla et al. bound the distance of the UAV
path between any points (x 1 ,y 1 ,θ 1 ) and (x 2 ,y 1 ,θ 2 ) in terms of the Euclidean
distance between the corresponding points. Also, using this result, they pro-
pose an algorithm which bounds the total distance travelled by the vehicle
in terms of the Euclidean distance tour. Ny et al. [27] provide an algorithm
8πr 14
with an approximation factor of (1+max{ , }) log n, where D min is the
D min 3
minimum Euclidean distance between any two locations. They approximate
RAP(1) as an asymmetric TSP and use the bound of log n by Frieze et al.
[28] to get the approximation factor. In [29], Rathinam et al. provide an algo-
rithm for RAP(1) with an approximation factor of 4.56 by assuming that
D min ≥ 2r. The main difference between the result in [29] and [27] is that
Rathinam et al. approximate the RAP(1) as as symmetric TSP and hence
the approximation factor is independent of n. Tang et al. [30] also provide a
heuristic for RAP(1)that uses an approximate gradient method to determine
the path of the UAV. However, there are no bounds presented in [30].
The paper that is most relevant to the multiple vehicle problem
(RAP(m)) is the work by Tang et al. [30]. In [30], Tang et al. provide