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

LI Anti; LI Chenglong; WU Dingjie; WEI Peng

doi:10.7527/S1000-6893.2020.23726

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

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

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

Electronics and Electrical Engineering and Control

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

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)

Cite this article

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 . DOI: 10.7527/S1000-6893.2020.23726

References

[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

Outlines

模态框（Modal）标题

Abstract

Cite this article

References