Adaptive Budgerigar Optimization-based Obstacle Avoidance Path Planning for Unmanned Aerial Vehicle

Authors: zhiqiang  li
jingyu  liu
mengji  shi
boxian  lin
meng  li
kaiyu  qin
Venue: IEEE_org_ICIST_2024_Conference
Published: 2024-08-15 08:56:54

Abstract: This paper addresses the path planning problem of Unmanned Aerial Vehicle (UAV) operating in a three-dimensional environment populated with obstacles. An enhanced Adaptive Budgerigar Optimization (ABO) algorithm is designed to navigate the UAV efficiently, ensuring collision avoidance while maintaining high solution accuracy. The primary innovation of our approach involves modifying the iteration update formula of the original Parrot Optimization algorithm by incorporating an adaptive adjustment factor. This factor dynamically regulates the convergence rate and accuracy, thereby enabling the algorithm to escape local optima and achieve globally optimal paths effectively. Through comprehensive simulation experiments, we compare the performance of the ABO algorithm against traditional Particle Swarm Optimization (PSO) and the original Budgerigar Optimization algorithm. The results demonstrate the superior convergence speed and solution quality of the proposed algorithm, thereby validating its effectiveness and feasibility.

Main paper: 
 introduction: 
 In recent years, the continuous advancements in robotic automation technologies, including visual perception, path planning, and intelligent control, have led to the widespread adoption of Unmanned Aerial Vehicles (UAVs) across various fields. This is largely attributed to their compact size, cost-effectiveness, high mobility, and enhanced safety features. Among the key technologies enabling UAV autonomy and intelligence, path planning has emerged as a primary research focus [1] [2] [3] . Path planning for UAVs involves designing an optimal flight path that adheres to specific UAV and terrain constraints while avoiding obstacles, no-fly zones, and potential threats along the route. The efficiency and safety of UAV mission execution are directly influenced by the effectiveness of path planning. By optimizing the flight path, UAVs can achieve mission objectives in the shortest possible time, thereby enhancing overall operational efficiency.Path planning methods are generally classified into three categories: traditional path planning algorithms, artificial intelligence algorithms, and swarm intelligence optimization algorithms. Traditional path planning algorithms [4] include methods such as the Artificial Potential Field (APF) algorithm [5] and the A* algorithm [6] . Artificial intelligence algorithms [7] [8] [9] primarily utilize techniques like neural networks, reinforcement learning, and other machine learning methods to address the UAV path planning problem. Swarm intelligence optimization algorithms [10] encompass approaches such as the Ant Colony Algorithm [11] [12] , Genetic Algorithm [13] [14] , and Particle Swarm Optimization (PSO) [15] [16] [17] . Unlike traditional path planning algorithms, which often suffer from high computational demands, limited applicability, and a propensity to converge to local optima, swarm intelligence algorithms are capable of global search, enabling the identification of optimal paths more effectively. Consequently, swarm intelligence algorithms are widely employed in UAV path planning.However, it is important to note that current swarm intelligence algorithms still face several challenges, including limited optimization capabilities and high computational resource consumption. Additionally, many path planning algorithms are tested in overly simplified scenarios, which may not adequately demonstrate their feasibility in more complex environments. To address these issues, researchers have developed the Parrot Optimization (PO) algorithm [18] . While this algorithm exhibits strong optimization performance, it continues to suffer from problems such as convergence to local optima and significant computational resource demands.Based on the above analysis, this article conducted indepth research on UAV path planning under obstacle constraints. The main innovative points are summarized as follows:(1) A novel path planning scheme based on the Adaptive Budgerigar Optimization (ABO) algorithm is designed. This scheme enables effective obstacle avoidance in a threedimensional environment while maintaining high solution accuracy. The UAV navigation efficiency and safety in complex environments are enhanced.(2) The traditional PO algorithm in [18] is improved by introducing a unique adaptive adjustment factor. This factor dynamically regulates the convergence rate and accuracy, allowing for more effective escape from local optima and achievement of globally optimal paths. The enhanced algorithm demonstrates superior convergence speed and solution quality compared to the PO algorithm, particularly in scenarios requiring high-precision path planning.The remainder of this paper is structured as follows: Section 2 presents the modeling of the UAV path planning problem in a three-dimensional environment. Section 3 introduces the ABO algorithm. Section 4 compares the proposed algorithm with the traditional PO and PSO algorithm, demonstrating its superiority and determining the optimal parameters through comparative experiments. Finally, Section 5 concludes the paper with a summary of the key findings.This section models the UAV mission planning problem and outlines the construction of randomly generated threedimensional (3D) maps. Additionally, it details the flight range constraints and terrain limitations [19] that the UAV must adhere to during the path planning process.In this paper, we address the UAV path planning problem within a mountainous environment. To enhance the randomness and demonstrate the adaptability of the algorithm, the centers of the peaks are generated randomly. The heights of the mountains in this environment are modeled using an exponential function, and the corresponding mathematical model is represented as follows:EQUATIONwhere parameter n represents the number of peaks; a x and a y are the center coordinates of the th a peak; a h is a geographic parameter, which controls the height degree; sa x and sa y are the th a peak's attenuation along the x-axis and y- axis directions, which control the slope of the peaks. The environment model is shown in Figure 1 . The flight path of a UAV is characterized by an ordered set of point coordinates, each interconnected spatial coordinate point is associated using a cubic B-spline smoothing curve. Assume that the set of sequence points of the UAV path is   EQUATIONThe constraints are designed to ensure the planning of feasible flight paths. In the context of single UAV path planning, two primary constraints are introduced: terrain and environment.Firstly, to prevent terrain collision during UAV flight, the flight altitude of UAV must consistently exceed the terrain altitude. Accordingly, the terrain constraints are formulated as follows:( , ); 1, 2, , ,EQUATIONwhere ( , ) aa Z x y is a terrain function, which can represent the height of the terrain at the position ( , ) a a xy.Secondly, to optimize path planning and minimize costs during UAV flight, the UAV is restricted to operate within a designated area. The environmental constraints are therefore defined as follows: EQUATIONFor the flyable path, the UAV's voyage obstacles, and boundary constraints must be collectively considered, enabling the generalization of the UAV's integrated cost function as follows:EQUATIONwhere C V represents voyage cost; C T represents terrain cost; and C B represents boundary cost.V essentially takes into account the distance flown by the UAV which is directly proportional to the distance D. It can be expressed as the total distance of the UAV from the starting point to the target point. If the total trajectory is composed of n waypoints, the voyage cost can be represented asEQUATIONThe terrain cost c V primarily accounts for the threat posed by mountain peaks along the UAV's flight path. The presence of this terrain cost significantly increases the expense of traversing mountainous obstacles, thereby optimizing the UAV's path to avoid such obstacles. It is expressed by the following mathematical formula: EQUATION- =            =  = =     (6)where the parameter P represents the penalty for collisions with obstacles.B is primarily considered to ensure that the UAV operates within the designated spatial region during the flight, and is expressed as follows: EQUATIONSimilarly, the parameter P represents the penalty for increasing the cost if the UAV exceeds its flight range.Similar to other swarm intelligence optimization algorithms, the ABO algorithm is inspired by the natural behaviors of budgerigars. Previous studies have identified four distinct behavioral traits in budgerigars: searching, staying, communicating, and escaping. These behaviors serve as the foundational inspiration for the design of the ABO algorithm.During searching behavior in ABO, the budgerigars determine the approximate location of the food by observation, and then fly towards the estimated location. The population of budgerigar is assumed to be N and the maximum number of iterations of the algorithm is iter , the behavior can be described by the following equation:( EQUATIONIn the equation ( 8), t i P represents the current position, (0,1) rand represents a random number generated from 0 and 1.() Levy n represents Levy flight strategy, where n represents the number of intermediate points selected throughout the path planning process. t denotes the number of iterations so far.For the parameter  in equation ( 8), is a dependency coefficient. The dependency coefficient is used to regulate the degree of dependency of an individual on the global search. By adjusting the size of the dependency factor, we can change the search weights of individuals globally and locally, which in turn gives better results.The average position of all individuals can be calculated using the following equation：EQUATIONThe Levy flight strategy can be represented by the following equation: (EQUATIONThe budgerigar is highly social, it may randomly explore a certain location and stay there for a while based on existing experience, therefore, its behavior can be expressed by the following equation: As a natural social animal, budgerigar's behavior is inextricably linked to communication in a group. There are two types of budgerigar communication: flying back into the group and communicating with a single companion. We assume in the ABO algorithm that the two modes of communication have the same probability of occurring and consider the average position of all individuals in the population t mean P to be the center of the population, we can express these two modes in the following two equation: EQUATION +    -  -    =     -      (12)where k in the equation is a random number from 0 to 1, which is used to randomly select which communication behavior occurs. 0. 9), represents the dependency coefficient, which can be adjusted artificially.As a bird, Budgerigars has a natural fear of unfamiliar environments. When budgerigar is confronted with sudden dangers and situations, it will actively engage in evasion and return to a position it is familiar with and safe. Based on this behavior, we get the following equation: EQUATIONwhere (0,1) (0.5 ) ( ) tThe optimization formula presented above is derived from the four behavioral traits of budgerigars. In the ABO algorithm, the behavior that an individual performs is determined by an identifier, known as the flag, which takes a positive integer value between 1 and 4, with each value having an equal probability of occurrence. Unlike traditional meta-heuristic algorithms, the ABO algorithm does not differentiate between the exploration and exploitation phases. Instead, individuals randomly select one of the four behaviors, resulting in a straightforward algorithm with strong optimization capabilities.The path planning process for the UAV using the ABO algorithm can be outlined in the following steps. First, the algorithm begins with the initialization of parameters, where the values of the hyperparameters are input. Next, the positions of the population are initialized, and the current value of the fitness function is calculated. Subsequently, the four behaviors of budgerigars are employed to update the positions, with the selection of behaviors determined by the random parameter flag. These behaviors optimize an individual's position by utilizing information such as the current optimal position and the average position of the population. The optimization process continues iteratively until the predefined stopping conditions are satisfied. The specific flowchart of the ABO algorithm is presented below: In this part, we aim to demonstrate that the ABO algorithm is suitable for solving the UAV path planning problem. To achieve this, task scenarios are randomly generated to validate the algorithm's generalization capability. Additionally, the optimization performance of the ABO algorithm is assessed through comparative experiments with the PSO algorithm.Simulation parameter settings: the number of intermediate points is three, the number of populations is set to 200, the number of iterations is set to 100, the coordinates of the starting point is [1,1,1], the coordinates of the target point is [85,80,40], and the three-dimensional coordinates are limited to [100,100,100]. The values of the adaptive parameters  and  are both chosen to be 1. The number of peaks n is taken to be 25.In the environment of MATLAB 2022a, based on the ABO and PSO algorithm for UAV path planning we can get the following results: 3 illustrates the UAV path planning results obtained using the ABO algorithm, while Figure 4 presents the results generated by the traditional PSO algorithm. Figure 5 displays the convergence curves for both the ABO and PSO algorithms, where the theoretical optimum represents the straight-line distance between the starting point and the target point. The simulation experimental results demonstrate that the ABO algorithm is a viable solution for the UAV path planning problem. Furthermore, the convergence curves in Figure 5 indicate that the optimization performance of the ABO algorithm surpasses that of the traditional PSO algorithm.The previous simulation results have demonstrated the feasibility of the ABO algorithm in solving the UAV path planning problem. The next step involves conducting multiple sets of comparison experiments to determine the optimal adaptive parameters. Given that the maps used earlier were randomized, different trials could produce varying maps, potentially impacting the accuracy of the results. To address this, a fixed map will be used in the subsequent experiments to ensure consistency and accuracy. 6 is the case  =  =1; the green curve is the case  =1,  =2; the pink curve is the case  =2,  =1 and the yellow curve is the case  =  =2. From the results, we can see that with enough iterations, it is still the case of  =  =1 that is optimized optimal.V. CONCLUSION This paper has addressed the UAV path planning problem in three-dimensional environments with obstacles. An enhanced ABO algorithm, which efficiently navigates the UAV while ensuring collision avoidance and high solution accuracy is proposed. By incorporating an adaptive adjustment factor into the iteration update formula, the algorithm effectively escapes local optima and achieves globally optimal paths. Simulation results demonstrated the ABO al orith 's superior co ver e ce speed a d solutio quality compared to traditional methods, validating its effectiveness. Future research will focus on multi-UAV cooperative path planning to further optimize coordination and efficiency. 
 
 Appendix:  



Reviews: review: title: title: Accept
main_review: main_review: The paper proposes an innovative enhancement to the Budgerigar Optimization algorithm, introducing an adaptive adjustment factor to tackle the complex path planning problem for UAVs in 3D environments with obstacles. This work is significant as it aims to improve the efficiency and accuracy of path planning algorithms.However,there are some suggestions :
1.Comparing ABO against a wider range of optimization algorithms, especially those specifically designed for path planning, would provide a more comprehensive evaluation.
2.Improve the clarity and conciseness of the writing, particularly in the introduction and related work sections.
3.It is better to  discuss the impact of parameter settings.
title: title: This manuscript has a certain degree of innovation and clear simulation figures. It is recommended to accept this paper for publication in IEEE ICIST 2024.
main_review: main_review: This paper addresses the path planning problem of Unmanned Aerial Vehicle (UAV) operating in a three dimensional environment populated with obstacles. This manuscript has a certain degree of innovation and clear simulation figures. It is recommended to accept this paper for publication in IEEE ICIST 2024. However, the following suggestions need careful consideration to further improve the quality of the paper：
1.The ABO algorithm has demonstrated its effectiveness in single-UAV path planning. To further enhance its practical applicability, extending the algorithm to support multi-UAV cooperative path planning would be highly valuable. By incorporating mechanisms for coordinating and optimizing the paths of multiple UAVs simultaneously, the proposed approach could achieve even higher operational efficiency and robustness in real-world missions involving teams of UAVs.
2.While the ABO algorithm effectively navigates UAVs around static obstacles, integrating real-time obstacle detection capabilities using sensors such as LiDAR, RADAR, or cameras could significantly enhance the system's adaptability to dynamic environments. This would allow the UAVs to respond to unforeseen obstacles encountered during flight, thereby improving overall safety and reliability.
3.The current ABO algorithm focuses on minimizing the overall path length and avoiding obstacles. To further optimize the performance of UAVs, incorporating energy-aware path planning into the algorithm would be beneficial. By considering factors like altitude, speed, and wind conditions into the cost function, the algorithm could generate paths that minimize energy consumption, extending the operational range and endurance of UAVs in real-world missions.
title: title: The paper is logically clear, the simulation results are credible, and it is recommended for publication.
main_review: main_review: This paper presents a noteworthy contribution to the field of UAV path planning by introducing an enhanced Adaptive Budgerigar Optimization (ABO) algorithm tailored for navigating three-dimensional environments with obstacles. The core innovation lies in the modification of the iteration update formula from the original Parrot Optimization algorithm, incorporating an adaptive adjustment factor that dynamically controls convergence rate and accuracy. This strategic adjustment significantly improves the algorithm's ability to escape local optima and find globally optimal paths. The reviewer has the following questions to discuss with the authors:

1. How does the adaptive adjustment factor in the ABO algorithm specifically regulate the convergence rate and accuracy? What criteria are used to determine when and how the factor is adjusted during the optimization process?

2. The paper mentions that ABO outperforms traditional Particle Swarm Optimization (PSO) in convergence speed and solution quality. What are the key differences in the performance of these algorithms, and are there particular situations where PSO might still be preferable?

3. How does the computational complexity of the ABO algorithm compare to that of the original Budgerigar Optimization and PSO algorithms? Is the improved performance achieved at the cost of higher computational demands?