Page 175 - Innovations in Intelligent Machines
P. 175
Algorithms for Routing Problems Involving UAVs 167
0
0
UAV
destination
Fig. 17. Calculate the minimum spanning tree (MST). In this example, there are
3 UAVs, hence MST will have 2 zero cost edges
UAV
destination
Fig. 18. Remove the zero cost edges from MST to yield a tree for each UAV
destination d 1 at an angle θ. Again, use algorithm S to construct a path
from (¯x(d 1 ), ¯y(d 1 ),θ)to(¯x(d 2 ), ¯y(d 2 )) and so on. (Fig. 21).
The above algorithm has an approximation factor of 6.07 [29]. This is
stated in the following theorem.
Theorem 8. AlgorithmMV A with the assumptions on the minimum Euclid-
ean distance solves the RAP(m) with an approximation factor equal to
2
2(π +1 − tan −1 (2)) ≈ 6.07 in O((n + m) ) steps.
