面向超低空物流场景的多机协同航迹规划算法

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

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (1): 50-66.doi: 10.16182/j.issn1004731x.joss.22-1028

面向超低空物流场景的多机协同航迹规划算法

程洁¹(), 郑远²(), 李诚龙¹^,³, 江波¹

^1.中国民用航空飞行学院空中交通管理学院, 四川广汉 618307
^2.中国民用航空飞行学院计算机学院, 四川广汉 618307
^3.北京航空航天大学电子信息工程学院, 北京 100191

收稿日期:2022-08-31 修回日期:2022-10-14 出版日期:2024-01-20 发布日期:2024-01-19
通讯作者: 郑远 E-mail:jiecheng@cafuc.edu.cn;ranchozy@cafuc.edu.cn
第一作者简介:程洁(1997-)，女，硕士生，研究方向为无人机城市空中交通管理。E-mail：jiecheng@cafuc.edu.cn
基金资助:
中央高校基本科研业务费重点项目(ZJ2021-03);民航教育人才类项目(MHJY2022032);民航飞行技术与飞行安全重点实验室开放基金(FZ2021KF13)

Multi-UAV Collaborative Trajectory Planning Algorithm for Urban Ultra-low-altitude Air Transportation Scenario

Cheng Jie¹(), Zheng Yuan²(), Li Chenglong¹^,³, Jiang Bo¹

^1.College of Air Traffic Management, Civil Aviation Flight University of China, Guanghan 618307, China
^2.College of Computer Science and Technology, Civil Aviation Flight University of China, Guanghan 618307, China
^3.School of Electronic Information Engineering, Beihang University, Beijing 100191, China

Received:2022-08-31 Revised:2022-10-14 Online:2024-01-20 Published:2024-01-19
Contact: Zheng Yuan E-mail:jiecheng@cafuc.edu.cn;ranchozy@cafuc.edu.cn

摘要/Abstract

摘要：

无人机产业的迅猛发展促进了低空开放，形成了国内外城市超低空物流运输的浪潮，然而，现有的航迹规划算法没有考虑空域的划分方式与运行规则，不适用于城市超低空物流场景下多无人机的协同航迹规划，桎梏了超低空物流行业的发展。针对该问题，从实际需求出发，在空域高度层架构的基础上探索适用于城市超低空物流场景的多无人机协同航迹规划方法。将原问题分解为无人机-高度层任务分配与多无人机单高度层协同航迹规划两个相互耦合的子问题，并分别运用基于知识图谱的任务分配解法与基于粒子群算法的改进人工势场法对两个子问题进行求解。仿真实验表明，该方法在求解单高度层协同航迹规划子问题中不但能够避免传统方法的固有缺陷，平均迭代次数相较于对比方法也减少了62.09%；同时，仿真结果也表明所提方法可以快速鲁棒的解决原问题，为城市超低空物流场景提供了切实可行的多机航迹规划方法。

关键词: 航迹规划, 任务分配, 多无人机, 知识图谱, 人工势场, 粒子群算法

Abstract:

The rapid development of the drone industry has promoted the opening of low-altitude, forming a wave of ultra-low-altitude air transportation in cities sweeping over the world. However, the existing trajectory planning algorithms do not consider the division method and operating rules of the ultra-low-altitude airspace. They are not suitable for the collaborative trajectory planning of multiple UAVs in the urban ultra-low-altitude air transportation scenario, which may restrict the development of the ultra-low-altitude air transportation industry. This paper explores a multi-UAV collaborative trajectory planning method for urban ultra-low-altitude air transportation scenario based on the airspace flight altitude layer architecture. Specifically, the paper decomposes the original problem into two coupled sub-problems: UAV flight altitude layer task assignment and multi-UAV single-altitude coordinated trajectory planning. It uses the task assignment solution based on mapping knowledge domains and the swarm-based improved artificial potential field method to solve these two sub-problems respectively. Simulation results show that the method can not only avoid the inherent defects of traditional methods in solving the cooperative trajectory planning sub-problem but also reduce the average number of iterations by 62.09% compared with the traditional method. At the same time, the simulation results also show that the proposed method solves the original problem fast and robustly, which can provide a feasible trajectory for multi-UAVs in urban ultra-low-altitude air transportation scenario.

Key words: trajectory planning, task assignment, multi-UAVs, mapping knowledge domains, artificial potential field, particle swarm algorithm

中图分类号:

TP391.9

程洁,郑远,李诚龙等 . 面向超低空物流场景的多机协同航迹规划算法[J]. 系统仿真学报, 2024, 36(1): 50-66.

Cheng Jie,Zheng Yuan,Li Chenglong,et al . Multi-UAV Collaborative Trajectory Planning Algorithm for Urban Ultra-low-altitude Air Transportation Scenario[J]. Journal of System Simulation, 2024, 36(1): 50-66.

图/表 17

图1

图2

图3

图4

图5

图6

表 1

算法参数

参数	数值	意义
p	40	粒子种群数
Max_iters	500	最大迭代次数
$ω$	1.5	惯性权重系数
$v m a x$	1	粒子最大速度
$c 2$	2	群体学习因子
$k a t t$	10	目标点引力参数
$k i b$	0.3	最优粒子引力参数
$k r e p$	10	障碍物斥力系数
r	2	斥力作用范围
l	0.05	搜索步长

表 1

表 2

图7

表 3

图8

图9

表4

图10

图11

图12

图13

参考文献 38

1	Homola J, Martin L, Cencetti M, et al. UAS Traffic Management (UTM) Technical Capability Level 3 (TCL3) Flight Demonstration: Concept Tests and Results[C]//2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC). Piscataway, NJ, USA: IEEE, 2019: 1-8.
2	Goyal R, Reiche C, Fernando C, et al. Urban Air Mobility (UAM) Market Study[EB/OL]. (2018-10-05) [2022-08-18]. .
3	Kopardekar P, Rios J, Prevot T, et al. Unmanned Aircraft System Traffic Management(UTM)Concept of Operations[C]//AIAA Aviation and Aeronautics Forum (Aviation 2016). [S.l.]: [s.n.], 2016.
4	McCarthy Tim, Pforte Lars, Burke Rebekah. Fundamental Elements of an Urban UTM[J]. Aerospace, 2020, 7(7): 85.
5	Pang Bizhao, Dai Wei, Ra Thu, et al. A Concept of Airspace Configuration and Operational Rules for UAS in Current Airspace[C]//2020 AIAA/IEEE 39th Digital Avionics Systems Conference (DASC). Piscataway, NJ, USA: IEEE, 2020: 1-9.
6	Sunil E, Hoekstra J M, Ellerbroek J, et al. Metropolis: Relating Airspace Structure and Capacity for Extreme Traffic Densities[C]//Proceedings of the 11th USA/Europe Air Traffic Management Research and Development Seminar (ATM2015). [S.l.]: FAA & Eurocontrol, 2015: 1-10.
7	汪玚. 迅蚁: 末端即时配送延伸 "路空一体" 空中配送 "触角"-专访杭州迅蚁网络科技有限公司联合创始人庾航[J]. 交通建设与管理, 2020(3): 118-123.
8	林舒仪, 张斌. 无人机物流配送行业未来发展研究-基于美团发布自研新型无人机的分析[J]. 物流工程与管理, 2022, 44(5): 104-106.
	Lin Shuyi, Zhang Bin. Research on the Future Development of UAV Logistics Distribution Industry-analysis of Self-developed New UAV Based on Meituan Release[J]. Logistics Engineering and Management, 2022, 44(5): 104-106.
9	钟求喜, 谢涛, 陈火旺. 基于遗传算法的任务分配与调度[J]. 计算机研究与发展, 2000, 37(10): 1197-1203.
	Zhong Qiuxi, Xie Tao, Chen Huowang. Task Matching and Scheduling by Using Genetic Algorithms[J]. Journal of Computer Research and Development, 2000, 37(10): 1197-1203.
10	牛双诚, 晋玉强, 寇昆湖. 基于区块链的多无人机协同任务分配方法研究[J]. 系统仿真学报, 2023, 35(5): 949-956.
	Niu Shuangcheng, Jin Yuqiang, Kou Kunhu. Research on Collaborative Task Allocation Method of Multiple UAVs Based on Blockchain[J]. Journal of System Simulation, 2023, 35(5): 949-956.
11	王峰, 张衡, 韩孟臣, 等. 基于协同进化的混合变量多目标粒子群优化算法求解无人机协同多任务分配问题[J]. 计算机学报, 2021, 44(10): 1967-1983.
	Wang Feng, Zhang Heng, Han Mengchen, et al. Co-evolution Based Mixed-variable Multi-objective Particle Swarm Optimization for UAV Cooperative Multi-task Allocation Problem[J]. Chinese Journal of Computers, 2021, 44(10): 1967-1983.
12	Dai Wei, Pang Bizhao, Kin Huat Low. Conflict-free Four-dimensional Path Planning for Urban Air Mobility Considering Airspace Occupancy[J]. Aerospace Science and Technology, 2021, 119: 107154.
13	Gallacher David. Drones to Manage the Urban Environment: Risks, Rewards, Alternatives[J]. Journal of Unmanned Vehicle Systems, 2016, 4(2): 115-124.
14	Hoekstra J M, Maas J B, Tra M A P, et al. How Do Layered Airspace Design Parameters Affect Airspace Capacity and Safety?[C]//7th International Conference on Research in Air Transportation. [S.l.]: [s.n.], 2016: 1-8.
15	Primatesta Stefano, Guglieri Giorgio, Rizzo Alessandro. A Risk-aware Path Planning Strategy for UAVs in Urban Environments[J]. Journal of Intelligent & Robotic Systems, 2019, 95(2): 629-643.
16	张洪海, 李翰, 刘皞, 等. 城市区域物流无人机路径规划[J]. 交通运输系统工程与信息, 2020, 20(6): 22-29.
	Zhang Honghai, Li Han, Liu Hao, et al. Path Planning for Logistics Unmanned Aerial Vehicle in Urban Area[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(6): 22-29.
17	张启钱, 许卫卫, 张洪海, 等. 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286.
	Zhang Qiqian, Xu Weiwei, Zhang Honghai, et al. Path Planning for Logistics UAV in Complex Low-altitude Airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286.
18	戴健, 许菲, 陈琪锋. 多无人机协同搜索区域划分与路径规划[J]. 航空学报, 2020, 41(增1): 146-153.
	Dai Jian, Xu Fei, Chen Qifeng. Multi-UAV Cooperative Search on Region Division and Path Planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S1): 146-153.
19	谌海云, 陈华胄, 刘强. 基于改进人工势场法的多无人机三维编队路径规划[J]. 系统仿真学报, 2020, 32(3): 414-420.
	Chen Haiyun, Chen Huazhou, Liu Qiang. Multi-UAV 3D Formation Path Planning Based on Improved Artificial Potential Field[J]. Journal of System Simulation, 2020, 32(3): 414-420.
20	司徒华杰, 雷海波, 庄春刚. 动态环境下基于人工势场引导的RRT路径规划算法[J]. 计算机应用研究, 2021, 38(3): 714-717, 724.
	Situ Huajie, Lei Haibo, Zhuang Chungang. Artificial Potential Field Based RRT Algorithm for Path Planning in Dynamic Environment[J]. Application Research of Computers, 2021, 38(3): 714-717, 724.
21	田广键, 代冀阳, 应进, 等. 基于自适应分段势场法的多无人机航迹规划[J]. 系统仿真学报, 2022, 34(11): 2368-2376.
	Tian Guangjian, Dai Jiyang, Ying Jin, et al. Multi-UAV Trajectory Planning Based on Adaptive Segmented Potential Field Method[J]. Journal of System Simulation, 2022, 34(11): 2368-2376.
22	陈劲峰, 黄卫华, 章政, 等. 动态环境下基于改进人工势场法的路径规划算法[J]. 组合机床与自动化加工技术, 2020(12): 6-9, 14.
	Chen Jinfeng, Huang Weihua, Zhang Zheng, et al. Path Planning Algorithm Based on Improved Artificial Potential Field Method in Dynamic Environment[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2020(12): 6-9, 14.
23	McCarthy Tim, Pforte Lars, Burke Rebekah. Fundamental Elements of an Urban UTM[J]. Aerospace, 2020, 7(7): 85.
24	陈世明, 江冀海, 吴龙龙, 等. 受限空间自适应区域栅格化的优化路径规划[J]. 控制与决策, 2012, 27(7): 1105-1108.
	Chen Shiming, Jiang Jihai, Wu Longlong, et al. Optimal Path Planning in Limited Space Based on Adaptive Regional Grid[J]. Control and Decision, 2012, 27(7): 1105-1108.
25	刘正锋, 张隆辉, 魏纳新, 等. 环境地图的格栅化及路径规划研究[J]. 舰船科学技术, 2021, 43(7): 141-145.
	Liu Zhengfeng, Zhang Longhui, Wei Naxin, et al. Research on Gridding and Path Planning of Environmental Map[J]. Ship Science and Technology, 2021, 43(7): 141-145.
26	Balakrishnan K, Polastre J, Mooberry J, et al. Blueprint for the Sky: The Roadmap for the Safe Integration of Autonomous Aircraft[J]. Airbus UTM, San Francisco, CA, 2018.
27	AirMatrix. UTM Software for Drone Pilots and Governments [EB/OL]. [2022-08-18]. .
28	Khatib O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. International Journal of Robotics Research, 1986, 5(1): 90-98.
29	Yi Ziwei, Li Linheng, Qu Xu, et al. Using Artificial Potential Field Theory for a Cooperative Control Model in a Connected and Automated Vehicles Environment[J]. Transportation Research Record, 2020, 2674(9): 1005-1018.
30	Shi Y, Eberhart R C. Empirical Study of Particle Swarm Optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation-CEC99. Piscataway, NJ, USA: IEEE, 1999: 1945-1950.
31	张婷婷, 柴来. 多无人机多目标路径规划[J]. 指挥信息系统与技术, 2020, 11(6): 32-36, 46.
	Zhang Tingting, Chai Lai. Path Planning for UAVs and Multiple Targets[J]. Command Information System and Technology, 2020, 11(6): 32-36, 46.
32	Li Zheng, Ruan Yi. Autonomous Inspection Robot for Power Transmission Lines Maintenance While Operating on the Overhead Ground Wires[J]. International Journal of Advanced Robotic Systems, 2010, 7(4): 25.
33	陈悦, 刘则渊. 悄然兴起的科学知识图谱[J]. 科学学研究, 2005, 23(2): 149-154.
	Chen Yue, Liu Zeyuan. The Rise of Mapping Knowledge Domain[J]. Studies in Science of Science, 2005, 23(2): 149-154.
34	胡泽文, 孙建军, 武夷山. 国内知识图谱应用研究综述[J]. 图书情报工作, 2013, 57(3): 131-137, 84.
	Hu Zewen, Sun Jianjun, Wu Yishan. Research Review on Application of Knowledge Mapping in China[J]. Library and Information Service, 2013, 57(3): 131-137, 84.
35	刘峤, 李杨, 段宏, 等. 知识图谱构建技术综述[J]. 计算机研究与发展, 2016, 53(3): 582-600.
	Liu Qiao, Li Yang, Duan Hong, et al. Knowledge Graph Construction Techniques[J]. Journal of Computer Research and Development, 2016, 53(3): 582-600.
36	庄晓东, 孟庆春, 高云, 等. 复杂环境中基于人工势场优化算法的最优路径规划[J]. 机器人, 2003, 25(6): 531-535.
	Zhuang Xiaodong, Meng Qingchun, Gao Yun, et al. Optimal Path Planning in Complex Environments Based on Optimization of Artificial Potential Field[J]. Robot, 2003, 25(6): 531-535.
37	朱毅, 张涛, 宋靖雁. 非完整移动机器人的人工势场法路径规划[J]. 控制理论与应用, 2010, 27(2): 152-158.
	Zhu Yi, Zhang Tao, Song Jingyan. Path Planning for Nonholonomic Mobile Robots Using Artificial Potential Field Method[J]. Control Theory & Applications, 2010, 27(2): 152-158.
38	Ge S S, CUI Y J. New Potential Functions for Mobile Robot Path Planning[J]. IEEE Transactions on Robotics and Automation, 2000, 16(5): 615-620.

无人机编号	起始点	目标点
UAV-1	(0，12)	(19，19)
UAV-2	(6，0)	(19，19)

算法	评价指标
算法	平均迭代次数	平均航迹生成时间/s
传统算法	+∞	+∞
本文算法	554	2.606 3

无人机编号	起始点	目标点	起飞时间
UAV-1	(0，0)	(20，29)	08:30
UAV-2	(29，0)	(20，20)	08:30
UAV-3	(0，20)	(20，29)	08:15
UAV-4	(20，0)	(29，29)	08:15
UAV-5	(0，29)	(10，20)	08:30
UAV-6	(20，29)	(20，20)	08:30
UAV-7	(0，0)	(29，29)	08:00
UAV-8	(0，0)	(20，20)	08:30
UAV-9	(15，0)	(10，20)	08:30
UAV-10	(29，10)	(20，20)	08:15
UAV-11	(20，0)	(29，29)	08:30
UAV-12	(0，20)	(20，20)	08:30
UAV-13	(0，10)	(15，29)	08:15
UAV-14	(15，0)	(29，29)	08:30
UAV-15	(29，10)	(15，29)	08:30

[1]	钟麟, 佟明安, 李盛. 特定多任务下飞机航迹规划研究[J]. 系统仿真学报, 2023, 35(9): 1909-1917.
[2]	王曼, 李大鹏, 丁良辉, 朱天林. 基于虚拟子目标联合边界力的编队避障算法[J]. 系统仿真学报, 2023, 35(9): 1918-1930.
[3]	林俊强, 王红军, 邹湘军, 张坡, 李承恩, 周益鹏, 姚书杰. 基于DPPO的移动采摘机器人避障路径规划及仿真[J]. 系统仿真学报, 2023, 35(8): 1692-1704.
[4]	刘家义, 王刚, 付强, 郭相科, 王思远. 基于分配策略优化算法的智能防空任务分配[J]. 系统仿真学报, 2023, 35(8): 1705-1716.
[5]	杜利珍, 叶涛, 王宇豪, 张亚军, 宣自风. 改进粒子群算法的不相关并行批处理调度优化[J]. 系统仿真学报, 2023, 35(7): 1549-1561.
[6]	王旭, 季伟东, 周国辉. 基于协同博弈粒子群算法的故障指示器配置优化[J]. 系统仿真学报, 2023, 35(6): 1278-1289.
[7]	赵传超, 郑睿, 龚莉, 马小陆. 网联环境中新能源货车的粒子群调度方法[J]. 系统仿真学报, 2023, 35(6): 1337-1350.
[8]	牛双诚, 晋玉强, 寇昆湖. 基于区块链的多无人机协同任务分配方法研究[J]. 系统仿真学报, 2023, 35(5): 949-956.
[9]	赵拓, 邓汉强, 高佳隆, 黄健. 基于网络节点聚类的多无人机动态目标分配[J]. 系统仿真学报, 2023, 35(4): 695-708.
[10]	杨伟凯, 王艳, 纪志成. 面向知识图谱的智能生产系统工艺知识推理方法[J]. 系统仿真学报, 2023, 35(4): 773-785.
[11]	马悦, 吴琳, 郭圣明. 作战任务分配建模及求解方法研究[J]. 系统仿真学报, 2023, 35(4): 887-898.
[12]	薛均晓, 孔祥燕, 董博威, 陶浩, 管海洋, 石磊, 徐明亮. 航母甲板上舰载机的混合避障和仿真[J]. 系统仿真学报, 2023, 35(3): 592-603.
[13]	胡万杰, 董建军, 任睿, 陈志龙. 考虑模糊不确定的地铁货运系统成网布局规划[J]. 系统仿真学报, 2022, 34(8): 1725-1740.
[14]	张玉超, 蒋沅, 代冀阳. 三阶多机器人协同编队动态避障控制[J]. 系统仿真学报, 2022, 34(8): 1762-1774.
[15]	冯飞波, 闫兴德, 郑宝强, 尹晓峰, 周梦真, 蒋鑫. 蓄电‒氢储混合储能系统的配电网双层优化[J]. 系统仿真学报, 2022, 34(7): 1405-1416.

面向超低空物流场景的多机协同航迹规划算法

Multi-UAV Collaborative Trajectory Planning Algorithm for Urban Ultra-low-altitude Air Transportation Scenario

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 38

相关文章 15

编辑推荐

Metrics

本文评价