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

doi:10.7523/j.issn.2095-6134.2013.04.015

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

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

余翀¹, 邱其文²

1. 复旦大学信息科学与工程学院, 上海 200433;
2. 南京邮电大学自动化学院, 南京 210046

收稿日期:2012-04-11 修回日期:2012-09-11 发布日期:2013-07-15
通讯作者: 余翀
基金资助:
机器人学国家重点实验室基金(R2200703)资助 

Hierarchical robot path planning algorithm based on grid map

YU Chong¹, QIU Qi-Wen²

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

摘要/Abstract

摘要：

采用分层规划的思想,给出一种基于栅格地图的最优路径规划算法. 分层路径规划算法的第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

中图分类号:

TP24

余翀, 邱其文. 基于栅格地图的分层式机器人路径规划算法[J]. 中国科学院大学学报, 2013, 30(4): 528-538.

YU Chong, QIU Qi-Wen. Hierarchical robot path planning algorithm based on grid map[J]. Journal of University of Chinese Academy of Sciences, 2013, 30(4): 528-538.

参考文献

[1] Zhu D Q, Yan M Z. Survey on technology of mobile robot path planning[J]. Control and Decision,2010,25(7):961-967(in Chinese). 朱大奇,颜明重. 移动机器人路径规划技术综述[J]. 控制与决策,2010,25(7):961-967.

[2] Willms A R,Yang S X. An efficient dynamic system for real-time robot-path planning[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics,2006,36(4):755-766.

[3] Zhang Y, Zhang L, Zhang X H. Mobile robot path planning base on the hybrid genetic algorithm in unknown environment [C]//Eighth International Conference on Intelligent Systems Design and Applications (ISDA). China:Taiwan,2008:661-665.

[4] Hassanzadeh I,Madani K,Badamchizadeh M A. Mobile robot path planning based on shuffled frog leaping optimization algorithm [C]//Conference on Automation Science and Engineering (CASE). Canada:Ontario,2010:680-685.

[5] Guo J M,Liu L,Liu Q,et al. An improvement of D^* algorithm for mobile robot path planning in partial unknown environment[C]//Second International Conference on Intelligent Computation Technology and Automation (ICICTA). China:Hunan,2009:394-397.

[6] Zhang C G,Xi Y G. Robot rolling path planning based on locally detected information[J]. Acta Automatica Sinica,2003,29(1):38-44(in Chinese). 张纯刚,席裕庚. 基于局部探测信息的机器人滚动路径规划[J]. 自动化学报,2003,29(1):38-44.

[7] Yang Y W,Yang J Y,Gong L. The solution for robot path planning based on Level Set method[J]. Journal of Image and Graphics,2005,10(9):1139-1145(in Chinese). 杨余旺,杨静宇,龚璐. Level Set方法求解机器人路径规划的探讨[J]. 中国图象图形学报,2005,10(9):1139-1145.

[8] Kimmel R,Amir A,Bruckstein A M. Finding shortest paths on surfaces using Level Sets propagation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(6):635-640.

[9] Xu B,Stilwell D J,Kurdila A. Efficient computation of Level Sets for path planning[C]//International Conference on Intelligent Robots and Systems (IROS). USA:Louis,2009:4414-4419.

[10] Philippsen R,Siegwart R. An interpolated dynamic navigation function[C]//Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). Spain:Barcelona,2005:3782-3789.

[11] Scheding S,Dissanayake G,Nebot E M, et al. An experiment in autonomous navigation of an underground mining vehicle[J]. IEEE Transactions on Robotics and Automation,1999,15(1):85-95.

[12] Li M,Wang J,Zhu M Q. On skeleton extraction algorithm for path planning of mobile robots in complex planar maps[C]// 29th Chinese Control Conference (CCC). China:Beijing,2010:3704-3708.

[13] Minhyeok Kwon,Heonyoung Lim,Yeonsik Kang,et al. Hierarchical optimal time path planning method for an autonomous mobile robot using A^* algorithm[C]//2010 International Conference on Control Automation and Systems (ICCAS). Korea:Gyeonggi-do,2010:1997-2001.

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

Hierarchical robot path planning algorithm based on grid map

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

访问统计

联系我们