基于分层改进D^＊算法的室内路径规划

Indoor path planning based on improved hierarchical D ^＊ algorithm

提出了一种基于部分已知室内环境的移动机器人路径规划方法。针对D*算法搜索空间较大的问题,引入抽象分层思想,将室内环境结构化为层次图并设置关键节点,将关键节点作为局部目标节点,分段进行路径搜索;为提高在线路径规划效率,利用Voronoi图理论离线生成关键节点间的先验安全路径;为降低路径的时间成本,在扩展节点过程中考虑扩展的方向性,且用对角函数对D*算法的路径代价函数进行改进。仿真结果表明,在较复杂的环境中,算法能较迅速地规划出优化路径,且能安全避碰。

This paper presented an approach to path planning for mobile robot under indoor environment partly known. In order to compress the searching space of D^ ＊ algorithm, the method structured indoor environment into hierarchical graph using abstraction hierarchies and placed key path nodes in each hierarchical level. Regarding key path nodes as partial target nodes, the method obtained the global optimal path by searching sectionally. For improving the efficiency of online path planning, it generated the pre-caleulated safe paths connecting key path nodes using Voronoi diagram theory. In order to decrease the time cost of paths,it considered the directivity in the process of extension and improved the path cost function of D^ ＊ algorithm using diagonal function. Theoretical and simulation results show that the algorithm can plan the optimal path quickly and avoid collision safely at the same time in complex environment.