RRT-based Motion Planning Algorithm for Intelligent Vehicle in Complex Environments
DU Mingbo1,2, MEI Tao2, CHEN Jiajia2, ZHAO Pan2, LIANG Huawei2, HUANG Rulin1,2, TAO Xiang2
1. Department of Automation, University of Science and Technology of China, Hefei 230027, China;
2. Institute of Applied Technology, Hefei Institutes of Physical Science, Chinese Academy of Sciences, Hefei 230027, China
The existing planning algorithms can not properly solve the motion planning problem of intelligent vehicle in complex environments with many irregular and random obstacles. To solve the problem, a simple and practical RRT-based algorithm, continuous-curvature RRT algorithm, is proposed. This algorithm combines the environmental constraints and the constraints of intelligent vehicle with RRTs. Firstly, a goal-biased sampling strategy and a reasonable metric function are introduced to greatly increase the planning speed and quality. And then, a post-processing method based on the maximum curvature constraint is presented to generate a smooth, continuous-curvature and executable trajectory. Simulation experiments and real intelligent vehicle test verify the correctness, validity and practicability of this algorithm.
[1] 刘华军,杨静宇,陆建峰,等.移动机器人运动规划研究综述 [J].中国工程科学,2006,8(1):85-94. Liu H J, Yang J Y, Lu J F, et al. Research on mobile robots motion planning: A survey[J]. Engineering Science, 2006, 8(1): 85-94.[2] 康亮,赵春霞,郭剑辉.基于模糊滚动 RRT 算法的移动机器人路径规划 [J].南京理工大学学报:自然科学版,2010,34(5):642-648. Kang L, Zhao C X, Guo J H. Path planning based on fuzzy rolling rapidly-exploring random tree for mobile robot[J]. Journal of Nanjing University of Science and Technology: Natural Science, 2010, 34(5): 642-648.[3] 宋金泽,戴斌,单恩忠,等.一种改进的 RRT 路径规划算法 [J].电子学报,2010,38(B02):225-228. Song J Z, Dai B, Shan E Z, et al. An improved RRT path planning algorithm[J]. Acta Electronica Sinica, 2010, 38(B02): 225-228.[4] 徐娜,陈雄,孔庆生,等.非完整约束下的机器人运动规划算法 [J].机器人,2011,33(6):666-672. Xu N, Chen X, Kong Q S, et al. Motion planning for robot with nonholonomic constraints[J]. Robot, 2011, 33(6): 666-672.[5] 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. [6] Fraichard T, Scheuer A. From Reeds and Shepp's to continuous-curvature paths[J]. IEEE Transactions on Robotics, 2004, 20(6): 1025-1035. [7] Elbanhawi M, Simic M. Randomised kinodynamic motion planning for an autonomous vehicle in semi-structured agricultural areas[J]. Biosystems Engineering, 2014, 126: 30-44.[8] Elbanhawi M, Simic M, Jazar R. Continuous-curvature bounded trajectory planning using parametric splines[M]//Frontiers in Artificial Intelligence and Applications, vol.262. Amsterdam, Netherlands: IOS Press, 2014: 513-522.[9] Gómez-Bravo F, Cuesta F, Ollero A, et al. Continuous curvature path generation based on β -spline curves for parking manoeuvres[J]. Robotics and Autonomous Systems, 2008, 56(4): 360-372. [10] Du M B, Chen J J, Zhao P, et al. An improved RRT-based motion planner for autonomous vehicle in cluttered environments[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 2014: 4674-4679.[11] Lee J, Kwon O, Zhang L, et al. SR-RRT: Selective retraction-based RRT planner[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 2012: 2543-2550.[12] Rodriguez S, Tang X, Lien J M, et al. An obstacle-based rapidly-exploring random tree[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 2006: 895-900.[13] LaValle S M, Kuffner J J. Rapidly-exploring random trees: Progress and prospects[C]//4th International Workshop on Algorithmic Foundations of Robotics. Wellesley, USA: A K Peters, 2000: 293-308.[14] Kuffner J J Jr, LaValle S M. RRT-connect: An efficient approach to single-query path planning[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 2000: 995-1001.[15] Lau B, Sprunk C, Burgard W. Kinodynamic motion planning for mobile robots using splines[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway, USA: IEEE, 2009: 2427-2433.[16] Koyuncu E, Inalhan G. A probabilistic B-spline motion planning algorithm for unmanned helicopters flying in dense 3D environments[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway, USA: IEEE, 2008: 815-821.[17] Cheng P. Reducing RRT metric sensitivity for motion planning with differential constraints[D]. Ames, USA: Iowa State University, 2001.[18] LaValle S M. Rapidly-exploring random trees: A new tool path pla