复杂城市环境下无人机路网模型研究

doi:10.16097/j.cnki.1009-6744.2023.04.025

交通运输系统工程与信息 ›› 2023, Vol. 23 ›› Issue (4): 251-261.DOI: 10.16097/j.cnki.1009-6744.2023.04.025

复杂城市环境下无人机路网模型研究

胡小兵^a，杨常澍^a,b，周隽^*a,b

中国民航大学，a. 体系安全与智能决策实验室；b. 中欧航空工程师学院，天津 300300

收稿日期:2023-05-28 修回日期:2023-06-19 接受日期:2023-06-28 出版日期:2023-08-25 发布日期:2023-08-22
作者简介:胡小兵(1975- )，男，四川人，教授，博士
基金资助:
中央高校基本科研业务费专项资金(3122023012)；天津市应用基础研究多元投入基金重点项目(21JCQNJC00790)

Route Network Modeling for Unmanned Aerial Vehicle in Complex Urban Environment

HU Xiao-bing^a, YANG Chang-shu^a,b, ZHOU Jun^*a,b

a. Laboratory of Complex System Safety and Intelligent Decisions; b. Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin 300300, China

Received:2023-05-28 Revised:2023-06-19 Accepted:2023-06-28 Online:2023-08-25 Published:2023-08-22
Supported by:
Fundamental Research Funds for the Central Universities of Ministry of Education of China (3122023012)；Key Program of Tianjin Science and Technology Plan (21JCQNJC00790)

摘要/Abstract

摘要： 针对复杂城市环境下无人机路径规划问题，采用三维可视图法研究路网模型。首先，在考虑无人机飞行安全裕度的前提下，将城市密集而不规则的障碍物环境进行变形重组，再以不同的水平和竖直间隔对障碍物外表面进行离散化的节点采集，并构建基于三维可视图的复杂城市低空路网模型。其次，为降低无人机之间的潜在冲突和碰撞风险，引入无人机机动保护区的概念，进一步缩减路网规模，优化路网结构。最后，结合无人机性能和平稳飞行的要求，以最大航向角改变量作为主要限制条件，以最小化路径长度为目标，提出改进的涟漪扩散算法进行求解。仿真结果表明：三维可视图中的采点间隔直接决定了路网模型中节点和链接的数量，并对最优路径与规划时间具有显著影响；1000组仿真实验表明，考虑机动保护区后，最短路径的平均长度相较于无机动保护区时增长了不足1%，而计算耗时降低了近70%。仿真实验验证，通过引入无人机机动保护区和航向角改变量的限制，能够有效降低路网规模，提升运算效率，并有利于获得平滑的路径，降低无人机的潜在碰撞风险。

关键词: 航空运输, 路网模型, 三维可视图, 无人机, 路径规划, 改进涟漪扩散算法

Abstract: This paper focuses on the path planning problem of unmanned aerial vehicle (UAV) in complex urban environments and uses the three-dimensional(3D) visibility graph method for the road network modeling. First, the dense and irregular obstacle environment of the city is deformed and reorganized under the premise considering the safety margin of UAV flight, and then the discrete nodes are collected on the outer surface of the obstacles at different horizontal and vertical intervals. A complex urban low-altitude road network model is developed based on 3D visibility graphs. To reduce the potential conflicts and collision risks between UAVs, the concept of UAV maneuvering protection zone is introduced to further reduce the road network scale and optimize the road network structure. Combined with the requirements of UAV performance and smooth flight, an improved ripple spreading algorithm is proposed to solve the problem with the maximum heading angle change as the main constraint and the minimum path length as the goal. The simulation results show that: the interval of picking points in the 3D visibility graph directly determines the number of nodes and links in the road network model and has a significant impact on the optimal path and planning time. 1000 sets of simulation experiments show that the average length of the shortest path after considering the maneuvering protection zone increases by less than 1% compared with that without the maneuvering protection zone, while the computation time is reduced by nearly 70% . The simulation experiments verify that the introduction of UAV maneuvering protection zone and the limitation of heading angle change can effectively reduce the size of the road network, improve the computational efficiency, and help to obtain smooth paths and reduce the potential collision risk of UAVs.

Key words: air transportation, route network model, three- dimensional(3D) visibility graph, unmanned aerial vehicle (UAV), track planning, ripple spreading algorithm

中图分类号:

胡小兵, 杨常澍, 周隽. 复杂城市环境下无人机路网模型研究[J]. 交通运输系统工程与信息, 2023, 23(4): 251-261.

HU Xiao-bing, YANG Chang-shu, ZHOU Jun. Route Network Modeling for Unmanned Aerial Vehicle in Complex Urban Environment[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(4): 251-261.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/10.16097/j.cnki.1009-6744.2023.04.025

http://www.tseit.org.cn/CN/Y2023/V23/I4/251

参考文献

[1] 蒋丽, 杨露, 梁昌勇, 等. 基于无人机的高层住宅最后“一百米”配送优化[J]. 交通运输系统工程与信息,2022, 22(4): 236-245, 292. [JIANG L, YANG L, LIANG C Y, et al. Optimization of final "100 Meters" UAV delivery in high-rise residential buildings[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 236-245, 292.]

[2] 廖小罕, 屈文秋, 徐晨晨, 等. 城市空中交通及其新型基础设施低空公共航路研究综述[J/OL]. 航空学报. (2023-04-10) [2023-05-15]. http: //kns.cnki.net/ kcms/ detail/11.1929.v.20230407.1711.008.html. [LIAO X H, QU W Q, XU C C, et al. A review of urban air mobility and its new infrastructure low-altitude public routes[J/OL]. Acta Aeronautica et Astronautica Sinica. (2023-04-10) [2023-05-15]. http: //kns.cnki.net/ kcms/ detail/11.1929.v.20230407.1711.008.html.]

[3] 胡莘婷, 吴宇. 面向城市飞行安全的无人机离散型多路径规划方法[J]. 航空学报, 2021, 42(6): 463- 474. [HU X T, WU Y. Risk-based discrete multi-path planning method for UAVs in urban environment[J]. Acta Aeronautica et Astronautica Sinica, 2021,42(6): 463- 474.]

[4] 张洪海, 李翰, 刘皞, 等. 城市区域物流无人机路径规划[J]. 交通运输系统工程与信息, 2020, 20(6): 22-29. [ZHANG H H, LI H, LIU H, 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.]

[5] 王钦禾, 尹永鑫, 戴丽, 等. 基于Voronoi图和蚁群算法的无人机航迹规划[J]. 导航定位与授时, 2021, 8(2): 66-73. [WANG Q H, YIN Y X, DAI L, et al. Trajectory planning of UAV based on Voronoi diagram and ant colony optimization algorithm[J]. Navigation Positioning & Timing, 2021, 8(2): 66-73.]

[6] BLASI L, D'AMATO E, MATTEI M, et al. UAV path planning in 3D constrained environments based on layered essential visibility graphs[J]. IEEE Transactions on Aerospace and Electronic Systems, 2022, 59(3):2359-2375.

[7] 张启瑞, 魏瑞轩, 何仁珂, 等. 城市密集不规则障碍空间无人机航路规划[J].控制理论与应用, 2015, 32(10): 1407-1413. [ZHANG Q R, WEI R X, HE R K, et al. Path planning for unmanned aerial vehicle in urban space crowded with irregular obstacles[J]. Control Theory & Applications, 2015, 32(10): 1407-1413.]

[8] ZHEN Z, XING D, GAO C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm[J]. Aerospace Science and Technology, 2018, 76: 402-411.

[9] 赵丽华, 万晓冬. 基于改进A*算法的多无人机协同路径规划[J]. 电子测量技术, 2020, 43(7): 72- 75, 166. [ZHAO L H, WANG X D. Multi-UAV collaborative path planning based on improved A* algorithm[J]. Electronic Measurement Technology, 2020, 43(7): 72-75, 166.]

[10] 吴宇, 胡莘婷. 城市低空环境中多旋翼无人机在线航线规划方法[J]. 控制与决策, 2021, 36(12): 2851-2860. [WU Y, HU X T. An online route planning method for multi-rotor drone in urban environments[J]. Control and Decision, 2021, 36(12): 2851-2860.]

[11] MOHAMED S M F B, WANCHAO C, WANG Z, et al. Preliminary concept of adaptive urban airspace management for unmanned aircraft operations[M]. Florida: 2018 AIAA Information Systems-AIAA Infotech@ Aerospace, 2018.

[12] OH S, LEONG H W. Edge n-level sparse visibility graphs: Fast optimal any-angle pathfinding using hierarchical taut paths[C]// Proceedings of the International Symposium on Combinatorial Search, 2017, 8(1): 64-72.

[13] CANNY J. The complexity of robot motion planning[M]. Boston: MIT press, 1988.

[14] GAN X, QU H, LIU P, et al. Detection of threat situation for UAV collision avoidance based on sliding window polynomial fitting prediction method[C]. Chongqing: 2019 International Conference on Intelligent Computing, Automation and Systems (ICICAS), IEEE, 2019.

[15] HU X B, WANG M, LEESON M S, et al. Deterministic agent-based path optimization by mimicking the spreading of ripples[J]. Evolutionary Computation, 2016, 24(2): 319-346.

[16] HU X B, GU S H, ZHANG C, et al. Finding all pareto optimal paths by simulating ripple relay race in multi�objective networks[J]. Swarm and Evolutionary Computation, 2021, 64: 100908.

[17] HU X B, WANG M, DI P E. Calculating complete and exact pareto front for multi-objective optimization: A new deterministic approach for discrete problems[J]. IEEE Transactions on Cybernetics, 2013, 43(3): 1088-1101.

[18] HU X B, ZHANG M K, ZHANG Q, et al. Co-evolutionary path optimization by ripple-spreading algorithm[J]. Transportation Research Part B: Methodological, 2017, 106: 411-432.

[19] 张洪海, 张连东, 刘皞, 等. 城市低空物流无人机航迹规划模型研究[J]. 交通运输系统工程与信息, 2022, 22 (1): 256-264. [ZHANG H H, LI L D, LIU H, 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.]

[20] 中国民用航空局航空器适航审定司. 城市场景轻小型无人驾驶航空器物流航线划设规范[EB/OL]. (2022- 08-01) [2023-04-15]. http: //www.caac.gov.cn/ XXGK/ XXGK/BZGF/HYBZ/ 202208/ t20220811_214939. html. [Department of Aircraft Airworthiness Certification, Civil Aviation Administration of China. Route design specification of the light-small unmanned aircraft system for urban logistics [EB/OL]. (2022-08-01) [2023-04- 15]. http://www.caac.gov.cn/XXGK/XXGK/BZGF/HYBZ/ 202208/t20220811_214939.html.]

[21] GAN X, WU Y, LIU P, et al. Dynamic collision avoidance zone modeling method based on UAV emergency collision avoidance trajectory[C]. Dalian: 2020 IEEE International Conference on Artificial Intelligence and Information Systems (ICAIIS). IEEE, 2020.

复杂城市环境下无人机路网模型研究

Route Network Modeling for Unmanned Aerial Vehicle in Complex Urban Environment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王维莉, 王逸文. 基于气象因素与特征选择的进港航班延误可解释预测研究[J]. 交通运输系统工程与信息, 2023, 23(5): 162-171.
[2]	李艳华, 阳杰, 刘志硕, 邓杰. 考虑旅客跨楼中转的航空公司所属航站楼分配优化研究[J]. 交通运输系统工程与信息, 2023, 23(5): 298-311.
[3]	王建忠, 丁小芹, 王树伟. 考虑潜在冲突的进离场航班协同排序[J]. 交通运输系统工程与信息, 2023, 23(5): 312-320.
[4]	吴维, 林芷伊, 陈旭梅. 基于双层博弈模型的机场间航线网络协同演化研究[J]. 交通运输系统工程与信息, 2023, 23(4): 237-250.
[5]	彭宏勤, 张国伍. “双碳”目标下高铁与民航高质量发展策略——“交通7+1论坛”第五十九次会议[J]. 交通运输系统工程与信息, 2023, 23(3): 1-5.
[6]	赵桂红, 马晨傲, 赵巧同, 李建伏. 考虑收益的航空升舱服务产品动态定价方法[J]. 交通运输系统工程与信息, 2023, 23(3): 76-84.
[7]	胡小兵, 赵宇勃, 王瑞昕, 吴志冬, 曾志鸿. 基于组合优化的飞机定检任务调度优化方法研究[J]. 交通运输系统工程与信息, 2023, 23(3): 214-222.
[8]	康柳江, 李浩, 孙会君, 吴建军. 复杂山区工程建设物资运输无人机巡航模型构建与实证研究[J]. 交通运输系统工程与信息, 2023, 23(3): 290-299.
[9]	王红勇, 张加豪, 许平. 基于复杂性的多扇区移交策略优化[J]. 交通运输系统工程与信息, 2023, 23(1): 284-294.
[10]	张勰, 肖恩媛, 刘宏志, 赵嶷飞, 王梦琦. 基于有限穿越可视图的进场航班流量波动特性研究[J]. 交通运输系统工程与信息, 2022, 22(6): 244-257.
[11]	季金华, 刘亚君, 别一鸣, 王琳虹. 基于无人机与卡车协作的封控社区生活物资配送方法[J]. 交通运输系统工程与信息, 2022, 22(5): 264-272.
[12]	温瑞英, 刘文瀚, 王红勇. 编队飞行中基于危险区域的后机最优位置研究[J]. 交通运输系统工程与信息, 2022, 22(5): 300-308.
[13]	唐小卫, 陈祯, 张生润, 丁叶. 繁忙机场机坪空间构型对航班离港滑行时间的影响[J]. 交通运输系统工程与信息, 2022, 22(5): 309-317.
[14]	韩博, 邓志强, 于敬磊, 石依琳, 于剑. 碳达峰目标下中国民航CO₂与NO_x减排协同效益分析[J]. 交通运输系统工程与信息, 2022, 22(4): 53-62.
[15]	蒋丽, 杨露, 梁昌勇, 董骏峰. 基于无人机的高层住宅最后“一百米”配送优化[J]. 交通运输系统工程与信息, 2022, 22(4): 236-245.