RoboCup標準平臺組中基于改進合同網(wǎng)協(xié)議的任務分配算法*

梁志偉，吳海健

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

1 引言

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

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

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

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

2.1 問題描述

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

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

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

(1)

(2)

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

2.2 約束條件

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

(3)

(4)

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

3 任務分解以及行為任務樹模型

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

3.1 層次結構分解模型

本文建立多機器人系統(tǒng)任務分配的層次結構模型，模型第1層為根任務，第2層為總任務，第3層為角色層，第4層為各個角色的行為任務樹，如圖1所示。

Figure 1 Hierarchical model圖1 層次結構模型

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

3.2 行為任務樹模型

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

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

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

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

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

4.1 單個Agent模型

本文首先需要對Agent進行建模，單個Agent基本結構如圖3所示。

Figure 3 Basic structure of single Agent圖3 單個Agent基本結構

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

4.2 單個Agent控制過程

Agent的控制大致分為上線程、下線程、感知、運動和調試5個過程，如圖4所示。

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

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

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

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

(1)總任務為attack時，優(yōu)先級如表1所示。

Table 1 Priority comparison table(attack)

(2)總任務為defend時，優(yōu)先級如表2所示。

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

Table 2 Priority comparison table(defend)

4.4 評價函數(shù)

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

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

(5)

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

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

(6)

其中，Lgoal表示機器人與己方球門的橫向距離；η表示機器人的方向信息，當機器人朝向己方球門一側時η=1；當機器人朝向對方球門一側時η=0；k4和k5為權重系數(shù)。

4.5 任務分配算法

(1)管理者招標流程。

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

Figure 5 Flow chart of tendering algorithm 圖5 招標算法流程圖

(2)合同者投標流程。

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

Figure 6 Flow chart of bidding algorithm 圖6 投標算法流程圖

(3)任務分配過程。

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

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

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

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

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

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

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

步驟7簽署合同。

步驟8任務分配完成。

5 實驗驗證

5.1 Matlab仿真實驗

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

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

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

5.2 SimRobot仿真實驗

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

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

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

5.3 實體機器人驗證

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

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

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

Figure 11 Physical robot experiment圖11 實體機器人實驗

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

Figure 12 Robot behavior task tree圖12 機器人行為任務樹

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

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

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

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

除此之外，為了驗證任務分配在機器人防守端的效果，本文通過機器人5V5攻防賽對機器人防守端的任務分配效果進行驗證。機器人團隊的防守成功率如圖15所示。從圖15中可以看出，使用改進后的合同網(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 機器人團隊防守成功率

6 結束語

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