Distributed Multi-Target Search and Surveillance Mission Planning for Unmanned Aerial Vehicles in Uncertain Environments

Abstract

In this paper, a distributed, autonomous, cooperative mission-planning (DACMP) approach was proposed to focus on the problem of the real-time cooperative searching and surveillance of multiple unmanned aerial vehicles (multi-UAVs) with threats in uncertain and highly dynamic environments. To deal with this problem, a time-varying probabilistic grid graph was designed to represent the perception of a target based on its a priori dynamics. A heuristic search strategy based on pyramidal maps was also proposed. Using map information at different scales makes it easier to integrate local and global information, thereby improving the search capability of UAVs, which has not been previously considered. Moreover, we proposed an adaptive distributed task assignment method for cooperative search and surveillance tasks by considering the UAV motion environment as a potential field and modeling the effects of uncertain maps and targets on candidate solutions through potential field values. The results highlight the advantages of search task execution efficiency. In addition, simulations of different scenarios show that the proposed approach can provide a feasible solution for multiple UAVs in different situations and is flexible and stable in time-sensitive environments.

1. Introduction

With the mission environment becoming increasingly complex and dynamic, multiple unmanned aerial vehicles (UAVs) have been used to form a cooperative combat system with complementary advantages and cooperation to enhance the overall combat capability of UAVs [1]. UAV swarm systems are inspired by swarm intelligence derived from the biological swarm behavior in nature such as the behavior of ants and bees, which is coordinated and controlled according to the swarm intelligence principle, making full use of local perception and interaction ability to complete relatively complex tasks. Meanwhile, as the number of UAVs increases, their computational and communication complexity will increase dramatically. Moreover, a UAV swarm has high requirements for system robustness, communication reliability, and capacity. Distributed control architecture employs an autonomous and cooperative method, breaking down complex issues into smaller sub-problems that can be addressed by individual nodes. This approach maximizes the independent abilities of each UAV and significantly enhances the computational efficiency and is widely used in search and rescue (SAR) [2], surveillance [3], civil security [4], searching [5,6,7], task allocation [8], and mapping [9] applications.

In the above tasks, the problem of path planning is crucial to ensure the safe and efficient completion of a particular task. In general, path planning issues associated with UAV flight can be categorized into two types: target-oriented issues and area coverage issues. In target-oriented problems, the objective is for the UAV to arrive at a designated target [10]. For instance, in a dynamic environment, UAVs may need to reach different targets for various purposes while resolving conflicts. In contrast, area coverage problems do not involve a specific destination, and the goal is typically to achieve full coverage of a designated area in the least amount of time possible [11]. Considering that in collaborative search and surveillance mission-planning problems, the UAV is not knowledgeable about the mission environment or the a priori state of the target, we mainly considered the study of the area coverage. In practical applications, monitoring missions that do not involve a ground control station can be quite complex. The control logic of an individual UAV must be meticulously designed to allow for smooth and autonomous switching between various operating modes such as search mode and continuous target-surveillance mode.

Existing research on multi-UAV collaborative search problems has focused on geometry-based methods, probability-based methods, and other related methods. The geometry-based approach focuses on individual UAV planning, integrating area decomposition, and task assignment algorithms to accomplish a multi-UAV coverage search of the area. Xu et al. [12] put forward an optimal terrain coverage algorithm for UAV mission areas. This offline method segments the open space into several cells and calculates the full-coverage motion path that connects these regions, generating coverage of the deployed sensor by solving a linear programming formulation. The authors of [13] divided the task area into several equal sub-regions, each corresponding to a specific robot, to ensure complete coverage while minimizing the coverage path. Mansouri et al. [14] addressed the problem of infrastructure inspection tasks by developing a theoretical framework that slices the infrastructure through the XOY plane to facilitate the identification of branches and provide each UAV with a path to achieve full infrastructure coverage. Choi et al. [15] used this method to consider the energy required by a UAV in different phases of flight, and for the problem of covering multiple regions with regular shapes, it was reduced to a traveling sales problem (TSP) with the goal of completely covering all regions with the shortest path. Although the geometry-based approach to planning offers benefits such as no omissions, a low repetition rate, and high reconnaissance efficiency, its centralized and offline nature represents a limitation of this approach in dynamic environments. If a UAV fails or the detection environment shifts, the entire team must execute a replanning process, resulting in significant computational cost.

The probability-based approach can assist UAVs in developing cooperative search strategies. With a probabilistic model characterizing the uncertainty of the unknown environment, UAVs can continuously sense the environment and update the probability map, thereby effectively using real-time detection information for online decision making, which is applicable to dynamic search processes. Takahiro et al. [16] investigated time-constrained multi-intelligent search and action problems. They used probability density maps and a time–cost-based reward prediction function to evaluate actions. Multiple agents can make near-optimal decisions, leading to maximum gains using probabilistic reasoning. Zhen Ziyang [17] introduced a collaborative mission-planning scheme for multiple UAVs using a hybrid artificial potential field and ant colony optimization (HAPF-ACO) method for UAVs to search for and attack moving targets in uncertain environments. Zheng et al. [18] proposed a biogeographically based optimization (BBO) method to minimize the expected time for aid workers to reach a target in response to the problem of human–UAV cooperative search planning and conducted experiments showing that the proposed algorithm was superior to many popular algorithms. Duan [19] proposed a dynamic discrete pigeon-inspired optimization (D²PIO) algorithm to handle cooperative search-attack mission planning for UAVs and achieved promising experimental results. However, probability-based path optimization methods are still subject to problems such as missing search targets and long search times. For example, the greedy strategy is short-sighted and only focuses on the largest value of the objective function in the current candidate raster (i.e., it only considers the information of a single raster or a single point) without considering the information of the whole region. Therefore, the frequently adopted greedy strategy generates duplicate paths and missing regions, and the whole search process may easily fall into local optimality, leading to decreased search efficiency as the task progresses. Furthermore, reinforcement learning (RL) has garnered increasing interest from researchers for search problems. By planning each UAV’s navigation trajectory, the problem of autonomous UAV navigation in extensive, complex environments has been tackled, treating it as a Markov decision process, and the problem of autonomous UAV navigation in large-scale complex environments has been solved by planning the navigation trajectory of each UAV, which is described as a Markov decision process [20,21]. However, these methods require a priori determination of the degree of impact of previous policies in different training phases and often require a large number of calculations, which may not be suitable for real-time systems.

In addition, different strategies have been adopted in target reconnaissance missions according to specific tactical needs. Three typical applications of tactical intent in reconnaissance missions can be specified: (1) UAVs converge to the vicinity of the target in a short period of time for follow-on fire operations [17]; (2) UAV swarms chase and round up the target in a hunting manner [22]; (3) UAVs converge quickly to the vicinity of the target and maintain surveillance continuously until the target is no longer functional [3]. For the third tactical requirement, in this paper, we propose a distributed autonomous cooperative mission-planning (DACMP) method in the mission scenario of the search and reconnaissance of targets by a heterogeneous UAV swarm, which enables the UAV swarm to achieve the reconnaissance of targets while still maintaining the optimal search capability.

Therefore, the main contributions of this paper can be summarized as follows:

(1) A DACMP method is initially presented for the search and surveillance of time-sensitive moving targets in an uncertain dynamic environment by considering the constraints of maneuverability, collision avoidance, and threat avoidance. To the best of our knowledge, this DACMP method has not been explored in the literature to date.

(2) This distributed method allows heterogeneous UAVs to adaptively switch between area coverage and target surveillance missions, ensuring that each target is continuously monitored by a suitable UAV while still maintaining the optimal search capability of the entire UAV swarm for other potential targets or to handle special situations.

(3) Inspired by the successful use of image pyramids in computer vision, we developed a grid map pyramid to represent the environment. This grid graph pyramid-based heuristic enables a multiscale view of the environment, which can prevent the search process from getting stuck in local optima, thus enhancing the search efficiency of the UAV swarm.

2. Cooperative Search and Surveillance Problem Description

In this section, the cooperative search and surveillance mission is modeled, and the mission environment is established. The search and surveillance mission-planning problem is defined, and the constraints of the model are provided.

2.1. Hybrid Mission-Planning Architecture and Assumption

Multi-UAV cooperative search and surveillance mission planning is a complex optimization problem with the aim of discovering and monitoring as many targets as possible under various constraints. As previously stated, our research focused on a group of heterogeneous fixed-wing UAVs performing search and surveillance missions in an unknown region. Assume that:

• UAVs are equipped with optical sensors that have a fixed detection range and are projected in a circle;
• The UAVs do not have any a priori knowledge of the threat and target location;
• Two different types of heterogeneous UAVs with different maximum speeds are employed. We believe that higher-speed UAVs have better search capabilities and are better-suited for search missions, whereas lower-speed UAVs are more suitable for continuous surveillance missions after the target has been detected;
• Each target only needs to be monitored by one UAV, and other UAVs are encouraged to conduct more exploratory movements to find other potential targets;
• The maximum speed of the target is lower than the speed of the UAV to ensure surveillance efficiency.

At the beginning of the mission, the UAVs are deployed in the mission area, and each UAV performs a coverage search of the area following a real-time online planned path, as shown in Figure 1. The aim is to discover as many targets as possible. Each UAV maintains a probabilistic grid map in the form of locally stored data. The UAVs then heuristically evaluate candidate solutions and make the next state-shifting decision within the performance constraints. Once the target is detected, UAVs within the target’s sphere of influence are flexible in adaptive mission allocation, with low-speed UAVs maintaining continuous detection of the target, whereas high-speed UAVs are better-suited to continue searching for other potential targets. By planning the next waypoint of the UAVs, the search and surveillance efficiency of the UAV swarm is maximized during the mission, resulting in improved execution performance.

2.2. Cooperative Search and Surveillance Model of the UAV Swarm

The status of the UAV swarm is defined as:

$$\chi =\left\{x_1,x_2,\dots ,x_i,\dots ,x_N\right\}$$

(1)

$$x_i={\left[x y v \theta \right]}^T$$

(2)

where $x_i$ is the state of UAV $i$, and $N$ is the number of UAVs. The purpose of cooperative search and surveillance of the UAV swarm is to cover the mission area and detect and monitor multiple targets while adhering to the given constraints. The objective function of this problem is defined as follows:

$$\begin{array}{l}{V}^{*}=\underset{V}{\arg \max }(J(\chi ))\\ s.t. \mathrm{C}\le 0\\ J(\chi )=J_S(\chi )+J_T(\chi )\end{array}$$

(3)

where $V$ is the decision input, which represents the waypoints of the UAV swarm in the next iteration; $C$ represents a set of constraint items; $J_S(\chi )$ represents the search benefit for the whole area of the UAV swarm; $J_T(\chi )$ represents the surveillance benefit of the UAV swarm, which can be defined as follows:

$$T(\chi )={\displaystyle \sum _{m=1}^{M}valu{e}_m}$$

(4)

where $valu{e}_m$ is the value of the target m, and $M$ is the number of targets monitored by the UAV swarm.

For the distributed control structure, each sub-UAV is equipped with a processor to build its own solution so that the centralized search-track mission planning indicator can be transformed into a distributed form:

$$\begin{array}{l}{{\displaystyle V}}_i^{*}=\underset{{{\displaystyle V}}_i}{\arg \max }(J_i(\chi ))\\ s.t.{ \mathrm{C}}_i\le 0\\ J_i(X_i)={\omega }_i{J}_{Si}(x_i,{\widehat{x}}_i)+(1-{\omega }_i)J_{Ti}(x_i)\end{array}$$

(5)

where ${\widehat{x}}_i$ represents the set of neighboring UAVs under the same communication topology, and ${\omega }_i$ is a Boolean variable, ${\omega }_i$ = 1 means that UAV $i$ is performing the search task; otherwise, UAV $i$ is performing a surveillance task. The global objective function $J(\chi )$ can be achieved by summing the local objective functions generated by each UAV:

$$J(\chi )={\displaystyle \sum _{i=1}^N\left({\omega }_i{J}_{Si}(x_i,{\widehat{x}}_i)+(1-{\omega }_i)J_{Ti}(x_i)\right)}$$

(6)

The specific form of $J_S(\chi )$ relies on the way the environment is modeled.

2.3. Uncertainty Map Model of The Environment

Due to the time-varying nature of the mission area, the characteristics of the target should be taken into consideration when modeling the environment. Considering that the target may move to the previously detected area, the environment was modeled using a time-varying uncertainty map [23] to ensure that the UAV swarm completes the tasks of search and tracking of all targets. Each UAV maintains an uncertainty map, which is divided into a two-dimensional probabilistic grid map $\{q_{11},q_{12},\dots ,q_{HW}\}$. According to the prior information of the mission, the uncertainty of a grid is expressed as follows:

$$q_{hw}=1-e^{-{\tau }_{\mathrm{v}}t}$$

(7)

where $t$ is the time elapsed since the last search. The uncertainty of a grid indicates the probability that it contains a hiding target, which depends on how long it has been since it was last detected and the prior mobility of the target. When $t=0$, the grid is within the current detection radius of the UAV, and the uncertainty of the grid is zero. The uncertainty of the grid increases over time, and the rate of change is determined by the memory factor (${\tau }_v$), which depends on the prior velocity ($v$) of the target. The uncertainty map for a single UAV over time is shown in Figure 2. In the search process, the uncertainty of the area that has not been detected is high, and the uncertainty within the UAV detection radius is 0. The uncertainty of the searched area gradually increases with time to achieve effective return visits to the searched area by the UAV in the long search process and timely follow-up of the mission area situation. The aim of the UAV swarm searching the map is to increase the certainty of the map. The more uncertain the map’s subtractions, the more aware the UAV swarm is of its environment, and the fewer places the target can hide. The surveillance coverage ratio indicates how certain the UAV swarm is about the mission area, which is calculated as the sum of the uncertainty of all grids [24]:

$$J_S(\chi )=1-{\displaystyle \sum _{h=1}^H{\displaystyle \sum _{w=1}^W\frac{q_{hw}^{}}{HW}}}$$

(8)

where $H$,$W$ indicates the size of the origin grid map.

2.4. Constraints of the Cooperative Planning Problem

The main constraints of multi-UAV flight path planning include dynamic constraints, collision avoidance constraints, threat avoidance constraints, and communication constraints, which are described as follows.

2.4.1. Dynamic Constraints

When carrying out a search mission, a fixed-wing UAV usually moves on a horizontal plane. The motion model can be simplified to a particle’s motion on a two-dimensional plane without considering the size of the UAV.

$$\left[\begin{array}{l}\dot{x}\\ \dot{y}\end{array}\right]=v\left[\begin{array}{l}\cos \theta \\ \sin \theta \end{array}\right]$$

(9)

$$\left[\begin{array}{l}\dot{v}\\ \dot{\theta }\end{array}\right]=\left[\begin{array}{l}a\\ \omega \end{array}\right]$$

(10)

where ${[x \mathrm{y}]}^T$ is the position of the fixed-wing UAV in flight profile, and $\theta$ is the heading angle. For fixed-wing UAVs, the linear acceleration ($a$) is restricted by engine performance, and its speed ($v$) is affected by air:

$$\begin{array}{l}{C}_a:\left|a\right|-a_{\max }\le 0\\ C_v:v_{\min }-v\le 0, v-v_{\max }\le 0\end{array}$$

(11)

The turning angular velocity is expressed by $\omega =\frac{v}{r}$, where the turning radius ($r$) should be larger than the minimum turning radius ($r_{\min }$).

$$C_r:r_{\min }-r\le 0$$

(12)

2.4.2. Collision Avoidance Constraints

Considering flight safety, the distance ($d_{uav}$) between UAVs should be longer than the minimum distance ($d_{\min }$) to avoid colliding:

$$C_{d_{uav}}:d_{\min }-d_{uav}\le 0$$

(13)

2.4.3. Threat Constraints

In general, the mission area contains numerous threats, which have a negative impact on the mission execution of UAVs. Therefore, UAVs must avoid threats while carrying out missions. The distance ($d_{threat}$) between a UAV and the threat should be longer than the threat radius ($R_T$), which can be expressed as:

$$C_c:R_T-d_{threat}\le 0$$

(14)

3. Design of DACMP

3.1. Model Solving

Inspired by the foraging behavior of birds, PSO is a technique with many key advantages that has been widely used in path planning for multiagent navigation [25,26,27]. Two important characteristics of PSO are related to swarm intelligence, namely, cognition and social coherence, which allow each particle of the population to search for solutions by following individual and group experiences rather than using traditional evolutionary operators such as mutation and crossover [25]. Therefore, compared with other algorithms, the PSO algorithm has advantages in terms of computational efficiency and stable solution convergence [28]. Moreover, PSO is not considerably affected by changes in the initial conditions and the objective function, and can adapt to various environmental constructions with a small number of parameters [29].

Suppose that N UAVs are performing a cooperative search and surveillance mission, and each UAV corresponds to a particle population composed of M particles, which represent a possible solution. Each particle can be regarded as a searching individual with a certain flight speed and direction in n-dimensional search space, and the current position of the particle is a candidate solution to the corresponding optimization problem. Particles are randomly initialized within the blue circle outside the detection radius ($R_s$), as shown in Figure 3. The particle moving to the optimal position changes its state by referring to its previous optimal experience and the experience of other individuals in the swarm.

To avoid early convergence to a local optimum and further improve the performance of the PSO, the algorithm is improved. First, the initial values of the control variables obey a normal distribution, traversing the allowed range. Second, according to the literature [30], inertia weight ($\omega$) and cognitive and social coefficients ($c_1$, $c_2$) are introduced, which decrease linearly with each iteration. Finally, a random value ($Q$) is added to the position update formula, expressed by:

$$z_{kd}^{t+1}=z_{kd}^t+\Delta z_{kd}^{t}Q$$

(15)

where $z_{kd}^t$ and $\Delta z_{kd}^t$ are the position and position increment vectors of particle $k$ in the $d$-th dimension, respectively.

3.2. State Transfer

The state transfer of a UAV is used to evaluate the quality and feasibility of each particle, and the objective value ($J(\chi )$) is maximized by a reasonable design of the state transfer function. We abstract the motion environment of the UAV swarm as a potential field, and the potential field value ($f(k)$) is used to measure particle $k$. In the search process, the higher the uncertainty in the region, the greater the search gain of the UAV and the more the UAV tends to move to that region, so the effect of the uncertainty map on particle $k$ is modeled by the attraction potential value ($f_s(k)$). When the target appears within the detection range of the UAV, the target generates an attractive potential field for the particles corresponding to the UAV within its influence range, thereby converging the UAV’s waypoints toward the target. In order to ensure that a target is monitored by only one UAV, the competing repellent potential values between UAVs are also considered so that the potential value received by particle $k$ of a UAV within the target influence range is represented as $f_t(k)$. The total potential value ($f(k)$) of a particle can be described as:

$$f(k)=f_s(k)+f_t(k)$$

(16)

3.2.1. Construction of Pyramid Map

When a UAV performs a search mission, the goal is to reduce the uncertainty in the mission area to maximize the probability of the detection of the target. Therefore, UAVs tend to fly to locations with high uncertainty. However, a single level of an uncertainty map is not enough to represent the whole information of the mission area. Information at different scales also contributes to the understanding of the environment. With the aim of obtaining a larger global view, the image pyramids initially used in computer vision were a series of images arranged in a pyramid shape with gradually decreasing resolution from the same original image.

Inspired by its successful use in computer vision, a map pyramid was constructed for a better understanding of the mission area. The map pyramid is a multiscale representation of maps, which is an effective structure with simple concepts to interpret maps with multiple resolutions for a better understanding of the task area. The best-known hierarchical structures are Gaussian [31] and Laplacian pyramids [24]. The pyramid model is one of the most intuitive multiscale descriptions of the signal and generally consists of two steps: first, the map is smoothed by a Gaussian filter; then, the smoothed map is sampled or interpolated to obtain a sequence of scaled-down or scaled-up maps, as shown in Figure 4. Each level of the map in the sequence is the result of the sampling of every other row and column after Gaussian filtering of the previous level of the map. That is,

$$G_l(\alpha ,\beta )={\displaystyle \sum _{m=-2}^2{\displaystyle \sum _{n=-2}^{2}w(m,n)G_{l-1}(2\alpha +m,2\beta +n)}}$$

(17)

where $G_l(\alpha ,\beta )$ is the map of the $l$-layer Gaussian pyramid; $G_0$ is the original map as the lower layer of the Gaussian pyramid; $w(m,n)=h(m)\cdot h(n)$ is an $m\times n$ window function with low-pass property; $h(m)$ is the Gaussian density distribution function that satisfies the following constraints: normalization, symmetry, parity term, and other contribution terms. Then, a typical 5 × 5 window function $w(5,5)$ can be expressed as follows:

$$w(5,5)=\frac{1}{256}\left[\begin{array}{ccccc}1& 4& 6& 4& 1\\ 4& 16& 24& 16& 4\\ 6& 24& 36& 24& 6\\ 4& 16& 24& 16& 4\\ 1& 4& 6& 4& 1\end{array}\right]$$

(18)

Thus,$G_0$, $G_1$, ..., $G_L$ form the Gaussian pyramid of the uncertainty map.

To prevent the waypoints from falling into local optima during the search process, we used information from each layer of the map to construct an attractive potential function, which can be expressed as:

$$f_{S,l}(k)=\frac{{\displaystyle \sum _{l=1}^L{\lambda }_{l}P(X_i^k(t),l)}}{1+{{\displaystyle \left(\frac{D(x_i(t),X_i^k(t))-R_i^{search}}{R_i^{search}}\right)}}^2}$$

(19)

where $P(X_i^k(t),l)$ is the uncertainty that the potential target exists in the same region as particle $k$ in the $l$-th level of the map pyramid at moment $t$. Regions with high uncertainty should have a higher search priority. ${\lambda }_l$ is a weight used to balance the uncertainty of each layer, and $R_i^{search}$ is the detection radius of UAV $i$. A Dubins path ($D(x_i(t),X_i^k(t))$) is used to measure the distance from particle $k$ to UAV $i$.

$f_{S,l}(k)$ describes the local potential field of the UAV; therefore, knowledge of the environment is still short-sighted. In order to further improve the global search capability of the UAV, an area with high uncertainty and that could be reached by the current UAVs in the next phase in the whole area was detected in the upper layer of the pyramid. Taking the seven-layer pyramid as an example, the seventh layer of the pyramid divided the map into 4 x 4 sub-areas. The center point of the area with the highest uncertainty among the eight areas adjacent to the current UAV was selected. The attractive field function of the global guidance point of particle $k$ is expressed by:

$$f_{s,g}^{}(k)=\frac{1}{1+e^{\frac{\theta (P(x,y),x_i(t),x_i^k(t))}{\pi }}}$$

(20)

Figure 5 shows a larger view of the global guideline ($P(x,y)$) represented by the center of the nearby area. $\theta (P(x,y),x_i(t),x_i^k(t))$ is the angle among the position of the global guideline ($P$), UAV $i$, and particle $k$, which causes the optimized waypoint to be more inclined to the direction of the global guideline and guides the UAV to search in the direction of the high-uncertainty region, thereby improving the search efficiency.

$$f_S(k)=\eta f_{S,l}(k)+(1-\eta )f_{S,g}(k)$$

(21)

where $\eta$ is the balancing factor and is usually set to 0.5 to maintain a balance between the local and global information.

3.2.2. Distributed Adaptive Target Allocation Approach

When the UAVs detect one or more targets, the targets have an attractive effect on the particles within their sphere of influence, guiding the UAVs toward the targets and maintaining surveillance on them. The attraction potential value of the target to particle $k$ is expressed as follows:

$$f_{t,att}(k)=\left\{\begin{array}{l}{\displaystyle \sum _{m=1}^M\frac{{\omega }_{t,i}}{d(X_i^k(t),g_m(t))v_i^{\max }{v}_i^{\max }}} if(d(X_i^k(t),g_m(t))<D_i)\hfill \\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}else\hfill \end{array}\right.$$

(22)

where ${\omega }_{t,i}$ is the weight of an attractive potential item; $g_m(t)$ is the state of target $m$ at time $t$; $d(X_i^k(t),g_m)$ denotes the distance between the particle $k$ and target $m$; $v_i^{\max }$ is the maximum velocity of UAV $i$. $D_i$ is the maximum radius of influence of the target on UAV $i$. As shown in Figure 6, both the high-speed UAV1 and the low-speed UAV2 were within the range of influence of the target. Because the high-speed UAV is more suitable for area exploration and the low-speed UAV is more suitable for maintaining continuous surveillance of the target, the low-speed UAV had a larger range of influence and was more vulnerable to the target than the high-speed UAV.

When more than one UAV is within the scope of the target, the exclusion behavior between UAVs is introduced. The UAV swarm is encouraged to perform more exploration actions while ensuring that one target is scouted by one UAV, preventing UAVs from clustering in a small group, therefore searching for all targets faster. The corresponding repulsive field value of particle $k$ is expressed as:

$$f_{t,rep}^{}(k)=\left\{\begin{array}{l}-{\displaystyle \sum _{j=1,j\ne i}^N\frac{{\omega }_{r,i}^{}}{d(X_i^k(t),x_j(t+1))v_i^{\max }{v}_j^{\max }}} if both in the scope of target\hfill \\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}else\hfill \end{array}\right.$$

(23)

where ${\omega }_{r,i}$ is the weight of the repulsive potential item, and $d(X_i^k(t),x_j(t+1))$ denotes the distance between particle $k$ of UAV $i$ and the waypoint of UAV $j$ at the next moment ($t+1$). Therefore, the potential energy function combining the target and other UAV effects is:

$$f_t(k)=f_{t,att}(k)+f_{t,rep}(k)$$

(24)

According to the different motion characteristics of the UAVs, we can adjust the values of $f_{t,att}$ and $f_{t,rep}$ to meet the task assignment requirements. Figure 7 depicts a case of two heterogeneous UAVs competing for a target. Assuming that a high-speed UAV with greater search capability detects the target first, if there is no low-speed UAV within the target range, the high-speed UAV maintains surveillance of the target, and if a low-speed UAV appears within the target range, the integrated potential energy field of the nearby low-speed UAV changes at this time. To make the high-speed UAV with higher search capability continue to explore the potential target and the lower-speed UAV maintain surveillance of the target, the attractive potential value of the target to the particle of the low-speed UAV should be greater than the repulsive potential value of the high-speed UAV to the particle of the low-speed UAV. Then, the integrated potential field guides the low-speed UAV toward the target; this inequality can be achieved by adjusting ${\omega }_t$ and ${\omega }_r$ as follows:

$$\frac{{\omega }_{t,low}}{{{\displaystyle v}}_{\max }^{low}}>\frac{{\omega }_{r,low}}{{{\displaystyle v}}_{\max }^{high}}$$

(25)

When the low-speed UAV moves near the target, the attractive potential value of the target to the particle of the high-speed UAV should be lower than the repulsive potential value of the low-speed UAV to the particle of the high-speed UAV:

$$\frac{{\omega }_t,high}{{{\displaystyle v}}_{\max }^{low}}<\frac{\omega r,high}{{{\displaystyle v}}_{\max }^{high}}$$

(26)

Then, the integrated force field leads the particle swarm of the high-speed UAV away from the target and back to the search state. The result is the same when the low-speed UAV finds the target first.

Assuming that two UAVs are isomorphic, to prevent multiple UAVs from tracking a target at the same time, the repulsive potential value between the particles of the isomorphic UAVs should be greater than the attractive potential value of the target to them:

$${\omega }_{t,i}<{\omega }_{r,i}$$

(27)

3.2.3. Local Planning Module Based on APF

Appropriate control sequences should be provided to the UAV to ensure that it can reach the next optimal track point quickly and safely. In a dynamic and uncertain environment, the main challenge associated with this problem is to plan and execute an inflation-free path. In recent years, the method based on APF has shown considerable potential in path planning in highly dynamic environments due to its rapidity and simplicity.

The next optimized waypoint generates a gravitational field ($U_{att}$) with the APF method, which causes the UAV to approach the next waypoint by applying a gravitational force ($F_{att}$) to the UAV. Based on the real-time waypoints ($f_i(X)$) of UAV $i$, the attraction field is expressed as:

$$U_{att,i}=k_{att}\cdot f_i(X)$$

(28)

where $k_{att}>0$ represents the gravitational coefficient. The gravitational force is the gradient of the gravitational potential field, which can be expressed as:

$$F_{att,i}(X)=\nabla U_{att,i}(X)$$

(29)

The UAV may encounter no-fly zones that need to be avoided to ensure safety. Assuming that the threat is a circle, based on the APF method, the threat area creates a repulsive force field, keeping the UAV away from the threat area. The repulsive force of threats can be obtained by:

$$F_{rep,i}^T=\left\{\begin{array}{l}{k}_{rep}\cdot {\displaystyle \sum _{e\in S}(\frac{1}{{‖x_{ie}‖}^2}-\frac{1}{{(d_{\max ,e}^t-d_0)}^2})\cdot {\widehat{x}}_{ie}},{‖x_{ie}‖}^2\le d_{\max ,e}^t\hfill \\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{‖x_{ie}‖}^2>d_{\max ,e}^t\hfill \end{array}\right.$$

(30)

where $k_{rep}$ is the repulsion coefficient, and $S$ is the threat set. $x_{ie}$ is the position vector of the detected $e$-th threat pointing to the $i$-th UAV, ${\widehat{x}}_{ie}=x_{ie}/‖x_{ie}‖$. $d_{\max ,e}^t$ represents the influence radius of the $e$-th threat’s repulsion field. $d_0$ is the minimum safe distance between the UAV and the threat center.

As the number of UAVs in the same airspace increases, the trajectories between UAVs may appear to be close or even overlap in time and space during mission execution. To ensure the safety of UAVs, we introduced repulsive fields between the UAVs [17]:

$$U_{rep,i}^V=\left\{\begin{array}{l}{\displaystyle \sum _{j=1,j\ne i}^N\frac{b}{e^{\frac{‖x_{ij}‖}{c}}-e^{\frac{{‖x_{ij}‖}_{\min }}{c}}}, if d_{uav}\in \left[d_{\min },d_{\max }^v\right]}\hfill \\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}else\hfill \end{array}\right.$$

(31)

where $b$ and $c$ are adjustable parameters that govern the magnitude and rate of change of the repulsive field, respectively; $‖x_{ij}‖$ is the distance from UAV $i$ to the UAV $j$; $d_{\max }$ represents the maximum operating distance of the repulsion field between the UAVs. The repulsion force between the UAVs is:

$$F_{rep,i}^V=-\nabla U_{rep,i}={\displaystyle \sum _{j=1,j\ne i}^N\frac{b}{c}\cdot \frac{1}{{(e^{\frac{‖x_{ij}‖}{c}}-e^{\frac{{‖x_{ij}‖}_{\min }}{c}})}^2}{e}^{\frac{‖x_{ij}‖}{c}\cdot {\widehat{x}}_{ij}}}$$

(32)

where ${\widehat{x}}_{ij}=x_{ij}/‖x_{ij}‖$ is the unit vector pointing from UAV $j$ to UAV $i$.

4. Experimental Analysis

To provide a comprehensive analysis of the DACMP algorithm presented in this paper, a series of simulation experiments was conducted. The simulation platform consisted of a desktop computer equipped with a 64-bit Windows 10 operating system, an Inter(R) Core (TM) i5-8265u 1.6 GHz CPU, and 8 G of RAM. The experiment was conducted using C++14 programming language, and MATLAB was employed for the analysis of the experimental results. In accordance with the information provided in Section 3, the procedural flow of the simulation is shown in Figure 8.

4.1. Experimental Parameters

The mission area was 50 km × 50 km, inside which both the UAVs and targets moved. A seven-layer map pyramid with a 100 m × 100 m bottom resolution was used to model the mission area. To verify the performance of the algorithm for heterogeneous UAVs in a multi-target search and tracking scenario, two different types of UAVs were adopted. We used the same kinetic model of the UAV to simulate the movement of the target and a Wiener random process of acceleration. The information on the UAVs and targets is shown in

Table 1. Parameter setup of the UAVs and targets.

Parameter	UAV		Target
Type	A	B	/
Speed	30~50 m/s	60–90 m/s	0–20 m/s
Linear acceleration	±0.4 m/$s^2$	±0.6 m/$s^2$	±0.4 m/$s^2$
Maximum bank angle	30°	20°	/
Detection radius	1.5 km	2 km	/
${\omega }_t$	5.0	2.0	/
${\omega }_r$	5.1	2.1	/
D	10 km	4 km

.

4.2. Comparison with the Search Model

Given that our method is an online, real-time, and distributed approach, it is suitable for comparison with other probability-based methods. For this purpose, we selected the basic but effective greedy strategy as the benchmark for comparison. To analyze the performance of the DACMP algorithm in the search process, we conducted a set of experiments and compared our heuristic strategy with the greedy strategy. The advantages of the two methods were analyzed by comparing two metrics: the coverage of the region and the number of targets searched. We used average values to estimate the performance of the two strategies after 30 executions.

Assuming that six type-B UAVs search for 14 targets in the mission area without considering threats, the initial positions of the UAVs were (0, 20) km, (0, 22) km, (0, 24) km, (0, 26) km, (0, 28) km, and (0, 30) km. We believed that the target information was captured without further surveillance if the target appeared in the UAV’s field of view, and the UAV then continues to search for the remaining targets.

The trajectories of the UAV swarm for a regional search task guided by two methods are shown in Figure 9 under the same initial conditions. The colored curves and dots represent the path and current position of each UAV, respectively. The black dashed line indicates the path of the target. Figure 9a shows the coverage path of multi-UAVs using the greedy strategy. The multiple UAVs can complete the target search of the region, but only the uncertainty of the current position of the candidate solution is considered in the optimization process, which can easily cause the whole search task to fall into the local optimum and lead to the repeated search of UAVs in a small area. Figure 9b shows the coverage path of multiple UAVs based on the DACMP heuristic strategy, which considers not only the uncertainty of the current candidate raster but also the uncertainty of the region near the raster as well as the directional guidance of the urgent region to be searched. The pursuit of long-term optimality enables the UAV to choose a better path to search the region, thereby improving the overall search coverage. The path of the UAV is evenly distributed in any part of the region.

Figure 10 displays the mission area coverage rates and the numbers of searched targets under the two methods. The proposed DACMP algorithm demonstrated better mission execution efficiency compared to the greedy strategy. As shown in Figure 10a, the mission area coverage rates of the greedy strategy and DACMP algorithm were roughly the same in the early stage. With an increase in the number of iterations, the advantage of the DACMP became increasingly apparent.

To ensure reliability, we carried out 30 simulations of the two methods to better analyze the performance. As shown in Figure 11, the simulation time of each method was 2000 s. The results showed that the average coverage area under the greedy strategy was 0.712, with 12.1 targets searched. The DACMP algorithm could search for 13.7 targets, and the average area coverage was 0.763. Therefore, our method has a significant advantage in terms of the number of searched targets and the coverage region.

4.3. Mission Execution Analysis

Organizing UAVs for collaborative search and surveillance missions under various constraints is a challenging task, particularly in complex environments with threats. To assess the feasibility and effectiveness of the proposed method, three cases were established. Case 1 and Case 2 were designed as non-threatening and threatening scenarios, respectively, to verify the feasibility and reliability of the proposed method. Case 3 builds on Case 2 by adding a new UAV in the middle of the mission to illustrate the scalability and adaptability of the solution.

Case 1: Three UAVs were deployed into the mission area, which contained two targets dispersed in a threat-free environment. UAV 1 and UAV 2 are high-speed UAVs with initial positions of (20, 22) km and (36, 22) km, with a low-speed UAV (3) located at (10, 22) km. Figure 12a–c represents multiple UAVs performing missions at different moments. As shown in Figure 12a, UAV 1 detected target 1 first, at which time the particles gradually converged to the position of target 1 under the effect of the attractive field, thereby guiding UAV 1 to fly toward target 1. Figure 12b shows that the low-speed UAV (3) within the sphere of influence of target 1 flew toward target 1 because its particles were more attracted to the target than repelled by UAV 1. When UAV 3 reached the vicinity of target 1, the particles of UAV 1 were subjected to a repulsive potential value greater than the attractive potential value, and UAV 1 automatically left target 1 to undertake the search task. As shown in Figure 12c, UAV 1 passed through the range of influence of target 2 while searching, but because UAV 2 maintained surveillance of target 2, UAV 1 was not disturbed by the attraction of the target and continued to search because the repulsive potential value among the isomorphic UAVs to which the particles of UAV 1 were subjected was greater than the attractive potential value of the target to the particles, so the nearest UAV could prioritize its own surveillance relationship with the target and avoid the entanglement of multiple isomorphic UAVs to one target, leading to a reduction in the search capability of the UAV swarm. Figure 12d shows the distance calculation results of multiple UAVs and target 1. This experiment shows that the proposed algorithm can make the UAVs adaptively switch between search and surveillance tasks according to their own capabilities so that the whole UAV swarm can reach the optimal search and surveillance state. In this case, the proposed algorithm can accomplish the distributed target assignment task quickly and efficiently without threats, which validates the basic feasibility of the proposed approach.

Case 2: Ten UAVs were deployed into the mission area, with six targets scattered in the environment and four threats. UAVs 1–5 are high-speed UAVs with initial positions of (10, 1) km, (29, 1) km, (30, 49) km, (15, 49) km, and (39, 49) km, and UAVs 6–10 are low-speed vehicles located at (20, 1) km, (35, 1) km, (5, 49) km, (23, 49) km, and (45, 49) km. Figure 13 represents multiple UAVs performing missions at different moments. Targets 4, 6, 1, 3, and 2 were the first to be detected and were temporarily kept under surveillance by high-speed UAVs 1, 5, 4, 3, and 2, respectively. Target 5 was detected and kept under continuous surveillance by low-speed UAV 7. After the high-speed UAVs detected the targets, they shared the target information with other UAVs through information interaction, and the particles of the low-speed UAVs near the targets started to converge toward the targets under the effect of the target attraction field. As shown in Figure 13b,c, UAV 9 flew toward target 3, and the particles of UAV 3 were repelled by UAV 9, which canceled the surveillance of the target and returned to search the area. The remaining high-speed UAVs (5, 4, and 1) also completed the mission transition with low-speed UAVs (10, 8, and 6, respectively). In this process, the low-speed UAVs replaced the high-speed UAVs to monitor the target, and the high-speed UAVs continued to search the area. The response result of the search and surveillance task is shown in Figure 14. Figure 15 illustrates the task execution of UAVs during the whole search and surveillance task-planning period. Figure 15 shows the coverage rate during the execution of the task. In this case, the UAVs completed the search and surveillance tasks while avoiding threats and adaptively completed the target assignment, illustrating the practicality of the proposed method in complex environments.

Case 3: To further verify the scalability and adaptability of the DACMP algorithm to the UAV swarm system, we added a new UAV in the process of mission execution in Case 2. We assumed that a new type-B UAV (UAV11) was initially located at position (50, 25) km and was added to the UAV swarm system at 300 s. The response result of the search and surveillance task is shown in Figure 16, and the task allocation of the UAV swarm is shown in Figure 17. As shown by the comparison of the coverage rate (Figure 18), the coverage increased after the addition of the new UAV, and the new UAV quickly adapted to the UAV swarm system and elevated the efficiency. Therefore, the multi-UAV system based on the DACMP algorithm is flexible, stable, and expandable.

5. Conclusions

In this paper, we proposed a novel distributed autonomous collaborative mission-planning method for the multi-UAV search and surveillance mission-planning problem. Satisfactory performance was achieved using grid pyramid time-varying uncertainty maps to simulate environmental cognition and construct heuristic search strategies. By modeling the effects of uncertain maps and targets on candidate solutions as potential field values, an adaptive distributed mission assignment was enabled for multiple UAVs, maximizing the area coverage capability of heterogeneous UAV swarms. Numerical simulation results and analyses demonstrated that the proposed method could achieve fast area coverage and dynamic task assignment under multiple constraints and is robust to the dynamic topology of the UAV swarm.

However, only two types of UAVs with area coverage search strategies were analyzed in this paper. How to cope with more UAV types and more target types is a problem to be considered in the future, and experiments will be conducted on the performance of the algorithm in real scenarios.