Analysis of factors affecting the speed of probabilistic target search using unmanned aerial vehicles

Abstract

When searching for targets using unmanned aerial vehicles, speed is important for many applications such as the discovery of patients in a medical emergency. The speed of operation of actual unmanned aerial vehicles is strongly related to the performance of the camera sensor used for target recognition, search altitude, and the search algorithm employed by the unmanned aerial vehicle. In this study, the major factors affecting the speed of a probabilistic unmanned aerial vehicle target search are analyzed. In particular, simulations are performed to analyze the influence of the search altitude, sensor false alarm rate, and sensor missed detection rate on the required travel distance and the time required for a search. Furthermore, the search performance of an unmanned aerial vehicle is analyzed by varying the search altitude with fixed false alarm and missed detection probabilities. The simulation results show that the search performance is significantly affected by changes in the false alarm and missed detection probabilities of the sensor, and it confirms that the effect of the missed detection probability is greater than that of the false alarm probability. The second simulation proves that the altitude of an unmanned aerial vehicle is a very important factor for the speed of a target search. In particular, the result shows that, for a real data set, the search distance and time at 10 and 5 m are about 2.8 times and 14.3 times larger, respectively, than those at 20 m.

Keywords

Unmanned aerial vehicles unmanned aerial vehicle altitude control target detection altitude change drone search

Introduction

Speed is a critical factor when searching for targets in a wide search area using unmanned aerial vehicles (UAVs). The speed of a target search is dependent upon the search algorithm, search altitude, and performance of the search sensor.¹ The behavior of a UAV is determined by the search algorithm employed in the target search; therefore, it is important to use an efficient algorithm to ensure a rapid search.²

UAVs are difficult to control directly from a remote location, and therefore autonomous navigation is required to locate a target. The search altitude and performance of the search sensor are the major factors that affect the search performance of a UAV in a probabilistic search, which requires autonomous navigation. The probabilistic search method is one of the most studied methods for autonomous navigation.^3,4 The probability of a target being present in the search area is recursively updated by the method while performing various actions based on the initial search parameters to determine whether the target is present.

In this study, the effect of several factors on the speed of a probabilistic search with a UAV is investigated; these factors include altitude and the false alarm and missed detection rates of the search sensor. The effects of varying the false alarm and missed detection rates of the search sensor on the search performance of a UAV are investigated through simulations. Furthermore, the effect of varying the search altitude while the false alarm and missed detection probabilities are fixed is also studied. The analysis results demonstrate that the search altitude and the false alarm and missed detection rates of the sensor are important factors affecting the performance of a probabilistic target search for a UAV.

The remainder of this article is organized as follows: In section “Related work,” the probabilistic search method is described and existing research on factors affecting its speed are analyzed. In section “Factors related to the speed of probabilistic search,” the characteristics of the main factors affecting the speed of searching for a target using a UAV are analyzed. In section “Simulation,” the importance of each factor affecting the speed by means of simulations is verified and the results are analyzed. Finally, the conclusions are presented in section “Conclusion.”

Related work

In this section, the probabilistic search method for UAVs is examined, and existing research on the factors affecting the speed of a probabilistic search is reviewed.

Probabilistic search

A probabilistic search is a search method for the autonomous navigation of UAVs. This method involves choosing search actions based on the probability that a target exists in a search area. That is, it is a method of determining the possibility of the presence of a target by considering the information from an initial search of the region and information from the current search and then performing an effective autonomous search operation. For probabilistic searches using UAVs, it is necessary to define the search problem along with various factors such as the search area, number of targets, movement of the targets, and the properties of the sensor. In this study, the problem of searching is defined as follows.^3,4

First, the search area of the UAV is denoted by A and there exists a single static within A; therefore, the UAV must find a single static target x_T in the search area A; second, the search area contains |A| grid cells, with the target being contained in at least one cell; third, the UAV is equipped with a search sensor that collects location and detection information on the target; and fourth the sensor covers each cell m_k at an altitude h.

A probabilistic search starts by constructing a probabilistic map (belief map), which comprises the initial search information for the search area A. The belief map is composed of several cells, similar to the search area, and each cell is associated with a probability of the target existing in the cell. A different value, that is, probability, is assigned to each cell of the initial belief map based on which features the cell contains, if any, such as rivers, hiking trails, trees, or buildings. That is, high and low probability values can be assigned to features suggesting high and low probabilities, respectively, of finding the target. The UAV calculates the probability that the target exists in a search cell based on information from the initial belief map and information from the current search.

Different actions are taken by the algorithm based on the computed probability for each cell. The equation for calculating the probability of the target’s presence can be expressed as

\Pr (x_{T} = a | D^{t}) = \frac{\Pr (d_{a}^{t} | x_{T} = a, D^{t - 1})}{\Pr (d_{a}^{t} | D^{t - 1})} \Pr (x_{T} = a | D^{t - 1})

(1)

as presented in Chung and Burdick’s^3,4 study. This equation is derived via Bayesian filtering,^5–7 and the observed value of a drone influences the probability function. In this equation, $d_{a}^{t}$ represents the search measure for cell a at time t, Dt becomes a set of observations up to time t as {d1, …, dt}, and x_T = a indicates the presence of the target in cell a. Therefore, Pr(x_T = a|D^t − 1) represents the probability function at the previous time, and Pr(x_T = a|D^t) represents the probability at time t. Furthermore, $\Pr (d_{a}^{t} | D^{t - 1})$ represents the marginalization of the measurement, and it can be obtained as

\begin{matrix} \Pr (d_{a}^{t} | D^{t - 1}) = [\Pr (d_{a}^{t} | x_{T} = a, D^{t - 1}) \Pr (x_{T} = a | D^{t - 1}) \\ + \Pr (d_{a}^{t} | H = 0, D^{t - 1}) (1 - \Pr (x_{T} = a | D^{t - 1}))] \end{matrix}

(2)

where H is a binary variable indicating whether a target exists in the search area and $\Pr (d_{a}^{t} | x_{T} = a, D^{t - 1})$ is the search result of cell “a” at time t and is obtained from the search model of

\Pr (d_{a}^{t} | x_{T}) : {\begin{matrix} \Pr (d_{a}^{t} = 0 | x_{T} = a) = β \\ \Pr (d_{a}^{t} = 1 | x_{T} = a) = 1 - β \\ \Pr (d_{a}^{t} = 0 | x_{T} \neq a) = 1 - α \\ \Pr (d_{a}^{t} = 1 | x_{T} \neq a) = α \end{matrix}

(3)

where α (false alarm) refers to the case where the UAV wrongly determines that there is a target present in a cell and β (missed detection) corresponds to the case where the UAV determines that there is no target in a cell when a target is actually present. The values of α and β can be considered to represent the performance of the search sensor. In general, they take different values depending on the search altitude. The following search model was proposed by Chung and Burdick^3,4 and was frequently employed in the study by Waharte and Trigoni⁸ and Symington et al.⁹ In a probabilistic search, the false alarm and missed detection rates are denoted by α and β, respectively.

Studies related to search altitude

In Chung and Burdick’s^3,4 study, the factors that affect promptness in probabilistic searches with UAVs were analyzed. They defined the problem of a search with a UAV, proposed a search model incorporating a false alarm probability and missed detection probability, and proposed a discrete Bayesian formulation for calculating the probability of a target being present in a search cell. Their study also introduced various search control strategies for determining the presence of a target.

Symington et al.⁹ derived the confusion metrics for false alarms and missed detections based on observations from experiments. They also derived the update equation for the recursive Bayesian estimator

P_{t} = {\begin{matrix} \frac{(1 - β_{h}) P_{t - 1}}{(1 - β_{h}) P_{t - 1} + α_{h} (1 - P_{t - 1})}, if d^{t} = 1 \\ \frac{(β_{h}) P_{t - 1}}{(β_{h}) P_{t - 1} + (1 - α_{h}) (1 - P_{t - 1})}, if d^{t} = 0 \end{matrix}

(4)

This is configured such that different formulations are applied depending on whether the current search event is positive or negative.

Trigoni et al.¹⁰ studied a method for calculating the probability for a cell when the range of the search sensor covers the boundaries of several search cells, reflecting the actual movement of the UAV. Waharte and Trigoni⁸ studied the possibility of the exchange of search information between several UAVs. In that study, it was verified through simulation that two drones achieve better search performance when they collaborate through the exchange of search information. Waharte and Trigoni¹¹ introduced various search algorithms, such as greedy heuristics, potential-based heuristics, and partially observable Markov decision process (POMDP)-based heuristics,^12,13 and they explained that search methods that incorporate altitude control are the most efficient.

One of the major factors affecting the speed of a probabilistic search using a UAV is the search altitude. Table 1 summarizes the findings of existing studies on factors that affect the search performance of UAVs. Chung and Burdick’s^3,4 study defines a navigation problem and proposes a navigation model based on probabilistic methods. This model is significant as a starting point to tackle issues of accuracy related to altitude. Waharte and Trigoni’s⁸ study is an early study presenting a method of cooperation between a high-altitude and a low-altitude drone. This study focuses on the comparison between cooperation and non-cooperation of the two drones at different altitudes. However, there is no analysis or experiment concerning the other factors that affect the performance of a UAV, such as the α and β values.

Table 1.

Existing research on the search altitudes of unmanned aerial vehicles.

Study	Features	Weakness and difference
Chung and Burdick^3,4	Defines of the drone’s target detection problem. Proposal for the search model	Performance test based on changes in α and β values, no performance test based on changes in altitude
Waharte and Trigoni⁸	Proposes a cooperative method for multiple drones at different altitudes	Lack of analysis of various performance-impacting factors, such as α and β
Symington et al.⁹	Determines α and β values by experiment and simplifies the update equation	Lack of performance-related experiments according on changes in α and β values
Waharte and Trigoni¹¹	Introduces algorithms related to the altitudes of drones and simulates their performance in a specific experimental environment	Lack of a detailed analysis of factors affecting the search performance, such as altitude and α and β values
Chung¹⁴	Compares the navigation performance of two drones at varying altitudes	Lack of performance-related experiments related to changes in various factors
Wang et al.¹⁵	Finds the optimal drone position by decoupling the DBS deployment problem in the horizontal and vertical dimensions	Mainly focuses on the height of the drones for efficient data transfer between drones and people, rather than searching for targets on the ground
Mozaffari et al.¹⁶	Studies the coverage performance of DSCs acting as base stations in a low-altitude platform and evaluates the impact of a DSC altitude on the downlink ground coverage and the optimal values for altitude	Focuses on how drones serving as aerial wireless base stations have maximum coverage with minimal communication costs and focus on the optimal altitude for maximum communication coverage, not the optimal search altitude for target detection
Zorbas et al.¹⁷	Deals with the cost minimization problem related to the optimal placement of drones in order to cover a set of static or mobile targets	Focuses on minimizing the number of drones and the total energy consumption rather than the altitude of the drones in order to search the targets of the drones
Sekander et al.¹⁸	Focuses on investigating the feasibility of a multi-tier drone network architecture over traditional single-tier drone networks	Aims at efficient energy use in drone-assisted cellular networks, proposes a multi-tier drone network, and studies optimal ratios and altitudes of large and small drones
Brunton et al.¹⁹	Studies the importance of altitude factors in the case of using drones. In other words, it studies animal behavior according to the altitude of drone flight in drone-based animal monitoring	Focuses on the importance of flight altitude in drone-based kangaroo monitoring and examines the importance of high altitude rather than optimal flight altitude in drone applications

DBS: drone base station; DSCs: drone small cells.

Symington et al.’s⁹ study experimentally determined the α and β values, as well as simplified the update equation for the recursive Bayesian estimator. However, there is a lack of experimental studies on the effect of changes in the values of α and β on search performance. Another study by Waharte and Trigoni¹¹ introduced algorithms related to the altitudes of drones, simulated their performance in a specific experimental environment, and undertook a comparative analysis of the results. However, there is a lack of a detailed analysis of other factors affecting search performance, such as changes in altitude and in the values of α and β. Chung’s study¹⁴ compares the navigation performance of two drones at varying altitudes using the POMDP method. However, there is a lack of experiments related to the impact of various other factors on search performance.

Recent studies related to the search altitude of drones are as follows.^15–19 An optimal drone base station (DBS) placement method to serve a set of ground users, using minimum required transmit power, was proposed in Wang et al.’s¹⁵ study. They study the optimal drone position by decoupling the DBS deployment problem in the horizontal and vertical dimensions. They focus on the height of the drones for efficient data transfer between drones and people, rather than searching for targets on the ground. In other words, they focus on the optimal communication altitude in terms of efficient energy use rather than the optimal search altitude for target discovery. Mozaffari et al.’s¹⁶ study focuses on how drones serving as aerial wireless base stations have a maximum coverage with minimal communication costs. Therefore, they focus on the optimal altitude for maximum communication coverage, not the optimal search altitude for target detection. Zorbas et al.’s¹⁷ study deals with the cost minimization problem related to the optimal placement of drones in order to cover a set of static or mobile targets, and they focus on minimizing the number of drones and the total energy consumption rather than the altitude of the drones in order to search the targets of the drones. Sekander et al.’s¹⁸ study focuses on investigating the feasibility of a multi-tier drone network architecture over traditional single-tier drone networks. This study aims at efficient energy use in drone-assisted cellular networks. In this study, they propose a multi-tier drone network and study optimal proportion and altitudes of large and small drones. Brunton et al.’s¹⁹ study deals with the cost minimization problem related to the optimal placement of drones in order to cover a set of static or mobile targets. This study focuses on the importance of flight altitude in drone-based kangaroo monitoring and examines the importance of high altitude rather than optimal flight altitude in drone applications.

Recent research^15–19 on the importance of drone search altitude has focused on the energy efficiency of data transmission in most drones intervening communications networks. In other words, although they focus on the importance of the drone’s search altitude, we can see that the ultimate goal of these studies is energy efficiency.

Although there have been studies^20–24 relating to probabilistic searching with UAVs, few studies have focused on the importance of search altitude. There are very few studies that analyze the search performance of drones according to the change of search altitude. In particular, the results of studies on the change of false alarm and missed detection, which are important factors in probabilistic search, are very rare.

Therefore, this study is different and unique compared with previous studies based on the following points: First, we investigated the importance of search altitude in probability search of drones by associating false alarm and missed detection, which are important factors of probability search. Second, we show the change of search performance according to the change of search altitude through various simulations. Finally, we have shown what is more important in false alarms and missed detection, which are important factors in probability search through various simulations.

Factors related to the speed of probabilistic search

In this section, we explore problems related to the factors that affect the speed of a probabilistic search using UAVs, namely, search altitude, false alarms, and missed detections.

Problems with search altitude

The search altitude is very important in a probabilistic search using UAVs. This is because there is a significant difference in the performance of the search sensor at different altitudes, which affects the search execution algorithm. There are many potential problems related to the search altitude of a UAV, but one of the most important problems is determining the search area based on the altitude. The size of the search area is related to the search angle of the sensor, as shown in Figure 1.

Figure 1.

Relationship between search altitude and search area of a UAV.

If the search angle of the sensor is 2θ, as shown in Figure 2, then the searchable range becomes circular. However, due to camera distortion, the area at the edge of the circle cannot be precisely searched. Therefore, it is more stable to define a rectangular search range within the circle; this is also more convenient for the calculation of the search area. Therefore, when the search height is h and the search angle is 2θ, the size of the search area A can be obtained using equation (5) as follows

A = b \times b = {(\sqrt{2} \times a)}^{2} = 2 a^{2} = 2 {(\frac{h}{\tan θ'})}^{2}

(5)

According to this equation, the size of the search area is proportional to the square of the search altitude. That is, when the search altitude is doubled, the size of the search area increases by a factor of four. Similarly, when the search altitude is reduced by a factor of two, the size of the search area is reduced by a factor of four. Conversely, when the height is reduced to half its original size, the search area is reduced to one fourth of its original size, as shown in Figure 1.

Figure 2.

Linear search algorithm used in the simulation.

Problems related to false alarm and missed detection rates

In equation (3), which represents a probabilistic search model, the false alarm and missed detection probabilities are very important factors affecting the speed of a probabilistic search using a UAV.

The probability of a false alarm corresponds to the probability that the UAV detects a target in the search area when the target is not actually present in the search area, and the probability of a missed detection corresponds to the probability that the UAV does not detect a target in the search area when the target is actually present. The false alarm and missed detection probabilities depend on the altitude of the search and the performance of the search sensor. In general, the probability of a false alarm tends to increase as the search altitude decreases, and the probability of a missed detection tends to increase as the search altitude increases. The exact false alarm and missed detection probabilities depend on the search conditions. Therefore, they can be determined experimentally based on the performance of the search altitude and search sensor in a given environment. Symington et al.⁹ and Waharte and Trigoni¹¹ determined the experimental probabilities of false alarms and missed detections through actual experiments, as detailed in Table 2.

Table 2.

Experimentally obtained values of α and β.

Altitude (m)	Data Set 1^3,4		Data Set 2⁷
Altitude (m)	α	β	α	β
5	0.24569	0.21428	0.243599	0.000000
10	0.06286	0.20000	0.028369	0.000000
20	0.00130	0.34593	0.001110	0.046745

The false alarm and missed detection probabilities can be calculated using four kinds of judgment values: true positives (TPs), true negatives (TNs), false positives (FPs), and false negatives (FNs). Therefore, the false alarm and missed detection probabilities α_h and β_h at a height h can be defined as follows⁹

α_{h} = \frac{FP}{FP + TN}, β_{h} = \frac{FN}{FN + TP}

(6)

Simulation

In this section, we discuss a variety of simulations and analyze the results to investigate the importance of the search altitude and the false alarm and missed detection rates of the search sensor on the speed of a probabilistic search using a UAV.

Search algorithm

The algorithm used in this simulation is a linear search algorithm, as shown in Figure 2, because this method performs most effectively despite changes in altitude.

As shown in Figure 2, the search is performed at high, medium, and low altitudes. At each altitude, the drone traverses the search area once, then returns to the origin, and repeats the process.

Simulation environment

For the simulation, we assume the search environment shown in Figure 3. For simplicity, the map on the left is approximated by the initial map on the right for use in the simulation. The search area consists of an 8 × 8 grid of cells. The search area has a river, which is relatively unlikely to contain a target, and a hiking trail, which is relatively likely to contain the target. Furthermore, there are obstacles, such as trees and buildings, on the side of the road. An initial belief map is constructed by assigning appropriate weights to these features for a probabilistic search. Namely, a weight of +0.2 is assigned to the hiking trail, a weight of −0.2 is assigned to the river, and weights of −0.1 and −0.2 are assigned to trees and buildings, respectively.

Figure 3.

Simulation map.

Other specifications of the simulation environment are shown in Table 3. It is assumed that a single unmanned aircraft with a speed of 15 km/h is employed for the search. The search altitude is varied between 20, 10, and 5 m. When the search altitude is 20 m, the size of the search area is 4 × 4 units. At 10 m, the altitude is reduced by 1/2, so the size of the search area is 2 × 2 units. At 5 m, the size of the search area is 1 × 1 unit. When the angle of the search sensor is 94°, the actual side length of a unit is 7.592 m. In the probabilistic search, the threshold for the success of a search is set to 0.95.

Table 3.

Simulation environment.

Category	Value
Size of search area	8 × 8 units
Average speed	15 km/h (4.1666667 m/s)
Search altitudes	4 × 4 units (altitude: 20 m) 2 × 2 units (altitude: 10 m) 1 × 1 units (altitude: 5 m)
Threshold probability	0.95
Length of a side of one unit	7.592 m
Number of targets	1 (random)
Number of UAVs	1

UAVs: unmanned aerial vehicles.

In this simulation, we assumed a typical small drone with a camera sensor and being capable of flying over an altitude of 20 m, and the drones’ search speed was assumed to be 15 km/h. As a data collection method, in this simulation, the drone shoots the search area with the camera sensor and analyzes the shot image on the drone itself to determine whether the target exists in the search area. Also the MATLAB 2013 software was used for simulation and data collection and visualization.

In this simulation, the drone performs a probabilistic autonomous search to locate the target. We use equation (3) as the probabilistic search model and equation (4) to calculate the probability.

Simulations of false alarm and missed detection factors

Several simulations were performed to investigate the effects of false alarms and missed detections on a probabilistic search. First, the height was fixed at 20 m and the search distance and time required for a successful search were measured while varying the values of the false alarm and missed detection rates from 0.0 to 1.0. Linear search refers to a method of sequentially searching an area at a given altitude. In this case, the travel distance required for the search is obtained from equation (7) and is based on the number of cells traversed before the target is successfully located. In this equation, U_m denotes the number of units moved, tan θ_hb refers to the tangent of the angle between the hypotenuse and base, and h is the altitude of the drone²⁵

D = U_{m} \sqrt{2 {(\frac{1}{\tan θ_{hb}} h)}^{2}}

(7)

The time required for a successful search is obtained from equation (8), which takes into account the average speed of the UAV based on its search travel distance

Search time = \frac{Velocity of drone}{Search distance}

(8)

Two types of simulations were performed. In the first, the search altitude was fixed at 20 m, the value of β was fixed at 0.0, and the effects of the false alarm value α on the search distance and time were observed while varying the value of α from 0.0 to 1.0. The results are shown in Figure 4. In the second simulation, the search altitude was fixed at 20 m, the value of α was fixed at 0.0, and the missed detection value β was varied from 0.0 to 1.0 while the effects on the search distance and time were examined. The results are illustrated in Figure 5.

Figure 4.

Total search distance and time for each method at a fixed search altitude and fixed β value.

Figure 5.

Total search distance and time for each method at a fixed search altitude and fixed α value.

As shown in Figure 4, the search travel distance and search time increase as α increases at a fixed search height and fixed β. As shown in Figure 5, the search travel distance and search time increase as β increases at a fixed search altitude and fixed α. In this case, it can be seen that the increases in the search travel distance and time resulting from the increase in β are sharper than the increases in response to an increasing value of α. Therefore, as shown in the figures, it can be seen that β has a greater influence on the search travel distance and search time than α.

Simulation of search altitude

To investigate the influence of the search altitude on a probabilistic search, we used the values of α and β derived from actual experiments, listed in Table 2, for this simulation. Using these values, the search distance and time required for a successful search were calculated for different altitudes.

Figure 6(a) illustrates the number of rounds the UAV needed to locate the target for each of 100 searches, where a round refers to the UAV searching the entire target area once. As shown in the figure, as the altitude decreases, the number of required rounds increases.

Figure 6.

Number of cycles, search distance, and search time required for target search success: (a) number of cycles required for a target search success, (b) search distance of each round, and (c) search time of each round.

Figure 6(b) and (c) shows the search distance and time, respectively, at different search altitudes for the two sets of α and β values from Table 2. As shown in the figure, as the altitude decreases, the required search distance and time increase.

Figure 7 illustrates the accumulation of search distance and time values at different search altitudes using the values from Table 2. As shown in the figures, the search distance and time increase very rapidly as the search altitude decreases. Figure 8 shows the comparison of the total search distance and time at different search altitudes with a bar graph for both sets of α and β values. The figure shows that, for Data Set 1, the search distance and time at 10 and 5 m are about 2.8 times and 14.3 times larger, respectively, than those at 20 m. For Data Set 2, the search distance and time at 10 and 5 m are about 1.96 and 9.69 times larger, respectively, than those at 20 m.

Figure 7.

Change in search performance at different search altitudes for each experimental data set.

Figure 8.

Difference in search performance at different search altitudes for each real data set.

Therefore, we can see that, when the experimentally obtained values of α and β are used, the search altitude has a significant impact on the success of a search in terms of speed.

Discussion

In this study, various simulations were conducted assuming actual flight conditions due to several constraints. However, we set the simulation environment, that is, the performance of the drone performing the search, and the data collection method to be the same as the actual environment.

In the simulation, we simulated the performance of the drone when the search altitude changes in various environments, which is an important factor affecting the search performance in the probabilistic search of the drones. We also investigate how the search performance changes when other important factors affecting search performance such as false alarm and missed detection change.

Through the analysis of the simulation results, we found that the search altitude is a very important factor in probabilistic search of drones and that missed detection is more important than false alarm among the factors affecting search performance in probability-based search.

In the simulations above, we investigated the effects of search altitude and the false alarm and missed detection rates in the probabilistic UAV search. There are a variety of factors other than the above factors affecting search performance. That is, the search algorithm that determines the search path of the drone, the number and distribution of the drones performing the search, the external environment of the search, and the processing location of the collected data may be the factors that may affect the search performance.

Several search strategies have been proposed in relation to the search algorithm for determining the search path of the drones. Such algorithms include random search, sweeping search,²⁶ optimal look-ahead search,¹⁵ saccadic search,²⁷ and Drosophila-inspired search.²⁸ These are the methods of finding neighboring cells in a search area. In addition to these basic search strategies, it is also possible to flexibly adjust the search altitude to detect the target based on the results of this study.

The number of drones performing the search and the arrangement of the drones are also very important issues affecting the search performance. When using multiple drones, it is important how the drone cooperates. Various studies^29,30 have already been conducted in relation to this problem. The arrangement of drones is also a very important issue, that is, how to arrange multiple drones in vertical and horizontal spaces.

The factors that influence the search performance of the drones mentioned above are all internal factors of the drones. However, when evaluating the performance of drones, external factors must be considered. Factors affecting the drone’s search performance include features such as buildings, trees, and climatic conditions such as rain and wind. These are factors to consider in the search performance of drones.³¹

Interest in big data processing is growing in recent years. The data that the drones collect in real time can be big data in some cases. However, it is very important to know where to process such large amounts of data. In this case, the data analysis performance of the drones and the urgency of data processing should be considered. Lots of research^32,33 has been carried out in relation to this problem, and we suspect it will become an interesting research topic in the future.

Conclusion

In this study, we analyzed the influence of the major factors that affect the speed of a probabilistic target search using a UAV. In particular, we performed simulations to analyze the effects of search altitude and the false alarm and missed detection rates of a search sensor.

First, we held the search altitude and one of the two variables α and β fixed while varying the other one and analyzed the resulting performance of the search. As the value of each variable increased, the required search distance and time increased. In particular, the search distance and time increased more rapidly when β was increased than when α was increased. Therefore, we inferred that β has a greater effect on the search performance.

Second, simulations were performed by introducing two sets of experimentally obtained values of α and β to investigate the effect of search altitude on search distance and time. For both data sets, as the search altitude decreased, the distance and time required for a successful search rapidly increased. In addition, it was found that the drone’s search performance changed very rapidly as the altitude changed. Specifically, the search performance became increasingly poor as the altitude decreased. Therefore, we can see that, when the experimental values of α and β are used, the search altitude is very important to the success of a search in terms of the speed, and we can confirm that altitude is a significant factor affecting the speed of a probabilistic search with UAV.

In the actual search environment of the drones, it is difficult to find the target in most navigation areas when the drones are searching for targets. For example, it is difficult to find very rare targets, such as those who fall in the wilderness that we assume in this study. Therefore, it is very important to let the drones navigate by specifying areas that are likely to find the target. When drones searched for a target, they would not be able to find the target in most of the search area, so the drone would learn this search environment, which may affect the search performance. This is likely to have a greater impact when the drones process data in a machine learning way.

In future research, we will try to explore a target search method that takes into account the drone’s learning of the search results and to carry out the simulation based on the learning results of the drone in addition to the search altitude, false alarm, and missed detection as factors that can affect the search of the drones’ target. We are also interested in developing more efficient algorithms that take into account false alarms, missed detections, and variations in the search altitude, as mentioned in the section “Discussion.”

Footnotes

Handling Editor: Sadik Gharghan

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) and funded by the Ministry of Education (No. 2017R1D1A1B03029895). This research was partly supported by Next Generation Information Computing Development Program through the NRF funded by the Ministry of Science and ICT (No. NRF-2017M3C4A7083676).

ORCID iD

Ilkyu Ha

References

Bekmezci

Sahingoz

Temel

. Flying ad-hoc networks (FANETs): a survey. Ad Hoc Netw 2013; 11: 1254–1270.

Sahingoz

. Networking models in flying ad-hoc networks (FANETs): concepts and challenges. J Intell Robot Syst 2014; 74: 513–527.

Chung

Burdick

. A decision-making framework for control strategies in probabilistic search. In: Proceedings of the 2007 IEEE international conference on robotics and automation, Rome, 10–14 April 2007, pp.4386–4393. New York: IEEE.

Chung

Burdick

. Analysis of search decision making using probabilistic search strategies. IEEE Trans Robot 2012; 28(1): 132–144.

Schneider

Gavrila

. Pedestrian path prediction with recursive Bayesian filters: a comparative study. In: Proceedings of the German conference on pattern recognition, 2013, pp.174–183, http://www.gavrila.net/Publications/gcpr13.pdf

Thrun

Burgard

Fox

. Probabilistic robotics. Cambridge, MA: MIT Press, 2005.

Zarco-Tejada

Diaz-Varelaa

Angileria

, et al. Tree height quantification using very high resolution imagery acquired from an unmanned aerial vehicle (UAV) and automatic 3D photo-reconstruction methods. Eur J Agron 2014; 55: 89–99.

Waharte

Trigoni

. Coordinated search with a swarm of UAVs. In: Proceedings of the 2009 6th IEEE annual communications society conference on sensor, mesh and ad hoc communications and networks workshops, Rome, 22–26 June 2009. New York: IEEE.

Symington

Waharte

Julier

, et al. Probabilistic target detection by camera-equipped UAVs. In: Proceedings of the 2010 IEEE international conference on robotics and automation, Anchorage, AK, 3–7 May 2010, pp.4076–4082. New York: IEEE.

10.

Trigoni

Waharte

Symington

. Probabilistic search with agile UAVs. In: Proceedings of the 2010 IEEE international conference on robotics and automation, Anchorage, AK, 3–7 May 2010, pp.2840–2845. New York: IEEE.

11.

Waharte

Trigoni

. Supporting search and rescue operations with UAVs. In: Proceedings of the international conference on emerging security technologies, Canterbury, 6–7 September 2010, pp.142–147. New York: IEEE.

12.

Ragi

Chong

. UAV path planning in a dynamic environment via partially observable Markov decision process. IEEE Trans Aerosp Electron Syst 2013; 49(4): 2397–2412.

13.

Chanel

Königsbuch

Lesire

. POMDP-based online target detection and recognition for autonomous UAVs. In: Proceedings of the seventh conference on prestigious applications of intelligent systems, 2012, https://www.researchgate.net/publication/239976139_POMDP-based_online_target_detection_and_recognition_for_autonomous_UAVs

14.

Chung

. Probabilistic search optimization and mission assignment for heterogeneous autonomous agents. In: Proceedings of the 2009 IEEE international conference on robotics and automation, Kobe, Japan, 6 July 2009. New York: IEEE.

15.

Wang

Chen

. Energy efficient placement of a drone base station for minimum required transmit power. IEEE Wirel Commun Lett. Epub ahead of print February 2018. DOI: 10.1109/LWC.2018.2808957, https://www.researchgate.net/publication/323371946_Energy_Efficient_Placement_of_a_Drone_Base_Station_for_Minimum_Required_Transmit_Power

16.

Mozaffari

Saad

Bennis

, et al. Drone small cells in the clouds: design, deployment and performance analysis. In: Proceedings of the 2015 IEEE global communications conference, San Diego, CA, 6–10 December 2015. New York: IEEE.

17.

Zorbas

Pugliese

Razafindralambo

, et al. Optimal drone placement and cost-efficient target coverage. J Netw Comput Appl 2016; 75: 16–31.

18.

Sekander

Tabassum

Hossain

. Multi-tier drone architecture for 5G/B5G cellular networks: challenges, trends, and prospects. IEEE Commun Mag 2018; 56(3): 96–103.

19.

Brunton

Bolin

Leon

, et al. Fright or flight? Behavioural responses of kangaroos to drone-based monitoring. Drones 2019; 3(2): 41.

20.

Lanillos

Gan

Portas

, et al. Multi-UAV target search using decentralized gradient-based negotiation with expected observation. Inform Sci 2014; 282: 92–110.

21.

Dogan

. Probabilistic approach in path planning for UAVs. In: Proceedings of the 2003 IEEE international symposium on intelligent control, Houston, TX, 8 October 2003. New York: IEEE.

22.

Riehl

Collins

Hespanha

. Cooperative search by UAV teams: a model predictive approach using dynamic graphs. IEEE Trans Aerosp Electron Syst 2011; 47(4): 2637–2656.

23.

Vidal

Shakernia

Kim

, et al. Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation. IEEE Trans Robot Autom 2002; 18(5): 662–669.

24.

Kothari

Pstlethwaite

. A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees. J Intell Robot Syst 2013; 71(2): 231–253.

25.

Cho

. A probabilistic target search algorithm based on hierarchical collaboration for improving rapidity of drones. Sensors 2018; 18(8): 2535.

26.

Kolling

Kleiner

. Multi-UAV motion planning for guaranteed search. In: Proceedings of the 2013 international conference on autonomous agents and multi-agent systems, 2013, pp.79–86, https://www.ida.liu.se/divisions/aiics/publications/AAMAS-2013-Multi-UAV-Trajectory.pdf

27.

Chung

Burdick

. Multi-agent probabilistic search in a sequential decision-theoretic framework. In: Proceedings of the IEEE international conference on robotics and automation, Pasadena, CA, 19–23 May 2008. New York: IEEE.

28.

Niedfeldt

Carroll

Howard

, et al. Enhanced UAS surveillance using a video utility metric. Unmanned Syst 2013; 1(2): 277–296.

29.

Menouar

Guvenc

Akkaya

, et al. UAV-enabled intelligent transportation systems for the smart city: applications and challenges. IEEE Commun Mag 2017; 55(3): 22–28.

30.

Bouachir

Abrassart

Garcia

, et al. A mobility model for UAV ad hoc network. In: Proceedings of the 2014 international conference on unmanned aircraft systems, Orlando, FL, 27–30 May 2014. New York: IEEE.

31.

Rubio-Hervas

Gupta

Ong

. Data-driven risk assessment and multicriteria optimization of UAV operations. Aerosp Sci Technol 2018; 77: 510–523.

32.

Luo

Jiang

, et al. Stability of cloud-based UAV systems supporting big data acquisition and processing. IEEE Trans Cloud Comput 2019; 7: 866–877.

33.

Jin

Wah

Cheng

, et al. Significance and challenges of big data research. Big Data Res 2015; 2(2): 59–64.