变概率双向RRT改进路径规划算法

doi:10.16180/j.cnki.issn1007-7820.2019.06.004

摘要/Abstract

摘要：

针对RRT算法收敛速度慢、路径不规则的问题,基于双向RRT算法和概率搜索策略,提出了一种变概率策略下的双向RRT搜索优化算法。该算法根据搜索节点的不同周边状态,采用不同的概率策略扩展目标点,使搜索算法能够在空旷场景下向目标点快速生成,同时避免了路径陷入局部最小值的问题。在完成初次路径搜索后,根据路径节点位置优化不规则路线,减少小车行驶过程中的拐弯次数和总路径长度。在仿真中进行了多场景重复试验测试,仿真结果表明,改进后的算法在搜索速度和路径长度上有明显改善。

关键词: 智能车, 路径规划, 双向RRT, 概率搜索, 收敛速度, 路径不规则

Abstract:

To deal with the problems of slow convergence speed and the irregular searching path of the RRT algorithm, a variable probability search strategy optimization algorithm based on the bidirectional RRT was proposed. This bidirectional RRT algorithm searched different surrounding states of nodes, then extended the target point with different probability strategies. Therefore, this algorithm could rapidly converge to the target in the open environment as well as avoid falling into local minimum. After the initial path search was completed, the irregular route was optimized according to the location of the path node, and the number of turning times during the car driving and the length of the total path were effectively reduced.The multi scene repeated test was carried out in the simulation, and the simulation results showed that this algorithm had a significant improvement in the search speed and path length.

Key words: intelligent vehicle, path planning, bidirectional RRT, probability search, convergence speed, irregular searching path

中图分类号:

TP242

胡浍冕. 变概率双向RRT改进路径规划算法[J]. 电子科技, 2019, 32(6): 16-21.

HU Huimian. An Improved Path Planning Algorithm With Variable Probability Bidirectional RRT[J]. Electronic Science and Technology, 2019, 32(6): 16-21.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

表1

参考文献 16

[1]	LaValle S M . Rapidly-exploring random trees: A new tool path planning[D]. Ames: Iowa State University, 1998.
[2]	刘华军, 杨静宇, 陆建峰 , 等. 移动机器人运动规划研究综述[J]. 中国工程科学, 2006,8(1):85-94.
	Liu Huajun, Yang Jingyu, Lu Jianfeng , et al. Research on mobile robots motion planning: A survey[J]. Engineering Science, 2006,8(1):85-94.
[3]	康亮, 赵春霞, 郭剑辉 . 基于模糊滚动RRT 算法的移动机器人路径规划[J]. 南京理工大学学报:自然科学版, 2010,34(5):642-648.
	Kang Liang, Zhao Chunxia, Guo Jianhui . Path planning based on fuzzyrolling rapidly-exploring random tree for mobile robot[J]. Journalof Nanjing University of Science and Technology:Natural Science, 2010,34(5):642-648.
[4]	徐娜, 陈雄, 孔庆生 , 等. 非完整约束下的机器人运动规划算法[J]. 机器人, 2011,33(6):666-672.
	Xu Na, Chen Xiong, Kong Qingsheng , et al. Motion planning for robot with nonholonomic constraints[J]. Robot, 2011,33(6):666-672.
[5]	Kuffner J J, LaValle S M.RRT-connect: An efficient approach to single-query path planning [C].Piscataway:IEEE International Conference on Robotics and Automation, 2000.
[6]	Lau B, Sprunk C, Burgard W. Kinodynamic motion planning for mobile robots using splines [C].Piscataway:IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009.
[7]	Fraichard T, Scheuer A . From Reeds and Shepp’s to continuouscurvature paths[J]. IEEE Transactions on Robotics, 2004,20(6):1025-1035. doi: 10.1109/TRO.2004.833789
[8]	Cheng P . Reducing RRT metric sensitivity for motion planning with differential constraints[D]. Ames:Iowa State University, 2001.
[9]	Salzman O, Dan H . Asymptotically Near-Optimal RRT for fast, High-Quality motion planning[J]. IEEE Transactions on Robotics, 2016,32(3):473-483. doi: 10.1109/TRO.2016.2539377
[10]	Kuwata Y, Teo J, Fiore G , et al. Real-time motion planning with applications to autonomous urban driving[J]. IEEE Transactions on Control Systems Technology, 2009,17(5):1105-1118. doi: 10.1109/TCST.2008.2012116
[11]	Qureshi A H, Ayaz Y . Potential functions based sampling heuristic for optimal path planning[J]. Autonomous Robots, 2016,40(6):1079-1093. doi: 10.1007/s10514-015-9518-0
[12]	Chang An, Chang Jingang . Path planning for mobile robot based on an improved probabilistic roadmap method[J]. Chinese Journal of Electronics, 2009,18(3):395-399.
[13]	Rasekhipour Y, Khajepour A, Chen S K , et al. A potential field-based model predictive path-planning controller for autonomous road vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2017,18(5):1255-1267. doi: 10.1109/TITS.2016.2604240
[14]	宋金泽, 戴斌, 单恩忠 , 等. 一种改进的RRT 路径规划算法[J]. 电子学报, 2010,38(B02):225-228.
	Song Jinze, Dai Bin, Shan Enzhong , et al. An improved RRT path planning algorithm[J]. Acta Electronica Sinica, 2010,38(B02):225-228.
[15]	李怡弘, 裘炅 . 粒子群蚁群融合算法的火灾救援路径研究[J]. 电子科技, 2018,31(1):58-62.
	Li Yihong, Qiu Jiong . The particle swarm optimization algorithm merged with ant colony optimization algorithm of fire rescue way research[J]. Electronic Science and Technology, 2018,31(1):58-62.
[16]	Cui R, Li Y, Yan W . Mutual information-based Multi-AUV path planning for scalar field sampling using multidimensional RRT * [J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2017,46(7):993-1004.

空间图	A	B	C	D
原始RRT搜索时间/s	4.13	7.18	8.33	3.73
原始RRT路径长度	845	1301	1388	892
原始RRT节点个数	44.8	76.5	69.2	45.2
优化后RRT搜索时间/s	2.31	5.64	8.45	2.12
优化后RRT路径长度	722	1112	1191	742
优化后RRT节点个数	3.5	10.2	15.3	3.1