Abstract：An improved path planning algorithm is proposed by combining rapidly-exploring random tree (RRT) and rolling path planning. In this algorithm, the real-time local environment information detected by the robot is fully used and the on-line planning is performed in a rolling style. Therefore, the RRT algorithm can be used in both known and unknown environment. Only the local environmental map is calculated in the planning to improve the planning efficiency, and thus the planning in real time is guaranteed. The calculation of analytical expressions of the obstacle can be ignored. Hence, the memory is saved greatly. Based on the algorithm of rapidly-exploring random, the heuristic evaluation function is introduced into the improved algorithm, so that the exploring random tree can grow in the direction of target point. The regression analysis, which avoids local minimum, enhances the capability of searching unknown space. The simulation results verify the effectiveness of the improved algorithm.
康亮，赵春霞，郭剑辉. 未知环境下改进的基于RRT算法的移动机器人路径规划*[J]. 模式识别与人工智能, 2009, 22(3): 337-343.
KANG Liang, ZHAO Chun-Xia, GUO Jian-Hui. Improved Path Planning Based on Rapidly-Exploring Random Tree for Mobile Robot in Unknown Environment. , 2009, 22(3): 337-343.
[1] Cai Zhixing, He Hanggen, Chen Hong. Some Issues for Mobile Robot Navigation under Unknown Environments. Control and Decision, 2002, 17(4): 385-390 (in Chinese) (蔡自兴,贺汉根,陈 虹.未知环境下移动机器人导航控制研究的若干问题.控制与决策, 2002, 17(4): 385-390) [2] LaValle S M. Planning Algorithms. Illinois, USA: University of Illinois Press, 2004 [3] LaValle S M. Rapidly-Exploring Random Trees: A New Tool for Path Planning. Technical Report, TR98-11, Ames, USA: Iowa State University. Department of Computer Science, 1998 [4] LaValle S M, Kuffner J. Rapidly-Exploring Random Trees: Progress and Prospects // Proc of the International Workshop on Algorithmic Foundations of Robotics. Hanover, USA, 2000: 45-59 [5] Zhang Chungang, Xi Yugeng. Rolling Path Planning and Safety Analysis of Mobile Robot in Dynamic Uncertain Environment. Control Theory and Applications, 2003, 20(1): 37-44 (in Chinese) (张纯刚,席裕庚.动态未知环境中移动机器人的滚动路径规划及安全性分析.控制理论与应用, 2003, 20(1): 37-44) [6] Laumond J P, Sekhavat S, Lamiraux F. Guidelines in Nonholonomic Motion Planning for Mobile Robots. Lectures Notes in Control and Information Sciences, 1998, 229: 1-53 [7] Melchior N A, Simmons R. Particle RRT for Path Planning with Uncertainty // Proc of the IEEE International Conference on Robotics and Automation. Roma, Italy, 2007: 1617-1624 [8] Kuffner J J Jr, LaValle S M. RRT-Connect: An Efficient Approach to Single-Query Path Planning // Proc of the IEEE International Conference on Robotics and Automation. San Francisco, USA, 2000, Ⅱ: 995-1001 [9] Cheng Peng. Reducing RRT Metric Sensitivity for Motion Planning with Differential Constraints. Master Dissertation. Ames, USA: Iowa State University. Graduate College, 2001 [10] de Smith J. Distance and Path: The Development, Interpretation and Application of Distance Measurement in Mapping and Modeling. Ph.D Dissertation. London, UK: University of London, 2003 [11] AlDahak A, Elnagar A. A Practical-Evasion Algorithm: Detection and Tracking // Proc of the IEEE International Conference on Robotics and Automation. Roma, Italy, 2007: 343-348 [12] Urmson C. Locally Randomized Kinodynamic Motion Planning for Robots in Extreme Terrain. Ph.D Dissertation. Pittsburgh, USA: Carnegie Mellon University. Robotics Institute, 2002 [13] Xi Yugeng. Predictive Control of General Control Problems under Dynamic Uncertain Environment. Control Theory and Applications, 2007, 17(5): 665-670 (in Chinese) (席裕庚.动态不确定环境下广义控制问题的预测控制.控制理论与应用, 2007, 17(5): 665-670) [14] Tang Zhenmin, Zhao Chunxia, Yang Jingyu, et al. Local Trajectory Planning for Autonomous Land Vehicles, Robot, 2001, 23(7): 742-745 (in Chinese) (唐振民,赵春霞,杨静宇,等.地面自主机动平台的局部路径规划.机器人, 2001, 23(7): 742-745) [15] Kalisiak M, van de Panne M. RRT-Blossom RRT with a Local Flood-Fill Behavior // Proc of the IEEE International Conference on Robotics and Automation. Orlando, USA, 2006: 1237-1242 [16] Sugihara K, Smith J. Genetic Algorithms for Adaptive Motion Planning of an Autonomous Mobile Robot // Proc of the IEEE International Symposium on Computational Intelligence in Robotics and Automation. Monterey, USA, 1997: 138-143 [17] Howie C, Joel B. Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph. The International Journal of Robotics Research, 2000, 19(2): 126-145 [18] Agirrebeitia J, Avilés R, de Bustos I F, et al. A New APF Strategy for Path Planning in Environments with Obstacles. Mechanism and Machine Theory, 2005, 40(6): 645-658 [19] Ettlin A, Bleuler H. Randomized Rough-Terrain Robot Motion Planning // Proc of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Beijing, China, 2006: 5798-5803
2009, Vol. 22 
