基于改进RRT算法的无人机航迹规划

doi:10.3969/j.issn.0372-2112.2017.07.029

电子学报 ›› 2017, Vol. 45 ›› Issue (7): 1764-1769.DOI: 10.3969/j.issn.0372-2112.2017.07.029

基于改进RRT算法的无人机航迹规划

尹高扬, 周绍磊, 吴青坡

海军航空工程学院控制科学与工程系, 山东烟台 264001

收稿日期:2015-12-25 修回日期:2016-10-08 出版日期:2017-07-25
- 作者简介:
- 尹高扬,男,1987年6月出生于湖南湘潭,从事导航、制导与控制相关研究.E-mail:ygy3632@163.com;Tel:15969659253;周绍磊,男,1963年1月出生于山东淄博,教授、博士生导师,主要研究领域为控制与测试.
- 基金资助:
- 航空科学基金 (No.20135184007）

An Improved RRT Algorithm for UAV Path Planning

YIN Gao-yang, ZHOU Shao-lei, WU Qing-po

Department of Control Engineering, Naval Aeronautical and Astronautical University, Yantai, Shandong 264001, China

Received:2015-12-25 Revised:2016-10-08 Online:2017-07-25 Published:2017-07-25

摘要/Abstract

摘要：

针对快速扩展随机树（RRT）算法用于无人机自主在线航迹规划时，只能快速获得可行的航迹，无法获得接近于最短航迹的较优航迹的缺点，提出了一种改进的RRT算法.该算法将无人机动力学约束融入到节点扩展过程中，通过改进离随机采样点最近的根节点的选取策略和引入航迹距离约束，搜索树将沿着航迹距离较短的方向朝着目标点进行扩展，使得规划出来的航迹接近最优，并采用基于B样条曲线的航迹平滑方法生成平滑可跟踪的航迹.仿真结果表明该算法能够快速地搜索安全并且满足无人机动力学约束的较优航迹.

关键词: 无人机, 快速扩展随机树, 实时性, 航迹距离约束, 航迹平滑

Abstract:

To solve the problem that the basic RRT algorithm for UAV path planning can only quickly get feasible path,unable to obtain near optimal path,an improved RRT algorithm is proposed.The algorithm takes into account the dynamic constraints of UAV,by introducing the path length constraint and improving the selection strategy for root node that nearest to the random sample point,the search tree will explore along the direction of the near optimal path.Flyable path is generated by using B-spline curves for path smoothing.Simulation results demonstrated that this proposed method can complete UAV path planning mission quickly and effectively.

Key words: unmanned aerial vehicle(UAV), rapidly-exploring random tree, real-time, path length constraint, path smoothing

中图分类号:

V249.1

尹高扬, 周绍磊, 吴青坡. 基于改进RRT算法的无人机航迹规划[J]. 电子学报, 2017, 45(7): 1764-1769.

YIN Gao-yang, ZHOU Shao-lei, WU Qing-po. An Improved RRT Algorithm for UAV Path Planning[J]. Acta Electronica Sinica, 2017, 45(7): 1764-1769.

参考文献

[1] 沈林成,牛轶峰,朱华勇.多无人机自主协同控制理论与方法[M].北京:国防工业出版社,2013. SHEN Lin-cheng,NIU Yi-feng,ZHU Hua-yong.Theories and Methods of Autonomous Cooperative Control for Multiple UAVs[M].Beijing:National Defense Industry Press,2013.(in Chinese)
[2] 沈林成,陈璟,王楠.飞行器任务规划技术综述[J].航空学报,2014,35(3):593-606. SHEN Lin-cheng,CHEN Jin,WANG Nan.Overview of air vehicle mission planning techniques[J].Acta Aeronautica et Astronautica Sinica,2014,35(3):593-606.(in Chinese)
[3] JENNIFER W,MARIO G P,BRENTON W.Development of a modified voronoi algorithm for UAV path planning and obstacle avoidance[A].Proceedings of AIAA Guidance,Navigation,and Control Conference[C].Minnesota,2012:1-12.
[4] 雷兴明,邢昌风,吴玲.基于分布式约束优化的多平台导弹协同航路规划[J].电子学报,2012,40(10):2068-2072. LEI Xing-ming,XING Chang-feng,WU Ling.Path planning for multi-platform missiles based on distributed constrained optimization[J].Acta Electronica Sinica,2012,40(10):2068-2072.(in Chinese)
[5] 龙涛,孙汉昌,朱华勇,沈林成.战场环境中多无人机任务分配的快速航路预估算法[J].国防科技大学学报,2006,28(5):109-113. LONG Tao,SUN Han-chang,ZHU Hua-yong,SHEN Lin-cheng.Fast route predicting algorithm for multiple UAVs task allocation in battlefield[J].Journal of National University of Defense Technology,2006,28(5):109-113.(in Chinese)
[6] CANNY J F,LIN M.An opportunistic global path planner[J].Algorithmica,1993,10(3):102-120.
[7] BORTOFF S.Path-planning for unmanned air vehicles[A].Proceedings of American Control Conference[C].Chicago,2000:364-368.
[8] 李春华,郑昌文,周成平.一种三维航迹快速搜索方法[J].宇航学报,2002,23(3):13-16. LI Chun-hua,ZHENG Chang-wen,ZHOU Cheng-ping.Fast search algorithm for 3D-route planning[J].Journal of Astronautics,2002,23(3):13-16.(in Chinese)
[9] 郑昌文,丁明跃,周成平.一种飞行器在线航迹重规划算法[J].华中科技大学学报,2003,31(2):90-92. ZHENG Chang-wen,DING Ming-yue,ZHOU Cheng-pin.A new algorithm for aircraft online route re-planning[J].Journal of Huazhong University of Science and Technology,2003,31(2):90-92.(in Chinese)
[10] 周兰凤,洪炳熔.用基于知识的遗传算法实现移动机器人路径规划[J].电子学报,2006,34(5):911-914. ZHOU Lan-feng,HONG Bing-rong.A knowledge based genetic algorithm for path planning of a mobile robot[J].Acta Electronica Sinica,2006,34(5):911-914.(in Chinese)
[11] CHEN M,WU Q X,JIANG C S.A modified ant optimization algorithm for path planning of UCAV[J].Applied Soft Computation,2008,8(4):1712-1718.
[12] DUAN H B,ZHANG X Y,WU J.Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments[J].Journal of Bionic Engineering,2009,6(2):161-173.
[13] FU Y G,DING M Y,ZHOU C P.Routing planning for unmanned aerial vehicle(UAV)on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization[J].IEEE Transaction on Systems,Man,and Cybernetics:Systems,2013,43(6):1451-1465.
[14] 涂吉林,丁明跃,周成平.满足直飞限制二维航迹规划方法研究[J].电子学报,2000,28(3):87-89. TU Ji-lin,DING Ming-yue,ZHOU Cheng-ping.Research on 2D route planning approach constrainted for straight-flight[J].Acta Electronica Sinica,2000,28(3):87-89.(in Chinese)
[15] LAVALLE S M.Rapidly-Exploring Random Trees:A New Tool for Path Planning[R].Computer Science Department,Iowa State University,1998.
[16] 周金良,黄彦文,曹其新.对抗环境下足球机器人路径规划[J].上海交通大学学报,2006,40(11):1827-1831. ZHOU JiN-liang,HUANG Yan-wen,CAO Qi-xin.The path planning for robot soccer under antagonistic environment[J].Journal of Shanghai Jiaotong University,2006,40(11):1827-1831.(in Chinese)
[17] AMIN J N,BOSKOVIC J D,MEHRA R K.A fast and efficient approach to path planning for unmanned vehicles[A].Proceedings of AIAA Guidance,Navigation and Control Conference and Exhibit[C].Keystone,2006.
[18] KUFFNER J J,LAVALLE S M.RRT-connect:An efficient approach to single-query path planning[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].San Francisco:IEEE,2000:995-1001.
[19] URMSON C,SIMMONS R.Approaches for heuristically biasing RRT growth[A].Proceedings of the IEEE Conference on Intelligent Robots and Systems[C].Las Vegas,Nevada:IEEE,2003:1178-1183.
[20] 彭辉,王林,沈林成.区域搜索中基于改进RRT的UAV实时航迹规划[J].国防科学技术大学学报,2009,31(5):86-91. PENG Hui,WANG Lin,SHEN Lin-cheng.The modified RRT-based real-time route planning for UAV area target searching[J].Journal of National University of Defense Technology,2009,31(5):86-91.(in Chinese)
[21] YERSHOVA A,JAILLET L,SIMEON T.Dynamic-domain RRTs:Efficient exploration by controlling the sampling domain[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].Barcelona:IEEE,2005:3851-3861.
[22] DUBINS L.On curves of minimal length with a constraint on average curvature,and with prescribed initial and terminal position[J].American Journal of Math,1957,79(3):497-516.
[23] 宋金泽,戴斌,单恩忠等.一种改进的RRT路径规划算法[J].电子学报,2010,38(2A):225-228. SONG Jin-ze,DAI Bin,SHAN En-zhong.An improved RRT path planning algorithm[J].Acta Electronica Sinica,2010,38(2A):225-228.(in Chinese)

基于改进RRT算法的无人机航迹规划

An Improved RRT Algorithm for UAV Path Planning

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	樊凌雁, 燕武, 陈晞涵. 一种低传输能耗的无人机数据传输设计[J]. 电子学报, 2021, 49(3): 573-577.
[2]	张聪炫, 陈震, 熊帆, 黎明, 葛利跃, 陈昊. 非刚性稠密匹配大位移运动光流估计[J]. 电子学报, 2019, 47(6): 1316-1323.
[3]	王巍, 彭力, 赵继军, 常存喜, 黄晓丹, 田立勤. 移动物联网非完整约束中继的协同任务规划[J]. 电子学报, 2019, 47(6): 1251-1259.
[4]	柳强, 何明, 刘锦涛, 牛彦杰, 黄倩. 无人机“蜂群”的蜂拥涌现行为识别与抑制机理[J]. 电子学报, 2019, 47(2): 374-381.
[5]	徐恒舟, 朱海, 朱思峰, 余忠洋. 一种宽范围低复杂度的载波频偏估计算法[J]. 电子学报, 2019, 47(12): 2550-2555.
[6]	薛塬, 苏伟, 王洪超, 杨冬. 支持异步TDOA测量的确定性定位网络[J]. 电子学报, 2019, 47(10): 2017-2024.
[7]	高杨, 李东生, 柳向. 无人机集群协同态势觉察一致性评估[J]. 电子学报, 2019, 47(1): 190-196.
[8]	韩博文, 姚佩阳, 钟赟, 丁云松, 刘子震. 基于QABC-IFMADM算法的有人/无人机编队作战威胁评估[J]. 电子学报, 2018, 46(7): 1584-1592.
[9]	王巍, 赵继军, 彭力, 黄晓丹, 李林茂, 魏丁丁. 基于UAV的移动物联网远距离通信节能策略研究[J]. 电子学报, 2018, 46(12): 2914-2922.
[10]	张美玉, 张倩颖, 孟子琪, 施智平, 关永. 实时嵌入式双操作系统架构研究综述[J]. 电子学报, 2018, 46(11): 2787-2796.
[11]	韩博文, 姚佩阳, 孙昱. 基于多目标MSQPSO算法的UAVS协同任务分配[J]. 电子学报, 2017, 45(8): 1856-1863.
[12]	陈宝华, 邓磊, 陈志祥, 段岳圻, 周杰. 基于即时稠密三维重构的无人机视觉定位[J]. 电子学报, 2017, 45(6): 1294-1300.
[13]	张华美, 张业荣, 王芳芳. 墙体参数未知时的穿墙雷达实时成像方法[J]. 电子学报, 2016, 44(7): 1613-1618.
[14]	王伟, 余玉揆, 郝燕玲. 一种新型混合并行粒子滤波频率估计方法[J]. 电子学报, 2016, 44(3): 740-746.
[15]	李岩山;裴继红;谢维信;李良群. 一种新的无人机航拍序列图像快速拼接方法[J]. 电子学报, 2012, 40(5): 935-940.