基于效用函數(shù)的多機器人系統(tǒng)任務(wù)分配

(廣東工業(yè)大學(xué) 自動化學(xué)院， 廣州 510090）



摘 要：目前所采用的多機器人系統(tǒng)任務(wù)分配方法大多都忽略了任務(wù)分配的解質(zhì)量問題。從定量的角度出發(fā)，提出了一種基于效用函數(shù)的多機器人系統(tǒng)任務(wù)分配策略，在機器人能力向量和子任務(wù)要求的能力向量基礎(chǔ)上，建立了效用函數(shù)的數(shù)學(xué)模型，根據(jù)效用函數(shù)大小進行任務(wù)分配。仿真實驗在足球機器人仿真比賽平臺上進行，結(jié)果表明該任務(wù)分配算法對異構(gòu)多機器人系統(tǒng)合作具有很好的通用性，且算法快速簡單，能夠?qū)崿F(xiàn)任務(wù)到機器人的最優(yōu)映射。

關(guān)鍵詞：效用函數(shù)；多機器人系統(tǒng)；任務(wù)分配

中圖分類號：TP24 文獻標(biāo)志碼：A

文章編號：10013695(2009)02053703



Utilitybased task allocation for multirobot system



LI Ping，YANG Yimin，LIAN Jiale

(Institute of Automation， Guangdong University of Technology， Guangzhou 510090， China)

Abstract:The solution qualities have been ignored by most algorithms for task allocation in multirobot system so far.This paper brought forward a task allocation strategy based on utility function.Used the utility to measure the solution quality quantificationally， in order to guiding the task allocation in multirobot system.Constructed it based on capacity vectors of robots’ and demanding in tasks，allocated tasks depending on the utility matrix.And illustrated the feasibility of this task allocation algorithm in the simulation experiment of robot soccer.This task allocation algorithm is simple and rapidly， it is also generalpurposed to heterogeneous robots.

Key words:utility; multirobot system(MRS); task allocation

多機器人系統(tǒng)(MRS)中研究的核心問題是多機器人的合作。任務(wù)分配屬于多機器人合作問題，其目的就是尋找一個最合理的子任務(wù)分配方案，以達到提高效率、節(jié)約成本、合理配置資源或整體效用最優(yōu)等系統(tǒng)總目標(biāo)[1]。任務(wù)分配體現(xiàn)了系統(tǒng)高層的組織形式與運行機制，是多機器人系統(tǒng)實現(xiàn)目標(biāo)的基礎(chǔ)，在很大程度上決定了系統(tǒng)的工作效率。多機器人任務(wù)分配主要基于協(xié)商主義和行為主義兩種思想。在基于協(xié)商主義的任務(wù)分配中，多機器人系統(tǒng)在某些協(xié)議基礎(chǔ)上通過機器人之間的相互協(xié)商、談判來完成任務(wù)分配，其優(yōu)點是能夠?qū)崿F(xiàn)全局最優(yōu)任務(wù)分配；缺點是任務(wù)分配的過程耗時太長。協(xié)商主義的典型代表是合同網(wǎng)法。近年來，基于合同網(wǎng)的任務(wù)分配方法得到了廣泛的應(yīng)用，如R. Zlot等人[2，3]采用面向任務(wù)樹的競價拍賣合同網(wǎng)法分配一類松耦合子任務(wù)，取得了較好的效果；周浦城等人[4]從利用經(jīng)驗縮小任務(wù)招標(biāo)范圍，以及引入信心度、信譽和任務(wù)熟悉程度作為輔助決策因素構(gòu)成輔助決策矩陣改善聯(lián)盟決策兩方面對傳統(tǒng)的合同網(wǎng)協(xié)議進行了改進?；谛袨橹髁x的任務(wù)分配的主要特點是任務(wù)分配過程的實時性和魯棒性好，但任務(wù)分配方案只能達到局部最優(yōu)?；谛袨榈亩鄼C器人分布式合作結(jié)構(gòu)[5]以及具有相應(yīng)參數(shù)學(xué)習(xí)能力的系統(tǒng)LALLIANCE[6]，采用基于閾值的任務(wù)分配，具有較強的容錯能力、自適應(yīng)能力和可靠性。本文提出了一種基于效用函數(shù)的多機人系統(tǒng)任務(wù)分配策略，建立了效用函數(shù)數(shù)學(xué)模型，通過該模型來指導(dǎo)多機器人系統(tǒng)的任務(wù)分配。

1 任務(wù)分配的基本策略

假定全局任務(wù)M={t1，t2，…，tj，…，tn}由n個子任務(wù)組成，多機器人系統(tǒng)R={r1，r2，…，ri，…，rm}包含m個機器人，現(xiàn)要求由多機器人系統(tǒng)R完成全局任務(wù)M，ρ為將子任務(wù)分配給機器人系統(tǒng)的方案集。為了保證系統(tǒng)具有較高的性能，多機器人系統(tǒng)R的任務(wù)分配必須實現(xiàn)最優(yōu)的子任務(wù)到機器人的映射。不同的任務(wù)對機器人的要求不同，機器人選擇不同的任務(wù)產(chǎn)生的效用不同，因此給每個機器人分配與其能力相匹配的子任務(wù)可以提高系統(tǒng)性能。

2 基于效用函數(shù)的任務(wù)分配 

定義 若實值函數(shù)值uj(1≤j≤n)的大小表征機器人對子任務(wù)tj的勝任程度，稱函數(shù)uj為子任務(wù)tj的效用函數(shù)，uj(i)(1≤i≤m)表示機器人ri對子任務(wù)tj的勝任程度，uj(i)越大表示ri能更好地完成tj。

機器人對子任務(wù)的勝任程度用效用來量度，效用就是勝任程度的量化。效用函數(shù)代表當(dāng)前情況下，機器人執(zhí)行子任務(wù)的合適程度，機器人ri對子任務(wù)tj的執(zhí)行能力越強，其對tj的效用值也越大。為了使全局性能達到帕累托最優(yōu)，進行任務(wù)分配的目標(biāo)就是使全局的效用函數(shù)之和最大。令θ*j=arg max uj(i)，進行多機器人系統(tǒng)任務(wù)分配使系統(tǒng)耗時或耗能最少，這就要求每一個子任務(wù)都分配給最合適它的機器人，即將子任務(wù)tj分配給效用函數(shù)uj(i)最大的機器人θ*j。

本文采用關(guān)于機器人能力、子任務(wù)要求的能力函數(shù)來表征機器人勝任任務(wù)的程度，效用函數(shù)uj=Uj(C)，其中C為子任務(wù)分配涉及的能力。多機器人系統(tǒng)任務(wù)分配所涉及的只是機器人的執(zhí)行能力，如移動、探測及處理能力等。將這些能力分類細(xì)化成簡單的原子能力，并將所有這些原子能力組成能力集合。假設(shè)由k個原子能力cα組成的能力集合為C={cα}，1≤α≤k。

2.1 機器人和任務(wù)的能力描述

設(shè)子任務(wù)tj對傳感和執(zhí)行能力的需求強度Wtj={wtj1，

wtj2，…，wtjk}。其中：0≤wtjα≤1.0，α=1，2，…，k。第α項功能cα對子任務(wù)的影響越大則wtjα越大。定義子任務(wù)tj要求的能力向量為

Ctj=CTWtj=[c1wtj1，c2wtj2，…，ckwtjk] (1)

設(shè)機器人ri的傳感和執(zhí)行能力水平Wri={wri1，wri2，…，wrik}。其中0≤wriα≤1.0，α=1，2，…，k。機器人具備第α項功能cα越強則wriα越大。定義ri的能力向量為

Cri=CTWri=[c1wri1，c2wri2，…，ckwrik] (2)

2.2 效用函數(shù)模型

1)機器人完成任務(wù)的能力條件

在給機器人分配任務(wù)時，首先要判斷機器人是否具備子任務(wù)要求的能力。采用函數(shù)vij表示機器人ri是否具備完成子任務(wù)tj的能力，其表達式為

vij=1 if

wriα-

wtjα≥0 α，1≤α≤k

0 else(3)

只有vij=1，ri才能夠獨自完成子任務(wù)tj。然而要優(yōu)化整個系統(tǒng)的性能，不僅要滿足這個前提條件，還要量化機器人勝任子任務(wù)的程度，采用明確的標(biāo)度度量任務(wù)分配的后果。

2)勝任程度的量化

若vij=0，機器人ri不能獨自完成子任務(wù)tj，uj(i)=0。對滿足vij=1這一前提條件的情況，還需要計算效用函數(shù)來量化任務(wù)分配的后果。隨著環(huán)境的變化，任務(wù)要求的能力和機器人的能力都隨之改變，各機器人對子任務(wù)的勝任程度也相應(yīng)變化。機器人ri對子任務(wù)tj的效用函數(shù)為uj(i)是一個關(guān)于當(dāng)前任務(wù)要求能力、機器人能力的函數(shù)。效用函數(shù)的完全表達式為

uj(i)=Uj(Cri，Ctj) vij=1

0vij=0 (4)

由于不同的子任務(wù)對機器人的要求不同，不同子任務(wù)對應(yīng)的效用函數(shù)也不同，即對tk≠tj，Uk(#8226;)≠Uj(#8226;)。為了使uj(i)與uk(i)具有可加性，需要對它們進行歸一化處理：

j(i)=uj(i)/mi=1uj(i) (5)

由此獲得效用函數(shù)矩陣：

U=[U1U2… Un]=

u1

u2



um=u11u12…u1nu21u22…u2n



um1um2…umn(6)

式中：uij=j(i)。

對同一子任務(wù)而言，效用函數(shù)值越大，在當(dāng)前狀態(tài)下，機器人對子任務(wù)的執(zhí)行能力越強，越能勝任該子任務(wù)。進行多機器人系統(tǒng)任務(wù)分配就是在效用函數(shù)矩陣U中，選擇m個不同行同列的元素，求解

maxnj=1uθj j，1≤h，l≤n，h≠l，θh≠θl(7)

的最大值，對應(yīng)獲得的{θ1，θ2，…，θn}就是帕雷托最優(yōu)任務(wù)分配方案[7]。

對全局任務(wù)M進行分解時，將全局任務(wù)分解成與機器人個數(shù)相等的m個、能力要求小于機器人最高能力配備(wriα=1，α=1，2，…，k)的子任務(wù)(任務(wù)分配的最簡單情況)，保證每個子任務(wù)都能由單個機器人完成，而且每一時刻每個機器人只執(zhí)行一項子任務(wù)，則矩陣U中有m2個元素。為每個機器人分配一個子任務(wù)(每行選一個元素，m個元素在不同列)有m!種不同的分配方案，求解矩陣U中m個不同行不同列的元素之和最大的排列，得到最佳的任務(wù)分配方案。當(dāng)m比較小時，可以直接采用單純形法求解；當(dāng)m較大時，求解最優(yōu)分配方案就變得難以處理了，可以嘗試采用遺傳算法對空間進行搜索。本文僅考慮m較小的情況。

2.3 任務(wù)分配算法

根據(jù)基于效用函數(shù)的任務(wù)分配策略，提出了一種多機器人系統(tǒng)任務(wù)分配算法，該算法可以用于采用集中式體系結(jié)構(gòu)的多機器人系統(tǒng)中，也可用于分布式多機器人系統(tǒng)中。采用集中式時，由系統(tǒng)中的一個機器人計算每個機器人對每個子任務(wù)的效用函數(shù)uij，并為每個機器人分配任務(wù)，使得全局效用函數(shù)之和（式(7)）最大。采用分布式時，隨機確定一個leader，每個機器人計算自身的效用函數(shù)向量ui并把它發(fā)送給當(dāng)前的leader，由leader獲得效用函數(shù)矩陣，為每個機器人分配任務(wù)，使得全局效用函數(shù)之和最大。該算法考慮了機器人能力、子任務(wù)要求的能力對效用函數(shù)的影響，使得機器人的功能結(jié)構(gòu)不再是影響任務(wù)分配的重要因素，算法對異構(gòu)機器人系統(tǒng)具有較好的通用性；也充分考慮到環(huán)境因素對機器人能力、子任務(wù)要求能力的影響，因此總能給ri分配當(dāng)前環(huán)境下合適的子任務(wù)，使得全局效用值最大，適合動態(tài)環(huán)境。假定機器人ri在t=hT時刻進行任務(wù)分配，集中式任務(wù)分配算法的偽代碼如下：

decomposes mission M into a set of subtasks{t1，t2，…，tm}，and initializes Wtj for every tj，1≤j≤m

initializes vij=0，uij=0，for 1≤j≤m，1≤i≤m

updates，Wri，Wtj

for(i=1;i++;i≤m)

for(j=1;j++;j≤m)

vij=1 if wrix-wtjx≥0 x，1≤x≤k

0 else

uj(i)=Uj(Cri，Ctj) vij=1

0vij=0

for(i=1，i++;i≤m)

for(j=1，j++;j≤m)

uij=uj(i)/mi=1uj(i) 

for(1≤j≤n)

θj=arg maxnj=1uθj j，h≠l，θh≠θl

send message about j to θj，then θj takes tj as its task

3 仿真實驗與分析

仿真實驗在多機器人足球仿真比賽平臺上進行，設(shè)定比賽基于全局視覺。系統(tǒng)包含R={r1，r2，r3}，M被分解成三個簡單子任務(wù){(diào)t1，t2，t3}(任務(wù)分解另文介紹)，其中依據(jù)球是否能被踢到，獲得t1的機器人有兩種不同的角色：截球球員或傳球員。當(dāng)球不能被踢到時，獲得t1的機器人就為截球員，它的任務(wù)就是攔截足球，獲得足球的控制權(quán)；否則，它的任務(wù)就是找到合適的時機將球傳給獲得t2的機器人，獲得t3的機器人則被動配合執(zhí)行任務(wù)。

每個機器人和子任務(wù)都具有一個對應(yīng)的能力向量，根據(jù)需要事先在一個數(shù)據(jù)庫中設(shè)置這些向量的取值。定義機器人和子任務(wù)需求的能力包括視覺能力、移動能力及探測能力。在實驗過程中，比賽基于全局視覺，且傳感器均工作正常。效用函數(shù)值主要取決于機器人的移動能力，表現(xiàn)為機器人運動的快慢和機器人離目標(biāo)的遠近。

設(shè)子任務(wù)需要的能力都在每個機器人的能力范圍之內(nèi)，即vij=1(i，j=1，2，3)，每個機器人都能獨立完成其中的每一項任務(wù)。

設(shè)ui1=U1(Cri，Ct1)=1/timei。其中機器人ri截到球的時間timei=si/vi，si為ri和球從時刻t到第一次相遇所走過的路程，這里所涉及的能力包括機器人的位置和角度、運動速度及方向、球的位置、運動速度及方向等。設(shè)

ui2=U2(Cri，Ct2)=1/max(1，dig)+1 if dib＜λ

1/max(1，dig)otherwise

其中:dig和dib分別為機器人ri到對方球門的距離和球的距離，由機器人位姿及球的位置計算獲得；λ=20為機器人ri以最大速度踢球時，球的最大行走距離，在這個范圍內(nèi)的機器人更有機會獲得t2。

設(shè)每個機器人獲得t3的效用值u3(i)=1/3（i=1，2，3），它們在沒有獲得其他子任務(wù)時，自動獲得子任務(wù)t3。比賽場景如圖1所示，圖中機器人r1離球最近，最有可能截獲球的控制權(quán)，應(yīng)承擔(dān)子任務(wù)t1；而r2距離r1不遠，且更靠近目標(biāo)球門，它應(yīng)承擔(dān)子任務(wù)t2；剩下的r3自動獲得t3。

與圖1對應(yīng)的效用函數(shù)矩陣為

0.450 2360.333 5120.333 333

0.360 1890.333 4400.333 333

0.189 5750.333 0490.333 333

采用本文提出的任務(wù)分配算法，最后任務(wù)分配結(jié)果為(1，2，3)，子任務(wù)t1，t2，t3分別分配給r1，r2，r3，這樣獲得juθjj=1.117 009為圖中當(dāng)前時刻的最大全局效用函數(shù)值。雖然u12＞u22，但是從整體看將任務(wù)t2分配給r2全局效用最大，分配結(jié)果與分析一致。實驗結(jié)果表明了模型的合理性和算法的有效性。如2.2節(jié)所述，該任務(wù)分配算法對異構(gòu)多機器人系統(tǒng)的合作具有很好的通用性，且充分考慮了環(huán)境的變化，適應(yīng)于動態(tài)環(huán)境。

為了比較本文獲得的效用函數(shù)之和最大對應(yīng)的方案與其他方案的優(yōu)劣，在仿真足球機器人系統(tǒng)中，設(shè)定相同的初始狀態(tài)，對三個機器人、三個角色(對應(yīng)任務(wù))情況下的六種分配方案分別進行了10次實驗，要求系統(tǒng)完成任務(wù)越快越好。取任務(wù)執(zhí)行時間的平均值作為分配方案優(yōu)劣的評價標(biāo)準(zhǔn)，任務(wù)執(zhí)行時間短的分配方案優(yōu)。任務(wù)執(zhí)行時間為任務(wù)分配結(jié)束到截球員獲得球并將球傳給接球員或球被踢進門所需要的時間。六種分配方案的效用值和耗時分別如圖2、3所示。

從圖2和3可以看到，隨著效用函數(shù)值的增加，實際的平均耗時減少，效用函數(shù)值越大，耗時越少，方案越優(yōu)，證明本文構(gòu)建的效用函數(shù)模型具有效用值越大對應(yīng)方案越優(yōu)的性質(zhì)，能夠有效應(yīng)用于多機器人系統(tǒng)任務(wù)分配。

在集中式任務(wù)分配中，當(dāng)機器人和任務(wù)均為m個時，算法的計算復(fù)雜性為O(m2+m!)，通信復(fù)雜性為O(m)。在分布式任務(wù)分配中，各機器人計算各自的效用函數(shù)向量ui，由leader分配任務(wù)，計算復(fù)雜性為O(m2+m!)，通信復(fù)雜性為O(m)。對較小的系統(tǒng)，算法快速簡單且能夠獲得全局最優(yōu)分配方案；當(dāng)系統(tǒng)比較大時，需采用智能方法對任務(wù)分配解空間進行搜索。本文僅考慮機器人數(shù)和任務(wù)數(shù)相等且比較少的情況。

4 結(jié)束語 

本文引入了機器人效用函數(shù)的概念，提出了一種基于效用函數(shù)的多機人系統(tǒng)任務(wù)分配策略，建立了一個效用函數(shù)的數(shù)學(xué)模型，通過該模型來指導(dǎo)多機器人系統(tǒng)的任務(wù)分配。算法適應(yīng)于集中式和分布式任務(wù)分配，仿真實驗表明了算法的有效性，算法快速簡單且能獲得全局最優(yōu)分配方案，還能擴展到機器人數(shù)量和任務(wù)數(shù)量不等的情況。然而算法僅適應(yīng)于較小系統(tǒng)，算法的求解復(fù)雜性隨機器人數(shù)和子任務(wù)數(shù)呈階乘增長，且本文僅考慮機器人能夠獨立完成的簡單任務(wù)分配問題，對不能再分的、需要多個機器人聯(lián)合執(zhí)行的任務(wù)未作討論。今后，要對以下幾個方面進行研究：

a)將機器人的信用值加入到效用函數(shù)模型中；

b)嘗試用完全分布的任務(wù)分配方式，在不降低解質(zhì)量的前提下簡化任務(wù)分配，降低任務(wù)分配的求解復(fù)雜性，研究在完全分布式的情況下如何分配任務(wù)，獲得全局最優(yōu)的任務(wù)分配方案；

c)嘗試采用智能搜索方法求解較大多機器人系統(tǒng)的任務(wù)分配方案；

d)解除系統(tǒng)對通信的依賴性，研究在通信失效時的任務(wù)分配，提高系統(tǒng)的適應(yīng)性；

e)討論不能再分的需要多個機器人聯(lián)合完成的復(fù)雜任務(wù)的分配。

參考文獻：

［1］

韓泉葉，王松，黨建武.競爭環(huán)境下任務(wù)分配方法的研究[J].計算機工程與設(shè)計，2007，28(3):517519.

[2]ZLOT R，STENTZ A.Marketbased multirobot coordination for complex tasks[J].International Journal of Robotics Research，2006，25(1):73101.

[3]ZLOT R，STENTZ A.Complex task allocation for multiple robots[C]//Proc of IEEE International Conference on Robotics and Automation.2005:15151522.

[4]周浦城，洪炳镕，王月海.動態(tài)環(huán)境下多機器人合作追捕研究[J].機器人，2005，27(4):289299.

[5]PARKER L E.ALLIANCE:an architecture for faulttolerant multirobot cooperation[J].IEEE Trans on Robotics and Automation，1998，14(2):220240.

[6]PARKER L E.LALLIANCE:taskoriented multirobot learning in beha-viorbased systems [J].Advanced Robotcis，1997，11(4):305322.

[7]岳超源.決策理論與方法[M].北京:科學(xué)出版社，2003.