填埋场裸膜红外巡检机器人最优路径规划

孟彩茹， 杜金鹏， 张维民， 陈亚宇， 魏浩良

(河北工程大学机械与装备工程学院， 邯郸 056038)

目前，垃圾填埋场环境污染是制约中国生态发展的重要因素之一。在填埋场建设过程中，受多种因素影响，防渗层会产生不同程度的损伤，由于垃圾渗滤液中含有大量有毒污染物，一旦渗漏会对周围土壤环境、水资源以及人体健康造成极大危害[1]。因此在填埋场建设初期做好裸膜检测，发现破损并及时修复具有重要意义。传统的人工巡检方法效率低下且漏检率高，已无法满足检测要求。本文基于红外探伤理论采用红外巡检机器人代替人工完成巡检，节省了大量人力物力。为了能有效提高巡检效率，笔者对巡检机器人全覆盖路径规划算法展开研究。

在机器人路径规划方面，曹晓燕等[2]针对货物运输问题开发设计了基于遗传算法的货运路径规划系统，提高了货运效率，但整体路径规划系统适用性低，性能不稳定；韩孟宜等[3]设计了混合遗传算法，将遗传算法与节约算法、邻域搜索算法相结合，实现了应急物资快速配送，求解结果较标准遗传算法更优，但其计算量大，路径规划耗时长；Di等[4]提出了采用神经网络算法完成未知动态环境下移动机器人路径规划的方法，并用遗传算法调整和训练神经网络，使机器人以较平滑的路径实现高效率避障；吴飞龙等[5]将A*算法和动态窗口法相融合实现了实时动态避障，极大减少了路径长度和机器人运行时间，但其不适用于全覆盖路径规划；Li等[6]通过简化信息素的存储方法来改进蚁群算法；昝新宇等[7]根据路径中多因素综合指标分配信息素来改进蚁群算法，二者都有效提升了算法收敛速度和稳定性，但在初始信息素差别分布上考虑不足。

在对垃圾填埋场路径规划中，以上算法在局部区域覆盖以及点到点的路径转移中有显著效果，但因填埋场障碍分布的特殊性，这些算法虽能完成路径规划，但巡检效率较低，易陷入局部最优。全覆盖路径规划要求红外巡检机器人合理高效的遍历垃圾填埋场内除障碍物以外的所有二维空间[8]。垃圾填埋场区域宽阔，各填埋单元都建有圆柱状导气石笼，用来导排垃圾陈化过程中产生的沼气，属于路径规划中的障碍物。垃圾填埋场最优巡检路径规划，可简化为性能评价函数最优值求解问题，主要包括：覆盖面积百分率、重复覆盖率和能量消耗等[9]。因此，现提出一种模板模型法与改进的遗传算法相结合的全覆盖路径规划模型，能有效提高机器人巡检效率。

1 相关工作

对红外巡检机器人路径规划，要先了解所规划的环境并对其建模；然后根据障碍物的分布对其进行区域分解，规划分解后的各子区域遍历方式；最后基于改进后的遗传算法对垃圾填埋场完成全覆盖路径规划。具体流程如图1所示。

图1 全覆盖路径规划流程图Fig.1 Flow chart of full coverage path planning

2 路径规划模型研究

2.1 环境建模

获取垃圾填埋场场地形状和各障碍物分布信息，建立相应环境模型。图2为垃圾填埋场示意图，黑色为障碍物，白色为可行域。

采用栅格法[10]对垃圾填埋场进行环境建模。规定红外巡检机器人检测范围与栅格大小相同，将垃圾填埋场分解为n×n栅格单元，建立一个n×n的二维矩阵，矩阵中的每一个元素代表一个栅格。如图3所示。

图2 填埋场示意图Fig.2 Schematic diagram of landfill site

图3 栅格地图Fig.3 Grid map

2.2 区域分解

垃圾填埋场中各单元都设有导气石笼，其分布较为规律整齐。为避免产生大量子区域造成路径冗余，采用区域分解法中的矩形分解法对环境进行优化分解，将整个区域分解为较规则的矩形子区域，按照从左到右从上到下规则，依次对区域分块编号，并用Q1,Q2,…,Q11表示，如图4所示，垃圾填埋场区域分解后示意图。

图4 区域分解示意图Fig.4 Schematic diagram of area decomposition

基于区域分解法的全覆盖路径规划方法主要完成子区域内部遍历和子区域间连接转换工作[11]。

2.3 子区域遍历

遍历所有子区域就是对垃圾填埋场的全覆盖。在子区域内部遍历中，针对垃圾填埋场地形和障碍物分布，采用模板模型法定义机器人巡检模式，用一系列模板模型规划出覆盖各子区域的路径[12]。其核心模板模型有前行(towards marker，TM)，右转(right turn,RT),左转(left turn,LT)，U形转弯(U turn,UT),躲避障碍(steer clear of obstacle,SCOO)，内螺旋(inside spin,IS),其具体巡检模式如图5所示。

对于无障碍物子区域，可以直接使用往复式遍历法和螺旋法[13]，其具体模型如图6所示。

图6(a)为往复式遍历模型，是一种阶梯式遍历方法，图中黑点为起点和终点，首先确定红外巡检机器人起始位置和最初运动方向，以往复式运动方式遍历该区域。图6(b)为螺旋法中内螺旋模型，保证红外巡检机器人在该区域的边沿位置起步，使其沿着该区域边缘螺旋式的由外向内进行遍历。这两种方法都能对无障碍物区域实现高效全覆盖。

对于存在障碍物的区域主要通过模板模型法中躲避障碍模型(SCOO)的行走方式来避障，经过环境建模和对填埋场的区域分解，障碍物都分布在各子区域边界处，SCOO模式可以很好地完成避障。

图5 模板示意图Fig.5 Schematic diagram of formwork

图6 传统遍历法Fig.6 Traditional traversal method

2.4 全区域覆盖

在对垃圾填埋场区域分解和子区域遍历方式确定后，规划各子区域间连接路径。研究基于遗传算法的全覆盖路径规划，找到各子区域间路径转移最优解，减少其重复覆盖率和能耗。由于遗传算法的万向性，使得它比一般随机搜索算法效率要高，且使用简单、鲁棒性强，对实际问题有高度适应性[14]。

2.4.1 遗传算法基本原理

遗传算法能实现优胜劣汰，可以使问题解逐代优化，逼近最优解。遗传操作主要有选择、交叉、变异，其中交叉和变异决定着整个算法的收敛速度和全局寻优能力[15]。其基本原理如图7所示。

2.4.2 遗传算法在路径规划中的实现

1)编码

通过编码将求解问题表示成遗传空间的染色体或个体。各子区域间遍历顺序决定着路径规划的优劣，本文研究中采用排列编码方式对各子区域遍历顺序进行编码。染色体由头部和主体两部分组成，头部表示各子区域间排列顺序，主体表示各子区域内节点遍历顺序，由节点连线组成，如图8所示。

2)初始种群的形成

传统遗传算法中初始种群一般随机产生，这样虽然简单，但会消耗计算资源出现大量不可行路径，且使算法收敛速度变慢。因此，初始路径序列由相邻子区域并根据启发式最邻近算法来生成，可以快速优化，加快收敛速度，而生成的初始路径序列就是染色体的头部。根据图4各子区域的编号，生成大量初始路径序列，具体如下。

head1:Q1,Q2,Q3,Q4,Q7,Q6,Q5,Q8,Q9,Q10,Q11；

head2:Q1,Q2,Q5,Q8,Q9,Q10,Q7,Q6,Q3,Q4,Q11。

3)适应度函数

适应度函数用来评价遗传算法解的优劣，直接影响着遗传算法的收敛速度和成败，其值越大，解就越优。针对机器人巡检路径问题，适应度函数由总距离和总时长两个约束条件组成。覆盖总时长主要取决于机器人的转弯次数，距离和时间值越大，适应度值越小，所以适应度函数为

(1)

式(1)中：c为调整常数，使适应度值保持在0～1，便于分析；∑dist和∑time分别为机器人行驶总距离和总时间，且∑dist>0，∑time>0；wdist和wtime分别为距离和时间的权重比例。

wdist+wtime=1

(2)

机器人对填埋场巡检时，转弯消耗时间和转弯个数成正比，适应度函数也可表达为

(3)

式(3)中：∑turn为机器人总转弯次数；wturn为转弯的权重比例。根据垃圾填埋场地形和障碍物分布形势，设定wdist=0.6，wturn=0.4是较为合理的。

4)选择

选择是以适应度为准则从群体中选择优胜个体。将锦标赛选择法和随机遍历选择法相结合，以加快收敛速度和增强全局寻优能力。锦标赛法是从群体中选择M个个体，选出其中适应度值最高的个体遗传到下一代，重复此操作，使得适应值较好的个体有更大的“生存机会”。随机遍历选择法要先计算个体被选中的概率，定义指针选择距离，然后等距离选择个体，对于不同适应值个体选择机会相对均等。选择步骤如下。

(1)设种群大小为N，以锦标赛的规则选出k个适应值最高的个体。

(2)根据随机遍历选择法，计算第i条路径被选中的概率，计算公式为

(4)

式(4)中：P(bi)为选中个体bi的概率；F(bi)为个体bi的适应度值。然后进行等距离选择个体。

5)交叉和变异

交叉和变异是遗传算法中的重要操作，交叉能产生大量新个体，决定整个算法的收敛速度;而变异对于产生新个体有辅助作用，影响算法的局部搜索能力[16]。

交叉操作中，要求其不能破坏表现优良个体，同时还可以有效产出较好的新个体。对交叉概率Pc进行模糊优化，使遗传算法寻优性能更加，具体优化方式如下：前期交叉概率应小，以避免收敛速度过快；种群适应值方差较大时，增大交叉概率；种群适应值较为优良的则减小交叉概率；对于接近的高适应值个体和距离较远的个体应施以较大的交叉概率。交叉概率Pc的一般取值范围为0.25～0.75。

基于路径规划的交叉重组具体步骤如下。

(1)根据交叉概率选取k组适应值较大的染色体，即

k=PcGn

(5)

式(5)中：Gn为种群大小。随后对k组染色体进行两两随机配对。

(2)配对后，在[0,n]间生成一个随机数，确定交叉点的位置。比如随机数为6，则将在第6位进行交叉重组。

实际操作如下。

交叉前，head1:Q1,Q2,Q3,Q4,Q7,Q6(UT),Q5,Q8,Q9,Q10,Q11；head2:Q1,Q2,Q5,Q8,Q9,Q10(IS),Q7,Q6,Q3,Q4,Q11。

交叉后，head1:Q1,Q2,Q3,Q4,Q7,Q6(IS),Q5,Q8,Q9,Q10,Q11；head2:Q1,Q2,Q5,Q8,Q9,Q10(UT),Q7,Q6,Q3,Q4,Q11。

如果需要较大的交叉概率，可以适当增加交叉点的个数，配对的路径序列可以同时对2或3个子区域进行交叉重组。

变异操作中，主要对群体中个体串基因进行改变。当遗传算法通过交叉重组接近最优解领域时，可以利用变异操作的局部寻优能力加快算法收敛速度。变异概率Pm取值较小，根据实际情况对变异进行优化。

种群适应度值方差较大时应减小变异概率，可以保证算法稳定性；种群适应度值方差较小时应加大变异概率，可以加快淘汰劣质个体；种群适应值较高的个体应取较小的变异概率。变异概率一般为0.01～0.2。

基于路径规划的变异操作具体步骤为：①对群体中所有个体以事先设定的变异概率判断是否进行变异；②选中的变异个体随机选取两个位置进行变异操作。比如随机两个位置是3和9，实际操作如下。

变异前，head3:Q1,Q11,Q10,Q9,Q8,Q5,Q2,Q3,Q4,Q7,Q6。

变异后，headnew3:Q1,Q11,Q4,Q9,Q8,Q5,Q2,Q3,Q10,Q7,Q6。

3 仿真

基于MATLAB对垃圾填埋场红外巡检机器人全覆盖路径规划进行仿真，生成一条最优路径，验证所设计算法对实现路径规划的高效可行性。

仿真主要分为两部分：第一部分要对填埋场环境采用栅格法进行仿真，处理成为31×31个栅格，如图9所示，其中黑色栅格表示障碍物，白色栅格表示可行域。第二部分为绘制红外巡检机器人在地图上的行走路径。首先要对填埋场采用矩形分解法进行区域分解仿真，将整个区域分解为多个子区域，如图10中蓝色线为各子区域间边界线；然后结合模板模型算法和改进的遗传算法对整个区域进行全覆盖路径规划。

图9 地图仿真Fig.9 Map simulation

遗传算法中，种群大小为11的阶乘，根据上述所提优化方法设定交叉概率为0.4、0.6、0.75，变异概率为0.1、0.2，经过迭代换算最终得出最优路径，如图10(a)所示，图10(a)中绿色三角形符号为机器人行走的起点和终点。图10(b)为普通遗传算法对该环境的路径仿真结果。

图10 机器人行走路径Fig.10 Robot walking path

由图10可得改进算法的重复覆盖率为1.21%，普通算法的重复覆盖率为2.43%，改进算法的行走时间比普通算法的快1.14倍。较改进算法，普通算法规划出的路径重复覆盖率较大，并且拐弯次数较多，耗费大量时间。

图11为改进前后算法求最优解的收敛曲线，图中可以看出两个算法在开始时收敛都较快；改进算法在逐渐向最优靠近，普通算法会出现浮动，可能产生局部最优解；改进算法在迭代80次时趋于稳定，而普通算法则在迭代110次才趋于稳定，并且适应度值较改进算法低。结果表明所提算法对垃圾填埋场红外巡检机器人最优路径规划是可行有效的。

图11 算法最优解收敛曲线Fig.11 Convergence curve of optimal solution of algorithm

4 结论

针对垃圾填埋场裸模渗漏检测工作，提出采用红外巡检机器人代替人工完成巡检任务，将全覆盖路径规划运用到填埋场这个特殊环境中去。采用矩形分解法对整个区域进行分解，将模板模型法和改进的遗传算法相结合构成一个成熟的全覆盖路径规划模型，为机器人找到一条最优巡检路径。基于MATLAB仿真结果表明，所改进算法对寻找全覆盖最优路径有着显著效果，且较普通算法有较快的收敛速度、较低的重复覆盖率和能耗。其除却文中所用领域亦可应用在智能机器人室内外清洁、矿区等地的全覆盖采样、工厂机器人智能运输货物等领域，且不会造成大量的路径冗余和较高的重复覆盖率，有较高的实用性。