RoboCup標(biāo)準(zhǔn)平臺組中基于改進(jìn)合同網(wǎng)協(xié)議的任務(wù)分配算法*

梁志偉，吳海健

(南京郵電大學(xué)自動化學(xué)院、人工智能學(xué)院，江蘇 南京 210023)

1 引言

RoboCup機(jī)器人足球賽是由多個機(jī)器人組成的多智能體系統(tǒng)MAS(Multi-Agent System)。隨著機(jī)器人智能水平的提高，由于比賽的對抗性和動態(tài)環(huán)境的時變性，如何規(guī)劃各個機(jī)器人的運(yùn)動、發(fā)揮球隊的整體功能，即多智能體任務(wù)分解與分配[1]是機(jī)器人研究的關(guān)鍵問題。其中任務(wù)分配在比賽中起著重要的作用，主要體現(xiàn)在通過視覺模塊和傳感器模塊獲取信息，使得多個機(jī)器人之間不會互相干擾、沖突，在任務(wù)的執(zhí)行上具有一致性，同時需要解決各個機(jī)器人在每個時刻分別完成什么任務(wù)、執(zhí)行什么動作的問題。任務(wù)分解是設(shè)計任務(wù)分配算法的前提，如何簡單適度、有效地分解任務(wù)對任務(wù)分配算法有至關(guān)重要的影響[2]。

任務(wù)分配通過構(gòu)建科學(xué)健壯的數(shù)學(xué)模型，設(shè)計優(yōu)化算法完成任務(wù)配置，使個體的資源得到充分利用，從而高效地完成任務(wù)，體現(xiàn)了多智能體系統(tǒng)(MAS)的高層組織形式與運(yùn)行機(jī)制[3]。合同網(wǎng)協(xié)議CNP(Contract Network Protocol)是一種比較經(jīng)典的任務(wù)協(xié)商和資源分配策略。隨著多智能體系統(tǒng)的發(fā)展，合同網(wǎng)由于具有對分布式系統(tǒng)的適用性，逐漸成為一種有效的多Agent協(xié)調(diào)機(jī)制[4]。然而傳統(tǒng)合同網(wǎng)協(xié)議存在通行開銷大、任務(wù)資格評價策略不完善等不足，因此國內(nèi)外的學(xué)者針對諸多不足提出了不同程度的改進(jìn)。為了減少通信開銷，降低協(xié)商通信量，陳明等[5]基于對Agent心智的綜合評價，將Agent分為熟人、一般熟人和陌生人3種類型，以從大到小的概率選擇3種Agent招標(biāo)。Zhang等[6]為了減少協(xié)商過程中產(chǎn)生的冗余信息量，在蟻群算法的基礎(chǔ)上，建立動態(tài)響應(yīng)閾值模型和信息素流模型。Yeung[7]針對多智能體系統(tǒng)容易受到消息擁塞的影響從而影響任務(wù)分配決策效率的問題，將受眾限制AR(Audience Restriction)引入了合同網(wǎng)協(xié)議。此外，由于管理者知識的局限性，為全面評價合同者能力，賀利堅[8]采用信譽(yù)值從直接與間接2方面獲取合同者的信任度；Rob[9]從雙邊市場經(jīng)濟(jì)理論和機(jī)制設(shè)計的角度出發(fā)引入了價值網(wǎng)的概念，擴(kuò)展了合同網(wǎng)協(xié)議。在完善任務(wù)資格評價策略方面，錢艷平等[10]首先以常規(guī)評價策略將任務(wù)分配給合同者，而后以負(fù)載系數(shù)(定義同負(fù)載率)為依據(jù)，通過合同者之間的協(xié)商，達(dá)到負(fù)載均衡。同樣，考慮到合同者接受任務(wù)授權(quán)的可能性，周坤[11]通過定義可用度為已投標(biāo)書與投標(biāo)費(fèi)用乘積的倒數(shù)來反映合同者的可用度；Zhang等[12]研究了協(xié)同任務(wù)的目標(biāo)選擇策略、協(xié)商的合同投標(biāo)方法以及合同的評價方法，并在虛擬星座應(yīng)用場景下對合同網(wǎng)協(xié)議進(jìn)行了擴(kuò)展;Hu等[13]引入了QoS(Quality of Service)多目標(biāo)約束，給投標(biāo)者和招標(biāo)者提供了雙向的篩選約束，大大提高了任務(wù)完成的質(zhì)量。對于突發(fā)出現(xiàn)的重要問題或者在任務(wù)執(zhí)行過程中合同者不再滿足要求時，郝會成[14]引入了可解約機(jī)制。當(dāng)突發(fā)重要任務(wù)或者合同者不能完成任務(wù)時，合同者可以提出解約合同，中止當(dāng)前任務(wù)，所有的“解約任務(wù)”就重新由管理者向其他合同者招標(biāo)。在減少任務(wù)沖突的影響方面，Du等[15]提出了合同網(wǎng)協(xié)議的二次分配策略，通過公告、競價和授標(biāo)等方式，有效地提高了觀測收益。

本文在分析相關(guān)工作的基礎(chǔ)上，以RoboCup標(biāo)準(zhǔn)平臺組機(jī)器人足球賽為背景，針對目前對任務(wù)分解和任務(wù)分配在機(jī)器人足球賽上的應(yīng)用研究較少的問題，首先對多機(jī)器人系統(tǒng)進(jìn)行任務(wù)分解和層次規(guī)劃，將總?cè)蝿?wù)分解為若干子任務(wù)，以機(jī)器人足球賽為背景建立整個系統(tǒng)的層次分解模型；同時根據(jù)機(jī)器人的角色建立每個機(jī)器人的行為任務(wù)樹模型，并通過層次分析法AHP(Analytic Hierarchy Process)確定每個子任務(wù)的優(yōu)先級；最后，對傳統(tǒng)的合同網(wǎng)協(xié)議進(jìn)行改進(jìn)，對任務(wù)分配流程和中標(biāo)函數(shù)等進(jìn)行了改進(jìn)和擴(kuò)展。

2 任務(wù)分配數(shù)學(xué)模型

2.1 問題描述

動態(tài)任務(wù)分配問題是指在一定的區(qū)域內(nèi)，有m個機(jī)器人需要執(zhí)行n個任務(wù)，m個機(jī)器人的集合定義為R={Ri|i=1,2,3,…,m},n個任務(wù)的集合定義為T={Tj|j=1,2,3,…,n}[16]；由于比賽中機(jī)器人是5V5的賽制，所以m設(shè)置為5。

定義1任務(wù)用一個四元組描述Tj=〈ID,Name,Pri,Info〉,Info=〈x,y,θ〉，其中，ID表示任務(wù)編號，Name表示任務(wù)名稱，Pri表示任務(wù)優(yōu)先級，Info表示目標(biāo)點(diǎn)位置信息，〈x,y〉表示目標(biāo)位置，θ表示目標(biāo)角度。

定義2多機(jī)器人系統(tǒng)中的目標(biāo)函數(shù)定義如式(1)所示：

(1)

(2)

其中，Cij為任務(wù)執(zhí)行代價;θij表示第i個機(jī)器人在執(zhí)行任務(wù)Tj時，機(jī)器人需要轉(zhuǎn)過的角度;ω表示機(jī)器人的角速度;Sij表示第i個機(jī)器人在執(zhí)行任務(wù)Tj時，距離任務(wù)點(diǎn)的路程長度;V表示機(jī)器人的運(yùn)動速度;maxd表示所有參與投標(biāo)的機(jī)器人距離任務(wù)點(diǎn)的最大距離;mind表示所有參與投標(biāo)的機(jī)器人距離任務(wù)點(diǎn)的最小距離。

2.2 約束條件

定義3第i個機(jī)器人的任務(wù)隊列為Li={Li1,Li2,Li3,…,Lil},其中，Li1表示機(jī)器人待執(zhí)行的第1個任務(wù)；定義變量φij表示任務(wù)Tj是否分配給機(jī)器人Ri,當(dāng)φij=1表示分配成功，φij=0表示暫未分配；則目標(biāo)函數(shù)f需要滿足的約束條件如式(3)和式(4)所示：

(3)

(4)

式(3)限定了同一時刻任意一個機(jī)器人只能執(zhí)行一個任務(wù)；式(4)確保了每個任務(wù)都能分配給機(jī)器人，保證所有任務(wù)都被執(zhí)行。

3 任務(wù)分解以及行為任務(wù)樹模型

任務(wù)分解是設(shè)計任務(wù)分配算法的前提，簡單適度、有效地分解任務(wù)對任務(wù)分配算法有至關(guān)重要的影響[17]。本文將總?cè)蝿?wù)設(shè)置為{attack,defend}，當(dāng)球位于對方半場時，己方總?cè)蝿?wù)為attack;球位于己方半場時，己方總?cè)蝿?wù)為defend。當(dāng)總?cè)蝿?wù)為attack時，根據(jù)場上機(jī)器人數(shù)量，將機(jī)器人分別設(shè)置為5個角色，它們是：前鋒、助攻1、助攻2、后衛(wèi)和守門員；當(dāng)總?cè)蝿?wù)為defend時，將機(jī)器人分別設(shè)置為：前鋒、助攻、后衛(wèi)1、后衛(wèi)2和守門員。前鋒的主要任務(wù)是進(jìn)攻，把球射入到對方的球門；助攻的主要任務(wù)是協(xié)作前鋒進(jìn)攻，后衛(wèi)1和后衛(wèi)2的主要任務(wù)是防守，防止對方射門得分；守門員的主要任務(wù)是攔截球，防守球門。

3.1 層次結(jié)構(gòu)分解模型

本文建立多機(jī)器人系統(tǒng)任務(wù)分配的層次結(jié)構(gòu)模型，模型第1層為根任務(wù)，第2層為總?cè)蝿?wù)，第3層為角色層，第4層為各個角色的行為任務(wù)樹，如圖1所示。

Figure 1 Hierarchical model圖1 層次結(jié)構(gòu)模型

此外，本文設(shè)置一個共享信息區(qū)用來提供機(jī)器人執(zhí)行任務(wù)過程中需要的交互數(shù)據(jù)，主要包括視覺處理模塊、定位模塊和路徑規(guī)劃模塊。

3.2 行為任務(wù)樹模型

在層次結(jié)構(gòu)分解模型的基礎(chǔ)上，根據(jù)每個機(jī)器人角色的不同，建立機(jī)器人的行為任務(wù)樹模型。本文以前鋒角色為例建立前鋒機(jī)器人的行為任務(wù)樹模型，如圖2所示。

Figure 2 Behavior task tree model of forward role 圖2 前鋒角色行為任務(wù)樹模型

由圖2可知：行為任務(wù)樹模型分為3層，第1層為角色層，第2層為行為層，第3層為動作層。在此基礎(chǔ)上，采用層次分析法AHP對任務(wù)進(jìn)行定量分析，確定每個任務(wù)的優(yōu)先級大小。

4 合同網(wǎng)協(xié)議的改進(jìn)

傳統(tǒng)的合同網(wǎng)協(xié)議存在協(xié)商通信量大、任務(wù)評價資格不完善等問題[18]，針對這些問題，本文在降低協(xié)商通信量、優(yōu)化合同網(wǎng)流程和評價策略方面對其進(jìn)行了改進(jìn)和擴(kuò)展。本文以5個機(jī)器人組成一個分布式多機(jī)器人系統(tǒng)，系統(tǒng)中有管理者和合同者，管理者和合同者的身份可以按照實(shí)際情況進(jìn)行動態(tài)轉(zhuǎn)換，管理者主要負(fù)責(zé)招標(biāo)任務(wù)的發(fā)布、標(biāo)書的評估和任務(wù)的分配；合同者可以根據(jù)招標(biāo)信息評估協(xié)作成本以及根據(jù)任務(wù)隊列負(fù)載決定是否參與投標(biāo)。

4.1 單個Agent模型

本文首先需要對Agent進(jìn)行建模，單個Agent基本結(jié)構(gòu)如圖3所示。

Figure 3 Basic structure of single Agent圖3 單個Agent基本結(jié)構(gòu)

單個Agent基本結(jié)構(gòu)中包含視覺模塊、定位模塊、路徑規(guī)劃模塊、信息庫、決策和信息處理中心、任務(wù)執(zhí)行器、動作模塊和通信模塊。信息庫中主要存儲任務(wù)相關(guān)信息(包含任務(wù)點(diǎn)坐標(biāo)和運(yùn)動路徑等)、歷史任務(wù)信息和Agent狀態(tài)信息(包含能力信息、角色信息和機(jī)器人位置信息)。決策和信息處理中心進(jìn)行任務(wù)的發(fā)布、招標(biāo)、投標(biāo)、任務(wù)資格評價、任務(wù)分配以及合同的簽署。在合同簽署之后任務(wù)執(zhí)行器根據(jù)決策和信息處理中心的決定執(zhí)行相應(yīng)的任務(wù)。動作模塊執(zhí)行Agent需要執(zhí)行的動作。通信模塊用來發(fā)布和接收信息，以便在節(jié)點(diǎn)之間進(jìn)行通信，以及在調(diào)試階段與PC(Personal Computer)進(jìn)行連接[19]。

4.2 單個Agent控制過程

Agent的控制大致分為上線程、下線程、感知、運(yùn)動和調(diào)試5個過程，如圖4所示。

Figure 4 Control process of single Agent 圖4 單個Agent控制過程

其中上線程用來接收上攝像頭的數(shù)據(jù)，下線程用來接收下攝像頭的數(shù)據(jù)；此外，還可以從世界模型中的感知線程獲取環(huán)境信息以及從運(yùn)動線程中獲取傳感器信息[20]。同時，上、下線程對圖像進(jìn)行處理并將檢測結(jié)果發(fā)送到感知線程。感知線程將這些信息與來自運(yùn)動線程的傳感器數(shù)據(jù)一起用于世界建模和行為控制，并將高級運(yùn)動命令發(fā)送到運(yùn)動線程。調(diào)試線程執(zhí)行與主機(jī)PC的TCP通信以進(jìn)行調(diào)試[21]。

4.3 優(yōu)先主動招標(biāo)策略

為了降低協(xié)商通信量，管理者在招標(biāo)時優(yōu)先向合適的合同者進(jìn)行招標(biāo)；合同者收到招標(biāo)信息后，首先評估自身能力和負(fù)載確定是否投標(biāo)。本文結(jié)合機(jī)器人足球賽背景，確定了如表1和表2所示的優(yōu)先級對照表。

(1)總?cè)蝿?wù)為attack時，優(yōu)先級如表1所示。

Table 1 Priority comparison table(attack)

(2)總?cè)蝿?wù)為defend時，優(yōu)先級如表2所示。

本文將優(yōu)先級分為3個等級，最高為等級3；當(dāng)管理者需要進(jìn)行招標(biāo)時，優(yōu)先向優(yōu)先級最高的Agent進(jìn)行招標(biāo)，若未得到回應(yīng)則轉(zhuǎn)向優(yōu)先級次之的Agent進(jìn)行招標(biāo)，依次下去；當(dāng)所有Agent都沒有回應(yīng)，且等待超時時，管理者向所有合同者進(jìn)行招標(biāo)。

Table 2 Priority comparison table(defend)

4.4 評價函數(shù)

在合同網(wǎng)協(xié)議中管理者收到合同者的標(biāo)書后，需要對其進(jìn)行任務(wù)資格評價，常見的任務(wù)資格評價策略包括時間最短策略、成本最低策略、質(zhì)量優(yōu)先策略、負(fù)載均衡、協(xié)作成本和可用度等，通過設(shè)計統(tǒng)一的評標(biāo)函數(shù)對標(biāo)書進(jìn)行評價形成綜合評價表。然而在不考慮合同者自身特性的情況下使用單一的評價函數(shù)對所有任務(wù)標(biāo)書進(jìn)行評價存在片面性和不合理性，針對此問題，本文按照機(jī)器人角色的不同設(shè)計了不同的評價函數(shù)。

(1)進(jìn)攻類角色(如前鋒、助攻)的評價函數(shù)如式(5)所示：

(5)

其中，dball表示球相對于機(jī)器人的距離；θgoal表示機(jī)器人質(zhì)心、球、對方球門中心三者之間的夾角；τ表示機(jī)器人的視覺丟球時間，單位為s;k1、k2和k3為權(quán)重系數(shù)。

(2)防守類角色(如后衛(wèi)、守門員)的評價函數(shù)如式(6)所示：

(6)

其中，Lgoal表示機(jī)器人與己方球門的橫向距離；η表示機(jī)器人的方向信息，當(dāng)機(jī)器人朝向己方球門一側(cè)時η=1；當(dāng)機(jī)器人朝向?qū)Ψ角蜷T一側(cè)時η=0；k4和k5為權(quán)重系數(shù)。

4.5 任務(wù)分配算法

(1)管理者招標(biāo)流程。

機(jī)器人有招標(biāo)需求后變?yōu)楣芾碚撸鶕?jù)定義1將任務(wù)通過團(tuán)隊通信網(wǎng)絡(luò)進(jìn)行發(fā)布。管理者根據(jù)4.3節(jié)制定的優(yōu)先招標(biāo)策略，優(yōu)先進(jìn)行招標(biāo)；當(dāng)收到投標(biāo)信息后，管理者將投標(biāo)的標(biāo)書進(jìn)行公示。若其他空閑機(jī)器人在公示期內(nèi)有異議則可以發(fā)起投標(biāo)，管理者收到其他機(jī)器人發(fā)送的標(biāo)書后進(jìn)行綜合評估形成綜合評價排序表，最后選取最優(yōu)合同者簽署合同，完成任務(wù)分配。若公示期結(jié)束后沒有機(jī)器人發(fā)出異議，管理者直接與優(yōu)先合同者進(jìn)行合同簽署完成任務(wù)分配，結(jié)束招標(biāo)。反之，當(dāng)管理者沒有收到優(yōu)先合同者發(fā)出的投標(biāo)信息，等待超時時，管理者則向所有機(jī)器人發(fā)出招標(biāo)請求，管理者收到標(biāo)書后進(jìn)行評估形成綜合評價表，最后選取最優(yōu)合同者簽署合同完成任務(wù)分配，結(jié)束招標(biāo)。管理者招標(biāo)算法流程圖如圖5所示。

Figure 5 Flow chart of tendering algorithm 圖5 招標(biāo)算法流程圖

(2)合同者投標(biāo)流程。

合同者通過感知獲取環(huán)境中的任務(wù)，根據(jù)自身能力評估招標(biāo)任務(wù)，并從任務(wù)隊列中選取合適的任務(wù)參與投標(biāo)。投標(biāo)的標(biāo)書由四元組描述：〈ID′,IDT,C,L〉,其中，ID′表示合同者的ID；IDT表示招標(biāo)任務(wù)的ID；C表示合同者的任務(wù)執(zhí)行代價；L表示定義3中的機(jī)器人任務(wù)隊列。合同者等待招標(biāo)信息，收到招標(biāo)信息后，首先判斷自身是否是管理者的優(yōu)先招標(biāo)方，若是優(yōu)先招標(biāo)方則評估自身能力和任務(wù)負(fù)載決定是否投標(biāo)。若自身不是優(yōu)先招標(biāo)方就繼續(xù)等待公示期管理者進(jìn)行標(biāo)書公示，合同者評估自身能力并計算任務(wù)執(zhí)行代價，從而決定是否參與競爭投標(biāo)。為了防止優(yōu)先方搶占更多資源以及在獲得授權(quán)前未加節(jié)制地盲目投標(biāo)，造成投標(biāo)消息劇增和任務(wù)無法最優(yōu)執(zhí)行的情況出現(xiàn)，本文采用閾值限定的方式進(jìn)行限制，即當(dāng)合同者任務(wù)隊列中待執(zhí)行的任務(wù)小于閾值時合同者才可以繼續(xù)投標(biāo)，否則忽略所有新的招標(biāo)消息。合同者投標(biāo)算法流程圖如圖6所示。

Figure 6 Flow chart of bidding algorithm 圖6 投標(biāo)算法流程圖

(3)任務(wù)分配過程。

任務(wù)分配過程主要包括招標(biāo)和投標(biāo)；管理者先發(fā)布招標(biāo)信息，合同者獲取招標(biāo)信息并決定是否進(jìn)行投標(biāo)，管理者根據(jù)收到的投標(biāo)信息進(jìn)行綜合評估并選擇最優(yōu)的合同者中標(biāo)，中標(biāo)合同者執(zhí)行中標(biāo)任務(wù)。分配任務(wù)的整個過程如下所示：

步驟1管理者為每個招標(biāo)任務(wù)設(shè)置ID，同時將任務(wù)釋放到環(huán)境中并向優(yōu)先招標(biāo)方進(jìn)行招標(biāo)。

步驟2合同者從環(huán)境中感知招標(biāo)任務(wù)，若自身為優(yōu)先招標(biāo)方則評估自身能力和任務(wù)負(fù)載決定是否投標(biāo)；若自身不是優(yōu)先方則等待管理者進(jìn)行標(biāo)書公示。

步驟3管理者將收到的優(yōu)先標(biāo)書進(jìn)行公示，若公示期內(nèi)沒有合同者有異議則評估標(biāo)書，轉(zhuǎn)步驟6；若合同者有異議則等待投標(biāo)信息。

步驟4合同者感知到管理者進(jìn)行公示的標(biāo)書后，進(jìn)行評估并計算任務(wù)執(zhí)行代價C，若有異議則進(jìn)行投標(biāo)。

步驟5管理者收到相同ID′和IDT的投標(biāo)信息后，通過計算對標(biāo)書進(jìn)行評估，在任務(wù)集相同的情況下，按任務(wù)的優(yōu)先級從最大值到最小值進(jìn)行排序，得到任務(wù)的綜合評價排序表。

步驟6將任務(wù)分配給列表中第1個Agent，通知它中標(biāo)并發(fā)布中標(biāo)結(jié)果。

步驟7簽署合同。

步驟8任務(wù)分配完成。

5 實(shí)驗驗證

5.1 Matlab仿真實(shí)驗

本文先使用Matlab進(jìn)行模擬仿真實(shí)驗，設(shè)定任務(wù)數(shù)為10，實(shí)驗結(jié)果如圖7和圖8所示。當(dāng)任務(wù)數(shù)為10時，機(jī)器人任務(wù)分配圖如圖7所示，由圖7可以看到利用傳統(tǒng)的合同網(wǎng)協(xié)議，2號機(jī)器人沒有被分配到任務(wù)，處于空閑狀態(tài)，而5號機(jī)器人分配路徑過長，任務(wù)過多，顯然是分配不合理的。圖8為改進(jìn)合同網(wǎng)后機(jī)器人任務(wù)分配結(jié)果，可以看出沒有機(jī)器人處于空閑狀態(tài)，資源利用最優(yōu)，分配路徑也較為合理。

Figure 7 Result of traditional contract network protocol圖7 傳統(tǒng)合同網(wǎng)協(xié)議結(jié)果

Figure 8 Result of improved contract network protocol圖8 改進(jìn)后的合同網(wǎng)協(xié)議結(jié)果

5.2 SimRobot仿真實(shí)驗

SimRobot仿真軟件是用于RoboCup機(jī)器人世界杯標(biāo)準(zhǔn)平臺組足球比賽調(diào)試的模擬仿真軟件，它能夠模擬物理世界機(jī)器人進(jìn)行比賽對抗的真實(shí)場景。通過軟件預(yù)先設(shè)置2支機(jī)器人比賽隊伍，以5個機(jī)器人為一組進(jìn)行5V5對抗；本文選用一支隊伍使用改進(jìn)后的合同網(wǎng)協(xié)議，另一支隊伍使用傳統(tǒng)合同網(wǎng)協(xié)議進(jìn)行對抗賽。

如圖9所示，守門員為1號，前鋒為5號，后衛(wèi)2為3號，后衛(wèi)1為4號。當(dāng)2號前鋒根據(jù)行為任務(wù)樹進(jìn)攻到對方球門準(zhǔn)備射門時，射門路線被對方機(jī)器人阻斷不能進(jìn)行射門操作。因此，2號前鋒(此時為管理者)發(fā)出協(xié)作請求信息(請求協(xié)作進(jìn)攻)；優(yōu)先向5號助攻(此時為合同者)進(jìn)行招標(biāo)，5號助攻收到招標(biāo)信息后評價自身能力并計算任務(wù)執(zhí)行代價決定是否投標(biāo)，2號前鋒收到投標(biāo)請求后對其執(zhí)行代價進(jìn)行公示，在公示期內(nèi)其他機(jī)器人若無異議則進(jìn)行合同簽署，招標(biāo)完成。5號機(jī)器人收到中標(biāo)結(jié)果后執(zhí)行相應(yīng)任務(wù)。

Figure 9 Cooperation between robots after improving contract network protocol圖9 改進(jìn)合同網(wǎng)協(xié)議后機(jī)器人之間的協(xié)作

5.3 實(shí)體機(jī)器人驗證

本文在仿真實(shí)驗的基礎(chǔ)上采用NAO機(jī)器人作為實(shí)驗平臺，進(jìn)行實(shí)驗驗證。機(jī)器人在運(yùn)行時，首先需要從共享信息區(qū)獲取環(huán)境信息(比如足球的位置信息、對方球門信息、對方機(jī)器人位置信息等)，如圖10所示。

Figure 10 Information sharing area圖10 信息共享區(qū)獲取信息

用實(shí)體機(jī)器人進(jìn)行驗證實(shí)驗，如圖11a所示，2號前鋒機(jī)器人的前進(jìn)射門路線被對方機(jī)器人阻擋。因此發(fā)出協(xié)作請求，優(yōu)先向5號機(jī)器人進(jìn)行招標(biāo)，經(jīng)過投標(biāo)、公示和評標(biāo)等流程后，5號機(jī)器人中標(biāo)并走到相應(yīng)位置；當(dāng)防守時，如圖11b所示，對方機(jī)器人進(jìn)攻我方球門前，1號守門員執(zhí)行防守任務(wù)；同時發(fā)出協(xié)助防守請求，4號機(jī)器人中標(biāo)并執(zhí)行中標(biāo)任務(wù)。

Figure 11 Physical robot experiment圖11 實(shí)體機(jī)器人實(shí)驗

在足球比賽實(shí)驗中，機(jī)器人根據(jù)設(shè)定的行為任務(wù)數(shù)執(zhí)行相應(yīng)的任務(wù)。某一時刻機(jī)器人行為任務(wù)樹如圖12所示。

Figure 12 Robot behavior task tree圖12 機(jī)器人行為任務(wù)樹

通過上面的實(shí)驗結(jié)果可知，相比使用傳統(tǒng)合同網(wǎng)協(xié)議的機(jī)器人隊伍，使用改進(jìn)后合同網(wǎng)協(xié)議的機(jī)器人隊伍靈活性、協(xié)作效率、進(jìn)攻成功率和防守成功率都有很大的提高。任務(wù)完成分配時間對比如圖13所示。任務(wù)完成分配時間較傳統(tǒng)的任務(wù)完成分配時間縮短了約57%，有效提高了團(tuán)隊協(xié)作效率。

Figure 13 Comparison of task allocation time consumption圖13 任務(wù)分配時間消耗對比

同時，本文對機(jī)器人團(tuán)隊進(jìn)攻端的任務(wù)分配效果進(jìn)行驗證，以機(jī)器人足球賽為背景進(jìn)行了50場次的機(jī)器人團(tuán)隊對抗賽，機(jī)器人團(tuán)隊的進(jìn)球數(shù)如圖14所示。從圖14中可以看出，使用改進(jìn)后合同網(wǎng)協(xié)議的團(tuán)隊平均進(jìn)球數(shù)穩(wěn)定在5左右，而使用傳統(tǒng)合同網(wǎng)協(xié)議的團(tuán)隊平均進(jìn)球數(shù)穩(wěn)定在2左右，進(jìn)球率提高了30%。

Figure 14 Number of goals scored by the team圖14 比賽團(tuán)隊進(jìn)球數(shù)

除此之外，為了驗證任務(wù)分配在機(jī)器人防守端的效果，本文通過機(jī)器人5V5攻防賽對機(jī)器人防守端的任務(wù)分配效果進(jìn)行驗證。機(jī)器人團(tuán)隊的防守成功率如圖15所示。從圖15中可以看出，使用改進(jìn)后的合同網(wǎng)協(xié)議的防守成功率較使用傳統(tǒng)合同網(wǎng)協(xié)議的有了很大的提升，防守成功率在97%左右，魯棒性較好；而使用傳統(tǒng)合同網(wǎng)協(xié)議的防守成功率在87.5%左右，并且成功率波動幅度較大。

Figure 15 Defense success rate of robot team圖15 機(jī)器人團(tuán)隊防守成功率

6 結(jié)束語

通過以上實(shí)驗表明，改進(jìn)的合同網(wǎng)協(xié)議能夠有效提高機(jī)器人團(tuán)隊之間的協(xié)作能力，具有良好的魯棒性和快速性。本文首先以機(jī)器人足球賽為背景提出了系統(tǒng)的層次分解模型以及機(jī)器人行為任務(wù)樹，并對任務(wù)進(jìn)行了分解和確權(quán)；針對傳統(tǒng)合同網(wǎng)協(xié)議的不足之處，從降低協(xié)商通信量、任務(wù)資格評價和合同網(wǎng)協(xié)作模型3方面對傳統(tǒng)合同網(wǎng)協(xié)議進(jìn)行了改進(jìn)，并通過實(shí)驗進(jìn)行了驗證。實(shí)驗結(jié)果表明了本文算法在解決時間緊迫的實(shí)際任務(wù)分配問題上的有效性。本文算法還存在一些不足之處，接下來的研究重點(diǎn)主要集中在如何為任務(wù)隊列中待執(zhí)行任務(wù)和招標(biāo)任務(wù)建立耦合模型，以便在任務(wù)分配時考慮任務(wù)之間的耦合性。其次，對于任務(wù)分解本文主要是根據(jù)實(shí)際經(jīng)驗手動進(jìn)行分解和確權(quán)，因此如何對任務(wù)進(jìn)行自動分解和確權(quán)是接下來需要解決的重點(diǎn)問題之一。