Keywords

1 Introduction

Basic missions of present unmanned aerial vehicle (UAV) are still intelligence, surveillance and reconnaissance (ISR) [1]. With increasing complexity of battlefield environment, it is now difficult for a single UAV to search a large area with multiple targets. However, cooperative search task implemented by multiple UAVs sharing information with each other is a well method to overcome sensor limitations and improve search efficiency.

Researches on multi-UAV search for uncertain static targets are now in hotspot, in which approaches can be mostly attributed to search path planning based on information graph. Baum M L proposes distributed protocol for greedy search strategy based on rate of return (ROR) map, and multi-UAV cooperative search is studied through optimal theory [2]. Fuzzy C-Mean clustering method is used in Literature [3] to distribute the search area to different UAVs, so that cooperative search case is converted into several single UAV search problems. With distribution of target probabilities given, Literature [4] makes a path planning of cooperative search with minimum cost.

Designing cooperative search strategies is significant for multiple UAVs to reduce return-free consumptions and gain more profits in a specified time. In this paper, multi-UAV search process is analyzed first, and then strategies of area clustering and path planning are given. Finally, two other algorithms are compared with it to evaluate its search effect.

2 Modeling

2.1 Grid Partition

Suppose that probability density function of all the targets satisfy continuous distribution, and a continuous search area of any shape can be partitioned into grids [5,6,7], as shown in Fig. 1: in the rectangular coordinate system, the maximum length of a search area along Axis X and Y are respectively l1 and l2; the area can be reasonably divided to form a series of cells; each cell is called a search unit.

Fig. 1.
figure 1

Grid partition of a search area.

Full size image

2.2 Related Indicators

Related indicators of UAV search process can be quantitatively described through detection, revenue and ROR which are defined as below [2, 3].

Detection function is used to estimate the detection ability of targets in a valuable search unit j with a time consumption of z. And its commonly used exponential form is given as follows:

$$ b\left( {j,z} \right) = 1 - e^{{ - \frac{Wvz}{A}}} . $$
(1)

where v is UAV search speed, W means scan width, and A stands for unit size.

When multiple UAVs are searching unit j, there is a revenue function defined as follows:

$$ e(j,z) = \sum\limits_{i = 1}^{n} {\omega_{i} p_{i} (j)b(j,z)} . $$
(2)

in which ωi represents weight for target i whose probability in unit j is pi(j).

The final expectation of multi-UAV cooperative search task is to get a larger profit in a shorter time. Therefore, ROR is introduced and a common definition is as follows:

$$ \frac{d(e)}{d(z)} = \frac{Wv}{A} \cdot e^{{\frac{ - Wvz}{A}}} \cdot \sum\limits_{i = 1}^{n} {\omega_{i} p_{i} \left( j \right)} . $$
(3)

which shows that ROR value will decrease if unit j is searched by a UAV when condition of \( \sum\limits_{i = 1}^{n} {\omega_{i} p_{i} \left( j \right)} \) is given.

3 Cooperative Search Strategies

Total revenue of search area is updating because ROR values of searching grids are changing. There is an assumption that each UAV can be informed of current ROR values of all the search units as well as present and next locations of other UAVs. As a result, UAV cooperative search process is resolved into a problem of putting forward specific strategies for search area distribution and search path planning.

3.1 Clustering of Search Area

To make a maximum ROR value in the multi-UAV cooperative search, the search area should be partitioned reasonably so that each part is a connected domain with similar sizes and has units with analogous ROR values. A clustering algorithm based on theory of minimum spanning tree (MST) is proposed to segment the search area.

Minimum spanning tree is a subgraph of a connected graph which contains all the original nodes. There is no loop inside and two new tree structures will be generated if one edge is cut off. MST method named Prim Algorithm is adopted in this paper [8], and Fig. 2 shows an example of MST after the grids are connected.

Fig. 2.
figure 2

An example of minimum spanning tree.

Full size image

Search area clustering can be transformed into tree division problem after the generation of minimum spanning tree. Stepwise strategy is used that only one edge of one tree is removed at a time. When selecting an edge, we consider its influence on the overall quality of clustering partition.

SSD, the intracluster square deviation, is a measure of dispersion of attribute values for the objects in a region [9]. Homogeneous regions have small SSD values. Thus, the quality measure of partition is the sum of SSDi, which needs to be minimized. But there are unbalanced situations when only taking SSD into account. To solve the disproportion problem, a penalty term is proposed to quality index Q seen as follows:

$$ Q = \sum\limits_{i = 1}^{k} {SSD_{i} } + 100 \cdot \hbox{max} (\alpha - \frac{{\hbox{min} (G^{*} )}}{{\hbox{max} (G^{*} )}},0). $$
(4)

where min(G*) and max(G*) represent the minimum and maximum grid numbers of a connected graph G* composed of every subtree Ti, and a balance factor α (0 ≤ α ≤ 1) is put forward.

Figure 3 shows the division of a search area with different balance factors. Graph (a) demonstrates that some parts will contain only a few nodes if no balance factor is given, and the other three graphs indicate that it is more balanced when α is increasing. However, similarity of search units in the same partition will decrease if the balance factor enlarges.

Fig. 3.
figure 3

Division with different values of α.

Full size image

The pseudo code of the above clustering algorithm can be seen in Table 1.

Table 1. Pseudo code.
Full size table

3.2 Optimizing of Search Path

It is necessary to optimize its path when a UAV is searching a cell, and a spiral flying model is designed with a consideration of its scan width, as shown in Fig. 4. In this way, the UAV can search evenly and gradually fly to the cell periphery so that it is conducive to moving to a next search unit if necessary. When ROR value of the cell is high, the UAV only need to continue circling to search more.

Fig. 4.
figure 4

Spiral flying model.

Full size image

ROR value is decreasing when UAV is searching the unit, so we should plan the search time for every UAV in each cell reasonably. To improve search efficiency, a concept of dynamic break value is introduced in the search process. Suppose that there are number of M search units ranked by ROR values and a quantile is defined as β (0 < β < 1), and then ROR value of No.\( \left\lceil {\beta M} \right\rceil \) unit is considered as the break value which is also automatically decreasing.

4 Simulation

Some comparison experiments are carried out through the above cooperative search strategies (Algorithm T for short) and two other common methods named Search Algorithm based on Fuzzy C-Mean Cluster (Algorithm C for short) [3] and Greedy Search Algorithm with Distributed Agreement (Algorithm D for short) [2].

4.1 Parameter Conditions

As to pi(j), the probability of every target in each cell, it is given in advance by intelligence resources [2]. Some major parameters of UAV searching task are listed in Table 2, and one example of initial ROR values with normal distribution is shown in Fig. 5. To ensure a consistent starting state, it is presumed that all UAVs begin flying at the bottom right corner with a minimum velocity value of 10 m/s and the same upward direction. As to UAV flight restrictions, there are axial and lateral acceleration constraints of 2.5 m/s2 and 0.55 m/s2 respectively, as well as a speed limit of 35 m/s. What’s more, Algorithm T has an additional condition of α = β = 0.3 and there is a restriction of 50 iterations on Algorithm C.

Table 2. Major parameters.
Full size table
Fig. 5.
figure 5

An example of ROR distribution.

Full size image

4.2 Evaluation Index

Within a certain cost of time, a sum of revenue values searched by multiple UAVs in the overall area can reflect the search performance, so total revenue is taken as a measurement of algorithm performance.

In order to evaluate the stability of algorithm, each algorithm is applied in the same case for many times so that we can get three sets of total revenues. In addition, coefficient of variation (CV) is defined in the following function, where σ is the standard deviation of a group of total revenues with average value μ. It is obvious that algorithm stability is better when CV value is smaller.

$$ CV = \sigma /\mu . $$
(5)

4.3 Results and Analyses

The UAV search paths using three different algorithms are shown from Figs. 6, 7 and 8 in the order of Algorithm T, C and D, and these trajectories of UAV indicate that there is shortest transfer route in Algorithm T which reveals that its path planning is practical and effective.

Fig. 6.
figure 6

Search paths using Algorithm T.

Full size image
Fig. 7.
figure 7

Search paths using Algorithm C.

Full size image
Fig. 8.
figure 8

Search paths using Algorithm D.

Full size image

Figure 9 shows different changing rules of total revenue with search time through different algorithms. From the beginning to 120 s, there is little difference among three algorithms. Since then, Algorithm T gains faster, and its total earnings are more than others. Further analyses of the other two algorithms are as follows: Algorithm C is better than Algorithm D due to some kind of area division, but both are in pursuit of the search unit with highest ROR, ignoring the overall revenue; these two algorithms have lower search efficiencies because of longer transfer flight without revenues.

Fig. 9.
figure 9

Changing rules of total revenue.

Full size image

20 experiments of each algorithm are carried out independently, and the results are listed in Table 3. The conclusion shows that the total revenue of Algorithm T is better than the other two, which is about 20.9% higher than Algorithm C and 38.6% higher than Algorithm D. Each algorithm has a small value of CV, but the stability of Algorithm T is more obvious. The main reason maybe that Algorithm T which uses MST clustering method is less affected by the initial condition, and there is trade-off analysis of search process.

Table 3. Results of 20 experiments.
Full size table

5 Conclusion

As to multi-UAV search issue, both area clustering and path planning are of great importance. Cooperative strategies in this paper are both practical and efficient, and the algorithm is effective because of its well stability.