基于栅格地图移动机器人完全遍历算法——矩形分解法.docVIP

基于栅格地图的移动机器人完全遍历算法——矩形分解法 秦 超 （控制与工程学院 模式识别与智能系统 2009010217） 摘 要：提出移动机器人的一种新的完全遍历算法：矩形分解算法。首先通过机器人环境学 习建立栅格地图，对环境中的障碍物实行矩形化建模。而后应用矩形化模型中的关键点将环 境分解成为矩形块，最后在这个分块环境的拓扑图中寻找到一条Hamilton路径，机器人沿 此路径即可实现对环境的完全遍历。 栅格地图是机器人自主学习得到的，每当机器人被应用于一个新的环境时，机器人对环境自主学习并建立栅格地图。在工作中如果发现地图中未标注的未知障碍即调用模板进行处理并且根据新障碍的情况更新地图。 o 机器人建立栅格地图的具体算法如图1所示，机器人首先从环境原点O沿x方向进行移动，发现障碍即绕过障碍物，此后继续沿原方向运动，到达边界后沿Y增大方向移动一个车距返回，重复这个过程，直到学习环境完毕。当机器人遇到障碍物时，记录该格点为有障碍物，否则记录为无障碍，根据机器人的记录情况即可以建立该环境的栅格地图。 图1 栅格地图建模过程 图2是对矩形房间遍历学习后建立的栅格地图，每个格点可以用(x,y)来表示，x表示格点所在列数，y表示格点所在横数。于是左上角格点（1，1），右下角格点（20，10）。其中，含有障碍物的格点标注为1，不含有障碍物的格点标注为0。可以看到，该环境中存在两个障碍物。首先，找到每个障碍物x值最小的格点，如果x值最小的格点不止一个，则找出这些点中y值最小的格点，标记为M（x1 ,y1） 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 图2 栅格地图 按照从左至右，从上至下的顺序依次对障碍矩形化的栅格地图进行分块。以矩形障碍的M点为起点，沿纵向做割线直到边界或矩形障碍或其他的分割线。以矩形化障碍的N点为起点，沿横向做割线直到环境边界或矩形障碍或其他的分割线，如图3所示（用1所在方格线表示割线）。 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 图3 环境分块图 其中对分割线所在格点做如下定义： 定义1：割线不存在区域S1={x.y︱ocup(x,y)=0},割线存在区域S2={x,y︱ocup(x,y)=1}。其中ocup(x,y)表示割线占有函数。图3中对割线存在的区域进行了直观的标识。 定义2：矩形分块T=T1∪T2。其中T1表示被割线分离开的独立区域，T2表示与独立区域T1紧相邻的割线存在区域。所以存在关系∑T1=∑S1,∑T2=∑S2。 定义3：设（x1,y1））A A C E