基于改进甲虫搜索算法的城市无人机路径规划

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

系统仿真学报 ›› 2023, Vol. 35 ›› Issue (12): 2527-2536.doi: 10.16182/j.issn1004731x.joss.22-0778

基于改进甲虫搜索算法的城市无人机路径规划

杨青青¹^,²(), 邓敏仪¹^,², 彭艺¹^,²()

^1.昆明理工大学信息工程与自动化学院，云南昆明 650500
^2.昆明理工大学云南省计算机重点实验室，云南昆明 650500

收稿日期:2022-07-04 修回日期:2022-09-08 出版日期:2023-12-15 发布日期:2023-12-12
通讯作者: 彭艺 E-mail:1016188826@qq.com;2530349532@qq.com
第一作者简介:杨青青(1981-)，女，讲师，博士，研究方向为无人机路径规划、智能反射面辅助通信。E-mail：1016188826@qq.com
基金资助:
国家自然科学基金(61761025)

Urban UAV Path Planning Based on Improved Beetle Search Algorithm

Yang Qingqing¹^,²(), Deng Minyi¹^,², Peng Yi¹^,²()

^1.School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
^2.Yunnan Provincial Key Laboratory of Computer Science, Kunming University of Science and Technology, Kunming 650500, China

Received:2022-07-04 Revised:2022-09-08 Online:2023-12-15 Published:2023-12-12
Contact: Peng Yi E-mail:1016188826@qq.com;2530349532@qq.com

摘要/Abstract

摘要：

为提高无人机在城市多障碍物环境下执行任务时的安全性和路径平滑度，并获得最短路径，提出一种改进退火甲虫搜索算法。该算法在探索路径进行位置更新时不再完全依赖于甲虫左右触须的气味浓度差，而是在充分利用甲虫搜索算法较强的搜索能力的基础上，通过引入退火算法增加下一位置的邻域位置解，最终在邻域位置解中筛选得到下一步最佳位置。由退火算法的Metropolis准则对以上得到的最佳位置进行是否可以移动的判断，克服了经典甲虫搜索算法易陷入局部最优解的缺点。仿真结果表明：在城市多障碍物环境下，该算法在收敛速度和生成路径的安全性、平滑度和路径长度方面都优于甲虫搜索算法和蚁群算法。在当前多障碍物城市场景下，当初始步长和步长因子分别为16 m和0.99时，规划的路径最优。

关键词: 无人机, 路径规划, 退火甲虫搜索算法, 城市环境, 最优路径

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

中图分类号:

TP391.9

杨青青,邓敏仪,彭艺 . 基于改进甲虫搜索算法的城市无人机路径规划[J]. 系统仿真学报, 2023, 35(12): 2527-2536.

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.

图/表 12

图1

表1

参数设置

参数	数值
最远路径长度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

表1

表2

图2

图3

图4

图5

表3

表4

表5

表6

初始步长对路径规划结果的影响

初始步长 $δ 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

表6

表7

步长因子对路径规划结果的影响

步长因子 $α$	路径长度/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

表7

参考文献 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]	陈德峻, 方子豪, 曾云秀, 许凯. 战场迷雾中的欺骗路径规划[J]. 系统仿真学报, 2023, 35(9): 1895-1908.
[2]	焦嵩鸣, 首云锋, 白健鹏, 王祝. 变电站巡检无人机分层运动规划方法研究[J]. 系统仿真学报, 2023, 35(9): 1975-1984.
[3]	李文静, 骆岩林, 王玉辉, 朱丽. 基于八叉树势场的鼻内镜虚拟导航路径规划[J]. 系统仿真学报, 2023, 35(9): 2054-2063.
[4]	林俊强, 王红军, 邹湘军, 张坡, 李承恩, 周益鹏, 姚书杰. 基于DPPO的移动采摘机器人避障路径规划及仿真[J]. 系统仿真学报, 2023, 35(8): 1692-1704.
[5]	杨来义, 毕敬, 苑海涛. 基于SAC算法的移动机器人智能路径规划[J]. 系统仿真学报, 2023, 35(8): 1726-1736.
[6]	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
[7]	杨海兰, 祁永强, 吴保磊, 荣丹, 洪妙英, 王军. 动态环境下基于忆阻强化学习的移动机器人路径规划[J]. 系统仿真学报, 2023, 35(7): 1619-1633.
[8]	牛双诚, 晋玉强, 寇昆湖. 基于区块链的多无人机协同任务分配方法研究[J]. 系统仿真学报, 2023, 35(5): 949-956.
[9]	宋大雷, 干文浩, 许嘤枝, 曲秀青, 曹江丽. 无人船实时路径规划与编队控制仿真研究[J]. 系统仿真学报, 2023, 35(5): 957-970.
[10]	付玉, 张垚, 赵萌, 王绵沼, 郑江鹏, 贾晨, 陈胜勇. 基于仿真数据迁移学习的固定翼无人机检测[J]. 系统仿真学报, 2023, 35(5): 998-1007.
[11]	吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.
[12]	赵拓, 邓汉强, 高佳隆, 黄健. 基于网络节点聚类的多无人机动态目标分配[J]. 系统仿真学报, 2023, 35(4): 695-708.
[13]	薛均晓, 孔祥燕, 董博威, 陶浩, 管海洋, 石磊, 徐明亮. 航母甲板上舰载机的混合避障和仿真[J]. 系统仿真学报, 2023, 35(3): 592-603.
[14]	张国辉, 王璇, 张雅楠, 高昂. 实际环境中多无人车协同路径规划模型研究[J]. 系统仿真学报, 2023, 35(2): 408-422.
[15]	杜梦瑶, 许凯, 张淼, 傅翔, 尹全军. 基于区块链的无人机群可靠应急搜救模型[J]. 系统仿真学报, 2023, 35(12): 2537-2549.

基于改进甲虫搜索算法的城市无人机路径规划

Urban UAV Path Planning Based on Improved Beetle Search Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价

项目	SABAS	BAS	ACO
路径长度/m	1 438	1 451	1 454
路径点数	238	247	249

项目	BAS	ACO
少障碍物环境	13	16
多障碍物环境	35	29

项目	BAS	ACO
少障碍物环境	6	8
多障碍物环境	16	12