基于资源拍卖的农业多机器人任务分配

赵 辉 郝梦雅 王红君 岳有军

1(天津理工大学天津市复杂系统控制理论与应用重点实验室 天津 300384)2(天津农学院工程技术学院 天津 300384)

0 引 言

在农业生产中，多机器人协作对于实现规模化、多样化、精准化起重要作用，并在实际中得到广泛运用[1]。多机器系统研究中，任务分配问题(Multi-robot task allocation，MRTA)是基础和研究热点之一[2]。

MRTA的目标是建立机器人和任务之间的有效关系。传统的MRTA问题处理任务时，每个任务只能通过一个已符合需求的机器人来完成[3]，当任务需求超出单个机器人能力时，机器人则无法完成任务。因此，针对单机器人这一任务缺陷，Parker等[4]提出了使一组异构机器人形成联盟，共享传感器来完成任务，但计算成本较高。为了降低计算成本，Chen等[5]设计了两个基于联盟的资源约束分配方法，即序列联盟和整体联盟方法，计算复杂度显著改进，但完成任务机器人所需的资源数量须事先指定，难以在实际中实现。同时采用贪婪的解决方案，可能导致资源浪费。为降低时间和通信复杂度，Cao等[6]提出组级任务分配和成员级任务分配，采用改进的PSO-FSA和分布式拍卖算法求解。

近年来基于分布式的拍卖分配算法在多机器人任务分配中受到广泛关注，基于拍卖的方法是以市场经济原则为基础，使其利润最大化，从而导致收入再分配和产出的有效生产。与集中式方法相比，其可以得到计算量小、可扩展性高的灵活任务分配结果，并有效地产生次优解[7]。姜来浩等[8]为解决多机器人在搜索过程中多任务分配和多机器人利用率问题，提出了一种带有即时拍卖的K-means聚类捆绑式拍卖算法，通过K-means聚类算法解决多机器人系统中的多任务捆绑问题，再运用捆绑式拍卖机制把聚类分配给相应的机器人。赵明明等[9]针对多无人机实现同时攻击目标的任务，提出了拍卖算法，使无人机在不确定因素中到达目标的时间趋于一致。许可等[10]提出了将任务根据类型分组，以总收益最大为目标函数，考虑无人机能力、任务分组等约束条件建立模型。设计了带共享存储中心的分布式拍卖算法，通过无人机个体目标的最大化实现了整体目标最大化，但该方法未考虑再充电问题，机器人使用初始给定的能量来执行任务。

综上所述，现有基于拍卖方法的研究虽然较多，但仅考虑在路径长度、时间下的最优分配。实际工作中，机器人存在资源填充问题，当机器人在长期执行任务中资源量不足(如电池电量低或机器人存储量少)时，机器人将无法执行或按时完成其给定的任务，从而增大了运行时间成本，分配结果与实际工作将产生较大偏差，从而失去预估分配的意义。

因此，本文提出一种基于资源的拍卖算法，与现有的拍卖算法相比，机器人在进行任务分配时，认为资源是可再填充的或可替换的。在分配中，每个机器人都会考虑其工作期间的资源消耗，即出价。当它们中的任何一个低于一定的阈值时，机器人就会立即停止执行任务，并访问各自的站点来补充它们的资源。通过考虑机器人的执行能力，采用分散的竞价和分配过程，通过仿真实验可得，该算法在任务完成时间和机器人之间的通信等方面最大限度地提高了机器人资源的使用效率，并且任务分配消耗出价与实际工作消耗更接近，增加了机器人工作的准确性。

1 问题描述

多机器人协同任务规划需要多个农机和多个作业地块之间建立一种映射关系，在满足实际作业约束条件的前提下，生成一个最优的任务调度方案。现有的大多数研究是通过任务中机器人走过的距离、完成任务所需的时间或固有的资源进行任务分配，从而导致分配出现“就近”问题[11]。同时，机器人在长期任务操作过程中存在能量消耗问题，产生能量限制，影响分配结果。因此，本文在进行任务分配时，既考虑了机器人数目约束、工作时间约束、距离约束，又加入了任务执行能力的约束，考虑了机器人在任务执行期间的电量消耗问题。根据农田机器人智能自主执行任务场景，以性能指标最小为目标函数，构建MRTA问题描述，使各个农机有序地为农田地块服务，降低整个系统的执行代价，提高作业效率，实现区域农田内的多机协同作业调度管理。

1.1 约束指标

1) 机器人数目约束。在实际农田环境中任务目标数目远远大于机器人数目，因此在进行任务编队分配时，要求每个机器人执行多个目标任务；所有的任务都应分配给机器人；每个任务由一个机器人执行。

(1)

(2)

式中：ζ是机器人的集合，即ζ={1,2,…,NR}；ψ为任务集合，即ψ={1,2,…,NT}；Ai表示机器人i的有序任务列表；如果任务j在Ai中，则e(j，Ai)=1，否则等于0。

2) 电量约束。机器人i从起始点到任务j的距离可以表示为：

(3)

任务i与任务j的距离表示为：

(4)

根据机器人和任务目标的位置，计算机器人执行期间各自的电量消耗，为确保机器人自身安全，要求完成任何任务后机器人所有资源元素都应高于阈值。

(5)

式中：ξ为资源集合，即ξ={1,2,…,NL}。

3) 任务载荷数目。任务载荷表示每个机器人可以执行任务数目，约束可以表示为：

(6)

1.2 任务代价

为了考虑在任务分配中机器人的资源影响，可以用全局目标函数的最小化表示：

(7)

2 算法设计

2.1 MTSP模型

当任务数量多于机器人数量时，会出现多个任务同时分配给一个农机的情况，此时就需要解决任务序列规划问题。任务序列规划问题与旅行商问题(TSP)[12]相似，主要差别为：TSP是单一旅行商从起点出发，完成系列任务后回到起始点的路径；而本文的MTSP是机器人完成所有任务后，不需要回到起点。因此，在计算路径代价时，只需要计算起点到最后目标点之间走过的路径长度。

2.2 考虑资源的拍卖算法分配过程

以市场经济为原则的基础拍卖方法中，机器人根据自身的局部信息计算报价，任务分配完全由机器人的报价决定。在拍卖算法中，拍卖代理对从投标人代理收到的出价进行评估，然后拍卖人将任务分配给出价最高的投标人[13]。

本文提出面向资源的竞价生成算法，考虑了机器人的剩余资源，并根据预期成本生成一个竞价值。在工作中资源可以再填充，场地内设置一定量的充电桩，当机器人电量低于某些阈值时，机器人将不能执行或完成其给定的任务，转向充电桩进行充电，确保足够能源执行当前任务。

图1所示为机器人i对于任务j的投标过程。

图1 机器人i对于任务j的投标生成过程

为了考虑在任务分配中机器人的资源影响，将任务列表中任务的资源向量存储在资源列表中，则机器人i的资源列表定义为：

(8)

2.2.1投标生成过程

投标时位于路径k的再填充站的站向量为:

V(k)=[v1(k)v2(k) …vNL(k)]

k∈{1,2,…,NP} (9)

(1) 机器人通过路径1完成任务j，则其资源向量为：

(10)

(2) 通过除路径1的其他路径时：

(11)

通过式(10)、式(11)可以得出，机器人在nj中执行任务j时每个路径的资源向量为：

(12)

(13)

式中：I是NL×NL的单位矩阵。

2.2.2路径选择概率

机器人i对于任务j选择路径k的任务保证概率为：

(14)

(15)

用归一化路径的任务保证概率的变化率计算路径选择概率，机器人i执行任务j的路径k的任务保证概率的变化率为：

(16)

式中：λm(k)(m(k)∈{1,2，…，NP})代表第m(k)个最小概率值。

机器人i对任务j选择路径k的选择概率为：

(17)

由式(12)-式(13)、式(17)投标代价及路径选择概率可得，机器人i对于任务j的估计资源向量为:

(18)

估计成本为：

(19)

机器人i对于任务j的出价为：

(20)

(21)

2.3 拍卖流程

基于拍卖算法的任务分配由投标生成、胜利者更新、任务交易和列表更新四个过程组成。与传统的竞价生成过程不同的是，在假设机器人有足够的资源来执行任务的前提下，任务的竞价计算是确定的，所提出的投标生成过程采用了考虑机器人资源的概率生成方法。四个过程间的数据流具体步骤如下：

步骤一胜利者更新过程接收交易任务的投标消息，并向投标生成过程请求新交易任务的投标。

步骤二投标生成过程通过列表更新过程提供任务列表、投标列表、资源列表计算新任务的投标。

步骤三胜利者更新当前交易任务的信息，确定投标的任务，为该任务发送投标、交易任务后更新交易列表。

步骤四接受新的任务后进行列表更新，并把过时的任务发送给胜利者。

3 仿真与分析

为验证算法性能，在Windows 10操作系统上，基于MATLAB 2016a环境实现算法的仿真。

实验一：模拟在识别病害作物后，喷洒机器人智能性地进行病害区域药物治理的工作，设定有3个农业机器人及30个病害作业地块，即R=3，T=30。取每个地块边界上的某一点位置坐标作为该地块的任务坐标进行实验。所有机器人单位电量消耗均为1，电池容量约束可看作路径长度的约束，3个机器人从同一位置出发，得到MRTA优化结果。机器人的起始位置、电池容量和储备载荷参数信息如表1所示。

表1 机器人性能参数

当任务点位置如图2所示时，通过本文基于资源的模型分配可得，机器人分别执行10个任务量，满足任务载荷约束，同时基于资源量最优、距离最优得到分配结果，证明本文算法的合理性。

图2 多机器人任务分配结果

由图2可得机器人任务最优分配执行结果如表2所示。

表2 任务分配优化结果

实验二：对重复连续单项拍卖(RSSIA)、文献[8]基于聚类的捆绑式算法(KCA-I)、文献[10]基于固定载荷量的拍卖算法及本文算法，分别进行数量为3、5、7、9、11的机器人进行对比，观察本文算法在相同机器人数量下的任务完成量及资源消耗情况，如图3所示。

(a) 机器人任务完成量

(b) 机器人资源消耗量图3 算法对比图

(22)

式中：dw*j为机器人w与任务j的距离。

(23)

实验结果表明，本文方法考虑了机器人多项任务中存在的资源不足以补充资源的消耗量情况，得到的仿真结果能正确估计任务完成时间和资源的消耗，与实际工作结果更接近。

4 结 语

本文考虑了基于资源的影响，建立了多机作业任务分配模型。运用拍卖算法进行任务分配，充分考虑了机器人运行所需的资源消耗量，以机器人执行能力、距离、时间为出价竞拍任务。从仿真结果可以看出，在相同条件下本文算法相对其他算法在任务完成数量及资源消耗量具有优越性，有效地降低路径代价，提高了工作效率。满足多机协同作业的实时性需求，实现了区域农田内的多机协同作业调度管理。同时考虑机器人在工作中的资源消耗量，使仿真结果更加准确。