Ground threat prediction-based path planning of unmanned autonomous helicopter using hybrid enhanced artificial bee colony algorithm

Zengliang Han, Mou Chen, Haojie Zhu, Qingxian Wu

School of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China

Keywords:UAH Path planning Ground threat prediction Hybrid enhanced Collaborative thinking

ABSTRACT Unmanned autonomous helicopter(UAH)path planning problem is an important component of the UAH mission planning system.Aiming to reduce the influence of non-complete ground threat information on UAH path planning, a ground threat prediction-based path planning method is proposed based on artificial bee colony (ABC) algorithm by collaborative thinking strategy.Firstly, a dynamic threat distribution probability model is developed based on the characteristics of typical ground threats.The dynamic no-fly zone of the UAH is simulated and established by calculating the distribution probability of ground threats in real time.Then, a dynamic path planning method for UAH is designed in complex environment based on the real-time prediction of ground threats.By adding the collision warning mechanism to the path planning model, the flight path could be dynamically adjusted according to changing no-fly zones.Furthermore, a hybrid enhanced ABC algorithm is proposed based on collaborative thinking strategy.The proposed algorithm applies the leader-member thinking mechanism to guide the direction of population evolution, and reduces the negative impact of local optimal solutions caused by collaborative learning update strategy, which makes the optimization performance of ABC algorithm more controllable and efficient.Finally, simulation results verify the feasibility and effectiveness of the proposed ground threat prediction path planning method.

1.Introduction

In recent years, it has been demonstrated that unmanned autonomous helicopter (UAH) represents one of the most challenging and high-potential equipments in aeronautics [1-3].Meanwhile, the path planning mission is becoming one of the key technologies of UAHs and has been widely investigated by scholars around the world[4].The main objective of UAH path planning is to design a flight path to reach the target point with minimal comprehensive costs, i.e., minimal probability of being destroyed while meeting the UAH performance requirements.The current solution is to plan and generate flight paths offline based on available global and local information,and subsequently adjust the pre-planned paths based on changes in environment,and mission,etc [5].However, how to combine all possible constraints to generate flight paths efficiently and stably is still an open problem[6].

In general, the path planning problems of UAH can be divided into global flight path planning and local dynamic flight path planning [7].Before the UAH takes off, the ground command system pre-plans a flight path for UAH on the mission based on the current information available about the mission.So far, many achievements have been made in the research of static path planning in known environment, such as artificial potential field (APF)[8], rapidly-exploring random tree (RRT) [9], A* algorithm [10],voronoi diagram [11] and probabilistic roadmaps (PRM) [12].In addition, with the advancement of technology, a large number of computational intelligence (CI) methods have emerged one after another [13,14].In Ref.[15], a new algorithm named spherical vector-based particle swarm optimization(SPSO)was developed to deal with the problem of path planning for unmanned aerial vehicles(UAVs)in complicated environments subjected to multiple threats.In Ref.[16], an improved fireworks algorithm (FWA) and particle swarm optimization (PSO) cooperation algorithm were designed to deal with the UAV global path planning problem.In Ref.[17],a path planning method was proposed based on the multistrategy evolutionary learning artificial bee colony (MSEL-ABC)algorithm for producing the UAH path planning problem.The results of numerous studies have shown that the above algorithms and their improvements can indeed solve the global path planning problem [18].

However,the modern air combat environment is so varied that the ideal path planning environment does not exist.In order to ensure that UAH can survive in a dynamic environment, its flight path must be dynamically adjusted according to the actual situation, i.e., local dynamic planning [19].The common planning methods include dynamic path planning method [20], artificial neural network method [21], fuzzy logic method [22], velocity obstacle method [23] and so on.In Ref.[24], a dynamic path planning approach based on neural networks was proposed to evacuation planning in large public buildings.In Ref.[25], the hybrid technology of the dynamic window approach (DWA) and the teaching learning-based optimization(TLBO)was designed for the NAO humanoid robot navigation.In Ref.[26],a hazardous flight region prediction system for small UAVs operated in urban areas was developed using a deep neural network(DNN)to support a risk assessment and safe trajectory planning.Unlike offline global path planning, online dynamic planning depends more on the performance of on-board sensors and computers.Real-world experience shows that for unexpected unknown threats, frequent dynamic planning will inevitably reduce the stability and reliability of the planning system.In fact, the occurrence of this situation is caused by the inadequacy of the global planning system to grasp the battlefield threat information.

Obviously, battlefield information is an important guarantee to support the UAH path planning system.Information about enemy threats is obtained through pre-war intelligence collection and analysis on the one hand [27].On the other hand,it relies on realtime detection by UAH's own sensor equipment during mission execution.However, pre-war information gathering and dynamic threat detection exacerbate the strain on the path planning system.More reliable ground threat information will directly affect the effectiveness of the UAH path planning system[28].In other words,the global path planning system with more threat information reference can reduce the number of local dynamic planning, and the whole flight process of UAH can be safer and more stable.Therefore, it is necessary and important to intelligently and efficiently process and predict non-complete ground threat information based on the available information and compensate for the adverse effects caused by ground threats in global path planning.

In this paper, we focus on the path planning problem for UAH based on dynamic ground threat prediction.The designed dynamic ground threat prediction method and hybrid enhanced ABC algorithm are able to provide a safe flight path for UAH.The main innovations and contributions of this work are summarized as follows:

(1) A ground threat prediction method based on probability density distribution is proposed.The distribution probabilities of ground threats are calculated and updated in real time based on their instantaneous orientation,velocity,intent and other non-complete information.

(2) A probabilistic diffusion-based dynamic no-fly zones modelling approach is designed to support path planning for UAH with the ground threat prediction.The boundaries of the dynamic no-fly zone are determined and updated in real time by extracting the edge of the probability spread area.

(3) To process the UAH path planning efficiently based on ground threat prediction, a hybrid enhanced ABC algorithm based on collaborative thinking strategy is proposed.Through the leader-member thinking mechanism and collaborative learning strategy, the negative impact of the local optimal solution is weakened, which effectively improves the quality of the UAH flight path.

The rest of this paper is arranged as follows.Section 2 demonstrates the problem formulation.Section 3 investigates the ground threat prediction-based path planning.Section 4 investigates the hybrid enhanced ABC algorithm based on collaborative thinking strategy.Section 5 provides the feasibility and effectiveness of the proposed method by simulation experiment.Finally, a brief summary is given in Section 6.

2.Problem formulation

As shown in Fig.1, the path planning problems can be divided into global planning and local planning [29].The globally planned flight paths provide the relevant reference confidence for the dynamic adjustment of local planning.In practice, global path planning faces the problem of difficulty in obtaining accurate threat information.In addition, local planning poses a huge challenge to the performance and reliability of the computer and sensors.Therefore, in order to reduce the frequency of UAH local dynamic planning and improve the stability of the path planning system,it is particularly important to accurately predict dynamic ground threats in global planning.

To solve the above problems,a path planning method based on dynamic ground threat prediction is proposed in this paper.As shown in Fig.2,the proposed path planning method of the UAH can be divided into the following three modules.

?Ground threat prediction module

In this module,the probability of dynamic threat distribution is calculated based on non-complete threat information.The range of possible the ground threat is simulated and predicted,thus the UAH dynamic no-fly zone can be established.

?Path planning module

The module solves the UAH flight path by a hybrid enhanced ABC algorithm based on the collaborative thinking strategy.By embedding the collision warning mechanism into the loop of the optimization algorithm,it improves the efficiency of dynamic path planning.

?Algorithm enhancement module

In this module, the traditional ABC algorithm can be enhanced by introducing human intelligence.The optimization performance of ABC algorithm can be upgraded by introducing leader-member thinking mechanism and collaborative learning update strategy.

3.Dynamic ground threat prediction-based path planning

3.1.Modeling of UAH environment

As shown in Fig.3, the UAH path planning technology is an important part of the mission planning for finding an optimal flight path that meets constraints in urban, battlefield, and other environments.

Fig.2.Framework of ground threat prediction-based UAH path planning.

First of all, the coordinate of S and T are set as (xps,yps,zps) and(xpt,ypt, zpt).The x-axis range has been divided into n+1 equal portions according to the S and T.The perpendicular planes(Ps,P1,P2,...,Pn,PT) of the x-axis are established according to the corresponding split points.

Put a discrete point in each vertical plane, and generate a collection of discrete points Cwp={S,p1(xp1,yp1,zp1),p2(xp2,yp2,zp2),...,pn(xpn,ypn,zpn),T} [29].In order to simplify the solution to the optimization problem,the optimization variable E is defined as

In this way, the path planning problem is transformed to 2n dimensional optimization problem.

Fig.3.Schematic of UAH battlefield model.

Fig.4.Diagram of movement direction selection.

3.2.Modeling of dynamic ground threats

In this section, a dynamic threat distribution probability model is designed based on non-complete information about the ground threat.Moreover,the dynamic ground threat distribution is used to build and update the dynamic no-fly zone of the UAH in real time.

3.2.1.Calculation of dynamic ground threat distribution probability

As shown in Fig.5, we summarize the maneuvering intentions of the dynamic ground threat into the following two categories.

?Intention 1: Manoeuvres towards a specific destination

Mobile air defence units choose to travel along roads or flat terrain when the dynamic ground threat has a clear driving target point.

?Intention 2: Evade reconnaissance or strikes

When the mobile air defense unit is evading our reconnaissance or strikes, the dynamic ground threat moves away from roads or gentle terrain.

Thus,different kinds of threats receive relative Πtyi according to different intentions, as shown in Table 1.where, Cr1, Cm1, Cg1are the intent factors when Intention 1 is adopted for different types of dynamic ground threats, respectively.Cr2, Cm2, Cg2are the intention factors for the dynamic ground threat when Intention 2 is adopted,respectively.

If the dynamic ground threat moves faster at the previous moment, it can be inferred that the probability that it will change its manoeuvre direction at the next moment is lower [31].Assuming the average speed of the threat as the judgement criterion,the speed impact factor for different threats can be described as

Fig.5.Schematic of ground threat driving intentions.

Table 1 Values of intention impact factor.

3.2.2.Predictive update mechanism for the dynamic ground threat status

The state update process can be divided into updating the direction of movement, updating the speed of movement and updating the distribution location.

(1) Update of movement direction

The movement direction update mechanism based on the roulette strategy can be defined as

Fig.6.Diagram of ground threats climb and descent.

(2) Update of movement speed

When the travel direction at moment t+1 is the same as at moment t, the travel speed of the dynamic ground threat can be understood to remain constant.

(3) Update of the distribution location

After determining the direction of manoeuvre and speed of travel of the dynamic ground threat,the coordinates of the threat's position in the map can be updated.The location update mechanism can be expressed as

3.2.3.Probabilistic diffusion mechanisms for the dynamic ground threat

Based on the laws of probability statistics,the distribution of the dynamic ground threat in a certain region basically obeys the Gaussian distribution [32].

As shown in Fig.7, we take the endpoint coordinates of each prediction and spread its probability values through a Gaussian distribution, ultimately forming a probability distribution region rather than a single coordinate point.The specific diffusion can be calculated by

where,Kp(x0,y0)denotes the probability of the current coordinate point, lijis the diffusion step size, i, j respectively represent the horizontal and vertical diffusion steps,and μ,σ represent the mean and variance of the error, respectively.

The distribution probability calculation and diffusion process of the dynamic ground threat can be shown in Fig.8.

3.2.4.Modelling of UAH dynamic no-fly zones

To ensure the safety of the UAH, any area where the dynamic ground threat may exist should be considered a no-fly zone.Areas where the dynamic ground threat may exist should be considered the no-fly zone to ensure the safety of UAH flights.As shown in Fig.9, the different colours in the heat map indicate differences in the probability of a threat occurring at that location.

The dynamic no-fly zone can be determined by establishing the boundaries of the probability spread area.It is important to note that the no-fly zone in this area is dynamically irregular and can change as the area of spread changes.The dynamic no-fly zone flow chart is shown in Fig.10.

3.3.Objective function and performance constraints

In this paper,the cost function of a flight path is described as the sum of three optimization criteria and three penalty terms.Thus,the objective function for predictive path planning can be expressed as [33].

Fig.7.Schematic of distribution probability diffusion.

Fig.8.Flowchart of the ground threat prediction algorithm.

Fig.9.Dynamic no-fly zone modeling.

Fig.10.Flowchart of dynamic no-fly zone modeling.

? Cost of the flight altitude

Fig.11.Schematic diagram of waypoint threat cost.

4.Hybrid enhanced ABC algorithm based on collaborative thinking strategy

The ABC algorithm has been widely used in the field of path planning due to its excellent optimization capability[35].However,as the path planning problem becomes more and more complex,the traditional ABC algorithm can no longer meet the performance requirements of current path planning algorithms.

In this paper, a hybrid enhanced ABC algorithm is designed based on collaborative thinking strategy(CTS).As shown in Fig.12,by introducing the leader-member thinking mechanism and the collaborative learning strategy, the CTS-ABC algorithm can effectively address the shortcomings of the traditional ABC algorithm,significantly improve the optimization performance of the ABC algorithm.

4.1.Initialization

All the vectors of the population of food sources x→iare initialized x→i(i ?1,2,...,SN by scout bees and control parameters are set.One nectar source represents a feasible solution to the path planning problem.Each nectar source x→ihas D parameters to be optimized (xji,j = 1,2,...,D).The initial source locations are randomly initialized by[36]

4.2.Employed bee phase based on leader-member thinking mechanism

For the traditional ABC algorithm, an employed bee searches a new food position v→iusing its current food position x→ias follows[36]:

where,i,k?{1,2,...,SN},j?{1,2,...,D},i≠k,and φ =rand(-1,1).

The necessity of mining near the current optimal nectar source is often higher than that of other nectar sources.The optimal food source should be searched in a different way from other nectar sources in the same iteration cycle.

As shown in Fig.13,the best individual in the current population is the leader and uses its own excellent position to evolve using innovative thinking.The rest of the individuals become members and adopt a guided thinking approach to position updating.

Fig.13.The schematic of leader-member thinking mechanism.

Fig.12.Schematic diagram of hybrid enhanced swarm intelligence.

(1) Search strategy based on innovative thinking

This search strategy is suitable for the optimal individual in the current iteration cycle.In order to fully explore the development potential for the highest quality individual, the search strategy based on innovative thinking is defined as

4.3.Onlooker bee phase

After completing the employed bees phase,a probability value is computed as follow[36]:

4.4.Scout bee phase based on collaborative learning strategy

When a nectar source has been explored several times and still not renewed,this employed bee will be transformed into the scout bee to explore a new nectar source by Ref.[37].It is worth mentioning that the local optimum solution is updated by randomly selecting a new nectar source in its vicinity.As shown in Fig.15, if the evolutionary direction of the local optimal solution does not improve the quality of this individual,the utilization value of this individual will be reduced and this situation may continue[38-40].

In order to reduce the negative impact of randomness on the scout bee phase, a collaborative learning based evolutionary strategy is proposed.As shown in Fig.16, during the scout bee phase, the locally optimal individuals generally go through three processes to cooperatively learn other individuals' knowledge before proposing their own ideas.

The core idea of collaborative learning search strategy is to adopt a new method to simulate the process of human swarm intelligence generating new ideas [41].Taking individual xji as an example,the specific steps for its adoption of collaborative learning strategies are as follows:

(1) Local optimal individual determination

The collaborative learning strategy is only applicable to locally optimal individuals.This judgment criterion of the locally optimal individuals can be described as

Fig.14.Specific steps of the employed bee phase.

Fig.15.The schematic of local optimal solution evolution/degeneration.

Fig.16.The schematic of collaborative learning process.

4.5.Computing complexity analysis

The computing complexity of the proposed method includes the dynamic threat prediction algorithm computing complexity and the CTS-ABC algorithm computing complexity.

(1) The dynamic threat prediction algorithm

Fig.17.Flowchart of the collaborative learning strategy.

The dynamic threat prediction algorithm can be viewed as an inference process that runs with two loops nested in it.The computing complexity of the dynamic threat prediction algorithm can be calculated by

Fig.18.Specific steps of the CTS-ABC algorithm.

Thus,we can get the maximum computing complexity of the CTSABC algorithm.

Table 2 Main parameters of scenarios.

Similarly, the maximum computing complexity of the traditional ABC algorithm can be described as [33].

The analysis results show that the computing complexity of the dynamic threat prediction algorithm and the CTS-ABC algorithm are relatively low.The efficiency of solving the UAH path planning problem can still be guaranteed.

Table 3 Main parameters of dynamic threats distribution model.

Table 4 Main parameters of scenarios.

5.Simulation results

Fig.19.The diffusion process of dynamic threat in Map 1.

In order to verify the efficiency of the proposed model and algorithm for the dynamic threat path planning problem, we have introduced the two scenarios with the different level (the higher level has the more complex threats and no-flight zones).The detailed information of scenarios is shown in Table 2, main parameters of dynamic threats distribution model are shown in Table 3,and main parameters of the CTS-ABC algorithm are shown in Table 4.Furthermore, to make the experiment results more objective,we make the following assumptions for each simulation:1) Assume that the initial location of all dynamic threats is on the flat terrain; 2) Assume that the UAHs in all scenarios fly at a constant speed; 3) The threat prediction termination time is the moment when the UAH simulation reaches the end point.

5.1.Scenario 1

For the first scenario, Fig.19 shows the diffusion process of dynamic threats in Map 1.Over time, the distribution of dynamic threats expands and the probability of distribution decreases.The diffusion process lasted a total of 16 s, which is the time taken for the UAH to reach the target point during the planning process.The colour change in the area of the probability distribution of dynamic threats in the graph illustrates this process.

Fig.20 describes the final shape of the dynamic no-fly zone.In order to reduce the computer rendering time,the boundaries of the dynamic no-fly zone are drawn to describe the extent and size of the entire no-fly zone.Due to the relatively flat terrain,the dynamic no-fly zone is relatively concentrated in scope.

Fig.21 shows the process of the UAH path planning based on the CTS-ABC algorithm in Map 1.The red path indicates the preplanned flight path and the yellow path indicates the actual flight path of the UAH.The green waypoints in the path are collision warning points, i.e.location nodes for path replanning.The red paths in Fig.21(5), Fig.21(7) and Fig.21(8) indicate the replanned UAH flight path.The dynamic no-fly zone changes over time during the path planning process.The yellow path in Fig.21(12)indicates the actual path flown by the UAH.It is important to note that although part of this path crosses the no-fly zone, the UAH has flown out of the area before the arrival of this no-fly zone, so this path does not affect the safety of the UAH.

Fig.22 shows the final path planning results of the CTS-ABC algorithm in Map 1.The CTS-ABC algorithm can plan a smooth predicted flight path for UAH based on the incomplete information of the battlefield.The predicted path enables the UAH to avoid ground threats that could affect flight safety,significantly reducing the computational stress on onboard computers and sensors.

Fig.20.The final shape of the dynamic no-fly zone Map 1.

Fig.21.The final shape of the dynamic no-fly zone Map 1.

Fig.22.The final flight path by the CTS-ABC algorithm in Map 1.

Fig.23 shows the convergence curves of the CTS-ABC algorithm in Map 1.Fig.23(a) depicts the iterative process of the flight path pre-planned by the CTS-ABC algorithm.It can be intuitively seen that the iterations for the CTS-ABC algorithm to converge to the global optimum is 27.The curves in Fig.23(b)indicate the iterative process of the five replanned flight paths using the CTS-ABC algorithm.Form the convergence curve, it is clear that the cost values for the five replanned paths are 1.71 × 104,1.65 × 104,1.59 × 104,1.51×104,and 1.28×104,respectively.Since the waypoints of the five replans are closer,the cost values of these replanned paths are also closer.The statistical results of the path planning can be shown in Table 5.

5.2.Scenario 2

Fig.23.The convergence results in Map 1.

Table 5 Statistical results of the CTS-ABC algorithm in Map 1.

Fig.24.The diffusion process of dynamic threat in Map 2.

Fig.25.The final shape of the dynamic no-fly zone Map 2.

In the second scenario,a more complex planning environment is used to verify the effectiveness of the proposed method.Fig.24 shows the diffusion process of dynamic threats in Map 2.Due to the more complex terrain,the dynamic threat spreads more widely across the map.The simulation of the threat diffusion process took 25 s,in other words,the simulated flight time of the UAH following the pre-planned path was also 25 s.

Fig.25 shows the final shape of the dynamic no-fly zone in Map 2.Compared to Map 1,the dynamic no-fly zones in Map 2 are more discrete in their distribution and more irregular in shape.The increase in the size and number of no-fly zones will directly increase the difficulty of UAH predictive path planning.Fig.26 shows the part of the process of UAH predictive path planning in Map 2.Fig.26(5)-Fig.26(17) show the part of the process of UAH path replanning.

Fig.27 shows the final path planning results of the CTS-ABC algorithm in Map 2.Due to the constantly changing dynamic nofly zone, the predictive path planning was replanned 21 times.

Fig.28 is the convergence curves of the CTS-ABC algorithm in the complex environment model.Form the simulation convergence curve,we can see that the CTS-ABC algorithm can find the optimal solution with fewer iterations in both path pre-planning and path re-planning.In Fig.28(a),the CTS-ABC algorithm requires only 120 iterations to plan an initial flight path.The cost value of the initial flight path is 0.62 × 106.The curves in Fig.28(b) indicate the iterative process of flight path re-planning using the CTS-ABC algorithm.The intuitive quantitative statistical results are shown in Table 6.

Simulation results show that the ground threat prediction path planning method of UAH can plan a safe flight path in the case of incomplete battlefield information.In addition, the collaborative thinking strategy enhances the optimization performance of the traditional ABC algorithm.Effective threat information prediction with hybrid enhanced CTS-ABC algorithm provides a strong guarantee for the UAH path planner.

6.Conclusions

Fig.26.The processes of pre-planning and re-planning Map 2.

Fig.27.The final flight path by the CTS-ABC algorithm in Map 2.

In this paper, a ground threat prediction-based path planning method for UAH has been proposed.Firstly, a dynamic ground threat distribution probability model was developed based on the characteristics of typical air defense threats.The movement state of dynamic threats was fuzzy inferred from the distribution probability, based on which the possible distribution area of dynamic ground threats was simulated.Then, based on the probability of distribution of the ground threat, we have modelled dynamic no-fly zones for UAH path planning.The boundaries of the dynamic no-fly zone were determined and updated in real time by extracting the edge of the probability spread area.Furthermore,for improving the efficiency and quality of the UAH predictive path planner, a hybrid enhanced ABC algorithm based on collaborative thinking strategy has been proposed.By introducing the leadermember thinking mechanism and the collaborative learning update strategy, the optimization performance of ABC algorithm was released and the solution efficiency of UAH path planning system was improved.Finally, simulation results show that the proposed path planning method can provide a safe flight path for UAH in the presence of non-complete dynamic ground threats.

Fig.28.The convergence results in Map 2.

Table 6 Statistical results of the CTS-ABC algorithm in Map 2.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.