改进A*算法与动态窗口法的机器人动态路径规划

Improved A* Algorithm and DynamicWindow Method for Robot Dynamic Path Planning

针对传统A*算法自身节点搜索策略存在路径转折点多、转折角度大、可行路径不是理论上的最优路径等缺点,将传统A*算法3×3的搜索邻域扩展为7×7,同时去除扩展邻域同方向的多余子节点,改进为7×7的A*算法,消除了传统A*算法的3×3邻域搜索和节点移动方向仅为0.25π的整数倍的限制,优化了搜索角度。其次,针对移动机器人在复杂环境下动态路径规划问题,将改进7×7的A*算法与动态窗口算法进行融合,设计了一种全局最优路径的动态窗口评价函数,综合考虑移动速度、转角平滑度、安全性等因素,将改进7×7的A*算法与动态窗口法的融合算法与多种算法仿真比较,结果表明:改进7×7的A*算法与动态窗口法的融合算法更具有高效性和可行性。

In view of the disadvantages of traditional A*algorithm’s own node search strategy,such as many path turning points,large turning angles,and feasible paths that are not theoretically optimal paths,the traditional A*algorithm 3×3 search neighborhood is expanded to 7×7,at the same time the redundant sub-nodes in the same direction in the extended neighborhood are removed and it is improved to the 7×7 A*algorithm,eliminating the traditional A*algorithm’s 3×3 neighborhood search and the restriction that the node moving direction is only an integer multiple of 0.25π,and the search angle is optimized.Secondly,for the problem of dynamic path planning of mobile robots in complex environments,the improved 7×7 A*algorithm and dynamic window algorithm are combined,and a dynamic window evaluation function of the global optimal path is designed,taking into account the moving speed and turning angle.For factors such as smoothness and security,the fusion algorithm of the improved 7×7 A*algorithm and the dynamic window method is compared with a variety of algorithm simulations.The results show that the improved 7×7 A*algorithm and the fusion algorithm of the dynamic window method are better.It is highly efficient and feasible.