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

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

Abstract

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

CLC Number:

TP391.9

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

Figures/Tables 17

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 1

Algorithm parameters

参数	数值	意义
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	搜索步长

Table 1

Table 2

Fig. 7

Table 3

Fig. 8

Fig. 9

Table 4

Fig. 10

Fig. 11

Fig. 12

Fig. 13

References 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]	Wang Man, Li Dapeng, Ding Lianghui, Zhu Tianlin. Formation Obstacle Avoidance Algorithm Based on Joint Virtual Sub-target and Boundary Force [J]. Journal of System Simulation, 2023, 35(9): 1918-1930.
[2]	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.
[3]	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.
[4]	Jiayi Liu, Gang Wang, Qiang Fu, Xiangke Guo, Siyuan Wang. Intelligent Air Defense Task Assignment Based on Assignment Strategy Optimization Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1705-1716.
[5]	Lizhen Du, Tao Ye, Yuhao Wang, Yajun Zhang, Zifeng Xuan. Improved Particle Swarm Algorithm of Unrelated Parallel Batch Scheduling Optimization [J]. Journal of System Simulation, 2023, 35(7): 1549-1561.
[6]	Chuanchao Zhao, Rui Zheng, Li Gong, Xiaolu Ma. Particle Swarm Optimization for New Energy Truck Scheduling in Network Environment [J]. Journal of System Simulation, 2023, 35(6): 1337-1350.
[7]	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.
[8]	Yuchao Zhang, Yuan Jiang, Jiyang Dai. Dynamic Obstacle Avoidance Control of Three-order Multi-robot Cooperative Formation [J]. Journal of System Simulation, 2022, 34(8): 1762-1774.
[9]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[10]	Kui Chen, Li Bi, Wenya Wang. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop [J]. Journal of System Simulation, 2022, 34(3): 461-469.
[11]	Guangjian Tian, Jiyang Dai, Jin Ying, Ning Wang. Multi-UAV Trajectory Planning Based on Adaptive Segmented Potential Field Method [J]. Journal of System Simulation, 2022, 34(11): 2368-2376.
[12]	Fuzhen Zhang, Yaoqin Zhu. Task Allocation Method for Multi-UAV Cooperative Reconnaissance in Complex Environment [J]. Journal of System Simulation, 2022, 34(10): 2293-2302.
[13]	Zeng Sijie, Yan Liang, Duan Xiaojun. Planning and Analysis on UAV Trajectory Based on PCE Method [J]. Journal of System Simulation, 2022, 34(1): 145-152.
[14]	Li Zhang, Huizhen Zhang, Dong Liu, Yuxin Lu. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency [J]. Journal of System Simulation, 2022, 34(09): 1988-1998.
[15]	Duan Xianyin, Zhang Can, Zhu Zerun, Sun Zhaoyang, Jiang Guozhang, Xiang Feng. Trajectory Planning of 6-DOF Manipulator Based on Inverse Multi-objective Optimization [J]. Journal of System Simulation, 2021, 33(9): 2128-2137.