Page 156 - Innovations in Intelligent Machines

148 S. Rathinam and R. Sengupta
Minimum distance to travel from A to B ≠ minimum distance from B to A
A B

Fig. 1. An example that illustrates the asymmetry in resource allocation problems
involving UAVs

by the vehicle is minimum is called the Travelling Salesman Problem (TSP).
TSP is known to be NP-Hard [1],[2]. That is, there are no algorithms that
are currently available in the literature that can solve the TSP optimally in
3
polynomial time . There are other variants of the standard TSP that can
be useful for applications involving UAVs. For example, in multiple UAV
problems, vehicles might start their missions from a single depot or from
multiple depots.
The presence of kinematic constraints for the UAV complicates these
resource allocation problems further. A typical constraint that is used in plan-
ning problems involving UAVs is the yaw rate constraint. The yaw rate con-
straint models the inability of a UAV to turn at any arbitrary yaw rate. This
yaw rate constraint introduces asymmetry in the distances travelled between
two points. For example, a UAV starting at destination A with heading ψ A
and arriving at destination B with heading ψ B may not equal the length of its
optimal path starting at destination B with heading ψ B and arriving at desti-
nation A with heading ψ A . An illustration of this asymmetry for an example
is shown in figure 1.
This chapter formulates three sets of resource allocation problems that are
useful in the context of UAVs and presents algorithms that have been devel-
oped in the literature to address each of them. To simplify the presentation,
the chapter formulates each resource allocation problem, discusses the relevant
literature and presents algorithms to solve the same in separate sections.

2 Single Vehicle Resource Allocation Problem
in the Absence of Kinematic Constraints

2.1 Problem Formulation

Let one UAV be required to visit n destinations. Let V be the set of ver-
tices that correspond to the location of the UAV and the destinations, with
the first vertex V 1 representing the UAV and V 2 ,...,V n+1 representing the
3
An algorithm can solve a problem in polynomial time if the number of steps
required to run the algorithm is a polynomial function of the input size of the
problem.