Welcome to Journal of University of Chinese Academy of Sciences,Today is

Journal of University of Chinese Academy of Sciences ›› 2013, Vol. 30 ›› Issue (4): 528-538.DOI: 10.7523/j.issn.2095-6134.2013.04.015

• Research Articles • Previous Articles     Next Articles

Hierarchical robot path planning algorithm based on grid map

YU Chong1, QIU Qi-Wen2   

  1. 1. School of Information Science and Technology, Fudan University, Shanghai 200433, China;
    2. School of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210046, China
  • Received:2012-04-11 Revised:2012-09-11 Online:2013-07-15

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.

Key words: hierarchical path planning, grid map, Voronoi graph construction frothing algorithm, generalized level-set algorithm, local fast marching method algorithm

CLC Number: