同种农机机群动态作业任务分配方法

王 猛，赵 博，刘阳春，伟利国，汪凤珠，方宪法

（中国农业机械化科学研究院土壤植物机器系统技术国家重点实验室，北京 100083）

0 引言

中国是农业大国，农业机械化可极大提高农业生产效率、减轻农民体力劳动。随着农机合作社和农场作业模式的快速发展，农机和土地都呈现集中的趋势，如何更有效地规划机群作业，提高作业效率，对有作业窗口期要求的农业生产具有重大作用。

动态任务分配是机群作业领域的一个重要研究内容，动态任务分配指机群作业过程中，面对导致机群无法继续执行原有作业计划的意外情况时，根据任务执行进度和机群位置，对作业任务计划进行相应的调整使得机群能够继续执行并完成新的任务计划。动态任务分配方法在机器人搜索、无人机作战、水下机器人搜索和无人机搜索等领域有了较深入的研究和发展[1-5]。研究人员对静态任务分配技术研究较多，研究方法包括基于作业经验和效率的任务分配[6-8]、基于聚类的任务分配[9]、基于博弈论的任务分配[10]和基于启发式算法的任务分配[11-16]等，对动态任务分配研究较少，主要采用合同网算法，动态任务分配比静态任务分配更加复杂[17-20]。农机作业领域的相关研究有任务规划和调度等。其中任务规划指规划农机执行任务的先后顺序和田块间的路径，曹如月等[21]采用蚁群算法解决机群作业任务规划，使农机行驶的距离最短；Jensen等[22]研究了一台运粮车对多台收割机运粮的田块内和田间的路径规划方法，使农机作业代价最小；姚竟发等[23]提出联合收割机多机无冲突协同作业路径优化算法，缩短了矩形农田和梯形农田农机作业时间。农机调度是对一系列作业点选择合适的行车路径，让农机有序地通过它们，在满足作业点的时间窗和所需农机数约束条件下，达到路程最小或收益最高[24-28]。随着我国农机合作社和农场作业模式的快速发展和农机管控平台的开发[28]，农机和土地趋于集中且参数可知趋势，如何在合作社或农场土地范围内对多台农机进行有效的任务分配，并在有突发状况条件下进行合理的任务再分配对具有强“农时”性的农业生成具有重要意义。

本研究以同种作业农机为研究对象，以农机合作社或农场作业模式为作业场景，综合考虑机群中作业时间最长的农机作业时间、农机机群的油耗和路上的路程建立机群代价，以代价最小作为优化目标，构建基于合同网算法的机群动态任务分配招投标流程和投标代价函数，针对农机作业特点优化合同网算法以降低机群作业代价、得到最优动态任务分配结果。

1 机群系统体系结构

根据农机机群动态任务分配特点设计了农机机群作业的体系结构，主要包括农机、服务器和客户端三个部分。其中农机安装车载计算机、北斗定位模块和无线自组网模块等，可实现自身定位和与其他农机通信；服务器中储存田块信息和农机信息并且具有计算功能；客户端可以选择和下发任务到指定作业机群。其结构如图1所示。

2 农机机群代价数学模型

2.1 基本假设

农机机群作业过程中，作业情况往往过于复杂，为突出动态任务分配问题，简化其他次要问题，做出农机作业的基本假设。

1）作业机群为具有高精度定位与导航功能的同种作业农机。

2）任务田块数量大于作业农机数量。

3）每个任务田块只有1台农机作业，同一台农机可以在连续多个任务田块作业。

4）不考虑其他补给或配合农机的调配。

5）任务田块没有严格的作业时间窗口要求。

6）农机机群从车库出发，完成全部任务后返回车库。

7）机群的作业时间为机群中用时最长农机的作业时间。

2.2 目标函数

假设作业的农机数量为m，任务田块的数量为n，用A={a1,a2,…,am}表示农机集合，T={T1,T2,…,Tn}表示任务田块集合，任务分配是指将任务田块集合T按一定的作业顺序分配给农机集合A。

农机作业过程中，对于农资、能源补给类车辆常以农机的路程为代价；对于需要在田间作业的农机常以农机作业的总时间为代价。本文考虑机群的作业时间、油耗和路程建立目标函数：

式中f为机群代价函数，α为系数向量，α=[1,0,0]表示以机群作业时间为代价，α=[0,1,0]表示以机群作业油耗为代价，α=[0,0,1]表示以机群到达作业地块的路程为代价；ti为农机ai的作业时间，h；ci为农机ai的油耗，L；si为农机ai路上的路程，km。

当系数确定的情况下，当代价函数最小时，对应的任务分配方案即为该确定系数下多机协同最优分配方案。

2.2.1 田间路径规划

参考文献[29-31]，以农田最长边为作业方向可有效提高作业效率，降低作业代价；满足半圆形调头时采用半圆形调头，不满足半圆形调头时采用弓形调头可提高调头效率，本文以不满足半圆形调头情况为例进行研究。

地头转弯区域分为种植农作物和不种植农作物2种情况，本文以种植农作物为例设置作业模式，根据文献[32]，为实现作业区域的全覆盖，采用直行与绕行相结合的方式进行路径规划，如图2所示。

以图2所示的带斜边的多边形田块为例，根据文献[32]，弓形路径调头中地头最小转弯地带宽度E∏为

式中R为农机的最小转弯半径，m；W为作业幅宽，m；Lk为农机机组中心至最远农具作业部件的距离，m。

为使绕行路径可以满若干幅宽作业，令地头转弯地带宽度为农机幅宽的整数倍，则地头转弯宽度E为

其中

弓形路径调头过程中，根据几何关系，农机转弯跳过的最小路径smin为

根据文献[30，33]，采用弓形调头路径时实现作业区域全覆盖的的最小路径数量Bmin为

作业过程中，当田块剩余宽度小于农机作业幅宽时，收获机械可直接进行作业；播种机械等为避免重复作业可采用小型机械补耕或调整相邻作业行出种行数的方式，本研究中田块数量较多且分散，采用后种方式。农机在田块中总的纵向路径数量N为田块垂直于作业路径的宽度与作业幅宽的比值，则N为

式中bT为任务田块垂直于作业路径的宽度，m。

当(N-2kE)≥Bmin时，满足弓形调头要求，将农田划分为多个标准区块和1个非标准区块，为使农机在每个区块都能完成全覆盖作业，令标准区块路径数量为Bmin，非标准区块数量BN≥Bmin，采用弓形调头路径进行逐区块作业。图3所示为smin=2时的区块划分结果，其中左侧为标准区块右侧为非标准区块。标准区块数量ks为

标准区块路径编号qi,j为

式中qi,j为田块中第j个区块内第i个顺序的路径编号。

非标准区块路径数量BN为

非标准区域跳过的路径数量sN为

非标准区块路径编号为

农机进入和离开田块位于同一端地头时，作业路径数量为偶数，位于不同端地头时则为奇数。若作业路径数量为偶数，要实现农机进入和离开农田位置位于不同端地头、或作业路径数量为奇数要实现农机进入和离开农田位置位于同一端地头时，需要在绕行区域增加一条空行路径。当2个需要作业的田块地头相邻，且农机可以从地界处进入田块时，令要进入的田块为目标田块，正在作业的田块为当前田块，为方便农机进入目标田块后经过最小的调整就能作业，令当前田块的最后作业路径与目标田块的第1条作业路径横向偏差最小，如图4所示，其中No.last（白色）行为当前田块的最后作业行，区块划分中不包括No.last行。

根据文献[32]，弓形调头路径近似长度S∏为

式中x为调头中2条路径的距离，m。

(N-2kE)2kE且(N-2kE)

鱼尾形调头路径最小转弯地带宽度ET为

鱼尾形调头路径近似长度ST为

2.2.2 农机作业时间

农机ai的作业时间ti主要由农机在路上的时间和农机在田块的时间2部分构成：

式中tRi为农机ai在路上的时间，h；tFi为农机ai在田块的时间，h；si为农机ai在路上的总路程，km；vi为农机ai在路上的速度，km/h。

2.2.3 农机作业路上的总路程

建立n个任务田块间农机可行驶的实际最短距离矩阵，若将车库作为第0个任务，得到矩阵D为

式中dij为第i-1个任务田块到第j-1个任务田块之间的实际可行驶距离，km，i,j=2,3,…,n+1,且i≠j。

如果j、k两个任务田块地头相邻，且农机可从地界直接驶入田块进行作业，则dj+1,k+1=0。

总路程si由3部分组成：农机ai从车库到其第一个任务田块Tj的路程d1,j+1、农机从第j个任务田块Tj到下一个任务田块Tk的路程dj+1,k+1、农机从最后一个任务田块Tl回到车库的路程d1,l+1，其中j,k,l=1,2,…,n。具体计算如下：

其中

农机在田块的作业时间tFi主要由作业时间、调头时间和直线空行时间构成：

式中li,j,k为农机ai在任务田块Tj的第k条直行路径的长度，km；bi,j,k为农机ai在任务田块Tj中绕行的第k条横行路径的长度，km；Si,j,k为农机ai在任务田块Tj的第k条转弯路径的长度，km；Ni,j,t为农机ai在任务田块Tj的调头数量；lB为农机ai在任务田块Tj的空行直线路径长度，km；vwi为农机ai的作业速度，km/h；vti为农机ai在田块的调头的速度，km/h。 其中

2.2.4 农机作业油耗

农机ai的作业油耗ci主要农机在路上的油耗和农机在田块的油耗由2部分构成：

式中cRi为农机ai在路上的油耗，L；cFi为农机ai在田块的油耗，L；Fci为农机ai非作业状态下平均每公里的油耗，L/km；Fwci为农机ai作业状态下平均每公里油耗，主要由作业油耗、调头油耗和直线空行油耗构成，L/km。

3 动态任务分配

农机机群作业过程中，受一些因素的影响，机群无法继续执行原有作业计划，需要根据任务执行进度和机群状态进行动态任务分配。农机机群作业过程中需要进行动态任务分配的情况主要有：①新增作业任务；②作业过程中有农机出现故障无法继续作业；③原有作业任务中一些作业任务取消。其中情况①、②是多机作业过程中最常见的情况，本文主要针对情况①、②进行动态任务分配研究。

动态任务分配分为集中式和分布式，在本文的体系结构中，集中式任务分配由服务器负责整个机群的任务分配，分布式任务分配由整个机群联合处理进行任务分配。其中，在集中式任务分配中服务器处理所有计算，需要服务器具有强大的计算功能，对终端设备要求较低，当终端很多时会导致响应速度变慢；在分布式任务分配中所有终端都参与计算，对终端设备要求较高，处理能力强。考虑到目前农机终端计算机都有较强的计算能力，为减少服务器压力，采用分布式方式处理动态任务分配问题。

3.1 合同网算法

合同网算法（CNP，Contract Net Protocol）是处理分布式任务分配方法的常用算法，通过模仿经济行为的“招标-投标-中标”机制来实现任务分配[34-36]，其基本流程如图5所示。

使用CNP解决农机机群任务分配过程中，服务器端作为招标者、农机端作为投标者。假设机群原分配任务及顺序为最优分配结果，动态任务分配过程中投标者计算投标值时，使用将招标任务插入原有任务序列的方法计算农机ai执行新任务田块Tj的代价Δfij，招标者选择Δfij最小的招标者作为中标者。

农机ai对任务田块Tj投标的代价函数Δfi j为

式中tij为第i台农机添加任务田块Tj后所需作业的总时间，h；tmax为招标开始前整个机群的机群工作时间，h；Δci为第i台农机添加任务Tj后所需油耗的增量，L；Δsi为第i台农机添加任务Tj后路上路程的增量，km。

当第i台农机中标任务田块Tj后整个机群代价f'为

式中f为招标前机群的总代价。

3.2 改进合同网算法

3.2.1 任务分配结构设计

为减少服务器的计算量，设计了基于农机间招-投标过程的动态任务分配方法。如图6所示，服务器端设有管理者和公告板2个模块，管理者可以与客户端和农机终端进行通信，当有新任务需要动态分配时，管理者通知相关农机读取公告板；公告板接收管理者信息并展示，起到信息共享作用；农机终端可与管理者通信、读取公告板信息；动态任务分配在农机终端之间进行。

3.2.2 算法改进

在设计的动态任务分配结构中，任务分配过程在正常作业的农机间进行，所有作业的农机作为投标者，其中一台农机既作为招标者又作为投标者。招投标过程中可能出现以下问题，如果招标者距离其他投标者距离过远会加大丢包率，影响任务分配效果；如果招标者为最终的中标者，多次招投标通信为无效通信；在有新任务加入的情况下，农机原有任务及序列可能不是最优分配。基于以上问题设计了几种改进基于公告板合同网算法的几种办法。

1）选择招标者

任务分配的招投标过程由农机间无线网络完成通信，选择招标者使招标者与投标者之间的直线距离和最短

式中(xi,yi)为农机ai当前位置的高斯平面坐标，m。

2）设定招标阈值

由于招标者自身也作为投标者，为减少无效投标，降低任务分配过程中农机间的通信，采用设定招标阈值的方法，招标者在对任务Tj进行招标前，首先计算招标者自身执行该任务的最小代价Δf j作为动态阈值。

式中Δfbidj为招标者执行新增任务Tj的代价。

投标者ai接收招标信息并计算自身执行该任务的最小代价Δfij，如果Δfij<Δf j发送投标信息，如果Δfij≥Δf j，则不发送投标信息。

3）中标者任务再分配

为使农机任务分配更加均衡，减小农机间作业代价的差，建立单机代价函数，按中标农机作业代价从高到低的顺序依次作为招标者进行任务再分配，i台农机的代价函数fi为

按招标农机任务面积从小到大的顺序进行任务再分配，农机ai对任务田块Tj招标的阈值Δf j为

式中ti-j为农机ai去掉任务田块Tj后完成任务的时间，h；Δci'为农机ai去掉任务田块Tj后减少的油耗，L；Δsi'为农机ai去掉任务田块Tj后减少的路程，km。

4）农机间任务交换

农机执行任务过程中有部分代价发生在从一个任务到另一个任务的路程中，进行合理的任务交换以减少总路程是降低整体代价的一个办法。

设农机ai执行任务Tj的路程代价fsij为

式中si-j为农机ai去掉任务Tj后的路程，km。

任务交换流程如下：

① 完成任务代价最大的农机ai计算出最大路程代价max(fsij)和对应的任务田块Tj。

② 农机ai作为招标者对任务田块Tj进行交换招标；

③ 其他工作正常的农机作为投标者，投标者将任务田块Tj依次与自身未作业任务田块进行替换，并使用2-opt进行优化，计算替换后自身最小代价；

④ 如果替换后代价小于替换前，该任务作为投标信息；

⑤ 招标者计算删除任务j后加入每个投标任后的代价，并取最小代价fik和对应的任务田块Tk；

⑥ 如果fik

3.3 基于改进合同网算法的任务分配流程

基于改进合同网算法的任务分配流程如图7所示。

4 仿真试验

由于农机油耗与农机牵引力正相关，每公里油耗确定困难,为验证改进合同网算法动态任务分配效果，以α=[1,0,0]为例，从中国农机开发的农业机械化精准作业平台选择包括多个较集中且平整地块参数作为仿真试验地块参数，选择农机合作社常见拖拉机及机具参数作为仿真试验农机参数，试验田块如图8所示，共15个任务，任务主要参数如表1所示，田块较规则，均为标准矩形田块；共4台农机，农机主要性能参数如表2所示。分别用传统合同网算法和改进合同网算法对新增任务情况和出现故障的情况进行动态任务分配仿真试验。

表2 农机性能参数 Table 2 Performance parameters of agricultural machineries

表1 任务田块参数 Table 1 Task field parameters

4.1 有新任务加入情况的动态任务分配试验

假设农机a1、a2和a3共同进行作业，分别以{T1～T10}、{T1～T11}和{T1～T12}为原任务，{T11～T14}、{T12～T15}和{T13～T15}为新增任务。使用遗传算法将原任务进行静态任务分配，原任务的多机协同代价分别为7.63 、8.57 和9.22 h。实际作业过程中，假设农机同时开始作业，新增任务可能发生在农机作业后的各个阶段，根据原有任务的作业时间，假设当作业时间分别为2、4、6 h时进行新增任务的动态任务分配，任务分配结果如表3所示。

表3 新增任务情况下动态任务分配结果 Table 3 Dynamic task allocation results in the case of new tasks

{T1～T10}为原任务{T11～T14}为新增任务时，动态任务分配前的任务分配结果为农机a1田块作业顺序为1→2 →4→6，农机a2田块作业顺序为7→8→10→9，农机a3田块作业顺序为3→5，动态任务分配结果表明，基于改进合同网算法比基于传统合同网算法的动态任务分配农机机与服务器通信次数较少85%，机群多机协同时间代价降低7.34%～8.05%。

{T1～T11}为原任务{T12～T15}为新增任务时，动态任务分配前的任务分配结果为农机a1田块作业顺序为5 →10→9→11，农机a2田块作业顺序为2→1→3→4，农机a3田块作业顺序为6→8→7，动态任务分配结果表明，基于改进合同网算法比基于传统合同网算法的动态任务分配农机机与服务器通信次数较少85%，机群多机协同时间代价降低4.41%～6.67%。

{T1～T12}为原任务{T13～T15}为新增任务时，动态任务分配前的任务分配结果为农机a1田块作业顺序为1→3 →11→9→12，农机a2田块作业顺序为7→8→6→5，农机a3田块作业顺序为4→10→2，动态任务分配结果表明，基于改进合同网算法比基于传统合同网算法的动态任务分配农机机与服务器通信次数较少80%，机群多机协同时间代价降低0.83%～5.58%。

由任务分配结果可知，在不同时刻执行新增任务的动态任务分配，基于改进合同网算法的结果都优于基于传统合同网算法的结果，在新增任务试验情况下农机与服务器的通信次数降低80%～85%，机群时间代价降低0.83%～8.05%，均有较明显降低。试验结果表明，在新增任务情况下，基于改进合同网算法的动态任务分配方法性能更加优秀。

4.2 有农机出现故障情况的动态任务分配试验

播种作业过程中，故障农机所在作业行及作业行中间的未作业行由故障农机修复后完成作业；收获类作业将未作业区域全部规划进行作业。以收获作业为例假设作业开始前将任务T1～T15分配给农机a1～a4，任务分结果为：农机a1的田块作业顺序为15→5→1→3；农机a2的田块作业顺序为13→12→8→14；农机a3的田块作业顺序为2→4→6→7；农机a4的田块作业顺序为9→10→11；机群作业时间代价为10.26 h。分别假设开始作业1、3、5 h后农机a3发生故障，对农机a3未完成的任务进行动态任务分配，任务分配结果如表4所示，基于改进合同网算法比基于传统合同网算法的动态任务分配农机与服务器通信次数较少77.4%，机群多机协同时间代价降低1.77%～12.89%。

表4 有农机故障情况下动态任务分配结果 Table 4 Dynamic task allocation results in the case of agricultural machinery failure

由任务分配结果可知，在有农机出现故障的情况下基于改进合同网算法的动态任务分配结果比基于传统合同网算法的动态任务分配结果机群时间代价平均降低5.86%，最高降低12.89%，农机与服务器间的通信次数降低77.4%，均有较明显降低。试验结果表明，在有农机出现故障情况下，基于改进合同网算法的动态任务分配方法性能更加优秀。

仿真结果表明，传统合同网算法和改进合同网算法都可以用来处理动态任务分配问题。其中，使用改进合同网算法可以得到更好的任务分配效果并且减少农机与服务器间的通信次数，同时，在使用改进合同网算法的任务分配过程中，服务器只执行简单的通信而不参与任务分配的计算，将全部计算和部分通信放在农机终端计算机，充分利用了农机终端计算机的计算能力，大大减轻了服务器负担，因此，基于改进合同网算法的动态任务分配方法具有明显优势。

5 实际播种作业试验

为验证本文基于改进合同网算法的动态任务分配方法在实际作业场景中的有效性，进行实际播种作业试验。图9为内蒙古兴安农垦吐列毛杜农场一区某日播种作业情况，3台播种机共完成11个田块任务。根据中国农机院农机合作社管理云服务平台得到播种机性能参数和任务参数，3台播种机所用拖拉机型号分别为约2台翰迪尔2204拖拉机和1台约翰迪尔1854拖拉机，主要性能参数如表5所示，11个任务参数如表6所示。

3台播种机执行任务的实际作业田块顺序分别为1→2→8 →9→10→11、6→7和3→4→5，如图10所示，其中亮色区域为相应播种机该日作业田块。3台播种机的理论作业时间分别为14.14 、5.78 和6.50 h。播种机1率先完成任务1和任务2回到车库后接到新增任务8、9、10和11，造成任务分配不均衡播种机1作业时间过大，导致机群作业代价增加。

假设3台播种机同时出发作业，当作业时间分为2、4、6 h时进行基于改进合同网算法的动态任务分配试验，结果如表7所示。当作业时间分别为2、4、6 h时，经过基于改进合同网算法的多机协同动态任务分配机群时间代价比实际作业理论机群时间代价降低30.20～34.09%。

表7 不同时间下试验结果 Table 7 Experiment results at different times

由试验结果可知，在不同时间执行动态任务分配均可得到较优的任务分配结果，任务分配后机群代价比实际作业理论机群代价降低30%以上。因此，基于改进合同网的动态任务分配方法可以较好的解决实际作业情况下有突发情况的动态任务分配问题。

6 结 论

1）本文对同种作业农机机群动态任务分配问题进行了研究，以机群中用时最长农机的作业时间、机群的油耗和机群的路程为代价建立代价函数和目标函数。

2）提出了基于合同网算法的动态任务分配方法和改进合同网算法的4种方法，包括基于直线距离和最短的招标者选择方法、基于招标者作业能力的阈值设定方法、基于最小面积的任务再招标方法和基于路程最大的任务交换方法。

3）选择适当田块作为任务田块，分别对有新任务增加的情况和农机出现故障的情况进行了基于合同网算法和基于改进合同网算法的动态任务分配仿真试验，仿真结果表明基于改进合同网算法的动态任务分配结果比基于传统合同网的动态任务分配结果农机与服务器通信次数减少77.4%～85.0%，机群时间代价均降低0.83%～12.89%。

4）进行实际播种新增任务情况下动态任务分配试验，由试验结果可知，在不同的时间执行基于改进合同网算法新增任务的动态任务分配，任务分配后机群时间代价比真实机群理论时间代价降低30.20%～34.09%。试验结果表明，基于改进合同网的农机机群动态任务分配方法可以解决机群作业过程中有突发情况且无严格作业时间窗口的动态任务分配问题。