Computer Science ›› 2022, Vol. 49 ›› Issue (9): 194-201.doi: 10.11896/jsjkx.210700107

• Artificial Intelligence • Previous Articles     Next Articles

Collision Avoidance Planning for Unmanned Aerial Vehicles Based on Spatial Motion Constraints

LUO Xiong-feng, ZHAI Xiang-ping   

  1. College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
  • Received:2021-07-12 Revised:2022-03-04 Online:2022-09-15 Published:2022-09-09
  • About author:LUO Xiong-feng,born in 1998,is a member of China Computer Federation.His main research interests include UAV and Internet of things.
    ZHAI Xiang-ping,born in 1984,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include the area of UAV,Internet of things,wireless networks,resource optimization,and spatial analysis.
  • Supported by:
    National Natural Science Foundation of China(61701231,61802181).

Abstract: In three-dimensional space,how to conduct motion planning when unmanned aerial vehicles(UAV)facing moving obstacles is an interesting research direction.In dynamic environments,traditional algorithms based on the speed obstacles mainly aim at two-dimensional robots,which realizes obstacle avoidance actions by selecting velocities from the reachable velocity set out of the collision velocity set.This paper generalizes algorithms based on the current positions and velocities of UAV and obstacles to calculate the set of velocities that will cause collisions.According to the maximum speed and maximum acceleration of UAV,the velocity space that can be reached at the current moment is restricted.Different strategies are formulated for the needs of various scenes and are selected in a specific method in this subtraction set,so as to avoid obstacles in a three-dimensional scene with specific requirements.Aiming at the scene where UAV abstracted as spherical travels to the destination by avoiding spherical obstacles in 3D space,this paper verifies the obstacle avoidance algorithm by combining C++ and blueprint programming.It captures the movement trajectory of different strategies and records the corresponding consumption time,which demonstrates that the proposed algorithm can effectively complete the dynamic obstacle avoidance task of UAV in three-dimensional space.

Key words: Dynamic environments, Collision avoidance, Motion planning, Velocity obstacle, Reachable velocity set

CLC Number: 

  • TP242
[1]SUN D S,WANG Y.Robot control technology[M].Beijing:Machinery Industry Press,1997.
[2]WANG Z,WEN M,DANG S,et al.Trajectory design and resource allocation for UAV energy minimization in a rotary-wing UAV-enabled WPCN[J].AEJ-Alexandria Engineering Journal,2020,60(1):1787-1796.
[3]HAYWARD V,AUBRY S,FOISY A,et al.Efficient collisionprediction among many moving obstacles[J].International Journal of Robotics Research,1995.14(2):129-143.
[4]XI Y G,ZHANG C G.Rolling path planning of mobile robot in a kind of dynamic uncertain environment [J].Acta Automatica Sinica,2002,28(2):161-175.
[5]REIF J,SHARIR M.Motion planning in the presence of moving obstacles[C]//Symposium on Foundations of Computer Science.2008.
[6]ERDMANN M,LOZANO-PEREZ T.On multiple moving objects[J].Massachusetts Institute of Technology,1986,2(4):477-521.
[7]FUJIMURA K,SAMET H.A hierarchical strategy for pathplanning among moving obstacles[J].IEEE Trans.Robotics Automation,1989,5(1):61-69.
[8]KANT K,ZUCKER S W.Toward Efficient Trajectory Plan-ning:The Path-Velocity Decomposition[J].International Journal of Robotics Research,1986,5(3):72-89.
[9]LEE B H,MEMBER,IEEE,et al.Collision-Free Motion Planning of Two Robots[J].IEEE Transactions on Systems Man & Cybernetics,1987,17(1):21-32.
[10]FRAICHARD T.Dynamic trajectory planning with dynamicconstraints:A ‘state-time space' approach[C]//IEEE/RSJ International Conference on Intelligent Robots & Systems.IEEE,1993.
[11]FRAICHARD T,LAUGIER C.Path-velocity decomposition revisited and applied to dynamic trajectory planning[C]//IEEE International Conference on Robotics & Automation.IEEE,1993.
[12]FUJIMURA K.Time-minimum routes in time-dependent net-works[J].IEEE Transactions on Robotics & Automation,1995,11(3):343-351.
[13]FUJIMURA K,SAMET H.Time-minimal paths among moving obstacles[C]//IEEE International Conference on Robotics & Automation.IEEE,1989.
[14]FUJIMURA K.Motion Planning Amid Transient Obstacles[J].The International Journal of Robotics Research,1994,13(5):395-407.
[15]SANBORN J.A model of reaction for planning in dynamic environments[J].Artificial Intelligence in Engineering,1988,3(2):95-102.
[16]TSUBOUCHI T,ARIMOTO S.Behavior of a mobile robotnavigated by an “iterated forecast and planning” scheme in the presence of multiple moving obstacles[C]//IEEE International Conference on Robotics & Automation.IEEE,1994.
[17]FIORINI P,SHILLER Z.Motion planning in dynamic environments using the relative velocity paradigm[C]//International Conference on Robotics and Automation.IEEE,1993.
[18]FIORINI P,SHILLER Z.Robot Motion Planning in DynamicEnvironments[M].Springer,1996.
[19]FIORINI P,SHILLER Z.Motion Planning in Dynamic Environments Using Velocity Obstacles[J].International Journal of Robotics Research,1998,17(7):760-772.
[20]LI L,YE T,TAN M,et al.Presentstate and future development of mobile robot technology research[J].ROBOT,2002,24(5):475-480.
[21]ZHUANG X D,MENG Q C,YIN B,et al.A method of robot's path searching in dynamic environment based on fuzzy concept[J].ROBOT,2001,23(5):397-399,458.
[22]LI R F,LI W Z.Path Planning for Mobile Robot Based onMulti-sensor Information [J].Mechatronics,2002(4):21-24.
[23]YUNG N H C,YE C.An intelligent mobile vehicle navigatorbased on fuzzy logic and reinforcement learning [J].IEEE Transactions on Systems Man & Cybernetics Part B Cyberne-tics A Publication of the IEEE Systems Man & Cybernetics Society,1999,29(2):314-321.
[24]WANG J,HUANG X H.Obstacle-avoidance control of the two-wheeled cart based on evolving neural network[J].ROBOT,1996,18(5):292-297.
[25]LIU C,WANG H L,YAO P,et al.Modeling and analysis of dynamic collision region for UAV avoiding aerial intruders [J].Journal of Beijing University of Aeronautics and Astronautics,2015,41(7):1231-1238.
[26]LÓPEZ A M,VILLALONGA G,SELLART L,et al.Training my car to see using virtual worlds-ScienceDirect[J].Image and Vision Computing,2017,68:102-118.
[27]O'ROURKE J,BADLER N.Decomposition of three-dimen-sional objects into spheres [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1979,1:295-305.
[1] CHEN Bo-chen, TANG Wen-bing, HUANG Hong-yun, DING Zuo-hua. Pop-up Obstacles Avoidance for UAV Formation Based on Improved Artificial Potential Field [J]. Computer Science, 2022, 49(6A): 686-693.
[2] HU Jie, LAN Yu-bin, OUYANG Fan. Anti-collision Route Planning of UAVs for Charging Ground WSN [J]. Computer Science, 2019, 46(1): 162-168.
[3] KONG Ying, SUN Ming-xuan. Repeatable Motion Planning of Redundant Manipulators Based on Terminal Neural Networks [J]. Computer Science, 2018, 45(12): 201-205.
[4] KONG Ying, SUN Ming-xuan. Terminal Neural Network Algorithm for Solution of Time-varying Sylvester Matrix Equations [J]. Computer Science, 2018, 45(10): 207-211.
[5] CHI Kai-kai, LIN Yi-min and LI Yan-jun. High-throughput and Collision-free Medium Access Control for Wireless Nanosensor Networks [J]. Computer Science, 2015, 42(Z11): 273-276.
[6] . Cognitive Radio Based Routing Protocol for Multi-channel Wireless Mesh Networks [J]. Computer Science, 2012, 39(10): 40-44.
[7] ZHOU Mi,CUI Yong, XU Xing-fu, YANG Xu-ning. Survey of the MAC Protocols on Underwater Acoustic Sensor Network [J]. Computer Science, 2011, 38(9): 5-10.
Full text



No Suggested Reading articles found!