曾慶山， 馮珊珊

(鄭州大學 電氣工程學院，河南 鄭州 450001)

0　引言

多機器人協(xié)作策略是多機器人系統(tǒng)執(zhí)行任務的前提，也是系統(tǒng)執(zhí)行效率是否高效的關鍵，是組織簡單機器人完成復雜任務的核心.尤其近幾年云計算的興起，任務分配的相關算法在云調(diào)度[1]中也發(fā)揮了重要的作用，因此具有重要的研究價值.

目前，多機器人協(xié)作策略研究主要集中于3種方法[2]：市場機制、群體智能和建模法.在動態(tài)環(huán)境中，多機器人系統(tǒng)經(jīng)常面臨任務在不確定的時間和不斷變化的位置發(fā)布的問題[3].建模法最主要的優(yōu)點就是實時性強，尤其在這種動態(tài)情況下，能較快地針對環(huán)境做出合理高效的決策.董煬斌等[4]創(chuàng)建的基于適應度的多機器人協(xié)作策略，在針對動態(tài)松散多任務分配方面展現(xiàn)了較好的實時性和靈活性，且能夠在限制任務執(zhí)行優(yōu)先級、機器人能力有限[5]等情況下完成較優(yōu)的任務分配，仿真試驗表明，算法也具有較好的穩(wěn)定性.馮曉海等[6]通過對該算法的改進，使用正余切函數(shù)作為外部適應度函數(shù)，避免了原始函數(shù)中一直歸一化計算的問題，提高了機器人與任務之間適應度計算的穩(wěn)定性.

1　適應度協(xié)作策略及其不足

1.1　外部適應度算法

外部能力適應度的計算如下:

(1)

外部能力適應度的歸一化處理方法,

(2)

該算法很好地建立了任務的內(nèi)部狀態(tài)和外部聯(lián)系，在機器人選擇任務過程中，任務的內(nèi)部狀態(tài)即內(nèi)部適應度保持不變，不會因為機器人的不同而改變.這也說明，機器人選擇任務的關鍵在于它與任務的外部適應度，外部適應度的設置是否合理將直接影響到任務分配的效果.顯然，外部適應度過度依賴全局信息且頻繁進行歸一化的過程增加了系統(tǒng)的復雜度，降低了穩(wěn)定性.

1.2　正余切外部適應度算法

正余切外部適應度如下：

(3)

式中：Er為機器人的實際能力；Et為任務的實際需求能力.

改進的方法提高了算法的獨立性，但也存在一些不合理：改進的外部適應度在較符合能力要求的范圍內(nèi)適應度值下降較快，在遠超過能力的范圍內(nèi)適應度值保持較大值且下降緩慢.在計算適應度前，系統(tǒng)是有開關控制變量的，當機器人能力不足時，不進行適應度計算，它必須與其他機器人的能力進行加和、并操作后才能進行適應度的計算[7].在進行加和、并操作時，把能力不足時的適應度作為聯(lián)合的依據(jù)不能保證聯(lián)合的機器人組合與任務最優(yōu)匹配,因此，對機器人能力不足時的外部適應度計算是多余的.

2　改進的外部適應度

2.1　改進外部能力適應度

在機器人能力滿足任務需求時，計算能力適應度時，一般要求在較符合能力要求的范圍內(nèi)，能力適應度較大且區(qū)分明顯；在遠超出能力要求的范圍內(nèi)，能力適應度較小.為實現(xiàn)這一要求，筆者設計了基于高斯分布模型的外部能力適應度函數(shù)，如下式：

(4)

式中：L(i)為機器人Ri的實際能力水平；W(j)為任務Tj的實際能力需求.其仿真對比如圖1、2.

圖1　W=20時的適應度值對比Fig.1　Fitness comparlson when W=20

圖2　W=50時的適應度值對比Fig.2　Fitness comparlson when W=50

從圖1、2可以看出，在任務的能力需求是20(50)時，機器人在40(100)以內(nèi)的適應度要比反余切函數(shù)的大，超過40(100)以后，適應度迅速減小，比反余切函數(shù)要小得多，可以保證其它能力在任務選擇中占據(jù)主導，選擇任務的匹配度更高.算法的計算只與該任務的能力需求和當前機器人的能力有關，不受系統(tǒng)里其它因素的影響，確保算法的獨立性、穩(wěn)定性和可延拓性.

2.2　距離適應度策略

圖3為機器人不合理的任務選擇.如圖3所示，機器人起止位置異地，當A選擇任務1后，B對1、2兩個任務的適應度相同，按照原適應度算法的選擇原則，由于1任務的編號在前，則機器人B將選擇任務1，導致任務2漏選，從位置上看機器人B選擇任務2更合理.顯然，外部適應度如果只包含能力的匹配而不包含位置的匹配是不合理的，由此考慮加入機器人的代價[8].

圖3　機器人不合理的任務選擇Fig.3　The unreasonable task selection of robots

基于此，筆者在外部適應度的結構中加入了與機器人起止位置有關的距離適應度函數(shù)，

(5)

式中：Fdis為距離適應度；Ldis為任務空間的最大距離，一般在任務之前就已經(jīng)確定；RTdis(ij)為機器人Ri與任務Tj之間的距離.

外部適應度函數(shù)改為：

Aij=Wn·Nij+Wf·Fdisij,

(6)

式中：Wn+Wf=1,0

任務分配中，不僅涉及到任務執(zhí)行的時間效率，還要考慮機器人的能量消耗問題，只有這樣才能保證任務是最優(yōu)分配.為方便計算，給出多機器人執(zhí)行任務的能量消耗計算公式,

(7)

Ei=Li/2,

(8)

式中：E(i)為機器人Ri執(zhí)行完所有任務的能量消耗；Ei為機器人Ri每行走1 m消耗的能量，與機器人的能力水平Li相關，機器人能力水平越大，則單位消耗的能量越大；LTij為機器人Ri執(zhí)行任務Tj的行走路程.

改進后的算法與之前的算法相比有如下優(yōu)點.

①改進后，針對圖3中的問題，由于加入了距離適應度，使得機器人B對任務2的適應度更大，從而選擇出了更合理且更優(yōu)的任務.

②機器人起止位置異地.當機器人對任務的其他適應度相同時，機器人距離任務越近，則適應度越大.這樣，機器人可以縮短一次返回行走的距離，節(jié)約時間.尤其是在大規(guī)模的任務分配中，將大大減少執(zhí)行時間，如圖4所示.圖4中機器人A要將任務1、2送到倉庫1.改進前A的任務執(zhí)行順序為：A→1→倉庫1→2→倉庫1，則機器人A的行程為21.59 m；改進后A的執(zhí)行任務順序為：A→2→倉庫1→1→倉庫1，機器人A的行程為18.10 m，縮短了行程.

③機器人起止位置相同.當機器人對任務的其他適應度相等時，距離越遠的適應度越大.我們一般認為，當機器人與任務能力最匹配時達到資源的充分利用.因此，讓最優(yōu)匹配的機器人選擇更遠距離的任務，讓過匹配的機器人去執(zhí)行較近的，這樣，在總行走距離相等的情況下，總體節(jié)約了能量.如圖4，讓機器人B、C分別將任務1、2送到倉庫1.其中，B對兩任務的適應度相同且屬于最優(yōu)匹配，C對兩任務是屬于過匹配.改進前分配結果為：B→1，C→2；改進后分配結果為：B→2，C→1.根據(jù)公式(7)計算可知改進后更節(jié)省能量，證明如下.

已知：0

改進前的能量消耗：

E(B)=L(B)/2·LT1,E(C)=L(C)/2·LT2，

E1=L(B)/2·LT1+L(C)/2·LT2.

改進后的能量消耗：

E(B)=L(B)/2·LT2,E(C)=L(C)/2·LT1,

E2=L(B)/2·LT2+L(C)/2·LT1.

ΔE=E1-E2

=L(B)/2·LT1+L(C)/2·LT2-

(L(B)/2·LT2+L(C)/2·LT1)=

(L(B)-L(C))(LT1-LT2)/2>0.

證畢.

圖4　機器人和任務分布圖Fig.4　The distribution of robots and tasks

3　仿真試驗

以搬運任務進行驗證，在一個10×10 m的空間內(nèi)，配備有4個機器人，為進行對比仿真驗證，每個機器人的能力水平各不相同，機器人起始位置也不相同，任務的能力需求、位置、數(shù)量也各不相同，在執(zhí)行任務期間，機器人均以0.24 m/s的速度行進，仿真試驗分別對不同組合的任務進行分配和結果分析.

表1是機器人的初始參數(shù)，其中，Ri是機器人編號；RPosX、RPosY是機器人坐標；L是機器人能力水平；CKPos是倉庫位置.表2是任務的一些初始參數(shù)，Tj是任務編號；P是任務優(yōu)先級；I是子任務總量；Ic是子任務完成量；Ar是當前選擇本子任務的機器人數(shù)；Lup是允許機器人上限[9]；Ldn是允許機器人下限；W是任務能力需求；TPos是任務坐標.初始時，起止位置異地.內(nèi)部適應度參數(shù)設置為Ws=0，Wp=0.8,Wr=0.2，第一次任務選擇時，要保證機器人盡量選擇較近的任務，參數(shù)設置為：Wn=0.2,Wf=0.8，接下來的參數(shù)設置為Wn=0.5,Wf=0.5.

表1　機器人初始參數(shù)

表2　任務初始參數(shù)

針對此次試驗，我們假設不考慮機器人之間的避碰耗時，機器人在執(zhí)行任務中能力保持不變，機器人依次進行任務選擇.為了保證試驗的可靠性和嚴謹性，筆者特意設計了沒有適應度相同的情況和有兩個任務適應度相同位置不同的情況，這兩個任務分別是任務3和4.試驗分別以任務組合(1、2、3)，(1、2、3、4)，(1、2、3、4、5)，(1、2、3、4、5、6)進行4組仿真試驗.為了驗證試驗的有效性，試驗還分別用原始適應度算法、正余切改進的適應度算法進行了仿真試驗驗證,試驗結果如表3.

表3　執(zhí)行任務時間對比

從表3可以看出，T=3時，任務中沒有適應度相同的任務，原始適應度算法比正余切改進的算法、筆者改進的算法運行時間都要長；當T=4 ～6時，任務中有一組會出現(xiàn)剛開始適應度相同的情況，此時筆者改進的算法運行時間明顯小于原始算法和正余切改進的算法，說明改進的算法有效且效率更高.

根據(jù)仿真試驗，可以得到每個機器人的行走距離及能力大小，然后通過公式(7)可以計算出所有任務執(zhí)行結束后每個機器人的總能量消耗，3種方法的統(tǒng)計結果如表4～6所示.

由以上3組的能量計算可看出，筆者改進的算法能量消耗最低，即使在T=3時，正余切改進的算法和筆者算法執(zhí)行時間相差無幾，但能量消耗卻大于筆者改進的算法，由此證明筆者改進的算法也實現(xiàn)了能量的消耗最低.

表4　原算法的能量消耗

表5　正余切算法的能量消耗

表6　筆者改進算法的能量消耗

4　結論

主要研究了基于改進適應度的多機器人協(xié)作策略，針對適應度算法的外部能力匹配度不夠理想的問題，提出了高斯分布模型來計算機器人的能力匹配度.仿真表明,筆者算法更符合匹配度的要求，且保證了算法的獨立性與延拓性.針對出現(xiàn)適應度相同的任務時，機器人可能無法選擇出最合理任務的問題，通過加入與機器人起止位置有關的距離適應度，不僅解決了適應度相同時依次分配帶來的不合理，提高了算法分配合理性，而且任務的執(zhí)行效率也明顯提升，保證能量消耗最低，在松散多機器人環(huán)境中，該算法優(yōu)于改進前的算法.

參考文獻：

[1]王俊英,顏芬芬. 基于概率自適應蟻群算法的云任務調(diào)度方法[J]. 鄭州大學學報(工學版),2017,38(4):51-56.

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

[3]CHEN Y, MAO X J，HOU F，et al. Combining re-allocating and re-scheduling for dynamic multi-robot task allocation [C]∥IEEE Intermational Conference on Systems,Man,and Cybernetics.Budapest:IEEE,2016:000395-000400.

[4]董煬斌,蔣靜坪. 基于適應度的多機器人任務分配策略[J]. 浙江大學學報(工學版),2007,41(2):272-277.

[5]MITICHE H, BOUGHACI D,GINI M.Efficient heuristics for a time-extended multi-robot task allocation problem [C]∥International Conference on New Technologies of Information & Communication， 2015:1-6.

[6]張萬緒,馮曉海，趙江波，等. 改進適應度的異構多機器人任務分配[J]. 西北工業(yè)大學(自然科學版),2013,43(1):22-26.

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

[8]韋兆文,區(qū)云鵬,閆俊燕. 一種改進的動態(tài)合同網(wǎng)協(xié)議[J].計算機工程與應用,2007,43(36):208-211.

[9]LERMAN K, GALSTYAN A. A general methodology for mathematical analysis of multi-agent systems [R]. Los Angeles:USC information sciences technical report ISI-TR-529,2001.