Page 177 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 169
5 Summary and Open Problems

This chapter formulated a set of resource allocation problems that are moti-
vated by the applications involving Unmanned Aerial Vehicles. Since UAVs
have fuel constraints in them and the distance travelled by the vehicles depend
upon its fuel capacity, the problems focussed on the objective of minimizing
the total distance travelled. Since these problems are variants or generaliza-
tions of the Travelling Salesman Problem that is NP-Hard, approximation
algorithms were presented to solve the same. The kinematics of the UAVs
further complicate these resource allocation problems and methods that have
been presented in this chapter combine results from the TSP and the opti-
mal control literature. The following part of the section discusses some of the
key issues that have not been addressed in this chapter and the related open
problems in the context of UAV applications:
• Approximation algorithms with lesser bounding factors:
This chapter reviewed algorithms with an approximation factor of 2 for
different variants of multiple depot routing problems. It is not clear
whether the Christofides algorithm can be extended to the multiple depot
case. The main difficulty in deriving lesser approximation factors is due to
the hardness in obtaining a suitable partition of the destination vertices.
Another result that is worth mentioning here is a complexity result for the
bottleneck variants of the multiple depot problem. In [35], it is stated that
it is hard to derive an algorithm with an approximation factor less than 2
unless P=NP for bottleneck variants. It is unclear whether a similar result
can be derived for the multiple depot problems presented in this chapter.

• Distributed algorithms:
The algorithm for the multi depot problem given in this paper involved
finding a minimum spanning tree of all the vertices. It is known that mini-
mum spanning tree computations can be distributed and auction style
algorithms can be developed for these problems as shown in [34]. But it
seems that there is a tradeoff between obtaining a tighter approximation
factor versus distributed computation. It is intuitive that it would be even
harder to obtain distributed algorithms with approximation factors less
than 2. Recent results in [34] suggest some approaches for these routing
problems based on auctions. Further studies on distributed, routing algo-
rithms are suggested in the context of UAV applications.

• Computational results involving UAVs:
The main difference between the routing problems involving UAVs and the
TSP variants is that UAVs have additional kinematic and dynamic con-
straints. Though there are several theoretical results for routing problems
involving UAVs currently in the literature, there have been no computa-
tional results that compare the performance of different heuristics for these