Page 170 - Innovations in Intelligent Machines

162 S. Rathinam and R. Sengupta
cost edges. Remove the edges between any pair of vertices representing
the UAVs.
˜
2. Construct a constrained Minimum Spanning Tree on G such that the sum
of the degrees of the vertices denoting the UAVs to be at most m + p.
3. By dropping all the edges between the root vertex and each of the vertices
representing the UAVs in the constrained MST found from step 2, one will
get a forest consisting of at most p non-trivial trees (a non-trivial tree is
one which consists of atleast one edge) that spans all destinations with
exactly one UAV in each tree and at least m − p vehicles that are not
incident on any edge.
4. We then double the edges of the non-trivial trees and construct a tour
for each of the vehicles by following the exact procedure outlined in the
2-approximation algorithm for single TSP in section 2.3.
The following theorem in [13] shows this algorithm CT has an approxima-
tion factor of 2.
Theorem 6. The algorithm CT solves the MVMDP with an approximation
4
factor of 2 in O((n + m) ) steps when the costs are symmetric and satisfy
triangle inequality.

4 Resource Allocation Problems in the Presence
of Kinematic Constraints

4.1 Problem Formulation

Let (x(v i ,t),y(v i ,t),θ(v i ,t)) denote the position and the heading of UAV
v i at time t. Let each UAV start at an initial heading θ(v i , 0) = α i . Sim-
ilarly, let (x(d j ,t),y(d j ,t)) denote the position of destination d j at time t.
Since the destinations are assumed to be stationary, let (¯x(d j ), ¯y(d j )) =
(x(d j ,t),y(d j ,t)) ∀ t.GivenasetofUAVs {v 1 ,v 2 , ...v m } and destinations
{d 1 ,d 2 , ...d n }, the problem is to

• assign a sequence of destinations P i to each UAV to visit such that

{d 1 ,d 2 ...d n } = { P i } and {P i } {P j } = ∅ if i = j.
i
• assign to each UAV v i , a path through the sequence P i such that the path
of each UAV v i satisfies the following kinematic constraints:

dx(v i ,t)
= v o cos (θ(v i ,t)),
dt
dy(v i ,t)
= v o sin (θ(v i ,t)),
dt
dθ(v i ,t)
= Ω where Ω [−ω, +ω], (5)
dt