# Path Planning of Unmanned Autonomous Helicopter Based on Human-Computer Hybrid Augmented Intelligence

Authors: Zengliang Han; Mou Chen; Tongle Zhou; Zhiqiang Nie; Qingxian Wu
Journal: Neural Plasticity
 (2021)

---

## Abstract

Unmanned autonomous helicopter (UAH) path planning problem is an important component of the UAH mission planning system. The performance of the automatic path planner determines the quality of the UAH flight path. Aiming to produce a high-quality flight path, a path planning system is designed based on human-computer hybrid augmented intelligence framework for the UAH in this paper. Firstly, an improved artificial bee colony (I-ABC) algorithm is proposed based on the dynamic evaluation selection strategy and the complex optimization method. In the I-ABC algorithm, the following way of on-looker bees and the update strategy of nectar source are optimized to accelerate the convergence rate and retain the exploration ability of the population. In addition, a space clipping operation is proposed based on the attention mechanism for constructing a new spatial search area. The search time can be further reduced by the space clipping operation under the path planning result within acceptable changes. Moreover, the entire optimization process and results can be feeded back to the knowledge database by the human-computer hybrid augmented intelligence framework to guide subsequent path planning issues. Finally, the simulation results confirm that a feasible and effective flight path can be quickly generated by the UAH path planning system based on human-computer hybrid augmented intelligence.


---

## Body

## 1. Introduction

In recent years, the developments in automated and unmanned flight technologies have been of high interest to many military organizations throughout the world [1, 2]. Due to their outstanding capability to work in remote or hazardous situations, the unmanned autonomous helicopters (UAHs) have been widely used for many civil and military applications [3]. Path planning is the key to ensure the successful completion of UAH missions [4]. This particular issue is classified as an NP-Hard optimization problem in the high dimension [5]. In the past few years, a variety of methods have been proposed for the path planning problem of UAHs [6, 7]. Traditional methods, such as Voronoi diagram algorithm [8], A∗ algorithm [9], artificial potential field algorithm [10], and rapidly exploring random tree algorithm [11] were proposed to process the path planning problem. However, most of these methods exist the long search times and precociousness issues when the UAH flight path has complex constraints.Recently, with the development and application of metaheuristic algorithms, more and more swarm intelligence algorithms have been widely applied to the complex optimization problems [12, 13]. As a kind of nature-inspired algorithms, metaheuristic algorithms were originated from imitating biological interactive behaviors or physical phenomena [14], such as the particle swarm optimization (PSO) algorithm [15], genetic algorithm (GA) [16], and differential evolution (DE) algorithm [17]. In recent years, lots of studies have been investigated on improving and modifying the existing metaheuristic algorithms, such as wavelet mutation strategy differential evolution (WMSDE) algorithm [18], multistrategy-based coevolutionary DE (MPPCEDE) algorithm [19], and multiple strategies quantum-inspired differential evolution (MSIQDE) algorithm [20].Based on the existing research, recently, series of metaheuristic algorithms had been used to solve the UAH path planning problem [21]. In [22], a modification of wolf pack search (WPS) algorithm was presented for path planning of the unmanned aerial vehicle (UAV). Similarly, a grey wolf optimizer (GWO) was applied for path planning problem in the battle field in [23]. In [24], an improved bat algorithm (I-BA) was proposed to process the 3D path planning problems for unmanned combat air vehicles (UCAV). In [25], the multiverse optimizer (MVO) was used for resolving the 2D path planning problem for the UAV. In [26], the discrete particle swarm optimization (PSO) technique was enhanced and used to the path planning problem for surface inspection based on UAV vision.In 2005, a novel global optimization algorithm based on swarm intelligence called artificial bee colony (ABC) algorithm was proposed by Karaboga [27]. Compared with other intelligent algorithms, the principle of the artificial bee colony (ABC) algorithm makes the algorithm has the advantages of implementation and flexibility. With the continuous in-depth study of the ABC algorithm, it has been widely applied to resolve many engineering application and control problems, such as system identification, task assignment, and path planning. The ABC algorithm has a superior effect in solving path planning problems. However, it is easy to fall into a local optimal solution during the ABC algorithm iteration. To this end, many improved ABC algorithms have been proposed, such as Rosenbrocks rotational direction strategy [28], Boltzmann selection strategy [29], DE-ABC (differential evolution-ABC) [30], PSO-ABC (particle swarm optimization-ABC) [31], and QE-ABC (quantum evolutionary-ABC) [32]. Although those modified ABC algorithms have been widely used in various path planning problems, they were limited by the inherent limitations of the heuristics. Thus, the path planning results need to be further optimized and improved.Due to the open-ended nature of the path planning problems, no matter how intelligent computers are, they still cannot completely replace humans. Unmanned systems still need human supervision to take advantage of them. Therefore, it is indispensable to utilize human cognitive capabilities or human-like cognitive models into optimization layer to exploit a new path planning system for the UAH [33]. In recent years, with the development of artificial intelligence, researchers have become interested in a new kind of technique called hybrid-augmented intelligence [34]. From the actual situation, “hybrid-augmented intelligence” has been widely used in the fields of industrial development decision-making, online intelligent learning, medical health care, and human-computer codriving [35–37]. The idea of human-computer integration provides a new research approach for the path planning of the UAH. In this paper, the human-computer hybrid augmented intelligence is applied to the path planning system of the UAH. Combining the human intelligent experience to compensate for the shortcomings of the heuristic algorithm, a feasible flight path can be calculated by the improved algorithm. Furthermore, the search time of the flight path can also be further reduced while ensuring that it meets all constraints.To sum up, the ABC algorithm has great preponderance in solving the multiconstraints optimization problem. Similarly, the concept of hybrid augmented intelligence relies on the characteristics of human-computer integration, enabling the system to handle the complex and difficult problems. To overcome the defects of the traditional ABC algorithm and improve the quality of the flight path, a path planning system is proposed based on human-computer hybrid augmented intelligence framework for the UAH in this paper. The innovations in this paper are summarized as follows.(i)
A new path planning system based on human-computer hybrid augmented intelligence framework for UAH is designed to improve the rapidity and optimality of the automatic path planner. The used human-computer hybrid augmented intelligence framework combines the advantages of human and computer for planning a high-quality flight path(ii)
An I-ABC algorithm is proposed based on the dynamic evaluation selection strategy and the complex optimization method for accelerating the convergence rate and maintaining the exploration ability of the population(iii)
A space clipping method is designed based on the attention mechanism for reconstructing the spatial search area. The space clipping operation further reduces the subsequent search time of the flight path for the path planning system(iv)
The simulation studies are executed to comprehensively prove the effectiveness of path planning system based on human-computer hybrid augmented intelligence framework for UAH by various air combat environment modelsThe remainder of the paper is organized as follows. Section2 demonstrates the problem statement. Section 3 investigates the framework of human-computer hybrid augmented intelligence for path planning. Section 4 investigates an improved ABC algorithm. Section 5 investigates the space clipping method based on human optimizing attention mechanism. Section 6 provides the feasibility and effectiveness of the system by simulation experiment. Finally, the concluding remarks are involved in Section 7.


## 2. Problem Statement

As shown in Figure1, the path planning is the critical part of the UAH mission assignment system, and it is used to find the optimal flight path under the constraints such as weather threat, terrain threat, radars threat, and missiles threat. In this paper, we mainly study the 2D path planning of the UAH which execute the mission at the same flight altitude. We assume that the UAH maintains constant flight speed and altitude during its mission.Figure 1
Schematic of UAH path planning mission.


### 2.1. Modeling of UAH Path Planning

In this paper, the starting point and the terminal point are defined asS and T.According to the method given in [38] which is shown in Figure 2, we divided ST into D+1 equal parts by D vertical lines Lk,k=1,2,⋯,D, which intersect ST at each segment point. A flight path is formed by connecting the series of points on the new axis. To simplify the calculations, the threat regions covered in this paper are assumed to be circular projections. Therefore, the path planning problem can be converted to the route point coordinate optimization problem.Figure 2
Schematic of 2D UAH battlefield model.To simplify the calculation process, a new coordinate frame need to be established. In this section, the segmentST is considered as the new x-axis [39]. Each path point on the original combat field gets transferred in the new axes as defined in (1).
(1)x′y′=cosθsinθ−sinθcosθ,where θ represents the angle between the x-axis of the inertial frame and the x′ of the body-fixed frame direction, xs,ys correspond to the start point on the body-fixed frame.The damage probability is determined by the distance between the UAH and the threat center. Assuming that the new coordinates of the threat center point arexi,yi and the threat radius are ri, then the threat area can be expressed as [40]
(2)x−xi2+y−yi2=ri2.


### 2.2. Cost Function and Performance Constraints

In this paper, the performance evaluation index of the UAH flight path is composed of the threat costJthreati and the fuel cost Jfulei. The total cost and the each cost are described as follows [41].
(3)J=∑i=1D+1τJthreati+1−τJfulei,where τ is the weighting parameter between 0 and 1.The flight cost from the point alongLi to the one along Li+1 is calculated at five points (as shown in Figure 3). If the flight path shown above falls into a threat region, the Jthreati is calculated as follows.
(4)JthreatLi→Li+1=li5·∑k=1Ntsk·1d0.1,ik+1d0.3,ik+1d0.5,ik+1d0.7,ik+1d0.9,ik,where Nt is the total number of threats, li is the length of the ith subtrack, d0.1,ik stands for the distance between the 1/10 point on the path and the kth threat center, and sk is regarded as the grade of the kth threat.Figure 3
Schematic diagram of flight cost computation.Assume that the UAH is moving at a constant speed, theJfulei is calculated as follows.
(5)Jfulei=∑i=1Dlivη,where li is the length of the ith subtrack, v is the speed of the UAH, and η is the fuel consumption per unit time of the UAH.Considering the actual flight situation for the UAH, the yawing angle constraints are introduced as follows.(6)φj=arctanyj+1−yjxj+1−xj≤φmax,where φj is the yaw angle of the jth node and φmax is the maximum yawing angle.


## 2.1. Modeling of UAH Path Planning

In this paper, the starting point and the terminal point are defined asS and T.According to the method given in [38] which is shown in Figure 2, we divided ST into D+1 equal parts by D vertical lines Lk,k=1,2,⋯,D, which intersect ST at each segment point. A flight path is formed by connecting the series of points on the new axis. To simplify the calculations, the threat regions covered in this paper are assumed to be circular projections. Therefore, the path planning problem can be converted to the route point coordinate optimization problem.Figure 2
Schematic of 2D UAH battlefield model.To simplify the calculation process, a new coordinate frame need to be established. In this section, the segmentST is considered as the new x-axis [39]. Each path point on the original combat field gets transferred in the new axes as defined in (1).
(1)x′y′=cosθsinθ−sinθcosθ,where θ represents the angle between the x-axis of the inertial frame and the x′ of the body-fixed frame direction, xs,ys correspond to the start point on the body-fixed frame.The damage probability is determined by the distance between the UAH and the threat center. Assuming that the new coordinates of the threat center point arexi,yi and the threat radius are ri, then the threat area can be expressed as [40]
(2)x−xi2+y−yi2=ri2.


## 2.2. Cost Function and Performance Constraints

In this paper, the performance evaluation index of the UAH flight path is composed of the threat costJthreati and the fuel cost Jfulei. The total cost and the each cost are described as follows [41].
(3)J=∑i=1D+1τJthreati+1−τJfulei,where τ is the weighting parameter between 0 and 1.The flight cost from the point alongLi to the one along Li+1 is calculated at five points (as shown in Figure 3). If the flight path shown above falls into a threat region, the Jthreati is calculated as follows.
(4)JthreatLi→Li+1=li5·∑k=1Ntsk·1d0.1,ik+1d0.3,ik+1d0.5,ik+1d0.7,ik+1d0.9,ik,where Nt is the total number of threats, li is the length of the ith subtrack, d0.1,ik stands for the distance between the 1/10 point on the path and the kth threat center, and sk is regarded as the grade of the kth threat.Figure 3
Schematic diagram of flight cost computation.Assume that the UAH is moving at a constant speed, theJfulei is calculated as follows.
(5)Jfulei=∑i=1Dlivη,where li is the length of the ith subtrack, v is the speed of the UAH, and η is the fuel consumption per unit time of the UAH.Considering the actual flight situation for the UAH, the yawing angle constraints are introduced as follows.(6)φj=arctanyj+1−yjxj+1−xj≤φmax,where φj is the yaw angle of the jth node and φmax is the maximum yawing angle.


## 3. Human-Computer Hybrid Augmented Intelligence Framework for the Path Planning

Introducing human intelligence to the loop of the path planning system can can tackle the fuzzy and uncertain problems [42]. Hence, human and computer cooperate with each other to form a double-sided information exchange and control. The ′1+1>2′ hybrid augmented intelligence can be realized by conforming human cognitive ability, computer computing, and storage capacities [43].In this paper, a path planning system based on the human-computer hybrid augmented intelligence framework is designed. The new system integrates the artificial bee colony (ABC) algorithm and human intelligence. Through the human-computer cooperation, the intelligent process ability of the path planning system will be enhanced, and the flight path of the UAH will be efficiently improved. The framework of the path planning system based on the human-computer hybrid augmented intelligence is shown in Figure4.Figure 4
Framework of the human-computer hybrid augmented intelligence.The core of the path planning system for the UAH is mainly composed of the following two parts.


### 3.1. Computer Processing Module

When the new combat mission is entered, the computer will calculate an original flight path by the ABC algorithm according to the relevant constraints [44]. This process will always be guided by the experience of the expert knowledge database [45]. The original flight path needs to be evaluated to determined if it becomes the final result. However, it is initially difficult for the traditional ABC algorithm to obtain a high confidence flight path for the UAH path planning system.


### 3.2. Human Optimizing Module

When the original flight path cannot meet the needs of the actual combat, the human-computer hybrid augmented intelligence system will decide whether the result needs human adjustment or human intervention [46]. In this paper, the human optimization module is mainly divided into the following two parts.
(i)
Algorithm optimization layerThe ABC algorithm has a good effect in solving path planning problems; however, it is easy to fall into a local optimal solution during algorithm iteration. In the algorithm optimization layer, the traditional ABC algorithm is improved by the dynamic evaluation selection strategy and the complex optimization method. The improved ABC (I-ABC) algorithm raises the optimisation efficiency, avoids the algorithmic precocity, and plans a high confidence flight path according to the actual task requirements.(ii)
Human computing layerThe path planning based on the I-ABC algorithm can basically meet the mission demands. However, the time of the flight path planning can still be further reduced to improve the efficiency of the planning system. In the human computing layer, the efficiency of the planning system can be further improved by space clipping operation based on the attention mechanism. This step can be used as empirical knowledge to feed back into the expert knowledge base to guide and monitor the entire path planning system, thus enabling human-computer hybrid-augmented features.


## 3.1. Computer Processing Module

When the new combat mission is entered, the computer will calculate an original flight path by the ABC algorithm according to the relevant constraints [44]. This process will always be guided by the experience of the expert knowledge database [45]. The original flight path needs to be evaluated to determined if it becomes the final result. However, it is initially difficult for the traditional ABC algorithm to obtain a high confidence flight path for the UAH path planning system.


## 3.2. Human Optimizing Module

When the original flight path cannot meet the needs of the actual combat, the human-computer hybrid augmented intelligence system will decide whether the result needs human adjustment or human intervention [46]. In this paper, the human optimization module is mainly divided into the following two parts.
(i)
Algorithm optimization layerThe ABC algorithm has a good effect in solving path planning problems; however, it is easy to fall into a local optimal solution during algorithm iteration. In the algorithm optimization layer, the traditional ABC algorithm is improved by the dynamic evaluation selection strategy and the complex optimization method. The improved ABC (I-ABC) algorithm raises the optimisation efficiency, avoids the algorithmic precocity, and plans a high confidence flight path according to the actual task requirements.(ii)
Human computing layerThe path planning based on the I-ABC algorithm can basically meet the mission demands. However, the time of the flight path planning can still be further reduced to improve the efficiency of the planning system. In the human computing layer, the efficiency of the planning system can be further improved by space clipping operation based on the attention mechanism. This step can be used as empirical knowledge to feed back into the expert knowledge base to guide and monitor the entire path planning system, thus enabling human-computer hybrid-augmented features.


## 4. UAH Path Planning Based on I-ABC Algorithm

The ABC algorithm is the most important component of the path planning system for the UAH. The rationality and efficiency of the ABC algorithm in dealing with complex problems will directly affect the results of the path planning system for the UAH. Although the ABC algorithm is widely used at present, it still exposes many problems when it faces complex multiconstraints optimization problems.In this section, the traditional ABC algorithm will be improved in the algorithm optimization layer to optimize the path planning of the UHA. In the algorithm optimization layer, there are mainly two optimization measures as follows.(i)
First, in order to prevent the ABC algorithm premature convergence problem, a dynamic evaluation selection strategy is proposed to optimize the follow way of on-looker bees for improving the searching efficiency(ii)
Second, in order to improve the quality of the flight path, the complex method is used to guide the optimization of the swarm. The nectar source is updated during each iteration, the search efficiency of the nectar source is improved, and the algorithm convergence is acceleratedThe specific process of the I-ABC algorithm is as follows.


### 4.1. Initialization

There are three kinds of bees, i.e., employed bees, onlooker bees, and scout bees in the ABC algorithm [27]. Accordingly, the triple search capability of the ABC includes of three search phases: employed bee stage, onlooker stage, and scout stage [28]. The position of the nectar source (initial 2D track) is represented by a D×NP-dimensional matrix E=eij, the vector in the ith row of the matrix is represented as
(7)Xi=xi1,⋯,xij,⋯,xiD,where 1≤i≤Np, 2≤j≤D−1, and xi1=xiD=0.All theNP employed bees need to be randomly initialized by equation (8) [27]. In other words, each track point is randomly generated within a specified range in the feasible solution space.
(8)xij=ximin+rand0,1·ximax−ximin,where ximin and ximax are the constraints of the ith parameter, rand0,1 is a random number range from 0 to 1.Then, the corresponding fitness is calculated as(9)fitnessi=11+obji,obji≥0,1+obji,obji<0,where obji represents the objective function value with respect to Xi.


### 4.2. Employed Bee Phase

Each employed bee is related with only one nectar source. The employed bee finds a new candidate solution through changing the nectar source position in its memory based on the local information. In each iteration cycle, the employed bee adopts (10) to search for the better nectar source Vij around the current nectar source [27].
(10)vij=xij+rand1,−1·xij−xkj,where i=1,2,⋯,NP,k∈1,2,⋯,NP,j∈1,2,⋯,D, k is a random integer different from i, j is a random integer, and rand1,−1 is a random number range from −1 to 1.During the neighborhood search process, when the location of the nectar source searched by the employed bees exceeds the search boundary constraint, the bee is selected according to (11).
(11)xij=xjmin+∂xjmax−xjmin,xij≤xjmin,xjmin−∂xjmax−xjmin,xij>xjmin,∂∈rand0,1where xjmin and xjmax are the constraints of the jth parameter.


### 4.3. Onlooker Bee Phase

In the onlooker bee phase, the amounts and positions of their nectar sources will be transmitted by the employed bees to onlooker bees. Then, the onlooker bee evaluates all the information of nectar sources transmitted by employed bees, and chooses one nectar source site according to the probability valuepi formulated as [27]
(12)pi=fitnessi∑j=1NPfitnessi,where NP represents the number of bees.However, the traditional following selection method overly focus on the development of excellent nectar sources. Ignoring other potential nectar sources will cause the algorithm’s global search capability to decline and reduce the algorithms solution efficiency. For solving this problem, we propose a dynamic evaluation selection strategy instead of the traditional method to follow the location of the nectar sources.(1)
Defining the nectar source dynamic evaluation integral valueIn this section, the dynamic evaluation integral values of nectar sources are defined asΨ1i and Ψ2i. When the nectar source i maintains unchanged, Ψ1i is calculated according to equation (13), and Ψ2i is 0. When the nectar source position i is replaced by a better one, Ψ2i is calculated according to equation (14), and Ψ1i is 0.
(13)Ψ1i=Ψ1i+step,Ψ1i<limitd,limitd,Ψ1i≥limitd,(14)Ψ2i=Ψ2i+step,Ψ2i<limitd,limitd,Ψ2i≥limitd,where Ψ1i is the number of searching near the nectar source i but the position has not changed, Ψ2i is the number of searching near the nectar source i and the position has changed, and limitd is the dynamic update limit parameter, step is the search unit length.
(2)
Building the dynamic evaluation functionConsidering that there will be more greater possibility of finding excellent nectar sources near the continuously optimized nectar sources. The dynamic evaluation functionFi is constructed according to the dynamic evaluation criteria which is written as
(15)Fi=ζ1−Ψ1ilimitd,Ψ1i≠0,ζ1+Ψ2ilimitd,Ψ1i=0,where ζ is the base score of the nectar source.
(i)
WhenΨ1i=0, this nectar source may be trapped in a local optimum. Onlooker bees should try to avoid selecting this type of nectar source for further development(ii)
WhenΨ1i≠0, this nectar source has been continuously optimized multiple times. Onlooker bees need to try to select this type of nectar source for neighborhood searchThe evaluation integral value of the nectar source is calculated by the evaluation functionFi. The basic score of the nectar source is ζ, and the selection possibility of all individuals is guaranteed. The scores of nectar sources with continuously changing positions are more than ζ, which has a greater possibility of being followed. The optimized selection probability is calculated by (16).
(16)p′i=FimaxFi.


### 4.4. Scout Bee Phase

In each iteration cycle, the exhausted nectar source will be checked by ABC algorithm after all the employed bees and onlookers complete their searches. If the new positionXi is not improved continuously for a certain time, then the corresponding nectar source will be abandoned by the employed bee. At this time, this employed bee will become a scout bee. According to (10), a new nectar source vij will be generated by the scout bee.In order to improve the efficiency of the nectar source and the quality of the flight path, a complex optimization method is used to guide the swarm. The complex optimization method is a direct search algorithm for finding constrained optimization problems [47]. In solving nonlinear problems, by virtue of its freedom from the constraints of the research problem and the objective function, it has a wide range of applicability and can be embedded in many other algorithms to guide the problem to an optimal or suboptimal solution.From the nectar sources before the end of each iteration,u nectars are selected to construct the complex geometry, which is ordered as X1,X2,⋯Xu according to the size of the objective function value from best to worst (as shown in Figure 5). The process of the complex optimization method is as follows.Step 1.
Centroid calculation(17)Xc=1u−1∑i=1u−1Xi.Step 2.
Reflection point calculation(18)Xr=Xc+αXc−Xu,where α∈0,1 is the reflection coefficient. If Xr is better than Xu, Xu will be replaced by Xr; otherwise, go to Step 4.Step 3.
Extension point calculation(19)Xe=Xr+βXr−Xc,where β∈0,1 is the extension coefficient. If Xe is better than Xu, Xu will be replaced by Xe; otherwise, go to Step 4.Step 4.
Systolic point calculation(20)Xs=Xu+χXc−Xu,where χ∈0,1 is the systolic coefficient. If Xs is better than Xu, Xu will be replaced by Xs; otherwise, go to Step 1.Figure 5
Schematic model of the complex method for five nectar sources.In this paper, the purpose of the complex optimization method is to emphasize the “replacement” effect, not the traditional “search for excellence.” So when the convergence termination condition is setted, it is only necessary for the algorithm to reach the required number of iterations, which is related to the number of selected nectar sources. The convergence termination is as follows.(21)Ncomplex=u.The flow diagram of the complex optimization method is shown in Figure6.Figure 6
Flow diagram of the complex optimization method.By the complex optimization method, the originalu worst nectar sources in the search space are replaced. The complex geometry keeps reflecting, extending, and contracting in the above ways to make the nectar source approach the optimal location. Since the nectar source is updated during each iteration, the problem of dimensionality reduction due to failure to take into account the correlation and number of points of the initial complex is avoided.To overcome the defects exposed by the traditional ABC algorithm in dealing with the path planning of the UAH, an I-ABC algorithm is proposed based on the dynamic evaluation selection strategy and complex optimization method in the algorithm optimization layer. The I-ABC algorithm avoids the premature convergence problem, reduces the algorithm search time, and improves the quality of the flight path. The flow diagram of the I-ABC algorithm is shown in Figure7.Figure 7
Flow diagram of the I-ABC.During the iteration, if an employed bee searches globally but finds no better nectar source, or if an onlooker bee searches around an employed bee and finds no better nectar source, the invalid trail timetrial plus one. On the other hand, when any better nectar source can be searched by the ith employed bee, the relevant triali is set to zero immediately. At the end of each iteration, it is necessary to determine whether any triali outpaces a certain threshold Limit. If triali>Limit, the ith employed bee will be diametrically replaced by a scout bee. A scout bee still uses (8) to point to a randomly initialized location in the food source. The pseudocode of the I-ABC algorithm are shown in Algorithm 1.Algorithm 1: The I-ABC algorithm.
1: initialize solution population using (8)2: settriali=1i=12,⋯NP3:foriter=1:MCNdo4:foritem=1:SNdo5:  generate positions for employed bees by (10)6:  evaluate and greedily select employed bees7:if better position is found then8:trialitem⟵19:else10:trialitem⟵trialitem+111:end if12:end for13: calculate the dynamic evaluation probabilityp′i by (16)14: setitem=115:whileitem<SNdo16:  generate positions for employed bees by (10)17:  evaluate and greedily select employed bees18:if position is changed then19:trialitem⟵120:  else21:trialitem⟵trialitem+122:end if23:end while24:iftrialitem≥Limitthen25:  initialize the position by (8)26: end if27:whileitem<udo28:  calculate centroidXc by (17)29:  calculate reflection pointXr by (18)30:ifFXr<FXuthen31:Xu=Xr32:   calculate extension pointXe by (19)33:ifFXe<FXuthen34:Xu=Xe35:   end if36:  else37:   calculate systolic pointXs by (20)38:ifFXs<FXuthen39:Xu=Xs40:item=item+141:end if42:end if43:end while44:iftrialitem≥Limitthen45:  initialize the position by (8)46:end if47: record current best solution48:iter⟵iter+149:end for50: output global optimal solutionRemark 1.
The I-ABC algorithm can be divided into two phases. As the first phase of the program, the initialization phase is executed one time at the start, and the other phases are executed in each cycle. The computational complexity is mostly affected by the phase of the algorithm.The computation is applied to the population with size ofN, the individuals’ position in population is a vector with size of D, and O is the asymptotic time complexity. The computing complexity Tn of each phase is shown as follows:
(i)
Initialization phase(22)T1n=maxO1,ON·D=ON·D.(ii)
Optimization phase(23)T2n=maxON2·D,ON·D,ON·D,ON·D=ON2·D.Therefore, the maximum computing complexity of the I-ABC algorithm is shown as(24)Tn=T1n+T2n=maxON·D,ON2·D=ON2·D.So it proves that this algorithm owns fast execution speed.


## 4.1. Initialization

There are three kinds of bees, i.e., employed bees, onlooker bees, and scout bees in the ABC algorithm [27]. Accordingly, the triple search capability of the ABC includes of three search phases: employed bee stage, onlooker stage, and scout stage [28]. The position of the nectar source (initial 2D track) is represented by a D×NP-dimensional matrix E=eij, the vector in the ith row of the matrix is represented as
(7)Xi=xi1,⋯,xij,⋯,xiD,where 1≤i≤Np, 2≤j≤D−1, and xi1=xiD=0.All theNP employed bees need to be randomly initialized by equation (8) [27]. In other words, each track point is randomly generated within a specified range in the feasible solution space.
(8)xij=ximin+rand0,1·ximax−ximin,where ximin and ximax are the constraints of the ith parameter, rand0,1 is a random number range from 0 to 1.Then, the corresponding fitness is calculated as(9)fitnessi=11+obji,obji≥0,1+obji,obji<0,where obji represents the objective function value with respect to Xi.


## 4.2. Employed Bee Phase

Each employed bee is related with only one nectar source. The employed bee finds a new candidate solution through changing the nectar source position in its memory based on the local information. In each iteration cycle, the employed bee adopts (10) to search for the better nectar source Vij around the current nectar source [27].
(10)vij=xij+rand1,−1·xij−xkj,where i=1,2,⋯,NP,k∈1,2,⋯,NP,j∈1,2,⋯,D, k is a random integer different from i, j is a random integer, and rand1,−1 is a random number range from −1 to 1.During the neighborhood search process, when the location of the nectar source searched by the employed bees exceeds the search boundary constraint, the bee is selected according to (11).
(11)xij=xjmin+∂xjmax−xjmin,xij≤xjmin,xjmin−∂xjmax−xjmin,xij>xjmin,∂∈rand0,1where xjmin and xjmax are the constraints of the jth parameter.


## 4.3. Onlooker Bee Phase

In the onlooker bee phase, the amounts and positions of their nectar sources will be transmitted by the employed bees to onlooker bees. Then, the onlooker bee evaluates all the information of nectar sources transmitted by employed bees, and chooses one nectar source site according to the probability valuepi formulated as [27]
(12)pi=fitnessi∑j=1NPfitnessi,where NP represents the number of bees.However, the traditional following selection method overly focus on the development of excellent nectar sources. Ignoring other potential nectar sources will cause the algorithm’s global search capability to decline and reduce the algorithms solution efficiency. For solving this problem, we propose a dynamic evaluation selection strategy instead of the traditional method to follow the location of the nectar sources.(1)
Defining the nectar source dynamic evaluation integral valueIn this section, the dynamic evaluation integral values of nectar sources are defined asΨ1i and Ψ2i. When the nectar source i maintains unchanged, Ψ1i is calculated according to equation (13), and Ψ2i is 0. When the nectar source position i is replaced by a better one, Ψ2i is calculated according to equation (14), and Ψ1i is 0.
(13)Ψ1i=Ψ1i+step,Ψ1i<limitd,limitd,Ψ1i≥limitd,(14)Ψ2i=Ψ2i+step,Ψ2i<limitd,limitd,Ψ2i≥limitd,where Ψ1i is the number of searching near the nectar source i but the position has not changed, Ψ2i is the number of searching near the nectar source i and the position has changed, and limitd is the dynamic update limit parameter, step is the search unit length.
(2)
Building the dynamic evaluation functionConsidering that there will be more greater possibility of finding excellent nectar sources near the continuously optimized nectar sources. The dynamic evaluation functionFi is constructed according to the dynamic evaluation criteria which is written as
(15)Fi=ζ1−Ψ1ilimitd,Ψ1i≠0,ζ1+Ψ2ilimitd,Ψ1i=0,where ζ is the base score of the nectar source.
(i)
WhenΨ1i=0, this nectar source may be trapped in a local optimum. Onlooker bees should try to avoid selecting this type of nectar source for further development(ii)
WhenΨ1i≠0, this nectar source has been continuously optimized multiple times. Onlooker bees need to try to select this type of nectar source for neighborhood searchThe evaluation integral value of the nectar source is calculated by the evaluation functionFi. The basic score of the nectar source is ζ, and the selection possibility of all individuals is guaranteed. The scores of nectar sources with continuously changing positions are more than ζ, which has a greater possibility of being followed. The optimized selection probability is calculated by (16).
(16)p′i=FimaxFi.


## 4.4. Scout Bee Phase

In each iteration cycle, the exhausted nectar source will be checked by ABC algorithm after all the employed bees and onlookers complete their searches. If the new positionXi is not improved continuously for a certain time, then the corresponding nectar source will be abandoned by the employed bee. At this time, this employed bee will become a scout bee. According to (10), a new nectar source vij will be generated by the scout bee.In order to improve the efficiency of the nectar source and the quality of the flight path, a complex optimization method is used to guide the swarm. The complex optimization method is a direct search algorithm for finding constrained optimization problems [47]. In solving nonlinear problems, by virtue of its freedom from the constraints of the research problem and the objective function, it has a wide range of applicability and can be embedded in many other algorithms to guide the problem to an optimal or suboptimal solution.From the nectar sources before the end of each iteration,u nectars are selected to construct the complex geometry, which is ordered as X1,X2,⋯Xu according to the size of the objective function value from best to worst (as shown in Figure 5). The process of the complex optimization method is as follows.Step 1.
Centroid calculation(17)Xc=1u−1∑i=1u−1Xi.Step 2.
Reflection point calculation(18)Xr=Xc+αXc−Xu,where α∈0,1 is the reflection coefficient. If Xr is better than Xu, Xu will be replaced by Xr; otherwise, go to Step 4.Step 3.
Extension point calculation(19)Xe=Xr+βXr−Xc,where β∈0,1 is the extension coefficient. If Xe is better than Xu, Xu will be replaced by Xe; otherwise, go to Step 4.Step 4.
Systolic point calculation(20)Xs=Xu+χXc−Xu,where χ∈0,1 is the systolic coefficient. If Xs is better than Xu, Xu will be replaced by Xs; otherwise, go to Step 1.Figure 5
Schematic model of the complex method for five nectar sources.In this paper, the purpose of the complex optimization method is to emphasize the “replacement” effect, not the traditional “search for excellence.” So when the convergence termination condition is setted, it is only necessary for the algorithm to reach the required number of iterations, which is related to the number of selected nectar sources. The convergence termination is as follows.(21)Ncomplex=u.The flow diagram of the complex optimization method is shown in Figure6.Figure 6
Flow diagram of the complex optimization method.By the complex optimization method, the originalu worst nectar sources in the search space are replaced. The complex geometry keeps reflecting, extending, and contracting in the above ways to make the nectar source approach the optimal location. Since the nectar source is updated during each iteration, the problem of dimensionality reduction due to failure to take into account the correlation and number of points of the initial complex is avoided.To overcome the defects exposed by the traditional ABC algorithm in dealing with the path planning of the UAH, an I-ABC algorithm is proposed based on the dynamic evaluation selection strategy and complex optimization method in the algorithm optimization layer. The I-ABC algorithm avoids the premature convergence problem, reduces the algorithm search time, and improves the quality of the flight path. The flow diagram of the I-ABC algorithm is shown in Figure7.Figure 7
Flow diagram of the I-ABC.During the iteration, if an employed bee searches globally but finds no better nectar source, or if an onlooker bee searches around an employed bee and finds no better nectar source, the invalid trail timetrial plus one. On the other hand, when any better nectar source can be searched by the ith employed bee, the relevant triali is set to zero immediately. At the end of each iteration, it is necessary to determine whether any triali outpaces a certain threshold Limit. If triali>Limit, the ith employed bee will be diametrically replaced by a scout bee. A scout bee still uses (8) to point to a randomly initialized location in the food source. The pseudocode of the I-ABC algorithm are shown in Algorithm 1.Algorithm 1: The I-ABC algorithm.
1: initialize solution population using (8)2: settriali=1i=12,⋯NP3:foriter=1:MCNdo4:foritem=1:SNdo5:  generate positions for employed bees by (10)6:  evaluate and greedily select employed bees7:if better position is found then8:trialitem⟵19:else10:trialitem⟵trialitem+111:end if12:end for13: calculate the dynamic evaluation probabilityp′i by (16)14: setitem=115:whileitem<SNdo16:  generate positions for employed bees by (10)17:  evaluate and greedily select employed bees18:if position is changed then19:trialitem⟵120:  else21:trialitem⟵trialitem+122:end if23:end while24:iftrialitem≥Limitthen25:  initialize the position by (8)26: end if27:whileitem<udo28:  calculate centroidXc by (17)29:  calculate reflection pointXr by (18)30:ifFXr<FXuthen31:Xu=Xr32:   calculate extension pointXe by (19)33:ifFXe<FXuthen34:Xu=Xe35:   end if36:  else37:   calculate systolic pointXs by (20)38:ifFXs<FXuthen39:Xu=Xs40:item=item+141:end if42:end if43:end while44:iftrialitem≥Limitthen45:  initialize the position by (8)46:end if47: record current best solution48:iter⟵iter+149:end for50: output global optimal solutionRemark 1.
The I-ABC algorithm can be divided into two phases. As the first phase of the program, the initialization phase is executed one time at the start, and the other phases are executed in each cycle. The computational complexity is mostly affected by the phase of the algorithm.The computation is applied to the population with size ofN, the individuals’ position in population is a vector with size of D, and O is the asymptotic time complexity. The computing complexity Tn of each phase is shown as follows:
(i)
Initialization phase(22)T1n=maxO1,ON·D=ON·D.(ii)
Optimization phase(23)T2n=maxON2·D,ON·D,ON·D,ON·D=ON2·D.Therefore, the maximum computing complexity of the I-ABC algorithm is shown as(24)Tn=T1n+T2n=maxON·D,ON2·D=ON2·D.So it proves that this algorithm owns fast execution speed.


## 5. Space Clipping Operation Based on Attentional Mechanism

As shown in Figure8, the incorporation of human intelligence is an important feature of the human-computer hybrid augmented intelligence framework. In order to further reduce the flight path search time and improve the efficiency of the UAH path planning system, a human computing layer is designed for the refinement operation of the flight path. Combined with the prior knowledge and human intelligence, the UAH flight space will be clipped by the spatial attention mechanism.Figure 8
Diagram of human-computer collaboration.


### 5.1. Attentional Mechanism

The main idea of the human computing layer presented in this paper is the space clipping based on the attention mechanism. The attention mechanism is a brain signal processing mechanism that is unique to humans [48]. The flight space clipping operation mimics the process by which the human brain rapidly sifts high-value information from large amounts of data through limited attentional resources [49]. The principle of the mechanism is shown in Figure 9.Figure 9
Space clipping operation based on attentional mechanism.The division of the threat areas will be determined by the degree of association between the flight path and the threat. Eventually, the spatial area of the path planing will be redrawn.


### 5.2. Space Clipping Operation

In order to meet the constraint of minimizing the length of the path, the flight path can only through the safe space between a part of the threat areas. Numerous studies show that the unrelated threats will increase the search time of the swarm intelligence algorithm and reduce the efficiency of the path planning system. Therefore, it is crucial to distinguish different threat areas by the human computing layer. Combining the priori path planning results knowledge, the UAH flight space can be clipped by following steps.(1)
Voronoi diagram constructionThe Voronoi diagram is widely used in terrain processing and other areas of division [8]. The points on each edge of the Voronoi diagram polygon are equidistant from the corresponding two threat points. In other words, all points on the edge of the Voronoi diagram are as far away as possible from the threat.Step 1.
As shown in Figure10(a), the threat region is considered as a point tn, and all threat regions form a scatter set T of finite distances, that is, T=t1,t2,⋯,tn.Step 2.
As shown in Figure10(b), construct Delaunay triangles by connecting discrete points tn into triangles. Find the edges of the Voronoi diagram by traversing the triangle chain table and draw the Voronoi diagram based on the final result.Figure 10
Process of the space clipping operation.
(a)
Original obstacle point set(b)
Voronoi diagramThe Voronoi diagram divides the flight path planning space inton convex polygons vii=1,2,⋯,n centered on the threat area, and the Voronoi diagram composed of V=v1,v2,⋯,vn satisfies the following two conditions.
(1)
Each convex polygon includes one and only one threat area, that is,∀vi∈V, ∃!tj∈T, where tj∈vi,∀tk∈Tk≠j,tk∉vj.(2)
Suppose thatdx,y is the Euclid distance on ℝ2, if tj∈vi, so that ∀t∈vi,∀tk≠tj, where dx,xj≤dx,xk,i,j=1,2⋯,n.(2)
Threat areas classificationAssume that the flight path isCpath, the edge between threat ti and threat tj is Lvi,j, the intersection of the flight path and the edge of the convex polygon is Ξi,jk, where i≠j and i,j=1,2,⋯,n, and k is the number of the intersection. The guidelines for determining the type of threat areas are as follows.
(i)
IfCpath intersects Lvi,j and the intersection point is Ξi,jk (k≥1), threat ti and threat tj are defined as associated threats. When the position of Ξ is located at the intersection of the three edges of the convex polygon, Ξ=Ξh,i,jkh≠i≠j,h,i,j=1,2,⋯,n,k=1; threat th, threat ti, and threat tj are defined as associated threats(ii)
If there is no intersection betweenCpath and Lvij, that is, Ξijk does not exist, threat ti and threat tj are defined as unrelated threatsAs shown in Figure11, the flight space includes 11 threat areas (T=t1,t2,⋯,t11), and the Voronoi diagram divides them into 11 convex polygons (V=v1,v2,⋯,v11). According to the above theory, the threat areas in Figure 11 can be judged as follows.
(i)
Part IFigure 11
The distribution ofΞi,jk..Cpath and Lv1,2 intersect at Ξ1,21 and Ξ1,22; threat t1 and threat t2 are associated threats; Cpath and Lv1,4 intersect at Ξ1,41; threat t1 and threat t4 are associated threats.
(ii)
Part IICpath and Lv4,8 intersect at Ξ4,81 and Ξ4,82; threat t4 and threat t8 are associated threats.
(iii)
Part IIICpath and Lv4,7 and Lv4,8 and Lv7,8 at Ξ4,7,81; threat t4, threat t7, and threat t8 are associated threats.
(iv)
Part IVCpath and Lv7,10 intersect at Ξ7,101; threat t7 and threat t10 are associated threats.
(v)
Part VCpath and Lv10,11 intersect at Ξ10,111; threat t10 and threat t11 are associated threats.In summary, as shown in Figure12, the associated convex polygonal areas set is Vassociated=v1,v2,v4,v7,v8,v10,v11, and the associated threat set is Tassociated=t1,t2,t4,t7,t8,t10,t11.Figure 12
Associated convex polygonal areas and threats.


### 5.3. Search Space Construction

The new spatial search area consists of a closed-loop space connected in sequence by the mission starting pointS, the boundary docking points, and the mission end point T. The key of constructing a new spatial search area are to find the reasonable boundary docking points and determine the spatial search boundary. In order to ensure that the results of the path planning in the new spatial search area remain largely optimal and the computation time of the swarm intelligence algorithm can be reduced. The spatial search area and the boundary docking point should satisfy the following properties.
(i)
The spatial search area is a closed loop area(ii)
The spatial search area contains all associated threatsVassociated(iii)
The positions of the boundary docking points should be on the associated threats’ bordersTo simplify the calculation, according to the properties of the space search boundary, the method for determining the boundary docking points is designed as follows.(i)
r1=r2Case 1.
Shown in Figure13, make the tangent line LR1 of the threat circle 1 through S (start or end point), and the tangent point A is the boundary docking point of the start/end point to the associated threat, where AR1⊥LR1, ∠AR1S=ζ.Case 2.
Shown in Figure14, cross point R1 to make the vertical line l of SR1, find the symmetrical point A′ of A with respect to l, and the point A′ is the boundary docking point on the associated threat.Case 3.
Different associated threats have different threat radius. According to the radius of adjacent associated threats, the location of the boundary docking point can be divided into three situations.Figure 13
The boundary docking point of the start/end point to the associated threat.Figure 14
The boundary docking point on the same associated threat.As shown in Figure15(a), straight line l′ is the vertical bisector of line segment R1R2, and point B is the symmetry point of A′ with respect to l′. For r1=r2, the point B must be on the boundary of threat 2, so point B is the boundary docking point of associated threat 1 to associated threat 2.
(ii)
r1<r2Figure 15
The boundary docking point of different associated threats.
(a)
R1=R2(b)
R1<R2(c)
R1>R2As shown in Figure15(b), straight line l′ is the vertical bisector of line segment R1R2, and point P is the symmetry point of A′ with respect to l′, where P is within the threat 2. Crossing point P to make the vertical line A′P of R1R2, and the intersection point B with threat 2 is the boundary docking point of associated threat 1 to associated threat 2, where ∠AR1R2=∠BR2R1=ζ.
(iii)
r1>r2As shown in Figure15(c), straight line l′ is the vertical bisector of line segment R1R2, and point P is the symmetry point of A′ with respect to l′, where P is out of the threat 2. Crossing point P to make the vertical line A′P of R1R2, and the intersection point B with threat 2 is the boundary docking point of associated threat 1 to associated threat 2, where ∠AR1R2=∠BR2R1=ζ.Due to the location of the associated threats and the mission start/end point were known, the boundary docking point and the search boundary information can be determined by the prior knowledge. The new spatial search area is shown in Figure16.Figure 16
Diagram of new spatial search area.


## 5.1. Attentional Mechanism

The main idea of the human computing layer presented in this paper is the space clipping based on the attention mechanism. The attention mechanism is a brain signal processing mechanism that is unique to humans [48]. The flight space clipping operation mimics the process by which the human brain rapidly sifts high-value information from large amounts of data through limited attentional resources [49]. The principle of the mechanism is shown in Figure 9.Figure 9
Space clipping operation based on attentional mechanism.The division of the threat areas will be determined by the degree of association between the flight path and the threat. Eventually, the spatial area of the path planing will be redrawn.


## 5.2. Space Clipping Operation

In order to meet the constraint of minimizing the length of the path, the flight path can only through the safe space between a part of the threat areas. Numerous studies show that the unrelated threats will increase the search time of the swarm intelligence algorithm and reduce the efficiency of the path planning system. Therefore, it is crucial to distinguish different threat areas by the human computing layer. Combining the priori path planning results knowledge, the UAH flight space can be clipped by following steps.(1)
Voronoi diagram constructionThe Voronoi diagram is widely used in terrain processing and other areas of division [8]. The points on each edge of the Voronoi diagram polygon are equidistant from the corresponding two threat points. In other words, all points on the edge of the Voronoi diagram are as far away as possible from the threat.Step 1.
As shown in Figure10(a), the threat region is considered as a point tn, and all threat regions form a scatter set T of finite distances, that is, T=t1,t2,⋯,tn.Step 2.
As shown in Figure10(b), construct Delaunay triangles by connecting discrete points tn into triangles. Find the edges of the Voronoi diagram by traversing the triangle chain table and draw the Voronoi diagram based on the final result.Figure 10
Process of the space clipping operation.
(a)
Original obstacle point set(b)
Voronoi diagramThe Voronoi diagram divides the flight path planning space inton convex polygons vii=1,2,⋯,n centered on the threat area, and the Voronoi diagram composed of V=v1,v2,⋯,vn satisfies the following two conditions.
(1)
Each convex polygon includes one and only one threat area, that is,∀vi∈V, ∃!tj∈T, where tj∈vi,∀tk∈Tk≠j,tk∉vj.(2)
Suppose thatdx,y is the Euclid distance on ℝ2, if tj∈vi, so that ∀t∈vi,∀tk≠tj, where dx,xj≤dx,xk,i,j=1,2⋯,n.(2)
Threat areas classificationAssume that the flight path isCpath, the edge between threat ti and threat tj is Lvi,j, the intersection of the flight path and the edge of the convex polygon is Ξi,jk, where i≠j and i,j=1,2,⋯,n, and k is the number of the intersection. The guidelines for determining the type of threat areas are as follows.
(i)
IfCpath intersects Lvi,j and the intersection point is Ξi,jk (k≥1), threat ti and threat tj are defined as associated threats. When the position of Ξ is located at the intersection of the three edges of the convex polygon, Ξ=Ξh,i,jkh≠i≠j,h,i,j=1,2,⋯,n,k=1; threat th, threat ti, and threat tj are defined as associated threats(ii)
If there is no intersection betweenCpath and Lvij, that is, Ξijk does not exist, threat ti and threat tj are defined as unrelated threatsAs shown in Figure11, the flight space includes 11 threat areas (T=t1,t2,⋯,t11), and the Voronoi diagram divides them into 11 convex polygons (V=v1,v2,⋯,v11). According to the above theory, the threat areas in Figure 11 can be judged as follows.
(i)
Part IFigure 11
The distribution ofΞi,jk..Cpath and Lv1,2 intersect at Ξ1,21 and Ξ1,22; threat t1 and threat t2 are associated threats; Cpath and Lv1,4 intersect at Ξ1,41; threat t1 and threat t4 are associated threats.
(ii)
Part IICpath and Lv4,8 intersect at Ξ4,81 and Ξ4,82; threat t4 and threat t8 are associated threats.
(iii)
Part IIICpath and Lv4,7 and Lv4,8 and Lv7,8 at Ξ4,7,81; threat t4, threat t7, and threat t8 are associated threats.
(iv)
Part IVCpath and Lv7,10 intersect at Ξ7,101; threat t7 and threat t10 are associated threats.
(v)
Part VCpath and Lv10,11 intersect at Ξ10,111; threat t10 and threat t11 are associated threats.In summary, as shown in Figure12, the associated convex polygonal areas set is Vassociated=v1,v2,v4,v7,v8,v10,v11, and the associated threat set is Tassociated=t1,t2,t4,t7,t8,t10,t11.Figure 12
Associated convex polygonal areas and threats.


## 5.3. Search Space Construction

The new spatial search area consists of a closed-loop space connected in sequence by the mission starting pointS, the boundary docking points, and the mission end point T. The key of constructing a new spatial search area are to find the reasonable boundary docking points and determine the spatial search boundary. In order to ensure that the results of the path planning in the new spatial search area remain largely optimal and the computation time of the swarm intelligence algorithm can be reduced. The spatial search area and the boundary docking point should satisfy the following properties.
(i)
The spatial search area is a closed loop area(ii)
The spatial search area contains all associated threatsVassociated(iii)
The positions of the boundary docking points should be on the associated threats’ bordersTo simplify the calculation, according to the properties of the space search boundary, the method for determining the boundary docking points is designed as follows.(i)
r1=r2Case 1.
Shown in Figure13, make the tangent line LR1 of the threat circle 1 through S (start or end point), and the tangent point A is the boundary docking point of the start/end point to the associated threat, where AR1⊥LR1, ∠AR1S=ζ.Case 2.
Shown in Figure14, cross point R1 to make the vertical line l of SR1, find the symmetrical point A′ of A with respect to l, and the point A′ is the boundary docking point on the associated threat.Case 3.
Different associated threats have different threat radius. According to the radius of adjacent associated threats, the location of the boundary docking point can be divided into three situations.Figure 13
The boundary docking point of the start/end point to the associated threat.Figure 14
The boundary docking point on the same associated threat.As shown in Figure15(a), straight line l′ is the vertical bisector of line segment R1R2, and point B is the symmetry point of A′ with respect to l′. For r1=r2, the point B must be on the boundary of threat 2, so point B is the boundary docking point of associated threat 1 to associated threat 2.
(ii)
r1<r2Figure 15
The boundary docking point of different associated threats.
(a)
R1=R2(b)
R1<R2(c)
R1>R2As shown in Figure15(b), straight line l′ is the vertical bisector of line segment R1R2, and point P is the symmetry point of A′ with respect to l′, where P is within the threat 2. Crossing point P to make the vertical line A′P of R1R2, and the intersection point B with threat 2 is the boundary docking point of associated threat 1 to associated threat 2, where ∠AR1R2=∠BR2R1=ζ.
(iii)
r1>r2As shown in Figure15(c), straight line l′ is the vertical bisector of line segment R1R2, and point P is the symmetry point of A′ with respect to l′, where P is out of the threat 2. Crossing point P to make the vertical line A′P of R1R2, and the intersection point B with threat 2 is the boundary docking point of associated threat 1 to associated threat 2, where ∠AR1R2=∠BR2R1=ζ.Due to the location of the associated threats and the mission start/end point were known, the boundary docking point and the search boundary information can be determined by the prior knowledge. The new spatial search area is shown in Figure16.Figure 16
Diagram of new spatial search area.


## 6. Simulation Experiments

In this section, for verifying the feasibility and effectiveness of the path planning system based on human-computer hybrid augmented intelligence framework for the UAH, a complete set of simulation experiments are designed. The simulation experiment process is shown in Figure17.Figure 17
Structure of the simulation.The simulation experiments are conducted in two-dimension (2D) field. In the 2D field, the size of the UAH flight space is700km∗400km. The start point is set to [0,0]. The target point is set to [500,0]. We assume that the threats in the planning space are denoted by several circular areas. The related information of the threats is shown in Tables 1 and 2.Table 1
The information of threat areas.
Threat numberThreat center (km)Threat radius (km)t1[125,-50]50t2[95,70]60t3[250,-110]50t4[230,7]50t5[240,160]90t6[310,50]30t7[360,-45]60t8[420,90]70Table 2
The information of threat areas.
Threat numberThreat center (km)Threat radius (km)t1[0,-150]90t2[60,-60]40t3[70,80]55t4[150,-90]38t5[130,0]30t6[210,160]90t7[230,7]50t8[250,-110]50t9[330,80]60t10[360,-50]60t11[500,-170]110t12[440,60]40t13[420,230]100


### 6.1. Algorithm Optimization Simulation Comparison Results

To show the superiority of the I-ABC algorithm improved in the algorithm optimization layer, the PSO algorithm, the ABC algorithm, and the I-ABC algorithm are simulated and compared under the same environment model. The maximum iteration number is set as500, the dimension D is set as 40, and the population size NP is set as 60. The results are averaged 20 independent runs, and the results of the simulation are illustrated in Figures 18, 19, and 20. The comparison result is listed in Table 3. In this table, the mean, worst, and optimal represent the mean fitness value, the worst fitness value, and the optimal fitness value, respectively.Figure 18
The comparative path planning results.Figure 19
The evolution curves of three algorithms.Figure 20
The statistical results for the three algorithms.
(a)
Statistical cost value for the three algorithms(b)
Statistical time for the three algorithmsTable 3
Results comparison for three algorithms.
AlgorithmsPSOABCI-ABCPerformancesValueTime(s)ValueTime(s)ValueTime(s)Optimal3.3928.032.8215.382.7114.36Worst6.9639.813.6419.753.2815.71Mean5.0229.863.2317.32.9915.07Figure18 shows that the intuitive differences of the experimental results between three algorithms in the 2D planning field. We can determine that the result planned by I-ABC algorithm can satisfy the requirements of the UAH path planning. The flight path planned by the PSO algorithm and the standard ABC algorithm have touched and crossed the edge of the threats, and the result of the PSO algorithm is oscillatory.The convergence curves of the three algorithms are shown in Figure19. It can be obviously seen from these curves that the convergence effect of the I-ABC algorithm is better than other algorithms. The I-ABC algorithm attains the global optimal value in iteration 221. But the standard ABC algorithm approaches to their optimal value in iteration 278. What is worse is that the PSO algorithm still cannot find its optimal value when the number of iterations is reached.The intuitive quantitative statistical results are shown in Figure20 and Table 3. The statistical results of the PSO algorithm are poor, the optimal value is 3.39, the worst value is 6.96, and the average running time is 29.86 s. For the standard ABC algorithm, the optimal value is 2.82, the worst value is 3.64, and the average running time is 17.3 s. Compared with the ABC and PSO algorithms, the planning results of the I-ABC algorithm has smaller cost value and average running time. These denote that the I-ABC algorithm can search for the optimal path stably and also verify the superior performance of the algorithm optimization layer in improving the traditional standard ABC algorithm.


### 6.2. Human Computing Optimization Simulation Comparison Results

To further reduce the search time of the flight path and keep its feasibility, the flight space needs to be clipped according to the prior knowledge for constructing a new spatial search space. The process of the space clipping operation is demonstrated in Figures21 and 22 and Tables 4 and 5. The results are averaged 20 independent runs in the different search spaces, and the results of the simulation are demonstrated in Figures 23 and 24 and Table 6.Figure 21
Threat space division.
(a)
Voronoi diagram construction(b)
Ξ1,21(c)
Ξ1,41,Ξ1,42,Ξ1,43(d)
Ξ3,41,Ξ3,42(e)
Ξ4,61(f)
Ξ6,71(g)
Ξ7,81Figure 22
Threat space tailoring.
(a)
Threat area classification(b)
Search space constructionTable 4
Associated convex polygons and threats.
Intersection pointsAssociated convex polygonsAssociated threatsΞ1,21v1, v2t1, t2Ξ1,41v1, v4t1, t4Ξ1,42v1, v4t1, t4Ξ1,43v1, v4t1, t4Ξ3,41v3, v4t3, t4Ξ3,42v3, v4t3, t4Ξ4,61v4, v6t4, t6Ξ6,71v6, v7t6, t7Ξ7,81v7, v8t7, t8Table 5
Boundary docking points.
Associated threatsBoundary docking pointsDistribution coordinates (km)t1A77.45,−65.45A′160.4,−85.36t2B41.54,97.24B′148.5,97.24t3C209.6,−117.8C′308.4,−117.8t4D207.3,51.55D′252.7,51.55t6E296.4,76.73E′323.6,76.73t7F317.6,−87.43F′402.4,−87.43t8G370.5,139.5G′489,101Figure 23
The comparative results for two different spatial search areas.
(a)
The comparative path planning results(b)
The comparative evolution curves resultsFigure 24
The statistical results of two different spatial search areas.
(a)
Statistical cost value(b)
Statistical timeTable 6
Results comparison for two spatial search areas.
Original spatial search areaNew spatial search areaPerformancesCost valueTime (s)Cost valueTime (s)Optimal1.95714.361.9129.05Worst3.40915.713.13512.34Mean2.81315.072.61311.69Figure21(a) shows that the original spatial search space was divided into 8 parts include v1,v2,⋯v8 by Voronoi diagram. According to the intersections of the flight path and the boundary of the convex polygon, the associated threats can be determined. Shown in Figures 21(b)–21(g)) and Table 4, the intersection point set is Ξ1,21, Ξ1,41, Ξ1,42, Ξ1,43, Ξ3,41, Ξ3,42, Ξ4,61, Ξ6,71, and Ξ7,81, the associated convex polygons are v1,v2,v3,v4,v6,v7,andv8, and the associated threats are t1,t2,t3,t4,t6,t7,andt8. Table 5 shows the coordinates of the boundary docking points, by connecting the start/end points with the boundary docking points, we can get the new search space construction as shown in Figure 22.Figure23(a) shows the path planning results of the I-ABC algorithm in two different spatial search areas. From the planning results, we can intuitively find that the final results planned by the I-ABC algorithm have almost no differences in two different spatial search areas. The convergence curves of two spatial search areas are illustrated in Figure 23(b). Similarly, from these curves, it can be find that the convergence effect by I-ABC algorithm in the new spatial search areas is slightly better than the original spatial search areas; however, the differences can be almost ignored in practical applications. In other words, the flight path result in the new spatial search area still maintains its optimality in the original spatial search area.The difference between the flight path of two spatial search areas can be found through the data in Figure24. For the original spatial search area, the optimal value is 1.957, the worst value is 3.409, and the mean value is 2.813. The optimal search time of the I-ABC algorithm witch runs 20 times is 14.56 s, the worst search time is 15.71 s, and the mean search time is 15.07 s. For the new spatial search area, the optimal value is 1.912, the worst value is 2.778, and the mean value is 2.346. The optimal search time of the I-ABC algorithm witch runs 20 times is 9.05 s, the worst search time is 12.34 s, and the mean search time is 11.69 s. By the comparison, the change in cost value is minimal. And the smoothness and feasibility of the flight path have not changed in the new spatial search area. These denote that the space clipping operation in the human computing layer can indeed reduce the search time of the flight path under the planning result within acceptable changes. Furthermore, the efficiency of the path planning system can be improved.


### 6.3. UAH Path Planning System Simulation Results

To further verify the effect of the space clipping operation for the path planning in the complex environment, a complicated environment model with more threats will be used for the simulation. The information of the threats in new environment is shown in Table2. The maximum iteration number of the I-ABC algorithm is set as 500, the dimension D is set as 40, the population size NP is set as 60. The simulation results of the path planning system for the UAH in the new map are shown as Figures 25(a)–25(e) and 26 and Table 7.Figure 25
The planning results by I-ABC for the two different spatial search areas.
(a)
Flight path by I-ABC in original spatial search area(b)
Threat area classification(c)
Search space construction(d)
Path planned by I-ABC in new spatial search area(e)
The comparative evolution curves resultsFigure 26
The statistical results of two different spatial search areas.
(a)
Statistical cost value(b)
Statistical timeTable 7
Results comparison for two spatial search areas.
Original spatial search areaNew spatial search areaPerformancesCost valueTime (s)Cost valueTime (s)Optimal2.91219.562.75413.6Worst4.02123.33.69819.81Mean3.57621.013.02616.94Figure25(a) shows that the path planning result by the I-ABC algorithm in the original spatial search area. We can see that the result planned by I-ABC algorithm avoids all threat areas, and it can meet the constraints of the UAH path planning.Figures25(b) and 25(c), respectively, show the process of the threat area classification and the search space construction. As shown in Figure 25(b), the associate threats can be identified as t2,t3,t4,t5,t7,t8,t9,t10,andt12. The new spatial search area consists of associated threats and black spatial search boundaries (as shown in Figure 25(c)).Figure25(d) shows the path planning results of the I-ABC algorithm in the new spatial search area. Compare with Figure 25(a), the flight path planned in the new spatial search area is similar to the flight path planned in the original spatial search area, both in terms of path smoothness and flight length. The convergence curves of the two spatial search areas are displayed in Figure 25(e). According to these curves, it can be obviously found that the convergence effect by I-ABC algorithm in the new spatial search areas is also similar to the original spatial search areas.The difference between the planning results of two spatial search areas can be found through the data in Figure26. For the original spatial search area, the optimal value is 2.912, the worst value is 4.021, and the mean value is 3.576. The optimal search time of the I-ABC algorithm witch runs 20 times is 19.56 s, the worst search time is 23.32 s, and the mean search time is 21.01 s. For the new spatial search area, the optimal value is 2.754, the worst value is 3.698, and the mean value is 3.026. The optimal search time of the I-ABC algorithm witch runs 20 times is 13.62 s, the worst search time is 19.81 s, and the mean search time is 16.94 s. By the comparison, the space clipping operation can maintain the excellent performance of the previous flight path planned by I-ABC algorithm. Moreover, the search time of the path planning system can be further reduced.


## 6.1. Algorithm Optimization Simulation Comparison Results

To show the superiority of the I-ABC algorithm improved in the algorithm optimization layer, the PSO algorithm, the ABC algorithm, and the I-ABC algorithm are simulated and compared under the same environment model. The maximum iteration number is set as500, the dimension D is set as 40, and the population size NP is set as 60. The results are averaged 20 independent runs, and the results of the simulation are illustrated in Figures 18, 19, and 20. The comparison result is listed in Table 3. In this table, the mean, worst, and optimal represent the mean fitness value, the worst fitness value, and the optimal fitness value, respectively.Figure 18
The comparative path planning results.Figure 19
The evolution curves of three algorithms.Figure 20
The statistical results for the three algorithms.
(a)
Statistical cost value for the three algorithms(b)
Statistical time for the three algorithmsTable 3
Results comparison for three algorithms.
AlgorithmsPSOABCI-ABCPerformancesValueTime(s)ValueTime(s)ValueTime(s)Optimal3.3928.032.8215.382.7114.36Worst6.9639.813.6419.753.2815.71Mean5.0229.863.2317.32.9915.07Figure18 shows that the intuitive differences of the experimental results between three algorithms in the 2D planning field. We can determine that the result planned by I-ABC algorithm can satisfy the requirements of the UAH path planning. The flight path planned by the PSO algorithm and the standard ABC algorithm have touched and crossed the edge of the threats, and the result of the PSO algorithm is oscillatory.The convergence curves of the three algorithms are shown in Figure19. It can be obviously seen from these curves that the convergence effect of the I-ABC algorithm is better than other algorithms. The I-ABC algorithm attains the global optimal value in iteration 221. But the standard ABC algorithm approaches to their optimal value in iteration 278. What is worse is that the PSO algorithm still cannot find its optimal value when the number of iterations is reached.The intuitive quantitative statistical results are shown in Figure20 and Table 3. The statistical results of the PSO algorithm are poor, the optimal value is 3.39, the worst value is 6.96, and the average running time is 29.86 s. For the standard ABC algorithm, the optimal value is 2.82, the worst value is 3.64, and the average running time is 17.3 s. Compared with the ABC and PSO algorithms, the planning results of the I-ABC algorithm has smaller cost value and average running time. These denote that the I-ABC algorithm can search for the optimal path stably and also verify the superior performance of the algorithm optimization layer in improving the traditional standard ABC algorithm.


## 6.2. Human Computing Optimization Simulation Comparison Results

To further reduce the search time of the flight path and keep its feasibility, the flight space needs to be clipped according to the prior knowledge for constructing a new spatial search space. The process of the space clipping operation is demonstrated in Figures21 and 22 and Tables 4 and 5. The results are averaged 20 independent runs in the different search spaces, and the results of the simulation are demonstrated in Figures 23 and 24 and Table 6.Figure 21
Threat space division.
(a)
Voronoi diagram construction(b)
Ξ1,21(c)
Ξ1,41,Ξ1,42,Ξ1,43(d)
Ξ3,41,Ξ3,42(e)
Ξ4,61(f)
Ξ6,71(g)
Ξ7,81Figure 22
Threat space tailoring.
(a)
Threat area classification(b)
Search space constructionTable 4
Associated convex polygons and threats.
Intersection pointsAssociated convex polygonsAssociated threatsΞ1,21v1, v2t1, t2Ξ1,41v1, v4t1, t4Ξ1,42v1, v4t1, t4Ξ1,43v1, v4t1, t4Ξ3,41v3, v4t3, t4Ξ3,42v3, v4t3, t4Ξ4,61v4, v6t4, t6Ξ6,71v6, v7t6, t7Ξ7,81v7, v8t7, t8Table 5
Boundary docking points.
Associated threatsBoundary docking pointsDistribution coordinates (km)t1A77.45,−65.45A′160.4,−85.36t2B41.54,97.24B′148.5,97.24t3C209.6,−117.8C′308.4,−117.8t4D207.3,51.55D′252.7,51.55t6E296.4,76.73E′323.6,76.73t7F317.6,−87.43F′402.4,−87.43t8G370.5,139.5G′489,101Figure 23
The comparative results for two different spatial search areas.
(a)
The comparative path planning results(b)
The comparative evolution curves resultsFigure 24
The statistical results of two different spatial search areas.
(a)
Statistical cost value(b)
Statistical timeTable 6
Results comparison for two spatial search areas.
Original spatial search areaNew spatial search areaPerformancesCost valueTime (s)Cost valueTime (s)Optimal1.95714.361.9129.05Worst3.40915.713.13512.34Mean2.81315.072.61311.69Figure21(a) shows that the original spatial search space was divided into 8 parts include v1,v2,⋯v8 by Voronoi diagram. According to the intersections of the flight path and the boundary of the convex polygon, the associated threats can be determined. Shown in Figures 21(b)–21(g)) and Table 4, the intersection point set is Ξ1,21, Ξ1,41, Ξ1,42, Ξ1,43, Ξ3,41, Ξ3,42, Ξ4,61, Ξ6,71, and Ξ7,81, the associated convex polygons are v1,v2,v3,v4,v6,v7,andv8, and the associated threats are t1,t2,t3,t4,t6,t7,andt8. Table 5 shows the coordinates of the boundary docking points, by connecting the start/end points with the boundary docking points, we can get the new search space construction as shown in Figure 22.Figure23(a) shows the path planning results of the I-ABC algorithm in two different spatial search areas. From the planning results, we can intuitively find that the final results planned by the I-ABC algorithm have almost no differences in two different spatial search areas. The convergence curves of two spatial search areas are illustrated in Figure 23(b). Similarly, from these curves, it can be find that the convergence effect by I-ABC algorithm in the new spatial search areas is slightly better than the original spatial search areas; however, the differences can be almost ignored in practical applications. In other words, the flight path result in the new spatial search area still maintains its optimality in the original spatial search area.The difference between the flight path of two spatial search areas can be found through the data in Figure24. For the original spatial search area, the optimal value is 1.957, the worst value is 3.409, and the mean value is 2.813. The optimal search time of the I-ABC algorithm witch runs 20 times is 14.56 s, the worst search time is 15.71 s, and the mean search time is 15.07 s. For the new spatial search area, the optimal value is 1.912, the worst value is 2.778, and the mean value is 2.346. The optimal search time of the I-ABC algorithm witch runs 20 times is 9.05 s, the worst search time is 12.34 s, and the mean search time is 11.69 s. By the comparison, the change in cost value is minimal. And the smoothness and feasibility of the flight path have not changed in the new spatial search area. These denote that the space clipping operation in the human computing layer can indeed reduce the search time of the flight path under the planning result within acceptable changes. Furthermore, the efficiency of the path planning system can be improved.


## 6.3. UAH Path Planning System Simulation Results

To further verify the effect of the space clipping operation for the path planning in the complex environment, a complicated environment model with more threats will be used for the simulation. The information of the threats in new environment is shown in Table2. The maximum iteration number of the I-ABC algorithm is set as 500, the dimension D is set as 40, the population size NP is set as 60. The simulation results of the path planning system for the UAH in the new map are shown as Figures 25(a)–25(e) and 26 and Table 7.Figure 25
The planning results by I-ABC for the two different spatial search areas.
(a)
Flight path by I-ABC in original spatial search area(b)
Threat area classification(c)
Search space construction(d)
Path planned by I-ABC in new spatial search area(e)
The comparative evolution curves resultsFigure 26
The statistical results of two different spatial search areas.
(a)
Statistical cost value(b)
Statistical timeTable 7
Results comparison for two spatial search areas.
Original spatial search areaNew spatial search areaPerformancesCost valueTime (s)Cost valueTime (s)Optimal2.91219.562.75413.6Worst4.02123.33.69819.81Mean3.57621.013.02616.94Figure25(a) shows that the path planning result by the I-ABC algorithm in the original spatial search area. We can see that the result planned by I-ABC algorithm avoids all threat areas, and it can meet the constraints of the UAH path planning.Figures25(b) and 25(c), respectively, show the process of the threat area classification and the search space construction. As shown in Figure 25(b), the associate threats can be identified as t2,t3,t4,t5,t7,t8,t9,t10,andt12. The new spatial search area consists of associated threats and black spatial search boundaries (as shown in Figure 25(c)).Figure25(d) shows the path planning results of the I-ABC algorithm in the new spatial search area. Compare with Figure 25(a), the flight path planned in the new spatial search area is similar to the flight path planned in the original spatial search area, both in terms of path smoothness and flight length. The convergence curves of the two spatial search areas are displayed in Figure 25(e). According to these curves, it can be obviously found that the convergence effect by I-ABC algorithm in the new spatial search areas is also similar to the original spatial search areas.The difference between the planning results of two spatial search areas can be found through the data in Figure26. For the original spatial search area, the optimal value is 2.912, the worst value is 4.021, and the mean value is 3.576. The optimal search time of the I-ABC algorithm witch runs 20 times is 19.56 s, the worst search time is 23.32 s, and the mean search time is 21.01 s. For the new spatial search area, the optimal value is 2.754, the worst value is 3.698, and the mean value is 3.026. The optimal search time of the I-ABC algorithm witch runs 20 times is 13.62 s, the worst search time is 19.81 s, and the mean search time is 16.94 s. By the comparison, the space clipping operation can maintain the excellent performance of the previous flight path planned by I-ABC algorithm. Moreover, the search time of the path planning system can be further reduced.


## 7. Conclusion

In this paper, a path planning system is presented based on human-computer hybrid augmented intelligence framework for improving the rapidity and optimality of the UAH path planner. At first, the proposed I-ABC algorithm optimizes the follow way of on-looker bees and the update strategy of nectar source. The dynamic evaluation selection strategy and complex optimization method accelerate the convergence rate and maintain the exploration ability of the population. In addition, the space clipping operation based on the attention mechanism reconstructs the spatial search area of the UAH. Unlike adjusting the number of iterations or modifying the parameters of the algorithm, the space clipping operation is directly applied to the optimal solution searched by the I-ABC algorithm. Benefit from this operation, the subsequent search time of the flight path for the path planning system is further reduced. Eventually, the experimental results show that the path planning system based on human-computer hybrid augmented intelligence framework for the UAH can combine the advantages of human and computer for planning a high-quality flight path. This study provides promising results for actual military mission.



---

*Source: 6639664-2021-01-13.xml*