Heuristic optimization technique to locate and avoid buried landmines: drone-based approach

Published Online November 2018 in MECS DOI: 10.5815/ijitcs.2018.11.05

Currently, there are over 100 million landmines buried in more than 70 countries [1]. This number is increasing daily and used as a weapon of terror against civilians. It has been estimated that more than 20,000 people are killed by mines every year, which means that there is one victim every 20 minutes. Besides human victims, mines cause large area of fertile farmland to be inaccessible. Generally, Landmines can be divided into two types: Antipersonnel (AP) mines and Antitank (AT) mines. Antitank mines are designed to destroy tanks and vehicles. They have more explosive material than antipersonnel mines and weight up to 14 kg. On the other hand, antipersonnel mines are small and designed to kill people. Those mines are triggered by a trip wire or a pressure switch that requires minimal pressure. Both types are easy to make, cheap and deployed over large areas.

In recent years, a wide variety of sensing tools are tried for mine detection applications [2, 3, 4]. Among those is the acoustic-to-seismic method. The acoustic-to-seismic method provides a high probability of detection with a low false alarm rate [5]. Generally speaking, acoustic-to-seismic method is documented very well in literature [6, 7, 8, 9, 10, 11]. This method is coupled with Laser Doppler Vibrometer (LDV) for measuring surface vertical seismic motion [12]. Such existing systems are accurate in protecting operators involved in demining activities and unaffected by moisture and weather.

With the development of unmanned aerial vehicles Drones, it is be possible to install landmine detector on them, and thus preventing loss of human life [13, 14, 15]. The landmine detector should be light enough to be carried on the unmanned aerial vehicles Drones. Visual landmine detection was tested in realistic conditions by a low-cost Quad-rotor [16, 17]. This technique creates a map of the covered terrain based on the images captured by the Quad-rotor. Ground penetrating radar (GPR) is also tested in realistic conditions by a low-cost Quadrotor [18]. The authors in [18] propose the fabrication of a small GPR to be lifted with a UAV. Although the results were acceptable, detection of plastic landmines and other mines buried in wet soil still a challenge. Accordingly, we propose the use of LDV system which is accurate in detecting both plastic and metal mines.

The core objective of this research is to develop a compact, lightweight and low power consumption aerial system that is efficient for detecting both plastic and metal mines, and is accurate in identification locations of landmines over rough terrains. The system will employ a hexacopter unmanned aerial vehicle to detect landmines using laser-acoustic technique so as to enable military forces to avoid them by selecting a safe route through the minefields in a short time. Another objective of our research is to design a robust algorithm that combines the landmine detection with three types of controllers:

Hands free flight controller, emergency flight controller, and the main on-board flight controller. This algorithm should meet the need for a fast way to locate landmines, and offer the highest level of safety for military forces without the risk of triggering landmines during any mission.

The main contributions of the paper are: (i) developing a heuristic optimization technique to locate and avoid buried Landmines (ii) developing a hexcopter drone capable of carrying the proposed products and meets the system’s requirements. The remainder of this paper is organized as follows: Section 2 reveals some recent researches on search algorithms and the correlation between the UAVs’ kinematics and the planned path. In section 3, we present an overview of our proposed approach in locating and avoiding buried landmines. In section 4, we present the search algorithm that is called Roll, Pitch and Yaw Tuning Algorithm (RPYTA). In section 5, we explained the hardware and system architecture. In section 6, we present the simulation and experimental results. Finally, we summarize the main results in section 7.

• II.    Related Work

Locating and avoiding buried landmines require an efficient algorithm for path planning of UAVs inside the area of interest. Many algorithms in the literature were developed for solving path planning problems for UAVs [19]. The Bayesian approach in [20] uses the spatial information of the environment such as: Target distance, and signal strength to compute the posterior probability distribution of the missing person, and then a greedy approach is used to determine which cell the UAV should fly to. Instead of using the greedy approach, the author in [21] uses a local hill-climbing algorithm to select the next cell that the UAV should fly to. Advantage of both algorithms is the flexibility of quickly adapting to changes, while the major drawback is that such algorithms tend to get stuck in local maxima.

A graph search algorithm like Dijkstra is widely used in many fields to find the shortest path between nodes [22]. Additionally, several algorithms were developed to find the optimal path as Dijksta’s algorithm did. As an example, A-star algorithm implements a heuristic search based on Dijkstra’s algorithm [23, 24], but with the benefit of exploring less nodes and thus reaching the goal faster. The main drawback of the A-star algorithm resides on the heading constraints and grid characteristics. Meanwhile, the authors in [25, 26] refined the graph search by obtaining a generalized paths with any heading.

Correlation between the UAVs’ kinematics and the planned path was researched in [27]. The authors in [28] described five different approaches to generate a path trajectories that navigate a UAV from its present location to a desired target in a hostile environment. The UAV is assumed to be flying at constant speed with a constant wind speed and with a magnitude less than its velocity. Another important method is the adaptive path planner which is developed to adapt to the variations and fluctuations of UAVs’ performances with regard to kinematic properties. The authors in [29] addressed the development of adaptive path planning algorithms for a small vertical take-off and landing unmanned four-rotor helicopter.

• III.    Overview of the Proposed Approach

We propose the use of a lightweight system that consists of a hexacopter drone, landmine detector, hands free flight controller, emergency flight controller, and the main on-board flight controller. Figure 1 shows a general description of the proposed system:

Hexacopter

Emergency Flight Controller

Hands Free Flight

Troops

15M

Direction

Laser Beams

X 2

Acoustic Signal

Landmines

Fig.1. General description of the system.

The hexacopter unmanned aerial vehicle is responsible for caring the laser-acoustic system, emergency flight controller, main on-board flight controller, and guide troops to avoid landmines. Laser-acoustic system is a promising approach that sends a high power acoustic waves from the hexacopter to the ground. The penetrating acoustic waves generate a series of seismic waves in the soil. Those waves can cause both plastic and metal mines to vibrate and resonate differently from the surrounding soil. This vibration can be measured by the LDV and can be used to detect landmines. Altitude and speed of the Hexacopter are an important factor for an accurate detection. Altitude will be 15m and speed will not exceed the steps of the marching troops (0.5m/s.). This scenario will be explained in the hands free flight controller.

Using the hands free flight controller, and during the searching for landmines; hexacopter will be controlled by one of the marching troops who is following it. Hands free flight controller will be installed at the leader’s helmet. This subsystem keeps a fix distance between the leader and the hexacopter, so if the leader stops; hexacopter will stop too. Otherwise, if the leader steps forward, the hexacopter will move too. Mechanism of this subsystem is based on the readings from the GPS. Simply, hands free flight controller is used to pitch up/down the hexacopter while searching for landmines. Consequently, if the hexacopter detects a landmine, emergency flight controller will send a signal to the leader (hands free flight controller) to inform him that a threat is detected, meanwhile hands free flight controller is disconnected. At that moment, the leader must follow the hexacopter to avoid landmines. This scenario will be explained in the emergency flight controller.

Using the emergency flight controller, hexacopter will change its direction and continue for searching landmines. Commands for changing the direction of the hexacopter are the responsibility of this subsystem. Additionally, this subsystem monitors other subsystems and executes commands received from the hands free flight controller. Once the direction is changed, the leader’s helmet (hands free flight controller) will be able to control the drone until it detects a new landmine or change its direction.

At the beginning of each mission, hexacopter is launched remotely and controlled by the main on-board flight controller. Once the hexacopter reaches an altitude of 15m, a communication channel will be established with the leader’s helmet. Following the previous scenarios, our hexacopter can detect landmine and inform the troops to be aware while crossing minefield. The process of removing landmines is out of this project scope but our aerial system has the capability to provide a map for future use.

• IV.    Search Algorithm

To achieve the proposed approach, the problem at hand requires to detect all landmines a head of the marching troop. This means that the complexity of the system grows exponentially as the number of landmines increases. As a result, this problem can be seen as an optimization problem. Our goal is to minimize the number of landmines seen by the hands free flight controller, and thus the leader of the troop. Additionally, the desired area should be increased while meeting the conditions of offering the highest level of safety for the marching troop without the risk of triggering any landmine during the mission. Since an optimal solution needs a lot of time to minimize the number of landmines seen by the hands free flight controller, which are indeed not feasible due to the constraints and dynamics of the Drone, a heuristic search algorithm is proposed for implementing our approach. This algorithm is based on the decision that is taken by the hands free flight controller and also based on the number of messages received from the laser-acoustic detector. The number of messages is an important factor in this algorithm since it reflects how many landmines are distributed on the ground. Roll, Pitch and Yaw Tuning Algorithm based on the existence of landmines is the name of our algorithm (RPYTA).

The input to the RPYTA is the number of the messages received by the emergency flight controller from the laser-acoustic detector. The output from the RPYTA is a number preceded by a letter to set; the roll (R0, R1,... Rz) , pitch (P0, P1,... Py) and yaw (Y0, Y1, ... Yz), where x, y, and z are consecutive positive integers such that (R0,P0,... Y0) indicate that the output from the hands free flight controller is maximized. The goal is to let the troop moves to the safest direction (left, right, back, or forward). In other words, troop moves forward as soon as there is no landmines (i.e. no messages received). If there is any, the system should guide the troop to move to the left, right, or let the troop move back based on the calculated weight.

The area of interest is divided into clusters in which the size of each can be calculated with the following expression:

С = ((2й/5) .(h/5))             (1)

where h is the copter's height. Then each cluster is divided into two uniform square cells and each cell is given a weight as follows:

w⁽s) = ⁽w⁽s') — k t )                ⁽²⁾

where w(s ' ) is the given maximum weight plus the number of messages received from the detector, and k_t is an integer number from 0 — ((7 ^/5) — 1). To calculate the w(s ' ), the following expression is used.

w(s ' ) = Max w(s) + m(s))         (3)

The dimension of each cell is set based on the height of the hexacopter (^/5). The movement of the Drone (i.e. the roll (R₀,R 1 , .R_z) , pitch (P₀,P 1 , .P_y) and yaw (Y₀, Y 1 ,... Y_z) depends on the weight of each cell, where it moves forward while the difference between w(s ' ) and k_t is minimum.

After scanning a certain cell (i,j) , Drone should turn 180 degree and scan the surrounding cells based on the following expressions.

s' (i — 3,j — 3)(4)

s' (i + 3,j — 3)(5)

s' (i + 3J)(6)

s' (i + 3,j + 3)(7)

s' (i,j + 3)(8)

For each cluster scanned by Drone, the weight is decreased gradually from (0-20), where 20 means forward movement (i.e. pitch down (R_x, P₀, ... Y₀)).

The algorithm starts as soon as the drone reaches a presetting height where an explicit mine graph G(s) is created with a maximum weight for the whole cells. The algorithm     terminates     successfully     if     the

• V.    System Overview

The following sections explain the hardware and system architecture.

• A.    Hardware

Our system was structured with five units: Hexacopter unmanned aerial vehicle, landmine detector, hands free flight controller, emergency flight controller, and the main on-board flight controller. Landmine detector (laseracoustic system) was researched in the literature and we will not present it in this article.

Table 1. Roll, Pitch and Yaw Tuning Algorithm

Algorithm: Roll, Pitch and Yaw Tuning Algorithm based on the existence of landmines (RPYTA).

Initialization

S(i, j) =starting location

Assign maximum weight for each cell in the cluster

Initialize MineGraph

While true do

For each cell in the cluster do

GetMesages ((s'(i-3, j-3), s' (i+3, j-3), s' (i+3, j), s' (i+3, j+3), s' (i, j+3)).

w(s') = # of messages received

+ maxWeight(s').

w(s) = w(s') - Ki

Update MineGraph for the cluster

End

D(S) = min((w'(i-3, j-3), w' (i+3, j-3), w' (i+3, j), w' (i+3, j+3), w' (i, j+3)).

Set the (Rx, Py, Yz)

Move UAV to location D(S)

Stop the movement of UAV

End

End

• 1)    Hexacopter Unmanned Aerial Vehicle

As shown in figure 2, a hexacopter was chosen for carrying out the whole system. The frame of the hexacopter is composed of six arms attached symmetrically to the central hub. The landmine detector, emergency flight controller, on-board flight controller, and power supply are all placed on the central hub. At the end of each arm, a propeller driven by an electric motor is attached. The distance between the centers of any two motors on the same arm is 55 cm. The copter weighs 2 kilograms and it can carry a payload of approximately 1.5 kilograms.

(b)

Fig.2. Hexacopter platform (a) Hexacopter with the main on-board flight controller (Pixhawk) mounted at the center. (b) Hexacopter with the emergency flight controller mounted on top.

The main on-board flight controller is the Pixhawk, figure 3. Pixhawk is an open source autopilot system capable of controlling angular rotations and altitude of any Drone. The Pixhawk flight controller consists of an Inertial Measurement Unit (IMU), magnetometer, barometer, and a cortex-M4F microprocessor. The flight control board is attached to six Turnigy Plush 30 amp Electronic Speed Controllers (ESCs). Brushless three-phase Tiger motor (MN2214) rated for 920KV / 251W are used in this project. Six (9 X 45) inch propellers with a fixed pitch blades are mounted on the motors, three pieces for standard rotation and three pieces for righthand rotation.

(a)

(b)

Fig.3. Pixhawk flight controller (a) Pixhawk is attached to six ESCs. (b) Pins dedicated for the ESCs and RC.

• 3)    Hands Free Flight Controller

The hands free flight controller is designed in this project to be small, lightweight, and to be easily fasten to the helmet of the leader. It consists of a small cabinet with XBee DigiMesh 2.4 GHz module, GPS module, audio system, and Arduino Nano board. GPS receiver captured leader’s behavior data such as position, velocity, acceleration, and heading. Arduino Nano board gets the data from the GPS receiver and passes it to the Xbee module. XBee module forwards the data to Drone. The data will be processed by emergency flight controller and retransmitted again to regulate troop's movements. An overview of the hardware system is outlined in figure 5.

• 2)    Emergency Flight Controller

As shown in figure 4, emergency flight controller is fitted with a companion computer (Raspberry pi 3), Adafruit GPS, Arduino Nano board, and XBee-pro S2C DigiMesh 2.4 GHz module. XBee-pro module is power-amplified versions of Digi XBee modules for extended range applications. It operates with 63 mW/2.4GHz and transmits power that enables outdoor RF line-of-sight range up to 3.2 km. This range is sufficient to allow the base station to monitor the movements of the Drone from a distance. Raspberry is programmed to run the search algorithm and output PWM signals to control the movements of the Drone as well as the leader of the troops. Additionally, raspberry communicates with the main flight board, Adafruit GPS, and Arduino Nano board.

(a)

(b)

Fig.4. Emergency flight controller (a) Simplified block diagram of the hardware. (b) Photo of the controller platform, raspberry is underneath the board.

(a)

(b)

Fig.5. Hands free flight controller (a) Simplified block diagram of the hardware. (b) Photo of the controller platform.

• B.    System Architecture

Figure 6 presents an overview of how the hardware is connected in this project. Drone works by the way of several propellers which lift the platform into the air, with the height, speed, and the direction being controlled by the main on-board flight controller. The companion computer (Raspberry pi 3) does all the flying, from auto take off to landing. Guided mode is the main mode used in this project for flying Drone autonomously without a predefined mission. Raspberry controls the vehicle on the fly and react to the data collected by the landmine detector. Fig. 6. An overview of how the hardware is connected in this project

Fig.6. An overview of how the hardware is connected in this project

• VI.    Experimental Results and Analysis

To validate the system, experiments are carried out in simulation and on the real hardware.

• A.    Simulation Results

To assess the performance of the proposed search algorithm, we used the Matlab to simulate the system according to the previous scenario. We divided the simulation process into two stages: Simulating the dynamics model of the hexacopter using PID controller, and simulating the whole system including the proposed algorithm.

For the simulation of the hexacopter, the dynamics of the UAV is well described in [30]. The work done in this research is to evaluate the dynamic performance of the hexacopter using the PID controller. The vehicle attitude was stabilized by using a PID controller with Kp = 7.7, Ki= 3.1 and Kd = 0.25. The controller was able to make the vehicle follows the reference command with altitude of 15m. Figure 7 shows the 3D plot of the hexacopter flight simulation, and the results of the simulation are presented in figure 8.

The plot in figure 7(b) is used to analyze the position and the orientation of the hexacopter, and hence verify its performance. As shown in figure 7(a), the hexacopter object is represented with six arms and six bulbs. The bulbs in the figure is used to represent the propellers at the end of each arm. A Matlab script is implemented for the calculation of the thrust and torque of each engine. The physical parameters of the system along with the calculated thrust and torque are used to animate the hexacopter in flight. As shown in figure 7(b), the vehicle flies from position (0,0,0) to (0,0,15), and continues to position (15,15,15).

(a)

(b)

Fig.7. 3D-plot of the hexacopter (a) Hexacopter flight simulation (b) Position and orientation of the hexacopter.

In figure 8, the response of the PID controller to the roll, pitch and yaw angles are presented. The errors along the x, y, and z axis's are practically minimum because the hexacopter is able track the attitudes of reference points efficiently. We can say that PID controller has a good performance, and hence it will provide a stable flight during the landmine detection.

Finally, as shown in figure 9, and for the purpose of simulating the whole system, the area of interest was divided into 100 cells. The dimension of each cell is set based on the height of the hexacopter. The UAV begins by searching the map for the existence of a landmines and then attempts to move forward toward its goal. Decision on the next step is taken when the hexacopter scanned the whole cells in the cluster. The hexacopter continually senses its environment and updates its map.

(a)

(b)

(d)

Fig.9. A graphical representation of the area of interest (a) 3D-plot of the area of interest with maximum weight (b) A grid of 10 by 10 is defined and covered an area of 30m by 30m (c) Dividing the area of interest into clusters and each has a size of (6 X 3), where h=15m (d) Positions of the landmines (82, 53, 21, 33) along with segments trajectory of the hexacopter, common color for each cluster.

Fig.8. Response of the PID controller (a) Performance of the roll, pitch and yaw angles (a) Performance of the angular velocity.

(c)

(a)

(b)

• B.    Hardware Experimental Results

As shown in figure 10, several empirical experiments have been performed using the hexacopter fabricated at TTU laboratories. They all carried out with three different approaches: The first experiment was conducted to evaluate the main flight controller (PixHawk) in stabilizing the copter, the second experiment was conducted to test the capability of the emergency flight controller to autonomously fly the Drone without any problems, and last, the third experiment was conducted to test the whole system.

During the first experiment. Four basic movements are considered to test the platform: throttle, roll, pitch, and yaw movements. A radio controller is used to control the hexacopter by sending reference values for roll, pitch, yaw and throttle with a limited boundary from 1000 s to 2000 s. The experiments showed that Drone is stable and very responsive to control inputs.

Using the emergency flight controller, and during the second experiment. Flight tests were conducted to ensure that the hexacopter would be able to autonomously fly without any problems. Python script was written and implemented by the raspberry pi to gradually increase the thrust until the hexacopter lifted off the ground and hovered at 15 meters. Guided mode have been enabled on the hexacopter platform during the test. The rate during takeoff and landing has been set to be controllable by the software. The hexacopter was able to take off and hover autonomously with some deviations caused by air turbulence.

For the evaluation of the proposed approach, the third experiment was partially conducted. Unfortunately a lightweight laser-acoustic detector that fits Drones is still not offered in market so the test was conducted using only the hands free flight controller, and the emergency flight controller. A random number was generated to represent the landmine's messages. The data is then processed and transmitted to the hand free flight controller using the Xbee wireless transmitter.

Fig.10. Experimental setup for the evaluation of the three different approaches stated above

• VII.    Conclusion and Future Work

In this research, the feasibility of employing a Drone equipped with a landmine detector, hands free flight controller, emergency flight controller, and the main onboard flight controller for locating and avoiding buried landmines from a distance was studied. The main aim of the proposed project was to offer the highest level of safety for military forces without the risk of triggering landmines during any given mission. Due to the complexity of this problem, we have proposed a new heuristic, the RPYTA, which combines the number of messages received from the laser-acoustic detector with the movements of the Drone as well as the troops. The simulation environment was used to evaluate the proposed project. The performance of the system was significantly superior because the dynamics of the Drone are coupled with three different controllers. The initial empirical experiments have shown that the Drone is stable and very responsive to control inputs. The research in this paper is still at an early exploration stage. In the future, we will continue searching the markets for a powerful, lightweight, and small laser-acoustic detector with a good accuracy. With this goal in mind, we will also investigate more complex scenarios that accelerate the detection process.