基于聯(lián)合投標(biāo)的多目標(biāo)機器人圍捕

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

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

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

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

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

1 問題描述

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

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

2 拍賣算法

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

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

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

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

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

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

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

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

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

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

n=C26×C24P33=15

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

2.2 標(biāo)值的計算

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

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

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

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

圖1 角度示意圖

標(biāo)值的大小綜合這兩方面因素，d1，d2，d3越大，圍捕機器人的分布越不利于圍捕;標(biāo)值越大，120-θ1+120-θ2越大，圍捕機器人分布越不利于圍捕，標(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)機器人分配1個距離其較近的圍捕機器人，然后其他機器人采用聯(lián)合投標(biāo)的策略決定參加哪個目標(biāo)機器人的圍捕。

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

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

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

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

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

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

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

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

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

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

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

Step 7:返回到Step 2。

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

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

表1 圍捕成功和消耗時間

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

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

減少組合數(shù)目8814.2

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

圖2 一次圍捕過程截圖

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

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

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

4 結(jié) 論

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

參考文獻

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

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

[3]柳林，季秀才，鄭志強.基于市場法及能力分類的多機器人任務(wù)分配方法[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]姜健，臧希喆，趙杰.基于焦慮概念和拍賣方法的多機器人協(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)東，席裕庚.多機器人協(xié)作探索的改進市場法[J].控制與決策，2005，20(5):516-524.

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

[9]熊舉峰，譚冠政，皮劍.基于虛擬力的群機器人圍捕算法[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.