662
addressed in this paper by creating a novel application to generate sub-millimeters resolution
three-dimensional models of mine terrain as well as presenting an algorithm to optimize the
drone path. With the advent of commercial drones for civil use, may software companies
have developed software packages/applications for flight planning and autonomous flight
execution of the UAVs. There are two stages of flights in this study. Firstly, an area mapping
flight is conducted over a new mine with ground control points to create accurate threedimensional models of the mine. Since the position of benches and walls keep changing in
the mine (which is not updated in the Google Maps frequently), this stage helps to create a
current map of the mine. Secondly, the surface terrain obtained in the first stage is used as an
input to fly the drone over the mine benches.
2 LITERATURE REVIEW
Photogrammetry is the science of measuring the 3-D coordinates of physical world object
from their photographs. Torrero et al. (2015) have presented a methodology for generating
high-resolution orthomosaic of an active landslide area using a micro UAV fitted with an
image sensor. Structure from Motion (SfM) is another technique of estimating the 3-D
form of a scene from a series of 2-D digital images (Hartley & Zisserman, 2000). Lucieer
(2011) showed the use of Sfm for generating a 3D point cloud of topography in a real-world
coordinate system with an accuracy of 3 cm from overlapping UAV photographs of the
terrain. Zarco-Tejada (2018) explains how UAV equipped with normal thermal and multispectral imaging sensors guided by autonomous navigation using GPS has overcome successfully the financial and technical challenges of Satellite sensors and derived quantitative
remote sensing products on crop stress and water spills. Visockienė (2016) and Di Franco &
Buttazzo (2016) presented the mathematical relations for flight planning and estimating the
parameters of flight for taking overlapping photos of an area. It is industry wide recommended to have 85% forward overlap and 70% side overlap for dense vegetation and fields
(PIX4D, 2018).
Due to the limited amount of battery onboard a drone, it is important to fly through the
waypoints in an optimized way. The optimization problem is such that the drone should start
from a starting point, fly and take photos at each waypoint exactly one and return to the
starting point in the shortest amount of energy consumed. Such an optimization problem is
typical of the travelling salesman problem (TSP). The TSP is one of the well-known problems
in the field of combinatorial optimization. It is basically a minimization of the total distance
traveled by the salesman while touring all cities exactly once and returning to the starting city
(Hussain et al., 2017). The TSP is a nondeterministic polynomial-time hard problem.
Different approaches have been suggested in the literature for solving the TSP, such as
simulated annealing (Kirkpatrick, 1985), neural networks (Bhide, 1993), and Tabu search
(Glover, 1990). Integer linear programming methods have also been proposed with ways to
eliminate subtours (Miller, 1960). However, as the number of points increases up to more
than 100, integer programming becomes impractical. Meneses (2017) has presented an application of a genetic algorithm for solving the 3-D variation of the TSP. The advantage of
deploying this kind of evolutionary algorithm is that the speed of reaching the solution can
be increased by using metaheuristics for estimating the initial solution.
Ergezer (2013) has presented a way of using a genetic algorithm for path planning for
multiple drones in a 3-D coordinate system. The problem was to plan the flight of drone
through some desired areas while avoiding some undesired areas. Portas et al. (2010) have
designed an evolutionary trajectory for multiple UAVs in a military environment which can
work online as well as offline. The objective function in their work tries to minimize the
risk to the UAV from enemy’s missiles and includes constraints based on drone’s dynamics and environment. To improve the speed of path planning using a genetic algorithm,
Pehlivanoglu & Abdurrahman (2007) proposed a vibrational mutation operator based
genetic algorithm. It also helps in escaping the local minima which the genetic algorithms
are more prone to reach on.
addressed in this paper by creating a novel application to generate sub-millimeters resolution
three-dimensional models of mine terrain as well as presenting an algorithm to optimize the
drone path. With the advent of commercial drones for civil use, may software companies
have developed software packages/applications for flight planning and autonomous flight
execution of the UAVs. There are two stages of flights in this study. Firstly, an area mapping
flight is conducted over a new mine with ground control points to create accurate threedimensional models of the mine. Since the position of benches and walls keep changing in
the mine (which is not updated in the Google Maps frequently), this stage helps to create a
current map of the mine. Secondly, the surface terrain obtained in the first stage is used as an
input to fly the drone over the mine benches.
2 LITERATURE REVIEW
Photogrammetry is the science of measuring the 3-D coordinates of physical world object
from their photographs. Torrero et al. (2015) have presented a methodology for generating
high-resolution orthomosaic of an active landslide area using a micro UAV fitted with an
image sensor. Structure from Motion (SfM) is another technique of estimating the 3-D
form of a scene from a series of 2-D digital images (Hartley & Zisserman, 2000). Lucieer
(2011) showed the use of Sfm for generating a 3D point cloud of topography in a real-world
coordinate system with an accuracy of 3 cm from overlapping UAV photographs of the
terrain. Zarco-Tejada (2018) explains how UAV equipped with normal thermal and multispectral imaging sensors guided by autonomous navigation using GPS has overcome successfully the financial and technical challenges of Satellite sensors and derived quantitative
remote sensing products on crop stress and water spills. Visockienė (2016) and Di Franco &
Buttazzo (2016) presented the mathematical relations for flight planning and estimating the
parameters of flight for taking overlapping photos of an area. It is industry wide recommended to have 85% forward overlap and 70% side overlap for dense vegetation and fields
(PIX4D, 2018).
Due to the limited amount of battery onboard a drone, it is important to fly through the
waypoints in an optimized way. The optimization problem is such that the drone should start
from a starting point, fly and take photos at each waypoint exactly one and return to the
starting point in the shortest amount of energy consumed. Such an optimization problem is
typical of the travelling salesman problem (TSP). The TSP is one of the well-known problems
in the field of combinatorial optimization. It is basically a minimization of the total distance
traveled by the salesman while touring all cities exactly once and returning to the starting city
(Hussain et al., 2017). The TSP is a nondeterministic polynomial-time hard problem.
Different approaches have been suggested in the literature for solving the TSP, such as
simulated annealing (Kirkpatrick, 1985), neural networks (Bhide, 1993), and Tabu search
(Glover, 1990). Integer linear programming methods have also been proposed with ways to
eliminate subtours (Miller, 1960). However, as the number of points increases up to more
than 100, integer programming becomes impractical. Meneses (2017) has presented an application of a genetic algorithm for solving the 3-D variation of the TSP. The advantage of
deploying this kind of evolutionary algorithm is that the speed of reaching the solution can
be increased by using metaheuristics for estimating the initial solution.
Ergezer (2013) has presented a way of using a genetic algorithm for path planning for
multiple drones in a 3-D coordinate system. The problem was to plan the flight of drone
through some desired areas while avoiding some undesired areas. Portas et al. (2010) have
designed an evolutionary trajectory for multiple UAVs in a military environment which can
work online as well as offline. The objective function in their work tries to minimize the
risk to the UAV from enemy’s missiles and includes constraints based on drone’s dynamics and environment. To improve the speed of path planning using a genetic algorithm,
Pehlivanoglu & Abdurrahman (2007) proposed a vibrational mutation operator based
genetic algorithm. It also helps in escaping the local minima which the genetic algorithms
are more prone to reach on.