改進合同網在多機器人圍捕任務分配中的應用

付光遠,李 源,付文宇,王湘瑤

(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 結論

提出了基于改進合同網協議算法的圍捕任務分配策略；通過計算與案例庫中歷史案例的匹配度，實現了任務的快速匹配和對承包商的快速選擇；結合信譽度，在承包商發生故障時，能夠較快選擇其他承包商如期完成任務。最后對不同類型和數量的入侵者進行仿真，本文所提改進合同網協議能夠縮短承包商的選擇時間，也能夠處理承包商的故障，有效提升任務的成功率，說明具有較好的應用性。