一种改进的移动机器人路径规划算法

An Improved Path Planning Algorithm for Mobile Robots

为解决快速随机扩展树算法(RRT)无效采样以及路径不最优等问题,提出一种基于RRT和A^(*)算法的拟水流避障算法RRT-QSA^(*)。在采样上引入RRT算法规定采样区间来限制采样点,增强采样的目标导向性;遇到障碍物时采用融合了A*算法的拟水流避障算法迅速绕过障碍物;采用路径优化算法对搜索到的路径进行路径优化。仿真结果表明:与RRT算法相比,RRT-QSA^(*)算法的计算时间减少了96.83%~99.88%,搜索节点数减少了86.62%~96.01%,路径长度数减少了9.9%~16.7%,转折角度减少了80.93%~93.04%。随着地图的增大,RRT-QSA^(*)算法比RRT算法计算效率的提升更加明显。

To solve the problems of invalid sampling and non-optimal paths of the RRT,the quasi-stream avoidance algorithm is proposed.The RRT algorithm is introduced to specify the sampling interval to limit the sampling points and enhance the goal-oriented nature of sampling.The quasi-stream avoidance algorithm incorporating the A^(*)algorithm(QSA^(*))is used to quickly bypass the obstacle when it is encountered.A path optimization algorithm is used to smooth the searched path.The simulation results show that compared with the RRT algorithm,the computation time of the RRT-QSA^(*)algorithm is reduced by 96.83%~99.88%,the number of search nodes is reduced by 86.62%~96.01%,the number of path lengths is reduced by 9.9%~16.7%,and the turning angle decreased by 80.93%~93.04%.The RRTQSA^(*)algorithm shows a more intense improvement in computational efficiency than the RRT algorithm as the map size increases.