Urban UAV Path Planning Based on Improved Beetle Search Algorithm

doi:10.16182/j.issn1004731x.joss.22-0778

Abstract

Abstract:

An improved SABAS is proposed to improve the safety and path smoothing of UAV missions in urban multi-obstacle environments and to obtain the shortest path. The algorithm no longer completely depends on the difference of odor concentration between the left and the right tentacles of beetle when exploring the path for position update. Instead, it makes full use of the strong searching ability of BAS algorithm, and introduces the annealing algorithm to add the neighborhood position solution of the next position, and finally selects the next best position from the neighborhood position solution. Metropolis criterion of annealing algorithm is used to judge whether the obtained best position is mobile or not, which overcomes the shortcoming of classical BAS being easy to fall into local optimal solution. Simulation results show that SABAS is superior to BAS and ACO convergence speed, safety, smoothness and the length of the path in urban multi-obstacle environment. It can be concluded that the planned path is optimal when the initial step size and step size factor are 16 m and 0.99 respectively in the current multi-obstacle city scenario.

Key words: UAV, path planning, annealing beetle search algorithm, urban environment, the optimal path

CLC Number:

TP391.9

Yang Qingqing, Deng Minyi, Peng Yi. Urban UAV Path Planning Based on Improved Beetle Search Algorithm[J]. Journal of System Simulation, 2023, 35(12): 2527-2536.

Figures/Tables 12

Fig. 1

Table 1

Parameter Settings

参数	数值
最远路径长度L_max/m	3 000
最大转弯角 $β m a x$ /rad	$π / 2$
最大飞行高度H_max/m	120
最小飞行高度H_min/m	20
最小安全距离d_min/m	10
起始点 $x 0$ 坐标/m	(0, 0, 30)
最大俯仰角 $μ m a x$ /rad	$π / 2$
初始步长/m	16
步长因子 $δ 0$	0.99
终点 $x T$ 坐标 $/ m$	(1 000, 1 000, 50)
危险度代价权重 $c 1$	0.4
高度代价权重 $c 2$	0.3
航程代价权重 $c 3$	0.3
与终点距离代价权重 $c 4$	0.3

Table 1

Table 2

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 3

Table 4

Table 5

Table 6

Influence of initial step size on path planning results

初始步长 $δ 0$ /m	路径长度/m	路径点数
≤14	<1 451	>>1 000 000
15	1 451	376
16	1 456	251
17	1 475	209
20	1 497	141

Table 6

Table 7

Influence of step size factor on path planning result

步长因子 $α$	路径长度/m	路径点数
<0.990	<1 456	>>1 000 000
0.990	1 456	251
0.991	1 468	199
0.992	1 476	170
0.993	1 479	151
0.994	1 483	137
0.995	1 487	126
0.999	1 503	99

Table 7

References 20

1	Hayat S, Yanmaz Evşen, Brown T X, et al. Multi-objective UAV Path Planning for Search and Rescue[C]//2017 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2017: 5569-5574.
2	Tu Guanting, Juang J G. Path Planning and Obstacle Avoidance Based on Reinforcement Learning for UAV Application[C]//2021 International Conference on System Science and Engineering (ICSSE). Piscataway, NJ, USA: IEEE, 2021: 352-355.
3	Causa F, Fasano G. Navigation-aware Path Planning for Multiple UAVs in Urban Environment[C]//2020 AIAA/IEEE 39th Digital Avionics Systems Conference (DASC). Piscataway, NJ, USA: IEEE, 2020: 1-10.
4	Zheng Kexin, Liu Xiaobo, Yang Jianfeng, et al. BRR-DQN: UAV Path Planning Method for Urban Remote Sensing Images[C]//2021 China Automation Congress (CAC). Piscataway, NJ, USA: IEEE, 2021: 6113-6117.
5	Ren Qian, Yao Yuan, Yang Gang, et al. Multi-objective Path Planning for UAV in the Urban Environment Based on CDNSGA-II[C]//2019 IEEE International Conference on Service-oriented System Engineering (SOSE). Piscataway, NJ, USA: IEEE, 2019: 350-3505.
6	Wu Yu, Wu Shaobo, Hu Xinting. Cooperative Path Planning of UAVs & UGVs for a Persistent Surveillance Task in Urban Environments[J]. IEEE Internet of Things Journal, 2021, 8(6): 4906-4919.
7	Ghambari S, Golabi M, Lepagnot J, et al. An Enhanced NSGA-II for Multiobjective UAV Path Planning in Urban Environments[C]//2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI). Piscataway, NJ, USA: IEEE, 2020: 106-111.
8	Causa F, Fasano G. Safe Planning and Deconfliction for Multiple UAVs in High Density Low Altitude Urban Environments[C]//2021 IEEE/AIAA 40th Digital Avionics Systems Conference (DASC). Piscataway, NJ, USA: IEEE, 2021: 1-10.
9	Ortlieb M, Adolf F M. Rule-based Path Planning for Unmanned Aerial Vehicles in Non-segregated Air Space Over Congested Areas[C]//2020 AIAA/IEEE 39th Digital Avionics Systems Conference (DASC). Piscataway, NJ, USA: IEEE, 2020: 1-9.
10	张洪海, 张连东, 刘皞, 等. 城市低空物流无人机航迹规划模型研究[J]. 交通运输系统工程与信息, 2022, 22(1): 256-264.
	Zhang Honghai, Zhang Liandong, Liu Hao, et al. Track Planning Model for Logistics Unmanned Aerial Vehicle in Urban Low-altitude Airspace[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 256-264.
11	李若恒, 邵荃, 董敏. 基于风险管控的城市空中交通无人机路径规划[J]. 航空计算技术, 2021, 51(2): 73-77.
	Li Ruoheng, Shao Quan, Dong Min. Path Planning for UAV in Urban Air Mobility Based on Risk Management[J]. Aeronautical Computing Technique, 2021, 51(2): 73-77.
12	Cheng Long, Yu Muzhou, Yang Junfeng, et al. An Improved Artificial Bee Colony Algorithm Based on Beetle Antennae Search[C]//2019 Chinese Control Conference (CCC). Piscataway, NJ, USA: IEEE, 2019: 2312-2316.
13	Song Jia, Sun Mingming. The High-speed Rotorcraft UAV Trajectory Planning Based on the Beetle Antennae Search Optimization Algorithm[C]//2020 39th Chinese Control Conference (CCC). Piscataway, NJ, USA: IEEE, 2020: 6833-6838.
14	Zhang Bin, Duan Yiqin, Zhang Yi, et al. Particle Swarm Optimization Algorithm Based on Beetle Antennae Search Algorithm to Solve Path Planning Problem[C]//2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). Piscataway, NJ, USA: IEEE, 2020: 1586-1589.
15	Wang Xiaorui, Chen Dongdong. Link Design for Wireless Optical Communication Network Based on Ant Colony Algorithm[J]. Journal of Communications and Networks, 2022, 24(2): 184-191.
16	Jiang Xuemei, Song Yanjie, Xing Lining. Dual-population Artificial Bee Colony Algorithm for Joint Observation Satellite Mission Planning Problem[J]. IEEE Access, 2022, 10: 28911-28921.
17	Phung M D, Ha Q P. Safety-enhanced UAV Path Planning With Spherical Vector-based Particle Swarm Optimization[J]. Applied Soft Computing, 2021, 107: 107376.
18	Elgamal Z, Aznul Qalid Md Sabri, Tubishat M, et al. Improved Reptile Search Optimization Algorithm Using Chaotic Map and Simulated Annealing for Feature Selection in Medical Field[J]. IEEE Access, 2022, 10: 51428-51446.
19	Jiang Xiangyuan, Li Shuai. BAS: Beetle Antennae Search Algorithm for Optimization Problems[J]. International Journal of Robotics and Control, 2018, 1(1): 1-5.
20	Wu Qing, Shen Xudong, Jin Yuanzhe, et al. Intelligent Beetle Antennae Search for UAV Sensing and Avoidance of Obstacles[J]. Sensors, 2019, 19(8): 1758.

[1]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Qu Changhong, Wang Junjie, Wang Kun, Cui Qingyong, Chen Jiangyang, Wang Xinpeng. A Modeling and Simulation Method for Firepower Intelligent Decision-making of Directed Energy System Based on Joint DQN [J]. Journal of System Simulation, 2025, 37(5): 1256-1265.
[8]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[9]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[10]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[11]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[12]	Yang Chao, Zheng Ruiqun, Li Zhen, Zhang Hongwei, Tang Yanqun, Li Dongze. Parallel Task Transmission and Processing Optimization Scheme for UAV-assisted Internet of Vehicles [J]. Journal of System Simulation, 2025, 37(3): 635-645.
[13]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[14]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[15]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.