A New Global Path Planning Strategy for Mobile Robots Using Hierarchical Topology Map and Safety-Aware Navigation Speed

摘要

This paper presents an efficient global path planning method for a mobile robot using a new skeleton representation of a map. For practical consideration of both safety and agility of the robot in narrow corridors, we introduce the concept of allowable speed at each point of free space of the map based on the distance to the closest obstacle. We define a new cost-to-go function corresponding to the allowable speed in a time-relevant way that eventually results in a safe time-minimized path. To realize the main idea, we built a hierarchical graph representation of a map using the skeleton that has the topology of undirected multigraph at the higher level and corresponding metric points at the lower level. The cost-to-go of the metric points are added up to construct the weight values of the edges of the graph. Then, the safe time-minimized path can be efficiently computed by obtaining optimal topological path from the higher level representation and identifying the corresponding metric points from the lower level. Using this approach, a safe and agile path can be found, which provides a good trade-off between the shortest path criterion and the admissible navigation speed based on lateral safety margins. The proposed method offers enhanced performance and less computational cost. We demonstrate the advantages of the proposed method through simulation results using a real map, where we also compared its performance with that of the conventional shortest path strategy.