基于遗传算法的完全遍历路径规划研究

比较了基于遗传算法的完全遍历路径规划方法的优缺点，提出了基于遗传算法与单元分解法Boustrophedon算法结合的完全遍历路径规划新方法。采用 Boustrophedon单元分解法将全部遍历区域分解为若干子区域，在实现单个子区域的遍历基础上，利用遗传算法确定子区域的遍历顺序。将该方法应用于清洁机器人的完全遍历路径规划，与基于其他算法的路径规划方法进行比较，在多个性能指标上都得到了改善与提高。该方法综合了于遗传算法与单元分解法Boustrophedon算法的优点 ，简单有效 ，还通过仿真研究表明 ，该方法在多个性能指标上都得到了改善与提高。

移动机器人遗传算法完全遍历路径规划

1引言

完全遍历路径规划（ Complete Coverage Path Planning， CCPP）是一种特殊的路径规划，它要求移动机器人在满足一定的指标下完遍历目标环境中的可达区域。在机器人的许多应用领域，大都需要用到遍历路径规划算法，例如军事用的地雷探测、家居及办公环境的地面清洁、不同应用领域地图的创建等。在这些应用中要求机器人覆盖环境中所有未被障碍物占据的区域。按照对环境知识的了解，在已知环境覆盖算法中让清洁机器人规划出一条能走过环境中的所有地方并目.是代价最小路径，这个时候的问题就相当于旅行家问题，未知环境的覆盖要求清洁机器人必须借助身体上携带的不同类型的传感器来感知周围的环境并进行规划。

为克服上述路径规划中存在的问题，本文比较了基于遗传算法的完全遍历路径规划方法的优缺点，提出了基于遗传算法与单元分解法、启发式搜索和障碍物逼近算法结合的完全遍历路径规划新方法，将该方法应用于清洁机器人的完全遍历路径规划，与基于其他算法的路径规划方法进行比较，在多个性能指标上都得到了改善与提高。

2完全遍历规划性能指标

移动机器人的完全遍历路径规划常用的性能评价指标有遍历面积百分率，遍历重叠率。

（1）遍历覆盖率，是指机器人沿可行轨迹线遍历完成后，己遍历面积与可达区域面积的百分比。

（2）遍历重叠率，指所有遍历重叠面积之和与可达区域面积的之比的百分数。

为了保证相邻区域之间不留有遍历盲区，相邻遍历区域必须有一定程度的重叠，显然，

重叠区域越小越好，但因受机器人本身的系统误差，定位误差，控制精度以及环境状态的影响，重叠区不可能太小，如果一个机器人性能越高，则遍历重叠率能控制在很小的范围内。

从遍历重叠率，还可以推出未遍历面积百分率，它指机器人沿着可行轨迹线遍历完成后，未遍历面积与可达面积的百分比。

如果一个机器人性能越高，则遍历覆盖率越高，遍历重叠率越低，遍历效果越好，本文中主要结合遍历重叠率和未遍历面积来综合评价完全遍历路径规划。

3基于遗传算法的完全遍历路径规划

本文的环境地图采用几何表示法表示，即用点、线及其组合来表示环境中的特征，并用参数来表明各个特征在环境中的具置。将地图进行Boustrophedon单元分解后，地图将由若干障碍区和若干遍历区组成。电子地图则表示为各个区域信息的集合，而其中单个区域的信息包括区域的属性（障碍区属性或遍历区属性）及区域顶点的坐标。通过 Boustrophedon单元分解，环境可以分解为如图 1所示的若干遍历区和障碍区。

如图1所示，区域 2和区域 5之间的连通距离是不方便求解的，本文通过定义一个距离来表示两者之间的实际距离。虽然这个距离与实际距离之间有一定的差距，但距离值的大小趋势是一致的，而且距离的定义主要考虑了两个区域之间的直线距离、区域之间的连通关系、区域之间的障碍物情况。对于非毗邻关系的区域之间的距离，我们用D%= bDJN%来表示。其中， b是一个可调系数，可以通过仿真来调整该值以得到一个较好的数值；D为环境中两个区域之间的直线距离矩阵，对于该表达式中的各个参数， D、N可以根据划分后的区域的边界信息来确定，而J需要通过下面的算法实现。

由图2我们可以得到矩阵A

aij = 1表示遍历子区域i和j毗邻，aij = 0表示不毗邻。矩阵A为对称矩阵，其对角线的元素值为0，即不存在通过一次连通的路径连通区域1与它自身。aij = 1表示存在一条从区域i到区域j的一次连通路径，如a12 = 1，从图 2看出，区域1、 2存在一次连通路径。那么如何得到非一次连通的区域之间的连通关系呢？我们可以通过求矩阵 A的n次幂来得到两个区域之间的n次连通关系。对于i、j、k三个区域，如果区域i和区域j连通，区域j和区域k连通，则区域i和区域k连通，即当元素aij为非零值，ajk也为非零值，则通过计算

得到区域i和k的有几条连通路径。图2中各区域之间的连通关系矩阵如下：

在电子地图中两个遍历子区域的最近顶点分别为 A（ x i ， y i ）、 B （ x j ， y j ） ，判断两者之间的障碍物个数就是判断AB连线通过的障碍物个数。障碍物顶点在向量AB的顺时针方向还是在逆时针方向可以通过向量的叉乘来判断，即

电子地图中遍历子区域之间的障碍物数矩阵 N如下：

为了只保留对角线元素为 0，将矩阵 N的非对角线元素加1，得到规格化后的障碍物矩阵N。

距离矩阵 D表示遍历子区域之间的实际距离，其元素dij为子区域i和j的最近顶点之间的距离，对于毗邻区域的距离值定为a，非毗邻区域的距离值由电子地图根据区域坐标定出。图 1区域之间距离矩阵 D实测如下：

通过对障碍物矩阵、距离矩阵、连通矩阵的相同位置的元素相乘，再对非一次连通的区域距离乘以系数b，得到一个重新定义的综合距离矩阵D'，其中

图1区域综合距离矩阵D'如下：

4仿真研究

基于本章提出的完全遍历路径规划算法，进行了大量的仿真实验。下面是对图3的仿真地图完全遍历结果。

经过大量地图的仿真表明，该遍历算法的覆盖率达到90%以上，有的甚至达到95%以上，而且重复率在10%以下。对于不同的地图覆盖率和重复率是不同的，不过对大多数地图而言，该算法是高效的、实用的，具有很强的适应性。该完全遍历算法特点是系统要处理的信息量很少，机器人实时性控制更强。特别是提出了基点这一重要概念，使得在未知环境中实现完全遍历更有效、更方便。

5结论

本文根据遍历环境内区域关系和区域连通图，将已有的连通图补充为完全连通图，并根据区域信息和连通信息定义一个区域之间的距离矩阵，赋予区域之间的连接权值。根据距离矩阵，采用遗传算法对区域的遍历顺序进行优化。仿真研究表明，该方法用于不确定环境下的移动机器人遍历路径规划，不但能保证遍历所有可达工作空间，并且规划的路径较短、路径重复率小，具有较高的规划效率。

参考文献：

[1]丁学恭.机器人控制研究[M].浙江大学出版社，2006.

[2]杨高波，元波.精通MATLAB7.混合编程[M].电子工业出版社，2006.

[3]张增圻.智能控制理论与技术[M].清华大学出版社，1995.

[4]王正林，刘明.精通Matlab 7.0[M].电子工业出版社，2006.