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%，并且在简单环境和复杂障碍物环境下规划能力均有提升. 所提算法规划效率更高、迭代次数更少.
-
关键词:
- 快速搜索随机树(RRT) /
- 自适应目标概率采样 /
- 动态步长 /
- 路径约束 /
- 随机转向策略
Abstract: A path planning algorithm based on improved rapidly-exploring random trees (RRT) is proposed for the path planning system of unmanned vehicles in narrow and long space, which solves the problems of large randomness and lack of safety of the traditional RRT algorithm. The algorithm improves the traditional RRT algorithm by adding adaptive target probability sampling strategy and dynamic step size strategy. At the same time, considering the dynamics constraints of driverless vehicles in the actual situation, the algorithm adds vehicle collision constraints and path angle constraints, and proposes a random turning strategy within the restricted area to solve the problem that the angle constraints will lead to the multiplication of iterations, and a path with higher safety is finally obtained. The performance of the proposed algorithm is compared with existing algorithms by computer simulation. Compared with the traditional RRT algorithm guided by artificial potential field in narrow and long space, the iteration times, planning time and path length of the proposed algorithm are reduced by 33.09%, 6.44% and 0.06%, and the planning ability of the proposed algorithm is improved in both simple environment and dense obstacle environment. The proposed algorithm has higher planning efficiency and fewer iteration . -
表 1 简单环境下不同算法实验结果数据
算法 平均
迭代次数平均
路径长度平均
规划时间/s成功率/% APF-RRT 120.64 29.285 1 0.206 3 100 改进RRT 78.42 27.852 9 0.122 4 100 约束条件下APF-RRT 373.05 29.148 2 0.430 5 100 约束条件下改进RRT 207.02 28.499 6 0.368 1 100 
下载: 导出CSV
表 2 复杂障碍物环境下不同算法实验结果数据
算法 平均
迭代次数平均
路径长度平均
规划时间/s成功率/% APF-RRT 145.65 29.205 0 0.250 1 100 改进RRT 122.15 28.022 0 0.243 3 100 约束条件下APF-RRT 542.85 30.425 6 1.524 3 100 约束条件下改进RRT 477.78 28.877 3 1.511 3 100
下载: 导出CSV
表 3 狭长空间下不同算法实验结果数据
算法 平均迭代次数 平均路径长度 平均规划时间/s 成功率/% APF-RRT 981.35 29.642 7 0.183 4 100 改进RRT 630.71 29.613 2 0.203 1 100 约束条件下APF-RRT 1761.95 31.758 7 1.557 1 100 约束条件下改进RRT 1178.93 31.738 1 1.456 9 100
下载: 导出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)
计量
- 文章访问数: 177
- HTML全文浏览量: 70
- PDF下载量: 22
- 被引次数: 0
