留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于改进RRT算法的狭长空间无人车辆路径规划

张俊豪 潘树国 高旺 郭芃 王萍 胡鹏

张俊豪, 潘树国, 高旺, 郭芃, 王萍, 胡鹏. 基于改进RRT算法的狭长空间无人车辆路径规划[J]. 全球定位系统, 2023, 48(4): 81-90. doi: 10.12265/j.gnss.2023090
引用本文: 张俊豪, 潘树国, 高旺, 郭芃, 王萍, 胡鹏. 基于改进RRT算法的狭长空间无人车辆路径规划[J]. 全球定位系统, 2023, 48(4): 81-90. doi: 10.12265/j.gnss.2023090
ZHANG Junhao, PAN Shuguo, GAO Wang, GUO Peng, WANG Ping, HU Peng. Path planning of unmanned vehicles in narrow and long space based on improved RRT algorithm[J]. GNSS World of China, 2023, 48(4): 81-90. doi: 10.12265/j.gnss.2023090
Citation: ZHANG Junhao, PAN Shuguo, GAO Wang, GUO Peng, WANG Ping, HU Peng. Path planning of unmanned vehicles in narrow and long space based on improved RRT algorithm[J]. GNSS World of China, 2023, 48(4): 81-90. doi: 10.12265/j.gnss.2023090

基于改进RRT算法的狭长空间无人车辆路径规划

doi: 10.12265/j.gnss.2023090
基金项目: 国家重点研发计划(2021YFB3900804)
详细信息
    作者简介:

    张俊豪:(2001—),男,硕士研究生,研究方向为导航感知与路径规划

    潘树国:(1975—),男,博士,教授,研究方向为高精度 GNSS 卫星定位、智能体环境感知与自主导航、多源融合泛在智能导航定位、高精度动态定位检定与溯源

    高旺:(1989—),男,博士,副教授,研究方向为多源融合高精度导航定位

    通讯作者:

    潘树国 E-mail: psg@seu.edu.cn

  • 中图分类号: P228.4

Path planning of unmanned vehicles in narrow and long space based on improved RRT algorithm

  • 摘要: 针对狭长空间无人车辆路径规划系统,提出一种基于改进的快速搜索随机树(rapidly-exploring random trees,RRT)路径规划算法,以解决传统RRT算法随机性较大、路径缺乏安全性的问题. 该算法通过加入自适应目标概率采样策略、动态步长策略对传统的RRT算法进行改进,同时考虑到实际情况中无人驾驶车辆的动力学约束,该算法加入车辆碰撞约束和路径转角约束,并针对转角约束会导致迭代次数激增的问题提出了一种限制区域内随机转向的策略,最终得到一条安全性较高的路径. 采用计算机仿真对所提算法和现有算法的性能进行对比验证. 所提算法在狭长空间相较于传统人工势场引导下的RRT算法迭代次数降低了33.09%,规划时间减少了6.44%,路径长度减少了0.06%,并且在简单环境和复杂障碍物环境下规划能力均有提升. 所提算法规划效率更高、迭代次数更少.

     

  • 图  1  APF-RRT算法示意图

    图  2  APF-RRT算法流程图

    图  3  动态步长策略示意图

    图  4  步长较大时两节点连线与障碍物相交

    图  5  路径转角

    图  6  限制区域随机转向策略示意图

    图  7  改进RRT算法流程图

    图  8  不同初始最大步长下算法的实验结果折线图

    图  9  不同最大迭代次数下算法的实验结果折线图

    图  10  简单环境下不同算法所得路径图

    图  11  复杂障碍物环境下不同算法所得路径图

    图  12  狭长空间下不同算法所得路径图

    图  13  狭长空间(极端狭窄)下不同算法所得路径图

    表  1  简单环境下不同算法实验结果数据

    算法平均
    迭代次数
    平均
    路径长度
    平均
    规划时间/s
    成功率/%
    APF-RRT120.6429.285 10.206 3100
    改进RRT 78.4227.852 90.122 4100
    约束条件下APF-RRT373.0529.148 20.430 5100
    约束条件下改进RRT207.0228.499 60.368 1100
    下载: 导出CSV

    表  2  复杂障碍物环境下不同算法实验结果数据

    算法平均
    迭代次数
    平均
    路径长度
    平均
    规划时间/s
    成功率/%
    APF-RRT145.6529.205 00.250 1100
    改进RRT122.1528.022 00.243 3100
    约束条件下APF-RRT542.8530.425 61.524 3100
    约束条件下改进RRT477.7828.877 31.511 3100
    下载: 导出CSV

    表  3  狭长空间下不同算法实验结果数据

    算法平均迭代次数平均路径长度平均规划时间/s成功率/%
    APF-RRT 981.3529.642 70.183 4100
    改进RRT 630.7129.613 20.203 1100
    约束条件下APF-RRT1761.9531.758 71.557 1100
    约束条件下改进RRT1178.9331.738 11.456 9100
    下载: 导出CSV

    表  4  狭长空间(极端狭窄)下不同算法实验结果数据

    算法 平均
    迭代次数
    平均
    路径长度
    平均
    规划时间/s
    成功率/%
    约束条件下RRT - - - 0
    约束条件下APF-RRT 5 972.00 33.045 4 5.260 0 2
    约束条件下改进RRT 5 708.85 34.212 2 9.801 7 55
    下载: 导出CSV
  • [1] 王鹤静, 王丽娜. 机器人路径规划算法综述[J/OL]. 桂林理工大学学报, 2023, 43(1): 137-147.
    [2] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The international journal of robotics research, 2011, 30(7): 846-894. DOI: 10.1109/ICRA.2014.6907642
    [3] 彭君. 改进RRT算法在移动机器人路径规划中的应用研究[D]. 南京: 南京邮电大学, 2022.
    [4] ZUCKER M, KUFFNER J, BRANICKY M S. Multipartite RRTs for rapidreplanning in dynamic environments[C]//IEEE International Conference on Robotics and Automation, 2007: 1603-1609. DOI: 10.1109/ROBOT.2007.363553
    [5] OTTE M W, FRAZZOLI E. RRTX: Asymptotically optimal single-querysampling-based motion planning with quick replanning[J]. The international journal of robotics research, 2016, 35(7): 797-822. DOI: 10.1177/0278364915594679
    [6] YANG Y, ZHANG L, GUO R H, et al. Path planning of mobile robot based on improved RRT algorithm[C]//Chinese Automation Congress (CAC), 2019: 4741-4746. DOI: 10.1109/CAC48633.2019.8996415
    [7] QI J, YANG H, SUN H X. MOD-RRT*: a sampling-based algorithm for robot path planning in dynamic environment[J]. IEEE transactions on industrial electronics, 2020, 68(8): 7244-7251. DOI: 10.1109/TIE.2020.2998740
    [8] WANG X Y, LI X J, GUAN Y, et al. Bidirectional potential guided RRT* for motion planning[J]. IEEE access, 2019(7): 95046-95057. DOI: 10.1109/ACCESS.2019.2928846
    [9] WU Z P, MENG Z, ZHAO W L, et al. Fast-RRT: a RRT-based optimal path finding method[J]. Applied sciences, 2021, 11(24): 11777. DOI: 10.3390/app112411777
    [10] WANG J K, LI B P, MENG M Q H. Kinematic constrained Bi-directional RRT with efficient branch pruning for robot path planning[J]. Expert systems with applications, 2021(170): 114541. DOI: 10.1016/j.eswa.2020.114541
    [11] LI Y J, WEI W, GAO Y, et al. PQ-RRT*: an improved path planning algorithm for mobile robots[J]. Expert systems with applications, 2020(152): 113425. DOI: 10.1016/j.eswa.2020.113425
    [12] YUAN C G, LIU G F, ZHANG W G, et al. An efficient RRT cache method in dynamic environments for path planning[J]. Robotics and autonomous systems, 2020(131): 103595. DOI: 10.1016/j.robot.2020.103595
    [13] 田小壮, 石辉, 刘家辛, 等. 复杂环境下无人机智能巡检轨迹规划方法研究[J]. 电子设计工程, 2021, 29(20): 77-81. DOI: 10.14022/j.issn1674-6236.2021.20.016
    [14] 董敏, 陈铁桩, 杨浩. 基于改进 RRT 算法的无人车路径规划仿真研究[J]. 计算机仿真, 2019, 36(11): 96-100.
    [15] 张兰勇, 韩宇. 基于改进的 RRT* 算法的 AUV 集群路径规划研究[J]. 中国舰船研究, 2023, 18(1): 43-51.
    [16] 李犇, 褚伟. 基于改进 RRT 与人工势场法的机器人路径规划[C]//中国生物医学工程学会血液疗法与工程分会第七届学术大会暨UBIO疗法专题研讨会, 2021.
    [17] 王海群, 王水满, 张怡, 等. 未知环境的移动机器人路径规划研究[J]. 机械设计与制造, 2021, 368(10): 233-235, 240. DOI: 10.19356/j.cnki.1001-3997.2021.10.052
  • 加载中
图(13) / 表(4)
计量
  • 文章访问数:  204
  • HTML全文浏览量:  80
  • PDF下载量:  25
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-04-17
  • 录用日期:  2023-04-17
  • 网络出版日期:  2023-08-22

目录

    /

    返回文章
    返回