梁志偉，吳海健

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

1 引言

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

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

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

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

2.1 問題描述

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

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

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

(1)

(2)

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

2.2 約束條件

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

(3)

(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 單個(gè)Agent模型

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

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

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

4.2 單個(gè)Agent控制過程

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

Figure 4 Control process of single Agent 圖4 單個(gè)Agent控制過程

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

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

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

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

Table 1 Priority comparison table(attack)

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

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

Table 2 Priority comparison table(defend)

4.4 評(píng)價(jià)函數(shù)

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

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

(5)

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

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

(6)

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

4.5 任務(wù)分配算法

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

機(jī)器人有招標(biāo)需求后變?yōu)楣芾碚?，根?jù)定義1將任務(wù)通過團(tuán)隊(duì)通信網(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)行綜合評(píng)估形成綜合評(píng)價(jià)排序表，最后選取最優(yōu)合同者簽署合同，完成任務(wù)分配。若公示期結(jié)束后沒有機(jī)器人發(fā)出異議，管理者直接與優(yōu)先合同者進(jìn)行合同簽署完成任務(wù)分配，結(jié)束招標(biāo)。反之，當(dāng)管理者沒有收到優(yōu)先合同者發(fā)出的投標(biāo)信息，等待超時(shí)時(shí)，管理者則向所有機(jī)器人發(fā)出招標(biāo)請(qǐng)求，管理者收到標(biāo)書后進(jìn)行評(píng)估形成綜合評(píng)價(jià)表，最后選取最優(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ù)自身能力評(píng)估招標(biāo)任務(wù)，并從任務(wù)隊(duì)列中選取合適的任務(wù)參與投標(biāo)。投標(biāo)的標(biāo)書由四元組描述：〈ID′,IDT,C,L〉,其中，ID′表示合同者的ID；IDT表示招標(biāo)任務(wù)的ID；C表示合同者的任務(wù)執(zhí)行代價(jià)；L表示定義3中的機(jī)器人任務(wù)隊(duì)列。合同者等待招標(biāo)信息，收到招標(biāo)信息后，首先判斷自身是否是管理者的優(yōu)先招標(biāo)方，若是優(yōu)先招標(biāo)方則評(píng)估自身能力和任務(wù)負(fù)載決定是否投標(biāo)。若自身不是優(yōu)先招標(biāo)方就繼續(xù)等待公示期管理者進(jìn)行標(biāo)書公示，合同者評(píng)估自身能力并計(jì)算任務(wù)執(zhí)行代價(jià)，從而決定是否參與競(jìng)爭(zhēng)投標(biāo)。為了防止優(yōu)先方搶占更多資源以及在獲得授權(quán)前未加節(jié)制地盲目投標(biāo)，造成投標(biāo)消息劇增和任務(wù)無法最優(yōu)執(zhí)行的情況出現(xiàn)，本文采用閾值限定的方式進(jìn)行限制，即當(dāng)合同者任務(wù)隊(duì)列中待執(zhí)行的任務(wù)小于閾值時(shí)合同者才可以繼續(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)行綜合評(píng)估并選擇最優(yōu)的合同者中標(biāo)，中標(biāo)合同者執(zhí)行中標(biāo)任務(wù)。分配任務(wù)的整個(gè)過程如下所示：

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

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

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

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

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

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

步驟7簽署合同。

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

5 實(shí)驗(yàn)驗(yàn)證

5.1 Matlab仿真實(shí)驗(yàn)

本文先使用Matlab進(jìn)行模擬仿真實(shí)驗(yàn)，設(shè)定任務(wù)數(shù)為10，實(shí)驗(yàn)結(jié)果如圖7和圖8所示。當(dāng)任務(wù)數(shù)為10時(shí)，機(jī)器人任務(wù)分配圖如圖7所示，由圖7可以看到利用傳統(tǒng)的合同網(wǎng)協(xié)議，2號(hào)機(jī)器人沒有被分配到任務(wù)，處于空閑狀態(tài)，而5號(hào)機(jī)器人分配路徑過長(zhǎng)，任務(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í)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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