Article
Cooperative search for moving targets with the ability to perceive and evade using multiple UAVs
Correspondence to: Ziyi Wang, School of Automation, Nanjing University of Science and Technology, No.200 Xiao Lingwei Street Xuanwu District, Nanjing 210094, Jiangsu, China. E-mail:
Abstract
This paper focuses on the problem of regional cooperative search using multiple unmanned aerial vehicles (UAVs) for targets that have the ability to perceive and evade. When UAVs search for moving targets in a mission area, the targets can perceive the positions and flight direction of UAVs within certain limits and take corresponding evasive actions, which makes the search more challenging than traditional search problems. To address this problem, we first define a detailed motion model for such targets and design various search information maps and their update methods to describe the environmental information based on the prediction of moving targets and the search results of UAVs. We then establish a multi-UAV search path planning optimization model based on the model predictive control, which includes various newly designed objective functions of search benefits and costs. We propose a priority-encoded improved genetic algorithm with a fine-adjustment mechanism to solve this model. The simulation results show that the proposed method can effectively improve the cooperative search efficiency, and more targets can be found at a much faster rate compared to traditional search methods.
Keywords
1. INTRODUCTION
In recent years, with the continuous development of unmanned aerial vehicle (UAV) technology, the application of UAVs for searching civilian or military targets has been increasing. Path planning for target search has become an important research direction^{[1,2]}. In common search problems, target search can be divided into stationary target search and moving target search based on the motion ability of targets. In stationary target search, it is usually required to plan the UAVs' search path in advance to achieve coverage of the mission area^{[3-5]}. However, since the target location may change at any time, UAVs need to update the search path in real time based on the search results to achieve real-time and dynamic target search, leading to the problem of moving target search.
Searching for moving targets typically involves constructing an environmental model with one or several search information maps. These maps usually include a probability map^{[6]}, a certainty map (also known as uncertainty map)^{[7]}, and a pheromone map^{[8]}. UAVs then update these search information maps based on the dynamic search results, and the search path is planned based on the updated environmental information to improve the search efficiency and probability of discovering targets. There are several concerns raised about this problem in recent research.
Firstly, addressing the motion model of moving targets, Zhong et al.^{[9]} used a Markov chain to represent a hidden movement of targets and predict the position of targets. Hu et al.^{[10]} assumed a type of moving target that collaborates with fixed sensors providing UAV-sensing ability distributed in the mission area and proposed a method to predict the distribution of targets. Yue et al.^{[11]} proposed a specialized search map for the problem of cooperative search in unknown sea areas, which achieves dynamic changes in target movement estimation by assuming a fixed probability diffusion coefficient matrix for probability.
Regarding the target perception method of UAVs, Li et al.^{[12]} studied the use of knowledge distillation (KD) for target perception by presenting a comprehensive survey of KD-based object detection models developed in recent years and offered valuable perspectives on incorporating object detection into the target search strategy. Li et al.^{[13]} provided a multi-modal perception method using the spatial-temporal graph obtained from videos to promote latent space alignment in unsupervised multi-modal machine translation (UMMT), which intersects with UAV perception capabilities.
On the topic of the encoding method of the search path, Shorakaei et al.^{[14]} proposed a path planning method that considers obstacles or threat areas using a novel encoding method by a matrix, which uniformly considers all UAVs and the coordinates of their waypoint positions. Alanezi et al.^{[15]} propose a motion-encoded genetic algorithm with multiple parents, which realizes a unified motion-encoding on a series of UAVs. For optimization, Luo et al.^{[16]} used the fruit fly optimization algorithm to solve the search path, in which multiple fruit fly swarms are used to enhance the global search ability. They adopted different search strategies through a strategy switching method in the odor search and visual search stages, making the planning process more effective and stable. Similarly, other heuristic algorithms, such as differential evolution^{[17]} and pigeon-inspired optimization^{[18]}, have been used in search path planning.
To address the resource allocation problem, Fang et al.^{[19]} provide several policies and optimization algorithms to find a near-optimal solution associated both with high age of information as well as high power consumption. Zhang et al.^{[20]} investigated the reliable transmission scheme of downlink Non-Orthogonal Multiple Access (NOMA) systems and provided valuable insights into realizing reliable transmission using NOMA with randomly deployed receivers.
When searching for targets, the idea of model predictive control (MPC) is commonly used for long-term search. Zhou et al.^{[21]} applied distributed MPC (DMPC) combined with digital pheromone maps to realize the path planning of regional cooperative search. The DMPC method based on Nash equilibrium can achieve global optimization by locally optimizing the newly designed performance indicators. Yao et al.^{[22]} considered the communication network and information fusion between UAVs, designed a consensus algorithm with state predictor based on the minimum spanning tree structure to realize the fusion of predicted target probability map, and proposed a future-dependent MPC framework to realize the cooperative trajectory optimization and obtain the optimal control input. In addition, deep reinforcement learning (DRL) is also a promising tool for solving such problems. Wei et al.^{[23]} proposed a joint design of the unmanned aerial/surface/underwater vehicle (UAV-USV-UUV) network for cooperative underwater target hunting and conceived a novel deep Q-learning (DQN) algorithm to solve the target hunting problem. These research results provide several new perspectives to solve the target search problem.
Based on the studies mentioned above, this paper considers a multi-UAV regional cooperative search problem for targets with the ability to perceive and evade. The targets are equipped with a UAV-sensing device and move randomly in the mission area in a Markovian fashion. However, they can perceive the UAVs and take corresponding evasive actions by increasing the distance from the UAVs to achieve the ability of autonomous evasion, which increases the difficulty of target search.
This paper proposes a novel Cooperative Search Method for Targets with the ability to Perceive and Evade (CSMTPE). Firstly, we define the motion model of such targets in detail and design various search information maps together with their update methods based on the prediction of moving targets and the search results of UAVs. Secondly, we establish a multi-UAV search path planning optimization model based on MPC and design objective functions of search benefits and costs. Finally, we propose an improved genetic algorithm with a fine-adjustment mechanism (IGAFA) to solve this optimization model. The simulation results confirm the effectiveness of the proposed method.
Several contributions are made in this paper to the regional cooperative search problem for targets with the ability to perceive and evade:
(ⅰ) A new motion model of moving targets and a detection model for UAVs are proposed, which are more consistent with real-world search scenarios compared to the traditional methods.
(ⅱ) The updated formula for the traditional probability map used to predict target probability is improved, enhancing UAV search efficiency when dealing with the evasive maneuvers of moving targets.
(ⅲ) A search information map that reflects the detection response of moving targets is introduced, providing real-time feedback to UAVs on their search results.
(ⅳ) A multi-UAV search path planning optimization model is established, and a series of objective functions are designed for this model.
(ⅴ) A priority-encoding method for multi-UAV search paths and a priority-encoded IGAFA algorithm are proposed, effectively solving the optimization problem of multi-UAV search path planning effectively.
Overall, the effectiveness and efficiency of cooperative search for moving targets with the ability to perceive and evade are improved by these contributions, which could have practical applications in fields such as search, rescue, surveillance, and military operations.
The rest of this paper is structured as follows: Section 2 describes the search problem and presents a model for it. Section 3 defines the search information maps and their update methods. Section 4 introduced a multi-UAV cooperative search method and optimization model. Section 5 presents the encoding method, the IGAFA algorithm, and the complete search method. In Section 6, simulation experiments confirm the effectiveness of the proposed method. Finally, in Section 7, we present the conclusion.
2. PROBLEM FORMULATION
Assuming that there are
2.1. Motion model of UAVs
Mission area
Based on this definition, the multi-UAV system executing cooperative search tasks can be considered as a complete control system. The state variables of the UAVs at time
The control input of i-th UAV at time
2.2. Motion model of moving targets
As the motion law of the moving targets is unknown, it is assumed that the moving target has a maximum movement distance of
In order to effectively evade the search of UAVs, a virtual evasive force is defined in this paper, which includes two directions of evasion: away from the current position of the UAV and away from the forward path of the UAV. Figure 4 shows the virtual evasive force of a moving target when facing the search for i-th UAV.
In Figure 4,
where
where
In summary, based on the Gauss-Markov motion model, it is assumed that the motions in the x and y axes are independent of each other, the transition probability density function of the target from the position
In order to appropriately allocate the proportion of random movement and the directional evasive movement, the hyperbolic tangent (tanh) function is used to saturate the virtual evasive force of the target in this paper. Therefore, the means of
where
2.3. Detection model of UAV
The UAV detection range is defined as a square area with a side length of
The i-th UAV can only detect the area within
where
Moreover, the additional conventions are given here:
(ⅰ) To avoid collisions between UAVs, at most one UAV is allowed to search within each mission grid cell at any time instance.
(ⅱ) Communications between UAVs are ideal, and there is no communication delay.
(ⅲ) There is at most one target in a single mission grid cell.
(ⅳ) After discovering the target, the UAV will detach from the search sequence, enter a tracking state, and will not participate in subsequent search missions.
3. SEARCH INFORMATION MAP
When the mission area is discretized into grid cells, each search step of the UAV will be regarded as a search for each corresponding cell and give feedback on the results, and search information maps can be used to express the dynamic process of target search for each cell.
3.1. Probability map
A probability map is a search information map that reflects the existence probability of targets. Considering the difference in speed between a UAV and a moving target, the mission grid
Denote the existence probability of the target in
where
The transition of the existence probability based on target motion prediction under the influence of the movement of UAVs in any grid cell of the probability map can be represented by the probability diffusion coefficient of one cell to another. Denote the probability diffusion coefficient for transferring the existence probability of the target from
where
Based on the definition above, the updated existence probability of the target based on target motion prediction in
After the update based on target motion prediction, the probability map will be updated again based on the real-time detection results of airborne detection sensors of every UAV. In this paper, Bayesian criteria are used to dynamically update the probability map^{[8]}. The update of existence probability after time
(ⅰ) i-th UAV finds a target in
(ⅱ) i-th UAV finds nothing in
(ⅲ)
3.2. Certainty map
A certainty map is a search information map that reflects the degree of UAV exploration of the mission area. Considering that UAVs move in mission grid cells, the region division of the certainty map is the same as
(ⅰ) i-th UAV flies past with the situation that
As in Equation (14), the certainty of the grid cell increases with the detectability and access of UAVs.
(ⅱ)
where
Detection response map
A detection response map is a search information map defined in this paper to provide feedback on the target detection results of UAVs, which solves the problem of the lack of direct search results in conventional search information maps. The region division of the detection response map is the same as
(ⅰ) i-th UAV finds a target in
where
(ⅱ) i-th UAV finds nothing in
(ⅲ)
where
4. COOPERATIVE SEARCH PATH PLANNING
In order to improve the path planning efficiency of the search problem, a cooperative search method CSMTPE based on MPC is designed with the basic idea of time-domain rolling optimization, which transforms the large time-domain search problem into a continuous short-term path planning problem and guides the UAVs to search and track targets faster and more effectively^{[26]}.
4.1. MPC method
According to the idea of MPC, by predicting and evaluating the search behavior in a limited period of time under different search decisions, the control input required by the current UAV swarm can be determined based on the current environment information. Figure 7 shows the cooperative search decision-making process for multi-UAV systems based on the idea of MPC.
It is assumed that an optimization process will consider the cooperative search process of
Obviously, the quantitative search effectiveness of the search path can be uniquely obtained through an objective function
where
4.2. Objective function
Considering that no actual search actions occurred during the estimation of the search results in prediction, the virtual search process of future steps is based on the premise that no targets are found in each step.
4.2.1. Index of search effectiveness
The index of search effectiveness
where
In addition,
4.2.2. Index of uncertainty
The index of uncertainty
where
4.2.3. Index of detection response
The index of detection response
where
4.2.4. Index of motion cost
The index of motion cost
where
Based on the indices above, the objective function in Equation (19) is defined as follows:
where
5. SOLUTION ALGORITHM
It is the key to obtaining the optimal control input in the current step among numerous control decision sets for CSMTPE; therefore, this problem can be transformed into a standard nonlinear optimization problem. Among the normal solutions, the genetic algorithm (GA) is a general optimization algorithm with strong adaptability^{[27]}. GA is designed and proposed according to the evolution law of organisms in nature. It is a computational model simulating the natural selection and genetic mechanism of Darwin's biological evolution theory and is a method of searching for the optimal solution by simulating the natural evolution process.
In this section, a priority-encoding method for CSMTPE is proposed, and a fine-adjustment mechanism based on this encoding method is designed. Finally, this mechanism is applied to various chromosome operations of traditional GA, forming a priority-encoded IGAFA algorithm to solve the problem above.
5.1. Priority-encoded IGAFA algorithm
5.1.1. Priority-encoding method
Considering the potential issue of chromosomes being sensitive to small changes and having a high probability of illegitimate offspring caused by traditional direct encoding method, a priority list of the indices of mission grid cells is used as an indirect encoding method in this paper. The chromosome is encoded as
Firstly, this encoding method can solve the problem of illegal offspring chromosomes, ensuring the efficiency of the iterative process by complying with the UAV moving rules. Secondly, changing a single gene will not alter or only slightly alter the search path of the destination cells before and after that gene, reducing the sensitivity of the chromosome while ensuring the randomness of the search path; in other words, the priority-encoded path will be more conducive to focusing on the long-term search benefits, rather than the short-term benefits of each move.
5.1.2. Fine-adjustment mechanism
A fine-adjustment mechanism is proposed to improve the efficiency of evolution in traditional GA in this paper, which mainly optimizes the stochastic process in the evolution to fine-adjust the evolution direction. The fine-adjusted localization and mutation of genes are included in the specific applications as follows:
(ⅰ) Fine-adjusted localization of genes
Considering the problem of uneven distribution of key genes in priority-encoded chromosomes, a random probability density function for selecting genes with the iteration step
where
where
At the early stage of the iteration, the probability density function will show the characteristics of approximate uniform distribution. As the iteration process proceeds, the probability density function will gradually evolve from the uniform distribution to the exponential distribution. By using the probability density function above, a random number with a specific distribution pattern can be achieved as follows:
where
By using the method above, a gene can be uniformly selected in the early stage of the iteration, and gradually evolved in the later stage to achieve precise optimization of the higher priority part for a better optimization process.
(ⅱ) Fine-adjusted mutation of gene
In order to make the mutation operation in traditional GA more purposeful and enable the overall population to effectively jump out of the local optimal solution during the iteration process, a weight matrix
where
where
where
5.1.3. Improved chromosome operations
The fine-adjustment mechanism is used in the chromosome operations of traditional GA in IGAFA. Considering the characteristics of the priority-encoding method, the traditional crossover is divided into two types: sexual and asexual crossover. The specific chromosome-operations are as follows:
(ⅰ) Sexual crossover
Sexual crossover refers to the crossover with two chromosomes as parents, which is similar to the traditional crossover in GA. Firstly, two random chromosomes are selected as parents, the chromosomal location of the start of crossover
(ⅱ) Asexual crossover
Asexual crossover refers to the crossover with only one chromosome as a parent, which is used to adjust the access priority or location of destination cells. There are four crossover operators defined as follows:
a. Swap: Select two different genes
b. Insert: Select two different genes
c. Delete: Select one gene
d. Shift: Select two different genes,
where the shift function has the definition as follows:
(ⅲ) Mutation
Mutation is mainly used to attempt to access a new destination cell to increase the adequacy of access to the solution space in this problem. In advantageous circumstances, UAVs may approach new cells with high search benefits in the new search path. In this algorithm, the mutated gene is selected by Equation (29) and the mutation result is selected based on the probability distribution in Equation (32).
(ⅳ) Selection
Similar to the traditional selection in GA, a binary tournament selection method is used to select the chromosomes in the population.
5.1.4. Procedures of the priority-encoded IGAFA
The procedures of the priority-encoded IGAFA, i.e., the procedures to obtain the optimal set of control input sequences, are as shown in Table 1.
Procedures of the priority-encoded IGAFA
Name: | Priority-encoded IGAFA |
Goal: | Obtain the optimal set of control input sequence |
1: | Input: probability map |
2: | Output: the optimal set of control input sequence |
3: | Generate |
4: | for |
5: | From |
6: | From |
7: | From |
8: | |
9: | for |
10: | if the fitness of i-th chromosome is not calculated |
11: | Decode i-th chromosome to a set of control input sequence |
12: | Calculate the fitness |
13: | if |
14: | |
15: | |
16: | end |
17: | end |
18: | end |
19: | Update weight matrix |
20: | |
21: | From |
22: | end |
23: | return |
5.2. Complete search process
Based on the previous sections, the procedures of a complete search process for moving targets using CSMTPE, are as shown in Table 2.
Procedures of a complete search process using CSMTPE
Name: | Complete search process using CSMTPE |
Goal: | Find all moving targets |
1: | Initialize multi-UAV system state |
2: | while not all targets are found |
3: | Get the optimal set of control input sequence |
4: | From |
5: | Update |
6: | Update |
7: | Update |
8: | for |
9: | if any |
10: | Turn i-th into tracking state and no longer participate in subsequent search missions; |
11: | Clear the element of the discovered target in |
12: | end |
13: | end |
14: | |
15: | end |
6. RESULTS
Simulation experiments for the multi-UAV regional cooperative search problem in this paper are performed in Matlab. The computer configuration is as follows: Windows 10, CPU AMD(R) Ryzen(R) 7 4800HS of 2.9GHz up to 4.2GHz, Memory 16GB of 3200MHz.
The experiment assumes a military scenario where UAVs are used to search for targets of concealed enemy soldiers in a mission area. The UAVs search for enemies through airborne human detection equipment, while the enemies actively evade the UAVs' search. Set the size of the mission area as
6.1. Motion prediction of moving targets
Assuming that there are two targets to be searched in the mission area, the initial position of the target is subject to the two-dimensional normal distribution, where the means of position are
To test the update process of the probability map, three experimental scenarios were used: (Ⅰ) target prediction without the search interference of UAVs, (Ⅱ) under the search interference of static UAVs, and (Ⅲ) moving UAVs. Figure 8 shows the updating process of the probability map in different scenarios at simulation steps k = 0, k = 10 and k = 20. In scenario Ⅰ, as the targets are not affected by the UAV search, the target follows a Gauss-Markov motion model. The result shows that the existence probability of the target spreads towards adjacent grid cells, and the uncertainty of the target position increases with the simulation steps. In Scenario Ⅱ, the target will be subject to the evasive virtual force A generated by the UAVs in addition to random movement, showing a trend of evading the UAVs. The result shows that there is a significant reduction in the existence probability of the target around the UAVs. In Scenario Ⅲ, the target is affected by the evasive virtual forces A and B, and the result shows that the target in the UAVs' forward direction will additionally evade both sides of the forward direction, while the target behind the UAVs may return to the previous search area by random movement after the UAVs have moved away.
Compared with previous methods^{[10,11]}, the changes in the probability map in the simulation results are consistent with the actual experimental scenario rather than purely numerical assumptions, reflecting the reasonable evasive maneuvers of moving targets and improving the efficiency of the search process.
6.2. Analysis on the influence of different factors
In addition to the configuration in the first experiment, set
In this experiment, the coefficients in the objective function and the factors in IGAFA will be determined. Firstly, considering the sensitivity to various indices and the balance between benefits and penalties, set
Average number of targets found with different search coefficients
1.15 | 1.48 | 1.62 | |
1.28 | 1.55 | 1.68 | |
1.25 | 1.53 | 1.58 |
Table 3 indicates that the group of
Secondly, the factors in IGAFA will be determined by calculating the optimal search path for UAVs at their initial position. First of all, without considering the weight matrix during the mutation process, test the influence of different
Figure 9. Best fitness under different iteration steps with different
Next, considering the weight matrix during the mutation process, we test the influence of different
6.3. Process and result analysis of a complete search simulation
Based on the configuration in the second experiment, randomly arrange moving targets with pre-set position distribution and simulate the complete cooperative search process using CSMTPE with the procedures in Table 2. Figure 11 shows the search process of a complete search simulation, including the current search path, the search path for the next
In the probability map in Figure 11(a), the existence probability of the target dynamically changes with the search process, and the UAV swarm converges and aggregates the probability to the actual position of the targets, achieving an effective search process. The certainty map in Figure 11(b) reflects the currently searched area of the UAV swarm, avoiding repeated searches of the same area in a short time, while the lower certainty after a long time will guide the UAVs to revisit the area to enhance the search order in the later stage of the search. The detection response map in Figure 11(c) reflects the current target detection situation of the UAV swarm, which includes both the real alarm signal caused by the target and the false alarm signal of the sensor, and finally guides the UAVs to focus on searching the alarm area. Figure 11(a) also reflects that the search path guided by the CSMTPE can effectively explore the area with the initial existence probability of the target, and the priority of accessing the area with higher probabilities is greater. Meanwhile, the allocation of search areas among UAVs is also reasonable.
Furthermore, the above initial conditions are used for multiple simulation experiments, where the initial positions of the targets are randomly set differently in each simulation. The target search results within the maximum simulation step of 100 are recorded. Figure 12 shows the result of 40 Monte Carlo experiments of the search for two moving targets. The result indicates that the number of targets found gradually increases with the simulation steps, with an average of 1.83 targets found and a search completion rate of 92% within 100 simulation steps.
In order to simulate more search scenarios, five cases of configuration were designed here, with the number of UAVs and targets being 3:1, 3:2, 6:2, 6:3, and 6:4, respectively. Figure 13 shows the search process in different cases of UAV-target configuration. In each case, the background of each figure shows the probability distribution of the targets' initial position, while the positions of UAVs and moving targets are plotted at the moment when all targets were discovered. The result of the average number of targets found is shown in Table 4.
Average number of targets found with five cases of configuration
Number of targets | |||||||
"*" represents that all targets are found | |||||||
0.68 | 0.93 | 1^{*} | — | ||||
0.90 | 1.75 | 1.83 | 1.40 | 1.83 | 2^{*} | ||
— | 1.93 | 2.50 | 2.75 | ||||
— | 2.33 | 3.33 | 3.58 |
The result in Table 4 indicates that the larger the ratio of the target number to the UAV number, the higher the corresponding search completion rate, and the faster the target can be found, and it also proves that the CSMTPE proposed in this paper can effectively cope with the multiple target search in different target distribution situations.
In order to verify the effectiveness of the update method of probability map based on target motion prediction, the search result was tested under the same simulation conditions without using Equation (10) for the update of the probability map. Based on the search result in Table 4, Figure 14 shows an intuitive comparison of the search result with and without the motion prediction, and it clearly indicates that when target motion prediction is not used, the average number of targets found will significantly decrease, which is because probability map cannot effectively predict the random and evasive movement of the target. Moreover, when the UAV approaches the target, the existence probability of the target shifts between adjacent grid cells without motion prediction due to the rapid movement of the target, and the probability of losing the target will be significantly increased.
6.4. Comparison of different optimization algorithms
In order to compare the optimization effectiveness of the proposed optimization algorithm, a set of optimization algorithms will be used as a comparison in the following experiment. First of all, a motion-encoded particle swarm optimization^{[10]} (ME-PSO) and a motion-encoded genetic algorithm^{[15]} (ME-GA) are chosen as the comparison group of the direct motion-encoding method as these are commonly used to solve similar problems in recent research. Secondly, to test the proposed priority-encoding method, these optimization algorithms have been rewritten with corresponding encoding methods and denoted as PE-PSO and PE-GA, respectively. In addition, to compare with more optimization algorithms, a differential evolution (DE) algorithm^{[28]} and an artificial bee colony (ABC) algorithm^{[29]} are chosen and rewritten with priority-encoding methods, which are PE-DE and PE-ABC.
In order to match the parameters used by IGAFA in the second experiment, the parameters in GA are set to
Among the algorithms that use the priority-encoding method, traditional PE-GA has the slowest optimization speed. By comparison, PE-PSO, PE-DE and PE-ABC have faster optimization speeds in the early stage due to their characteristics being close to random-search. However, in the later stage, considering the continuity problem of the solution, the optimization speed significantly decreases. As an improved algorithm for GA, priority-encoded IGAFA optimizes the evolution direction while retaining the excellent genes of its parents, making the evolution process closer to the encoding characteristics, thus maintaining good optimization efficiency in the middle and later stages of the optimization process. It proves that the fine-adjustment mechanism proposed in this paper has efficient optimization performance when dealing with priority-encoding methods.
In order to further compare the influence on the target search process when using different optimization algorithms, PE-GA and ME-PSO are selected as typical optimization algorithms representing priority-encoding method and motion-encoding method, respectively.
Table 5 shows the average execution time with different
Average execution time by typical optimization algorithms
Number of UAVs | |||||||
PE-GA | ME-PSO | OURS | PE-GA | ME-PSO | OURS | ||
2.8s | 2.6s | 3.1s | 4.9s | 4.8s | 5.1s | ||
4.6s | 4.5s | 4.8s | 7.8s | 7.5s | 8.5s |
We apply different algorithms to the search scenarios set in the third experiment and simulate the cooperative search using CSMTPE. The results of the average number of targets found using different optimization algorithms at simulation step
Average number of targets found using typical optimization algorithms at simulation step
Number of targets | |||||||
PE-GA | ME-PSO | OURS | PE-GA | ME-PSO | OURS | ||
"*" represents that all targets are found | |||||||
1^{*} | 0.43 | 1^{*} | — | ||||
1.68 | 0.85 | 1.83 | 1.95 | 1.18 | 2^{*} | ||
— | 2.58 | 1.35 | 2.75 | ||||
— | 3.23 | 1.85 | 3.58 |
Table 6 indicates that the ME-PSO has a significantly smaller number of targets found compared to other algorithms, while the search result using PE-GA is slightly worse than that using IGAFA. This is consistent with the conclusion obtained in Figure 15, proving that IGAFA is more suitable for solving such problems.
Comparison of different search methods
We now compare the CSMTPE proposed in this paper with traditional greedy search method and parallel search method. The greedy search method calculates each grid cell within the motion range of each UAV in each simulation step according to Equation (10) with
Average number of targets found using different search methods at simulation step
Number of targets | |||||||
Greedy search | Parallel search | CSMTPE | Greedy search | Parallel search | CSMTPE | ||
"*" represents that all targets are found | |||||||
0.93 | 0.60 | 1^{*} | — | ||||
1.65 | 1.23 | 1.83 | 2^{*} | 1.38 | 2^{*} | ||
— | 2.40 | 2.00 | 2.75 | ||||
— | 3.13 | 2.48 | 3.58 |
Table 7 indicates that CSMTPE has more targets in comparing search methods. Parallel search does not consider the initial distribution information of the target, and the search range is too rough, resulting in poor search efficiency. Greedy search has a similar search rate to CSMTPE in Case I and Case III, but overall, the number of targets found is lower than CSMTPE.
As shown in Figure 16, when using the greedy search method, the number of targets found is significantly less than that of CSMTPE at simulation step
Considering the existence of situations where the prior information of the target is unknown, the original problem will degenerate into a covering search problem. Under this circumstance, another similar experiment is conducted, and the search results are shown in Table 8.
Average number of targets found using different search methods at simulation step
Number of targets | |||||||
Greedy search | Parallel search | CSMTPE | Greedy search | Parallel search | CSMTPE | ||
0.38 | 0.58 | 0.73 | — | ||||
0.95 | 1.23 | 1.35 | 1.20 | 1.43 | 1.53 | ||
— | 1.53 | 1.95 | 2.15 | ||||
— | 2.25 | 2.53 | 2.68 |
When the prior information of the target is unknown, the search results reflect the conclusion that the search efficiency of CSMTPE will degenerate into the level of that using the parallel search method. Meanwhile, it also shows that the greedy search method performs significantly worse compared to other search methods above due to the lack of long-term predictability. In summary, it proves that CSMTPE can adaptively and effectively solve the multi-UAV regional cooperative search problem.
7. CONCLUSIONS
This paper addresses a challenging multi-UAV regional cooperative search problem for targets with the ability to perceive and evade. In this scenario, moving targets can detect the presence of UAVs and take evasive actions based on the UAVs' motion patterns, increasing the difficulty of target search. To solve this problem, we propose a novel search method called the CSMTPE for multi-UAV.
Firstly, we defined the motion model of such targets and design various search information maps and their update methods. Secondly, we established a multi-UAV search path planning optimization model based on MPC and designed a CSMTPE with various objective functions of search benefits and costs. Thirdly, we proposed an IGAFA to solve this optimization model. Finally, we conducted simulation experiments to evaluate the proposed methods, and the results confirm their effectiveness.
Our experimental results show that the CSMTPE with IGAFA has higher search efficiency compared to traditional search methods, making it well-suited for the dynamic search process for targets with the ability to perceive and evade. Overall, the proposed method could have practical applications in various fields, such as search and rescue, surveillance, and military operations.
DECLARATIONS
Authors' contributions
Made substantial contributions to the conception and design of the study and performed simulation and interpretation: Wang Z
Provided administrative, technical, and material support: Zou W, Li S
Availability of data and materials
Not applicable.
Financial support and sponsorship
None.
Conflicts of interest
All authors declared that there are no conflicts of interest.
Ethical approval and consent to participate
Not applicable.
Consent for publication
Not applicable.
Copyright
© The Author(s) 2023.
REFERENCES
1. Qu Y, Sun Y, Wang K, Zhang F. Multi-UAV cooperative search method for a moving t on the ground or sea. In: 2019 Chinese Control Conference (CCC). IEEE; 2019. pp. 4049-54.
2. Wang S, Njau CE, Jiang Z. Design and implementation of multi-uav cooperation search experimental platform. In: 2021 5th International Conference on Robotics and Automation Sciences (ICRAS). IEEE; 2021. pp. 94-8.
3. Chen S, Li C, Zhuo S. A distributed coverage algorithm for multi-UAV with average voronoi partition. In: 2017 17th International Conference on Control, Automation and Systems (ICCAS). IEEE; 2017. pp. 1083-86.
4. Pehlivanoglu YV. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV. Aerosp Sci Technol 2012;16:47-55.
5. Apostolidis SD, Kapoutsis PC, Kapoutsis AC, Kosmatopoulos EB. Cooperative multi-UAV coverage mission planning platform for remote sensing applications. Auton Robot 2022;46:373-400.
6. Fu X, Liu K, Gao X. Multi-UAVs communication-aware cooperative target tracking. Appl Sci 2018;8:870.
7. Xiao X, Dong Z, Wu J, Duan H. A cooperative approach to multiple UAVs searching for moving targets based on a hybrid of virtual force and receding horizon. In: IEEE 10th International Conference on Industrial Informatics. IEEE; 2012. pp. 1228-33.
8. Ru Cj, Qi Xm, Guan Xn, et al. Distributed cooperative search control method of multiple UAVs for moving target. Int J Aerospace Eng 2015;2015:1-12.
9. Zhong Y, Yao P, Sun Y, Yang J. Method of multi-UAVs cooperative search for Markov moving targets. In: 2017 29th Chinese Control And Decision Conference (CCDC). IEEE; 2017. pp. 6783-89.
10. Hu X, Liu Y, Wang G. Optimal search for moving targets with sensing capabilities using multiple UAVs. J Syst Eng Electron 2017;28:526-35.
11. Yue W, Xi Y, Guan X. A new searching approach using improved multi-ant colony scheme for multi-UAVs in unknown environments. Ieee Access 2019;7:161094-102.
12. Li Z, Xu P, Chang X, et al. When object detection meets knowledge distillation: A survey. IEEE Trans Pattern Anal Mach Intell 2023;45:10555-79.
13. Li M, Huang PY, Chang X, et al. Video pivoting unsupervised multi-modal machine translation. IEEE Trans Pattern Anal Mach Intell 2023;45:3918-32.
14. Shorakaei H, Vahdani M, Imani B, Gholami A. Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm. Robotica 2016;34:823-36.
15. Alanezi MA, Bouchekara HR, Apalara TAA, et al. Dynamic target search using multi-UAVs based on motion-encoded genetic algorithm with multiple parents. IEEE Access 2022;10:77922-39.
16. Luo R, Zheng H, Guo J. Solving the multi-functional heterogeneous UAV cooperative mission planning problem using multi-swarm fruit fly optimization algorithm. Sensors 2020;20:5026.
17. Ma C, Zhu X, Liu S, Gui J, Yao W. A multi-UAV cooperative searching method based on differential evolution. In: 2022 34th Chinese Control and Decision Conference (CCDC). IEEE; 2022. pp. 5643-48.
18. Zhikuo C, Chen W, Yuxing Z. A cooperative approach to multi-UAVs search for mobile targets based on pigeon-inspired optimization. In: 2018 IEEE CSAA Guidance, Navigation and Control Conference (CGNCC). IEEE; 2018. pp. 1-8.
19. Fang Z, Wang J, Ren Y, et al. Age of information in energy harvesting aided massive multiple access networks. IEEE J Select Areas Commun 2022;40:1441-56.
20. Zhang Y, Wang J, Zhang L, et al. Reliable transmission for NOMA systems with randomly deployed receivers. Ieee T Commun 2022;71:1179-92.
21. Zhou Z, Liu D, Bao W, et al. Multi-UAV cooperative target search method based on nash equilibrium distributed model predictive control. In: Proceedings of the 4th International Symposium on Application of Materials Science and Energy Materials; 2020. pp. 631-41.
22. Yao P, Wei X. Multi-UAV information fusion and cooperative trajectory optimization in target search. IEEE Syst J 2021;16:4325-33.
23. Wei W, Wang J, Fang Z, et al. 3U: Joint design of UAV-USV-UUV networks for cooperative target hunting. IEEE T Veh Technol 2022;72:4085-90.
24. Jia Z, Wenjun X, Qing G. Research on Multi-UAV collaborative search in dynamic environment. In: MATEC Web of Conferences. vol. 173. EDP Sciences; 2018. p. 02002.
25. Kamrani F, Ayani R. Using on-line simulation for adaptive path planning of UAVs. In: 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications (DS-RT'07). IEEE; 2007. pp. 167-74.
26. de Alcantara Andrade FA, Reinier Hovenburg A, Netto de Lima L, et al. Autonomous unmanned aerial vehicles in search and rescue missions using real-time cooperative model predictive control. Sensors 2019;19:4067.
27. Grefenstette JJ. Genetic algorithms and machine learning. In: Proceedings of the sixth annual conference on Computational learning theory; 1993. pp. 3-4.
28. Das S, Suganthan PN. Differential evolution: a survey of the state-of-the-art. IEEE T Evolut Comput 2010;15:4-31.
Cite This Article
OAE Style
Wang Z, Zou W, Li S. Cooperative search for moving targets with the ability to perceive and evade using multiple UAVs. Intell Robot 2023;3(4):538-64. http://dx.doi.org/10.20517/ir.2023.30
AMA Style
Wang Z, Zou W, Li S. Cooperative search for moving targets with the ability to perceive and evade using multiple UAVs. Intelligence & Robotics. 2023; 3(4): 538-64. http://dx.doi.org/10.20517/ir.2023.30
Chicago/Turabian Style
Wang, Ziyi, Wencheng Zou, Sheng Li. 2023. "Cooperative search for moving targets with the ability to perceive and evade using multiple UAVs" Intelligence & Robotics. 3, no.4: 538-64. http://dx.doi.org/10.20517/ir.2023.30
ACS Style
Wang, Z.; Zou W.; Li S. Cooperative search for moving targets with the ability to perceive and evade using multiple UAVs. Intell. Robot. 2023, 3, 538-64. http://dx.doi.org/10.20517/ir.2023.30
Comments
Comments must be written in English. Spam, offensive content, impersonation, and private information will not be permitted. If any comment is reported and identified as inappropriate content by OAE staff, the comment will be removed without notice. If you have any queries or need any help, please contact us at support@oaepublish.com.