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]	Chen Dejun, Fang Zihao, Zeng Yunxiu, Xu Kai. Deceptive Path Planning in Fog of War [J]. Journal of System Simulation, 2023, 35(9): 1895-1908.
[2]	Jiao Songming, Shou Yunfeng, Bai Jianpeng, Wang Zhu. Research on Hierarchical Motion Planning Method for UAV Substation Inspection [J]. Journal of System Simulation, 2023, 35(9): 1975-1984.
[3]	Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope [J]. Journal of System Simulation, 2023, 35(9): 2054-2063.
[4]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[5]	Laiyi Yang, Jing Bi, Haitao Yuan. Intelligent Path Planning for Mobile Robots Based on SAC Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1726-1736.
[6]	Menglong Cao, Wenbin Zhao, Zhiqiang Chen. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
[7]	Hailan Yang, Yongqiang Qi, Baolei Wu, Dan Rong, Miaoying Hong, Jun Wang. Path Planning of Mobile Robots Based on Memristor Reinforcement Learning in Dynamic Environment [J]. Journal of System Simulation, 2023, 35(7): 1619-1633.
[8]	Shuangcheng Niu, Yuqiang Jin, Kunhu Kou. Research on Collaborative Task Allocation Method of Multiple UAVs Based on Blockchain [J]. Journal of System Simulation, 2023, 35(5): 949-956.
[9]	Dalei Song, Wenhao Gan, Yingzhi Xu, Xiuqing Qu, Jiangli Cao. Simulation of Real-Time Path Planning and Formation Control for Unmanned Surface Vessel [J]. Journal of System Simulation, 2023, 35(5): 957-970.
[10]	Yu Fu, Yao Zhang, Meng Zhao, Mianzhao Wang, Jiangpeng Zheng, Chen Jia, Shengyong Chen. Fixed-Wing UAV Detection Based on Simulated Data Transfer Learning [J]. Journal of System Simulation, 2023, 35(5): 998-1007.
[11]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[12]	Tuo Zhao, Hanqiang Deng, Jialong Gao, Jian Huang. Dynamic Target Assignment of Multiple Unmanned Aerial Vehicles Based on Clustering of Network Nodes [J]. Journal of System Simulation, 2023, 35(4): 695-708.
[13]	Junxiao Xue, Xiangyan Kong, Bowei Dong, Hao Tao, Haiyang Guan, Lei Shi, Mingliang Xu. Obstacle Avoidance and Simulation of Carrier-Based Aircraft on the Deck of Aircraft Carrier [J]. Journal of System Simulation, 2023, 35(3): 592-603.
[14]	Guohui Zhang, Xuan Wang, Yanan Zhang, Ang Gao. Research on Cooperative Path Planning Model of Multiple Unmanned Vehicles in Real Environment [J]. Journal of System Simulation, 2023, 35(2): 408-422.
[15]	Du Mengyao, Xu Kai, Zhang Miao, Fu Xiang, Yin Quanjun. Reliable Emergency Rescue Model of UAVs Based on Blockchain [J]. Journal of System Simulation, 2023, 35(12): 2537-2549.