一种基于新的单元分解法的全覆盖路径规划算法

李燊

（沈阳新松机器人自动化股份有限公司，辽宁 沈阳 100169）

0 引言

全覆盖路径规划算法是指在一个有限且有界的区域内，获得一条能够覆盖除了障碍物外所有区域的路径[1-2]。一个好的全覆盖路径规划算法，应满足覆盖率高、重复率尽量低。

目前，已有全覆盖路径规划算法主要有随机法、模板法、单元分解法、栅格法等[3-4]。其中随机法让机器人随机选择一个方向前进，遇到障碍物后转向再继续前进。这种方法简单，但无法保证全覆盖[4]，一般用于未知环境中。模板法采用预先设定的模板与当前环境信息比较，进而选择下一步路径，但模板法缺乏对整个环境的规划，效率较低。

单元分解法是将含有障碍物的整个区域，分解成若干无障碍的子区域，子区域之间采用某种算法进行遍历。常用单元分解法有Trapeziodal分解法[5]和Boustrophedon分解法[6]。Trapeziodal分解法是将一条直线扫过目标区域，当直线遇到多边形障碍物的顶点时，产生IN,OUT,MIDDLE三种情形，依据不同情形将环境分成若干梯形子区域。为了减少相邻子区域边界处的重复覆盖，Boustrophedon单元分解法在Trapeziodal分解法基础上进一步合并MIDDLE操作产生的子区域，减少子区域个数，进而减少重复的覆盖，提高效率，但相邻子区域边界仍有重复覆盖问题。以上单元分解法，障碍物需为为多边形。为了解决非多边形的障碍物问题，morse分解法[7]以morse函数的等值线与障碍物的切点作为关键点,以关键点为顶点，障碍物的边界和等值线为边，对地图进行分区，同时选择不同的morse函数可以划分成不同的子区域，生成不同的规划路线。但此方法复杂且未解决相邻子区域边界重复覆盖问题。

在基于栅格地图的全覆盖路径规划方法中，文献［8］采用wavefront算法标记各个栅格的代价值，然后在从起点开始，在相邻的未覆盖的栅格中的找到代价最大的作为下一个目标点，如果代价相同则随机选择其中一个。

基于生物激励神经网络[9]的栅格覆盖规划方法是将神经元与栅格地图离散坐标对应，通过规定障碍物和非障碍物对神经元输入激励和抑制的不同，进而判断机器人的位置，该方法可用于未知环境，并对未知环境中动态障碍物实时避障。

栅格覆盖法的目的都是遍历所有空闲栅格，栅格的大小往往设置成机器人的宽度，而“部分占用”的栅格也被当作整体障碍物栅格，对于较大的机器人，会造成遗漏很多区域未覆盖。

本文提出一种全覆盖路径规划方法，采用一种新的基于栅格地图的单元分解方法,该方法对障碍物形状无任何要求，同时地图栅格的大小不必按机器人宽度设置，适用于高分辨率栅格地图。首先，在地图的空闲区域以机器人宽度为间隔生成若干条平行路线,然后根据相邻路线的端点是否属于同一障碍物，将所有路线划分成不同的区域，在子区域内机器人沿着已生成的路线往复运动，然后按照最短距离原则遍历子区域。

1 全覆盖路径规划

1.1 路线生成

栅格地图将机器人周围空间分解成若干单元格,依据障碍物占有情况将环境划分为空闲区域和占有区域。如图1所示，深色栅格代表占有栅格，用1表示，所围成区域为占有区域，白色栅格代表空闲栅格，用0表示，所围成区域为空闲区域。

首先对栅格地图进行预处理，即对栅格地图边界做封闭处理，并将障碍物以机器人半径进行膨胀。

设机器人直径为栅格宽度的倍，从地图最左侧有空闲栅格的第一列开始，每间隔（k-1）列生成路线，有路线的列称为路线列。为了图示清晰，本文中取k=2。

生成路线的具体方法，如图1所示，从路线列的最低端至最顶端遍历栅格状态，当栅格状态由占用栅格变为空闲栅格时，即由1变成0时，此处为0的栅格作为路线的一个端点，为了以下描述方便，这里我们称为1的障碍物栅格为路线的下端点；当栅格状态由0变为1时，此处为0的栅格为路线的另一个端点，为1的障碍物栅格我们称为路线的上端点。路线表示为，路线下端点为，路线上端点为，其中n表示路线的列数序号，m表示所在路线列上路线的序号。

图1 路线生成

1.2 子区域划分

子区域的划分就是把在空闲区域生成的路线划分为若干子区域，划分的原则为：如果两条相邻路线的上端点属于同一障碍物区域，下端点属于同一障碍物区域，则这两条路线属于同一个子区域。

划分区域的基本方法为：从地图的左侧至右侧遍历所有路线列，首先把第一路线列中所有路线分别放入新的不同子区域中，然后继续向右侧遍历其他路线列上的路线，对于路线，以图2所示为例，从下端点开始，沿着障碍物边缘向左侧搜索，如果能找到其左侧相邻路线列中某一路线的下端点；同时从的上端点开始沿着障碍物边缘向左侧搜索，如果也能找到左侧相邻路线列中的上端点，则将加入到所属的子区域，否则建立新的子区域，并加入。

图2 沿障碍物边缘搜索

图3 子区域的划分

划分区域的关键在于如何从路线端点沿障碍物边缘向左侧搜索相邻路线列中路线的端点。对于路线的下端点，首先将下端点作为当前栅格，搜索的具体流程如下：

①判断当前栅格左上角的栅格是否为1，如果不是1，转到②；如果是1，如图4中a所示，从左上角栅格开始，在此列继续向上遍历栅格状态，直到栅格状态由1变为0，即找到障碍物边缘栅格R，然后转至⑤。如果直至地图上边界栅格仍未变成0，说明从障碍物边缘向左侧搜索，未找到相邻路线列中路线的端点，转到⑥。

②判断当前栅格的左侧栅格是否为1，如果不为1，则转到③；如果为1，如图4中b所示，则找到相邻列障碍物边缘栅格R，转到⑤。

③判断当前栅格的左下角栅格是否为1，如果不为1，则转到④；如果为1，如图4中c所示，则找到相邻列障碍物边缘栅格R，转到⑤。

④判断当前栅格的下方栅格是否为1，如果不为1，转到⑥；如果为1，如图4中d所示，从这个下方栅格开始在当前列向下沿着为1的栅格遍历，直到其左列相邻栅格为1，即找到相邻列障碍物边缘栅格R，转到⑤；如果向下遍历栅格时，栅格状态变为0或者一直遍历到地图下边界，仍未在左侧列中找到R，则说明从沿着障碍物边缘向左侧搜索，未找到相邻路线列中路线的端点，转到⑥。

图4 从向左侧沿障碍物边缘搜索

⑥返回并输出无结果，即未找到相邻路线列中某路线端点。

图5 从向左侧沿障碍物边缘搜索

1.3 子区域的遍历

如果把子区域作为一个节点，那么子区域的遍历就是机器人从初始节点出发，用最短的路程依次走过其他节点。本文采用最短距离原则进行子区域的遍历。

子区域作为节点的位置可以取子区域的中心，在本文中用子区域中间路线的中点来代替。假设子区域包含有条路线，中间路线取左起第条，子区域节点位置即为该路线中点。同时，我们把子区域最左侧路线的两个端点和最右侧路线的两个端点称为子区域的四个顶点。

在子区域内机器人按生成路线往复运动，即采用弓字形路径规划，机器人在该子区域的最终位置在该子区域顶点处。然后采用A*算法规划机器人当前位置到其他未走过子区域节点的路径并计算路径距离，选择距离最近的子区域作为下一个目标子区域。

确定好目标子区域后，计算当前位置与目标子区域四个顶点的距离，此距离为采用A*算法规划路径并计算的路径距离。选择距离最近的顶点作为的目标点,到达目标子区域后继续按已生成路线进行弓字形路径规划。如此反复，直至走完所有子区域中的所有路线。

如图6所示为仿真实验中，子区域的遍历顺序。图7为最终规划的全覆盖路线。

图6 子区域遍历顺序

图7 全覆盖路径规划

2 结论

本文提出的全覆盖路径规划方法，采用了新的针对已知栅格地图的单元分解法，该方法简单，实用性强，覆盖率高，对障碍物形状无限制，可应用于高分辨率地图，仿真结果表明了算法的有效性。本文方法中，子区域的遍历时采用了A*算法规划当前位置与子区域各节点和顶点的路径并计算距离，对于子区域多的复杂环境，运算时间长。因此，如何更高效地进行子区域的遍历，也是本文的下一步重点研究内容。