Robot coverage algorithm under rectangular decomposition environment  

矩形环境分解机器人遍历算法(英文)

作　　者：张赤斌[1] 颜肖龙[1] 

机构地区：[1]东南大学机械工程学院,南京211189

出　　处：《Journal of Southeast University(English Edition)》2008年第2期188-191,共4页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China(No.50475076);the National High Technology Research and Development Pro-gram of China(863Program)(No.2006AA04Z234)

摘　　要：The environment modeling algorithm named rectangular decomposition, which is composed of cellular nodes and interleaving networks, is proposed. The principle of environment modeling is to divide the environment into individual square sub-areas. Each sub-area is orientated by the central point of the sub-areas called a node. The rectangular map based on the square map can enlarge the square area side size to increase the coverage efficiency in the case of there being an adjacent obstacle. Based on this algorithm, a new coverage algorithm, which includes global path planning and local path planning, is introduced. In the global path planning, uncovered subspaces are found by using a special rule. A one-dimensional array P, which is used to obtain the searching priority of node in every direction, is defined as the search rule. The array P includes the condition of coverage towards the adjacent cells, the condition of connectivity and the priorities defined by the user in all eight directions. In the local path planning, every sub-area is covered by using template models according to the shape of the environment. The simulation experiments show that the coverage algorithm is simple, efficient and adapted for complex two- dimensional environments.提出了一种矩形分解的环境建模方法.该方法模型用环境分解出的节点及节点之间的连接关系网络来表示.环境建模首先将环境分解为正方形区域,区域中心点代表该区域位置.在邻近区域有障碍物情况下,扩大正方形边长形成矩形区域,有利于提高局部遍历效率.在这种环境建模思想下,提出了一种包含局部和全局2层结构路径规划下的机器人遍历方法.在全局路径规划中子区域之间的探索采用了基于知识规则的方法,定义了决定局部子区域向周围区域移动的一维优先权数组,该数组综合表征了本区域与相邻区域的遍历情况、连通关系和用户定义优先权级别.局部子区域根据环境形状采用模版匹配法实现遍历.仿真实验结果说明,该方法简单、高效,并适合解决复杂二维环境遍历问题.

关 键 词：path planning complete coverage algorithm rectangular decomposition 

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