基于转折点优化算法的移动机器人路径规划研究

Mobile Robot Path Planning Based on Turning Point Optimization Algorithm

摘要:

为提升自主移动设备在复杂环境下的适应能力,解决传统A?算法路径规划时存在搜索时间长、转折点多和路径平滑度差等问题,提出基于A?的转折点优化算法TP-A?。该算法首先在A?算法的基础上,采用对角线距离作为启发函数并完成动态加权,保证算法前期以搜索速度为主,后期以搜索最优路径为主,从而提升自主移动设备的路径规划效率。其次,为了提升自主移动设备的效率和稳定性,采用“两过程、两准则和一个判断机制”完成路径优化。在普通栅格、复杂栅格、狭窄通道、迷宫4种场景下比较了机器人在A?、JPS、TP-A?3种算法中的运行情况,仿真结果表明:所提出的TP-A?算法在平均规划时间、路径长度、路径节点数以及转折点数等方面均优于其他算法。最后,基于Turtlebot2 机器人平台完成了室内全局代价地图的创建,比较了A?算法和TP-A?算法在实际运行过程中的应用效果,实验结果表明:所提出的TP-A?算法相比于传统的A?算法不仅路径更为平滑,且在寻路时间和路径长度上分别减少了88.53%和21.99%,验证了所提算法的有效性。

Abstract:

In order to improve the adaptability of autonomous mobile devices in complex environments and solve the problems of long search time, multiple turning points and poor path smoothness existing in traditional A?algorithm path planning, a turning point optimization algorithm TP-A? based on A? was proposed. Based on A? algorithm, diagonal distance was used as heuristic function and dynamic weighting was completed, which ensured that the algorithm focused on searching speed in the early stage and searching optimal path in the late stage, thus improving the path planning efficiency of autonomous mobile devices. Secondly, in order to improve the efficiency and stability of autonomous mobile devices, path optimization was completed by using “two processes, two criteria and one judgment mechanism”. The performances of A?, JPS and TP-A? algorithms were compared in four scenarios: ordinary grid, complex grid, narrow passage and maze. The simulation results showed that the proposed TP-A? algorithm was superior to other algorithms in average planning time, path length, number of path nodes and turning points. Finally, the indoor global cost map was created based on Turtlebot2 robot platform, and the application effect of A? algorithm and TP-A? algorithm in the actual operation process was compared. Experimental results showed that the proposed TP-A? algorithm not only had smoother path than the traditional A? algorithm, but also reduced the path-finding time and path length by 88.53% and 21.99%, respectively, which verified the effectiveness of the proposed algorithm.