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

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

◆刘先生皇甫瑞云

(1天津职业技术师范大学，2新乡职业技术学院)

【摘要】比较了基于遗传算法的完全遍历路径规划方法的优缺点，本文的环境地图采用几何表示法表示，即用点、线及其组合

提出了基于遗传算法与单元分解法Boustrophedon算法结合的完全来表示环境中的特征，并用参数来表明各个特征在环境中的具体

遍历路径规划新方法。采用Boustrophedon单元分解法将全部遍位置。将地图进行Boustrophedon单元分解后，地图将由若干障碍

历区域分解为若干子区域，在实现单个子区域的遍历基础上，利区和若干遍历区组成。电子地图则表示为各个区域信息的集合，

用遗传算法确定子区域的遍历顺序。将该方法应用于清洁机器人而其中单个区域的信息包括区域的属性(障碍区属性或遍历区属

的完全遍历路径规划，与基于其他算法的路径规划方法进行比较，性)及区域顶点的坐标。通过Boustrophedon单元分解，环境可以

在多个性能指标上都得到了改善与提高。该方法综合了于遗传算分解为如图1所示的若干遍历区和障碍区。

法与单元分解法Boustrophedon算法的优点，简单有效，还通过仿

真研究表明，该方法在多个性能指标上都得到了改善与提高。

【关键词】移动机器人遗传算法完全遍历路径规划

1引言

完全遍历路径规划(CompleteCoveragePathPlanning，CCPP)

是一种特殊的路径规划，它要求移动机器人在满足一定的指标下

完遍历目标环境中的可达区域。在机器人的许多应用领域，大都

如图1所示，区域2和区域5之间的连通距离是不方便求

需要用到遍历路径规划算法，例如军事用的地雷探测、家居及办公

解的，本文通过定义一个距离来表示两者之间的实际距离。虽然

环境的地面清洁、不同应用领域地图的创建等。在这些应用中要

这个距离与实际距离之间有一定的差距，但距离值的大小趋势是

求机器人覆盖环境中所有未被障碍物占据的区域。按照对环境知

一致的，而且距离的定义主要考虑了两个区域之间的直线距离、区

识的了解，在已知环境覆盖算法中让清洁机器人规划出一条能走

域之间的连通关系、区域之间的障碍物情况。对于非毗邻关系的

过环境中的所有地方并目．是代价最小路径，这个时候的问题就相

区域之间的距离，我们用D％=bDJN％来表示。其中，b是一个

当于旅行家问题，未知环境的覆盖要求清洁机器人必须借助身体

可调系数，可以通过仿真来调整该值以得到一个较好的数值；D为

上携带的不同类型的传感器来感知周围的环境并进行规划。

环境中两个区域之间的直线距离矩阵，对于该表达式中的各个参

为克服上述路径规划中存在的问题，本文比较了基于遗传算

数，D、N可以根据划分后的区域的边界信息来确定，而J需要通

法的完全遍历路径规划方法的优缺点，提出了基于遗传算法与单

过下面的算法实现。

元分解法、启发式搜索和障碍物逼近算法结合的完全遍历路径规

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

划新方法，将该方法应用于清洁机器人的完全遍历路径规划，与基

于其他算法的路径规划方法进行比较，在多个性能指标上都得到l【J

了改善与提高。旺疆