比较了基于遗传算法的完全遍历路径规划方法的优缺点，提出了基于遗传算法与单元分解法Boustrophedon算法结合的完全遍历路径规划新方法。采用 Boustrophedon单元分解法将全部遍历区域分解为若干子区域，在实现单个子区域的遍历基础上，利用遗传算法确定子区域的遍历顺序。将该方法应用于清洁机器人的完全遍历路径规划，与基于其他算法的路径规划方法进行比较，在多个性能指标上都得到了改善与提高。该方法综合了于遗传算法与单元分解法Boustrophedon算法的优点 ，简单有效 ，还通过仿真研究表明 ，该方法在多个性能指标上都得到了改善与提高。
移动机器人遗传算法完全遍历路径规划
1引言
完全遍历路径规划（ Complete Coverage Path Planning， CCPP）是一种特殊的路径规划，它要求移动机器人在满足一定的指标下完遍历目标环境中的可达区域。在机器人的许多应用领域，大都需要用到遍历路径规划算法，例如军事用的地雷探测、家居及办公环境的地面清洁、不同应用领域地图的创建等。在这些应用中要求机器人覆盖环境中所有未被障碍物占据的区域。按照对环境知识的了解，在已知环境覆盖算法中让清洁机器人规划出一条能走过环境中的所有地方并目.是代价最小路径，这个时候的问题就相当于旅行家问题，未知环境的覆盖要求清洁机器人必须借助身体上携带的不同类型的传感器来感知周围的环境并进行规划。
为克服上述路径规划中存在的问题，本文比较了基于遗传算法的完全遍历路径规划方法的优缺点，提出了基于遗传算法与单元分解法、启发式搜索和障碍物逼近算法结合的完全遍历路径规划新方法，将该方法应用于清洁机器人的完全遍历路径规划，与基于其他算法的路径规划方法进行比较，在多个性能指标上都得到了改善与提高。
2完全遍历规划性能指标
移动机器人的完全遍历路径规划常用的性能评价指标有遍历面积百分率，遍历重叠率。
（1）遍历覆盖率，是指机器人沿可行轨迹线遍历完成后，己遍历面积与可达区域面积的百分比。
（2）遍历重叠率，指所有遍历重叠面积之和与可达区域面积的之比的百分数。
为了保证相邻区域之间不留有遍历盲区，相邻遍历区域必须有一定程度的重叠，显然，
重叠区域越小越好，但因受机器人本身的系统误差，定位误差，控制精度以及环境状态的影响，重叠区不可能太小，如果一个机器人性能越高，则遍历重叠率能控制在很小的范围内。
从遍历重叠率，还可以推出未遍历面积百分率，它指机器人沿着可行轨迹线遍历完成后，未遍历面积与可达面积的百分比。
如果一个机器人性能越高，则遍历覆盖率越高，遍历重叠率越低，遍历效果越好，本文中主要结合遍历重叠率和未遍历面积来综合评价完全遍历路径规划。
3基于遗传算法的完全遍历路径规划
本文的环境地图采用几何表示法表示，即用点、线及其组合来表示环境中的特征，并用参数来表明各个特征在环境中的具体位置。将地图进行Boustrophedon单元分解后，地图将由若干障碍区和若干遍历区组成。电子地图则表示为各个区域信息的集合，而其中单个区域的信息包括区域的属性（障碍区属性或遍历区属性）及区域顶点的坐标。通过 Boustrophedon单元分解，环境可以分解为如图 1所示的若干遍历区和障碍区。
由图2我们可以得到矩阵A
得到区域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结论
本文根据遍历环境内区域关系和区域连通图，将已有的连通图补充为完全连通图，并根据区域信息和连通信息定义一个区域之间的距离矩阵，赋予区域之间的连接权值。根据距离矩阵，采用遗传算法对区域的遍历顺序进行优化。仿真研究表明，该方法用于不确定环境下的移动机器人遍历路径规划，不但能保证遍历所有可达工作空间，并且规划的路径较短、路径重复率小，具有较高的规划效率。
