Modified mayfly algorithm for UAV path planning

  Citation: Wang, X.; Pan, J.-S.; Yang, Q.; Kong, L.; Snášel, V.; Chu, S.-C. Modified Mayfly Algorithm for UAV Path Planning. Drones 2022,6, 134. https://doi.org/10.3390/drones 6050134 Academic Editor: Oleg Yakimenko Received: 19 April 2022 Accepted: 18 May 2022 Published: 23 May 2022 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). drones Article Modified Mayfly Algorithm for UAV Path Planning Xing Wang 1, Jeng-Shyang Pan 1, Qingyong Yang 1, Lingping Kong 2, Václav Snášel 2 and Shu-Chuan Chu 1,* 1College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, China; [email protected] (X.W.); [email protected] (J.-S.P.); [email protected] (Q.Y.) 2Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, 70032 Ostrava, Czech Republic; [email protected] (L.K.); vaclav[email protected] (V.S.) *Correspondence: [email protected] Abstract: The unmanned aerial vehicle (UAV) path planning problem is primarily concerned with avoiding collision with obstacles while determining the best flight path to the target position. This paper first establishes a cost function to transform the UAV route planning issue into an optimization issue that meets the UAV’s feasible path requirements and path safety constraints. Then, this paper introduces a modified Mayfly Algorithm (modMA), which employs an exponent decreasing inertia weight (EDIW) strategy, adaptive Cauchy mutation, and an enhanced crossover operator to effectively search the UAV configuration space and discover the path with the lowest overall cost. Finally, the proposed modMA is evaluated on 26 benchmark functions as well as the UAV route planning problem, and the results demonstrate that it outperforms the other compared algorithms. Keywords: path planning; modified mayfly algorithm; exponent decreasing inertia weight; adaptive Cauchy mutation; enhanced crossover operator 1. Introduction Unmanned aerial vehicles (UAV), as opposed to manned aircraft, refer to unmanned aircraft that can be controlled by remote radio control equipment or airborne computers. UAVs are less expensive and more flexible than manned aircraft, and they can reach difficult or dangerous places for humans to perform tasks. Therefore, UAVs have been widely used in civil and military fields. In the civil field, drones have played an important role in agricultural plant protection environment, aerial photography, express transportation, remote sensing of the oceans, and so on. In the military field, military drones can replace pilots in complex and dangerous missions such as intelligence gathering and reconnaissance surveillance. If the UAV is to complete the above tasks, one of the basic capabilities that the UAV must have is path planning capability [1]. The UAV path planning problem is to plan a collision-free path for the UAV from the starting point to the target point under the given flight conditions and flight environment. The planned path has the minimum cost and satisfies the relevant constraints. This problem can be simply described as an optimization problem with multiple constraints [ 2 ], so it is a challenge to traditional optimization strategies. There are already many mature solutions to this problem. In the direction of path planning based on graph search, Ref. [3] uses the A* algorithm for the UAV path planning problem with the goal of taking the least risk and consuming the least amount of fuel. Ref. [ 4 ] uses the D* Lite algorithm to plan an efficient path to the fire point for firefighting UAVs. In the direction of path planning based on sampling, Ref. [ 5 ] uses a hybrid algorithm combined with the artificial potential field method and the RRT-Connect algorithm for the path planning problem of UAV. Even though the techniques described above are relatively mature in mathematical theory, they are inefficient when working with discontinuous and non-derivative functions [ 6 ]. When Drones 2022,6, 134. https://doi.org/10.3390/drones6050134 https://www.mdpi.com/journal/drones Drones 2022,6, 134 2 of 21 tackling the UAV route planning problem with many restrictions [ 7 ], they are readily trapped into local optimum solutions. The path planning issue has been demonstrated to be an NP-hard problem, and the problem complexity grows with problem size [ 8 ]. When solving NP-hard problems, heuristic algorithms can produce high-quality solutions and are simple to implement. As a result, some well-developed meta-heuristics with good performance have been proposed in recent years, such as the Cuckoo Search algorithm (CS) [ 9 , 10 ], Particle Swarm Optimization (PSO) [11–13] , Genetic Algorithm (GA) [ 14 , 15 ], Artificial Bee Colony (ABC) algorithm [16,17], Differential Evolution (DE) algorithm [ 18 , 19 ], Grey Wolf Optimizer (GWO) [20,21], Ant Colony Optimization (ACO) algorithm [22,23], etc. The Mayfly algorithm (MA) [24] is a recently suggested optimization method, which takes the flight and mating behavior of the mayfly as the model. Female and male mayflies make up the entire mayfly population. The movements of the male and female mayflies offer the MA the capacity to conduct local searches, and the procedure of developing offspring through mayfly mating gives the MA global search capability. At present, research on MA is still relatively small. Inspired by the bare-bones PSO (BBPSO) [ 25 ], and then, Juan Zhao [ 26 ] proposed the bare-bones mayfly algorithm. The chaotic mayfly algorithm was suggested by Mohamed A. M. Shaheen [ 27 ], who used a logical chaotic map to initialize the mayfly population. This paper presented a modified Mayfly Algorithm (modMA), which includes the exponent decreasing inertia weight strategy, adaptive Cauchy mutation, and an enhanced crossover operator to analyze the path planning issue of UAV from the ground station to the destination, and it achieves good results. Many works on improving two-dimensional paths using metaheuristics have been proposed to this point. Ref. [ 28 ] used the bat and cuckoo algorithm in path planning. Ref. [ 29 ] used the grey wolf optimizer to tackle the UAV route planning issue. Ref. [ 30 ] used a chaotic cuckoo search algorithm to optimize drone paths in two-dimensional (2D) space. Besides, many researchers used other meta-heuristic algorithms to study UAV path planning problems [ 31 – 33 ]. However, no one has proposed the use of MA to tackle UAV path planning in a 2D environment. Hence, this paper will use the modified Mayfly Algorithm (modMA) to study this problem. The following are the contributions to this paper. (1) It proposes an enhanced crossover operator based on the MA, which can improve MA’s exploration capability and convergence speed. Then it proposes a modified Mayfly Algorithm (modMA), which combines the EDIW strategy, adaptive Cauchy mutation, and the enhanced crossover operator to balance the MA’s processes of exploration and exploitation; (2) It introduces three versions of the modMA and compares their performance on six 100 and 300 dimension benchmark functions; (3) Compare the three versions of the modified MA with other algorithms (MA, PSO, GWO, BOA) on twenty-six 50 dimension benchmark functions, and analyze the results of the experiments; (4) Use the three versions of the modified MA for tackling the 2D path planning problem of agricultural UAV. This paper is organized as follows: The standard MA, as well as the problem of UAV path planning, are briefly described in Section 2. Section 3provides three optimization ideas for improving the MA. In Section 4, two experiments are planned to compare the MA’s enhanced performance using different optimization ideas and apply the three versions of the modified MA to the path planning problem of the agricultural UAV. Section 5concludes. 2. Related Work This section will provide a quick overview of the standard MA and the two-dimensional path planning problem of UAV. Drones 2022,6, 134 3 of 21 2.1. Standard Mayfly Algorithm The proposed MA’s fundamental concept is derived from the flight and mating behavior of mayflies. It combines the advantages of PSO [ 11 ], GA [ 14 ] and FA [ 34 ]. MA initially produces a mayfly population comprising males and females at random. The current velocity and position of the ith mayfly are two n -dimensional vectors, they are denoted as vi=(vi1,vi2. . . , vin) and xi=(xi1,xi2. . . , xin) , respectively. Each mayfly modifies its position depending on its individual best ( pbest ) position and the best ( gbest ) position found by the whole mayfly swarm thus far. 2.1.1. Male Mayfly Flight Male mayflies cluster together, which suggests that their positions are updated based on social and personal experience. xt i is defined as the present position of the ith male mayfly at iteration t . Assuming that xt i is the current position of the ith mayfly at iteration t , the position can be updated by adding to a velocity vt i . Thus the male mayfly’s position update formula is: xt+1 i=xt i+vt i. (1) Consider those male mayflies are always performing nuptial dances not far from the water. The male mayfly’s velocity update formula is as follows: vt+1 ij =gvt ij +a1e−βr2 ppbestij −xt ij+a2e−βr2 ggbestj−xt ij, (2) where β is the visibility coefficient, a1 and a2 are defined as the positive constants representing the attraction. pbestij is the best position obtained by the ith male mayfly in dimension j . rp and rg are the Euclidean distances between xi and pbesti and between xi and gbest , respectively. The gravity coefficient is given by g , which can be a fixed number between 0 and 1, or it can be steadily lowered over iterations as in Equation (3). g=gmax −gmax −gmin itermax ×iter, (3) where gmax and gmin respectively represent the smallest and largest weights. The present and the total number of iterations are given by iter and itermax, respectively. The personal best position pbestiat iteration t+1 is determined by Equation (4). pbesti=(xt+1 i,i f f xt+1 i<f(pbesti) same as be f ore,otherwise.(4) The best male mayflies keep performing up and down motions through different velocities. The velocities of these male mayflies are determined by Equation (5). vt+1 ij =vt ij +d×r, (5) where the nuptial dance coefficient is given by d , and r means a random value in the range −1 to 1. 2.1.2. Female Mayfly Flight Female mayflies do not cluster together, however, they move towards male mayflies. yt i is defined as the present position of the ith female mayfly at iteration t . The change of the ith female mayfly in position is calculated as: yt+1 i=yt i+vt i. (6) In the MA, male and female mayflies with the same individual fitness ranking will attract each other, and the female mayfly’s position changes in response to the location of a male mayfly with the same ranking. The female mayfly’s velocity update formula is: Drones 2022,6, 134 4 of 21 vt+1 ij =   gvt ij +a2e−βr2 m f xt ij −yt ij,i f f (yi)>f(xi) gvt ij +f l ×r,i f f (yi)≤f(xi),(7) where vt ij and yt ij are respectively defined as the ith female mayfly’s velocity and position in dimension j at iteration t . a2 and β are defined as the attraction constant and the visibility coefficient, respectively. rm f is the Euclidean distance between the ith female mayfly and the ith male mayfly, f l is a random walk coefficient which suggests that a female is not attracted to a male, and rmeans a random value in the range −1 to 1. 2.1.3. Mating Procedure The mating is represented by the crossover operator which provides the global search capability for the MA. In the MA, male and female mayflies with the same individual fitness ranking will mate with each other to produce offspring mayflies. The mating operation of each pair of male and female mayflies produces two offspring, and the formula for the crossover operator is: γ1=L×male +(1−L)×f emale γ2=L×f emale +(1−L)×male,(8) where L means a random value in the range 0 to 1. Moreover, male and f emale denote the parents. Initially, the offspring’s velocity is set to zero. 2.1.4. Mutate the Genes of Offspring The mutation operator provides partial local search capability for MA. The chosen offspring can be updated by adding a random value to the variable throughout this process, so the offspring are changed to γ0 n=γn+σNn(0,1), (9) where the standard deviation and the standard normal distribution are represented by σ and Nn, respectively. 2.1.5. Reduction of Nuptial Dance and Random Walk Although these operators provide the MA with powerful local search capability, d and f l must be gradually reduced. Both values can be updated over the iterations t using Equations (10) and (11), respectively. dt=d0δt(10) f lt=f l0δt, (11) where δis a fixed number between 0 and 1. As previously stated, Algorithm 1depicts the MA’s pseudo-code. Drones 2022,6, 134 5 of 21 Algorithm 1 Pseudocode of MA. Input: male and female population sizes, N1 and N2 ; maximum iterations, itermax ; visibility coefficient, β ; learning factors, a1 and a2 ; nuptial dance coefficient, d ; random flight coefficient, f l; objective function, f(x) Output: Optimal solution gbest 1: Initialize the male and female velocities vmand vf 2: Evaluate population based on f(x) 3: Find the global best (gbest) 4: for iter = 1 to itermax do 5: Adjust the speed and position of each female mayfly using Equations (6) and (7) 6: Adjust the speed and position of each male mayfly using Equations (1), (2) and (5) 7: Sort the mayflies and rank them based on f(x) 8: Perform crossover and generate male and female offspring 9: Mutate the offspring 10: Divide offspring into male and female at random 11: Update the worst old individuals with the finest new ones 12: Update pbest and gbest 13: end for 2.2. UAV Path Planning Problem UAV path planning aims to discover the best flight route for the UAV given a variety of complicated flying restrictions such as threat constraints and fuel limits [ 35 ]. The flying height of the drone might be constant along its flight path from the start point to the target point, so this paper only focuses on the UAV’s horizontal flying distance. The mathematical model for UAV path planning and the cost function used to evaluate the planned path are described as follows. 2.2.1. Mathematical Model for Uav Path Planning In this model, we define S and T to be the start point and target point of the UAV, respectively. It is crucial to prevent collisions with numerous obstacles during the flight of the drone. As a result, this paper employs circles of varying radii to substitute barriers of varying threat levels. So the task of a UAV flight is to find a flight path from S to T with the smallest overall cost while avoiding collisions with obstacles. Figure 1depicts a schematic representation of the environment modeling for the UAV’s two-dimensional path planning. The path connected by the red line segments is the feasible path. Figure 1. Two-dimensional representation of planning space. Drones 2022,6, 134 6 of 21 The segment ST between the S and T in the original coordinate system OXY is split into D+ 1 equal portions by D vertical lines {Lk,k=1, 2, . . . , D} . We can get the path from S to T by picking a point on each vertical line. Thus, the planned path can be expressed as: L={S,(x(1),y(1)), . . . , (x(D),y(D)),T}. (12) To accelerate the processing speed, let the segment ST be the horizontal axis and use Equation (13) to transfer each point (x(k),y(k)) in the OXY to x0(k),y0(k) in the new coordinate system OX0Y0. "x0(k) y0(k)#=cos θsin θ −sin θcos θ x(k)−xs y(k)−ys,(13) where θ denotes to the rotation angle of the OXY , and the point (xs,ys) is the coordinate in the OXY. As shown in Figure 1, the abscissa of each node in the OX0Y0 can be calculated using formula x0(k)=|ST| D+1×k, so the planned path can be simplified and expressed as: L0=n(0,0),x0(1),y0(1), . . . . . ., x0(D),y0(D),(|ST|,0)o. (14) 2.2.2. Fitness Function Modeling A fitness function can be used to calculate the cost of a planned path. The fitness function value can be used to judge the quality of the planned path. The fitness function established in this paper is defined as the sum of two cost functions, given as follows: FL0=w1F1L0+w2F2L0, (15) where FL0 denotes the total cost function of the planned path; F1L0 denotes the cost of the planned path’s length; F2L0denotes the smoothness cost of the planned path. ω1 and ω2are the weight coefficients of the above cost function, and they are defined as: ωi≥0 ∑2 i=1wi=1. (16) Given the UAV’s restricted energy supply, the shorter the planned path length, the less time and energy the UAV spends, and the better it is for the UAV. Assume that the topography of the flight environment and information on the threatened area are known. The start state and the target state are L0 0 and L0D+1 , respectively. Hence, the cost F1 related to the path length can be computed as: F1L0= D ∑ k=0 dL0 k,L0 k+1, (17) where dL0 k,L0 k+1 is the distance between x0(k),y0(k) and x0(k+1),y0(k+1) . If the waypoint falls into the obstacle, we choose the intersection of the vertical line with the obstacle, the point closest to the waypoint, as the new search agent. Figure 2a,b depicts the post-collision processing flow. The path connected by the red line segments is the modified feasible path. Drones 2022,6, 134 7 of 21 (a) (b) Figure 2. The post-collision processing flow. (a)Scenario 1; (b)Scenario 2. The smoothness cost evaluates the turning rate critical to generating feasible paths. The smooth cost F2can be computed as:            F2L0=∑D k=1∆k ∆k=cos ϕ−cos θk,ϕ≥θi ϕ,ϕ<θi cos θ=aT iai+1 |ai||ai+1| , (18) where the ϕ is the maximum turning angle, θ is the current turning angle, and ai is a vector representing the ith segment of the entire route. 3. Modifided Mayfly Algorithm The standard MA has a better convergence speed than other swarm algorithms when dealing with low-dimensional situations. However, due to the influence of velocity fluctuation, the stability of the MA is poor, thus it leads to poor results. Furthermore, when dealing with high-dimensional nonlinear complicated situations, the MA cannot merely rely on its mechanism to get out of the local optimal zone, so the MA performs poorly on the multimodal functions. This section proposes a modified mayfly algorithm named modMA, which combines three strategies to improve the MA. One improvement is to use the exponent decreasing inertia weight strategy to improve MA, another uses the adaptive Cauchy mutation strategy to improve MA, and a third uses an enhanced crossover operator to improve MA. 3.1. Improvement 1: Exponent Decreasing Inertia Weight Strategy There are many decreasing inertia weight strategies, such as linear [ 36 ], adaptive [ 37 ], logarithmic [ 38 ], and others [ 39 ]. The larger inertia weight in the earlier period is favorable to the exploration of particles, and the particles can search a larger space. The smaller inertia weight in the later period is beneficial to the exploitation of particles. This paper introduces the exponent decreasing inertia weight [40] into MA, formula is as follows: g=gmin +exp1−itermax itermax −iter +1∗(gmax −gmin), (19) where gmax,gmin,iter, and itermax are the same to Equation (3). Drones 2022,6, 134 8 of 21 3.2. Improvement 2: Adaptive Cauchy Mutaion Strategy When utilizing Equations (1) and (2) in the standard MA to change the velocity of each male mayfly, the diversity of the entire mayfly population may decline. To mitigate this problem, the position of each male mayfly should be readjusted by using Cauchy-based mutation [ 41 , 42 ]. The standard Cauchy distribution’s probability density function can be described as: f(x)=1 π×1 1+x2, (20) where −∞<x<∞, the corresponding distribution function is expressed as: F(x)=1 πarctan(x)+1 2. (21) Random numbers generated via the standard Cauchy distribution are shown below: CM =tanπ×ε−1 2, (22) where CM denotes a random value produced by the inverse function of the standard Cauchy distribution function, ε means a random value in the range 0 to 1 produced by a uniform distribution. According to Fogarty [ 43 ], improved performance is attained when the mutation rate falls exponentially with the number of iterations. Ref. [ 44 ] pointed out that the concept is related to that of the simulated annealing (SA) algorithm [ 45 ]. So after utilizing Equations (1) and (2) to change the position of each male mayfly, the position of each male mayfly needs to be readjusted using the Equation (22), which combines Cauchy mutation strategy with an adaptive mutation. Xt+1 i=xt+1 i+xt+1 i×CM ×exp((1−t)×α), (23) where xt+1 i is the ith individual calculated using Equations (1) and (2), and Xt+1 i represents the mutated individual. α is a contraction-expansion coefficient that controls the speed of convergence and it is defined as 0.15. In this section, we combine the Cauchy mutation strategy with an adaptive mutation which can make the MA generate perturbations with a large step size in the early iterations so that the particles can jump from their current position to another and help MA escape the local optima. The perturbations with a smaller step size in the late iterations can speed up the convergence of the MA. It is worth mentioning that we do not use Cauchy-based mutation to readjust the positions of the particles calculated using Equations (1) and (5). 3.3. Improvement 3: Enhanced Crossover Operator Although the crossover and reproduction operations of mayflies provide the MA with exploration ability as well as enhance the MA’s convergence speed, the MA has a not strong exploration ability. Hence, we use the horizontal crossover search [ 46 ] to improve it. The enhanced crossover operator of the MA employing horizontal crossover search is as follows: γ1=L×male +(1−L)×f emale +c1×(male −f emale) γ2=L×f emale +(1−L)×male +c2×(f emale −male),(24) where c1 and c2 are expansion coefficients, and they are both random values between − 1 and 1 produced by a uniform distribution. The horizontal crossover operation divides the problem-solving space of multidimensional into half-population of hypercubes, allowing new spots on the hypercube’s periphery to be sampled with a low probability, and reducing the blind region that are unable to explore by two paired parent individuals. Offspring generated using the horizontal Drones 2022,6, 134 9 of 21 crossover operation need to be compared with their parents, and individuals with greater fitness values are selected for the following iteration. It causes the MA to continuously converge to the best solution and ensure the convergence efficiency without affecting the optimization accuracy through the horizontal crossover operation. We can also appropriately shrink or expand the search space generated by the two paired parent individuals. The formula of the crossover operator of the MA improved by shrinking the search space is as follows: γ1=d1×(L×male +(1−L)×f emale) γ2=d3×(L×f emale +(1−L)×male),(25) where d1 and d3 are the contraction coefficients, and they are both random values between 0.7 and 1 produced by a uniform distribution. The formula of the crossover operator of the MA improved by expanding the search space is as follows: γ1=d2×(L×male +(1−L)×f emale) γ2=d4×(L×f emale +(1−L)×male),(26) where d2 and d4 are the expansion coefficients, and they are both random values between 1 and 1.3 produced by a uniform distribution. Therefore, the enhanced crossover operator formula of MA can be described as: γ1=       L×male +(1−L)×f emale,rand1<pone L×male +(1−L)×f emale +c1×(male −f emale),rand1>pone,rand2<ptwo d1×(L×male +(1−L)×f emale),rand1>pone,rand2<ptwo,rand3<pthree d3×(L×male +(1−L)×f emale),rand1>pone,rand2<ptwo,rand3>pthree. (27) γ2=       L×f emale +(1−L)×male,rand1<pone L×f emale +(1−L)×male +c2×(f emale −male),rand1>pone,rand2<ptwo d2×(L×f emale +(1−L)×male),rand1>pone,rand2<ptwo,rand3<pthree d4×(L×f emale +(1−L)×male),rand1>pone,rand2<ptwo,rand3>pthree, (28) where rand1 , rand2 , and rand3 are the random input numbers between [0,1]. pone , ptwo , and pthree are the switching probabilities, which control the method of offspring generation. For the value of switching probability pone , we refer to the parameter tuning technique of switching probability in the Butterfly Optimization Algorithm (BOA) [ 47 ]. From our simulations, we found that pone = 0.8, ptwo = 0.5, and pthree = 0.5 work better for most applications. 4. Experimental Results and Application In this part, we select a variety of numerical optimization functions from CEC benchmark functions to assess the effect of the modified MA presented in this article. Tables A1 and A2 in Appendix Ashow the expression, dimension, domain of a variable, and minimum value of each benchmark function. These benchmark functions used in this study can be found in [ 48 ], and they are classified into two groups. The unimodal benchmark functions (F1–F14) and multimodal benchmark functions (F15–F26) are applied to calculate the abilities to exploit and explore of the algorithm benchmarked by benchmark functions, respectively. To assess the efficacy of the three improvement techniques described in this study for MA, we first test and analyze the three versions of the improved MA through comparison experiment 1 by six benchmark functions from Tables A1 and A2 with Dim = 100 and Dim = 300 . It is worth mentioning that modMA-1 is characterized in this study as an MA that is improved by an adaptive Cauchy mutation strategy and the original crossover operator, modMA-2 is defined as an MA modified using only the enhanced crossover operator, and modMA is defined as an MA that incorporates three improved strategies. Drones 2022,6, 134 16 of 21 Table 7. Space environment settings. Case Number Serial Number Obstacle Center Obstacle Radius 1 1 (50, 105) 70 2 (125, 250) 35 3 (304, 400) 45 4 (404, 320) 50 5 (440, 440) 20 6 (280, 310) 25 7 (230, 220) 25 8 (230, 100) 50 2 1 (160, 160) 15 2 (50, 105) 70 3 (275, 185) 80 4 (400, 425) 40 5 (125, 250) 35 6 (275, 325) 28 7 (450, 250) 45 8 (175, 410) 70 9 (35, 325) 50 10 (330, 300) 25 The experimental results are listed in Table 8. The corresponding convergence curves are shown in Figures 7a–f and 8a–f. From Figures 7a–f and 8a–f, all the seven algorithms can find collision-free flight paths, but they perform differently in terms of path length and smoothness. It can be seen from Table 8that in the case of D = 30, that is, in a lower dimension, each algorithm can achieve good results, and the path length planned by modMA is shorter and the path is smoother. In the case of D = 50, that is, in a higher dimension, modMA, modMA-1, and modMA-2 greatly improve the performance of MA. modMA and modMA-1 can achieve better results in most cases, and both have good initial solutions and convergence rates, but the fluctuation of modMA is smaller than that of modMA-1. Among all the comparison algorithms, the overall cost of modMA planning is the smallest in most cases, which shows that the path planned by the modMA can reach the best when the UAV avoids collision, which proves the effectiveness of the modMA. Table 8. The average and standard deviation values of the total cost function over thirty runs. Case Number D Results MA modMA-1 modMA-2 modMA BOA PSO GWO 1 30 Avg 705.432 690.146 692.234 689.532 711.309 698.138 693.970 Std 6.199 1.146 3.313 1.014 7.455 6.897 2.749 50 Avg 753.834 699.756 723.285 698.312 720.847 739.353 710.557 Std 18.143 2.822 11.390 1.419 13.549 18.421 9.951 2 30 Avg 717.855 692.493 693.226 691.735 711.219 694.774 694.458 Std 10.718 1.729 5.087 1.359 4.180 3.273 1.675 50 Avg 781.436 703.315 747.785 702.119 721.602 732.321 710.133 Std 28.557 3.123 23.130 1.978 6.189 12.167 7.973 The path planning problem has many local solutions, this makes classical optimization techniques difficult to solve. modMA shows excellent performance on this complex problem, i.e., the quality of the solution and the stability of the solution. In addition, modMA also has good initial solution and fast convergence speed. However, the model established in this paper still has some shortcomings. After collision handling, that is, the operation of moving the waypoint to the edge of the obstacle, the planned path length may be longer than the theoretical optimum. Drones 2022,6, 134 17 of 21 (a) (b) (c) (d) (e) (f) Figure 7. Path diagram of a single run in Case 1. ( a ) Comparative path planning results in Case 1, Dim = 30; ( b ) Evolution curves of four algorithms in Case 1, Dim = 30; ( c ) Evolution curves of different algorithms in Case 1, Dim = 30; ( d ) Comparative path planning results in Case 1, Dim = 50; ( e ) Evolution curves of four algorithms in Case 1, Dim = 50; ( f ) Evolution curves of different algorithms in Case 1, Dim = 50. (a) (b) (c) (d) (e) (f) Figure 8. Path diagram of a single run in Case 2. ( a ) Comparative path planning results in Case 2, Dim = 30. ( b ) Evolution curves of four algorithms in Case 2, Dim = 30. ( c ) Evolution curves of different algorithms in Case 2, Dim = 30. ( d ) Comparative path planning results in Case 2, Dim = 50. ( e ) Evolution curves of four algorithms in Case 2, Dim = 50. ( f ) Evolution curves of different algorithms in Case 2, Dim = 50. 5. Conclusions A new algorithm modMA which incorporates a mixed strategy consisting of three improved techniques is proposed throughout this research for solving the UAV path planning problem. By introducing the EDIW strategy to balance the particles’ processes of exploration and exploitation. By perturbing the position of each male particle with an adaptive Cauchy mutation operator, the diversity of the swarm is increased. By introducing an enhanced crossover operator, the exploration ability of the modMA is enhanced. To Drones 2022,6, 134 18 of 21 assess the efficacy of these three improvement techniques on MA, two experiments are designed. The suggested modMA is tested on 26 benchmark functions, and it has obvious advantages in finding both the best value and convergence speed. Finally, the proposed modMA, together with PSO, GWO, and BOA, are applied to the UAV path planning problem; simulation experiments show that the effect of modMA which is applied to the UAV path planning problem is relatively stable, and the quality of the planned path is high. The time cost of modMA in the path planning problem of UAV is higher than that of PSO, BOA and GWO, which is determined by its algorithm structure, but the the convergence speed is fast in the process of solving the problem. In future work, hybrid [ 49 , 50 ] can be introduced to further enhance the performance of the modMA. The cost of the drone collision threat can also be considered in the UAV path planning problem. Author Contributions: Conceptualization, X.W. and J.-S.P.; Formal analysis, X.W., J.-S.P., Q.Y. and S.-C.C.; Methodology, X.W., J.-S.P., L.K., V.S. and S.-C.C.; Validation, J.-S.P., Q.Y., L.K. and V.S.; Writing—original draft, X.W.; Writing—review & editing, X.W., J.-S.P., Q.Y., L.K., V.S. and S.-C.C. All authors have read and agreed to the published version of the manuscript. Funding: This research received no external funding. Institutional Review Board Statement: Not applicable. Informed Consent Statement: Not applicable. Data Availability Statement: Not applicable. Conflicts of Interest: The authors declare no conflict of interest of this paper. Appendix A Table A1. Unimodal benchmark functions. Name Formula of Functions Dim Range fmin Sphere F1(x)=Dim Σ i=1x2 i50 [−100, 100] 0 Schwefel 2.22 F2(x)=Dim Σ i=1|xi|+∏Dim i=1|xi|50 [−10, 10] 0 Schwefel 1.2 F3(x)=∑Dim i=1∑i j=ixj250 [−100, 100] 0 Schwefel 2.21 F4(x)=max{|xi|,1 ≤i≤Dim}50 [−10, 10] 0 Step F5(x)=∑Dim i=1(xi+0.5)250 [−10, 10] 0 Quartic F6(x)=∑Dim i=1Dim ·x2 i+rand(0,1)50 [−1.28, 1.28] 0 Exponential F7(x)=exp0.5 ∑Dim i=1xi50 [−10, 10] 0 Sum power F8(x)=∑Dim i=1|xi|(i+1)50 [−1, 1] 0 Sum square F9(x)=∑Dim i=1Dim ·x2 i50 [−10, 10] 0 Rosenbrock F10(x)=∑Dim i=1100xi+1−x2 i+(xi−1)250 [−5, 10] 0 Zakharov F11(x)=∑Dim i=1x2 i+∑Dim i=10.5ixi2+∑Dim i=10.5ixi450 [−5, 10] 0 Trid F12(x)=(xi−1)2+∑Dim i=1i·2x2 i−xi−1250 [−10, 10] 0 Elliptic F13(x)=∑Dim i=1106(i−1)/(Dim−1)·x2 i50 [−100, 100] 0 Cigar F14(x)=x2 1+106∑Dim i=1x2 i50 [−100, 100] 0 Drones 2022,6, 134 19 of 21 Table A2. Multimodal benchmark functions. Name Formula of Functions Dim Range fmin Rastrigin F15(x)=∑Dim i=1x2 i−10cos(2πxi)+1050 [−5.12, 5.12] 0 NCRastrigin F16(x)= Dim ∑ i=1hy2 i−10cos(2πyi)+10i, yi=xi,|xi|<0.5 round(2xi)/2, |xi|>0.5 50 [−5.12, 5.12] 0 Ackley F17(x)=−20 exp −0.2v u u t1 Dim Dim ∑ i=1 x2 i  +exp 1 Dim Dim ∑ i=1 cos(2πxi)!+20 +exp(1) 50 [−50, 50] 0 Griewank F18(x)=1 4000 ∑Dim i=1x2 i−∏Dim i=1cosxi √i+1 50 [−600, 600] 0 Alpine F19(x)=∑Dim i=1|xi·sin(xi)+0.1xi|50 [−10, 10] 0 Penalized 1 F20(x)=π Dim (Dim−1 ∑ i=1 (yi−1)2h1+10sin2(πy1)i+(yDim −1)2+10 sin2(πy1))+ Dim ∑ i=1 u(xi,10,100,4) yi=1+(xi+1)/4, uyi,a,k,m=   k(xi−a)m,xi>a 0, −a≤xi≤a k(−xi−a)m,xi<a 50 [−100, 100] 0 Penalized 2 F21(x)=1 10(sin2(πx1)+ Dim−1 ∑ i=1 (xi−1)2h1+sin2(3πxi+1)i+(xDim−1)21+sin2(2πxi+1))+ Dim ∑ i=1 u(xi,5,100,4)50 [−100, 100] 0 Schwefel F22(x)=∑Dim i=1xi·sinp|xi|50 [−100, 100] 0 Levy F23(x)=sin2(3πxi)+∑Dim−1 i=1(xi−1)21+sin2(3πxi+1)+|xDim −1|·1+sin2(2πxDim)50 [−10, 10] 0 Weierstrass F24(x)=∑Dim i=1∑kmax k=0akcos2πbk(xi+0.5)−Dim ·∑kmax k=0akcosπbk,a=0.5, b=3, kmax =20 50 [−1, 1] 0 Solomon F25(x)=1−cos2πq∑Dim i=1x2 i+0.1q∑Dim i=1x2 i50 [−100, 100] 0 Bohachevsky F26(x)=∑Dim i=1x2 i+2x2 i+1−0.3 ·cos(3πxi)50 [−10, 10] 0 Drones 2022,6, 134 20 of 21 References 1. Yu, X.; Zhang, Y. Sense and avoid technologies with applications to unmanned aircraft systems: Review and prospects. Prog. Aerosp. Sci. 2015,74, 152–166. [CrossRef] 2. Huo, L.; Zhu, J.; Wu, G.; Li, Z. A novel simulated annealing based strategy for balanced UAV task assignment and path planning. Sensors 2020,20, 4769. [CrossRef] 3. Dhulkefl, E.J.; Durdu, A. Path planning algorithms for unmanned aerial vehicles. Int. J. Trend Sci. Res. Dev. 2019 ,3, 359–362. [CrossRef] 4. Zhang, Z.; Wu, J.; Dai, J.; He, C. A novel real-time penetration path planning algorithm for stealth UAV in 3D complex dynamic environment. IEEE Access 2020,8, 122757–122771. [CrossRef] 5. Zhang, D.; Xu, Y.; Yao, X. An improved path planning algorithm for unmanned aerial vehicle based on rrt-connect. In Proceedings of the 2018 37th Chinese Control Conference (CCC), Wuhan, China, 25–27 July 2018; pp. 4854–4858. 6. Huo, L.; Zhu, J.; Li, Z.; Ma, M. A hybrid differential symbiotic organisms search algorithm for UAV path planning. Sensors 2021 , 21, 3037. [CrossRef] 7. Zhang, D.; Duan, H. Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning. Neurocomputing 2018,313, 229–246. [CrossRef] 8. Zhang, X.; Duan, H. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl. Soft Comput. 2015,26, 270–284. [CrossRef] 9. Rajabioun, R. Cuckoo optimization algorithm. Appl. Soft Comput. 2011,11, 5508–5518. [CrossRef] 10. Song, P.C.; Pan, J.S.; Chu, S.C. A parallel compact cuckoo search algorithm for three-dimensional path planning. Appl. Soft Comput. 2020,94, 106443. [CrossRef] 11. Kennedy, J.; Eberhart, R. Particle swarm optimization. In Proceedings of the ICNN’95-International Conference on Neural Networks, Perth, WA, USA, 27 November–1 December 1995; Volume 4, pp. 1942–1948. 12. Chu, S.C.; Roddick, J.F.; Pan, J.S. A parallel particle swarm optimization algorithm with communication strategies. J. Inf. Sci. Eng. 2005,21, 809–818. 13. Phung, M.D.; Ha, Q.P. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization. Appl. Soft Comput. 2021,107, 107376. [CrossRef] 14. Mirjalili, S. Genetic algorithm. In Evolutionary Algorithms and Neural Networks; Springer: Berlin/Heidelberg, Germany, 2019; pp. 43–55. 15. Roberge, V.; Tarbouchi, M.; Labonté, G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans. Ind. Info. 2012,9, 132–141. [CrossRef] 16. Basturk, B. An artificial bee colony (ABC) algorithm for numeric function optimization. In Proceedings of the IEEE Swarm Intelligence Symposium, Indianapolis, IN, USA, 12–14 May 2006. 17. Lei, L.; Shiru, Q. Path planning for unmanned air vehicles using an improved artificial bee colony algorithm. In Proceedings of the 31st Chinese Control Conference, Hefei, China, 25–27 July 2012; pp. 2486–2491. 18. Price, K.V. Differential evolution: A fast and simple numerical optimizer. In Proceedings of the North American Fuzzy Information Processing, Berkeley, CA, USA, 19–22 June 1996; pp. 524–527. 19. Pan, J.S.; Liu, N.; Chu, S.C. A hybrid differential evolution algorithm and its application in unmanned combat aerial vehicle path planning. IEEE Access 2020,8, 17691–17712. [CrossRef] 20. Mirjalili, S.; Mirjalili, S.M.; Lewis, A. Grey wolf optimizer. Adv. Eng. Softw. 2014,69, 46–61. [CrossRef] 21. Lv, J.X.; Yan, L.J.; Chu, S.C.; Cai, Z.M.; Pan, J.S.; He, X.K.; Xue, J.K. A new hybrid algorithm based on golden eagle optimizer and grey wolf optimizer for 3D path planning of multiple UAVs in power inspection. Neural Comput. Appl. 2022 ,193, 509–532. [CrossRef] 22. Dorigo, M.; Birattari, M.; Stutzle, T. Ant colony optimization. IEEE Comput. Intell. Mag. 2006,1, 28–39. [CrossRef] 23. Konatowski, S.; Pawłowski, P. Ant colony optimization algorithm for UAV path planning. In Proceedings of the 2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), Lviv-Slavske, Ukraine, 20–24 February 2018; pp. 177–182. 24. Zervoudakis, K.; Tsafarakis, S. A mayfly optimization algorithm. Comput. Ind. Eng. 2020,145, 106559. [CrossRef] 25. Kennedy, J. Bare bones particle swarms. In Proceedings of the 2003 IEEE Swarm Intelligence Symposium, SIS’03 (Cat. No. 03EX706), Indianapolis, IN, USA, 26 April 2003; pp. 80–87. 26. Juan, Z.; Zheng-Ming, G. Bare bones mayfly optimization algorithm. In Proceedings of the 2020 2nd International Conference on Machine Learning, Big Data and Business Intelligence (MLBDBI), Taiyuan, China, 23–25 October 2020; pp. 238–241. 27. Shaheen, M.A.; Hasanien, H.M.; El Moursi, M.; El-Fergany, A.A. Precise modeling of PEM fuel cell using improved chaotic MayFly optimization algorithm. Int. J. Energy Res. 2021,45, 18754–18769. [CrossRef] 28. Gigras, Y.; Gupta, K.; Choudhury, K. A comparison between bat algorithm and cuckoo search for path planning. Int. J. Innov. Res. Comput. Commun. Eng. 2015,3, 4459–4466. 29. Zhang, S.; Zhou, Y.; Li, Z.; Pan, W. Grey wolf optimizer for unmanned combat aerial vehicle path planning. Adv. Eng. Softw. 2016 , 99, 121–136. [CrossRef] Drones 2022,6, 134 21 of 21 30. Pan, J.S.; Liu, J.L.; Hsiung, S.C. Chaotic cuckoo search algorithm for solving unmanned combat aerial vehicle path planning problems. In Proceedings of the 2019 11th International Conference on Machine Learning and Computing, Zhuhai, China, 22–24 February 2019; pp. 224–230. 31. Duan, H.; Qiao, P. Pigeon-inspired optimization: A new swarm intelligence optimizer for air robot path planning. Int. J. Intell. Comput. Cybern. 2014,7, 24–37. [CrossRef] 32. Wang, G.; Guo, L.; Duan, H.; Liu, L.; Wang, H. A modified firefly algorithm for UCAV path planning. Int. J. Hybrid Inf. Technol. 2012,5, 123–144. 33. Zhu, W.; Duan, H. Chaotic predator–prey biogeography-based optimization approach for UCAV path planning. Aerosp. Sci. Technol. 2014,32, 153–161. [CrossRef] 34. Yang, X.S. Firefly algorithm, Levy flights and global optimization. In Research and Development in Intelligent Systems XXVI; Springer: Berlin/Heideberg, Germany, 2010; pp. 209–218. 35. Foo, J.L.; Knutzon, J.; Kalivarapu, V.; Oliver, J.; Winer, E. Path planning of unmanned aerial vehicles using B-splines and particle swarm optimization. J. Aerosp. Comput. Inf. Commun. 2009,6, 271–290. [CrossRef] 36. Shi, Y.; Eberhart, R. A modified particle swarm optimizer. In Proceedings of the 1998 IEEE International Conference on Evolutionary Computation Proceedings, IEEE World Congress on Computational Intelligence (Cat. No. 98TH8360), Anchorage, AK, USA, 4–9 May 1998; pp. 69–73. 37. Nickabadi, A.; Ebadzadeh, M.M.; Safabakhsh, R. A novel particle swarm optimization algorithm with adaptive inertia weight. Appl. Soft Comput. 2011,11, 3658–3670. [CrossRef] 38. Gao, Y.L.; An, X.H.; Liu, J.M. A particle swarm optimization algorithm with logarithm decreasing inertia weight and chaos mutation. In Proceedings of the 2008 International Conference on Computational Intelligence and Security, Washington, DC, USA, 13–17 December 2008; Volume 1, pp. 61–65. 39. Rathore, A.; Sharma, H. Review on inertia weight strategies for particle swarm optimization. In Proceedings of Sixth International Conference on Soft Computing for Problem Solving; Springer: Berlin/Heidelberg, Germany, 2017; pp. 76–86. 40. Cao, Z.; Shi, Y.; Rong, X.; Liu, B.; Du, Z.; Yang, B. Random grouping brain storm optimization algorithm with a new dynamically changing step size. In Proceedings of the International Conference in Swarm Intelligence; Springer: Berlin/Heidelberg, Germany, 2015; pp. 357–364. 41. Zou, Y.; Liu, P.X.; Yang, C.; Li, C.; Cheng, Q. Collision detection for virtual environment using particle swarm optimization with adaptive cauchy mutation. Clust. Comput. 2017,20, 1765–1774. [CrossRef] 42. Chakraborty, F.; Roy, P.K.; Nandi, D. Oppositional elephant herding optimization with dynamic Cauchy mutation for multilevel image thresholding. Evol. Intell. 2019,12, 445–467. [CrossRef] 43. Fogarty, T.C. Varying the Probability of Mutation in the Genetic Algorithm. In Proceedings of the 3rd International Conference on Genetic Algorithms, Fairfax, VA, USA, 4–7 June 1989; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 1989; pp. 104–109. 44. Lin, W.Y.; Lee, W.Y.; Hong, T.P. Adapting Crossover and Mutation Rates in Genetic Algorithms. J. Inf. Sci. Eng. 2003 ,19, 889–903. 45. Van Laarhoven, P.J.; Aarts, E.H. Simulated annealing. In Simulated Annealing: Theory and Applications; Springer: Berlin/Heidelberg, Germany, 1987; pp. 7–15. 46. Meng, A.b.; Chen, Y.c.; Yin, H.; Chen, S.Z. Crisscross optimization algorithm and its application. Knowl. Based Syst. 2014 , 67, 218–229. [CrossRef] 47. Arora, S.; Singh, S. Butterfly optimization algorithm: A novel approach for global optimization. Soft Comput. 2019 ,23, 715–734. [CrossRef] 48. Zhang, M.; Long, D.; Qin, T.; Yang, J. A chaotic hybrid butterfly optimization algorithm with particle swarm optimization for high-dimensional optimization problems. Symmetry 2020,12, 1800. [CrossRef] 49. Wang, G.G.; Gandomi, A.H.; Zhao, X.; Chu, H.C.E. Hybridizing harmony search algorithm with cuckoo search for global numerical optimization. Soft Comput. 2016,20, 273–285. [CrossRef] 50. Pan, J.S.; Zhuang, J.; Liao, L.; Chu, S.C. Advanced equilibrium optimizer for electric vehicle routing problem with time windows. J. Netw. Intell. 2021,6, 216–237.