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

李安醍; 李诚龙; 武丁杰; 卫鹏

doi:10.7527/S1000-6893.2020.23726

航空学报 >

2020 , Vol. 41 >Issue 8: 323726 - 323726

DOI: https://doi.org/10.7527/S1000-6893.2020.23726

电子电气工程与控制

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

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

展开

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

收稿日期: 2019-12-12

修回日期: 2020-01-14

网络出版日期: 2020-02-06

基金资助

国家自然科学基金民航联合基金（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

Expand

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 date: 2019-12-12

Revised date: 2020-01-14

Online 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)

Fold

摘要

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

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

本文引用格式

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

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)

参考文献

[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.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献