University of Nevada, Reno

Flight Path Planning and Optimization for High-Resolution Imaging in

Open Pit Mines by UAVs

A thesis submitted in partial fulfillment of the requirements for the

degree of Master of Science in Mining Engineering

By:

Rushikesh Battulwar

Dr. Javad Sattarvand/Thesis Advisor

December 2018
Copyright © by Rushikesh Battulwar 2018

All Rights Reserved

 THE GRADUATE SCHOOL

We recommend that the thesis

prepared under our supervision by

RUSHIKESH BATTULWAR

Entitled

Flight Path Planning And Optimization For High Resolution Imaging In Open Pit
Mines By Uavs

be accepted in partial fulfillment of the

requirements for the degree of

MASTER OF SCIENCE

Dr. Javad Sattarvand, Advisor

Dr. Karoly (Charles) Kocsis, Committee Member

Dr. Behrooz Abassi, Committee Member

Dr. Robert Watters, Graduate School Representative

David W. Zeh, Ph.D., Dean, Graduate School

December, 2018
 i

Abstract

The past decade has witnessed an unparallel augmentation in the field of Unmanned Aerial

Vehicles (UAVs). With the increased availability of cost-effective drones and skilled

personnel, there are many potential applications of drones in an open pit mining operation

like tension crack detection and characterization, drill holes accuracy measurement, blast

fragmentation or evaluating the condition of ramps. All these applications require high

resolution and accurate 3-D models of the mine. For example, despite advances in slope

monitoring, identification of tension crack remains an open problem for geotechnical

engineers. With the increasing size and depth of the mines, traditional tension crack

mapping is a laborious and dangerous task which eventually has necessitated automation.

A crucial bottleneck to accomplish this task is the availability of millimeter resolution

three-dimensional terrain models of the benches.

This thesis aims to address the problem of tension crack detection on the benches of open

pit mines by using Unmanned Aerial Vehicles. A UAV fitted with an image sensor has

been used for imaging the open pit benches to generate high-resolution 3-Dimensional

surface models of the mine. The contributions of this work include 1) Semi-automatic

procedure for generating 3-D models of the mine, 2) Battery consumption model for the

given UAV, 3) Path planning and optimization algorithm for taking high-resolution

imaging of the open pit benches, and 4) An android application for flight planning of the

UAV in the mine.

 ii

Dedication

This thesis is dedicated to my parents and brother. Thank you for always believing in me

and being my pillar of strength throughout my life.

Jai Shivaji, Jai Bhavani

 iii

Acknowledgments

Foremost, I would like to express my sincere gratitude to my advisor Dr. Javad

Sattarvand for his continuous support in achieving my dream of graduate education, for

his patience, motivation, enthusiasm, and immense ingenuity.

The research conducted in this dissertation is part of 2-year technology project titled

“Developing a New Tension Crack Analysis System to Increase the Safety of Open Pit

Slopes” funded by the National Institute for Occupational Health and Safety (NIOSH). I

would like to thank Dr. Bahram Parvin for his helpful insights during the research project.

I would also like to thank Jorge and Garrett for their outstanding help in outdoor

experiments and data analysis.

I am also grateful to my committee members: Dr. Karoly (Charles) Kocsis, Dr. Behrooz

Abassi and Dr. Robert (Bob) Watters for their continuing guidance throughout the 2-

year master’s studies.

Finally, I want to thank my parents whose countless sacrifices and immense patience have

helped me complete my education.

 iv

Table of Contents
Abstract ................................................................................................................................ i
Dedication ........................................................................................................................... ii
Acknowledgements ............................................................................................................ iii
Chapter 1: Introduction ....................................................................................................... 1
Chapter 2: Literature Review .............................................................................................. 4
Chapter 3: UAV Path Planning and Optimisation ............................................................ 23
3.1 Accuracy Assessment of Drone Barometer ............................................................ 23
3.2 Generating 3-D surface maps using aerial photography ......................................... 25
3.2.1 Data collection...................................................................................................... 26
3.2.2 Data Processing .................................................................................................... 31
3.3 Power consumption model of Drone ....................................................................... 34
3.3.1 Empirical Studies ................................................................................................. 34
3.3.2 Regression model of Power consumption for DJI Mavic Pro ............................. 37
3.3.3 Model Validation.................................................................................................. 39
3.4 Flight mission planning and optimisation ............................................................... 39
3.4.1 Mine Bench centrelines ........................................................................................ 41
3.4.2 Model formulation................................................................................................ 41
3.4.3 Genetic Algorithm ................................................................................................ 42
3.4.3.1 Fitness Function ................................................................................................ 44
3.4.3.2 Structure of chromosome .................................................................................. 45
3.4.3.3 GA Operators .................................................................................................... 46
3.5 Results ..................................................................................................................... 50
3.6 Conclusion............................................................................................................... 51
Chapter 4: Android Application: Development and deployment ..................................... 55
4.1 Connecting the App to the drone............................................................................. 56
4.2 Mission Planning Mode .......................................................................................... 57
4.3 Parallel Flight Planning ........................................................................................... 64
4.4 Polygonal Flight Planning ....................................................................................... 65
4.5 Deriving elevations from DEM ............................................................................... 70
4.5.1 Validation of algorithm ........................................................................................ 72
 v

4.6 Deriving elevations from Contours ......................................................................... 73

4.6.1 Validation of algorithm ........................................................................................ 76
4.7 Evaluation of the Android Application ................................................................... 77
4.8 Conclusion............................................................................................................... 85
References ......................................................................................................................... 86
Appendix ........................................................................................................................... 90
 vi

List of Tables

Table 1 Comparison of different DJI drones .................................................................... 11

Table 2 Critical comparison of flight planning application .............................................. 14

Table 3 Descriptive statistics of result .............................................................................. 25

Table 4 Flight logistic for Arturo and Goldstrike pits ...................................................... 31

Table 5 Photogrammetry outputs ...................................................................................... 34

Table 6 GA parameters ..................................................................................................... 51

Table 7 Test platform properties ....................................................................................... 55

Table 8 Flight planning ..................................................................................................... 78

Table 9 Processing results ................................................................................................. 80

Table 10 Flight parameters for stage 1 ............................................................................. 81

Table 11 Processing result for stage 1 flight ..................................................................... 82

Table 12 Flight planning for stage 2 ................................................................................. 82

Table 13 Processing result for stage 2 flight ..................................................................... 84

 vii

List of Figures

Figure 1 SSR system with its components .......................................................................... 6

Figure 2 Components of inclinometer ................................................................................ 7

Figure 3 Wire-line Extensometer ........................................................................................ 8

Figure 4 Seismic monitoring system[8] ............................................................................ 10

Figure 5 DJI Mavic Pro[9] ................................................................................................ 11

Figure 6 DJI phantom 4 Pro[9] ......................................................................................... 12

Figure 7 DJI Matrice 600 Pro[9]....................................................................................... 12

Figure 8 Area project by a camera with FOV α flying at height h[17] ............................ 17

Figure 9 Flight parameters[16] ........................................................................................ 18

Figure 10 (a) Experimental setup, (b) Bosch GLM 42 .................................................... 24

Figure 11 Cumulative frequency plot of errors................................................................. 26

Figure 12 Ground control point ........................................................................................ 28

Figure 13 Position of GCPs (a) Arturo pit, (b) Goldstrike pit .......................................... 29

Figure 14 (a) Setting up flight parameters; (b) Defining the area of mapping ................. 30

Figure 15 Maintaining the Line of Sight during drone flight execution ........................... 31

Figure 16 General workflow in Agisoft PhotoScan .......................................................... 32

Figure 17(a) PhotoScan UI, (b) Point cloud, (c) DEM, (d) Orthomosaic and (e) 3D Mesh

........................................................................................................................................... 33

Figure 18 Battery power consumption of DJI Mavic pro with different motions ............ 36

Figure 19 Battery power consumption of DJI Mavic Pro under different wind conditions

........................................................................................................................................... 38

Figure 20 Measured and modeled energy consumption for DJI Mavic Pro ..................... 40
 viii

Figure 21 Measured and modeled energy consumption for DJI Mavic Pro ..................... 40

Figure 22 Creating centerlines on mine benches .............................................................. 43

Figure 23 Bench centerlines as series of contiguous points ............................................. 43

Figure 24 Proposed genetic algorithm .............................................................................. 44

Figure 25 Route representation scheme ............................................................................ 46

Figure 26 Flip operation (a) Parent (b) Offspring ............................................................. 47

Figure 27 Demonstration of flip operator (a) Parent route (b) child route ....................... 48

Figure 28 Swap operation (a) Parent (b) Offspring .......................................................... 48

Figure 29 Demonstration of swap operator (a) Parent route (b) child route ..................... 49

Figure 30 Slide operation (a) Parent (b) Offspring ........................................................... 49

Figure 31 Demonstration of slide operator (a) Parent route (b) child route ..................... 50

Figure 32 GA evaluation results ....................................................................................... 53

Figure 33 Optimum path from current version of GA ...................................................... 54

Figure 34 Workflow of designed application ................................................................... 56

Figure 35 Connection status screen of the App ................................................................ 57

Figure 36 Mission planning mode .................................................................................... 58

Figure 37 Imported DEM of Arturo mine......................................................................... 58

Figure 38 Imported map of Arturo mine........................................................................... 60

Figure 39 Imported contours of Arturo mine .................................................................... 60

Figure 40 Imported contours overlapping on mine model................................................ 61

Figure 41 Waypoint mission configuration ...................................................................... 62

Figure 42 Illustration of parallel flight planning............................................................... 65

Figure 43 Parallel Flight planning algorithm .................................................................... 66

 ix

Figure 44 Illustration of polygonal flight planning........................................................... 67

Figure 45 Polygonal flight planning algorithm ................................................................. 68

Figure 46 Repairment process .......................................................................................... 69

Figure 47 Constructing offset polygon and waypoints ..................................................... 70

Figure 48 Extraction of the z values from imported DEM .............................................. 71

Figure 49 Errors in estimation of elevations ..................................................................... 74

Figure 50 Errors in estimation of elevations from contours ............................................. 77

Figure 51 Test flight with the designed application.......................................................... 78

Figure 52 Test flight 1 Photogrammetric outputs (a) Point cloud, (b) DEM, (c) Overlapping

statistics ............................................................................................................................. 80

Figure 53 Laying ground control points at Keystone trailhead ........................................ 81

Figure 54 Parallel flight for stage 2 .................................................................................. 83

Figure 55 Generated point cloud with location of images ................................................ 84

Figure 56 overlapping statistics for stage 2 flight ............................................................. 84

 1

Chapter 1: Introduction
The past decade has witnessed an unparallel augmentation in the field of Unmanned Aerial

Vehicles (UAVs). Their presence can be seen in every mining operation throughout the

whole. With the increased availability of cost-effective drones and skilled personnel, many

drone companies are looking for potential applications of drones in the mining industry.

The vast nature of mines and hazardous environment, UAV technology is the perfect tool

to be applied in the operations. As a result, many mining giants like Rio Tinto, Bhp,

Newmont, Barrick have been using drones for surveying, volumetric analysis, monitoring

purposes. Transforming these tasks into an aerial task gives a big advantage in terms of

time and man power.

This research work is part of a NIOSH project titled “Developing a New tension Crack

Analysis System to Increase the Safety of Open Pit Slopes”. This is a two-year technology

project aimed at developing an early warning system for open pit mines focussing on

detection and characterization of tension cracks using a drone fitted with a high -resolution

camera. Despite advances in slope monitoring, identification of tension cracks remains a

laborious task on the part of geotechnical engineers of the mine because of the size of

mines. It has been proposed to utilize (i) a UAV for imaging and mapping the open pit

mine, and (ii) state of the art machine learning techniques for automated identification of

cracks and characterizing their dynamics. The results will be an early warning system that

alerts the geotechnical engineer about the location of potential failures so that the necessary

safety steps can be executed.

 2

Some of the drawbacks of the current slope monitoring practices which are addressed

through this research work are (i) The radar-based scanners essentially monitor the slope

movement but cannot identify cracks which are useful for numerical modeling of slope

stability. Further, their deployment is expensive and unaffordable for small mining

operations. The rental charges for SSR can go as high as $25,000/month in the state of

Nevada. (ii) The process of installing instrumentation in a moving wall to monitor the

expansion of each crack is firstly unsafe and dangerous. Secondly, this task is slow and

time-consuming. In the current technological scenario, this task can be automated with the

use of drones and image processing.

This thesis is structured in the following order, consisting of five chapters which have been

explained in brief below:

Chapter 1: Introduction

A summary of the issues related to the current technology used for slope stability

analysis and monitoring in the mining industry has been explained. The goals of this

research work, as well as the entire NIOSH project, have been explained.

Chapter 2: Literature review

A review of the current slope stability monitoring techniques available in the

markets has been presented. An introduction to the FAA regulation regarding the use of

drones for civil purposes and how it affects the drone’s applicability to the mining industry.

A brief review of the commercially available drones and high-resolution imaging camera

has also been conducted. Photogrammetry is an important part of this project. A literature
 3

review of the photogrammetric equations and their relations with the aerial position of the

drone has been explained.

Chapter 3: UAV Path Planning and Optimization

In this chapter, the approach to solve the problem has been explained. The chapter has four

subtopics(i) Accuracy assessment of drone barometer, (ii) Generating 3-D surface maps

using aerial photography, (iii) Power consumption model of a given UAV and (iv) UAV

flight planning and optimization. In the first, the accuracy of the drone parameter has been

evaluated and in the second subtopic, the procedure for creating 3-D models with aerial

images of the mine has been explained. In the last two subtopics, the estimation of battery

consumption model and the development of the path planning and optimization algorithm

has been explained.

Chapter 4: Android Application: Development and Deployment

This chapter includes the designing and development of the Android application for flight

mission planning and execution. It starts with explaining the UI of the developed

application, then parallels and polygon flight planning algorithms and their validation. In

the end, the validation of this application has been presented using a case study at a local

test site.
 4

Chapter 2: Literature Review

Slope failure is one of the most significant problems in open pit mines. Slope stability

accidents are leading causes of deaths at U.S open pit mining operations[1]. The nature of

slope failure is such that it doesn’t fail impulsively. Before the failure, it exhibits some

signs like movement or formation of tension cracks. Therefore, proper monitoring of slope

for early detection of failure is necessary for a safe and profitable mining operation[2]. The

methods currently deployed for slope stability monitoring varies from a simple

extensometer to sub-millimeter precision slope stability radar. Apart from the conventional

methods of daily visual inspection of slopes, high walls, there are two major types of

monitoring techniques for slope failure: Monitoring Surface movements and monitoring

subsurface movements. The surface movements monitoring includes Prism monitoring,

LiDAR, slope stability radar (SSR) and Global Positioning System.

Prism monitoring: Conventional prism monitoring has been done most mines of the work

using surveyors or automated theodolites. Prism is installed on critical areas throughout

the mines horizontally and vertically at regular spacings. The prism positions are measured

regularly, and the data is sent to the database for the user to view it graphically. The

theodolites are housed in a steel structure to protect them from flyrock, harsh weather

conditions, and theft. The system plots the data automatically whenever new data is

received which enables quick and easy identification of slope movements. This technique

is generally used in the mines for detecting any prolong slope movement patterns and the

probability of slope failure. Many prisms are damaged or lost due to rockfall, slope failure,

and flyrocks even after their protection using steel casing. Many times, there are no access
 5

paths for installing prisms in critical areas. Hence, the installation task could be dangerous,

time-consuming and expensive. The network of prisms doesn’t offer full coverage of the

benches as there is a chance of failure between two prisms.

LiDAR Scanners: These are static or mobile mounted equipment which is generated point

cloud models of an area by targeting high-density laser beams at it. A laser scanner could

be installed in a protective shed to continuously scan an unstable wall in an open operation.

The point clouds generated by it are compared point by point to determine the slope

movement with time. The accuracy and precision of Riegl VZ-6000 are 15 mm both[3].

LiDAR is a safe, profitable and rapid way of continuous slope monitoring in mines[4].

However, it is not capable of acting as an early warning of slope failures for safe

evacuations[5].

Slope Stability Radar (SSR): SSR is a leading equipment for monitoring of wall

movements in open pit mines. It provides sub-millimeter precision and scans 10,000 m2

area in one minute[5]. This system uses a technique called differential interferometry using

radar waves. It calculates the movements of a wall by comparing phases of radar signals

present in one scan to that of another. It includes an antenna mounted which is mounted on

either a fixed or movable platform which sends radar beams at the wall against which it is

placed. It scans the wall in the vertical and horizontal direction. Figure 1 depicts an SSR

system from world leader GroundProbe company which has been derived from [6].

A Global Positioning System (GPS): The GPS is based on a constellation of 24 satellites

which enables a microwaves signals receiver present on the ground to determine its
 6

location, speed, and direction of movement. Therefore, the comparison of the initial and

final position of the GPS receivers, the movement of slopes can be determined. The RTK

GPS uses radio data link for transferring data between satellite, rover and reference points

which makes its application in real time. Further, the accuracy of an RT-DGPS is in the

range of 5 to 20 mm[7]. A GPS system requires a minimum of four satellites to determine

its coordinates every time. While it can be used during day or night time, its applicability

is blocked by trees or wall sometimes. Further, the vertical accuracy is two times lesser

than positional accuracy.

Figure 1 SSR system with its components[8]

Subsurface movement is a major indication of slope instability. Quantitative assessment of

this movement can provide relevant details relating to the depths, the rate of movement,

and internal kinematics of the instability. Some leading subsurface monitoring equipment

used in today’s open-pit mines are discussed.

Inclinometers: Inclinometers can measure time-dependent differential displacements

along the length of a borehole. Therefore, it is sometimes called “Borehole inclinometers”.

It consists of a plastic with four longitudinal groves as shown in Figure 2 in the inside wall,

and a probe that is lowered down the casing on an electrical cable with graduated depth
 7

markings. The probe is deployed with two mutually aligned accelerometers, to measure the

tilt of the probe in mutually perpendicular directions. It is important to accurately position

the probe below the depth of movement so that the readings made from the end of the hole

are referenced from a fixed position.

Figure 2 Components of the inclinometer

Extensometer: The development of tensions cracks on the top of the benches is clearly

associated with instability. The characterization of these cracks is necessary for the

identification of unstable areas. A common method to identify the movement across

tension cracks is using a wire-line extensometer. The principle of working is that a wire is

anchored to the unstable part of the ground with the measuring system and pulley stationed

on the stable part as shown in Figure 3. The wire running over the pulley is tensioned using

a suspended weight. As the unstable part moves away from the pulley, the position of the

weight will change, and the displacement can be recorded tracked manually or
 8

electronically. The readings are prone to error due to thermal expansion and the system is

also prone to damage due to weather conditions or vandalism.

Figure 3 Wire-line Extensometer

Time Domain Reflectometry: TDR is based on a principle same as radar and could be

called “cable radar”. It comprises two components: a coaxial cable and a cable tester. An

electrical pulse is sent down the coaxial cable by the cable tester. The coaxial cable is

grouted in the borehole and when the pulse come across a break or deformation in the cable,

it is reflected. This reflection is represented in the cable signature as a spike. It can

determine the relative magnitude, the rate of displacement and position of deformation

spontaneously and accurately[2]. The advantages are a lower cost of installation, deeper

hole depths, immediate deformation detections[1]. The disadvantages are no information

on the orientation of deformation, only applicable to localized shearing deformation and

hazardous to install in failing slopes.

Piezometer: Slope failure are very sensitive to changes in the groundwater levels.

Groundwater has the capabilities to change shear stress and to expand tension cracks
 9

causing the ultimate failure[1]. Therefore, it is essential to monitor the groundwater

conditions. Piezometer is installed in a borehole to measure water pressures. The standpipe

piezometer is the simplest and most commonly used. It comprises of a thin plastic tube

with a porous tip put inside a borehole such that tip is in contact with surrounding soil[7].

The portion above the tip is filled with bentonite-cement grout to prevent the vertical

movement of the water. The water level is measured by lowering down the standpipe a

probe, graduate cable or tape, and a cable reel with a built-in water sensor. As soon as the

contact is detected by the sensor, the lowering of the probe is stopped, and water level

reading is recorded. There are other two types of piezometers namely vibrating wire and

pneumatic.

Microseismic Monitoring: Slope deformation like shearing, cracking and slipping of

planes generates microseismic emissions. This system comprises acoustic receivers called

geophones which are installed on a wall to record the energy and positions of these

emissions[7]. These data are then used for detecting the weakness zone, deformation

region and rate of deformation and investigating any newly generated discontinuities. This

equipment has accuracy of + 0.001m[8].

The use of a drone in the mines is regulated by the Federal Aviation Administration which

is a federal agency. It has charted out the rules and laws for flying drones in civil airspace.

It requires for a person to get a part 107 remote pilot license to fly a drone for industrial

use. It is essential to acknowledge the most important operating limitations made by the

FAA which affects the use of drones in the mining industry. A UAV can’t be flown faster
 10

than 100 mph ground speed at any given time. In the vertical direction, the maximum

altitude it can fly is 400 feet or 120 meters above ground level (AGL). However, if the

highest point in a mine is more than 120 meters, it is always possible to start your flight

from a relatively higher point such that altitude difference between the highest point and

the point of start is less than 120 meters.

Figure 4 Seismic monitoring system[8]

The FAA doesn’t permit the operation of drone directly above people who are not

participating in the operation unless those people are under a safe cover like a stationary

vehicle or shed. In mines, the drone flights are conducted in the early mornings when there

is sparse population and most miners are inside their equipment.

The drone while flying must remain in the Visual Line of Sight throughout its flight of the

pilot or any of the participating member. The line of sight should also be unaided which

means it should be without any binoculars. This is difficult to achieve with small size

drone like DJI Mavic pro in open mines of Nevada which are 2 km x 1.5 km in size. This

can be solved by deploying more people as visual observers in the mine or just flying over

the mine in small segments such that the drone is completely visible in each segment.
 11

A brief review of the commercially available drones and high-resolution imaging camera

has also been conducted as part of this research and presented in Table 1.

Table 1 Comparison of different DJI drones

DJI Matrice 600

Model DJI Mavic Pro DJI Phantom 4 Pro
Pro
Max Flight time 27 min 30 mins 16 mins
Navigation GPS + GLONASS GPS + GLONASS RTK GPS
Battery 3830 mAh 11.4 v 5870 mAh 5700mAh x 6
Obstacle sensing Forward All directions NA
Camera 12.35 MP 20 MP Variable
Weight 734 g 1388 g 9.5 kg
Flight applications UGCS, MME UGCS, MME UGCS, DJI Go
Charging time 45 mins 60 mins 60 mins
Max. Speed 65 kph 72 kph 65 kph
Max. distance 7 km 7 km 5 km

Figure 5 DJI Mavic Pro[9]

 12

Figure 6 DJI phantom 4 Pro[9]

Da-Jiang Innovations a Chinese technology company is a market leader in commercial and

civilian drone business dominating over 70% of the drone market. The DJI Mavic Pro and

Phantom 4 Pro falls in the consumer drone’s category and Matric 600 Pro falls in

Figure 7 DJI Matrice 600 Pro[9]

 13

the enterprise category. There are a considerable size and weight difference between the

two categories of the drones as evident from Table 1. In the quadcopter segment, the DJI

Mavic Pro and Phantom 4 Pro are the two best drones with the highest flight time of 27

minutes and 26 minutes respectively[10]. Due to the considerable size of the open pit

mines, the flight time, camera sensor and the obstacle avoidance played crucial roles in the

selection of the above drones. The fixed drones available from senseFly(Parrot Group)

have flight times of 50-90 minutes, however, is fixed wing they are laced with their own

disadvantages. Fixed wing aerial vehicles need a relatively large take-off and landing zone

for flight, unlike quadcopters which can land and takeoff from a single point. This makes

their use critical in mining operations where the terrain is not plain. They are expensive

than quadcopters. Most importantly, they have large turning radius than quadcopters which

makes them not suitable for grid pattern area mapping flights [11].

With the advent of commercial drones for civil use, may software companies have

developed software/applications for flight planning and autonomous flight execution of the

UAVs. A review of the most popular applications currently available in the market is

conducted to help choose an application for the project. There two stages of flights in this

project. Firstly, an area mapping flight will be conducted over a new mine with ground

control points to create three-dimensional 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 will be used as an input to fly the drone over the mine benches.
 14

Table 2 Critical comparison of the flight planning application

Map
s
Names/Fe Airm B4U DroneDe Pix4Dca Autop
Litchi Mad UGCS
atures ap Fly ploy pture ilot
e
Easy
Real time
airspace
       
intelligenc
e
Info about
TFRs,
airspace        
regulation
s
Weather
       
info
Path
       
planning
Terrain
       
follow
Digital
notices to        
authorities
$29.9 From $
Price 0 0 0 0 $24.99 $9.99
9 65
A/Io Deskto
Platform A/Ios A/Ios A/Ios A/Ios Ios Ios
s p
APK
availabilit        
y
Gimbal
adjustmen        
t
Photos
       
capture
% of
photos        
overlap
Speed
adjustmen       
t 
 15

Heading
adjustmen        
t
Drones Mostl Most
DJI Mostly DJI DJI DJI Mostly
supported y ly
Flight logs        
Weather
       
forecast
- clean
- UI
-Best -Easy
Good Better -
2D and for to use
for Advance than Immer
3D maps waypo -
know less d Litchi sive
generatio ints Good
Comments ing relia 2D and for AF 3D
n from planni for
wher ble 3D maps -only planni
photos ng area
e to availa ng
-move mapp
fly ble in -
gimbal ing
ios Intuiti
ve

The first stage requires an application which can help in the planning of the grid mission

for area mapping. In the grid mission, each point is defined based on the forward and

sideward overlap required between two the images. Further, the height of the flight will be

constant and based on the required ground sampling distance resolution. The relation

between the height of flight and GSD resolution is discussed in the next section. It is always

useful to get certain logistics of the flight like a total number of images, batteries required,

flight duration, the area covered while flight planning. Maps Made Easy offers all these

features in an easy to use interface.

The second stage requires an application which can import the three-dimensional map

created in the previous flight as well as plan a mapping mission based on it. Currently,

there is no android application available providing all these features. UGCS is a desktop-
 16

based software offering all these features, however, it is not available in phone or tablet.

This created a need to develop a new Android application for flight planning and execution

of drone to fulfill the goal of high-resolution imaging of mine benches.

Photogrammetry is the science of measuring the measuring the 3D coordinates of physical

world object from their photographs. In [12], the authors have presented a methodology

for generating high-resolution Ortho mosaic 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[13]. [14] 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. [15] 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.[16], [17] present the mathematical relations for flight planning and

estimating the parameters of flight for taking overlapping photos of an area. The size (Lx,

Ly) of the image taken by a UAV flying at a height h above the ground depends on height

h and size of the image sensor. It can be computed as[16]

𝛼
Lx = 2h . tan ( 2 ); Ly = Lx/ ρ, where (1)

Lx = width of the image on the ground

Ly = height of the image on the ground

𝛼 = Angle of view of the camera

 17

ρ = Ix/Iy = Aspect ratio

Ix = Width of the image expressed in pixels

Iy = Length of the image expressed in pixels.

The Ground Sampling Distance (GSD) which is the distance between the centers of any
two pixels of an image on the ground is given by[17]
α
Lx 2h. tan( )
2
GSD = = (2)
Ix Ix
x

Figure 8 Area project by a camera with FOV α flying at height h[17]

The size of the image on the ground is directly proportional to the altitude of the flying

drone above ground. Another important parameter is the proportion of overlapping

between images along the length and width of the area. It is industry wide recommended

to have 85 % forward overlap and 70 % side overlap for dense vegetation and fields[18].
 18

The distance between two overlapping images along the length and width of the targeted

area is given by[16]

𝑞 𝑝
a = d x (1 - 100 ), b = d x (1 - 100 ), where (3) & (4)

a = distance between two images along the length of the mapping area

b= distance between two images along the height of the mapping area

d = size of the image

p = Percentage of forward overlap

q = Percentage of sidewise overlap

Figure 9 Flight parameters[16]

 19

In the previous sections, it has been established that the for regeneration of surface terrain

from overlapping photographs, the UAV should fly through and take photos at specific

positions above the ground. These specific locations can be called as waypoints. 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.

The Travelling salesman problem (TSP) is one of the most research problems in the field

of combinatorial optimization. It has been studied in various forms in the field of computer

science, engineering, operations research, discrete mathematics and more. 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[19].TSP is an NP-Hard problem. For a tour of n

cities, there are (n-1)! possible solutions of which one or more could be of minimum cost

for an asymmetric TSP [20]. Due to such a large number of solutions even for a small size

of n, an exhaustive search for finding the minimum is not feasible.

Literature has suggested different approaches to solving the TSP, such as simulated

annealing[21], neural network[22], and Tabu search[23]. Integer Linear Programming

methods have also been proposed with ways to eliminate subtours[24]. However, as the

number of point increase more than 100, integer programming becomes impractical. [25]

have presented an application of a genetic algorithm for solving the 3D variation of TSP.

The advantage of deploying this kind of evolutionary algorithm is that the speed of
 20

reaching the solution can be increased by using metaheuristics for estimating the initial

solution.

In [26] authors have presented a way of using a genetic algorithm for path planning for

multiple drones in a 3D coordinate system. The problem was to plan the flight of drone

through some desired areas while avoiding some undesired areas. [27] have designed an

evolutionary trajectory for multiple UAVs in a military environment which can work

online as well as offline. The objective function in this paper tries to minimize the risk to

the UAV form enemy missile as well as include constraints based on drone’s dynamics and

environment. To improve the speed of path planning using a genetic algorithm, [28]

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.

A two-step optimization algorithm has been presented in [29] which finds appropriate

waypoints for the UAV and a connecting trajectory such that the total cost is low. [30] have

proposed a path planner which takes the 3D model of a complex structure an input and

outputs multiple paths of UAV for a cooperative coverage of the structure in a short interval

of time. Both the approaches have been accomplished using advanced research aerial

research platforms. The DJI drones like Mavic Pro, Phantom 4 Pro have closed hardware

i.e. these drone’s flight controller can’t be programmed. However, DJI has provided a

Software Development Kit (SDK) for these drones using which an android/Ios application

can be programmed for flight control.

 21

While solving the TSP for route optimization of drone, the main aim is the minimization

of total distance[31]. Since drones are expected to carry out long missions in the dynamic

environment of the mines, optimizing the battery consumption to extend their operation is

highly desirable. Drones are basically electric vehicles run by battery on-board. To

continue flying over the extended period of time, they need to replace batteries by coming

back to the starting point. Further, wind affects the drone flight substantially.[32] has

presented a graph signal sampling and recovery based method to design an energy-efficient

trajectory taking into account the influences of wind.

A power consumption model of UAV considering the effect of wind is necessary for

optimizing the battery performance of drone. Literature studies proposed that there are two

main approaches to power consumption models of a drone. (i) White-box model

approach: In this, a microscopic behavior model for each drone is derived from a

comprehensive study of the motor performance, aerodynamic environment, and battery

systems. Such a model requires a lot of aerodynamic parameters relating to the body of the

drone and sophisticated experimental setups. Such a model is also specific to that particular

drone[33]. (ii) Blackbox model approach: In this, a multivariate regression model for the

power consumption of a drone is derived by doing empirical studies[34]. Such a model is

more flexible and acceptable for flight mission optimization. Further, this approach is more

desirable, as it is based on parameters which are more easily measurable. This makes it

more suitable for the mining industry as most of the companies use commercial drones

which usually don’t come with a development kit[35].

 22

Genetic operators are used for changing the genetic composition of chromosomes during

the evolutionary process. The common genetic operators are Crossover, Mutation, and

Immigration. A number of crossover and mutation operators have been proposed for TSP

problems in path representation[36]. [37] have presented a comparison and analysis of

PMX, CX and OX operators. Their results concluded that PMX finds the best shortest path

among the three operators. [38] have proposed a crossover operator which is a combination

of PMX and OX operator and found to be working better than the individual operators. In

TSP, one location should be visited only once. Therefore, a standard crossover operator

should be applied cautiously and invalid offspring should be either repaired or eliminated.

[39] have presented an enhanced version of Edge assembly crossover(EAX) for solving

ATSP which maintains a better population diversity and improved solution quality.[40]

have presented an algorithm to solve TSP with precedence constraints and proposed moon

crossover operator for this. This operator has found to be working better than OX crossover

and position-based crossover. The sequential constructive crossover presented in [20]

which generate new chromosome by selecting better genes from its parent's chromosomes

is found working exceptionally well than Edge recombination crossover(ERX) and

generalized N-point crossover (GNX) in terms of results and time for some TSP instances.

[26] have presented some mutation operators like changing the sequence of points in the

parent route or swapping locations in the parent route to generate new routes in multiple

UAV flight planning problem. [36] provides a comprehensive study for crossover and

mutation operators for TSP. According to it for path representation, ER, and OX is superior

crossover operator and DM, IVM, and ISM are superior mutation operators.
 23

Chapter 3: UAV Path Planning and Optimisation

In this chapter, the approach to solve the problem has been explained. The chapter has four

subtopics(i) Accuracy assessment of drone barometer, (ii) Generating 3-D surface maps

using aerial photography, (iii) Power consumption model of a given UAV and (iv) UAV

flight planning and optimization. In the first, the accuracy of the drone parameter has been

evaluated and in the second subtopic, the procedure for creating 3-D models with aerial

images of the mine has been explained. In the last two subtopics, the estimation of battery

consumption model and the development of the path planning and optimization algorithm

has been explained.

3.1 Accuracy Assessment of Drone Barometer

DJI drones flight controller uses a combination of barometer and GPS measurement data

to estimate the flight altitude above ground. The barometer measures the height by

detecting the atmospheric pressure change while the GPS sensor is dominant in

determining the horizontal position of the drone[41]. The aim of this experiment is to

measure the accuracy of barometer in determining the height of the drone above ground.

The resolution of the images taken by the drone partially depends on the height of the drone

above ground. Therefore, to the get the required resolution of the 3D dimensional mine

maps, it is essential that the drone is flying at the adequate altitude above ground. Also, the

once the error is known and if significant, it can be accommodated into the mission

planning procedure.

The equipment used in this experiment is a tripod, Bosch GLM 42 laser measure, and DJI

Phantom 4 Pro. The tripod is used to hold the Bosch laser measure pointing in a vertical
 24

direction. The laser measure has an accuracy of ±1.5 mm and operating range of 42 meters.

It provides a real-time length, area, volume and other measuring functions[42]. DJI

Phantom Pro 4 drones have been used for this test. Figure 10 depicts the experimental setup

and a Bosch laser measure used.

The Bosch GLM 42 laser measure was mounted on the tripod such that it is exactly level

to the ground. The DJI Phantom 4 Pro hovered exactly over the laser measure at different

heights. The distance from the laser measure to the drone was recorded from the digital

display of GLM 42. The barometer reading of the drone was recorded from the altitude

values of the DJI Go App. The laser measure values and barometer values were recorded

at different heights and the errors were calculated. The wind speed during the experiment

was 4 mph and the temperature was 16° C.

4.2”

1.8”
(a) (b)

Figure 10 (a) Experimental setup, (b) Bosch GLM 42[43]

 25

A total of 78 readings have been recorded for the height values. The mean error is found

to be 30 cm. It was observed that most of the time, the drone barometer was overestimating

the heights in the range of 30-40 cm. The standard deviation of 0.65 indicates that errors

are close to the mean values. This inference is again confirmed by the plotting the

histogram of the errors. Between 60 % to 75 % of the readings are under ±40-45 cm.

Therefore, it can be concluded that in a mission, the drone can be ±30-40 cm off the desired

height.

Table 3 Descriptive statistics of result

Mean -0.302653846
Standard Error 0.073780289
Median -0.359
Mode -0.359
Standard Deviation 0.651609871
Sample Variance 0.424595424
Kurtosis 0.068558605
Skewness 0.40698046
Range 3.22
Minimum -1.589
Maximum 1.631
Sum -23.607
Count 78
Confidence Level(95.0%) 0.146915325

It has been concluded that in a mission, the drone can be ±30-40 cm off the desired height.

However, all the readings have been collected on a single day. Therefore, the effect of

weather has not been studied.

3.2 Generating 3-D surface maps using aerial photography

 26

The geometry of the pit in an open pit is continuously changing every day. To enable the

UAV to follow the terrain of the mine, updated terrain of the mine is required.

Further, the 3-D dimensional models also used by mine personnel for updating the mine

plans.

Histogram
Frequency Cumulative %
18 120.00%
16
100.00%
14
12 80.00%
Frequency

10
60.00%
8
6 40.00%
4
20.00%
2
0 0.00%
-0.3815 0.021 0.4235 -0.784 0.826 -1.1865 1.2285 More -1.589
Error(m)

Figure 11 Cumulative frequency plot of errors

A drone fitted with an image sensor has been used for collecting overlapping images of the

mine with an adequate number of ground control points. These images are then processed

in a photogrammetry software to create the surface models, contours and orthomosaic.

3.2.1 Data collection

Two open pit mines, Barrick’s Arturo and Goldstrike have been selected for data collection.

The Goldstrike Mine property is located within the northern Carlin Trend in Eureka and

Elko Counties, north-central Nevada, USA approximately 38 mi northwest of Elko and 25

 27

mi north-northwest of the town of Carlin. The Arturo pit is non-operational and Goldstrike

pit is a truck and shovel operation. The ultimate size of the Goldstrike pit will be two miles

east to west, 1.5 miles north to south, and have an average depth of approximately 1300

ft[44].

Aerial flights have been conducted over both the open pits on the same day. Ground control

points have been laid through the mine at places accessible safely which are mostly the

ramp and some benches. These points are made with survey grade spray paint with a bright

color like yellow as shown in Figure 12. The size of the x-mark is 1m x 1m. It is

recommended to put 10-15 GCPs evenly distributed throughout the surveying area. The

distribution of the surveying points is presented in Figure 13. Due to the large size of

Goldstrike pit, it is impractical to fly the UAV over the entire pit in one single day.

Therefore, only a portion of the pit has been considered. Once the points have been marked

on the ground, each of them had been surveyed using a GPS surveying equipment.

Next phase is the flight planning and execution which has been completed using the Maps

Made Easy iOS application. Figure 14 shows the UI of the application for flight planning

which allows the user to set the altitude of the flight based on the GSD. The flight altitude

once set remains constant throughout the flight. There are also options to set the forward

and side overlap required. The terrains aware option adjusts the flight height of the drone

based on the elevation of the ground. It takes the elevation data from a third-party database

which is not updated to the current geometry of the mine The blue circle denotes the

position of drone generally called the Home Point. The green and red circles are the starting

point and ending points of the planned flight respectively.

 28

Figure 12 Ground control point

Table 4 presents the flight parameters estimate of UAV flight over the pits of Arturo and

Goldstrike. The altitude is set to the maximum in order to cover as much area of the mine

as possible. Due to the large size of the Goldstrike mine, the flight time is very high, and

it took 7 batteries to fly the UAV that long. The flight also produced a high number of

images to be processed later. Once the flight has been designed, the next step is to upload

the mission to the drone and start the mission. The drone will autonomously fly the mission

over the mine. Once the battery is drained, it will come back to the home point for a battery

change. After the battery has been replaced, it will start the mission from the same point

where it is left. The line of sight to the drone (Figure 15) must be maintained throughout

the flight to maintain caution and take control in case of an emergency.

 29

(a)

(b)

Figure 13 Position of GCPs (a) Arturo pit, (b) Goldstrike pit

 30

(a)

(b)

Figure 14 (a) Setting up flight parameters; (b) Defining the area of mapping

The speed of the wind on the day of data collection was between 1-5 m/s which is within

the limit that the drone can handle. The angle of the gimbal while taking images is -

90(nadir) and images are saved on an onboard memory card.

 31

Table 4 Flight logistic for Arturo and Goldstrike pits

Arturo Goldstrike Arturo Goldstrike

Altitude
120 m 120 m Forward overlap 80 80
(AGL)
Area 50.2 hect 249.7 hect Side overlap 70 70
14.31
Max speed 9.6 m/s 9.6 m/s Flight length 68.54 km
km
Flight time 28 min 132 min No. of images 437 2012

Figure 15 Maintaining the Line of Sight during drone flight execution

3.2.2 Data Processing

Agisoft PhotoScan[45] is photogrammetric software for processing 2-D images and

generating dense point clouds, digital elevations maps, georeferenced orthomosaic and

contours. The images from the drone local memory are downloaded into a PC and loaded

in the software. The processing steps for the creation of point cloud, DEM and orthomosaic

from the collected overlapping images are shown in Figure 16. The software has been

running on a computer with 32 GB ram and Nvidia GeForce GTX 1080 graphics card.

The photos are geotagged by the drone and contain the latitude, longitude, and elevation in
 32

meters of the point where the photo has been taken. There are errors in these values due to

inaccurate GPS in drones. Their errors are minimized with the help of ground control points

which have been surveyed using mm accuracy level GPS equipment. All the default

options have used for creating the dense point cloud. This step amounts for more than 90%

of the total time. The software uses the point cloud as a basis for creating the digital

elevation model. Then the DEM is used as a basis for generating the orthomosaics. These

models can be exported in various formats like .xyz, .arcgis, .kml,. dxf etc. Figure 17.a

shows the UI of the given photogrammetry software.

Add Photos

Align Photos

Place GCPs and input coordinates

Optimise Camera Alignment

Build Dense Point Cloud

Build DEM

Build Orthomosaic

Build DEM and Orthomosiac

Figure 16 General workflow in Agisoft PhotoScan

 33

(a)

(b) (c)

(d) (e)

Figure 17(a) PhotoScan UI, (b) Point cloud, (c) DEM, (d) Orthomosaic and (e) 3D Mesh
 34

The point cloud, digital elevation map, orthomosaic and mesh model of the given mine

generated by the software have been shown in Figure 17.b, Figure 17.c, Figure 17.d and

Figure 17.e respectively. The respective resolutions and processing time have been shown

in Table 5. The resolution of the created models is generally equivalent to that of the input

images and processing time as evident depends on the number of images.

Table 5 Photogrammetry outputs

Model Resolution Processing time

Arturo Goldstrike Arturo Goldstrike
Point cloud 67.5 pt/m2 40.7 pt/m2 3 hours 42 m 31 hours
Digital Elevation Maps 12.2 cm/pix 15.7 cm/pix 2 min 8 sec 1 min
Orthomosaic 6.09 cm/pix 7.84 cm/pix 10 min 39 sec 14 min 56 sec

3.3 Power consumption model of Drone

As discussed in Ch.2, the black box model approach has been used for the estimation of

the energy consumption model. In a drone, most of the battery is the black box the black

box model approach has been used for the estimation of the energy consumption model. In

a drone, most of the battery is the black box model approach has been used for the

estimation of the energy consumption model. In a drone, most of the battery is consumed

in powering of motors to lift the UAV body in the air. Further, energy is used in the

movements of UAV in the air.

3.3.1 Empirical Studies

This sub-section describes the experiments conducted for studying the performance of the

battery when the drone flies in different directions and wind speeds. Any drone has three
 35

main motions: hovering, horizontal moving and vertical moving. A flight of a drone is a

combination of these three motion types. To measure the rate of power consumption during

these motions, multiple experiments are conducted. In each experiment, the drone is

programmed to ascend and descent repeatedly at its maximum speed in a vertical direction.

Then, it is moved horizontally without altering its altitude at maximum speed. The drone

speed relative to ground in vertical and horizontal directions, battery power, barometer

readings are collected during each of the above experiments to study the performance of

the battery of DJI Mavic pro. Since the drone is not compatible with any development kit,

data has been derived from the log files of mission planning software UGCS[46]. The wind

speed and directions are also recorded using wind speed meter for these experiments.

Figure 18 depicts the recorded data of the above experiments of the test drone DJI Mavic

Pro. The barometer data shows the altitude of the drone. Acceleration in the vertical and

horizontal direction has also been calculated from time series data. During vertical

movements, the drone was slightly deviating from the straight path during errors in the

GPS modules. Similarly, during the horizontal motion, the UAV wasn’t exactly moving

horizontally due to barometer errors. However, these deviations have been less than 0.1m

and therefore neglected.

It has been observed that the power consumption steadily increases as the drone ascends

and decreases as it descends. During these motions, the drone also accelerates to reach its

maximum speed in a vertical direction. The horizontal speed data generated due to GPS

errors has been filtered. During the horizontal motions with constant altitude, the power
 36

consumption is relatively stable. The power consumption between the two motions has also

been recorded which account for the hovering motion.

fc:altitude_raw vxy vz power

40 200
Vertical motion Horizontal motion
35 180

30 160
Altitude(m) and Speed(m/s)

25 140

20 120

Power(W)
15 100

10 80

5 60

0 40
658 1158 1658 2158 2658 3158 3658 4158 4658 5158 5658
-5 20

-10 0
Time x 10-1 (sec)

Figure 18 Battery power consumption of DJI Mavic pro with different motions
Drones are electric vehicles like many other ground electric vehicles but being aerial they

face distinctive challenges. To elaborate, the wind is a major environmental factor to affect

the power consumption in Mavic Pro during the experiments. Therefore, another set of

experiments have been conducted to model the performance of the battery when the drone

flies in the same direction as wind and vice versa repeatedly. The speed and the direction

of the wind have been recorded with windspeed meter. The frequency of wind

measurements is 2s. The flights were made at a local park in Reno but on different days to
 37

consider the different wind speeds and make the study more comprehensive. The drone

was made to fly closer to the ground to minimize the error in wind measurements due to

elevation differences between windspeed meter and drone. The average wind speed of each

flight has been used as a representative speed for the entire flight. The experiments have

been conducted for three wind speed cases 17.28 km/hr,18 km/hr and 19.8 km/hr. From

Figure 19, it can be concluded that for DJI Mavic pro, the power consumption steadily

increases when it flies in headwind direction and decreases in the tailwind direction.

However, the relation is not linear. According to the aerodynamics, when flying into the

headwind, the power consumption slightly decreases due to the relative airflow over the

propellers increases and hence the translational lift increases. However, at higher wind

speeds, the aerodynamic drag could outweigh the translational lift. In our setting, the drone

is flying at its maximum speed and hence flying into the headwind is adding more drag to

the aircraft leading to more power consumption.

3.3.2 Regression model of Power consumption for DJI Mavic Pro

The data collected as described in the previous section was used for deriving the

coefficients of a multivariate linear regression model which is given below. The regression

analysis has been done in Minitab[47]. The estimated battery power consumption power is

denoted by P and is given by:

𝑣𝑥𝑦 𝑎𝑥𝑦
0.9 𝑇 −0.764 𝑇
2 2
0.048 𝑣𝑥𝑦 0.006 𝑎𝑥𝑦
P=103.67 + [ ] 𝑣𝑥𝑦 . 𝑎𝑥𝑦 + [ ] 𝑎𝑥𝑦 . 𝑎𝑧 +
0.204 −0.505
0.128 [𝑣𝑥𝑦 . 𝑤𝑖𝑛𝑑 ] 0.034 [𝑎𝑥𝑦 . 𝑤𝑖𝑛𝑑 ]
 38

−2.54 𝑇 𝑣𝑧 −2.493 𝑇 𝑎𝑧
−2.359 𝑣2 −0.016 𝑎2
[ ] [ 𝑣 .𝑧𝑎 ] + [ ] [ 𝑧 ]
1.167 𝑧 𝑧 −0.075 𝑤𝑖𝑛𝑑
1.987 𝑣𝑧 𝑤𝑖𝑛𝑑
. −0.08 𝑤𝑖𝑛𝑑 2

Where

• 𝑣𝑥𝑦 and 𝑎𝑥𝑦 are the speed and acceleration vectors in the horizontal

direction.

• 𝑣𝑧 and 𝑎𝑧 are the speed and acceleration vectors in vertthe ical direction.

• 𝑤𝑖𝑛𝑑 is the wind vector in the horizontal direction.

If the wind and speed are considered constant, the total energy consumed within a flight

with duration T can be estimated by P. T

130 17.28 km/hr 19.8 km/hr

125 Headwind Tailwind Headwind

120

115

110
Power (W)

105

100

95

90

85

80
700 800 900 1000 1100 1200 1300 1400 1500 1600 1700
Timex10-1 (sec)

Figure 19 Battery power consumption of DJI Mavic Pro under different wind conditions
 39

3.3.3 Model Validation

Another test flight has been conducted for validating the accuracy of the power

consumption model. The same DJI Mavic Pro has been used for conducting another set of

experiment. It has been programmed to fly in the vertical direction with maximum capacity

repeatedly and then horizontally in headwind and tailwind direction with maximum speed.

The wind speed is 5.76 km/hr during this period of flight. The velocity vectors have been

recorded and accelerations have also been calculated from the time series data in horizontal

and vertical directions. These estimated values of 𝑣𝑥𝑦 , 𝑎𝑥𝑦 , 𝑣𝑧 , 𝑎𝑧 and 𝑤𝑖𝑛𝑑 are input into

to the regression model, to get the modeled power data. This data is then compared against

the measured power data.

It has been observed that the average error of estimation is 0.7% with the standard deviation

of 0.11. Since the final goal is to optimize the entire flight of the drone, a total energy

consumption of the flight has been estimated which can be shown in Figure 20. The model

can accurately predict the energy consumption of the drone at a wind speed of 5.76 km/hr.

The error in estimating the total energy consumed at the end of the flight is 0.6 %. With

respect to the trend, the model is also able to capture the trends of power consumption with

respect to the wind speed and direction of movement. Both Figure 20 and Figure 21 depict

the good accuracy of the power consumption model for DJI Mavic Pro. This approach can

also be repeated for any other commercially available drone.

3.4 Flight mission planning and optimization

 40

180
power model
160

140

120

100
Power (W)

80

60

40

20

0
0 500 1000 1500 2000 2500
Time x 10-1 (sec)

Figure 20 Measured and modeled energy consumption for DJI Mavic Pro

Energy model ener 400000

350000

300000

250000

200000 Energy(J)

150000

100000

50000

0
0 500 1000 1500 2000 2500
Time x 10-1 (sec)

Figure 21 Measured and modeled energy consumption for DJI Mavic Pro
 41

This section describes the utilization of the energy consumption model of DJI Mavic Pro

from the last section to investigate the problem flight mission planning and optimization.

The objective is to fly through a set of the point with minimum power consumed. A real

mine case study has been developed by using the mine geometry from Barrick’s Arturo pit.

This methodology is also applicable in case of other applications of drones in open pit

mines like dust and noxious gas measurements.

3.4.1 Mine Bench centrelines

The availability of accurate 3D models of Barrick’s Arturo pit makes it an ideal choice to

be chosen for path planning simulation. On the point cloud model generated in previous

sections, some randomly selected bench centrelines have been drawn manually as shown

in Figure 22. These lines are then exported to Surpac[48] in a .dxf format for further editing.

In Surpac, the centrelines have been elevated from the ground by 36.75 m in z-direction

using the “maths function” to get the required resolution of images which is 1.27 cm. To

get a minimum forward overlap of 80% between successive images along a bench, the

maximum distance between two consecutive points has been restricted to 7.6 m. There is

a total of 373 contiguous points for four benches as shown in Figure 23 which are then

inputted to a genetic algorithm to find the optimum sequence in the tour.

3.4.2 Model formulation

In the given optimization problem, the optimum path should start and end at the same

starting point ensuring that the drone returns to the take-off location after flying the mission
 42

and each point on the path should be visited only once. This problem can be formulated as

a linear integer programming problem as

1, 𝑖𝑓 𝑖, 𝑗 𝑎𝑟𝑒 𝑝𝑎𝑟𝑡 𝑜𝑓 𝑑𝑟𝑜𝑛𝑒 𝑡𝑜𝑢𝑟

Minimize ∑𝑛𝑖,𝑗 𝐶 𝑥𝑖𝑗 , where 𝑥𝑖𝑗 = {
𝑖𝑗 0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Subject to constraints

∑𝑛𝑖=1 𝑥𝑖𝑗 = 1 𝑓𝑜𝑟 𝑗 = 1,2 … … 𝑛

∑𝑛𝑗=0 𝑥𝑖𝑗 = 1 𝑓𝑜𝑟 𝑖 = 1, 2, 3, … … . . 𝑛

∑𝑖,𝑗 𝑥𝑖𝑗 ≤ |𝑆| −1 ∀ 𝑆 ∁ 𝑉,𝑆 ≠0

𝐶𝑖𝑗 is the energy consumed or cost for the drone to move from waypoint I to j. The first

equality constraints that each point be visited from only one point and the second equality

ensures that only one point can be reached from a given point. Both these constraints

confirm that each point is visited exactly one in the tour. The last constraint prevents the

occurrence of any sub tours in the final solution.

3.4.3 Genetic Algorithm

Genetic algorithms are based on Darwin’s theory of evolution which states that the survival

of an organism is defined by “survival of the fittest” rule and was developed by

Goldberg[49]. As discussed in chapter 2, these algorithms have been presented in the past

to solve UAV path planning and optimization problems. In our case, we are trying to use

these algorithms to minimize the energy consumed in each path as well as fulfill the

constraints of a traveling salesman problem. Instead of using a simple distance function as

 43

in a typical TSP, an energy consumption model of the drone has been used in the fitness

function. Figure 24 presents the general flow of the proposed algorithm and the main

components of it are discussed in further sections

Figure 22 Creating centerlines on mine benches

Figure 23 Bench centerlines as series of contiguous points

 44

Generate the initial population randomly

Calculate the penalty, fitness and probability

values of individuals in the current
population

Repeat
until the
Select good individuals from population iteration
through roulette wheel number

Obtain a new generation using mutation

operators

Determine the best individual as solution and

terminate the algorithm
Figure 24 Proposed genetic algorithm

3.4.3.1 Fitness Function

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:

Fitness Functions = ∑𝑛𝑖, 𝑗 𝐸 + 𝛼𝜃𝑖,𝑗,𝑘

𝑖,𝑗

Ei,j is the energy consumed by the UAV in moving from i to j and 𝜃𝑖,𝑗,𝑘 is the vector angle

between i, j and 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
 45

sharp turns are desired, then the value of α should be input low and if the sharp turns are

not desired then it’s value should be considered high. There are two cost matrices to be

estimated. First, the energy matrix in which each element Ei,j is the energy consumed in

moving between i to j. This matrix is an asymmetric matrix as Ei,j ≠ Ej,i because the power

consumed when the drone is moving in upwaan rd direction is not samethe as when it is

moving in downa ward direction. It has been assumed that the UAV moves with a uniform

velocity between two points except for a 0.1s acceleration and deceleration in when it

leaves a waypoint and reaches next waypoint respectively.

These conditions have been considered because the UAV must stop at each waypoint

before taking the photo. In order to capture images while the drone is moving, a study needs

to be done to find out the speed of the drone with respect to the ground sampling distance.

If the distance traveled by the drone during the time its camera’s shutter is open is more

than the ground sampling distance, then the images captures are smeared. Smeared images

cause poor photogrammetric results in the Agisoft PhotoScan and therefore need to be

avoided. Such a study is also out of the scope of this project. The asymmetric cost matrix

makes this problem a case of asymmetric tsp which takes a longer time than normal tsp.

Second, the angle matrix is a 3-dimension matrix with each element 𝜃𝑖,𝑗,𝑘 is the vector

angle between i,j and j,k. These matrices are estimated before the algorithm starts running.

The fitness of a route is being interpreted in an inverse way such that routes with lease

fitness values are better than routes with more fitness values. The aim is to select individual

routes which consumes less power and has a smaller amount of turns.

3.4.3.2 Structure of chromosome

 46

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 called Path Representation and possibly the most natural

representation of a tour[36]. This representation also facilitates the use of many popular

genetic operators like PMX, cycle crossover, order crossover and genetic edge

recombination crossover (ER). Each chromosome should contain all the points in it so that

all the points are visited by the UAV. Further, each waypoint should occur in a

chromosome exactly once so that the UAV would visit each point only once. This

chromosome structure has been implemented such that the drone, after visiting all the

waypoints, will return to its initial starting point. Therefore, the first and last gene in every

chromosome should be entered same depending on the location selected as a start point.

In Figure 25, a sample chromosome used in GA has been presented. The label “1”

represents the mission initiating point and to enable the drone to return to the same point

after completing the mission the last label has been set up as “1”. If the waypoint i is at the

j-th position in the chromosome, then waypoint i is the j-th point to be visited. In a GA, the

generation of an initial population of chromosomes is one of the most important tasks. It

affects how quickly you can find the best solution. Conventionally, the initial populations

are generated randomly for GA.

1 5 12 16 2 20 23 7 25 1
Figure 25 Route representation scheme
3.4.3.3 GA Operators
 47

GA operators are used for generating a new population from the previous population. It is

necessary to select parent chromosome from the previous generation to generate a new

generation. Two important factors should be considered by implementing a parent selection

strategy. First, reproductive opportunities should be allocated to each individual

chromosome during parent selection. Secondly, more opportunity should be provided to

better cost chromosomes than the lower cost to generate new children[50]. Tournament

selection and roulette wheel are the two main types of selection strategies. Tournament

selection has been used as a parent selection strategy in the proposed algorithm due to its

ease of implementation and efficiency [51].

Once the parents have been selected, the offspring have to be generated by crossover and

mutation operators. There are three mutations operator used in the proposed algorithm:

Flip, Swap, and Slide. The flip operator reverses the sequence of the waypoints to be visited

in the parent tour to generate new offspring tour as shown in Figure 26. In this figure, two

random points are selected in the parent route(Figure 26.a) and sequence of genes in

between these points are reversed to produce the output route(Figure 26.b).

1 5 12 16 2 20 23 7 25 1
(a)

1 5 12 23 20 2 16 7 25 1

(b)
Figure 26 Flip operation (a) Parent (b) Offspring
 48

2 2
0 0
2 2
7
3 3
7

1 2 1 2
2 2

1 1
6 6
(a (b
) )

Figure 27 Demonstration of flip operator (a) Parent route (b) child route

The swap operator swaps the position of waypoints in parent tour to generate new offspring

tour as shown in Figure 28. In this figure, two random points are selected in the parent

route(Figure 28.a) and positions of these genes are swapped to produce the output

route(Figure 28.b). In Figure 29, the operator has been shown in action. It can be clearly

seen that the output route is better than the input route.

1 5 12 16 2 20 23 7 25 1
(a)

1 5 12 23 2 20 16 7 25 1
(b)
Figure 28 Swap operation (a) Parent (b) Offspring
 49

2 2 2
2 3
3 0 0

1 1
2 2
1
1 2
6
2
6
7 7

(a (b
) )

Figure 29 Demonstration of swap operator (a) Parent route (b) child route

The slide operator chooses two positions randomly in the parent tour. It removes the

waypoint at first position, shifts the waypoint between two positions one position backward

and places the first position waypoint at second positions as shown in Figure 30. The input

and corresponding output route for this operator can be seen in Figure 31. The mutation

operators apart from producing better solutions also help the algorithm in escaping local

minima.

1 5 12 16 2 20 23 7 25 1
(a)

1 5 12 2 20 23 16 7 25 1
(b)
Figure 30 Slide operation (a) Parent (b) Offspring
 50

2 2
3 2 3
2
0 0
2 2

1 1 1
2 1 6
2
6
7 7

(a (b
) )
Figure 31 Demonstration of slide operator (a) Parent route (b) child route

3.5 Results

A case study has been developed by deriving the centrelines of benches for local mine in

Nevada. Once the centrelines have been extracted using Surpac by digitizing the strings

between two contours of the mine. The centrelines are then elevated further 36.75 m above

the ground as the required resolution for the images is 1.27cm. These centrelines are then

fed to the GA for finding the optimum path. Currently, the algorithm has mutation

operators like swap and flip. For 317 points length path, the program is taking 15 minutes.

As much as 60% of the times goes for calculating the initial distance matrix and search

matrix. The parameters of the GA are depicted in Table 6. 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 at 100,000 dues to the complexity of the

problem and to ensure that the solution is as near-optimal as possible.

 51

At maximum iteration, the best solution amongst the current population of 100 is chosen

and output as the optimal path from the algorithm. It has been observed in the experimental

studies that the best route planned by the algorithm is very close to the optimal route as

shown in Figure 32. However, on an average, the solution provided by the proposed

algorithm is almost double the optimal solution. An example of the optimal solutions has

been presented in Figure 33. It can be seen that the mission start and end points have been

fixed as the first waypoint from the topmost bench. There are some problems with the

current version of GA like it has a long running time making its online deployment difficult.

Further, it requires some adjustment in the weights in the cost function to prevent the

jumping of the path from one bench another and reach more near to the optimal solution.

Table 6 GA parameters

Parameter Values
Population size 100
No. of iteration 100,000
Operator Mutation
Stopping criteria Max. Iteration

3.6 Conclusion

The traditional crack monitoring systems through instrumentation are laborious, expensive,

unsafe, and limited only to the accessible parts of mines. Even for the sophisticated radar

and laser scanning technologies, it is not possible to localize and monitor tension cracks

effectively. As a new methodology, application of drones (UAVs) is studied for

imaging/mapping of open pit mines and use machine learning techniques for identification
 52

and characterization of tension cracks. For the purpose of accurate detection of tension

cracks, a crucial bottleneck is the availability of high-resolution images/models of the mine

benches. This paper presents several contributions to the field of remote sensing of open

pit mine slopes using UAV.

Geo-referenced three-dimensional models of a mine can be generated from the nadir aerial

imagery with resolution comparable to other scanning methods. Resolution of the

generated point cloud and ortho-mosaic from the first stage flight is not sufficient to be

used for measuring tension cracks. Resolution of the models can be increased by increasing

the size of image sensor resolution or decreasing the flight altitude or both. Therefore, a

second terrain-aware flight has been planned for getting high-resolution images. The

weather conditions and position of the sun during the flight need to be considered while

planning the workflow of the future flight. Due to the large size of mine areas, it is essential

to calculate the number of fully charged UAV batteries required before the flight execution.

Empirical studies have also been performed to model the battery performance of a test

UAV considering various flight circumstances. A linear regression model for the power

consumption of the drone has been derived and validated for a test scenario.

Further, an optimization algorithm has been proposed to solve the problem of path planning

and outputs a path which consumes least battery power. A case study based on an open pit

mine from Nevada has been presented. The algorithm has been tested to find out the

optimum path for high resolution imaging the benches of the given mine. It is safe to
 53

conclude that the proposed algorithm can generate tours which are near-optimal

considering the stochastic nature of the algorithm.

In the future, an appropriate crossover operator will be implemented for fast convergence

and improved results. The algorithm will be further evaluated in case of different wind

speed and directions. The proposed algorithm can also be studied for online

implementation to maximize the area mapped in a mine with one single battery of the UAV.

Considering the huge size of open-pit mines, the algorithm can also study to be

implemented for the case of path planning for multiple drones.

Optimum Best Average Worst

250
201
200
159
150

96
100 80

50

0
Run time=15 min

Figure 32 GA evaluation results

 54

Figure 33 Optimum path from the current version of GA

 55

Chapter 4: Android Application: Development and deployment

In this chapter, the development and working of an android flight control application have

been explained. For this application, Android studio 3.1.4[52] has been used a developing

environment, DJI Android SDK[53] has been used for interaction with UAV’s flight

controller and Google Maps Platform’s Maps API[54] has been used for navigation. The

latest versions of all three kits have been downloaded 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. Test platform has been defined in Table 7.

Table 7 Test platform properties

Properties Values
CPU MediaTek MT8163 V/B 1.3 GHz
RAM 2 GB
Operating system Android 6.0 (Marshmallow)
Screen size 8 inches
GPS Yes

The initial interface of the application has been designed as shown in Figure 35. The

Application has been designed to import the 3-D terrains models from Photoscan as a

reference for the user. Further, it will allow the user to plan and edit mapping operations

based on the imported terrain. Then the user can further set the speed, altitude, return home

commands and more. The application then uploads the path to the drone controller which

will execute the mission (Imaging of the benches) and bring the drone back to its initial

launch position. The images taken by the drone during the mission will be uploaded to the

server where it will be processed for the next stages. The workflow of the App is shown in

Figure 34.
 56

Figure 34 Workflow of designed application

4.1 Connecting the App to the drone

First, it is ensured that the DJI firmware on the drone and its remote controller are updated.

Then, start the drone and remote controller and let them initialize for a few seconds.

Connect the remote controller to the tablet using a USB cable. Then, a popup will ask which

app to start, select “DJIApp” in the popup to initiate the connection. Once the connection

is initiated, open the “DJIApp” from the Tablet menu and the first interface app as shown

in Figure 35 will be running. The status indicates the connection status between the app

and the drone. The name of the DJI drone is indicated and even the DJI SDK version is

shown. The flight planning interface of the app can be opened by pressing the “OPEN”

button.
 57

Figure 35 Connection status screen of the App

4.2 Mission Planning Mode

Since the application has been developed using an official DJI SDK, the App supports all

the DJI drones. Mission planning mode allows the user to set up the traditional missions

as well as advanced monitoring missions.

a) Status Bar: on the top shows the number of satellites available to the drone at the given

location, the flight status, battery remaining of the drone, uplink, and downlink

strength.

b) Import DEM: It allows the user to import the digital elevation model of the mine site

in .json format. It can also present the model on the map with pixel colors based on

elevation as shown in Figure 37.

 58

Status Bar
Start
Import the DEM
Terrain
Stop
Focus on drone location Upload
aware
Start/Pause mission
Settings
Import orthomosaic/
Clear
Take
Go Home
off Camera
Telemet feed

ry
Figure 36 Mission planning mode

Figure 37 Imported DEM of Arturo mine

 59

c) Terrain-Aware: This is a switch to enable the user to plan a terrain-aware flight based

on the elevation values from an imported terrain. There are two ways in which the

elevation values can be imported: Digital elevation maps and Contours. Contours are

useful because mine personnel always has the updated contours of the mine. So there

is no need of the first stage of flight to get the updated mine terrain.

d) Focus on drone location: Due to the vast size of mines, it is important to refocus the

map on the drone location at the start or during the mission. It also helps to track the

movement of the UAV during flight.

e) Start/Pause mission: The mission can be started and stopped using this button.

f) Import orthomosaic: To aid the mine personnel in flight planning based on the up to

date geometry of the mine, a terrain import function has been programmed into the

application. Using this feature, the user can import and present the mining model on

the map as shown in Figure 38. The user can zoom in and out of the map to take a

closer look. The resolution of the imagery of the mine is 2048 x 2048 pi. This feature

can also be used for monitoring of the mine operations. Further, it can be used for

remote inspection of benches and blasted muck pile. During blasting, it is very useful

to estimate the range of flyrocks and this feature can be used for the remote survey of

the entire area. Mine contours can also be imported as shown in Figure 39 if the mine

imagery is not available. The position and orientation of the imported maps on the

google maps are validated in Figure 40 as the bench contours are exactly overlapping

the mine bench in the model.

 60

Figure 38 Imported map of Arturo mine

Figure 39 Imported contours of Arturo mine

 61

Figure 40 Imported contours overlapping on mine model

g) Take off: The aircraft will take off the ground and hover at 1.2 m.

h) Go Home: Allows the user to land the aircraft at the home position in the middle of the

flight autonomously. The Go Home altitude can be adjusted by the user. If there is an

emergency during the flight like not enough battery left, high-speed winds, rain or

snow, the user can call the UAV back to the home point.

i) Start mission: Once the waypoint mission has been uploaded to the drone, the UAV

can initiate executing it with this button.

j) Stop mission: The user can stop the mission by using the Stop button. The aircraft will

stop the ongoing mission and will start hovering at the same place. It can then either be

controlled by RC or another mission can be uploaded to it.

k) Upload: Once all the mission planning and setting has been completed and checked, it

can be uploaded to the aircraft. A maximum of 99 waypoints mission can be executed

 62

at a time due to the storage limit of DJI controllers onboard the DJI drone. This limit is

valid for all the DJI drones.

Figure 41 Waypoint mission configuration

l) Mission settings: It corresponds to the configuration of waypoints in a mission in terms

of their altitudes, speed and other settings(Figure 41). The Altitude above ground for

the mission is input in the Altitude field. This altitude decides how high above the

ground the drone will fly. Therefore, this altitude decides the ground sampling

resolution of the images taken during the mission. Further, if the terrain-aware switch

is enabled, then the drone will adjust its elevations to maintain the set altitude over

undulating terrain, else it will just fly at the set altitude based on the elevation at home

point. So, when the terrain following is not enabled, it is necessary to ensure the set

altitude is more than the height of nearby structures. There are three options for speed

mainly: low, medium and high. The values for which are 3m/s, 5m/s and 10 m/s
 63

respectively. It is advised to fly at low or medium speed to prevent the smearing of

images during photogrammetry missions. There are options to tell the UAV what to do

once it’s done executing the mission like Hover, land autonomously at the last

waypoint, come back to the home location or go back to the first waypoint.

It is better to decide to bring the home back to the home point after the mission due to

two reasons (i) To check the condition of drone for any damage to part or camera; and

(ii) To check quality of the images taken by the drone during the mission and ensure

whether to repeat the mission or not. The heading of the drone during the mission can

be set by the last option. The “auto” option always sets the heading towards the next

waypoints during the mission. The “initial” option sets the heading as the initial

heading of the drone through the mission. The heading of the drone during the flight

can be controlled by the remote controller manually with “RC control” option. In “use

waypoint”, heading during the mission will same as the first waypoint. In a mapping

mission, it is necessary to point the drone towards the next waypoint otherwise there

won’t be the required overlap between successive images. To ensure that there is

always the required overlap between images, the forward and side overlap has been set

80 %.

m) Delete waypoints: The waypoints can be cleared from the screen by using this button

or a mission can be erased by this icon. It will also remove any imported overlay like

mine images, contours over the google maps.

 64

n) Drone Camera Feed: This window telecasts the live video feed from the drone camera

as long as the drone and the tablet are connected. It also shows the images the drone is

taking while executing a mission.

o) Drone Telemetry: It is one of the most important panels as it depicts the live telemetry

information like altitude above ground, speed, and distance of the drone during a

mission. The AGL (Above Ground Level) altitude is basically calculated as the height

of the drone above the take-off location/home location.

4.3 Parallel Flight Planning

Parallel Flight is a way of UAV mission trajectory such that the area to be mapped is

covered by parallel passes to be followed by the drone during the mission as shown in

Figure 42. It shows a mapping mission for a small area of the pit over the benches. The

distance between the passes is determined by the side overlap. Along each pass, waypoints

are calculated such that the distance between successive points is determined based on

forward overlap. As discussed in chapter 2, Equation 1 and 2 have been used for

determining the position of the waypoints.

Figure 43 shows the designed algorithm for calculating the UAV Flight for mapping a

polygonal area. The input to the algorithm is a user-drawn polygon which is the black

outline polygon and the output the path for the drone mission which is red colored polyline

depicted in Figure 42. The red colored dots with blue outline are the estimated waypoints

where the UAV has to take images vertically downward (Gimbal pitch = -90°). The speed,

altitude, and heading of the drone can be set by the mission config button. With the terrain-
 65

aware option enabled, the UAV can be able to follow the terrain as it takes the pictures

maintaining a constant altitude with the ground. The UAV will travel at the set speed

between the waypoints and will stop at each waypoint to take pictures.

Figure 42 Illustration of parallel flight planning

4.4 Polygonal Flight Planning

The current open pit mines have a large size and polygon shapes. The shape of the mine

can be assumed to be like an inverted polyhedron as the depth increases the perimeter of

the bench becomes smaller. From the empirical studies, it has been found that a UAV

consumes less energy going downward than it takes while going upward. Keeping into

account all these facts, a novel flight planning technique has been designed called

“Polygonal Flight Planning”. In this, an offsetting of a user-drawn polygon is done in an

inward direction such that the offset distance is based on side overlap. After this, waypoints

are estimated along the edges of the polygons such that the distance between two
 66

successive waypoints based on forward overlap. Figure 44 depicts the algorithm in action

where it is estimating the polygonal flights for a small section of Goldstrike mines.

Start

Input: User
polygon

Calculate a surrounding rectangle using min. and max.

latitude and longitude as coordinates

Calculate the waypoints along the width and height of

given rectangle

Create a grid of points using the above points

Filter out the points outside the user polygon

Output:
parallel path

Stop

Figure 43 Parallel Flight planning algorithm

[55] presented a simple algorithm to estimate the offset polygon using winding numbers.

In this algorithm, a raw offset curve is calculated for an input polygon and then wind

number is estimated for each connected region. The regions with non-positive winding

numbers are invalid and removed giving an offset polygon. The implementation of this
 67

technique in an Android environment has found to be sophisticated. Therefore, based on

this technique a new algorithm has been designed to find the offsetting polygons.

Figure 44 Illustration of polygonal flight planning

In the algorithm presented in Figure 45, first each edge of the user drawn polygon is offset

to its normal direction by the offset distance s. The value of s is based on a percentage of

side overlap. The offset segments have the same orientation as the original edges. Then,

the vertices of the inner offset polygon are determined by estimating the intersection points

of adjacent segments as shown in Figure 47. Next, the waypoints are calculated along each

edge of the offset polygon such that distance between adjacent points is forward overlap.

The above process of offsetting polygons is repeated until the condition described by

Equation 5 is satisfied. The above condition ensures that the entire polygonal area is

mapped by the overlapping images and no unmapped area is left at the center of the smallest

polygon.
 68

½ x (Ground area covered by 1 image) x ≤ Area of polygon ( 5)

(No. of edges of the polygon)

Start

Input: User
polygon

Determine the offset edges

Determine the vertices of offset polygon

Estimate the waypoints along offset polygon

More offsetting Yes Is previous Yes

required? polygon valid?

No No

Output: path Repair

Stop

Figure 45 Polygonal flight planning algorithm

 69

Once it is decided to construct an offset polygon, its validity needs to be checked. A

polygon is said to be valid if it is not self-intersecting. In a self-intersecting polygon, the

boundary of the polygon crosses itself and this will generate more self-intersecting

polygons. Therefore, it needs to be repaired. It has been observed that a pair of alternate

edges intersects to give the point of self-intersection. For correcting it, that point of self-

intersection is considered as the new vertex and edge between the then given pair is

removed. This process has been shown in Figure 46.

It can be observed that in the repairment process, some area near the vertices might not get

covered during the imaging process. However, it can also be observed that such case arises

when one edge of the polygon is much shorter than other edges relatively. Due to the large

size of mining operations, such cases are rare to be confronted. Further, this algorithm is

also compatible with concave polygons. The direction in which the user draws the polygon

doesn’t affect the working of the algorithm.

Self-intersection

point

(a) Invalid (b) Repaired

polygon
Figure 46 Repairment process
 70

(a) Offset each edge (b) Connect intersection points

to get offset polygon

(c) Waypoints along offset polygon

Figure 47 Constructing offset polygon and waypoints

4.5 Deriving elevations from DEM

With the geometry of the mine changing every day, it is very important that the drone is

aware of the terrain to prevent crashes into the wall especially while imaging the benches

for crack detections. The presented application can import the terrain i.e. Digital Elevation

Model of the mine in. JSON format and adjust the flying altitude of the drone based on the

elevation values extracted from the imported model.

A novel algorithm has been designed for extracting the elevations values in the most

efficient way. The Algorithm 1 starts with importing latitudes, longitudes and elevation

values from the DEM. A map called “dem” is created with these values such that for each

lat and long pair, there is an elevation value. A grid of lat, lng is created by sorting demLat
 71

and demLong and then removing all the repeated values in demLat and demLong.

LATLNG_BOUNDS() takes all the vertices of the polygon P and output the maximum

latitudes and longitudes, minimum latitudes and longitudes values among the vertices.

These values are then searched in the Lat, Lng grid using the Algorithm 2. This process

makes the actual search area small and equal to the area of user polygon.

Search
User

Polygo

DEM

Waypoints

Elevation

values from
Figure 48 Extraction of the z values from imported DEM

In the second part of the algorithm, for each waypoint, a search box is being defined of the

size 10m x 10m. The bounds of this search box are found using the LINEARSEARCH()
 72

method. These bounds are used to find the elevation values which fall inside the search

box. The average of these values is taken and assigned as elevation for that waypoint. This

process is repeated until elevations for all the waypoints have been calculated.

Algorithm 1: Elevations_Extraction
1. Input: DEM, user polygon P and waypoints
2. Initialize Map dem[K,V] ← DEM
3. Initialize demLat ← Latitudes, demLong ← Longitudes
4. Initialize Grid: arrLat x arrLong, elevations ← waypoints.size()
5. {Minlat, Maxlat, Minlon, Maxlong} ← LATLNG_BOUNDS(P)
6. IndexboundsLat ← LINEARSEARCH (arrLat, Minlat, Maxlat)
7. IndexboundsLong ← LINEARSEARCH (arrLong, Minlon, Maxlong)
8. for i ∈ IndexboundsLat do
9. Lat.add(arrLat[i])
10. end for
11. for i ∈ IndexboundsLong do
12. Long.add(arrLong[i])
13. end for
14. Initialize i ← 0
15. for i < waypoints.size() do
16. {minlat, maxlat, minlong, maxlong} ← SEARCH_BOX (waypoints[i])
17. if minlat > Lat[0] && maxlat < Lat[Lat.size-1] then
18. latbounds ← LINEARSEARCH (Lat, minlat, maxlat)
19. end if
20. if minlong > Long[0] && maxlat < Long[Long.size-1] then
21. longbounds ← LINEARSEARCH (Long, minlong, maxlong)
22. end if
23. for j ∈ latbounds do
24. for k ∈ longbounds do
25. temp.add(dem.get(Lat[j], Long[k]))
26. end for
27. end for
28. sum ←0
29. for k : temp do
30. sum += k
31. end for
32. if temp.size ≠ 0 then
33. elevations[i] = sum / temp.size()
34. end if
35. end for
36. Output: elevations

4.5.1 Validation of an algorithm

 73

The presented approach has been implemented in JAVA as a functionality in the given

android application. The test flight has been designed over the Barrick’s Arturo pit and the

DEM of the same pit has been used. Due to the large size of the file, the resolution of the

imported DEM has been set to 1m.

A total of 10 waypoints have been selected from the path to evaluate the working of this

algorithm. The values of elevations computed by the algorithm for each waypoint have

compared against the actual elevation at that waypoints. The actual values have been found

using UGCS software. The errors which are the absolute difference between the actual and

estimated values have been found. The error has a mean value of 0.55 m and a standard

deviation of 0.7. For the purpose of crack detection, the UAV will be flying at the altitude

of 30-40 m above ground and therefore an average error of 0.5 m with a standard deviation

of 0.7 is acceptable. The maximum error in the estimation is 1.6 m (Figure 49). The error

could be introduced due to change in resolution of DEM when it is imported inside UGCS

software. Further, the errors can be minimized by increasing the size of the search box or

increasing the resolution of the DEM. If the resolution of DEM is increased, the number of

points inside it will be increased. This will increase the running time of the algorithm. It is

basically a trade-off between speed and accuracy.

4.6 Deriving elevations from Contours

Mine contours can be easily obtained from the CAD model of the mine. This helps to

eliminate the first stage of flight which consumes a lot of time and energy. Therefore, a
 74

feature has been added to this application in which it can import contours in .kml format

and extraction elevations from these contours for the waypoints.

estimated actual error

1605 2
1.62425 1.576
1600
1.25 1.5
Ground elevations(m)

1595
1
1590

Error(m)
0.43975 0.513
1585 0.297 0.2475 0.5
0.1245
0.02475
1580
0
1575 -0.51225
-0.5
1570
1565 -1
1 2 3 4 5 6 7 8 9 10
Waypoints

Figure 49 Errors in estimation of elevations

Algorithm 2: LINEARSEARCH (arrLat, Minlat, Maxlat)

1. Input: arrLat, Minlat, Maxlat
2. Initialize n ← arrLat.length; i ← 0; j ← 0; Idxbounds
3. while arrLat[i] < Minlat do
4. i = i +1
5. end while
6. Idxbounds[0] = i-1
7. j =i
8. while arrLat[j] < Maxlat do
9. j = j +1
10. end while
11. Idxbounds[1] = j+1
12. Output: Idxbounds
 75

Algorithm 3: Elevations_Contours

1. Input: Contours, user polygon P and waypoints

2. Initialize Map dem[K,V] ← DEM
3. Initialize demLat ← Latitudes, demLong ← Longitudes
4. Initialize Grid: arrLat x arrLong, elevations ← waypoints.size()
5. {Minlat, Maxlat, Minlon, Maxlong} ← LATLNG_BOUNDS(P)
6. IndexboundsLat ← LINEARSEARCH (arrLat, Minlat, Maxlat)
7. IndexboundsLong ← LINEARSEARCH (arrLong, Minlon, Maxlong)
8. for j ∈ IndexboundsLat ± 5 do
9. for k ∈ IndexboundsLong ± 5 do
10. if dem.get(Lat[j], Long[k]) ≠ null then
11. contourpointsInsidePolygon.add(dem.get(Lat[j], Long[k]))
12. end if
13. end for
14. end for
15. if contourpointsInsidePolygon.size() ≠ null then
16. Initialize i ← 0
17. for i < waypoints.size() do
18. Initialize Map insideTheWaypointCircle[d, LatLng]
19. Initialize l ← 0
20. for l < contourpointsInsidePolygon.size() do
21. d ← computeDistancebetween(contourpointsInsidePolygon[l], waypoints[i])
22. if d < 30 then
23. insideTheWaypointCircle.put(d, contourpointsInsidePolygon[l])
24. end if
25. end for
26. if insideTheWaypointCircle.size() ≠ null then
27. min ← min(insideTheWaypointCircle.keyset())
28. elevations.add(dem.get(insideTheWaypointCircle.get(min)))
29. else
30. elevations.add(elevations[i-1])
31. end
32. end for
33. end if

Algorithm 3 has been designed for estimating the elevations values from the contours of

the mine. A new class in JAVA has been implemented for parsing the .kml format contours

into arrays. After the parsing, a map called “dem” is created with these values such that for

each lat and long pair, there is an elevation value. A grid of lat, lng is created by sorting
 76

demLat and demLong and then removing all the repeated values in demLat and demLong.

LATLNG_BOUNDS() takes all the vertices of the polygon P and output the maximum

latitudes and longitudes, minimum latitudes and longitudes values among the vertices.

These values are then searched in the Lat, Lng grid using Algorithm 2 to get the index

bounds.

In the second part, the index bounds of the polygon are used to filter the contour points

which comes inside the polygon. Then, the nearest neighbor approach has been used for

determining the points closed given waypoints. The elevation of the nearest point is then

assigned to that waypoint. The search radius for the nearest neighbor has been set at 30 m.

If there is no elevation value inside the search radius, then the elevation value of the

previous waypoint is being assigned to that waypoint. The filtering of the entire contours

to find the points which come inside the user polygon is a time-intensive process.

4.6.1 Validation of an algorithm

Similar to the section 4.5.1, a test flight has been designed over the Barrick’s Arturo pit

and the contours of the same pit generated from PhotoScan software have been imported

into the application. The contour interval has been set to 12 m which are close to the bench

height of the pit. A total of 10 waypoints have been selected from the path to evaluate the

working of this algorithm. From Figure 50, the error has a mean value of 16.28 m and a

standard deviation of 1.5. The maximum error in the estimation is 24.6 m. The high errors

in the estimation are obvious because source data in contours is not in a uniform grid like

in DEM. The contours have elevation data in for contiguous lines and polygon as shown
 77

in Figure 39. If a waypoint is between two contours lines, then depending which contour

is closest to it, it’s elevation values is assigned to it. Therefore, it also recommended using

DEM as source data with the terrain-aware feature of the App. One interesting thing to note

is that the estimated values are all overestimated. It means even if the drone flies

considering these values, it will be well above the ground and will not crack in the mine

wall. However, the images taken by the drone will be of lower resolution than expected.

The errors can be minimized by decreasing the contour intervals in the PhotoScan software.

In the future, the study will be done to improve the speed and accuracy of this algorithm.

estimated actual error

1660 0.0

1650 -5.0

1640 -11.6 -10.0

-12.6
Elevation(m)

-13.4 -14.0

Error(m)
-15.1
-16.1
1630 -17.1 -15.0
-18.1

1620 -20.0
-24.6
-25.7
1610 -25.0

1600 -30.0
1 2 3 4 5 6 7 8 9 10
Waypoints

Figure 50 Errors in estimation of elevations from contours

4.7 Evaluation of the Android Application

The purpose of the designed application is to take high-resolution imaging of open pit

mines using commercially available drones. A test flight has been conducted at San Rafael
 78

Park, Reno, NV to test the flight planning and executing ability of the application. The

flight characteristics have been shown in Table 8 and the estimated parallel path for this

mapping operation has been shown in Figure 51. The altitude has been set to lower values

for generating high-resolution models in PhotoScan.

Table 8 Flight planning

Altitude (AGL) 30 m Forward overlap 80

Area 4130 m2 Side overlap 80
Max speed 5 m/s Terrain aware No
Flight time 3.15 min No. of images 23

Figure 51 Test flight with the designed application

The point cloud and DEM of the given area generated by the software have been shown in

Figure 52.a and Figure 52.b respectively. The software has been running on a PC with 16

GB ram and Nvidia GeForce 940MX 4GB graphics card. The respective resolutions and
 79

processing time have been shown in Table 9. It can be observed from Table 9 that

processes have taken less time due to a smaller number of images. Further, according to

the formula for GSD, resolution of the models should be 1.03 cm/pixel as the drone is

flying at 30 m. Resolution of the DEM is very close to the theoretical resolution. The

resolution of orthomosaic is further high with 8.54 mm/pix reasonably sufficient for

detecting cracks on the ground. Figure 52.c depicts the overlapping statistics such that

different colors correspond to a number of overlapping images for that area. It is obvious

that the entire area has been covered with a minimum of two images suggesting the

successful implementation of parallel flight planning. The black dots are the position where

the images have been taken.

Another test flight has been conducted at the East Keystone Trail Head, Reno, NV to test

the terrain-aware feature of the App. This site is appropriate for this experiment because of

hilly terrain. Ground control points have been laid over the area approximately 0.09 km2

as shown in Figure 53.a. These points are made with survey grade spray paint with a bright

color like orange as shown in Figure 53.b. The size of the x-mark is 1m x 1m. A wooden

peg has been installed at the center of the X mark to be used as a point of the survey. A

wooden stick with ribbon as shown in Figure 53.c has been placed near the GCPs to help

them spot easily over a long period of time. Once the points have been marked on the

ground, each of them had been surveyed using Trimble R8 as receiver and Trimble TSC3

as a data collector.
 80

(a) (b)

(c)

Figure 52 Test flight 1 Photogrammetric outputs (a) Point cloud, (b) DEM, (c)
Overlapping statistics

Table 9 Processing results

Model Resolution Processing time

Point cloud 0.343 points/cm2 22.5 min
Digital Elevation Maps 1.71 cm/pix 1.5 min
Orthomosaic 8.54 mm/pix 1 min
 81

The entire exercise of laying down the point and surveying them took 1.5 hours. The stage

1 flight has been conducted over the area with Phantom 4 Pro. The flight characteristics

have been shown in Table 10. Once the aerial imagery has been collected, it has been

(a)

(c)

(b)

Figure 53 Laying ground control points at Keystone trailhead

Table 10 Flight parameters for stage 1

Altitude (AGL) 60 m Forward overlap 80

Area 0.0658 km² Side overlap 80
Max speed 7 m/s Terrain aware No
Flight time 15 min No. of images 119
 82

processed in PhotoScan to generate 3-D models. The resolution and processing time for

these models have been shown in. The software was running on a PC with 32 GB RAM

and Nvidia GeForce GTX 1080 graphics card.

Table 11 Processing result for stage 1 flight

Model Resolution Processing time

Point cloud 967 points/cm2 40 min
Digital Elevation Maps 3.22 cm/pix 1 min
Orthomosaic 1.61 cm/pix 3 min

The generated models have been imported into the designed application to conduct the

stage 2 flight with the terrain-aware feature enabled. The flight characteristics have been

shown in Table 12 and the estimated parallel path for this mapping operation has been

shown in Figure 54. The altitude has been set to lower values for generating high-resolution

models in PhotoScan. It can be observed in Figure 54 that the imported terrain map of the

test site generated from PhotoScan has been overlaid on the google maps to aid the user in

flight planning. Since the terrain-aware feature has been enabled, the flight planning will

be based on the altitude values derived from the terrain. DJI Mavic Pro has been used for

this test flight.

Table 12 Flight planning for stage 2

Altitude (AGL) 36.5 m Forward overlap 80

Area 0.0104 km2 Side overlap 80
Max speed 5 m/s Terrain aware Yes
Flight time 7 min No. of images 84
 83

Figure 54 Parallel flight for stage 2

It can be observed from Figure 55 that the UAV was able to follow the terrain by

maintaining the altitude of 36.5 m above the ground throughout the flight. This feature

makes the drone increase its altitude as it approaches the hill. Without terrain awareness,

if the drone would be flying at 36.5 over the same area it would crack into the hill. The

advantage of flying at lower altitudes is evident in Table 13. The resolution of the DEM is

almost equal to the theoretical GSD when the flying altitude of a UAV is 36.5 m. Further,

the resolution of both DEM and orthomosaic has been significantly increased compared to

the stage 1 flight (Table 11). This is a significant advantage that even though the imaging

sensor of Mavic Pro is smaller than Phantom 4 Pro, higher resolution models can be

generated from the images of Mavic Pro. An orthomosaic with a resolution of 6.3 mm/pix

is reasonably sufficient for crack detection and drill hole accuracy measurement. The

overlapping requirement has also been fulfilled as shown in Figure 56.

 84

Figure 55 Generated point cloud with the location of images

Figure 56 overlapping statistics for stage 2 flight

Table 13 Processing result for stage 2 flight

Model Resolution Processing time

Point cloud 0.63 points/cm2 43 min
Digital Elevation Maps 1.26 cm/pix 1 min 44 sd
Orthomosaic 6.3 mm/pix 4 min 24 sec
 85

4.8 Conclusion

An android application has been designed using Android Studio, Google Maps API and

DJI Android SDK. The application is able to plan and execute area mapping operations

for remote surveying of any area with UAVs. The application is also able to import the 3-

D terrain models generated from photogrammetric software. A terrain-aware feature has

been implemented inside the application to maneuver the UAV over a non-planar terrain.

This feature enables the drone to fly at altitude as low as 10 m to take high definition images

of an area. It is able to accomplish this task with two stages of flight: Stage 1 and stage 2.

The stage 1 flight is a traditional high altitude mapping operation which outputs 3D models

of the area. Stage 2 flight is being planned using these models making the drone to adjust

its flying altitude based on the ground elevation. The result is the UAV is able to fly closer

to the ground and out high-resolution images. The entire method has been tested and

validated at a local site in Reno. The resolution of the models has been compared to arrive

at the conclusion that the stage two flight generates a high-resolution 3-D model of a given

area.
 86

References
[1] J. a. M. E. M. Girard, "Detecting Problems with Mine Slope Stability," 2000.
[2] K. a. B. A. T. S. Osasan, "Review of surface mine slope monitoring techniques,"
Journal of Mining Science, vol. 46, pp. 177-186, 2010.
[3] (2018, 12/1). RIEGL VZ-6000. Available: www.riegl.com/nc/products/terrestrial-
scanning/produktdetail/product/scanner/33/
[4] A. L. Okhotin, "Application of Laser scanning in mine surveying," ed. Proceedings
of FIG Commission 6 and Siberian State Academy of Geodecy (SSGA), 2009, pp.
53-62.
[5] M. J. Little, "Slope Monitoring Strategy at Pprust Open Pit Operation," 2005.
[6] O. Oageng, "safety in surface mining looking at the main hazards.," 2016.
[7] Dr. Erik Settles, "Slope Monitoring Methods A State of the Art Report," EU
Community Initiative Alpine Space Programme, Climate Change, Impacts and
Adaptation Strategies in the Alpine Space (ClimChAlp)2008.
[8] V. a. K. A. a. M. A. Srinivasan, "Status and Developments of Slope Monitoring
Techniques in Opencast Mines," 2016.
[9] "DJI," ed, 2018.
[10] "14 Drones with the best flight times," ed, 2017.
[11] "Choosing the Right Mapping Drone for Your Business Part I: Multi-Rotor vs.
Fixed Wing Aircraft," ed, 2017.
[12] L. Torrero et al., "The Use of Micro-UAV to Monitor Active Landslide Scenarios,"
Cham, 2015, pp. 701-704: Springer International Publishing.
[13] R. Hartley and A. Zisserman, Multiple view geometry in computer vision.
Cambridge University Press, 2000, p. 607.
[14] A. a. R. S. a. T. D. Lucieer, "Unmanned Aerial Vehicle (UAV) Remote Sensing for
Hyperspatial Terrain Mapping of Antarctic Moss Beds based on Structure from
Motion (SfM) point clouds," 2011.
[15] J. A. J. B. Pablo J. Zarco-Tejada, L. Suárez, and E. Fereres, "A new era in remote
sensing of crops with unmanned robots," SPIE Newsroom,, pp. pp. 2–4
[16] J. Sužiedelytė-Visockienė, "Unmanned Aerial Vehicles for Photogrammetry:
Analysis of Orthophoto Images over the Territory of Lithuania," Journal of
Aerospace Engineering, vol. 2016, p. 9, 2016.
[17] C. Di Franco and G. Buttazzo, "Coverage Path Planning for UAVs Photogrammetry
with Energy and Resolution Constraints," Journal of Intelligent & Robotic Systems,
journal article vol. 83, no. 3, pp. 445-462, September 01 2016.
[18] (2018, 11/07). How to verify that there is enough overlap between the images.
Available: http://support.pix4d.com/hc/en-us/articles/203756125-How-to-verify-
that-there-is-enough-overlap-between-the-images
[19] A. Hussain, Y. S. Muhammad, M. Nauman Sajid, I. Hussain, A. Mohamd Shoukry,
and S. Gani, "Genetic Algorithm for Traveling Salesman Problem with Modified
Cycle Crossover Operator," Computational Intelligence and Neuroscience, vol.
2017, p. 7, 2017, Art. no. 7430125.
 87

[20] Z. Ahmed, "Genetic Algorithm for the Traveling Salesman Problem using
Sequential Constructive Crossover Operator," International Journal of Biometric
and Bioinformatics, vol. 3, 2010.
[21] S. a. T. G. Kirkpatrick, "Configuration space analysis of travelling salesman
problems," http://dx.doi.org/10.1051/jphys:019850046080127700, vol. 46, 1985.
[22] S. a. J. N. a. K. M. R. Bhide, "A Boolean Neural Network Approach for the
Traveling Salesman Problem," Computers, IEEE Transactions on, vol. 42, pp. 1271
- 1278, 1993.
[23] F. Glover, "Artificial intelligence, heuristic frameworks and tabu search,
Managerial & Decision Economics," pp. 365–378., 1990.
[24] C. a. T. A. W. a. Z. R. A. E. Miller, "Integer Programming Formulation of Traveling
Salesman Problems," J. Acm, vol. 7, pp. 326-329, 1960.
[25] S. a. C. R. a. T. M. a. G. M. Meneses, "A genetic algorithm to solve 3D traveling
salesman problem with initial population based on a GRASP algorithm," Journal
of Computational Methods in Sciences and Engineering, vol. 17, pp. 1-10, 2017.
[26] H. a. L. K. Ergezer, "Path Planning for UAVs for Maximum Information
Collection," IEEE Transactions on Aerospace Electronic Systems, vol. 49, pp. 502-
520, 2013.
[27] E. a. d. l. T. C. L. a. d. l. C. J. a. d. A.-T. B. Besada, "Evolutionary Trajectory
Planner for Multiple UAVs in Realistic Scenarios," Robotics, IEEE Transactions
on, vol. 26, pp. 619 - 634, 2010.
[28] Y. a. H. A. Pehlivanoglu, "Vibrational Genetic Algorithm Based Path Planner for
Autonomous UAV in Spatial Data Based Environments," Proceedings of the 3rd
International Conference on Recent Advances in Space Technologies, RAST 2007,
pp. 573 - 578, 2007.
[29] A. a. A. K. a. B. M. a. O. P. a. O. S. a. M. T. a. S. R. Bircher, "Structural inspection
path planning via iterative viewpoint resampling with application to aerial
robotics," Proceedings - IEEE International Conference on Robotics and
Automation, vol. 2015, pp. 6423-6430, 2015.
[30] S. a. K. C. a. W. D. a. F. E. a. N. G. Sharif Mansouri, "Cooperative Aerial Coverage
Path Planning for Visual Inspection of Complex Infrastructures," 2016.
[31] A. a. K. M. S. a. A. K. a. B. M. a. O. P. a. O. S. a. M. T. a. S. R. Bircher, "Three-
dimensional coverage path planning via viewpoint resampling and tour
optimization for aerial robots," Autonomous Robots, vol. 40, 2015.
[32] T. a. C. S. a. V. R. a. K. J. Ji, "Energy-efficient route planning for autonomous
aerial vehicles based on graph signal recovery," pp. 1414-1421, 2015.
[33] E. a. L. J. a. S. K. Kim, "Real-time prediction of battery power requirements for
electric vehicles," Proceedings of the ACM/IEEE 4th International Conference on
Cyber-Physical Systems, ICCPS 2013, pp. 11-20, 2013.
[34] A. a. C. I. a. N. E. a. L. A. a. A. Z. M. Cappiello, "A Statistical Model of Vehicle
Emissions and Fuel Consumption," Proceedings of the IEEE 5th International
Conference on Intelligent Transportation Systems, pp. 801 - 809, 2002.
 88

[35] C.-K. C. Chien-Ming Tseng , Khaled Elbassioni , Majid Khonji, "Autonomous

Recharging and Flight Mission Planning for Battery-operated Autonomous
Drones," arXiv preprint arXiv:1703.10049, 2017.
[36] P. a. K. C. a. H. M. R. a. I. I. a. D. S. Larranaga, "Genetic Algorithms for the
Travelling Salesman Problem: A Review of Representations and Operators,"
Artificial Intelligence Review, vol. 13, pp. 129-170, 1999.
[37] K. Naveen kumar, Rajiv Kumar, "A Comparative Analysis of PMX, CX and OX
Crossover operators for solving Travelling Salesman Problem," vol. Vol.1,Issue 2,
July-August (2012) ed. International Journal of Latest Research in Science and
Technology: MNK Publication, 2012, pp. 98-101.
[38] R. a. G. G. Kumar, "Novel crossover operator for genetic algorithm for permutation
problems," International Journal of Soft Computing and Engineering, vol. 3, pp.
252-258, 2013.
[39] "A new genetic algorithm for the asymmetric traveling salesman problem," Expert
Systems with Applications, vol. 39, no. 10, pp. 8947 - 8953, 2012.
[40] C. a. K. J. a. C. G. a. S. Y. Moon, "An efficient genetic algorithm for the traveling
salesman problem with precedence constraints," European Journal of Operational
Research, vol. 140, pp. 606-617, 2002.
[41] D. L. Kulhavy et al., "SFA ScholarWorks - Symposium on Arts and Research:
Accuracy Assessment on Drone Measured Heights at Different Height Levels," in
Symposium on Arts and Research, 2017.
[42] (2018, 11/11). GLM 42 | BLAZEâ„¢ 135 Ft. Laser Measure with Color Display |
Bosch Power Tools. Available: https://www.boschtools.com/us/en/boschtools-
ocs/laser-measuring-glm-42-177548-p/
[43] (2018, 11/11). GLM 42 | BLAZEâ„¢ 135 Ft. Laser Measure with Color Display |
Bosch Power Tools. Available: https://www.boschtools.com/us/en/boschtools-
ocs/laser-measuring-glm-42-177548-p/
[44] (2018, 11/12). Barrick Gold Corporation - Operations - Barrick Nevada.
Available: https://www.barrick.com/operations/barrick-nevada/default.aspx
[45] (2018, 11/14). Agisoft PhotoScan. Available: http://www.agisoft.com/
[46] S. E. UgCS, "Ground Station Software | UgCS PC Mission Planning," 2018.
[47] Mintab. (2018, 11/15). Minitab 18. Available: http://www.minitab.com/en-us/
[48] (2018, 11/16). GEOVIA Surpac | Geology & Mine Planning - Dassault Systèmes®.
Available: https://www.3ds.com/products-services/geovia/products/surpac/
[49] M. a. C. R. Gen, Genetic Algorithms & Engineering Design. 1997.
[50] N. a. S. O. Özalp, "Optimal UAV path planning in a 3D threat environment by
using parallel evolutionary algorithms," 2013 International Conference on
Unmanned Aircraft Systems, ICUAS 2013 - Conference Proceedings, pp. 308-317,
2013.
[51] D. a. D. K. E. Goldberg, "A Comparative Analysis of Selection Schemes Used in
Genetic Algorithms," vol. 51, 1991.
[52] (2018, 11/24). Android Studio. Available: https://developer.android.com/studio/
[53] (2018, 11/24). DJI Developer. Available: https://developer.dji.com/mobile-sdk/
 89

[54] (2018, 11/24). Google Maps Platform. Available: https://cloud.google.com/maps-

platform/maps/
[55] X. a. M. S. Chen, "Polygon Offsetting by Computing Winding Numbers," 2005.
 90

Appendix