改进合同网在多机器人围捕任务分配中的应用

付光远,李 源,付文宇,王湘瑶

(1.火箭军工程大学 作战保障学院, 西安 710025； 2.中国华电集团公司四川宝珠寺水力发电厂, 四川 广元 628000)

多机器人的围捕任务指的是一群围捕机器人通过协调配合，对入侵者进行追踪和捕获。面对不同数量和类型的入侵者，重点是选出最为合适的围捕机器人执行任务[1-2]。合同网协议(Contract Net Protocol,CNP)是一种比较经典的任务协商和资源分配策略[3]，广泛应用于多机器人系统[4-5]和无人机[6-8]等领域，通过合同机制中招、投标的方式对任务进行分配。然而它依然存在着通信开销大和资源占用率高以及不能适应动态变化的环境等不足。国内外的专家学者针对诸多不足，进行了不同程度的改进。为了减少通信开销，案例推理技术[9]较为常用，利用与历史案例的相似性进行分配，减少了招标的步骤。针对承包商动态变化的问题，文献[10-11]结合任务负载率指标和令牌环网概念，建立了承包商的能力模型，动态改变自身的能力，然而计算复杂，系统的稳定性较弱。除此之外，通过引入均衡度指标[12-13]，衡量任务成本是否合理，也是优化任务分配的方式，但普适性未知。

本文基于文献中的优势和不足，结合案例匹配方法，提出了一种改进合同网策略，并将其应用于多机器人的围捕任务分配中，有效地解决了围捕机器人的分配问题，缩短了围捕时间，提升了围捕成功率。

1 多机器人围捕任务的描述

多机器人的围捕任务，通常是指围捕机器人通过对入侵者的搜索、追踪和包围，完成捕捉的过程。本文假设围捕机器人和入侵者的条件：

1) 围捕机器人和入侵者的外形和大小等客观信息忽略不计，均视为质点；

2) 围捕机器人的速率始终不变，记为Vr；当未被围捕机器人发现时，入侵者的速率与Vr相等，记为Ve1，即Ve1=Vr；当被发现之后，入侵者的速率为Vr的两倍，记为Ve2，即Ve2=2Vr；

3) 当围捕机器人与入侵者的欧式距离dij小于或等于一定值L时，即认为入侵者被围捕机器人发现；当所有围捕机器人与入侵者的欧式距离为1，即相邻状态时，围捕成功，任务结束。

1.1 围捕机器人策略

围捕机器人首先需要对环境进行搜索，以发现围捕目标；当发现之后，需要在其周围定义一些围捕点；之后，围捕机器人便朝着围捕点追踪；当围捕机器人占据围捕点中大部分位置之后，入侵者相当于已被包围；当所有围捕机器人到达围捕点之后，进一步缩小与入侵者的距离，完成围捕任务。策略如下：

1) 分散搜索策略，当dij≤L时，意为发现入侵者，定义围捕机器人Ri的运动表达式如下[14]：

(1)

式(1)中，[rx,ry]T为Ri下一步的运动方向，[rxo,ryo]T为Ri的初始运动方向，α为Ri随机偏转的角度。

设Ri当前的位置是(xr,yr)，在经过时间to后，Ri的位置(xr+1,yr+1)为

Vrox=Vr·rx

(2)

Vroy=Vr·ry

(3)

xr+1=xr+to·Vrox

(4)

yr+1=yr+to·Vrox

(5)

其中，Vrox、Vroy分别为围捕机器人在x、y两个方向下一步的速度。

2) 追踪策略。当发现入侵者之后，在其周围确定围捕点的位置，并根据围捕机器人与围捕点的距离最近原则，将围捕点分配给围捕机器人；若不止一个围捕机器人与该围捕点匹配，则根据围捕机器人与其他围捕点的距离，将此围捕点分配给次近距离(除去最近距离，与其他围捕点距离的最小值)最大值所对应的围捕机器人，以便所有围捕机器人到所有围捕点的总时间最短；随后，围捕机器人朝着各自的围捕点追踪。

3) 围捕策略。当所有围捕机器人均到达围捕点之后，相当于已将入侵者包围，此时缩小与入侵者的距离，当距离为1，为相邻状态时，围捕机器人已将入侵者成功围捕，任务结束。

1.2 入侵者运动

起初，入侵者在环境中随机运动；当被机器人发现后，入侵者需要逃避机器人的围捕，因此需要进行逃逸运动，通过计算相邻机器人与自身所成的角度，选择最大的夹角所对应的围捕机器人的中间位置作为逃逸方向，防止被捕捉[15]。定义入侵者E随机运动的方向如下：

(6)

式(6)中，[ex,ey]T为E下一步的运动方向，[exo,eyo]T为E的初始运动方向，β为E随机偏转的角度。

如图1所示，设E当前的位置是(xe,ye)，定义逃逸运动的方向如下：

(7)

式(7)中，(xr1,2,yr1,2)为E选择所成最大夹角的两个围捕机器人R1,R2的中点R1,2的坐标。

图1 入侵者逃逸运动示意图

2 改进的合同网模型

本文结合案例匹配方法，在传统的合同网协议中，引入匹配度(Suit)和信誉度(Cred)对其进行改进。通过构建案例库，根据新任务与历史任务的匹配度选择候选承包商，减少了传统算法中对所有承包商招标的通信开销和对标书的评估时间；再根据信誉度的高低选择最佳的承包商，避免了传统方法中承包商之间的冲突问题；当某承包商发生故障，在降低其信誉度的同时，选择次高信誉度的承包商完成任务，较于传统算法适应了动态环境。

2.1 构建案例库

为了获得案例库中的有效数据，使不同的围捕机器人组成的围捕小组在同一环境下执行任务。

案例Case用一个四元组描述：

Case=〈C,G,R,T〉

(8)

式(8)中，C表示任务类型(Character)；G表示任务所对应的承包商，即围捕小组(Group)；R表示完成任务的信誉度(Credit)；T表示完成任务的时间(Time)。

任务的标书Bid用一个三元组描述：

Bid=〈C,A,N〉

(9)

式(9)中，C表示任务类型(Character)；A表示至少需要有一个承包商满足任务的最低能力要求(Ability)；N表示完成任务所需的最少承包商个数(Number)。

本文假定有10个围捕机器人，根据能力的不同，分为3组：{R11,…,R13},{R21,…,R23},{R31,…,R34}，能力由速度和传感范围表示，分别设置为{(1.1,2),(1.2,2),(1.2,3)},{(1.3,2),(1.2,4),(1.4,3)},{(1.3,5),(1.4,5),(1.3,4),(1.5,5)}；由于是围捕任务，用入侵者的速度和传感范围表示任务特征，速度和传感范围的区域为[1.1,1.5]和[2,5]；不同类型的入侵者对应的标书设为：B1=〈1,2,(1.1,3)〉，B2=〈2,2,(1.2,3)〉，B3=〈3,3,(1.2,2)〉，B4=〈4,3,(1.2,4)〉，B5=〈5,4,(1.3,3)〉，B6=〈6,3,(1.3,5)〉，B7=〈7,4,(1.4,5)〉。

围捕状态如图2所示，其中，入侵者位于中心位置，用E表示；围捕机器人用R表示。

图2 围捕状态

根据以上描述，在能够完成围捕任务的前提下，即在围捕机器人组成的小组中，至少有一个围捕机器人的能力大于等于入侵者的能力；将围捕机器人依照不同的任务类型，由难到易合理分配，尽量使得各围捕机器人物尽其用，而非大材小用；之后各围捕小组的机器人进行随机组合，采用前述的围捕策略，根据自身能力通过搜索、追踪、包围和捕捉进行10次围捕实验，记录下信誉度和围捕时间的平均值，最终得到如表1所示的案例库。

表1 案例库

2.2 计算匹配度

匹配度指的是管理者接收的新任务Tj与案例库中已存的历史任务Ti的相似程度。根据余弦相似度的含义，定义匹配度Suit(Tj,Tj)如下：

(10)

式(10)中，Tj,m与Ti,m分别为任务Tj与Ti中第m(m=1,2,…,n)项特征的值，k为常数。当Suit(Tj,Ti)≥σ(σ为常数)时认为二者相似性高，匹配成功，将满足条件的Suit进行从小到大排序，选择最高Suit所对应的历史任务Ti，确定完成任务Tj的承包商ai。当发现匹配的历史任务Ti的承包商不唯一时，管理者需要根据信誉度的高低选出最合适的承包商。

2.3 计算信誉度

信誉度指的是在改进合同网协议中承包商ai完成任务Ti的成功率Pi。在执行任务的过程中，如果承包商ai能够完成管理者分配的任务Tj时，则更新案例库中ai的信誉度，使其增加ξ1，即Credii+ξ1；反之，如果不能顺利完成任务，则使其信誉度降低ξ2，即Credii-ξ2。

在分配任务时，管理者根据信誉度选择承包商，避免了面向所有承包商招标的情况，减少了通信开销。定义信誉度(Cred)如下：

Cred=max(Credmin,P)

(11)

(12)

其中，Credmin表示信誉度的最小阈值，P表示承包商完成任务的成功率，Cs为承包商成功完成任务的次数，Ct为承包商参加任务的总次数。

2.4 任务分配算法

根据上文的描述，基于案例匹配的改进合同网协议任务分配算法流程如图3。

图3 改进合同网协议的流程

3 仿真与分析

在基于栅格法建模的二维环境下进行仿真实验，在本文中，经过多次实验，取常数L=5，σ=90%效果较好；一般而言，需ξ2≫ξ1，因为一旦选定的承包商因为某种原因不能成功完成任务，管理者在下一次招标的时候应避免选中此承包商，因此需要大大降低其信誉度。因此在更新信誉度的过程中，令ξ1=0.01，ξ2=0.1。在下列仿真围捕示意图中，所标识的如“R12”等位置即为相关围捕机器人所在的初始位置。

1) 当入侵者数量为1的情形

当管理者接收到特征为(1.13,2.82)的围捕任务时(入侵者用E表示)，通过计算与入侵者标书中不同任务类型的特征距离，再根据匹配度的计算公式，得到与类型1的匹配度最高，约为99.9%，因此二者匹配；根据案例库可知，特征匹配的围捕机器人有2组，管理者向信任度最高且时间最短的组{R12,R13}招标，该组进行投标，与管理者确认消息后，管理者宣布其中标，并与其签订合同，于是此组被选派执行任务；如图4所示，R12经过搜索发现E之后，与R13合作对其进行追逐和包围，而E1采取一定的逃逸策略逃跑，R12和R13经过协作成功捕获E，管理者更新其信誉度为101%。

图4 入侵者数量为1的仿真围捕

2) 当入侵者数量为2的情形

当两个新任务的特征分别为(1.15,3.1)和(1.2,2.8)时(入侵者用E1和E2表示)，通过计算可知匹配度最高的围捕任务分别是类型1和2，匹配度分别约为100% 和99.9%；管理者选择信誉度最高且时间最短的组{R12,R13}和{R21,R22}进行招标，经投标和签订合同之后，围捕任务开始。如图5所示，两组围捕机器人通过搜索、追踪、包围之后，将E1和E2捕捉成功，管理者更新{R12,R13}和{R21,R22}的信誉度为101%和100.75%。

图5 入侵者数量为2的仿真围捕

3) 承包商故障的情形

当管理者接收到特征为(1.36,5)的新任务时，通过计算可知匹配的围捕任务为类型6，匹配度约为97%，管理者选择信誉度最高且时间最短的组{R31,R32,R34}进行招标，但是由于R31故障，该组不进行投标，于是管理者更新{R31,R32,R34}信誉度为90%，转而选择信誉度次高且时间最短的组{R32,R33,R34}进行招标，在该组完成一系列投标、中标和签订合同之后，R32,R33,R34开始执行任务，如图6所示，在三者的合力围捕下，围捕成功，管理者更新{R32,R33,R34}的信誉度为100.58%。

4) 与经典合同网协议的比较

以承包商{R32,R33,R34}围捕特征为(1.36,5)的入侵者为例，进行100次仿真实验，研究传统合同网与改进合同网协议下完成围捕任务的时间和成功率的不同。根据记录结果，经典合同网平均耗时25.02 s，平均成功率为96.32%；而改进合同网耗时8.06 s，平均成功率为98.62%。

图6 入侵者数量为3的仿真围捕

如图7所示，基于改进合同网的围捕任务完成分配的时间整体上低于经典合同网，主要原因是在传统的合同网协议中，需要向所有承包商进行招标，时间复杂度为O(n)；而在改进的合同网协议中，管理者只需结合匹配度和信誉度，向唯一的承包商进行投标即可，此时算法的时间复杂度为O(1)，缩短了约68%的通信时间。

图7 两种协议时间的比较

由图8可知，改进合同网协议的成功率高于经典合同网，提高了约2.3%。因为传统的协议不能适应承包商突然故障的情况，需要重新招标；而改进的合同网能够依据信誉度的次高值，较快选择新的承包商，完成围捕任务。

图8 两种协议成功率的比较

5) 与其他改进合同网协议的比较

同样以承包商{R32,R33,R34}围捕特征为(1.36,5)的入侵者为例，进行100次仿真实验。为更好地观察实验结果，将每20次分为一组，研究文献[5]改进合同网与本文所提改进合同网在完成围捕任务的时间和成功率的差异。根据记录结果，文献[5]算法平均耗时18.22 s，平均成功率为93.59%；而本文算法平均耗时7.88 s，平均成功率为96.63%。

图9和图10分别展示了文献[5]算法和本文算法在围捕时间和成功率方面的不同，其原因主要是在文献[5]改进合同网协议中，只考虑了单承包商完成任务的问题，未考虑多承包商协作问题；在面对复杂任务时，单承包商无法完成任务，管理者需要向余下的承包商进行招标、评估，既增加了通信开销，又影响了围捕的成功率。

图9 两种算法的时间

图10 两种算法的成功率

4 结论

提出了基于改进合同网协议算法的围捕任务分配策略；通过计算与案例库中历史案例的匹配度，实现了任务的快速匹配和对承包商的快速选择；结合信誉度，在承包商发生故障时，能够较快选择其他承包商如期完成任务。最后对不同类型和数量的入侵者进行仿真，本文所提改进合同网协议能够缩短承包商的选择时间，也能够处理承包商的故障，有效提升任务的成功率，说明具有较好的应用性。