欢迎访问中国科学院大学学报,今天是

中国科学院大学学报 ›› 2013, Vol. 30 ›› Issue (4): 528-538.DOI: 10.7523/j.issn.2095-6134.2013.04.015

• 信息与电子科学 • 上一篇    下一篇

基于栅格地图的分层式机器人路径规划算法

余翀1, 邱其文2   

  1. 1. 复旦大学信息科学与工程学院, 上海 200433;
    2. 南京邮电大学自动化学院, 南京 210046
  • 收稿日期:2012-04-11 修回日期:2012-09-11 发布日期:2013-07-15
  • 通讯作者: 余翀
  • 基金资助:

    机器人学国家重点实验室基金(R2200703)资助 

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 Published:2013-07-15

摘要:

采用分层规划的思想,给出一种基于栅格地图的最优路径规划算法. 分层路径规划算法的第1层为拓扑层规划,采用Voronoi图起泡生成算法描述全局可行域的拓扑关系; 第2层采用广义水平集算法,解决拓扑层的最优路径搜索问题; 第3层为栅格层的路径再规划. 在栅格层借鉴窄带水平集的思想,通过拓宽拓扑路径,得到一个机器人安全通行的窄带区域,并在此区域实行局部快速匹配算法,改善了拓扑路径,提高了算法的效率,并提高规划的实时性.

关键词: 分层路径规划, 栅格地图, Voronoi图起泡生成算法, 广义水平集算法, 局部快速匹配算法

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

中图分类号: