Cooperative Search of UAV Swarm Based on Ant Colony Optimization with Artificial Potential Field

XING Dongjing，ZHEN Ziyang，ZHOU Chengyu，GONG Huajun

College of Automation Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

Abstract:An ant colony optimization with artificial potential field（ACOAPF）algorithm is proposed to solve the cooperative search mission planning problem of unmanned aerial vehicle（UAV）swarm.This algorithm adopts a distributed architecture where each UAV is considered as an ant and makes decision autonomously.At each decision step，the ants choose the next gird according to the state transition rule and update its own artificial potential field and pheromone map based on the current search results.Through iterations of this process，the cooperative search of UAV swarm for mission area is realized.The state transition rule is divided into two types.If the artificial potential force is larger than a threshold，the deterministic transition rule is adopted，otherwise a heuristic transition rule is used.The deterministic transition rule can ensure UAVs to avoid the threat or approach the target quickly.And the heuristics transition rule considering the pheromone and heuristic information ensures the continuous search of area with the goal of covering more unknown area and finding more targets.Finally，simulations are carried out to verify the effectiveness of the proposed ACOAPF algorithm for cooperative search mission of UAV swarm.

Key words:ant colony optimization;artificial potential field;cooperative search;unmanned aerial vehicle（UAV）swarm

0 Introduction

With the development of inexpensive mini-UAV，a novel concept of“UAV swarm”has become a research hotspot[1-2].The main inspiration of UAV swarm comes from the biological groups，such as bird flock，ant colony and fish school，which exhibit a collective intelligence[3].Each UAV in the swarm acts with a certain level of autonomy based on the local perception and interaction with the environment without centralized control.Therefore，the UAV swarm is self-organized and shows good robustness，scalability and flexibility which are beneficial to operations.

Cooperative search for an unknown mission area is a typical operational task of UAV swarm，with purpose to determine where the targets lie.The commonly used algorithms are search map-based methods，such as occupancy maps[4]，probability maps[5]，pheromone maps[6]，and so on.However，many studies are based on the centralized architecture which will lead to an exponential increase in computation when the system becomes complex.Due to the large scale of swarm，an important requirement of the search strategy is to adopt distributed approaches[7].Qu et al.[8]studied the regional surveillance problem of multi-UAV based on pheromones and artificial potential field（APF），and successfully resolved the issues of optimal search and obstacle avoidance.Kurdi et al.[9]solved the task allocation problem in multi-UAV search and rescue mission based on a bio-inspired algorithm inspired from locust behavior.Yao et al.[10]presented a threelayer distributed control structure to generate the optimal search trajectories of multiple UAVs based on the Gaussian mixture model（GMM）and receding horizon control（RHC）.Gao and Zhen et al.[11]proposed an improved distributed ant colony optimization（ACO）and designed a self-organized search mechanism which successfully solved the online search-attack mission planning problem[11-12].

By combining the ant colony algorithm and artificial potential field，we propose a hybrid distributed ant colony optimization with artificial potential field（ACOAPF）algorithm to solve the cooperative search problem of UAV swarm.The APF is introduced into ACO for improving the state transition rule.When the potential force exerted on the UAV is larger than a certain threshold，a deterministic transition rule is adopted for UAV to avoid threats or approach targets quickly，otherwise a heuristics transition rule is used with the goal of covering more area and finding more targets.The proposed ACOAPF algorithm ensures that UAVs are able to search the uncovered mission area continuously meanwhile avoid threats effectively.

1 Description of Cooperative Search Mission Planning Problem for UAV Swarm

The cooperative search mission refers to a swarm of UAVs searching for targets in a designated area under some certain mission requirements and constraints.Thus the discretized search environment model and mission optimization model are established for describing this problem.

1.1 Search environment model

The cooperative search mission of UAV swarm is described as：The swarm with size of Nvisomorphic UAVs searches for targets in a given area with Nttargets and Nththreats which are unknown in advance.The UAVs should work in a cooperative way to search targets meanwhile avoid the threats.The mission area is two-dimensional and discretized to a grid map with size of L×W，as shown in Fig.1.The black circles represent the threats and red stars represent the targets.Assume that the detection radius of UAV is R，then the targets and threats within R will be found.Take the displacement of UAV in a decision step as the width of grid and consider the maximum turning angleθmax，then the gray grids will be the candidate grids for the next step.

Fig.1 Discretized search environment model

1.2 Mission optimization model

The goal for cooperative search mission of UAV swarm is to cover more area and find more targets.Therefore，the target discovery benefit and environment search benefit are defined for establishing the mission optimization model.

The target discovery benefit is defined as the sum of target existence probability of all grids within detection radius，namely

where Sirepresents the detection range of the i th UAV andthe target existence probability of grid(m，n)at the i th UAV’s target probability map at time k.

The environment search benefit is defined as the surveillance coverage rate，which is calculated by the ratio of grids that have been searched to all grids in the mission area.

where grid(x，y)(k)=1 if the grid(x，y)has been searched at time k，otherwise grid(x，y)(k)=0.

Then the mission optimization model with goal of maximizing the target discovery benefit and environment search benefit can be expressed as

whereωis the weighting coefficient and U the decision input.G≤0 is the set of constraints，including the maximum turning angleθmax，collision avoidance constraint Gcand threat avoidance constraint Gt.We have

where dij(k)is the distance between the i th UAV and the j th UAV at time k，which should be larger than the minimum safe distancek)is the distance between the i th UAV and the l th threat at time k，which should be larger than the radius of the l th threat

2 Design of ACOAPF Algorithm for Cooperative Search Mission Planning

For solving the mission optimization model，an ACOAPF algorithm is presented.Each ant establishes its own artificial potential field and pheromone map.Then at each decision step，ants carry out the state transition and accordingly update the artificial potential field and pheromone map based on search results.

2.1 Artificial potential field

UAVs are expected to move towards the grids with higher target existence probability meanwhile avoid threats effectively，thus the target attraction field and threat repulsive field are designed.

（1）Target attraction field

The target attraction field can be expressed by the target probability map（TPM），which describes the possibility that the target exists at a certain region.The greater target existence probability means the greater attraction to UAVs.The TPM for the whole mission area at time k stored by the i th UAV is

The initial value of TMP represents the priori information of mission area.And it will be dynamically updated at each decision step according to the search results.Then the target existence probability update method is designed based on the Bayes probability formula as

whereτ∈[0，1]is the attenuation factor.PD， PFrepresent the detection probability and false alarm probability of sensor，respectively.b(k)=1 if the sensor detects a target，otherwise b(k)=0.When the target existence probability of a grid is greater than a certain threshold，it is considered to have a target.

Then the target attraction force exerted on the i th UAV is the gradient of TPM at the position of UAV Xi.

Eq.（7）means that the attraction force will point to the direction where the target existence probability increases the most，so as to drive UAV move towards the grid with higher target existence probability quickly.

（2）Threat repulsive field

The threat repulsive field is designed for generating a repulsive force so as to prevent UAVs from entering the threat areas.The repulsive force needs to increase as the distance between UAV and threat decreases.Therefore，the repulsion function is designed as

where Kris the repulsion gain，Xtthe position of the discovered threat，d(Xi，Xt)the distance between UAV and threat，d0the minimum safe distance，and dmthe influence range of the repulsive potential field.The repulsive force points from threat to UAV so as to drive UAV away from the threat.

2.2 Pheromone map

Pheromone is an important medium for ant colony to realize the behavior coordination，whose concentration reflects the attraction degree of the grids to ants.Each ant establishes its own pheromone map to represent its perception of the environment as

whereτi(x，y)(k)denotes the pheromone concentration of the grid（x，y）at time k in the i th ant’s pheromone map.Then a local pheromone update mechanism and a global pheromone update mechanism are designed for achieving the cooperative search behavior of UAV swarm.

After a state transition，pheromone concentration of the grids that have been searched should be reduced so as to avoid repeated search.Thus the local pheromone update mechanism is designed as

Considering that new targets may appear in the grids which have been searched，the pheromone concentration of all grids should be enhanced at regular intervals.Therefore，a global pheromone update mechanism is designed as

where F∈(0，1)is the environment uncertainty.This update mechanism ensures the continuous search of the entire mission area.

2.3 State transition r ule

By introducing the APF into the state transition rule of ACO，an ACOAPF algorithm is proposed，where the transition rule is divided into deterministic transition and heuristics transition.When the ant is located at a grid with large potential field force，it means that the ant is close to threat or target.Thus the deterministic transition is adopted to drive the ant away from threat or approach target as quickly as possible under the guidance of force.While in other cases，heuristics transition considering pheromone and heuristic information is adopted for covering more area and finding more targets.

（1）Deterministic transition rule

Assume that smaxis the detected grid with the maximum potential field force.If the distance between current grid siand smaxis smaller than a certain threshold dT，the deterministic transition rule is adopted and the next gird sjis chosen from

whereΩis the set of candidate grids andθjthe angle between the potential force of siand the path pointed from sito sj.A candidate grid with minimumθjwill be chosen as the next grid for the ant，so as to lead it quickly away from threat or close to target.

（2）Heuristics transition rule

If there is no threat or target near the ant，the heuristics transition rule is adopted.The ant will transfer according to the pheromone concentrationτ and heuristic informationηas

whereα，βreflect the importance degree ofτandη in transition，respectively.In order to improve the coverage of mission area to find more targets，the surveillance coverage rate is constructed as heuristic information.

Furthermore，considering the situation that the ant is surrounded by grids that have been searched and trapped in a local search，an iteration threshold NTis introduced.If the coverage rate keeps unchanged for NTiterations，the ant will move towards the nearest unsearched gird.This improvement ensures that the surveillance coverage rate can always reach 100%.

3 Simulation Analysis

In order to verify the effectiveness of the designed ACOAPF algorithm，simulations are carried out in this section.The mission area is set as 100 km×100 km and discretized to grids with size of 100×100.There are 18 targets and 5 threats distributed in the mission area whose information is shown in Tables 1，2，respectively.The swarm consists of 10 UAVs，whose maximum turning angle θmax=45°and detection radius R=3 km.Moreover，the system parameters used in the simulations are：PD=0.9，PF=0.1，Δτl0=0.8，Δτg0=80，F=0.02，α=1，β=3，NT=10.

Table 1 Target information km

Table 2 Threat information km

To better verify the superiority of the proposed algorithm，following cases are designed for comparison.

Case 1：ACOAPF algorithm without considering the heuristic informationηand iteration threshold NT.

Case 2：ACOAPF algorithm considering the heuristic informationηand iteration threshold NT.

The UAV paths generated after 200 iterations of these two cases are shown in Figs.2，3，where the red stars and black circles represent the targets and threats，respectively.The black dots denote the initial position of UAVs.Fig.2 shows the UAV paths of Case 1 and it can be seen that the UAVs are trapped into local search in the top left of the area.While in Case 2，the UAVs are able to avoid the local search and cover more area，as shown in Fig.3.As a result，the coverage rate of Case 2 is significantly higher than that of Case 1，as shown in Fig.4.After 200 iterations，the coverage rate of Case 2 reaches 85.54%and all the targets are found.However，the coverage rate of Case 1 is only 77.21%and 16 targets are discovered.Moreover，the UAVs are able to avoid the threats effectively.Therefore，the proposed ACOAPF algorithm that considers theηand NThas great advantages in improving the coverage rate meanwhile realizing the online threat avoidance.

Fig.2 UAV paths generated after 200 iterations of Case 1

Fig.3 UAV paths generated after 200 iterations of Case 2

Fig.4 Comparison of coverage rate

4 Conclusions

A distributed ACOAPF algorithm is proposed for solving the cooperative search problem of UAV swarm.This algorithm introduces the APF into the ACO for improving the state transition rule，which is divided into the deterministic transition and heuristics transition.Simulation results show that the deterministic transition rule enables UAV to avoid threat or approach target effectively.And compared with traditional state transition rule in ACO，the heuristics transition rule considering heuristic information and iteration threshold significantly improves the coverage rate.Therefore，the proposed ACOAPF algorithm has great advantages in improving the search efficiency meanwhile realizing the online threat avoidance，which makes it more effective to deal with the dynamic environment.