结合跳点引导的无人机随机搜索避撞决策方法

doi:10.7527/S1000-6893.2020.23726

电子电气工程与控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

结合跳点引导的无人机随机搜索避撞决策方法

李安醍¹, 李诚龙¹, 武丁杰¹, 卫鹏²

1. 中国民用航空飞行学院空中交通管理学院, 广汉 618307;
2. 乔治·华盛顿大学机械与航空航天工程学院, 华盛顿特区 20052

收稿日期:2019-12-12 修回日期:2020-01-14 出版日期:2020-08-15 发布日期:2020-02-06
通讯作者: 李诚龙 E-mail:lcl@cafuc.edu.cn
基金资助:
国家自然科学基金民航联合基金（U1733105）；民航局安全能力建设项目（0241928）；浙江大学工业控制技术国家重点实验室开放基金（ICT1900342）；四川省大学生创新创业训练计划项目（S201910624216）

Collision avoidance decision method for UAVs in random search combined with jump point guidance

LI Anti¹, LI Chenglong¹, WU Dingjie¹, WEI Peng²

1. College of Air Traffic Management, Civil Aviation Flight University of China, Guanghan 618307, China;
2. Department of Mechanical and Aerospace Engineering, George Washington University, Washington, D. C. 20052, USA

Received:2019-12-12 Revised:2020-01-14 Online:2020-08-15 Published:2020-02-06
Supported by:
National Natural Science Foundation of China Civil Aviation Joint Fund (U1733105); Safety Capacity Building Program of Civil Aviation Administration of China (0241928); Open Research Project of the State Key Laboratory of Industrial Control Technology, Zhejiang University,China (ICT1900342); Sichuan Province College Students’ Innovative Entrepreneurial Training Plan Program (S201910624216)

摘要/Abstract

摘要： 针对无人机在城市空域环境和密集交通流下的避撞决策问题，提出马尔科夫决策过程（MDP）和蒙特卡洛树搜索（MCTS）算法对该问题进行建模求解。蒙特卡洛树搜索算法在求解过程中为保证实时性而使其搜索深度受限，容易陷入局部最优，导致在含有静态障碍的场景中无法实现避撞的同时保证全局航迹最优。因此结合跳点搜索算法在全局规划上的优势，建立离散路径点引导无人机并改进奖励函数来权衡飞行路线，在进行动态避撞的同时实现对静态障碍的全局避撞。经过多个实验场景仿真，其结果表明改进后的算法均能在不同场景中获得更好的性能表现。特别是在凹形限飞区空域仿真模型中，改进后的算法相对于原始的蒙特卡洛树搜索算法，其冲突概率降低了36%并且飞行时间缩短47.8%。

关键词: 城市空中交通, 无人机, 避撞决策, 路径规划, 蒙特卡洛树搜索(MCTS)

Abstract: Aiming at the collision avoidance decision of UAVs in urban airspace environment and dense air traffic flow, Markov Decision Process (MDP) and Monte Carlo Tree Search (MCTS) algorithms are proposed to model and solve this problem. To ensure real-time performance, the MCTS algorithm is limited in search depth, thus easy to fall into the local optimal solution, resulting in the inability to achieve collision avoidance and track optimization in the scene with static obstacles. Therefore, a discrete path point combining the advantages of Jump Point Search algorithm in global planning is established to guide UAVs, and the reward function is improved to balance the flight path, avoiding local dynamic collisions and static obstacles simultaneously. The simulation results show that the improved algorithm can achieve better performance in different experimental scenarios, particularly in the simulation model of concave restricted flight area, where, compared with the original MCTS algorithm, the collision probability of the improved algorithm and the flight time are reduced by 36% and 47.8%, respectively.

Key words: urban air mobility, unmanned aerial vehicle, collision avoidance decision, path planning, Monte Carlo Tree Search(MCTS)

中图分类号:

V279

李安醍, 李诚龙, 武丁杰, 卫鹏. 结合跳点引导的无人机随机搜索避撞决策方法[J]. 航空学报, 2020, 41(8): 323726-323726.

LI Anti, LI Chenglong, WU Dingjie, WEI Peng. Collision avoidance decision method for UAVs in random search combined with jump point guidance[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(8): 323726-323726.

参考文献 37

[1]	THIPPHAVONG D P, APAZA R, BARMORE B, et al. Urban air mobility airspace integration concepts and considerations[C]//2018 Aviation Technology, Integration, and Operations Conference, 2018:3676.
[2]	Uber Elevate. Fast-forwarding to a future of on-demand urban air transportation[EB/OL].(2016-10-27)[2019-12-05]. https://d1nyezh1ys8wfo.cloudfront.net/static/PDFs/Elevate%2BWhitepaper.pdf.
[3]	BALAKRISHNAN K, POLASTRE J, MOOBERRY J, et al. Blueprint for the sky[EB/OL].[2019-12-05].https://storage.googleapis.com/blueprint/Airbus_UTM_Blueprint.pdf.
[4]	VASCIK P D, HANSMAN R J, DUNN N S. Analysis of urban air mobility operational constraints[J]. Journal of Air Transportation, 2018, 26(4):133-146.
[5]	YU X, ZHANG Y. Sense and avoid technologies with applications to unmanned aircraft systems:Review and prospects[J]. Progress in Aerospace Sciences, 2015, 74:152-166.
[6]	HUNTER G, WEI P. Service-oriented separation assurance for small UAS traffic management[C]//2019 Integrated Communications, Navigation and Surveillance Conference (ICNS). Piscataway:IEEE Press, 2019:1-11.
[7]	KUCHAR J K, YANG L C. A review of conflict detection and resolution modeling methods[J]. IEEE Transactions on Intelligent Transportation Systems, 2000, 1(4):179-189.
[8]	刘慧颖,白存儒,杨广珺. 无人机自主防撞关键技术与应用分析[J]. 航空工程进展, 2014, 5(2):141-147. LIU H Y, BAI C R, YANG G J. Application and analysis discussion of autonomous collison avoidance techniques for unmanned aerial vehicle[J]. Advances in Aeronautical Science and Engineering, 2014, 5(2):141-147(in Chinese).
[9]	朱代武. 低空空域飞行冲突避让算法[J]. 交通运输工程学报, 2005(3):73-76. ZHU D W. Calculational methods of avoiding flight conflict in low altitude airspace[J]. Journal of Traffic and Transportation Engineering, 2005(3):73-76(in Chinese).
[10]	PARK J W, OH H D, TAHK M J. UAV collision avoidance based on geometric approach[C]//2008 SICE Annual Conference. Piscataway:IEEE Press, 2008:2122-2126.
[11]	TANG J, ALAM S, LOKAN C, et al. A multi-objective approach for dynamic airspace sectorization using agent based and geometric models[J]. Transportation Research Part C:Emerging Technologies, 2012, 21(1):89-121.
[12]	彭良福,林云松. 空中自动防撞系统最优逃避机动的确定[J]. 控制理论与应用, 2010, 27(11):1575-1579. PENG L F, LIN Y S. Determination of optimal escape maneuver for automatic air collision avoidance system[J]. Control Theory & Applications, 2010, 27(11):1575-1579(in Chinese).
[13]	LIU J Y, GUO Z Q, LIU S Y. The simulation of the UAV collision avoidance based on the artificial potential field method[C]//Advanced Materials Research, 2012, 591-593:1400-1404.
[14]	SUN J, TANG J, LAO S. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm[J]. IEEE Access, 2017, 5:18382-18390.
[15]	YANG Z, LI C, LIU G. Cooperative 4D guidance for multiple UAVs based on tensor field[C]//2018 13th World Congress on Intelligent Control and Automation (WCICA). Piscataway:IEEE Press, 2018:1709-1714.
[16]	梁宵,王宏伦,李大伟,等. 基于流水避石原理的无人机三维航路规划方法[J]. 航空学报. 2013, 34(7):1670-1681. LIANG X, WANG H L, LI D W, et al. Three-dimensional path planning for unmanned aerial vehicles based on principles of stream avoiding obstacles[J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(7):1670-1681(in Chinese).
[17]	WANG H, LYU W, YAO P, et al. Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system[J]. Chinese Journal of Aeronautics, 2015, 28(1):229-239.
[18]	ALONSO-AYUSO A, ESCUDERO L F, MARTIN-CAMPO F J. Collision avoidance in air traffic management:A mixed-integer linear optimization approach[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(1):47-57.
[19]	YANG H, ZHAO Y. Trajectory planning for autonomous aerospace vehicles amid known obstacles and conflicts[J]. Journal of Guidance, Control, and Dynamics, 2004, 27(6):997-1008.
[20]	CEKMEZ U, OZSIGINAN M, SAHINGOZ O K. Multi colony ant optimization for UAV path planning with obstacle avoidance[C]//2016 International Conference on Unmanned Aircraft Systems (ICUAS). Piscataway:IEEE Press, 2016:47-52.
[21]	SHAKHATREH H, SAWALMEH A H, AL-FUQAHA A, et al. Unmanned aerial vehicles (UAVs):A survey on civil applications and key research challenges[J]. IEEE Access, 2019, 7:48572-48634.
[22]	GUPTA J K, EGOROV M, KOCHENDERFER M. Cooperative multi-agent control using deep reinforcement learning[C]//International Conference on Autonomous Agents and Multiagent Systems. Berlin:Springer, 2017:66-83.
[23]	CHEN L, PAPANDREOU G, KOKKINOS I, et al. Deeplab:Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 40(4):834-848.
[24]	YANG X, DENG L, WEI P. Multi-agent autonomous on-demand free flight operations in urban air mobility[C]//AIAA Aviation 2019 Forum. Reston:AIAA, 2019:3520.
[25]	BAI H, HSU D, KOCHENDERFER M J, et al. Unmanned aircraft collision avoidance using continuous-state POMDPs[J]. Robotics:Science and Systems VⅡ, 2012, 1:1-8.
[26]	MUELLER E R, KOCHENDERFER M. Multi-rotor aircraft collision avoidance using partially observable Markov decision processes[C]//AIAA Modeling and Simulation Technologies Conference. Reston:AIAA,2016:3673.
[27]	YANG X, WEI P. Autonomous on-demand free flight operations in urban air mobility using Monte Carlo tree search[C]//International Conference on Research in Air Transportation (ICRAT), 2018.
[28]	BELLMAN R. A Markovian decision process[J]. Journal of Mathematics and Mechanics, 1957, 6:679-684.
[29]	KOCSIS L, SZEPESVÁRI C, WILLEMSON J. Improved Monte-Carlo search[D]. Tartu:University of Tartu, 2006.
[30]	KOCSIS L, SZEPESVÁRI C. Bandit based monte-carlo planning[C]//European Conference on Machine Learning. Berlin:Springer, 2006:282-293.
[31]	AUER P, CESA-BIANCHI N, FISCHER P. Finite-time analysis of the multiarmed bandit problem[J]. Machine Learning, 2002, 47(2-3):235-256.
[32]	BROWNE C B, POWLEY E, WHITEHOUSE D, et al. A survey of Monte Carlo tree search methods[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(1):1-43.
[33]	HARABOR D D, GRASTIEN A. Online graph pruning for pathfinding on grid maps[C]//Twenty-Fifth AAAI Conference on Artificial Intelligence. Palo Alto:AAAI, 2011.
[34]	HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
[35]	BOSSON C, LAUDERDALE T A. Simulation evaluations of an autonomous urban air mobility network management and separation service[C]//2018 Aviation Technology, Integration, and Operations Conference, 2018:3365.
[36]	DUBINS L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of Mathematics, 1957, 79(3):497-516.
[37]	ONG H Y, KOCHENDERFER M J. Markov decision process-based distributed conflict resolution for drone air traffic management[J]. Journal of Guidance, Control, and Dynamics, 2017,40(1):69-80.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

结合跳点引导的无人机随机搜索避撞决策方法

Collision avoidance decision method for UAVs in random search combined with jump point guidance

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 37

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王海峰, 刘坤澎, 江泓鑫, 杜晨曦. 螺旋桨多设计点气动优化方法和变桨距角策略[J]. 航空学报, 2024, 45(9): 528831-528831.
[2]	赵春晖, 刘安萌, 吕洋, 潘泉. 无人机韧性自主定位技术综述[J]. 航空学报, 2024, 45(8): 28839-028839.
[3]	张薇, 何若俊. 面向物联网数据收集的无人机自主路径规划[J]. 航空学报, 2024, 45(8): 329054-329054-1.
[4]	赵靖, 宋丹. 无人机GNSS/IMU组合导航系统完好性监测方法[J]. 航空学报, 2024, 45(7): 328943-328943.
[5]	王传云, 苏阳, 王琳霖, 王田, 王静静, 高骞. 面向反制无人机集群的多目标连续鲁棒跟踪算法[J]. 航空学报, 2024, 45(7): 329017-329017.
[6]	尹洪玉, 吴宇, 梁天骄. 固定翼无人机巡逻覆盖协同路径规划方法[J]. 航空学报, 2024, 45(6): 328944-328944.
[7]	罗旭东, 吴一全, 陈金林. 无人机航拍影像目标检测与语义分割的深度学习方法研究进展[J]. 航空学报, 2024, 45(6): 28822-028822.
[8]	安朝, 霍贵玺, 孟杨, 谢长川, 杨超. 翼尖铰接组合式无人机气动建模方法及布局参数影响[J]. 航空学报, 2024, 45(6): 629587-629587.
[9]	李广佳, 王红波, 张凯, 仪志胜. 临近空间太阳能无人机增升减阻技术综述[J]. 航空学报, 2024, 45(5): 529644-529644.
[10]	蔡云鹏, 周大鹏, 丁江川. 具有防撞安全约束的无人机集群智能协同控制[J]. 航空学报, 2024, 45(5): 529683-529683.
[11]	王祝, 张梦通, 张振鹏, 徐广通. 基于多指标动态优先级的无人机协同路径规划[J]. 航空学报, 2024, 45(4): 328816-328816.
[12]	郑高杰, 何小明, 李东坡, 谭慧俊, 汪昆, 吴祯龙, 王德鹏. 尾部推进无人机双90°偏折进气道/蜗壳耦合流动特性[J]. 航空学报, 2024, 45(4): 128782-128782.
[13]	张清瑞, 刘赟韵, 孙慧杰, 朱波. 固定翼无人机紧密编队的鲁棒协同跟踪控制[J]. 航空学报, 2024, 45(1): 629233-629233.
[14]	郭洪振, 陈谋, 戴永东, 王茂飞. 分布式自适应事件触发四旋翼无人机编队控制[J]. 航空学报, 2023, 44(S2): 729917-729917.
[15]	刘坤达, 刘雪明, 朱波, 张清瑞. 面向狭窄通道穿越的多机编队安全鲁棒控制[J]. 航空学报, 2023, 44(S2): 729768-729768.