Abstract: To solve the problems that the Rapidly-exploring Random Tree (RRT) path planning is unstable and not taking cost into consideration, an anytime RRT Algorithm was proposed. The algorithm produced an initial solution very quickly, and then improved its growth by reusing information from the previous trees. Besides, to improve the algorithm, a biased distribution was produced to save the cost by using a waypoint cache. The resulted approach produced an initial solution very quickly, and then improved the quality of this solution within given time. It was guaranteed that subsequent solution would be less costly than all previous ones by using the bound. In the biped robot's simulation experiment, compared to the initial algorithm, the number of search nodes created by the improved algorithm decreases from 883 to 704 and the efficiency increases approximately 25%. The simulation result demonstrates the effectiveness of the improved algorithm.

Key words: Rapidly-exploring Random Tree (RRT), path planning, biped robot, anytime algorithm, cost

摘要： 针对快速探索随机树(RRT)算法进行路径规划时随机性大且未考虑移动代价的问题，提出了任意时间快速探索随机树算法。生成一组快速探索随机树，之后每个树都重新使用上个树的信息来不断改进树的延伸。为进一步优化算法，使用节点缓存来生成一个引力函数来减少移动代价。最终的算法能够快速地生成初始路径，在规划时间内不断地改进路径且通过使用阈值来确保后面路径都比上次的移动代价更小。双足机器人仿真实验中，改进后的算法与初始的算法相比，搜索的节点数由883减少到704，效率提高了近25%。实验结果表明了改进算法的有效性。

关键词: 快速搜索随机树, 路径规划, 双足机器人, 任意时间算法, 移动代价