曾慶山， 馮珊珊

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

0　引言

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

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

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

1.1　外部適應(yīng)度算法

外部能力適應(yīng)度的計(jì)算如下:

(1)

外部能力適應(yīng)度的歸一化處理方法,

(2)

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

1.2　正余切外部適應(yīng)度算法

正余切外部適應(yīng)度如下：

(3)

式中：Er為機(jī)器人的實(shí)際能力；Et為任務(wù)的實(shí)際需求能力.

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

2　改進(jìn)的外部適應(yīng)度

2.1　改進(jìn)外部能力適應(yīng)度

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

(4)

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

圖1　W=20時(shí)的適應(yīng)度值對(duì)比Fig.1　Fitness comparlson when W=20

圖2　W=50時(shí)的適應(yīng)度值對(duì)比Fig.2　Fitness comparlson when W=50

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

2.2　距離適應(yīng)度策略

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

圖3　機(jī)器人不合理的任務(wù)選擇Fig.3　The unreasonable task selection of robots

基于此，筆者在外部適應(yīng)度的結(jié)構(gòu)中加入了與機(jī)器人起止位置有關(guān)的距離適應(yīng)度函數(shù)，

(5)

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

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

Aij=Wn·Nij+Wf·Fdisij,

(6)

式中：Wn+Wf=1,0

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

(7)

Ei=Li/2,

(8)

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

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

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

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

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

已知：0

改進(jìn)前的能量消耗：

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

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

改進(jìn)后的能量消耗：

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　機(jī)器人和任務(wù)分布圖Fig.4　The distribution of robots and tasks

3　仿真試驗(yàn)

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

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

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

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

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

表3　執(zhí)行任務(wù)時(shí)間對(duì)比

從表3可以看出，T=3時(shí)，任務(wù)中沒(méi)有適應(yīng)度相同的任務(wù)，原始適應(yīng)度算法比正余切改進(jìn)的算法、筆者改進(jìn)的算法運(yùn)行時(shí)間都要長(zhǎng)；當(dāng)T=4 ～6時(shí)，任務(wù)中有一組會(huì)出現(xiàn)剛開始適應(yīng)度相同的情況，此時(shí)筆者改進(jìn)的算法運(yùn)行時(shí)間明顯小于原始算法和正余切改進(jìn)的算法，說(shuō)明改進(jìn)的算法有效且效率更高.

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

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

表4　原算法的能量消耗

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

表6　筆者改進(jìn)算法的能量消耗

4　結(jié)論

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

參考文獻(xiàn)：

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

[2]張崳,劉淑華. 多機(jī)器人任務(wù)分配的研究進(jìn)展[J]. 智能系統(tǒng)學(xué)報(bào),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]董煬斌,蔣靜坪. 基于適應(yīng)度的多機(jī)器人任務(wù)分配策略[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版),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]張萬(wàn)緒,馮曉海，趙江波，等. 改進(jìn)適應(yīng)度的異構(gòu)多機(jī)器人任務(wù)分配[J]. 西北工業(yè)大學(xué)(自然科學(xué)版),2013,43(1):22-26.

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

[8]韋兆文,區(qū)云鵬,閆俊燕. 一種改進(jìn)的動(dòng)態(tài)合同網(wǎng)協(xié)議[J].計(jì)算機(jī)工程與應(yīng)用,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.