Abstract: A hierarchical path planning method was proposed based on a hybrid topology-grid-metric map for mobile robots, to deal with the problems of large search space, inefficiency and low success rate of obstacle avoidance for traditional path-planning methods in a partially unknown, complex, large-scene environment. Firstly, the robot operation environments were described as a grid map and divided into several grid sub-maps. The topological framework was obtained by extracting the location relation of the sub-maps as the key nodes, and the local region of grid maps was represented elaborately to construct a hybrid topology-grid-metric map. Then, the robot’s path was planned hierarchically in the different regions of the hybrid map. Floyd algorithm was used to plan the interregional path between sub-regions on the topology map. An improved A* algorithm was proposed to search the intraregional paths of each sub-map for the grid map. The filtering strategy of extension points, the mechanism of bidirectional search, and the elimination technique of redundant waypoints were introduced to improve the efficiency and quality of path planning. And the globally optimized initial path was generated by merging several interregional and intraregional paths. Finally, a dynamic obstacle-avoidance path planning method was proposed based on the deep reinforcement learning framework for the dynamic obstacles in a partly unknown environment on the metric map. In the framework, the mechanism of value-classified experience replay was devised to increase the utilization of experience samples and the efficiency of model training. The experimental results demonstrate that the proposed method has the high path-search efficiency and obstacle-avoidance success rate, and the generated paths are both safe and smooth.

Key words: hybrid map, mobile robot, path planning, improved A* algorithm, reinforcement learning

摘要： 针对传统路径规划方法在部分未知复杂大场景环境下搜索空间大、效率低、避障成功率不高等问题，提出一种基于拓扑栅格度量复合地图的移动机器人分层路径规划方法。首先将机器人作业环境描述为栅格地图并划分为多个栅格化的子区域，以子区域为关键节点进行位置关系抽象从而获得拓扑架构，并对局部栅格区域进行精细化描述，构建拓扑栅格度量的复合地图。其次，在不同地图层级上分区域搜索机器人路径，在拓扑地图上采用Floyd算法规划子区域之间的区间路径，面向栅格地图提出搜索子区域内部路径的改进A*算法，通过引入扩展点筛选策略、双向搜索机制、路径冗余点剔除技术提高路径规划的效率与质量，并拼接各段区间路径和内部路径生成全局优化初始路径。最后，针对部分未知场景中的动态障碍物，在度量地图上提出基于深度强化学习架构的动态避障路径规划方法，利用价值分类经验回放机制提高样本的利用率和模型训练的效率。实验结果表明，所提方法有较高的搜索效率和避障成功率，生成的路径兼具安全性和平滑性。

关键词: 复合地图, 移动机器人, 路径规划, 改进A*算法, 强化学习