么立雙，蘇麗穎，李小鵬

（北京工業(yè)大學(xué) 機電學(xué)院，北京 100124）

0 引言

面對復(fù)雜的環(huán)境與任務(wù)，與單機器人相比，多機器人系統(tǒng)具有許多優(yōu)越性：完成任務(wù)效率高、完成任務(wù)復(fù)雜程度高、信息傳遞速度快、定位信息準(zhǔn)確、系統(tǒng)魯棒性好以及優(yōu)化解決問題方案。

著名多機器人系統(tǒng)研究專家Lynne E。Parker從七個方面總結(jié)了多機器人系統(tǒng)領(lǐng)域的主要研究內(nèi)容及亟待解決的問題[1,2]。這七個方面包括：任務(wù)分配、動作選擇、協(xié)調(diào)及控制結(jié)構(gòu)；物體運輸、操作及構(gòu)建；通信及感知；運動協(xié)調(diào)；學(xué)習(xí)；可重構(gòu)及可建模機器人；協(xié)作定位及地圖構(gòu)建。多機器人系統(tǒng)在完成復(fù)雜環(huán)境探索任務(wù)時，合理選擇任務(wù)分配機制能大大提高環(huán)境探索的效率，是機器人建立環(huán)境及完成各種復(fù)雜智能任務(wù)的關(guān)鍵，在實際應(yīng)用中具有重要意義。協(xié)作定位及地圖構(gòu)建是路徑規(guī)劃、完成復(fù)雜環(huán)境探索任務(wù)的基礎(chǔ)。動作選擇等研究領(lǐng)域是多機器人系統(tǒng)的自動化和智能化的重要標(biāo)志。因此，對整個多機器人系統(tǒng)來講，在協(xié)作探索未知環(huán)境的過程中，任務(wù)分配問題是優(yōu)化多機器人系統(tǒng)能效的一個重要環(huán)節(jié)，如何提高任務(wù)分配效率是多機器人任務(wù)分配研究的關(guān)鍵問題[3,4]。

1 多機器人系統(tǒng)任務(wù)分配的問題描述

要使多個機器人共同完成一項任務(wù)，首先就要解決該項任務(wù)的分解、分配、以及資源的利用等問題。多機器人任務(wù)分配問題（MRTA）可定義為：給定一個多機器人系統(tǒng)、一個任務(wù)集合以及系統(tǒng)性能評價指標(biāo)，為每個子任務(wù)尋找一臺合適的機器人負責(zé)執(zhí)行該子任務(wù)，且使得機器人系統(tǒng)執(zhí)行完任務(wù)集合中的全部任務(wù)時所獲得的受益達到最大。任務(wù)分配問題是機器人協(xié)作的一個關(guān)鍵問題，它直接影響到機器人之間是否會發(fā)生任務(wù)沖突、空間沖突以及沖突的程度，直接影響到多機器人系統(tǒng)完成任務(wù)的效率。

在靜態(tài)環(huán)境中，機器人要探索的環(huán)境信息固定，且信息量相對較少，各機器人之間通信內(nèi)容以子任務(wù)信息和靜態(tài)環(huán)境信息為主。如果以系統(tǒng)完成全部偵察任務(wù)所需要移動的路徑總長度作為評價分配的最優(yōu)指標(biāo)，那么多機器人協(xié)同偵察多個目標(biāo)點的任務(wù)分配問題可歸結(jié)為求解一般形式（各移動體的起點、終點不一定相同）的多旅行商問題[5]（MTSP）。多旅行商問題作為一個純數(shù)學(xué)問題難度大、復(fù)雜程度高。通常只針對多旅行商問題的傳統(tǒng)形式——旅行商問題（TSP）進行討論。

在動態(tài)環(huán)境中，由著名學(xué)者Brian和Mataric首先提出了動態(tài)任務(wù)分配問題[6]。該問題可描述為：多機器人系統(tǒng)不確定任務(wù)出現(xiàn)的時間和空間位置，且工作環(huán)境具有動態(tài)不確定性和不完整性等，此時機器人探測任務(wù)的分配問題更為復(fù)雜。1）各機器人之間的通信內(nèi)容不但有子任務(wù)信息，還包括實時變化的動態(tài)環(huán)境信息，這就給機器人之間的通信帶來了一個通信瓶頸問題。合理選擇任務(wù)分配機制，能有效緩解帶寬壓力，降低通信代價，提高探索動態(tài)環(huán)境的效率。2）任何一個機器人隨時都有可能遇到突發(fā)狀況，在總?cè)蝿?wù)集合不變的條件下，分配到該機器人的子任務(wù)要根據(jù)環(huán)境的變化實現(xiàn)實時改變，這就要求任務(wù)分配機制具備實時更新子任務(wù)的能力。

無論靜態(tài)環(huán)境，還是動態(tài)環(huán)境多機器人任務(wù)分配的環(huán)境都具有以下特點：機器人在執(zhí)行任務(wù)的過程中發(fā)現(xiàn)新任務(wù)，即任務(wù)分配是一種動態(tài)任務(wù)分配過程；機器人所執(zhí)行的任務(wù)具有優(yōu)先級差別；任務(wù)的分布具有資源聚集區(qū)的特征。

2 任務(wù)分配機制的主要類型

任務(wù)分配機制與系統(tǒng)的協(xié)作與協(xié)調(diào)機制、組織結(jié)構(gòu)、通訊機制、感知及學(xué)習(xí)等多方面的因素相關(guān)，任務(wù)分配問題具有多方面的屬性特征，可根據(jù)不同屬性需要從不同方面劃分任務(wù)分配問題的類型[7,8]。

根據(jù)多機器人系統(tǒng)結(jié)構(gòu)中有無中央控制機器人，可將多機器人系統(tǒng)任務(wù)分配機制分為集中式任務(wù)分配機制和分布式任務(wù)分配機制。靜態(tài)環(huán)境中，采用集中式任務(wù)分配機制，可得到任務(wù)分配的最優(yōu)解。而對于動態(tài)環(huán)境，每個機器人所需探測的環(huán)境信息量及機器人之間通信量大大增加，集中式任務(wù)分配機制不再適合該情況，因此可采用分布式任務(wù)分配機制。

2.1 集中式任務(wù)分配機制

2.1.1 集中式任務(wù)分配方法的一般式

在多機器人任務(wù)分配發(fā)展最初階段，大多采用集中式任務(wù)分配機制。在該機制中，有一個中央控制機器人，它主要負責(zé)收集環(huán)境信息，并將任務(wù)分割成多個子任務(wù)，然后分配給各個機器人。

Burgard、Simmons[9,10]等提出一種基于邊界的集中式任務(wù)分配機制的協(xié)作探測方法。該方法中首先設(shè)置一個負責(zé)收集地圖信息與合成全局地圖的中央機器人。然后，在全局地圖上找出邊界并確定目標(biāo)點，通過集中式算法可以得到使得總體花費最小的分配方案。最后將任務(wù)分配結(jié)果下達給各個機器人。如此不斷更新地圖信息直至全局地圖能夠覆蓋整個探索區(qū)域。利用該方法可得到全局最優(yōu)分配結(jié)果，但中央機器人承擔(dān)復(fù)雜計算量和通信量，且魯棒性差。

集中式任務(wù)分配機制實現(xiàn)了機器人個體之間運動的緊密協(xié)調(diào)和最優(yōu)協(xié)調(diào)，但是也存在以下缺點：在任務(wù)分配時，該機制以犧牲中央機器人自主性為代價；在執(zhí)行任務(wù)過程中，中央機器人一旦出現(xiàn)故障，要求系統(tǒng)必須立即重新設(shè)置一個新的中央機器人，否則整個機器人群體可靠性將無法得到保障。不能充分體現(xiàn)多機器人系統(tǒng)的魯棒性好的特點。當(dāng)多機器人系統(tǒng)內(nèi)機器人數(shù)量越多時，系統(tǒng)性能就越低，其容錯性也就越差。

2.1.2 基于蟻群法的任務(wù)分配方式

為解決集中式任務(wù)分配機制的上述缺點，意大利學(xué)者Dorigo提出一種蟻群算法，并將其成功應(yīng)用于規(guī)劃問題和求解組合最優(yōu)化問題[11]。蟻群算法（ACA）是基于信息素的個體行為協(xié)調(diào)機制，是一種新型的啟發(fā)式、分布式協(xié)作尋優(yōu)算法，也被稱為蟻群優(yōu)化算法（ACO）。若以系統(tǒng)完成全部任務(wù)所需路徑總長作為最優(yōu)評價指標(biāo)，則實現(xiàn)最優(yōu)分配的難點在于子機器人移動路徑長度、任務(wù)分布與路徑規(guī)劃之間的相互影響，而路徑規(guī)劃問題就是組合優(yōu)化問題TSP的一般形式。

在基于蟻群算法的任務(wù)分配機制中，應(yīng)考慮以下五個因素[12～14]：路徑最短優(yōu)先原則；信息素量濃度最高優(yōu)先原則；完成任務(wù)時間最短優(yōu)先原則；任務(wù)重要性優(yōu)先原則及擅長任務(wù)優(yōu)先原則。

在與理想環(huán)境不同的條件下，充分考慮任務(wù)執(zhí)行時間，可用最大時間最小。改進的蟻群算法能夠得到最優(yōu)解，但是其并不適用于機器人數(shù)已知的任務(wù)規(guī)劃問題，因此蟻群算法還有改進的空間。余伶俐[15]等人提出一種改進蟻群算法解決任務(wù)分配問題。該方法首先是用預(yù)定閾值和信息素矩陣建立解集，通過計算得到城市圖權(quán)值和集中式分配中心，并以計算所得的目標(biāo)函數(shù)值作為標(biāo)準(zhǔn)選擇一組最優(yōu)解，再通過局部搜索重新計算城市權(quán)值和聚類中心，用這組最優(yōu)解更新信息素矩陣，并保留本次任務(wù)分配所得到的最優(yōu)解。

姜健在其博士學(xué)位論文中提出一種排斥信息素型蟻群算法（PR-ACA）[16]。采用排斥信息素作為任務(wù)分配的信息介質(zhì)，信息素存儲的數(shù)據(jù)信息結(jié)構(gòu)以放射狀的節(jié)點結(jié)構(gòu)代替經(jīng)典蟻群算法的圖結(jié)構(gòu)。與吸引信息素方法相比，排斥信息素更能減少因機器人過于集中而造成的空間沖突加劇，且在信息素增加的同時能阻止任務(wù)聚集區(qū)機器人的增加。該算法能夠在機器人數(shù)量較多的情況下有效減少機器人的空間沖突，并且實現(xiàn)了多機器人搜集任務(wù)的自主分配。

劉曉瑩等將正交和混沌融入蟻群算法中，提出正交混沌蟻群算法[17]。正交試驗法是解決多因素、多水平實驗問題的方法，它利用正交表安排試驗，對方案作最優(yōu)設(shè)計。而混沌特性是指先產(chǎn)生一組混沌變量（其變量數(shù)目與優(yōu)化變量數(shù)目相同），用載波方式將混沌引入優(yōu)化變量，使其呈現(xiàn)混沌狀態(tài)，將混沌運動遍歷范圍放大到優(yōu)化變量取值范圍，利用混沌變量直接搜索。根據(jù)正交試驗法對任務(wù)目標(biāo)進行聚類，再用混沌特性初始化，能有效改進個體質(zhì)量，抑制早熟和停滯，降低系統(tǒng)陷入局部最優(yōu)的概率。

丁瀅潁等在基于蟻群算法的多機器人協(xié)調(diào)過程中加入自適應(yīng)衰減因子[18]。當(dāng)衰減因子減小時，信息素值減小，其下一步選擇該任務(wù)的概率也隨之減小，機器人將執(zhí)行其他任務(wù)。在基于蟻群算法的多機器人協(xié)作過程中，引入衰減因子可有效防止系統(tǒng)死鎖。

2.2 分布式任務(wù)分配機制

為體現(xiàn)多機器人系統(tǒng)魯棒性好的優(yōu)勢，大部分多機器人系統(tǒng)采用分布式構(gòu)架。分布式任務(wù)分配的方法主要有市場法和基于免疫系統(tǒng)的方法。

2.2.1 市場法

市場法定義為：多機器人系統(tǒng)采用全分布式方法，只有目標(biāo)信息由機器人共享，而機器人間的協(xié)作通過投標(biāo)來體現(xiàn)。機器人根據(jù)本地地圖計算得到目標(biāo)點的花費，并將其作為投標(biāo)價格。根據(jù)市場經(jīng)濟充分競爭規(guī)律，標(biāo)將由出價最低的機器人獲得，若其他機器人投標(biāo)價格均高于底價或無法計算該花費，則該點由發(fā)現(xiàn)它的機器人獲得。若該點已被另一機器人，則它將通知提交的機器人取消該點。當(dāng)機器人擁有多個目標(biāo)點時，以花費最小為目標(biāo)點，即當(dāng)前目標(biāo)點。市場法采用公開拍賣機制進行任務(wù)分配，每個機器人都可當(dāng)拍賣主，因此整個構(gòu)架是分布式的。利用市場法實現(xiàn)任務(wù)分配的過程可分為任務(wù)發(fā)布、任務(wù)評價及投標(biāo)、投標(biāo)評估及合同授權(quán)、合同建立及終止[19]。市場法讓機器人個體間競爭以滿足自身利益最大化，其積累效果是整個系統(tǒng)的利益。

分布式系統(tǒng)魯棒性好，易容錯。機器人之間只需要傳遞標(biāo)與投標(biāo)信息，大大減少了機器人之間通信量和計算量，無需考慮NP-Hard問題。與集中式任務(wù)分配方法不同的是：它沒有中央機器人與全局地圖，每個目標(biāo)點就是一個目標(biāo)，目標(biāo)信息包括目標(biāo)點位置和該機器人到該點的花費（即標(biāo)的底價）；它不需要預(yù)先掌握有關(guān)其它機器人的信息，易實現(xiàn)動態(tài)分布式任務(wù)分配。

Zlot[20]等成功的將市場經(jīng)濟機制用于解決多機器人協(xié)作探索問題。然而原始的市場法，也存在一定局限性，比如在基于市場法探索未知環(huán)境的大多數(shù)的情況下，每個機器人個體單獨取得標(biāo)，使得機器人之間的協(xié)作產(chǎn)生一定的局限性。

張飛等針對多個機器人如何充分利用有限通信信息完成環(huán)境探測的問題，提出了一種改進的市場法以實現(xiàn)多機器人探索的任務(wù)分配[21]。該方法利用標(biāo)的信息，使用數(shù)據(jù)融合中的Bayes統(tǒng)計方法更新本地地圖。該方法有效解決了市場法中計算代價的局限性，并且不會增加額外的通信量。Lovekesh[22]基于市場法提出了一種用于解決搜集、推物體、目標(biāo)跟蹤和崗哨執(zhí)勤4種級別機器人的任務(wù)分配策略。沿用了傳統(tǒng)的任務(wù)分配方法，并提出了任務(wù)一致性以及各種任務(wù)之間機器人的數(shù)量分配等新問題。

2.2.2 免疫系統(tǒng)法

為更好地解決個別機器人失效或者通訊信息丟失問題，生物免疫系統(tǒng)逐漸受到人們關(guān)注。在機器人領(lǐng)域，可將基于生物免疫系統(tǒng)的人工免疫系統(tǒng)（AIS）應(yīng)用于機器人的路徑規(guī)劃[7]和多機器人協(xié)作[23]。

Jerne在免疫獨特網(wǎng)絡(luò)假說[24]指出免疫系統(tǒng)中B細胞產(chǎn)生的抗體非獨立存在，每個抗體上有抗體決定基因、抗原決定基因，抗體通過抗體決定基因接受抗原及其它抗體的正向刺激而濃度提高，通過抗原決定基因接受其它抗體的抑制而濃度下降。因此，F(xiàn)armer[25]提出計算抗體的機理水平及濃度的動態(tài)方程。

人工免疫法是通過模擬生物免疫系統(tǒng)而產(chǎn)生的人工智能方法。基于免疫系統(tǒng)的任務(wù)分配方法是采用人體免疫系統(tǒng)作為協(xié)作機制，它是沒有中央控制器的分布式任務(wù)分配協(xié)作機制。系統(tǒng)中各機器人的角色是免疫細胞，根據(jù)抗原和抗體、抗體和抗體間的相互作用，組成自我保護和自我維持的生命體系，使系統(tǒng)自主選擇合適的抗體消滅抗原。機器人自主選擇合適的探測點，利用機器人間的相互協(xié)作提高環(huán)境探測效率，并適應(yīng)動態(tài)變化的環(huán)境。

Jun等人利用生物免疫系統(tǒng)分布式機理，提出一種基于人工免疫系統(tǒng)來實現(xiàn)多機器人的群體作業(yè)的算法[26]。算法中設(shè)定一個抗體間的作用系數(shù)，以影響機器人之間的相互協(xié)調(diào)。

高云園等人針對未知環(huán)境的完全探測提出一種基于免疫的探測算法[27]。利用類似蟻群激素的概念，用邊界點記憶和遺忘來實現(xiàn)完全探測。機器人在探測過程中留下激素作為局部環(huán)境信息，傳感器感知的局部環(huán)境信息（障礙物和局部激素信息）為探測中抗原信息。環(huán)境柵格包括障礙物、已探測和未探測三種狀態(tài)。以機器人上下左右四個鄰近柵格作為目標(biāo)柵格，產(chǎn)生四個抗體。該算法在抗原值和抗體作用系數(shù)上進行改進，抗原綜合考慮成本和效益，并實現(xiàn)巧妙避障，充分發(fā)揮了系統(tǒng)在探測環(huán)境時的自主性、協(xié)作性和魯棒性等優(yōu)勢，提高系統(tǒng)探測環(huán)境的效率。

除上述方法外，分布式任務(wù)分配的協(xié)作機制還有政治體制進行覆蓋和探索的方法。雖然分布式的結(jié)果不一定是最優(yōu)，但當(dāng)團隊中有部分機器人失效或通訊信息丟失時，整個系統(tǒng)依然能較好地完成任務(wù)。這充分體現(xiàn)了多機器人系統(tǒng)魯棒性好的特點。

3 研究中存在的問題與發(fā)展趨勢

任務(wù)分配問題是多機器人協(xié)調(diào)與協(xié)作領(lǐng)域范圍內(nèi)首先要解決的關(guān)鍵問題。無論是在靜態(tài)，還是在動態(tài)環(huán)境中，只有合理利用任務(wù)分配算法，才能提高多機器人系統(tǒng)環(huán)境探測效率，使得整個系統(tǒng)在完成全部任務(wù)時獲得最大收益。本文圍繞多機器人系統(tǒng)的任務(wù)分配問題，總結(jié)了不同環(huán)境中多機器人系統(tǒng)任務(wù)分配機制算法。雖然多機器人系統(tǒng)在許多領(lǐng)域取得了很大進展，但也存在很多需要進一步深入研究的問題。

靜態(tài)環(huán)境中，集中式分配機制對中央機器人要求較高，其一旦出現(xiàn)故障，整個系統(tǒng)將處于癱瘓狀態(tài)。因此改進集中式任務(wù)分配算法，降低多機器人協(xié)調(diào)過程中的通信信息量，同時在機器人的基礎(chǔ)硬件上進行改進，提高通信網(wǎng)絡(luò)的帶寬，使得多機器人系統(tǒng)在靜態(tài)環(huán)境中能夠高效完成環(huán)境探索任務(wù)。

在解決多機器人任務(wù)分配問題的過程中，人們往往將解決問題的關(guān)鍵步驟放在如何降低任務(wù)總執(zhí)行成本和提高機器人系統(tǒng)的總收益，而常常忽視如何降低每個機器人平均完成子任務(wù)時間。在今后研究過程中，可以考慮通過降低每個機器人平均完成子任務(wù)時間來提高整個機器人系統(tǒng)總體收益。在動態(tài)環(huán)境下，為保證移動機器人滿足實時性的要求，任務(wù)分配也應(yīng)具有實時性。

4 結(jié)束語

本文在查閱大量文獻基礎(chǔ)上，綜述了多機器人任務(wù)分配的研究領(lǐng)域。在多機器人協(xié)調(diào)與協(xié)作探索未知環(huán)境的過程中，如何提高任務(wù)分配效率是多機器人任務(wù)分配研究的關(guān)鍵問題。本文對任務(wù)分配問題的分類、適用范圍以及優(yōu)缺點進行了歸納總結(jié)。

針對這些研究內(nèi)容，分析了存在的問題，并在此基礎(chǔ)上對該領(lǐng)域未來的發(fā)展趨勢進行了展望。

[1] Parker L E.Current research in multi-robot systems[J].Artif i cial Life and Robotics,2003,7(2):1-5.

[2] Parker L E,et al.Status of robotics in the U. S. workshop.national science foundation.Washington, D C,2004.

[3] Gordon D M.The organization of work in social insect colonies[J].Nature,1996,380:121-124.

[4] Parker L E.Multiple Mobile Robot Systems.Siciliano B,et al.Handbook of Robotics,Springer.2008:921-941.

[5] 蔡自興等.多移動機器人協(xié)同原理與技術(shù)[M].北京:國防工業(yè)出版社,2011:73.

[6] Gerkey B P,et al.A analysis and taxonomy of task allocation in multi-robot systems[J].International Journal of Robotics Research,2004,23(9):939-954.

[7] Gerkey B P,et al.A framework for studying multi-robot task allocation[J].In Proceedings of Multi-robot Systems:From Swarms to Intelligent Automata.Netherhands,Kluwer Academic Publishers,2003.2:15-26.

[8] Dudek G,et al.Taxonomy for multi-agent robotics[J].Autonomous Robots,1996,3(4):375-397.

[9] Burgard W,et al.Collaborative multi-robot exploration[C].IEEE International Conference on Robotics and Automation(ICRA).San Francisco:IEEE Press,2000:476-481

[10] Simmons R， et al.Coordination for multi-robot exploration and mapping[C].In Proceedings of the National Conference on Artif i cal Intelligence.Austin,2000:852-858.

[11] Gambardella L M,et al:A reinforcement learning approach to the traveling sales man problem[C].Proceedings of the Twelfth International Conference on Machine Learning.Palo Alto, CA,1994:252-260.

[12] 萬旭等.改進的最大最小蟻群算法在有時間窗車輛路徑問題中的應(yīng)用[J].計算機集成制造系統(tǒng),2005,11(4):572-576.

[13] Dror M.Note on the complexity of the shortest path models for column generation in VRPTW[J].Operations Research,1994,42(5):977-978.

[14] 任韶萱.蟻群算法在多機器人協(xié)作中的應(yīng)用[J].沈陽理工大學(xué)學(xué)報.2011,(05):49-53.

[15] 余伶俐等.一種多機器人任務(wù)規(guī)劃算法及其系統(tǒng)實現(xiàn)[J].計算機科學(xué).2010,(06):258-261.

[16] 姜健.多移動機器人協(xié)作方法研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2008:56.

[17] 劉曉瑩等.一種正交混沌蟻群算法在群機器人任務(wù)規(guī)劃中的應(yīng)用研究[J].小型微型計算機系統(tǒng).2010,(1):166-170.

[18] 丁瀅潁等.基于蟻群算法的多機器人協(xié)作策略[J].機器人.2003,(5):31-35.

[19] 趙慧靜.面向任務(wù)的多移動機器人體系結(jié)構(gòu)優(yōu)化的研究[D].沈陽:沈陽理工大學(xué),2010:21.

[20] Zlot R,et,al.Multi-robot exploration controlled by a market economy[C].proceedings of the IEEE International Conference on Robotics and Automation(ICRA).Washington:IEEE Press,2002:3016-3023.

[21] 張飛等.多機器人協(xié)作探索的改進市場法[J].控制與決策.2005,(05):37-41.

[22] Lovekesh V, et al.Market-based multi-robot coalition formation.Proceedings of the 8th International Symposium on Distributed Autonomous Robotic Systems[C].Paul,Minnesota,USA,2006:1-10.

[23] Parker L E,et al.Cooperative robot teams applied to the site preparation task[C].Atlanta,USA:Proc of 10th International Conference on Advanced Robotics.IEEE Press,2001:71-77.

[24] Jerne N K.Idiotopic networks and other preconceived ideas[J]. Immunological Review,1984,79:5-24.

[25] Farmer J D, et al.The immune system,adaptation,and machine learning[J].Physica,1986,22(1):187-204.

[26] Jun J H,et al.Realization of cooperative strategies and swarm behavior in distributed autonomous robotic systems using artif i cial immune system[C].Proceedings of the IEEE International Conference on Systems,Man and Cybernetics.Tokyo,Japan,1999:614-619.

[27] 高云園,韋巍.基于免疫機理的多機器人未知環(huán)境完全探測研究[J].模式識別與人工智能.2007,(2):51-57.