基于MB-RRT*的无人机多点航迹规划算法研究

摘要/Abstract

摘要： 随着小型无人机的广泛应用,无人机的自动巡航能力至关重要。多点航迹规划作为复杂的无人机航行任务之一,要求为无人机规划出一条最优航迹或次优航迹,如距离最短、速度最快或者时间最短,并保证其在不碰撞已知障碍物的条件下遍历所有特定的航点。针对无序的多点航迹规划问题,基于MB-RRT^*算法并结合原本用于解决TSP问题的贪心策略提出了贪心MB-RRT^*算法,其通过牺牲一定的航迹质量,来提高解决无人机多点航迹规划问题的速度,减少时间代价。最后在二维地图环境和三维环境下进行实验,验证了所提算法的可行性和有效性。

关键词: RRT, 多点航迹规划, 收敛速度, 贪心算法, 无人机

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

中图分类号:

TP242

陈晋音,胡可科,李玉玮. 基于MB-RRT^*的无人机多点航迹规划算法研究[J]. 计算机科学, 2018, 45(6A): 85-90. https://doi.org/

CHEN Jin-yin, HU Ke-ke,LI Yu-wei. Research on UAV Multi-point Navigation Algorithm Based on MB-RRT^*[J]. Computer Science, 2018, 45(6A): 85-90. https://doi.org/

参考文献

[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.

相关文章 15

[1]	蹇奇芮, 陈泽茂, 武晓康. 面向无人机通信的认证和密钥协商协议 Authentication and Key Agreement Protocol for UAV Communication 计算机科学, 2022, 49(8): 306-313. https://doi.org/10.11896/jsjkx.220200098
[2]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[3]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
[4]	陈博琛, 唐文兵, 黄鸿云, 丁佐华. 基于改进人工势场的未知障碍物无人机编队避障 Pop-up Obstacles Avoidance for UAV Formation Based on Improved Artificial Potential Field 计算机科学, 2022, 49(6A): 686-693. https://doi.org/10.11896/jsjkx.210500194
[5]	谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于PPO的任务卸载方案 PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing 计算机科学, 2022, 49(6): 3-11. https://doi.org/10.11896/jsjkx.220100249
[6]	史殿习, 刘聪, 佘馥江, 张拥军. GPS拒止环境下基于定位置信度的多无人机协同定位方法 Cooperation Localization Method Based on Location Confidence of Multi-UAV in GPS-deniedEnvironment 计算机科学, 2022, 49(4): 302-311. https://doi.org/10.11896/jsjkx.210200106
[7]	赵耿, 宋鑫宇, 马英杰. 混沌子载波调制的无人机安全数据链路 Secure Data Link of Unmanned Aerial Vehicle Based on Chaotic Sub-carrier Modulation 计算机科学, 2022, 49(3): 322-328. https://doi.org/10.11896/jsjkx.210200022
[8]	成昭炜, 沈航, 汪悦, 王敏, 白光伟. 基于深度强化学习的无人机辅助弹性视频多播机制 Deep Reinforcement Learning Based UAV Assisted SVC Video Multicast 计算机科学, 2021, 48(9): 271-277. https://doi.org/10.11896/jsjkx.201000078
[9]	徐浩, 刘岳镭. 基于深度学习的无人机声音识别算法 UAV Sound Recognition Algorithm Based on Deep Learning 计算机科学, 2021, 48(7): 225-232. https://doi.org/10.11896/jsjkx.200500091
[10]	孙一凡, 米志超, 王海, 赵宁. 基于分簇的拓扑自适应的无人机蜂群OLSR路由协议 Cluster-based Topology Adaptive OLSR Protocol for UAV Swarm Network 计算机科学, 2021, 48(6): 268-275. https://doi.org/10.11896/jsjkx.200500130
[11]	黄鑫权, 刘爱军, 梁小虎, 王桁. 基于矩阵论的一致性控制算法收敛速度分析 Matrix Theory Aided Convergence Analysis of Consensus Behavior in FANET with Beacon Loss 计算机科学, 2021, 48(6): 288-295. https://doi.org/10.11896/jsjkx.201000137
[12]	王宇晨, 齐文慧, 徐立臻. 基于区块链的无人机集群安全协作 Security Cooperation of UAV Swarm Based on Blockchain 计算机科学, 2021, 48(11A): 528-532. https://doi.org/10.11896/jsjkx.201100199
[13]	刘华玲, 皮常鹏, 刘梦瑶, 汤新. 一种新的优化机制:Rain New Optimization Mechanism:Rain 计算机科学, 2021, 48(11A): 63-70. https://doi.org/10.11896/jsjkx.201100032
[14]	杨章林, 谢钧, 张耕强. 基于定向天线的飞行自组网定向路由协议综述 Review of Directional Routing Protocols for Flying Ad-Hoc Networks Based on Directional Antennas 计算机科学, 2021, 48(11): 334-344. https://doi.org/10.11896/jsjkx.210400182
[15]	赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed