基于多策略融合的改进RRT路径规划算法

An improved RRT algorithm for path planning based on multi-strategy fusion

针对传统快速扩展随机树(RRT)及其衍生算法在路径规划时生成路径效率较低、无效探索点较多等问题,提出一种多策略融合的改进RRT算法。首先利用启发式选择策略确定最合适的扩展节点,然后结合基于目标偏置的自适应动态步长策略,使随机树始终向目标点区域扩展,最后通过垂距断点预优化的跳点连线策略去除冗余点,生成一条没有较大转折角的最短安全路径。通过不同复杂程度的仿真实验和现实环境实验对该算法进行测试。结果表明,与RRT、RRT*和Bi-RRT*算法相比,本文算法在时间消耗上分别减少了大约80%、50%和60%,在路径节点数上分别减少了大约65%、40%和35%。机器人依据该算法可以高效生成一条无碰撞,仅包含起始点、目标点和非突兀转折点的最优路径。

An improved RRT algorithm based on multi-strategy fusion was presented to address the problems of poor path generation efficiency and multiple invalid search points during path planning of robots via classical rapidly-exploring random tree(RRT)and its derivative algorithms.Firstly,a heuristic stra-tegy was introduced to select the most suitable extension node.Then an adaptive dynamic step strategy with target bias considered was combined to expand the random tree towards the target point region.Finally,the jump point connection strategy pre-optimized by vertical distance breakpoints was used to remove the redundant points and create a shortest safe path without large turning angles.This algorithm was tested by simulation experiments and actual experiments with different degrees of complexity.The results show that,compared with RRT,RRT*and Bi-RRT*algorithms,the proposed method reduces the time consumption by about 80%,50%and 60%,and the number of path nodes by about 65%,40%and 35%,respectively.By using this algorithm,the robots can efficiently generate an optimal path without collision,including only the start point,the target point and non-abrupt turning points.