Computer Science ›› 2017, Vol. 44 ›› Issue (Z11): 72-79.doi: 10.11896/j.issn.1002-137X.2017.11A.014

Previous Articles     Next Articles

UAV Navigation Algorithm Research Based on EB-RRT*

CHEN Jin-yin, LI Yu-wei and DU Wen-yao   

  • Online:2018-12-01 Published:2018-12-01

Abstract: With the wide application of UAV,automatic navigation capability of UAV becomes more important.UAV navigation algorithm was defined to plan a collision free and smooth path from start position to destination position in known maps.Aiming at three problems of current navigation algorithms including low convergence rate,long searching time and navigation path couldn’t be applied to real UAV,EB-RRT* (Efficient B-RRT*) algorithm was proposed.A self-adaptive obstacle avoidance strategy was designed to speed up convergence rate of traditional navigation algorithm by reducing memory cost.Grid based segmentation mechanism was put forward to reduce searching time for path planning.Suitable down sampling and three times Bessel interpolation formula were adopted to smooth final path for practical UAV applications.Several simulation maps were used to testify the performances of proposed algorithms compared with other classic algorithms.

Key words: RRT,UAV,Navigation algorithm,Convergence rate,Path optimization

[1] VALAVANIS K P.Advances in unmanned aerial vehicles[M]∥State of Art and Road to Autonomy.2007.
[2] DE A,CAVES J.Human-automation collaborative RRT for UAVmission path planning[M]∥Massachusetts Institute of Technology,2010.
[3] TRIHARMINTO H H,PRABUWONO A S.UAV DynamicPath Planning for Intercepting of a Moving Target:A Review[J].Communications in Computer and Information Science,2013,376:206-219.
[4] HOLLAND J H.Adaptation in natural and artificial systems[M].MIT Press,1992.
[5] ROBERGE V,TARBOUCHI M,LABONTE G.Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real Time UAV Path Planning[J].IEEE Transactions on Industrial Informatics,2013,9(1):132-141.
[6] KAVRAKI L,SVESTKA P.Probabilistic roadmaps for pathplanning in high-dimensional configuration spaces[J].IEEE Transactions on Robotics & Automations,1996,12(4):566-580.
[7] LAVALLE S M,KUFFNER J J.Randomized KinodynamicPlanning[J].IEEE International Conference on Robotics & Automation,1999,1(5):473-479.
[8] MELCHIOR N A,SIMMONS R.Particle RRT for Path Planning with Uncertainty[C]∥IEEE International Conference on Robotics & Automation.2007:1617-1624.
[9] LINDEMANN S R,LAVALLE S M.Incrementally reducing dis-persion by increasing voronoi bias in rrts[J].IEEE International Conference on Robotics & Automation,2004,4(4):3251-3257.
[10] KARAMAN S,FRAZZOLI E.Incremental sampling-based algorithms for optimal motion planning[J].International Journal of Robotics Research,2010,30(7):2011.
[11] QURESHI A H,MUMTAZ S,IQBAL K F,et al.Triangular geo-metry based optimal motion planning using RRT*-motion planner[C]∥IEEE International Workshop on Advanced Motion Control.2014:380-385.
[12] KUFFNER J J,LAVALLE S M.RRT-connect:An efficient approach to single-query path planning[C]∥IEEE International Conference on Robotics and Automation.2000:995-1001.
[13] JORDAN M,PEREZ A.Optimal Bidirectional Rapidly-Exploring Random Trees:MIT-CSAIL-TR-2013-021[R].2013.
[14] ZHANG X,LüTTEKE F,ZIEGLER C,et al.Self-learning RRT* Algorithm for Mobile Robot Motion Planning in Complex Environments[M]∥Intelligent Autonomous Systems 13,2016:57-69.
[15] BAIZID K,CHELLALI R,LUZA R,et al.RRS:Rapidly-Exploring Random Snakes a New Method for Mobile Robot Path Planning[M]∥Intelligent Autonomous Systems 13.Springer International Publishing,2014:291-305.
[16] XIONG J,HU Y,WU B,et al.Minimum-cost rapid-growing randomtrees for segmented assembly path planning[J].The International Journal of Advanced Manufacturing Technology,2015,77(5):1043-1055.
[17] YANG K.An efficient Spline-based RRT path planner for non-holonomic robots in cluttered environments[C]∥International Conference on Unmanned Aircraft Systems.2013:288-297.
[18] ABBADI A,PRENOSIL V.Collided Path Replanning in Dyna-mic Environments Using RRT and Cell Decomposition Algorithms[M]∥Modelling and Simulation for Autonomous Systems.Springer International Publishing,2015:131-143.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!