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

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

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

3、境并进展规划。为抑制上述途径规划中存在的问题，本文比较了基于遗传算法的完全遍历途径规划方法的优缺点，提出了基于遗传算法与单元分解法、启发式搜索和障碍物逼近算法结合的完全遍历途径规划新方法，将该方法应用于清洁机器人的完全遍历途径规划，与基于其他算法的途径规划方法进展比较，在多个性能指标上都得到了改善与进步。2完全遍历规划性能指标挪动机器人的完全遍历途径规划常用的性能评价指标有遍历面积百分率，遍历重叠率。1遍历覆盖率，是指机器人沿可行轨迹线遍历完成后，己遍历面积与可达区域面积的百分比。2遍历重叠率，指所有遍历重叠面积之和与可达区域面积的之比的百分数。为了保证相邻区域之间不留有遍历盲区，相邻遍历区域

4、必须有一定程度的重叠，显然，重叠区域越小越好，但因受机器人本身的系统误差，定位误差，控制精度以及环境状态的影响，重叠区不可能太小，假设一个机器人性能越高，那么遍历重叠率能控制在很小的范围内。从遍历重叠率，还可以推出未遍历面积百分率，它指机器人沿着可行轨迹线遍历完成后，未遍历面积与可达面积的百分比。假设一个机器人性能越高，那么遍历覆盖率越高，遍历重叠率越低，遍历效果越好，本文中主要结合遍历重叠率和未遍历面积来综合评价完全遍历途径规划。3基于遗传算法的完全遍历途径规划本文的环境地图采用几何表示法表示，即用点、线及其组合来表示环境中的特征，并用参数来说明各个特征在环境中的详细位置。将地图进展Bous

5、trophedon单元分解后，地图将由假设干障碍区和假设干遍历区组成。电子地图那么表示为各个区域信息的集合，而其中单个区域的信息包括区域的属性障碍区属性或遍历区属性及区域顶点的坐标。通过 Boustrophedon单元分解，环境可以分解为如图 1所示的假设干遍历区和障碍区。由图2我们可以得到矩阵A得到区域i和k的有几条连通途径。图2中各区域之间的连通关系矩阵如下：在电子地图中两个遍历子区域的最近顶点分别为 A x i ， y i 、 B x j ， y j ，判断两者之间的障碍物个数就是判断AB连线通过的障碍物个数。障碍物顶点在向量AB的顺时针方向还是在逆时针方向可以通过向量的叉乘来判断，即电

6、子地图中遍历子区域之间的障碍物数矩阵 N如下：为了只保存对角线元素为 0，将矩阵 N的非对角线元素加1，得到规格化后的障碍物矩阵N。间隔 矩阵 D表示遍历子区域之间的实际间隔 ，其元素dij为子区域i和j的最近顶点之间的间隔 ，对于毗邻区域的间隔 值定为a，非毗邻区域的间隔 值由电子地图根据区域坐标定出。图 1区域之间间隔 矩阵 D实测如下：通过对障碍物矩阵、间隔 矩阵、连通矩阵的一样位置的元素相乘，再对非一次连通的区域间隔 乘以系数b，得到一个重新定义的综合间隔 矩阵D'，其中图1区域综合间隔 矩阵D'如下：4仿真研究基于本章提出的完全遍历途径规划算法，进展了大量的仿真实验。

7、下面是对图3的仿真地图完全遍历结果。经过大量地图的仿真说明，该遍历算法的覆盖率到达90%以上，有的甚至到达95%以上，而且重复率在10%以下。对于不同的地图覆盖率和重复率是不同的，不过对大多数地图而言，该算法是高效的、实用的，具有很强的适应性。该完全遍历算法特点是系统要处理的信息量很少，机器人实时性控制更强。特别是提出了基点这一重要概念，使得在未知环境中实现完全遍历更有效、更方便。5结论本文根据遍历环境内区域关系和区域连通图，将已有的连通图补充为完全连通图，并根据区域信息和连通信息定义一个区域之间的间隔 矩阵，赋予区域之间的连接权值。根据间隔 矩阵，采用遗传算法对区域的遍历顺序进展优化。仿真研究说明，该方法用于