Page 172 - Innovations in Intelligent Machines

164 S. Rathinam and R. Sengupta
heuristics for multiple vehicles tracking moving destinations using clustering
and gradient techniques. Even though [30] consider moving destinations, their
main results are for stationary destinations which is essentially the RAP(m).
Also heuristics for more general versions of RAP(m) are presented in [31]
[32], but there are no bounds. Rathinam et al. [29] provide a algorithm for
RAP(m) with an approximation factor of 6.07 by assuming that D min ≥ 2r.
In the following subsections, we review two algorithms, one by Savla et al.
[26] for the single vehicle case and an other by Rathinam et al. [29] for the
multiple vehicle case.
Remark: Before we discuss the algorithms, we present the result by
L.E. Dubins [33] which forms the motivation for the paths chosen in the
algorithms. L.E. Dubins [33] gives the optimal path the vehicle must travel
between any two points subject to the path constraints given by equations 5.
Henceforth, any curved segment of radius r along which the vehicle executes
a clockwise (counterclockwise) rotational motion is denoted by R(L), and the
segment along which the vehicle travels straight is denoted by S.Thusthe
path in figure 15 is an RSL path. Dubin’s result states that the path joining
the two points (x 1 ,y 1 ,θ 1 ) and (x 2 ,y 2 ,θ 2 ) that has minimal length subject to
constraints in 5, is one of RSR, RSL, LSR, LSL, RLR and LRL. Such an
optimal path between any two points that has minimum length subject to
constraints in 5 would be called a Dubin’s path in this chapter.

4.3 Alternating Algorithm for the Single UAV Case
Let the number of destination points be (n ≥ 2).

1. Compute the optimal single TSP tour ignoring the kinematic constraints
of the vehicles (i.e. find the optimal single TSP tour based on the Euclid-
ean distances between all the points). Let the sequence of the destinations
.
in the calculated tour be denoted by d i 1 , ...d i n

x ,y 2 ,q 2
2

x ,y ,q
1 1 1

Fig. 15. Shortest path - {clockwise, straight, counter clockwise}