煤矿井下群机器人高效任务分配算法

吴文臻

摘要：松散型合作群機器人系统在现阶段煤矿辅助机器人作业中具有广泛应用前景。但松散型合作群机器人系统的任务分配过程未向划分过程进行反馈，导致任务划分与分配过程高效性与合理性不足。针对该问题，提出一种基于改进型鲁宾斯坦协商策略的煤矿井下群机器人高效任务分配算法。根据群机器人系统任务划分与分配过程的多方博弈特点，将鲁宾斯坦协商策略由双方博弈向多方共同博弈方向延伸，提出多方协商博弈的“出价?讨价?还价”规则。从机器人个体执行能力与任务执行情况差异的角度出发，提出基于机器人个体单位时间任务完成量的折扣因子计算方法，以及基于各分配周期任务执行情况的任务完成状态反馈参数模型，以实现任务的动态划分与分配。通过3组机器人合作执行煤矿矿区的整体监测任务，对算法性能开展实验验证，结果表明：①算法3（采用改进型鲁宾斯坦协商策略）的任务划分与分配效率较算法1（将每组无人机数量与运行速度乘积的比例直接作为3组无人机任务划分与分配的标准）、算法2（使用多方共同协商的鲁宾斯坦协商策略，但不考虑任务完成状态反馈参数）分别提升了30.10%，18.29%。②基于算法3的3组无人机执行任务的平均最大时间差为42 s，较算法1、算法2分别优化了77.66%，65.29%，这是由于算法3通过引入任务完成状态反馈参数，及时对任务参与方的任务执行过程进行评估，将任务的分配和执行过程向任务的划分阶段进行反馈，使任务的划分与分配更加准确。

关键词：煤矿井下群机器人；松散型合作群机器人；鲁宾斯坦协商策略；任务划分与分配；折扣因子；状态反馈

中图分类号： TD67    文献标志码： A

Efficient task assignment algorithm for coal mine underground group robots

WU Wenzhen1，2

（1. CCTEG China Coal Research Institute ， Beijing 100013， China；2. State Key Laboratory ofHigh Efficient Mining and Clean Utilization of Coal Resources， Beijing 100013， China）

Abstract： The loose cooperative group robot system has broad application prospects in the current coal mine auxiliary robot operation. However， the task assignment process of the loose cooperative group robot system did not provide feedback to the division process， resulting in insufficient efficiency and rationality of the task division and assignment process. To address this issue， an efficient task assignment algorithm for coal mine underground group robots based on an improved Rubinstein negotiation strategy is proposed. Based on the multi-party game features of task division and assignment in group robot systems， the Rubinstein negotiation strategy is extended from a bipartite game to a multi-party joint game. A "bid-bargain-counteroffer" rule for multi-party negotiation games is proposed. From the perspective of the difference between the execution capability and task execution status of individual robots， a discount factor calculation method based on the task completion quantity per unittime of robot individuals is proposed. A task completion status feedback parameter model based on the task execution status of each assignment cycle is also proposed to achieve dynamic task division and assignment. By collaborating with three groups of robots to perform overall monitoring tasks in coal mining areas， experimental verification is conducted on the performance of the algorithm. The results show the following points.① Algorithm 3 uses an improved Rubinstein negotiation strategy. Algorithm 1 directly uses the ratio of the number of unmanned aerial vehicles in each group multiplied by their running speed as the standard for task division and assignment in three groups of unmanned aerial vehicles. Algorithm 2 uses the Rubinstein negotiation strategy of multi-party negotiation without considering the feedback parameters of task completion status. Algorithm 3 has a higher efficiency in task division and assignment than Algorithm 1 and Algorithm 2 by 30.10% and 18.29% respectively.② The average maximum time difference for the three groups of unmanned aerial vehicles based on Algorithm 3 to execute tasks is 42 seconds. It is 77.66% and 65.29% optimized compared to Algorithm 1 and Algorithm 2， respectively. This is because Algorithm 3 introduces task completion status feedback parameters to timely evaluate the task execution process of the task participants. Algorithm 3 provides feedback on the task assignment and execution process to the task division stages， making the task division and assignment more accurate.

Key words： coal mine underground group robots; loose cooperative group robots; Rubinstein negotiation strategy; task division and assignment; discount factor; state feedback

0 引言

机器人在煤炭行业的应用研究是煤矿智能化技术创新的关键方向。作为机器人的核心组成部分，移动机器人已逐渐渗透到“采、掘、机、运、通”等煤矿生产的各个环节[1]。尤其是在面对如矿井采空区沉降监测、井下大面积危险区域监测等可并行完成的任务时，由多个具备简单结构与功能的同构机器人单元组成的群机器人系统可在任务执行效率方面展现出巨大优势[2]。在群机器人系统中，机器人单元之间的合作方式分为紧密型和松散型2种。紧密型合作方式主要基于行为技术、虚拟向量场技术实现机器人单元的高度协调运作，需要实时预知与优化多种因素，因此主要应用于机器人编队保持或合作搬运等强实时协作场景；松散型合作方式主要基于不同类型任务分配策略，在每个任务执行周期初始阶段实现机器人单元的任务分配，由于其对机器人单元实时性配合要求低，更适用于矿山救援、环境探测、灾害监测等任务中的未知区域探索和地图构建等场景[3-5]。因此，松散型合作群机器人系统在现阶段煤矿辅助机器人作业中有广泛应用前景。

松散型合作群机器人系统中，任务被划分为多个子任务，并分配至群机器人系统中的机器人单元分别执行。任务划分是以机器人单元的预定义任务执行成本为基础。在任务分配完成后，机器人单元自身任务执行能力是任务执行效果最大的影响因素[6]。由于松散型合作方式关注的重点是任务分配问题，其任务划分过程被假定为已经在协作技术框架外完成，所以松散型合作的主要缺点是任务分配过程与任务划分过程不是一体化，任务分配过程不会向任务划分过程进行反馈，导致任务分配过程中遇到的错误不能被及时修正[7-8]，进而导致任务的整体执行周期过长，即任务执行高效性不足，同时任务执行过程中机器人个体的空闲率过高，即任务分配合理性不足。例如松散型合作方式中运用最广泛的任务分配算法——合同网算法中，每个机器人单元会根据预定义的成本和收入函数来计算每个任务的预期收益和损失，然而机器人单元的偏好和限制等因素只在任务分配阶段被考虑，并没有在任务划分阶段考虑，导致任务分配的合理性不足[9]。

鲁宾斯坦协商策略是博弈论方面的合作博弈模型，没有第三方强制结束机制与任何附加基础，最终分配结果完全由博弈参与方自身因素决定，可兼顾所有博弈参与方最大利益[10]。鲁宾斯坦协商策略主要用于解决双方合作之前对总任务量的分配问题，用完全信息动态博弈方法模拟基本的、无限期的完全信息讨价还价过程，并据此将整个博弈建立为完全信息轮流“出价?讨价?还价”模型[11]。

针对群机器人系统在任务划分与分配过程中高效性与合理性不足的问题，本文将鲁宾斯坦协商策略与群机器人系统松散型合作方式的任务划分与分配相融合，提出煤矿井下群机器人高效任务分配算法。首先，将鲁宾斯坦协商策略由双方博弈向多方共同博弈方向延伸；然后，基于机器人个体的不同执行能力及当前任务的执行情况，融入表示任务完成状态的反馈参数，构建折扣因子计算模型，最终实现任务的动态划分与分配；最后，通过3组机器人共同合作执行煤矿矿区整体监测任务，对算法的任务划分与分配策略进行验证，并对算法的高效性与合理性展开实验验证。

1 鲁宾斯坦协商策略基本理论

在鲁宾斯坦协商策略中，根据轮流“出价?讨价?还价”模型，参与协商博弈的双方轮流提出希望得到的份额。博弈从发起者开始，得到報价的一方可选择接受报价，即最终达成协议，也可选择拒绝报价，并向对方提出新的报价。博弈过程会一直持续下去，直到博弈双方最终达成协议。该博弈过程参与方的出价方式都是加密的，每个参与方都不会掌握对方准确的出价方式，且通过运用鲁宾斯坦协商策略能够保证参与博弈的双方最终达成协议[12-13]。

1.1 折扣因子

在鲁宾斯坦协商策略模型中，参与双方都有一个与其自身特征相匹配的折扣因子，折扣因子越小，通过博弈最终所得任务份额越少。折扣因子为参与方的加密信息，对方无法得到该信息。假设总任务量为1，参与双方首次提出的任务份额均接近总任务量（一般取总任务量的99%），且提出的任务份额随博弈轮数的增加逐渐减小。随着博弈的进行，提出报价的参与方新要求的任务份额 K 与上一轮要求任务份额 L 之间关系为[14-15]

K =δL        （1）

式中δ为折扣因子，0<δ＜1。

将协商发起者和响应者的折扣因子分别记为δ1和δ2，首次提出的任务份额分别记为p和q，协商过程如图1所示。发起者先出价p，响应者可以接受或拒绝1-p的份额。如果响应者接受，则博弈结束，博弈结果按发起者提出的方案执行；如果响应者拒绝，则响应者出价（还价）q，发起者可以接受或拒绝 1- q 的份额；如果发起者接受，则博弈结束，博弈结果按响应者提出的方案执行；如果发起者拒绝，发起者再出价δ1p；如此持续进行下去，直到参与博弈的某一方出价被另一方接受为止。因此这是一个无限期完全信息博弈，发起者在轮数1，3，5，…出价，响应者在轮数2，4，6，…出价。

1.2 博弈平衡

鲁宾斯坦协商策略的博弈过程长度不确定，通过运用有限阶段逆向归纳法可获取博弈平衡点[16]。假设在第i（i≥3）轮博弈时参与人1出价M，参与人2在得到份额为1- M后达成协议。当第i轮博弈时的 M 等价于第i-1轮博弈时的δ1 M，参与人2在第 i-1轮博弈时得到1-δ1 M。同理，当第i-1轮博弈时的1-δ1 M等价于第i-2轮博弈时的δ2（1-δ1 M），参与人1在第i-2轮博弈时得到1-δ2（1-δ1 M），如图2所示，因此可得博弈结束时参与人1理论上能够得到的份额，即理论博弈平衡点 M。

由于参与双方出价策略具有保密性，博弈过程中双方无法通过理论博弈平衡点判断博弈是否结束，所以只能通过参与博弈的某一方判断对方的剩余报价是否大于自身在下一轮博弈中准备提出的报价，如果大于自身准备提出的报价，则博弈结束，否则进行下一轮的博弈[17-18]。

2 基于改进型鲁宾斯坦协商策略的群机器人任务划分与分配算法

群机器人任务划分与分配问题可看作多方合作博弈的过程。根据群机器人系统的工作特点，遵循鲁宾斯坦协商策略中提出的轮流“出价?讨价?还价”思想，将鲁宾斯坦协商策略参与方的数量由限定的双方协商向多方共同协商的方向进行拓展延伸，通过对任务完成的状态进行实时反馈，使群机器人在任务划分与分配过程中体现出高效性和合理性[19]。

2.1 多方共同协商博弈过程

基于改进型鲁宾斯坦协商策略的群机器人任务采用“循环出价，末位决定”原则进行博弈。在n个参与方共同博弈的过程中，由前n-1个参与方分别提出希望得到的份额，第n个参与方选择接受或拒绝，如果选择接受，则博弈结束，博弈结果按照前n-1个参与方提出的份额进行划分与分配；如果选择拒绝，则第n个参与方与前n-2个参与方再分别提出希望得到的份额，第n-1个参与方选择接受或拒绝，如果选择接受，则博弈结束，博弈结果按前n-2个参与方与第 n个参与方提出的份额进行划分与分配；如果选择拒绝，则前n-3个与后2个参与方再分别提出希望得到的份额，第n-2个参与方选择接受或拒绝；依此类推，直到最终任务划分与分配份额被所有参与方接受为止[20]。

以3方共同协商博弈为例（图3），将协商参与方的折扣因子分别记为δ1，δ2，δ3，首次提出的任务份额分别记为 X，Y，Z。第1轮博弈由参与方 A 和参与方 B 先出价，参与方 C 可以接受或拒绝。如果参与方 C 接受，则博弈结束，博弈结果按照参与方 A 和参与方 B 提出的方案执行；如果参与方 C 拒绝，第2轮博弈开始，参与方 C 和参与方 A 共同出价（还价），参与方 B 可以接受或拒绝；如果参与方 B 接受，则博弈结束，博弈结果按参与方 C 和参与方 A 提出的方案执行；如果参与方 B 拒绝，第3轮博弈开始，参与方 B 和参与方 C再出价；如此一直进行下去，直到出价被3个参与方都接受为止。

2.2 折扣因子计算模型

折扣因子δ表示任务参与方对任务的执行能力，是根据各参与方的自身特征来确定的加密参数，对任务最终的分配比例起着决定性作用。折扣因子的影响因素有诸多方面，每个影响因素的变化对折扣因子造成的影响程度差别很大。根据任务的不同，将影响因素分为主要部分和次要部分，这里只考虑对任务划分有较大影响的主要部分。

如果影响因素大小与单位时间内完成的任务量成正比，则随着影响因素数值增大，单位时间内完成的任务量变化趋势为递增（如果影响因素大小与单位时间内完成任务量成反比，则取影响因素的倒数作为其数值）。任取多个对数型、指数型及比例型3种典型递增模式的影响因素进行分析，如图4所示。首先给出影响因素数值x与单位时间完成的任务量f 之间的关系，可知随着不同影响因素数值的增大，单位时间内完成任务量的递增趋势差别较大。完成单位任务量所需时间为t，则t和f 之间的关系为 t =1/ f ，则基于x与f 之间的变化关系，可得影响因素数值x与t 的关系，当x一定时，t越大表示任务完成效率越低。

基于x与t 的变化关系，用折扣因子δ表示1- t，即表示影响因素对任务的影响能力，可得影响因素数值x与其折扣因子δ的关系，如图5所示。可看出随着影响因素数值增大，如果单位时间内完成任务量增大的幅度越大，即折扣因子增长越快，则该影响因素对任务的影响能力就越大，意味着该影响因素越影响因素数值x与折扣因子δ间的关系为

式中r为影响因素的权重系数，0＜r≤1，r 越大，单位时间完成的任务量越多，折扣因子越大，即越重要。

以指数型、对数型及比例型3种典型增长曲线为例，对影响因素数值x与折扣因子δ之间的关系进行验证，结果如图6所示。首先取3种影响因素数值x与单位时间完成任务量f 的数据，分别满足上述3种典型类型变化趋势，如图6（a）所示。根据影响因素數值x、完成单位任务量所需时间t及折扣因子δ之间的转换关系，可得影响因素数值x与其折扣因子δ关系，如图6（b）所示。可看出随着影响因素数值增大，指数型增长模式在单位时间内完成任务量增大幅度最大，折扣因子增长最快，即该影响因素重要性最大，比例型增长次之，对数型增长最小。

分别为3种影响因素选取合适权重系数，代入式（3）进行验证，其中指数型增长的权重系数 r1=0：078，对数型增长 r2=0：009，比例型增长 r3=0：025，将所得的计算结果与图6（b）中理论结果进行对比，结果如图7所示。可看出折扣因子计算结果与理论结果之间的误差在0.02范围内，所以在权重系数选择恰当的前提下，式（3）可对影响因素与折扣因子间的关系进行较好描述。

由于影响因素之间是耦合的，针对多个影响因素对折扣因子产生的影响，影响因素数值x与折扣因子δ的关系为

式中：k为任务完成状态反馈参数；m为影响因素总数；xj为第j 个影响因素数值；rj为第j 个影响因素的权重系数。

在折扣因子中引入任务完成状态反馈参数k，对上一个分配周期任务执行情况进行评估，根据评估结果对任务划分与分配情况进行调整，使群机器人系统最大限度地发挥自身任务执行能力，进而高效完成任务。任务完成状态反馈参数k为

式中：W为任务执行度参数，表示在上一个分配周期中完成的任务量与分配总任务量比值；Waverage为平均任务执行度参数，表示上一个分配周期中所有任务参与方任务执行度参数的算术平均数。

第1个分配周期（任务划分的初始阶段）进行任务划分与分配时k =1。

2.3 多方协商平衡

改进型鲁宾斯坦协商策略的最大特点是任务划分与分配由原来的双方进行博弈改进为多方博弈。由于最终的博弈平衡需要满足所有参与方的需求份额，所以其博弈过程更为复杂，持续时间更长。

改进型鲁宾斯坦协商策略基于有限阶段逆向归纳法寻找多方博弈的理论协商博弈平衡点：n个参与方进行博弈，每个参与方的折扣因子分别为δ1?δn，博弈过程如图8所示。在第i（i≥n）轮博弈时编号为1?n-1的参与方分别出价M1?Mn-1，编号为n的参与方得到剩余份额s0后达成协议。因为第i轮博弈时的 M1等价于第i-1轮博弈时的δ1 M1，参与方n在第i-1轮博弈时最多得到sn；因为第i-1轮博弈时的M2等价于第i-2轮博弈时的δ2 M2，参与方1在第i-2轮博弈时至少得到 s1；因为第 i-2轮博弈时的 M3等价于第 i-3轮博弈时的δ3 M3，参与方2在第i-3轮博弈时至少得到 s2；依次类推，在第i-n+1轮博弈时的sn等价于第i-n轮博弈时的δnsn，参与方n-1在第i-n轮博弈至少得到sn-1。

根据第i轮博弈时各参与方所得份额等价于第i一 n轮博弈时所得的份额，可得

该方程组的未知数分别为参与人1?n 的所得份额M1?Mn，求解该方程组即可得出参与人1?n 通过改进型鲁宾斯坦协商策略进行博弈后所得的理论协商博弈平衡点。

3 实验验证

以工业级四旋翼无人机组共同完成某煤矿矿区整体监测任务作为实验背景，对基于改进型鲁宾斯坦协商策略的群机器人任务划分与分配算法的高效性与合理性进行验证。工业级四旋翼无人机外形与视角如图9所示，技术参数见表1。在任务执行过程中，当完成任务划分与分配后，运用Web+GIS技术自动生成和优化作业航线。运用电子围栏与飞行控制系统相配合的方式规划作业区域和禁飞区域，其中任务区域的总面积为3.498 m2。无人机群依据规划航线自主飞行，实现任务区域遍历[21-22]。

实验准备阶段，将13架无人机分为3组，每一组作为一个参与方参与任务划分与分配过程的博弈。对每组无人机的最大运动速度进行限制，使无人机的飞行能力实现差异化。3组无人机的个数与飞行速度见表2。

3.1 第1个分配周期的任务比例分配

进行任务区域划分前需确定3组无人机的初始折扣因子。主要影响因素有每组无人机数量和运行速度，取无人机数量权重系数r1=0：95，机器人运行速度权重系数 r2=0：85，任务完成状态反馈参数 k =1。根据式（4）可得3组无人机的初始折扣因子分别为δ1=0：9823，δ2=0：9765，δ3=0：9655。设每一次任务划分与分配周期为120 s，总任务份额为1，在明确任务区域的总面积和3组无人机的折扣因子后，根据式（6）可得3组无人机的理论协商博弈平衡点，分别为0.3635，0.3256，0.3109。

根據3组无人机的参数，运用改进型鲁宾斯坦协商策略对任务份额进行划分，博弈过程如图10所示。博弈共进行了47轮，在第1轮博弈中，第1组和第2组无人机的初始出价（期望份额）为0.49，则第3组无人机得到的初始份额为0.02，小于其在第2轮博弈中准备提出的报价0.49，则3组无人机进入第2轮的博弈。依此类推，第2组无人机得到的报价为0.3360，大于其在下一轮博弈中准备提出的报价0.3351，则博弈过程结束，3组无人机得到博弈的平衡。在第1个分配周期的初始阶段，3组无人机分配的任务份额分别为0.3748，0.3360，0.2892，与理论协商博弈平衡点相比，误差份额保持在0.05范围内。误差产生的原因是，通过式（6）只需要经过1步计算即可得出理论博弈平衡点，但实际平衡点需要通过多步协商博弈获取，每一步计算产生的误差均会得到累计。

由于任务执行过程中受风速、任务区域轮廓等因素影响，第1个分配周期中每组无人机对分配所得任务的完成情况有较大差别。第1个分配周期结束后任务区域的剩余面积，即第2个分配周期任务区域总面积为3.303 km2。

根据式（5）计算第1个分配周期的任务完成状态反馈参数，对3组无人机的任务执行情况进行评估，根据评估情况对折扣因子进行适应性调整。第1个分配周期中3组无人机对任务的完成情况与状态反馈参数见表3。将k代入式（4），可得3组无人机的折扣因子：δ1=0：9859，δ2=0：9762，δ3=0：9538。

3.2 剩余分配周期的任务比例分配

在第2个分配周期的初始阶段，根据第2个分配周期的任务区域面积和3组无人机的折扣因子，运用改进型鲁宾斯坦协商策略对任务区域进行新一轮的划分与分配，在进行了44轮博弈后得到协商博弈平衡，3组无人机获得的任务份额分别为0.4022，0.3449，0.2529。

3组无人机共同执行矿区整体监测任务共经历15个分配周期。每组无人机在不同分配周期的任务完成情况如图11所示。受外界（如地形、气候等不可抗拒因素）影响，同一组无人机在不同分配周期完成的任务量相差较大，除第15个分配周期外，第1组无人机在单个分配周期完成任务量 task_1变化范围为0.0714～0.1258 km2，第2组无人机在单个分配周期完成任务量 task_2的变化范围为0.0524～0.1008 km2，第3组无人机在单个分配周期完成任务量 task_3的变化范围为0.0412～0.0829 km2。

在每个分配周期初始阶段，通过分析上个分配周期中每组无人机任务执行情况，即每组无人机的执行水平与任务总体执行水平之间的关系，确定任务完成状态反馈参数k。通过式（4）对折扣因子δ进行调整，进而通过改进型鲁宾斯坦协商策略对每个任务分配周期的任务划分比例p进行调整。任务执行过程中，在任务比例划分阶段，3组无人机在不同分配周期的反馈参数k、折扣因子δ、划分比例 h 的变化情况如图12所示。可看出划分比例 h 的变化趋势与任务完成状态反馈参数k的变化趋势基本相符，即在前一个分配周期中任务执行水平较高的无人机组，在下一周期中所分配的任务量会随之增大，相反地，任务执行水平较低的无人机组在下一周期中分配的任务量随之降低，实现了执行能力的最大化。

不同分配周期的博弈轮数如图13所示，可看出运用改进型鲁宾斯坦协商策略，每个分配周期的博弈轮数保持在40～50之间，稳定地解决了区域遍历任务过程中的任务划分分配问题。

3.3 不同任务划分与分配算法高效性与合理性对比实验

为了比较算法在任务划分与分配方面的高效性，分别运用3种不同的任务划分与分配算法进行煤矿矿区整体监测任务实验，实验中设置相同的无人机数量、运行速度及任务区域面积。每种任务划分与分配算法分别进行3次实验，取3次实验经历的平均时间作为参考。

算法1通过计算每组无人机数量与运行速度的乘积，将乘积的比例直接作为3组无人机任务划分与分配的标准，即每组无人机分配的任务份额分别为0.4412，0.3330，0.2258；算法2使用多方共同协商的鲁宾斯坦协商策略，但不考虑任务完成状态反馈参数k，任务的分配和执行过程不会向任务划分过程进行反馈，3组无人机分配的任务份额始终为0.3748，0.3360，0.2892；算法3采用改进型鲁宾斯坦协商策略，实现任务的动态划分与分配。由于无人机续航能力弱的缺点不可避免，无人机电池更换时间不在实验计时范围内。

通过对总体任务执行过程进行计时，实现对3种不同任务划分与分配算法高效性的对比。基于3种算法的任务执行过程所经历的时间见表4。可看出算法3的任务划分与分配效率较算法1、算法2分别提升了30.10%，18.29%。

通过对每组无人机的任务执行过程进行计时，实现对3种不同的任务划分与分配算法合理性的对比。每组无人机的平均任务执行时间见表5。可看出基于算法1的3组无人机执行任务的平均最大时间差为188 s，即无人机组在执行完任务之后平均有188 s 的等待时间，这段时间内部分无人机组处于空闲状态，而部分无人机一直处于任务执行状态；同理，基于算法2的3组无人机执行任务的平均最大时间差为121 s，这是由于算法2运用了多方共同协商的鲁宾斯坦协商策略，该策略通过折扣因子优化了影响因素（无人机数量和运行速度）与任务划分与分配结果之间的关系，避免了影响因素随着其数值增大导致的冗余问题；基于算法3的3组无人机执行任务的平均最大时间差为42 s，较算法1、算法2分别优化了77.66%，65.29%，这是由于算法3通过引入任务完成状态反馈参数k，及时对任务参与方的任务执行过程进行评估，将任务的分配和执行过程向任务的划分阶段进行反馈，使任务的划分与分配更加准确。

由实验结果可知，运用改进型鲁宾斯坦协商策略对任务进行划分与分配，能够最大化地发挥群机器人的任务执行能力，体现了改进型鲁宾斯坦协商策略在任务划分与分配方面的高效性和合理性优势。

4 结论

1）将鲁宾斯坦协商策略中的双方博弈向多方共同博弈的方向拓展延伸；以对任务最终分配起决定性作用的影响因素为研究对象，提出了折扣因子计算方法，根据该方法能够量化参与方对任务的执行能力；在折扣因子中引入任务完成状态反馈参数，通过评估对所分配任务的执行程度，对任务划分与分配情况进行调整。

2）基于3组无人机合作开展煤矿矿区监测任务实验，对算法的高效性与合理性进行了验证。验证结果表明：算法3的任务划分与分配效率较算法1、算法2分别提升了30.10%，18.29%；基于算法3的 3组无人机执行任务的平均最大时间差为42 s，较算法1、算法2分别优化了77.66%与65.29%。

参考文献（References）：

[1] 张鹏.智能矿山机器人协同管控[J].工矿自动化，2021，47（增刊2）：43-44.

ZHANG Peng. Collaborative control of robots in intelligent mine[J]. Industry and Mine Automation，2021，47（S2）：43-44.

[2] 王宏，宋智瀛，贾瑞清.基于模块化异构多机器人的煤矿灾害处置系统[J].煤炭科学技术，2011，39（10）：93-95，111.

WANG Hong， SONG Zhiying，JIA Ruiqing. Mine disaster control system based on module heteromerous multi robot[J]. Coal Science and Technology，2011，39（10）：93-95，111.

[3] GAUTHAM D，THOMAS M，SONYA C，et al. A distributed task allocation algorithm for a multi-robot system in healthcare facilities[J]. Journal of Intelligent & Robotic Systems，2015，80（1）：33-58.

[4] 彭凡彬，杨俊杰，叶波.改进蚁群算法的变电站群机器人路径规划研究[J].仪表技术，2018（3）：9-13，35.

PENG Fanbin，YANG Junjie，YE Bo. Research on robot path planning of substation group based on improved ant colony algorithm[J]. Instrumentation Technology，2018（3）：9-13，35.

[5] 王偉嘉，郑雅婷，林国政，等.集群机器人研究综述[J].机器人，2020，42（2）：232-256.

WANG Weijia，ZHENG Yating，LIN Guozheng，et al. Swarm robotics：a review[J]. Robot，2020，42（2）：232-256.

[6] XIAO Renbin，WU Husheng，HU Liang，et al. A swarm intelligence labour division approach to solving complex area  coverage  problems  of swarm  robots[J]. International Journal of Bio-Inspired Computation，2020，15（4）：224-238.

[7] 邱靖廷.基于群体智能的多机器人任务分配[D].哈尔滨：哈尔滨工程大学，2020.

QIU Jingting. Multi-robot task assignment based on group intelligence[D]. Harbin： Harbin Engineering University，2020.

[8] YEUNG W L. Efficiency of task allocation based on contract net protocol with audience restriction in a manufacturing control application[J]. International Journal of Computer Integrated Manufacturing，2018，31（10）：1005-1017.

[9] 梁志伟，吴海健. RoboCup标准平台组中基于改进合同网协议的任务分配算法[J].计算机工程与科学，2022，44（1）：176-183.

LIANG Zhiwei， WU Haijian. A task allocation algorithm based on the improved contract network protocol in RoboCup standard platform league[J]. Computer Engineering & Science，2022，44（1）：176-183.

[10] 黄柳强，秦丽娟，商云龙.电力市场双边协商交易模型设计研究[J].广西电力，2021，44（2）：14-19.

HUANG Liuqiang， QIN Lijuan， SHANG Yunlong. Research on a design of bilateral negotiation and transaction model in electricity market[J]. Guangxi Electric Power，2021，44（2）：14-19.

[11] 马金龙. 基于博弈论的国际工程承包合同纠纷研究[D].北京：北京交通大学，2020.

MA Jinlong. Research on the disputes of international engineering contracts based on game theory[D]. Beijing：Beijing Jiaotong University，2020.

[12] 罗震环.基于VCG和鲁宾斯坦模型的数据定价方法研究[D].哈尔滨：哈尔滨工业大学，2021.

LUO Zhenhuan. Research on data pricing methods based on VCG and rubinstein models[D]. Harbin：Harbin Institute of Technology，2021.

[13] JAEHWI S， HOUNG S. Bargaining model-based coverage area subdivision of multiple UAVs in remote sensing[J]. Journal of Biosystems Engineering，2021，45（3）：133-144.

[14] 張梦颖，王蒙一，王晓东，等.基于改进合同网的无人机群协同实时任务分配问题研究[J].航空兵器，2019，26（4）：38-46.

ZHANG  Mengying， WANG  Mengyi，WANGXiaodong，et al. Cooperative real-time task assignment of UAV group based on improved contract net [J]. Aero Weaponry，2019，26（4）：38-46.

[15] 马洪宽.博弈论[M].上海：同济大学出版社，2015：78-91.

MA Hongkuan. Game theory[M]. Shanghai：Tongji University Press，2015：78-91.

[16] 王磊.动态合作博弈中解的策略稳定性[D].青岛：青岛大学，2016.

WANG Lei. Strategic stability of solutions in dynamic cooperative games[D]. Qingdao：Qingdao University，2016.

[17] 郭超，熊伟，刘呈祥.合同网协议改进研究现状与展望[J].装备学院学报，2016，27（6）：82-89.

GUO Chao，XIONG Wei，LIU Chengxiang. Prospects and current researches on improvement of contract net protocol[J]. Journal of Equipment Academy，2016，27（6）：82-89.

[18] SZCZERBA R J，GALKOWSKI P，GLICKSTEIN I S， et al. Robust algorithm for real-time route planning[J].IEEE Transactions on Aerospace and Electronic Systems，2000，36（3）：869-878.

[19] 刘刚，王瑛，张发，等.合同网协议协商机制收敛性与收敛速率分析[J].控制与决策，2014，29（6）：1027-1034.

LIU Gang， WANG Ying， ZHANG Fa， et al. Convergence and convergent rate analysis of contract net protocol negotiation mechanism[J]. Control and Decision，2014，29（6）：1027-1034.

[20] 李娟，张昆玉.基于改进合同网算法的异构多AUV协同任务分配[J].水下无人系统学报，2017，25（6）：418-423.

LI Juan，ZHANG Kunyu. Heterogeneous multi-AUV cooperative task allocation based on improved contract net algorithm[J]. Journal of Unmanned Undersea Systems，2017，25（6）：418-423.

[21] 吳江，赵世钰，周锐，等.基于面向服务的多无人机辅助决策仿真集成方法[J].系统仿真学报，2012，24（12）：2525-2529.

WU Jiang，ZHAO Shiyu，ZHOU Rui，et al. Simulation integration of decision aiding based on service-oriented for multiple UAVs[J]. Journal of System Simulation，2012，24（12）：2525-2529.

[22] CHEN Kaiwen，REICHARD G，AKANMU A，et al. Geo-registering UAV-captured close-range images to GIS-based  spatial  model  for  building  facade inspections[J]. Automation in Construction，2021，122（1）. DOI：10.1016/j.autcon.2020.103503.