摘 要:針對多目標(biāo)機(jī)器人圍捕任務(wù)中的任務(wù)分配問題，提出了圍捕機(jī)器人聯(lián)合投標(biāo)的拍賣方法，該方法考慮圍捕機(jī)器人組合對任務(wù)的適應(yīng)程度，機(jī)器人聯(lián)合形成小組作為一個整體給任務(wù)投標(biāo)，并針對組合過多，計算量大，通信量大的問題對該方法進(jìn)行改進(jìn)。最后在MuRoS仿真平臺上對目標(biāo)機(jī)器人為3個，圍捕機(jī)器人為9個的情況進(jìn)行了仿真實驗，仿真結(jié)果顯示聯(lián)合投標(biāo)用于任務(wù)分配是可行的。

關(guān)鍵詞:多目標(biāo)機(jī)器人圍捕; 任務(wù)分配; 聯(lián)合投標(biāo); 拍賣

中圖分類號:TN919-34文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2010)21-0138-04

Multi-target Robots′Hunting Based on Combinatorial Bid

WANG Wen-xing， CHEN Yang-zhou， DAI Gui-ping

(College of Electronic Information and Control Engineering， Beijing University of Technology， Beijing 100124， China)

Abstract: A combinatorial bid method based on auction is presented to solve the task allocation in hunting of the multi-target robots. Taking the ability of combination between the robot hunters into account， the robots are taken as a group to bid for the task. The method is improved to avoid the excessive combination， too much calculation capacity and high communication traffic capacity. The simulation in which there are three preys and nine hunters are realized. The results show that the combinatorial bid for the task allocation is feasible.

Keywords: multi-target hunting; task allocation; combinatorial bid; auction

0 引 言

任務(wù)分配是多機(jī)器人系統(tǒng)協(xié)作[1]的一個關(guān)鍵環(huán)節(jié)，隨著機(jī)器人應(yīng)用環(huán)境復(fù)雜性的增加和系統(tǒng)規(guī)模的擴(kuò)大，任務(wù)分配尤其重要。目前使用較多的是拍賣算法[2]，拍賣算法根據(jù)經(jīng)濟(jì)市場中的拍賣來設(shè)計，其目的是為了實現(xiàn)資源的較優(yōu)分配。

基于拍賣的任務(wù)分配問題一般分為任務(wù)發(fā)布、投標(biāo)、任務(wù)分配三個階段[3]，拍賣算法將通信信息壓縮到標(biāo)，標(biāo)值反映了機(jī)器人對任務(wù)的適應(yīng)程度，通過投標(biāo)機(jī)制決定執(zhí)行任務(wù)的機(jī)器人，計算量小，通信量少[4]，具有靈活性，試圖在任務(wù)與機(jī)器人之間找到最佳分配。拍賣算法由Anthony Stentz最早提出，之后被廣泛用于搜尋[5]、空間探索[6-7]、編隊[8]等多機(jī)器人任務(wù)中。在拍賣的目標(biāo)之間可能出現(xiàn)增效時，Behauh提出了聯(lián)合拍賣的方法，投標(biāo)者給組合的目標(biāo)投標(biāo)，贏得組合的機(jī)器人贏得組合中的所有任務(wù)。

多目標(biāo)機(jī)器人圍捕任務(wù)是緊耦合任務(wù)，機(jī)器人之間需要緊密協(xié)作才能完成任務(wù)，單個機(jī)器人對任務(wù)的適應(yīng)程度往往依賴于其他的圍捕機(jī)器人。本文將圍捕機(jī)器人組成小組，以小組作為一個投標(biāo)者給任務(wù)投標(biāo)，標(biāo)值表示小組對任務(wù)的適應(yīng)程度，贏得任務(wù)的小組內(nèi)所有機(jī)器人共同完成該子任務(wù)，并且針對組合數(shù)過多導(dǎo)致計算量大的問題，減少參與形成組合的機(jī)器人數(shù)。仿真實驗顯示該方法是可行的。

1 問題描述

多機(jī)器人圍捕任務(wù)中，當(dāng)目標(biāo)機(jī)器人個數(shù)多于一個時，就需要確定選擇哪幾個圍捕機(jī)器人來圍捕它，怎樣選擇，這就是多目標(biāo)機(jī)器人圍捕的任務(wù)分配問題。本文研究多目標(biāo)機(jī)器人圍捕問題，圍捕機(jī)器人個數(shù)為9個，記為Ri(i=1，2，…，9)，目標(biāo)機(jī)器人個數(shù)為3個，記為Pi(i=1，2，3)，目標(biāo)機(jī)器人組成任務(wù)列表P={P1，P2，P3}。假定機(jī)器人在執(zhí)行圍捕任務(wù)中整個工作區(qū)為平面中的有界區(qū)域，形狀為矩形，各機(jī)器人為圓形，半徑為r，不考慮運動約束，可以向任意方向運動，位置和速度可以在瞬間變化。機(jī)器人間通過通信傳遞信息，實時地將自己的位置信息通過通信告知其他機(jī)器人，并根據(jù)被告知信息實時更新運動位置。

本文的研究重點是設(shè)計圍捕機(jī)器人投標(biāo)的策略及拍賣算法，給目標(biāo)機(jī)器人分配適合的圍捕機(jī)器人。任務(wù)分配完成后，圍捕機(jī)器人采用基于虛擬力的方法[9]對單個目標(biāo)實施圍捕。

2 拍賣算法

2.1 聯(lián)合投標(biāo)

圍捕任務(wù)中，圍捕機(jī)器人的運動目標(biāo)是對目標(biāo)機(jī)器人實施包圍，從幾何上看，即為圍捕機(jī)器人形成一個以目標(biāo)機(jī)器人為中心的正三角形。拍賣的方法選擇機(jī)器人執(zhí)行任務(wù)是根據(jù)標(biāo)值:機(jī)器人對任務(wù)的適應(yīng)程度為準(zhǔn)則。當(dāng)一個機(jī)器人給任務(wù)投標(biāo)時，其對任務(wù)的適應(yīng)程度只能依據(jù)其與目標(biāo)之間的距離，這樣選擇圍捕機(jī)器人可能會出現(xiàn)一種情況:選擇的3個圍捕機(jī)器人距離上離目標(biāo)較近，但是圍捕機(jī)器人的分布不利于圍捕，極端的情況是3個圍捕機(jī)器人的位置重合，并不是均勻分布在目標(biāo)機(jī)器人周圍，這種選擇顯然不適合。因此這種逐個招募圍捕機(jī)器人可能導(dǎo)致3個圍捕機(jī)器人在一起并不適合該圍捕任務(wù)。

一個機(jī)器人對任務(wù)的適應(yīng)程度是受其他機(jī)器人影響的，當(dāng)已知參與任務(wù)的另一個或另外兩個圍捕機(jī)器人的信息時，某一個圍捕機(jī)器人對任務(wù)的適應(yīng)程度是很好確定的。因此，可以將3個圍捕機(jī)器人聯(lián)合起來給任務(wù)投標(biāo)。與單個機(jī)器人投標(biāo)類似，任務(wù)分配分為三個階段:

(1) 拍賣者發(fā)布任務(wù);

(2) 每個組合根據(jù)其執(zhí)行指定任務(wù)的適合度對任務(wù)進(jìn)行投標(biāo);

(3) 拍賣機(jī)制決定將任務(wù)分配給哪個小組，小組內(nèi)的所有機(jī)器人共同完成該任務(wù)。

投標(biāo)者聯(lián)合起來形成小組投標(biāo)，組合的數(shù)目可能是投標(biāo)者的指數(shù)倍，因此遞交標(biāo)給每一目標(biāo)很耗時，標(biāo)值和選擇投標(biāo)者組合的計算量也很大。記各圍捕機(jī)器人組成的小組為集合:

S={s1，s2，s3，…，sn}

式中:n為圍捕機(jī)器人組成的集合個數(shù);si(i=1，2，…，n)為某三個圍捕機(jī)器人組成的集合。

文中圍捕機(jī)器人的個數(shù)為9個，可組成的小組數(shù)為1 280。如果1 280個小組給一個任務(wù)投標(biāo)，需要計算1 280個標(biāo)值，計算量較大，因此可以考慮先采用單個機(jī)器人投標(biāo)的方式，給每個目標(biāo)機(jī)器人分配1個距離其較近的圍捕機(jī)器人，剩下的機(jī)器人再聯(lián)合投標(biāo)。這樣給每個圍捕機(jī)器人分配一個圍捕機(jī)器人后，剩下6個圍捕機(jī)器人，可以組成的小組個數(shù)為:

n=C26×C24P33=15

另外，首先給每個目標(biāo)機(jī)器人分配1個圍捕機(jī)器人，不會有最后一個目標(biāo)機(jī)器人不能選擇圍捕機(jī)器人的情況，減少了陷入局部最優(yōu)的可能性。

2.2 標(biāo)值的計算

拍賣算法中，選擇哪些機(jī)器人執(zhí)行任務(wù)的選擇準(zhǔn)則是標(biāo)值的大小，標(biāo)值反映了機(jī)器人的局部信息，能完成任務(wù)的可能性，完成任務(wù)的消耗，完成任務(wù)需要的時間等諸多因素的綜合[10]，標(biāo)值的計算方法直接影響了任務(wù)分配的優(yōu)劣。不同的機(jī)器人任務(wù)中，標(biāo)值的計算有所不用。例如，在搜集任務(wù)中，標(biāo)值的計算與投標(biāo)機(jī)器人的載荷余量、目標(biāo)物的重量有關(guān)，在探索任務(wù)中，標(biāo)值的計算與機(jī)器人與目標(biāo)點之間的距離有關(guān)。

設(shè)計標(biāo)值的計算反應(yīng)一個小組對任務(wù)的適應(yīng)程度，包括兩個部分:

距離因素:各圍捕機(jī)器人與其目標(biāo)點間的距離分別為d1，d2，d3;

角度因素:圍捕過程中各機(jī)器人的位置如圖1所示，圍捕機(jī)器人與目標(biāo)機(jī)器人組成的兩個夾角為θ1，θ2，如圖1所示。

圖1 角度示意圖

標(biāo)值的大小綜合這兩方面因素，d1，d2，d3越大，圍捕機(jī)器人的分布越不利于圍捕;標(biāo)值越大，120-θ1+120-θ2越大，圍捕機(jī)器人分布越不利于圍捕，標(biāo)值應(yīng)該越大;反之，120-θ1+120-θ2越小，越利于圍捕，標(biāo)值應(yīng)該越小。因此，設(shè)計標(biāo)值的大小為:

b=d1+d2+d3+k(120-θ1+120-θ2)

式中:k為比例系數(shù)，為了防止120-θ1+120-θ2過小，標(biāo)值中不能反映角度的因素。

2.3 任務(wù)分配流程

對于動態(tài)環(huán)境，需要根據(jù)不同的情況采取不同的任務(wù)分配，資源和目標(biāo)得到重新分配[10]。圍捕任務(wù)中，限制圍捕者執(zhí)行分配任務(wù)的時間，執(zhí)行任務(wù)超過限制時間后，拍賣者更新目標(biāo)信息，舉行下一輪拍賣。每輪拍賣中，先給每個目標(biāo)機(jī)器人分配1個距離其較近的圍捕機(jī)器人，然后其他機(jī)器人采用聯(lián)合投標(biāo)的策略決定參加哪個目標(biāo)機(jī)器人的圍捕。

圍捕剛開始時，建立一個任務(wù)列表，投標(biāo)機(jī)器人列表和組合列表。任務(wù)列表包含所有的目標(biāo)機(jī)器人;投標(biāo)機(jī)器人列表包含所有的圍捕機(jī)器人(即投標(biāo)機(jī)器人);組合列表包含投標(biāo)機(jī)器人列表中機(jī)器人組成的組合。

任務(wù)分配過程中，列表是實時更新的:

(1) 因為1個機(jī)器人可能屬于不同的組合，當(dāng)一次拍賣中選擇某個機(jī)器人或者某個組合去執(zhí)行某一任務(wù)時，被選中機(jī)器人在下一次拍賣中不參加投標(biāo)，從投標(biāo)機(jī)器人列表中刪除該圍捕機(jī)器人，從組合列表中刪除包含這些圍捕機(jī)器人的組合。

(2) 當(dāng)1個目標(biāo)機(jī)器人被圍住時，防止其被釋放，該機(jī)器人以及圍捕它的圍捕機(jī)器人不參加下一輪的拍賣，從投標(biāo)機(jī)器人列表中刪除這些圍捕機(jī)器人，從任務(wù)列表中刪除該目標(biāo)機(jī)器人，并從組合列表中刪除包含這些圍捕機(jī)器人的組合。

任務(wù)發(fā)布采用逐個發(fā)布的方式，任務(wù)分配流程如下:

Step 1:當(dāng)圍捕開始時，各機(jī)器人位置隨機(jī)分布，列表初始化;

Step 2:任務(wù)列表中的任務(wù)投標(biāo)逐個招標(biāo)，投標(biāo)機(jī)器人列表中的機(jī)器人參加投標(biāo)，給每個任務(wù)選擇一個圍捕機(jī)器人，標(biāo)最小的機(jī)器人贏得任務(wù)，從投標(biāo)機(jī)器人列表中刪除被選中的機(jī)器人，從組合列表中刪除含有這些機(jī)器人的組合;

Step 3:任務(wù)列表中的任務(wù)投標(biāo)逐個招標(biāo)，組合列表里的組合投標(biāo)，給每個任務(wù)選擇一個組合，標(biāo)最小的組合贏得任務(wù)，從組合列表中刪除含有這些機(jī)器人的組合;

Step 4:所有圍捕機(jī)器人執(zhí)行任務(wù)一定時間;

Step 5:更新各機(jī)器人信息，判斷是否所有目標(biāo)機(jī)器人被圍住不能動，如果是，圍捕任務(wù)結(jié)束;否則轉(zhuǎn)Step 2;

Step 6:判斷是否有目標(biāo)機(jī)器人被圍住不能動，若有，列表初始化，然后從投標(biāo)機(jī)器人列表刪除完成此任務(wù)的圍捕機(jī)器人，并從組合列表中刪除包含這些圍捕機(jī)器人的組合;

Step 7:返回到Step 2。

3 仿真結(jié)果及分析

采用MuRoS(Multi Robot Simulator)仿真平臺進(jìn)行仿真實驗，仿真環(huán)境為1 000×600的平面，所有機(jī)器人在平面內(nèi)運動，仿真步長為0.1 s，每次仿真時間為圍捕開始到圍捕成功，仿真時間大于20 s時認(rèn)為圍捕不成功。實驗設(shè)計為每次實驗開始時隨機(jī)產(chǎn)生初始位置，目標(biāo)機(jī)器人與圍捕機(jī)器人的速度比是0.85。采用1 280個組合給任務(wù)投標(biāo)和前面介紹的減少組合數(shù)目的拍賣方法進(jìn)行試驗，兩種拍賣算法各進(jìn)行試驗50次，記錄圍捕成功消耗的時間，計算圍捕成功率，結(jié)果如表1所示。

表1 圍捕成功和消耗時間

圍捕成功率 /%圍捕使用平均時間 /s

采用聯(lián)合投標(biāo)9017.5

減少組合數(shù)目8814.2

一次圍捕過程截圖如圖2所示。

圖2 一次圍捕過程截圖

圖2(a)中，圍捕開始，界面中有9個圍捕機(jī)器人和3個目標(biāo)機(jī)器人，空心圓圈代表圍捕機(jī)器人，實心圓圈代表目標(biāo)機(jī)器人，各機(jī)器人位置隨機(jī)分布。圍捕過程中，各目標(biāo)機(jī)器人陸續(xù)被圍住，速度設(shè)為零，參加圍捕它的圍捕機(jī)器人速度也設(shè)為零，不參加之后的拍賣。

由表1可知，采用兩種方法圍捕成功率達(dá)到88%以上，說明任務(wù)分配是有效的，小部分圍捕失敗的原因為圍捕環(huán)境中機(jī)器人較多，死鎖幾率大大增加，導(dǎo)致圍捕不成功。圍捕過程時間消耗可能來自幾個方面:一方面是任務(wù)分配消耗時間;另一方面圍捕環(huán)境中機(jī)器人較多，機(jī)器人相互靠近的概率增大，運動規(guī)劃就要多考慮避障，圍捕機(jī)器人向目標(biāo)點運動行為的權(quán)重減小，增長了圍捕時間。

減少投標(biāo)組合后，圍捕使用平均時間減少，這與投標(biāo)組合由1 280個減少到15個的情況是符合的;另外所有機(jī)器人都形成組合投標(biāo)，可能第1個招標(biāo)的任務(wù)選擇了有利于任務(wù)完成的圍捕機(jī)器人，很快任務(wù)完成;最后1個招標(biāo)的機(jī)器人沒有選擇，被分到離目標(biāo)很遠(yuǎn)、位置分布也不利于圍捕的機(jī)器人，需要消耗較長時間才能圍捕成功，因此總體上看，圍捕耗時還是長的，減少組合數(shù)目使得最后1個招標(biāo)的任務(wù)也在每一輪拍賣開始時被分配了一個圍捕機(jī)器人，避免被分到完全不利于圍捕的機(jī)器人。

4 結(jié) 論

針對圍捕任務(wù)中各圍捕機(jī)器人協(xié)作關(guān)系緊密，機(jī)器人對任務(wù)的適應(yīng)程度依賴于其他機(jī)器人，提出機(jī)器人形成組合聯(lián)合投標(biāo)的拍賣方法，該方法能選擇適合任務(wù)的機(jī)器人，有效進(jìn)行任務(wù)分配。每輪拍賣開始時為每個任務(wù)先分配一個圍捕機(jī)器人，既大大減少了投標(biāo)組合的數(shù)目，也避免了最后發(fā)布標(biāo)書的任務(wù)沒有挑選圍捕機(jī)器人的余地。

參考文獻(xiàn)

[1]姚俊武，王建中.基于協(xié)商的多機(jī)器人協(xié)作決策方法研究[J].計算機(jī)應(yīng)用，2007(27):48-50.

[2]張崳，劉淑華.多機(jī)器人任務(wù)分配的研究與進(jìn)展[J].智能系統(tǒng)學(xué)報，2008，3(2):115-120.

[3]柳林，季秀才，鄭志強(qiáng).基于市場法及能力分類的多機(jī)器人任務(wù)分配方法[J].機(jī)器人，2006，28(3):337-343.

[4]MOSTEO Alejandro R， MONTANO Luis. Comparative experiments on optimization criteria and algorithms for auction based multi-robot task allocation[C]//2007 IEEE International Conference on Robotics and Automation Roma. Italy: IEEE， 2007:10-14.

[5]姜健，臧希喆，趙杰.基于焦慮概念和拍賣方法的多機(jī)器人協(xié)作搜集[J].控制與決策，2008，23(5):541-545.

[6]LAGOUDAKIS Michail G， MARKAKIS Evangelos， KEMPE David， et al. Auction-based multi-robot routing [C]//2009 IEEE International Conference on Robotics and Automation. USA: ICRA， 2009:958-963.

[7]張飛，陳衛(wèi)東，席裕庚.多機(jī)器人協(xié)作探索的改進(jìn)市場法[J].控制與決策，2005，20(5):516-524.

[8]楊帆，劉士榮.基于競標(biāo)機(jī)制的多移動機(jī)器人實時編隊控制[J].華東理工大學(xué)學(xué)報，2010，36(1):113-118.

[9]熊舉峰，譚冠政，皮劍.基于虛擬力的群機(jī)器人圍捕算法[J].計算機(jī)工程與應(yīng)用，2008，44(25):48-51.

[10]SUN Wei. Task allocation for multi-robot cooperative hunting behavior based on improved auction algorithm[C]//Proceedings of the 27th Chinese Control Conference. China: CCC， 2008: 435-440.