基于农田环境的农业机器人群协同作业策略

宫金良，王 伟，张彦斐，兰玉彬

（1. 山东理工大学机械工程学院，淄博 255049；2. 山东理工大学农业工程与食品科学学院，淄博 255049）

0 引言

随着第四次产业革命的到来，农村人口老龄化、人力短缺等问题日趋严峻[1]，这为大型无人农场的出现提供了可能[2]。无人农场具有精准化种植、智能决策和智能化操控的特点，是未来农业发展的主流方向[3]。在无人农场的大田作业中，随着农业机器人的作业任务日益复杂化，单机器人作业越发不能满足无人农场中的工作需求，农业机器人群协同作业具有极大应用前景。

机器人群协同作业需解决任务分配与全区域覆盖2个基本问题，即农场主控系统在接收到某一任务要求时通过任务分配方案决定哪些机器人参加工作以及确定各参加工作机器人的工作量，并根据机器人群全区域覆盖方案分配各机器人工作区域与规划各机器人工作路径。

为合理分配各机器人的工作区域、提高机器人群的工作效率[4]，近些年已有机器人群全区域覆盖的相关研究。Maxim等[5]利用机器人之间相互排斥的策略使其均匀散布在作业区域中，从而达到对目标工作区域的覆盖。Viet等[6]通过梨耕式移动与A*算法相结合解决多机器人在线全覆盖任务，机器人依次梨耕式移动覆盖空闲区域。以上2种方案能够保证多目标区域的全覆盖，但是机器人群遍历时会产生较多重复路径。郝宗波等[7]提出基于栅格地图的内螺旋算法（Internal Spiral Coverage，ISC），利用边界探索获得环境边界之后进行路径规划。Agmon等[8]提出基于构造生成树的方式为每个机器人规划好覆盖路径，这些路径联合构成整个覆盖地形。Rekleitis等[9]将目标二维区域分解成单元区域，通过对每个区域简单地前后移动完成多机器人的全区域覆盖。Acar等[10]通过构造不同的Morse方程寻求最合理的区域分解方式，以适合机器人覆盖不同形状的环境。上述4种方案在优化机器人群遍历面积重复率的基础上完成了机器人群对工作区域的全覆盖，但并未考虑机器人性能参数的差异分配各机器人工作量与工作区域。

本文在考虑农业机器人异质性的基础上，以机器人群整体效能为优化目标解决机器人群的任务分配问题。在任务分配的基础上以机器人群总遍历面积重复率为优化目标，通过改进的遗传算法与深度优先搜索算法解决农田复杂环境下异质机器人群的全区域覆盖问题。

1 机器人作业任务分配

随着农业机器人的更新换代和工作损耗的累积，无人农场中的农业机器人在历史任务量、能耗、故障率、服务质量、工作效率等方面可能存在差异，本文将以上性能参数不一致的农业机器人定义为异质农业机器人，反之为同质机器人。本文通过定义机器人团队整体效能的概念，综合考虑以上性能因素选择农场中的同质与异质机器人参加工作并为其分配工作量。

根据任务分配的收益（reward）与成本（cost）相减得到任务分配的效能U，其中机器人i的服务质量isq代表收益，历史工作量ih、能耗ic与故障率if代表成本，则机器人i的效能iU为

以上4种性能参数的取值范围差异较大，数值较小的性能参数对机器人效能值的影响会被弱化。为方便调节计算机器人效能时4种性能参数的权重，在计算机器人i的收益或成本时引入全体机器人的对应参数数据，将各参数所代表的收益或成本控制在0～1之内，设无人农场的总机器人数量为ψ，效能计算公式为

式中 1w，2w，3w，4w分别为各性能参数的权重因子，其大小由农场管理者根据机器人的实际状况设定，w1+w2+w3+w4=1。

根据公式（2）确定各机器人的效能值之后确定参加工作的机器人和各机器人工作量，具体步骤为：对各机器人的效能值进行降序排序，依次选择机器人进入机器人工作团队，并根据机器人i的工作效率ie与工作时限要求H计算机器人i的理论工作量Wi（Wi=ei·H），直至机器人团队工作量WN不小于工作量需求值Wd。机器人i的实际工作量由其理论工作量按比例分配：

2 基于栅格法的环境建模与矩形分区

常规机器人群全区域覆盖方案通常基于具有部分障碍物且形状规则的单片工作区域确定，但不适于机器人群在复杂农田环境的遍历，本文以山东理工大学兰玉彬院士团队与淄博禾丰种业公司合作共建的数字生态循环农业农场[11]为基础，重新设置农田中的工作环境。数字生态循环农业农场中存在离散分布且工作区域不规则的数片农田，田间道路纵横交错，农田中存在一些分散障碍物如风力发电机、电线杆、固定安装的传感器等[12]，如图1所示。

为简化复杂的农田工作环境以便于规划机器人工作区域与遍历路径，本文将田间道路自然分割的单片农田作为一级分区，通过栅格法对单片农田建模并对不规则障碍物进行膨胀处理，在此基础上划分单片农田内的二级分区并设置分区合并规则。

2.1 栅格化建模与障碍物膨胀处理

定义一个形状不规则且障碍物随机分布的单片农田，通过栅格法对农田建模时将机器人群共同的工作范围设置成栅格图中单元格的单位长度，栅格建模结果如图2a所示，空白单元格表示机器人可自由遍历的工作区域。对于障碍物边缘线与栅格边缘线不重合的情况，用二值形态学中的膨胀运算对不规则障碍物进行膨胀处理[13]。膨胀结果如图2b所示。

2.2 栅格分区与分区合并

根据膨胀处理后的障碍物形状及位置划分空闲矩形区域，如图3a所示。栅格分区步骤如下：

1）寻找横坐标或纵坐标相同的障碍物边界，并沿此边界画一条连接2个障碍物的分区线；

2）对于矩形或正方形障碍物，过障碍物左上角顶点画一条纵向直线，遇到其他障碍物或步骤1）形成的分区线即停止；过障碍物右下角顶点画一条横向直线，遇到其他障碍物或步骤1）形成的分区线即停止；

3）对于非矩形或正方形障碍物如障碍物D，按矩形障碍物数量最小化原则设置纵向虚拟分割线，将不规则障碍物分割成多个矩形，再转至步骤2）。

在栅格矩形分区之后进行分区合并，以尽量减少分区的数量。一个栅格分区与其邻近分区共同边长度相等则可以进行合并[14]，如图3a中的分区1、2、3可以合并为图3b中的分区4。分区时先合并可纵向合并的分区，再合并可横向合并的分区。

为保证对农田的全区域覆盖，在分区合并的环境地图基础上还原各障碍物的形状，将障碍物边缘线、膨胀后的障碍物边缘线以及分区线包围形成的封闭图形的空白区域按照“上-下-左-右”的顺序合并至邻近空白分区，找不到空白分区的不规则空白区域则设置为单独分区，障碍物还原后的分区效果图如图4所示。

3 基于改进遗传算法的分区遍历

在工作区域涉及多片农田时，农场中既存在一级分区（单片农田）又存在二级分区。本文在确定各一级分区遍历顺序之后再确定各一级分区内二级分区的遍历顺序，通过深度优先搜索算法（Depth First Search，DFS）根据确定好的遍历顺序在一级分区以及二级分区内遍历，同时根据机器人的工作量为其分配工作区域，实现工作区域的全覆盖。

3.1 基于遗传算法的分区遍历

优化DFS算法在一级分区与二级分区间的遍历顺序可以增加DFS算法规划的机器人工作区域的连续性进而减少机器人在环境地图中遍历的重复率。寻找DFS算法在分区间的最优遍历顺序首先需要通过构造对偶图的方式[15]确定形状规则或不规则的一级分区与二级分区的重心坐标，进而通过遗传算法寻找一条遍历所有分区重心且每个分区重心仅遍历1次的最短路径[16-18]，此最短路径中包含的分区重心遍历顺序即为DFS算法在分区间的最优遍历顺序。

本文通过交叉操作与交叉变异概率2方面改进遗传算法，旨在提高传统遗传算法跳出局部最优解的能力，减少迭代次数，提高遗传算法求解分区间遍历顺序的工作效率。

3.2 改进的交叉操作

遗传算法中的染色体采用整数编码，由各分区编号排列组成[19-21]，染色体适用度值与该染色体对应的遍历各分区重心的路径长度成反比[22-24]。传统遗传算法的交叉操作中两两染色体交叉产生2个新染色体的方式具有随机性[25]，虽然增加了种群多样性，但是算法收敛性差[26]。本文将混合粒子群算法的交叉操作应用于传统遗传算法的交叉操作中，通过染色体与迭代过程中出现的实时最优适应度值染色体交叉，在保证群体多样性的基础之上提高收敛速度。改进的遗传算法交叉操作如图5所示。

最优染色体与原染色体的交叉方式与传统遗传算法交叉操作两两染色体交叉的方式相同[27]。检测经过交叉操作的新染色体，若其适应度值高于原染色体则接受此新染色体，否则视此次交叉操作无效，保留原染色体。

3.3 自适应交叉变异概率

对于高适应度染色体，应设置较低的交叉概率 cp与变异概率 mp值以免破坏其染色体的优质基因结构[28]，对于低适应度染色体，则应该提高 cp与 mp值以将其淘汰并且生成新染色体[29]；在种群多样性较低时，应该适当提高低适应度染色体的交叉与变异概率以免算法陷入局部最优解。所以 cp与 mp的取值应根据染色体适应度值的高低与不同的种群多样性阶段自适应变化[30]。

本文根据种群实时最优适应度值maxf与种群实时平均适应度值avgf的关系定义当前种群多样性Fβ：

当 avgf逐渐向 maxf靠拢时，表明种群逐渐进化，各染色体向最优解靠拢，此时Fβ减小。

1）自适应交叉概率

根据f(t)与 maxf的关系，将不同染色体分为3等，自适应交叉概率调节机制如下：

式中 ctp为染色体t发生交叉的概率，最大交叉概率 cmaxp与不同时期种群多样性的大小有关。

2）自适应变异概率

变异概率一般在0.001～0.01之间[31]。自适应变异概率与自适应交叉概率的设置方式类似：

式中 mtp为染色体t发生变异的概率。

4 基于DFS算法的分区内遍历规则

DFS算法用来寻找从出发点至目标点的可行路径。算法通过依次访问与上一节点相邻的可行节点访问完图中所有与出发点有路径相通的节点[32]。

4.1 DFS算法在二级分区内的遍历顺序

设（m,n）为分区中的单元格，未被DFS算法遍历的单元格标记为“0”，已遍历的标记为“1”。

为保证机器人工作区域的连续性和减少机器人的转弯次数，建立P、Q两种分区遍历顺序矩阵：

DFS算法在分区内搜索下一步要遍历的单元格的过程如下：

式中下标q∈ { 1，2，3，4}，O1q表示矩阵O第1行第q列的元素，2qO表示矩阵O第2行第q列的元素。如果搜索到的新单元标记为“0”且在该分区范围内则以该单元格为新起点继续深度搜索并将q初始化为1且将该单元格标记为“1”，否则q从1开始依次加1搜索周围单元格。算法遍历至死角时则依次回溯已走过的单元格，同时根据公式（9）～（13）寻找新起点。

4.2 机器人工作区域与分区内DFS算法遍历起点与终点的确定

DFS算法搜索机器人作业路径的同时根据蒙特卡洛方法[33]计算当前单元格面积并计算已为机器人遍历的实时总面积，在满足机器人的工作区域要求之后记录算法走过的路径，继续深度搜索下一个工作区域。

DFS算法遍历完一个分区之后，根据改进的遗传算法规定的最优分区遍历顺序，DFS算法跳转至下一个分区的起点继续遍历。为保证机器人工作区域的连续性，选择下一个分区中最靠近上一个分区终点的单元格作为下一个分区的起点。

4.3 路径规划

通过DFS算法为机器人规划的工作区域可能涉及多个二级分区。机器人工作区域纵向跨度大于横向跨度的称为纵向区域，反之为横向区域。

机器人在纵向区域（横向区域）内从其工作区域最左端的最下方单元格开始遍历，在进入一列（一行）单元格遍历时检测进入该列（行）单元格的入口与该列（行）单元格两端的距离，优先向距离短的一端遍历，之后回溯遍历该列（行）中未遍历的部分，在未遍历部分的每个单元格中均按照“左-纵向-右”（“下-横向-上”）的顺序搜索工作区域进行遍历。当四周无可遍历单元格时，按照机器人群遍历面积重复率最低原则评估未遍历区域中的新遍历起点，并应用A*算法和八邻域搜索法规划遍历到达新起点的路径[34]。

5 算法仿真

为验证改进遗传算法的收敛能力与寻优能力，以及机器人群全区域覆盖策略对机器人群总遍历面积重复率优化效果，本文在设定多组试验样本的基础上，分别通过MATLAB 2014软件对改进遗传算法与机器人群全区域覆盖策略进行仿真分析。

5.1 基于路径代价与收敛速度的不同算法仿真结果与分析

分别定义10、20、30个分区的中心点坐标，对比传统遗传算法、模拟退火算法与本文改进遗传算法对不同分区数量规模计算得到的遍历各分区重心的路径长度、算法收敛时的迭代次数与耗时，结果如表1所示。其中传统遗传算法与改进遗传算法的种群规模均设置为75，最大遗传代数均设置为200；传统遗传算法的固定交叉与变异概率设置为0.9与0.01，改进遗传算法的最小交叉概率与最小变异概率设置为0.7与0.006；模拟退火算法的初始温度与终止温度设置为1400与 1× 10-6，各温度下的迭代次数（链长）设置为1100，降温速率设置为0.9。

表1 不同算法对不同分区规模的路径规划结果 Table 1 Planning results of different algorithms for different partition sizes

由表1可知，在分区规模为10、20时，传统遗传算法与模拟退火算法均能得到与改进遗传算法相近的路径长度，但算法收敛时的迭代次数与耗时均是改进遗传算法的数倍。在分区规模为30时，改进的遗传算法所获得的路径长度分别比传统遗传算法与模拟退火算法减少2.8%与9.3%，收敛时的迭代次数分别减少69.5%与19.0%，耗时分别减少64.2%与9.9%。

图6a与图6b为3种算法在分区规模为30时的路径长度随迭代次数的变化曲线。从图6a中可以看出，在迭代次数为50次之前，改进的遗传算法的曲线斜率的绝对值大于传统遗传算法，说明改进的遗传算法收敛速度更快。从图6b中可以看出，模拟退火算法的实时最优路径长度随迭代次数的增加呈现阶梯式的下降，且在算法收敛之前出现了5～6个较明显的平台期，说明模拟退火算法容易陷入局部最优。平台期的出现容易导致算法得不到全局最优解，而改进遗传算法无较明显的平台期，且在收敛速度与寻优能力方面均优于模拟退火算法。

5.2 路径遍历仿真结果与分析

本小节重在验证复杂环境下机器人群工作区域分配以及路径规划方案，故暂不使用本文设计的任务分配方案分配各机器人工作量。仿真试验中将图4所示农田中376.75 m2的总工作量随机分配至6个机器人，1～6号机器人的工作量分别为75.91 、36.80、52.97、66.77、51.30和93.00 m2。在此基础上通过改进遗传算法与DFS算法规划各机器人工作区域继而规划各机器人的工作路径，最后统计DFS算法对农田工作区域的覆盖率与机器人群遍历面积与农田面积的重复率。

DFS算法的遍历路径如图7a所示，在图7a确定的各机器人工作区域的基础上，根据本文设置的路径规划方案进行各机器人路径遍历仿真，结果如图7b所示。因DFS算法/机器人在栅格图虚拟栅格中遍历，故在仿真图中DFS算法/机器人遍历至一个栅格重心点即表示完成对该单元格的遍历。

以算法规划的遍历工作区域面积与原任务要求的遍历面积的比值定义面积覆盖率。由图7a可知，通过改进的遗传算法与DFS算法相结合规划的各机器人工作区域可以保证工作区域对农田的100%覆盖。机器人的工作区域是否连续将影响该机器人的作业面积重复率，从图7a中可以看出，除了3号机器人的工作区域出现2个分离的子区域外，其余机器人的工作区域均为连续。

定义机器人i的遍历面积重复率is为

式中iS表示机器人i的实际遍历面积。

设置另外4副与图7形状大小相同的环境地图，分别在4副地图中设置障碍物总面积与图7中障碍物总面积相等但数量不等的3、5、9、11个障碍物，1～6号机器人组成的机器人团队分别在4副环境地图中遍历，各机器人的工作量分别为75.91、36.80、52.97、66.77、51.30和93.00 m2。以地图中障碍物在X轴与Y轴的标准差表征障碍物的离散度。不同障碍物数量下的分区数量以及机器人总遍历面积重复率如表2所示。

由表2可知，障碍物数量的增多以及障碍物分布离散程度的增加使分区数量增加，机器人群总遍历面积重复率也随之增加。在11个障碍物时，分区数量达到21个，机器人群总面积重复率达到23.4%。

表2 不同障碍物数量下的机器人群遍历面积重复率 Table 2 Repetition rate of the traversal area of the robot groups with different number of obstacles

在图7障碍物数量、位置、形状不变的基础上，设置3种形状不同的农田，其中第一种环境地图仅有1个一级分区，后2种环境地图分别由纵向与T形田间道路将农田分割成2个二级分区。各环境地图的总工作面积均为376.75 m2，1～6号机器人组成的机器人团队分别在3种环境地图中遍历，各机器人的工作量分别为：75.91、36.80、52.97、66.77、51.30与93.00 m2。机器人群的遍历路径如图8所示。

由图8可知，3种农田环境下通过DFS算法规划的工作区域均可以实现对农田的100%覆盖，机器人群进行全区域覆盖的面积重复率分别为13.1%、11.9%和6.7%，说明本文设计的机器人群全区域覆盖方案对多片工作区域、形状多元化、多种异形障碍物分布的农田环境具有较好的适应性。

6 验证试验

为验证本文任务分配方案下机器人群能否在规定的时限要求内完成目标任务量，以及机器人群全区域覆盖策略在实际应用中对遍历面积重复率的优化作用，以数字生态农业农场中的信息采集机器人为对象进行任务分配与全区域覆盖遍历试验。试验地点为山东理工大学图书馆南侧草坪。通过数字生态农业农场云平台人机交互界面将整体工作区域划分为图9由虚拟道路分割成的3个子区域，并在整体工作区域中设置8个异形障碍物。

实际农业生产过程中有关任务分配的4个性能参数权重因子根据农场管理者对各性能参数的偏好制定，本文试验中设定4个性能参数权重因子均为0.25，根据农场中各机器人的历史工作记录统计各机器人的工作效率（hm2/h）、服务质量（取值范围：0～100）、能耗（W）、故障率（取值范围：0～1）以及历史工作量（hm2）等参数数据，总工作量需求值设置为1 hm2，任务时限要求为25 min。信息采集机器人搭载RMONCAM HD600红外摄像头进行农情勘测遍历试验，各机器人的摄像头对地工作范围均设置为1.5 m。

根据本文任务分配方案对农场中现有的10台信息采集机器人进行任务分配，最终选择7～10号机器人参加工作，根据公式（3）计算各机器人的实际工作量，如表 3所示。4台机器人的工作效率分别为0.810、0.594、0.648和0.702 hm2/h。以整体工作区域的左下角为起点。实际遍历面积表示机器人从进入草坪至驶出草坪全过程中遍历的面积；覆盖率为机器人在目标工作区域上的遍历面积与目标工作区域面积的比值；遍历面积重复率的定义与5.2 节一致；实际工作时间为机器人从起点至遍历完其工作区域的时间。机器人群现场遍历试验如图9所示。

通过各信息采集机器人实时回传至云平台的工作信息统计各机器人的实际遍历面积、对原定工作区域的覆盖率、机器人群总遍历面积重复率以及完成遍历任务的实际工作时间，结果如表3所示。

表3 各机器人工作数据统计 Table 3 Working data statistics of robots

由表3可知，4个试验机器人对目标工作区域的覆盖率均为100%，且能在规定的时限要求内完成分配的任务量，遍历面积重复率分别为5.77%、4.14%、6.75%以及4.85%，说明本文设计的农业机器人群任务分配与全区域覆盖方案能在保证机器人群任务完成度与优化机器人群遍历面积重复率的基础上，实现机器人的协同作业。

7 结论

1）本文在考虑遗传算法不同种群多样性阶段与染色体适应度值差异的基础上提出了自适应交叉变异概率，将混合粒子群算法与传统遗传算法相结合建立改进的遗传算法交叉操作。仿真试验表明，改进遗传算法所获得的遍历各分区重心的路径长度分别比传统遗传算法与模拟退火算法减少2.8%与9.3%，算法收敛时的迭代次数分别减少69.5%与19.0%，收敛到最优解的耗时分别减少64.2%与9.9%。

2）本文综合考虑农业机器人的异质性差异设计机器人群任务分配方案；通过分区简化工作环境，并分别通过改进遗传算法与深度优先搜索算法解决分区间与分区内的遍历顺序问题并根据机器人工作量分配其工作区域；通过设计机器人在其工作区域内的路径规划方案实现机器人群对整体工作区域的全覆盖。仿真试验结果表明，在包含3、5、7、9和11个障碍物的不同环境地图中，机器人群总遍历面积重复率分别为6.3%、8.9%、16.7%、21.7%和23.4%；障碍物数量、形状、位置相同而农田形状不同的环境地图中，机器人群总遍历面积重复率分别为16.7%、13.1%、11.9%与6.7%。

实际农业生产过程中，各机器人的性能参数不可能完全一致，同质机器人只在理论上存在。对于同质机器人群系统、异质与同质并存的机器人系统的协同作业策略，依然可以使用本文设计的任务分配方案根据各机器人性能参数与工作效率等选择机器人参加工作并计算各机器人工作量，确定任务分配结果后根据本文设计的全区域覆盖方案确定各机器人工作区域和路径规划。