Hierarchical robot path planning algorithm based on grid map

Abstract

Utilizing the hierarchical planning idea,we propose an optimal path planning algorithm based on grid map.The first layer of the algorithm is planning in topology layer,and we adopt Voronoi graph construction frothing algorithm to describe topological relationship of global passable regions.In the second layer,we design generalized level-set algorithm to solve the optimal path search problem in topological layer.The third layer is path replanning in grid layer.Utilizing the narrow-band level-set idea,we obtain a narrow band region that robot can safely pass by broadening the topology path in grid layer,and the local fast marching method algorithm is implemented in this region.It improves the topological path and increases the efficiency and real-time capability of the proposed algorithm.