666
consumed in each path as well as to fulfill the constraints of a traveling salesman problem.
An image sensor is fitted at the bottom of the UAV to take photos at each point in the tour.
If i, j, and k are three consecutive points in a proposed route, then the fitness of that route
can be determined by Eq. (2).
FitnessFunction =
+
∑ E ij
ijk
α θ ij
α α
(2)
where E i,j is the energy consumed by the UAV in moving from waypoints i to j, and θ i,j,k is
the vector angle between path segments (i, j) and (j, k). During our preliminary studies,
it was observed that the output route has a lot of sharp turns and the drone takes some
time and energy in changing its yaw direction. In order to avoid it, the parameter α is a
weight added as the penalty for sharp turns. If the sharp turns are desired, then the value
of α should be input low and if the sharp turns are not desired then its value should be
considered high.
The chromosome structure is represented in the form of a sequence of waypoints, which
defines a point with latitude, longitude, and elevation in the WGS 84 coordinate system. This
type of representation is referred to as “path representation” and possibly the most natural
representation of a tour (Larranaga, 1999). This representation also facilitates the use of
many popular genetic operators like PMX, cycle crossover, order crossover, and genetic edge
recombination crossover (ER).
3.3 Results
A case study has been developed by deriving the centerlines of benches for a mine in Nevada.
The centerlines have been extracted using Surpac (Dassaults, 2018) by digitizing the strings
between two contours of the mine. The centerlines are then elevated further 36.75 m above
the ground as the required resolution for the images is 1.27 cm. These centerlines are then fed
to the GA for finding the optimum path. Currently, the algorithm has mutation operators
such as swap, flip and slide. For a 317-points length path, the algorithm takes 15 minutes to
reach the solution. As much as 60% of the times goes for calculating the initial distance and
search matrices. In the algorithm, the population size of 100 has been used with swap, flip
and slide as mutation operators. The stopping criteria which are the conditions at which the
algorithm stops running are set as the maximum number of iterations. The number of iterations has been set at 100,000 dues to the complexity of the problem and to ensure that the
solution is as near-optimal as possible. The experiments have been conducted on a PC with
6GB RAM.
It has been observed in the experimental studies that the cost of the best route planned
by the algorithm is 96 which is very close to the optimal route whose length is 80. However,
on an average, the solution provided by the proposed algorithm is almost double the optimal
solution. The experimental verification has been conducted for the presented path planning
algorithm. However, being an NP-Hard problem, no evidence has been found that this is the
best solution for this kind of problems.
4 ANDROID APPLICATION: DEVELOPMENT AND EVALUATION
In this section, the development and working of an Android flight control application have
been explained. For this application, Android Studio V.3.1.4 has been used as developing
environment, DJI Android SDK (DJI, 2018) has been used for interaction with UAV’s flight
controller, and Google Maps Platform’s Maps API (Google, 2018) has been utilized for
navigation. The latest versions of all three kits have been accessed from the websites and
implemented in JAVA. DJI Mavic Pro has been used for conducting test flights using the
application during the development and testing stages. The android application is running on
a 1.3 GHz CPU with 2 GB RAM capacity.
consumed in each path as well as to fulfill the constraints of a traveling salesman problem.
An image sensor is fitted at the bottom of the UAV to take photos at each point in the tour.
If i, j, and k are three consecutive points in a proposed route, then the fitness of that route
can be determined by Eq. (2).
FitnessFunction =
+
∑ E ij
ijk
α θ ij
α α
(2)
where E i,j is the energy consumed by the UAV in moving from waypoints i to j, and θ i,j,k is
the vector angle between path segments (i, j) and (j, k). During our preliminary studies,
it was observed that the output route has a lot of sharp turns and the drone takes some
time and energy in changing its yaw direction. In order to avoid it, the parameter α is a
weight added as the penalty for sharp turns. If the sharp turns are desired, then the value
of α should be input low and if the sharp turns are not desired then its value should be
considered high.
The chromosome structure is represented in the form of a sequence of waypoints, which
defines a point with latitude, longitude, and elevation in the WGS 84 coordinate system. This
type of representation is referred to as “path representation” and possibly the most natural
representation of a tour (Larranaga, 1999). This representation also facilitates the use of
many popular genetic operators like PMX, cycle crossover, order crossover, and genetic edge
recombination crossover (ER).
3.3 Results
A case study has been developed by deriving the centerlines of benches for a mine in Nevada.
The centerlines have been extracted using Surpac (Dassaults, 2018) by digitizing the strings
between two contours of the mine. The centerlines are then elevated further 36.75 m above
the ground as the required resolution for the images is 1.27 cm. These centerlines are then fed
to the GA for finding the optimum path. Currently, the algorithm has mutation operators
such as swap, flip and slide. For a 317-points length path, the algorithm takes 15 minutes to
reach the solution. As much as 60% of the times goes for calculating the initial distance and
search matrices. In the algorithm, the population size of 100 has been used with swap, flip
and slide as mutation operators. The stopping criteria which are the conditions at which the
algorithm stops running are set as the maximum number of iterations. The number of iterations has been set at 100,000 dues to the complexity of the problem and to ensure that the
solution is as near-optimal as possible. The experiments have been conducted on a PC with
6GB RAM.
It has been observed in the experimental studies that the cost of the best route planned
by the algorithm is 96 which is very close to the optimal route whose length is 80. However,
on an average, the solution provided by the proposed algorithm is almost double the optimal
solution. The experimental verification has been conducted for the presented path planning
algorithm. However, being an NP-Hard problem, no evidence has been found that this is the
best solution for this kind of problems.
4 ANDROID APPLICATION: DEVELOPMENT AND EVALUATION
In this section, the development and working of an Android flight control application have
been explained. For this application, Android Studio V.3.1.4 has been used as developing
environment, DJI Android SDK (DJI, 2018) has been used for interaction with UAV’s flight
controller, and Google Maps Platform’s Maps API (Google, 2018) has been utilized for
navigation. The latest versions of all three kits have been accessed from the websites and
implemented in JAVA. DJI Mavic Pro has been used for conducting test flights using the
application during the development and testing stages. The android application is running on
a 1.3 GHz CPU with 2 GB RAM capacity.