改進(jìn)合同網(wǎng)在多機(jī)器人圍捕任務(wù)分配中的應(yīng)用

付光遠(yuǎn),李 源,付文宇,王湘瑤

(1.火箭軍工程大學(xué) 作戰(zhàn)保障學(xué)院, 西安 710025； 2.中國(guó)華電集團(tuán)公司四川寶珠寺水力發(fā)電廠, 四川 廣元 628000)

多機(jī)器人的圍捕任務(wù)指的是一群圍捕機(jī)器人通過(guò)協(xié)調(diào)配合，對(duì)入侵者進(jìn)行追蹤和捕獲。面對(duì)不同數(shù)量和類型的入侵者，重點(diǎn)是選出最為合適的圍捕機(jī)器人執(zhí)行任務(wù)[1-2]。合同網(wǎng)協(xié)議(Contract Net Protocol,CNP)是一種比較經(jīng)典的任務(wù)協(xié)商和資源分配策略[3]，廣泛應(yīng)用于多機(jī)器人系統(tǒng)[4-5]和無(wú)人機(jī)[6-8]等領(lǐng)域，通過(guò)合同機(jī)制中招、投標(biāo)的方式對(duì)任務(wù)進(jìn)行分配。然而它依然存在著通信開(kāi)銷大和資源占用率高以及不能適應(yīng)動(dòng)態(tài)變化的環(huán)境等不足。國(guó)內(nèi)外的專家學(xué)者針對(duì)諸多不足，進(jìn)行了不同程度的改進(jìn)。為了減少通信開(kāi)銷，案例推理技術(shù)[9]較為常用，利用與歷史案例的相似性進(jìn)行分配，減少了招標(biāo)的步驟。針對(duì)承包商動(dòng)態(tài)變化的問(wèn)題，文獻(xiàn)[10-11]結(jié)合任務(wù)負(fù)載率指標(biāo)和令牌環(huán)網(wǎng)概念，建立了承包商的能力模型，動(dòng)態(tài)改變自身的能力，然而計(jì)算復(fù)雜，系統(tǒng)的穩(wěn)定性較弱。除此之外，通過(guò)引入均衡度指標(biāo)[12-13]，衡量任務(wù)成本是否合理，也是優(yōu)化任務(wù)分配的方式，但普適性未知。

本文基于文獻(xiàn)中的優(yōu)勢(shì)和不足，結(jié)合案例匹配方法，提出了一種改進(jìn)合同網(wǎng)策略，并將其應(yīng)用于多機(jī)器人的圍捕任務(wù)分配中，有效地解決了圍捕機(jī)器人的分配問(wèn)題，縮短了圍捕時(shí)間，提升了圍捕成功率。

1 多機(jī)器人圍捕任務(wù)的描述

多機(jī)器人的圍捕任務(wù)，通常是指圍捕機(jī)器人通過(guò)對(duì)入侵者的搜索、追蹤和包圍，完成捕捉的過(guò)程。本文假設(shè)圍捕機(jī)器人和入侵者的條件：

1) 圍捕機(jī)器人和入侵者的外形和大小等客觀信息忽略不計(jì)，均視為質(zhì)點(diǎn)；

2) 圍捕機(jī)器人的速率始終不變，記為Vr；當(dāng)未被圍捕機(jī)器人發(fā)現(xiàn)時(shí)，入侵者的速率與Vr相等，記為Ve1，即Ve1=Vr；當(dāng)被發(fā)現(xiàn)之后，入侵者的速率為Vr的兩倍，記為Ve2，即Ve2=2Vr；

3) 當(dāng)圍捕機(jī)器人與入侵者的歐式距離dij小于或等于一定值L時(shí)，即認(rèn)為入侵者被圍捕機(jī)器人發(fā)現(xiàn)；當(dāng)所有圍捕機(jī)器人與入侵者的歐式距離為1，即相鄰狀態(tài)時(shí)，圍捕成功，任務(wù)結(jié)束。

1.1 圍捕機(jī)器人策略

圍捕機(jī)器人首先需要對(duì)環(huán)境進(jìn)行搜索，以發(fā)現(xiàn)圍捕目標(biāo)；當(dāng)發(fā)現(xiàn)之后，需要在其周圍定義一些圍捕點(diǎn)；之后，圍捕機(jī)器人便朝著圍捕點(diǎn)追蹤；當(dāng)圍捕機(jī)器人占據(jù)圍捕點(diǎn)中大部分位置之后，入侵者相當(dāng)于已被包圍；當(dāng)所有圍捕機(jī)器人到達(dá)圍捕點(diǎn)之后，進(jìn)一步縮小與入侵者的距離，完成圍捕任務(wù)。策略如下：

1) 分散搜索策略，當(dāng)dij≤L時(shí)，意為發(fā)現(xiàn)入侵者，定義圍捕機(jī)器人Ri的運(yùn)動(dòng)表達(dá)式如下[14]：

(1)

式(1)中，[rx,ry]T為Ri下一步的運(yùn)動(dòng)方向，[rxo,ryo]T為Ri的初始運(yùn)動(dòng)方向，α為Ri隨機(jī)偏轉(zhuǎn)的角度。

設(shè)Ri當(dāng)前的位置是(xr,yr)，在經(jīng)過(guò)時(shí)間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分別為圍捕機(jī)器人在x、y兩個(gè)方向下一步的速度。

2) 追蹤策略。當(dāng)發(fā)現(xiàn)入侵者之后，在其周圍確定圍捕點(diǎn)的位置，并根據(jù)圍捕機(jī)器人與圍捕點(diǎn)的距離最近原則，將圍捕點(diǎn)分配給圍捕機(jī)器人；若不止一個(gè)圍捕機(jī)器人與該圍捕點(diǎn)匹配，則根據(jù)圍捕機(jī)器人與其他圍捕點(diǎn)的距離，將此圍捕點(diǎn)分配給次近距離(除去最近距離，與其他圍捕點(diǎn)距離的最小值)最大值所對(duì)應(yīng)的圍捕機(jī)器人，以便所有圍捕機(jī)器人到所有圍捕點(diǎn)的總時(shí)間最短；隨后，圍捕機(jī)器人朝著各自的圍捕點(diǎn)追蹤。

3) 圍捕策略。當(dāng)所有圍捕機(jī)器人均到達(dá)圍捕點(diǎn)之后，相當(dāng)于已將入侵者包圍，此時(shí)縮小與入侵者的距離，當(dāng)距離為1，為相鄰狀態(tài)時(shí)，圍捕機(jī)器人已將入侵者成功圍捕，任務(wù)結(jié)束。

1.2 入侵者運(yùn)動(dòng)

起初，入侵者在環(huán)境中隨機(jī)運(yùn)動(dòng)；當(dāng)被機(jī)器人發(fā)現(xiàn)后，入侵者需要逃避機(jī)器人的圍捕，因此需要進(jìn)行逃逸運(yùn)動(dòng)，通過(guò)計(jì)算相鄰機(jī)器人與自身所成的角度，選擇最大的夾角所對(duì)應(yīng)的圍捕機(jī)器人的中間位置作為逃逸方向，防止被捕捉[15]。定義入侵者E隨機(jī)運(yùn)動(dòng)的方向如下：

(6)

式(6)中，[ex,ey]T為E下一步的運(yùn)動(dòng)方向，[exo,eyo]T為E的初始運(yùn)動(dòng)方向，β為E隨機(jī)偏轉(zhuǎn)的角度。

如圖1所示，設(shè)E當(dāng)前的位置是(xe,ye)，定義逃逸運(yùn)動(dòng)的方向如下：

(7)

式(7)中，(xr1,2,yr1,2)為E選擇所成最大夾角的兩個(gè)圍捕機(jī)器人R1,R2的中點(diǎn)R1,2的坐標(biāo)。

圖1 入侵者逃逸運(yùn)動(dòng)示意圖

2 改進(jìn)的合同網(wǎng)模型

本文結(jié)合案例匹配方法，在傳統(tǒng)的合同網(wǎng)協(xié)議中，引入匹配度(Suit)和信譽(yù)度(Cred)對(duì)其進(jìn)行改進(jìn)。通過(guò)構(gòu)建案例庫(kù)，根據(jù)新任務(wù)與歷史任務(wù)的匹配度選擇候選承包商，減少了傳統(tǒng)算法中對(duì)所有承包商招標(biāo)的通信開(kāi)銷和對(duì)標(biāo)書的評(píng)估時(shí)間；再根據(jù)信譽(yù)度的高低選擇最佳的承包商，避免了傳統(tǒng)方法中承包商之間的沖突問(wèn)題；當(dāng)某承包商發(fā)生故障，在降低其信譽(yù)度的同時(shí)，選擇次高信譽(yù)度的承包商完成任務(wù)，較于傳統(tǒng)算法適應(yīng)了動(dòng)態(tài)環(huán)境。

2.1 構(gòu)建案例庫(kù)

為了獲得案例庫(kù)中的有效數(shù)據(jù)，使不同的圍捕機(jī)器人組成的圍捕小組在同一環(huán)境下執(zhí)行任務(wù)。

案例Case用一個(gè)四元組描述：

Case=〈C,G,R,T〉

(8)

式(8)中，C表示任務(wù)類型(Character)；G表示任務(wù)所對(duì)應(yīng)的承包商，即圍捕小組(Group)；R表示完成任務(wù)的信譽(yù)度(Credit)；T表示完成任務(wù)的時(shí)間(Time)。

任務(wù)的標(biāo)書Bid用一個(gè)三元組描述：

Bid=〈C,A,N〉

(9)

式(9)中，C表示任務(wù)類型(Character)；A表示至少需要有一個(gè)承包商滿足任務(wù)的最低能力要求(Ability)；N表示完成任務(wù)所需的最少承包商個(gè)數(shù)(Number)。

本文假定有10個(gè)圍捕機(jī)器人，根據(jù)能力的不同，分為3組：{R11,…,R13},{R21,…,R23},{R31,…,R34}，能力由速度和傳感范圍表示，分別設(shè)置為{(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)}；由于是圍捕任務(wù)，用入侵者的速度和傳感范圍表示任務(wù)特征，速度和傳感范圍的區(qū)域?yàn)閇1.1,1.5]和[2,5]；不同類型的入侵者對(duì)應(yīng)的標(biāo)書設(shè)為：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)〉。

圍捕狀態(tài)如圖2所示，其中，入侵者位于中心位置，用E表示；圍捕機(jī)器人用R表示。

圖2 圍捕狀態(tài)

根據(jù)以上描述，在能夠完成圍捕任務(wù)的前提下，即在圍捕機(jī)器人組成的小組中，至少有一個(gè)圍捕機(jī)器人的能力大于等于入侵者的能力；將圍捕機(jī)器人依照不同的任務(wù)類型，由難到易合理分配，盡量使得各圍捕機(jī)器人物盡其用，而非大材小用；之后各圍捕小組的機(jī)器人進(jìn)行隨機(jī)組合，采用前述的圍捕策略，根據(jù)自身能力通過(guò)搜索、追蹤、包圍和捕捉進(jìn)行10次圍捕實(shí)驗(yàn)，記錄下信譽(yù)度和圍捕時(shí)間的平均值，最終得到如表1所示的案例庫(kù)。

表1 案例庫(kù)

2.2 計(jì)算匹配度

匹配度指的是管理者接收的新任務(wù)Tj與案例庫(kù)中已存的歷史任務(wù)Ti的相似程度。根據(jù)余弦相似度的含義，定義匹配度Suit(Tj,Tj)如下：

(10)

式(10)中，Tj,m與Ti,m分別為任務(wù)Tj與Ti中第m(m=1,2,…,n)項(xiàng)特征的值，k為常數(shù)。當(dāng)Suit(Tj,Ti)≥σ(σ為常數(shù))時(shí)認(rèn)為二者相似性高，匹配成功，將滿足條件的Suit進(jìn)行從小到大排序，選擇最高Suit所對(duì)應(yīng)的歷史任務(wù)Ti，確定完成任務(wù)Tj的承包商ai。當(dāng)發(fā)現(xiàn)匹配的歷史任務(wù)Ti的承包商不唯一時(shí)，管理者需要根據(jù)信譽(yù)度的高低選出最合適的承包商。

2.3 計(jì)算信譽(yù)度

信譽(yù)度指的是在改進(jìn)合同網(wǎng)協(xié)議中承包商ai完成任務(wù)Ti的成功率Pi。在執(zhí)行任務(wù)的過(guò)程中，如果承包商ai能夠完成管理者分配的任務(wù)Tj時(shí)，則更新案例庫(kù)中ai的信譽(yù)度，使其增加ξ1，即Credii+ξ1；反之，如果不能順利完成任務(wù)，則使其信譽(yù)度降低ξ2，即Credii-ξ2。

在分配任務(wù)時(shí)，管理者根據(jù)信譽(yù)度選擇承包商，避免了面向所有承包商招標(biāo)的情況，減少了通信開(kāi)銷。定義信譽(yù)度(Cred)如下：

Cred=max(Credmin,P)

(11)

(12)

其中，Credmin表示信譽(yù)度的最小閾值，P表示承包商完成任務(wù)的成功率，Cs為承包商成功完成任務(wù)的次數(shù)，Ct為承包商參加任務(wù)的總次數(shù)。

2.4 任務(wù)分配算法

根據(jù)上文的描述，基于案例匹配的改進(jìn)合同網(wǎng)協(xié)議任務(wù)分配算法流程如圖3。

圖3 改進(jìn)合同網(wǎng)協(xié)議的流程

3 仿真與分析

在基于柵格法建模的二維環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，在本文中，經(jīng)過(guò)多次實(shí)驗(yàn)，取常數(shù)L=5，σ=90%效果較好；一般而言，需ξ2?ξ1，因?yàn)橐坏┻x定的承包商因?yàn)槟撤N原因不能成功完成任務(wù)，管理者在下一次招標(biāo)的時(shí)候應(yīng)避免選中此承包商，因此需要大大降低其信譽(yù)度。因此在更新信譽(yù)度的過(guò)程中，令ξ1=0.01，ξ2=0.1。在下列仿真圍捕示意圖中，所標(biāo)識(shí)的如“R12”等位置即為相關(guān)圍捕機(jī)器人所在的初始位置。

1) 當(dāng)入侵者數(shù)量為1的情形

當(dāng)管理者接收到特征為(1.13,2.82)的圍捕任務(wù)時(shí)(入侵者用E表示)，通過(guò)計(jì)算與入侵者標(biāo)書中不同任務(wù)類型的特征距離，再根據(jù)匹配度的計(jì)算公式，得到與類型1的匹配度最高，約為99.9%，因此二者匹配；根據(jù)案例庫(kù)可知，特征匹配的圍捕機(jī)器人有2組，管理者向信任度最高且時(shí)間最短的組{R12,R13}招標(biāo)，該組進(jìn)行投標(biāo)，與管理者確認(rèn)消息后，管理者宣布其中標(biāo)，并與其簽訂合同，于是此組被選派執(zhí)行任務(wù)；如圖4所示，R12經(jīng)過(guò)搜索發(fā)現(xiàn)E之后，與R13合作對(duì)其進(jìn)行追逐和包圍，而E1采取一定的逃逸策略逃跑，R12和R13經(jīng)過(guò)協(xié)作成功捕獲E，管理者更新其信譽(yù)度為101%。

圖4 入侵者數(shù)量為1的仿真圍捕

2) 當(dāng)入侵者數(shù)量為2的情形

當(dāng)兩個(gè)新任務(wù)的特征分別為(1.15,3.1)和(1.2,2.8)時(shí)(入侵者用E1和E2表示)，通過(guò)計(jì)算可知匹配度最高的圍捕任務(wù)分別是類型1和2，匹配度分別約為100% 和99.9%；管理者選擇信譽(yù)度最高且時(shí)間最短的組{R12,R13}和{R21,R22}進(jìn)行招標(biāo)，經(jīng)投標(biāo)和簽訂合同之后，圍捕任務(wù)開(kāi)始。如圖5所示，兩組圍捕機(jī)器人通過(guò)搜索、追蹤、包圍之后，將E1和E2捕捉成功，管理者更新{R12,R13}和{R21,R22}的信譽(yù)度為101%和100.75%。

圖5 入侵者數(shù)量為2的仿真圍捕

3) 承包商故障的情形

當(dāng)管理者接收到特征為(1.36,5)的新任務(wù)時(shí)，通過(guò)計(jì)算可知匹配的圍捕任務(wù)為類型6，匹配度約為97%，管理者選擇信譽(yù)度最高且時(shí)間最短的組{R31,R32,R34}進(jìn)行招標(biāo)，但是由于R31故障，該組不進(jìn)行投標(biāo)，于是管理者更新{R31,R32,R34}信譽(yù)度為90%，轉(zhuǎn)而選擇信譽(yù)度次高且時(shí)間最短的組{R32,R33,R34}進(jìn)行招標(biāo)，在該組完成一系列投標(biāo)、中標(biāo)和簽訂合同之后，R32,R33,R34開(kāi)始執(zhí)行任務(wù)，如圖6所示，在三者的合力圍捕下，圍捕成功，管理者更新{R32,R33,R34}的信譽(yù)度為100.58%。

4) 與經(jīng)典合同網(wǎng)協(xié)議的比較

以承包商{R32,R33,R34}圍捕特征為(1.36,5)的入侵者為例，進(jìn)行100次仿真實(shí)驗(yàn)，研究傳統(tǒng)合同網(wǎng)與改進(jìn)合同網(wǎng)協(xié)議下完成圍捕任務(wù)的時(shí)間和成功率的不同。根據(jù)記錄結(jié)果，經(jīng)典合同網(wǎng)平均耗時(shí)25.02 s，平均成功率為96.32%；而改進(jìn)合同網(wǎng)耗時(shí)8.06 s，平均成功率為98.62%。

圖6 入侵者數(shù)量為3的仿真圍捕

如圖7所示，基于改進(jìn)合同網(wǎng)的圍捕任務(wù)完成分配的時(shí)間整體上低于經(jīng)典合同網(wǎng)，主要原因是在傳統(tǒng)的合同網(wǎng)協(xié)議中，需要向所有承包商進(jìn)行招標(biāo)，時(shí)間復(fù)雜度為O(n)；而在改進(jìn)的合同網(wǎng)協(xié)議中，管理者只需結(jié)合匹配度和信譽(yù)度，向唯一的承包商進(jìn)行投標(biāo)即可，此時(shí)算法的時(shí)間復(fù)雜度為O(1)，縮短了約68%的通信時(shí)間。

圖7 兩種協(xié)議時(shí)間的比較

由圖8可知，改進(jìn)合同網(wǎng)協(xié)議的成功率高于經(jīng)典合同網(wǎng)，提高了約2.3%。因?yàn)閭鹘y(tǒng)的協(xié)議不能適應(yīng)承包商突然故障的情況，需要重新招標(biāo)；而改進(jìn)的合同網(wǎng)能夠依據(jù)信譽(yù)度的次高值，較快選擇新的承包商，完成圍捕任務(wù)。

圖8 兩種協(xié)議成功率的比較

5) 與其他改進(jìn)合同網(wǎng)協(xié)議的比較

同樣以承包商{R32,R33,R34}圍捕特征為(1.36,5)的入侵者為例，進(jìn)行100次仿真實(shí)驗(yàn)。為更好地觀察實(shí)驗(yàn)結(jié)果，將每20次分為一組，研究文獻(xiàn)[5]改進(jìn)合同網(wǎng)與本文所提改進(jìn)合同網(wǎng)在完成圍捕任務(wù)的時(shí)間和成功率的差異。根據(jù)記錄結(jié)果，文獻(xiàn)[5]算法平均耗時(shí)18.22 s，平均成功率為93.59%；而本文算法平均耗時(shí)7.88 s，平均成功率為96.63%。

圖9和圖10分別展示了文獻(xiàn)[5]算法和本文算法在圍捕時(shí)間和成功率方面的不同，其原因主要是在文獻(xiàn)[5]改進(jìn)合同網(wǎng)協(xié)議中，只考慮了單承包商完成任務(wù)的問(wèn)題，未考慮多承包商協(xié)作問(wèn)題；在面對(duì)復(fù)雜任務(wù)時(shí)，單承包商無(wú)法完成任務(wù)，管理者需要向余下的承包商進(jìn)行招標(biāo)、評(píng)估，既增加了通信開(kāi)銷，又影響了圍捕的成功率。

圖9 兩種算法的時(shí)間

圖10 兩種算法的成功率

4 結(jié)論

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