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

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]. 航空学报, 2023, 44(1): 326107-326107.
[2]	郭琪磊, 桑为民, 牛俊杰, 袁烨. 复杂气象条件下考虑结冰风险的无人机飞行策略[J]. 航空学报, 2023, 44(1): 627518-627518.
[3]	胡阳修, 赵长春, 贾成龙, 钱洲元, 胡涛. 基于ROS的集群无人机同步路径编队控制[J]. 航空学报, 2022, 43(S1): 726914-726914.
[4]	胡伟, 万文章, 陈谋. 基于神经网络和干扰观测器的UAV自动着舰控制[J]. 航空学报, 2022, 43(S1): 726963-726963.
[5]	苏翎菲, 化永朝, 董希旺, 任章. 人与无人机集群多模态智能交互方法[J]. 航空学报, 2022, 43(S1): 727001-727001.
[6]	刘雷, 刘大卫, 王晓光, 陈俊男, 刘东兴. 无人机集群与反无人机集群发展现状及展望[J]. 航空学报, 2022, 43(S1): 726908-726908.
[7]	杨明月, 寿莹鑫, 唐勇, 刘畅, 许斌. 多四旋翼无人机编队保持与避碰控制[J]. 航空学报, 2022, 43(S1): 726913-726913.
[8]	李辉, 龙腾, 孙景亮, 徐广通. 基于自适应视线法的无人机三维航迹跟踪方法[J]. 航空学报, 2022, 43(9): 326105-326105.
[9]	刘文金, 裴扬, 葛玉雪, 艾俊强. 基于ABMS的对地攻击型无人机体系贡献率评估[J]. 航空学报, 2022, 43(9): 225972-225972.
[10]	芦方旭, 米志超, 马骏, 李艾静, 王海. 基于势博弈的多QoS无人机基站空间优化部署[J]. 航空学报, 2022, 43(9): 326137-326137.
[11]	周伟, 马培洋, 郭正, 王道平, 周睿孙. 基于翼尖链翼的组合固定翼无人机研究[J]. 航空学报, 2022, 43(9): 325946-325946.
[12]	孙杨, 昌敏, 白俊强. 微小型四旋翼无人机垂面栖停轨迹规划与控制[J]. 航空学报, 2022, 43(9): 325756-325756.
[13]	赵良玉, 李丹, 赵辰悦, 蒋飞. 无人机自主降落标识检测方法若干研究进展[J]. 航空学报, 2022, 43(9): 25882-025882.
[14]	张洲宇, 曹云峰, 范彦铭. 低空小型无人机空域冲突视觉感知技术研究进展[J]. 航空学报, 2022, 43(8): 25645-025645.
[15]	邢玲, 贾晓凡, 赵鹏程, 吴红海. 基于矩阵加密的无人机群位置隐私保护方法[J]. 航空学报, 2022, 43(8): 325386-325386.