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

Hierarchical robot path planning algorithm based on grid map

作　　者：余翀[1] 邱其文[2] 

机构地区：[1]复旦大学信息科学与工程学院,上海200433 [2]南京邮电大学自动化学院,南京210046

出　　处：《中国科学院大学学报（中英文）》2013年第4期528-538,546,共12页Journal of University of Chinese Academy of Sciences

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

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

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

分 类 号：TP24[自动化与计算机技术—检测技术与自动化装置]