Computer Science

Computer Science ›› 2018, Vol. 45 ›› Issue (6A): 85-90.

• Intelligent Computing • Previous Articles     Next Articles

Research on UAV Multi-point Navigation Algorithm Based on MB-RRT*

CHEN Jin-yin, HU Ke-ke,LI Yu-wei   

  1. College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China
  • Online:2018-06-20 Published:2018-08-03

PDF (PC)

996

Abstract: With the wider application of UAV,automatic navigation capability of UAV plays a more important role.As one of the complex UAV missions,multi-point navigation algorithm requires an optimal path or sub-optimal path,such as the fastest,shortest distance or shortest time to traverse all specific destinations without collision with known obstructions.Aiming at the problem of disordered multi-point path planning,the greedy MB-RRT* algorithm was proposed which is based on MB-RRT* and combined with greedy strategy used to solve the TSP problem.The algorithm improves the speed of the multi-point navigation problem by sacrificing a certain path quality.Finally,the effectiveness of the algorithm was verified by simulation experiments in the two-dimensional and tree-dimensional environment.

Key words: Convergence rate, Greedy algorithm, Multi-point navigation, RRT, UAV

CLC Number: 

  • TP242
[1]何雨枫,曾庆化,王云舒,等.室内微型飞行器实时路径规划算法研究[J].电子测量技术,2014,37(2):23-27.
[2]KAN E M,SIEN H J,PING Y S,et al.An evolutionary algorithm for multiple waypoints planning with B-spline trajectory generation for Unmanned Aerial Vehicles (UAVs) [C]∥International Conference on Computational Problem-Solving.IEEE,2011:77-81.
[3]LAVALLE S M,KUFFNER J J.Randomized Kinodynamic Planning[J].IEEE International Conference on Robotics & Automation,1999,1(5):473-479.
[4]MELCHIOR N A,SIMMONS R.Particle RRT for Path Planning with Uncertainty[C]∥IEEE International Conference on Robotics & Automation.2007:1617-1624.
[5]FAIGL J.On Self-Organizing Map and Rapidly-Exploring Random Graph in Multi-Goal Planning .New York:Springer International Publishing,2016.
[6]TRIHARMINTO H H,PRABUWONO A S,ADJI T B,et al. UAV Dynamic Path Planning for Intercepting of a Moving Target:A Review [C]∥RoboWorld Congress.Springer Berlin Heidelberg,2013:206-219.
[7]MARTIN S R,WRIGHT S E,SHEPPARD J W.Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments[C]∥IEEE International Conference on Automation Science and Engineering.IEEE,2007:1131-1136.
[8]WANG J W,DAI G M,XIE B Q,et al.A Survey of Solving the Traveling Salesman Problem[J].Computer Engineering & Scien-ce,2008,30(2):72-74.
[9]来学伟.贪心算法在TSP问题中的应用[J].许昌学院学报,2017,36(2):41-44.
[1] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[2] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[3] 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.
[4] ZHAO Geng, SONG Xin-yu, MA Ying-jie. Secure Data Link of Unmanned Aerial Vehicle Based on Chaotic Sub-carrier Modulation [J]. Computer Science, 2022, 49(3): 322-328.
[5] SUN Yi-fan, MI Zhi-chao, WANG Hai, ZHAO Ning. Cluster-based Topology Adaptive OLSR Protocol for UAV Swarm Network [J]. Computer Science, 2021, 48(6): 268-275.
[6] HUANG Xin-quan, LIU Ai-jun, LIANG Xiao-hu, WANG Heng. Matrix Theory Aided Convergence Analysis of Consensus Behavior in FANET with Beacon Loss [J]. Computer Science, 2021, 48(6): 288-295.
[7] WANG Yu-chen, QI Wen-hui, XU Li-zhen. Security Cooperation of UAV Swarm Based on Blockchain [J]. Computer Science, 2021, 48(11A): 528-532.
[8] ZHAO Xiao-wei, ZHU Xiao-jun, HAN Zhou-qing. Hover Location Selection and Flight Path Optimization for UAV for Localization Applications [J]. Computer Science, 2021, 48(11): 345-355.
[9] YOU Wen-jing, DONG Chao, WU Qi-hui. Survey of Layered Architecture in Large-scale FANETs [J]. Computer Science, 2020, 47(9): 226-231.
[10] ZHAO Xue-yuan, ZHOU Shao-lei, WANG Shuai-lei and YAN Shi. Formation Containment Control of Multi-UAV System Under Switching Topology [J]. Computer Science, 2020, 47(6A): 577-582.
[11] ZHANG Xin-ming, LI Shuang-qian, LIU Yan, MAO Wen-tao, LIU Shang-wang, LIU Guo-qi. Coyote Optimization Algorithm Based on Information Sharing and Static Greed Selection [J]. Computer Science, 2020, 47(5): 217-224.
[12] SUN Zhi-qiang, WAN Liang, DING Hong-wei. Android Malware Detection Method Based on Deep Autoencoder Network [J]. Computer Science, 2020, 47(4): 298-304.
[13] ZHAO Min,DAI Feng-zhi. Anti-disturbance Control Algorithm of UAV Based on Pneumatic Parameter Regulation [J]. Computer Science, 2020, 47(3): 237-241.
[14] HU Jun-qin, ZHANG Jia-jun, HUANG Yin-hao, CHEN Xing, LIN Bing. Computation Offloading Scheduling Technology for DNN Applications in Edge Environment [J]. Computer Science, 2020, 47(10): 247-255.
[15] LIAO Yong, YANG Xin-yi, XIA Mao-han, WANG Bo, LI Shou-zhi, SHEN Xuan-fan. Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios [J]. Computer Science, 2019, 46(8): 121-126.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.