曹宗華，吳 斌，黃玉清，鄧春艷

(西南科技大學(xué) 信息工程學(xué)院，四川 綿陽(yáng) 621010)

0 引言

隨著社會(huì)的發(fā)展，由于機(jī)器人應(yīng)用的領(lǐng)域和范圍在不斷擴(kuò)展，雖然單個(gè)機(jī)器人的能力在提高，但是對(duì)于一些復(fù)雜的任務(wù)，單個(gè)機(jī)器人并不能滿足人們的要求，因此，多機(jī)器人系統(tǒng)(MRS，Multi－Robot System)成為主要發(fā)展方向。MRTA(MRTA，Multi－Robot Task Allocate)是MRS 的研究方向中之一，MRTA 是指將多個(gè)任務(wù)分配給在最短時(shí)間內(nèi)完成任務(wù)的機(jī)器人。MRS的研究起源于1980 年，MRTA 的研究是為了提高多機(jī)器人系統(tǒng)的性能，確保多機(jī)器人在執(zhí)行任務(wù)過程中的協(xié)同性。MRTA 問題本質(zhì)是最優(yōu)分配問題，最初是在博弈論中提出的，相繼在組合優(yōu)化、調(diào)度、經(jīng)濟(jì)學(xué)、運(yùn)籌學(xué)、群體智能等學(xué)科進(jìn)行了深入研究。MRS 的結(jié)構(gòu)可分為兩大類:集中式分配和分布式分配。早期的多機(jī)器人系統(tǒng)任務(wù)分配多采用集中式的，由一個(gè)管理者負(fù)責(zé)任務(wù)的分配，這種方法不適合機(jī)器人規(guī)模較大的系統(tǒng);分布式任務(wù)分配方法可以發(fā)揮系統(tǒng)的分布計(jì)算性能，相比集中式它具有高效性和魯棒性。MRTA 算法主要包括基于行為的分配方法、基于市場(chǎng)機(jī)制方法及群體智能的分配方法等，這些分配算法都有各自的優(yōu)點(diǎn)?；谛袨榈姆峙浞椒ǎ?］，實(shí)時(shí)性和穩(wěn)定性較好，只能求解局部最優(yōu);基于市場(chǎng)機(jī)制的分配方法［2-3］，實(shí)時(shí)性差和系統(tǒng)開銷大，適用于小規(guī)模系統(tǒng)，能夠?qū)崿F(xiàn)全局最優(yōu);群體智能方法［4-6］，主要方法包括閾值法和蟻群方法，系統(tǒng)具有魯棒性、實(shí)時(shí)性及高效性，適用于分布式MRTA;在MRTA 的研究中，群體智能方法是解決MRTA 的主要發(fā)展方向，文中采用改進(jìn)的蟻群算法研究MRTA。

本文首先研究了多機(jī)器人系統(tǒng)及任務(wù)分配問題;然后敘述了蟻群算法;在此基礎(chǔ)上設(shè)計(jì)了改進(jìn)的蟻群算法來解決MRTA 問題;通過實(shí)驗(yàn)數(shù)據(jù)對(duì)算法仿真并分析;實(shí)驗(yàn)表明，本文算法能很好的解決大規(guī)模機(jī)器人系統(tǒng)任務(wù)分配問題。

1 多機(jī)器人系統(tǒng)描述

多機(jī)器人系統(tǒng)由單個(gè)具備多種不同功能的機(jī)器人構(gòu)成，如智能感知、搬運(yùn)能力、智能決策、通信能力等。且每個(gè)機(jī)器人都是自立的，對(duì)于簡(jiǎn)單的任務(wù)，單個(gè)機(jī)器就能完成。對(duì)于復(fù)雜任務(wù)，分成多個(gè)單個(gè)機(jī)器人可完成的原子任務(wù)，多機(jī)器人系統(tǒng)根據(jù)這些任務(wù)形成特定的聯(lián)盟，從而適應(yīng)任務(wù)需求。MRS 常采用Ad-hoc 網(wǎng)絡(luò)，機(jī)器人之間可以進(jìn)行信息交互，從而可實(shí)現(xiàn)分布式計(jì)算。

隨機(jī)分布的MRS 分布結(jié)構(gòu)。多機(jī)器人系統(tǒng)包括任務(wù)發(fā)布系統(tǒng)、通信系統(tǒng)及多個(gè)智能機(jī)器人。任務(wù)發(fā)布系統(tǒng)具備通信、復(fù)雜任務(wù)分解等功能;通信系統(tǒng)具備路由、點(diǎn)對(duì)點(diǎn)及廣播等通信功能;智能機(jī)器人具備通信、任務(wù)規(guī)劃及任務(wù)執(zhí)行等功能。

1.1 機(jī)器人能力描述

多機(jī)器人系統(tǒng)包含n 個(gè)異構(gòu)機(jī)器人R={Ri，1≤i≤n}，對(duì)于機(jī)器人Ri其能力向量ARi=diag{ai1，ai2…，ain}，ain定義為機(jī)器人Ri的第n 種能力強(qiáng)弱，若不具備能力n 則ain=0;C =［c1，c2，…cn］T，其中cn為機(jī)器人基本單項(xiàng)能力如移動(dòng)能力、搬運(yùn)能力、通信能力及各種傳感能力等。

綜上可得，單個(gè)機(jī)器人的能力可表示為E(Ri)=ARi×C。

1.2 任務(wù)描述

假設(shè)有m(m≥1)個(gè)任務(wù)，可表示為T ={Tk，1≤k≤m}，任務(wù)Tk對(duì)機(jī)器人的單項(xiàng)能力要求BTk=diag{bk1，bk2，…，bkn}。任務(wù)Tk所需能力E(Tk)=BTk×C，若機(jī)器人Ri能夠完成任務(wù)Tk，則要求ain≥bkn，可以記為E(Tk)≤E(Ri)。

任務(wù)的約束條件主要包括時(shí)序約束、任務(wù)時(shí)間約束及多機(jī)器人協(xié)同約束等。時(shí)序約束是指不同任務(wù)Tk之間存在執(zhí)行順序。任務(wù)時(shí)間約束是指某個(gè)任務(wù)必須在指定的時(shí)間內(nèi)完成。

1.3 機(jī)器人完成任務(wù)的代價(jià)

在多機(jī)器人系統(tǒng)中，由于機(jī)器人個(gè)體的能力存在差異，在完成相同的任務(wù)時(shí)，不同機(jī)器人所花費(fèi)的代價(jià)也會(huì)存在差異。機(jī)器人Ri的能力向量為E(Ri)，機(jī)器人的各項(xiàng)能力在完成任務(wù)過程中有能量消耗，針對(duì)各項(xiàng)能力，所花代價(jià)向量表示為cost(ARi)=［costai1，costai2…，costain］T，因此，機(jī)器人Ri完成任務(wù)Tk所花代價(jià)可以定義為costi(Tk)=E(Tk)×cost(ARi)。

1.4 MRTA 問題描述

MRTA 是多機(jī)器人系統(tǒng)動(dòng)態(tài)環(huán)境下協(xié)作完成任務(wù)的一個(gè)基本問題。對(duì)于多機(jī)器人系統(tǒng)執(zhí)行給定的系統(tǒng)級(jí)任務(wù)，需要解決的是如何把任務(wù)分解給多個(gè)機(jī)器人及在何時(shí)執(zhí)行該任務(wù)的問題，即MRTA。機(jī)器人Ri和任務(wù)Tk的分布如圖1 所示。

圖1 機(jī)器人及任務(wù)分布

多機(jī)器人系統(tǒng)的任務(wù)分配由協(xié)作規(guī)劃層完成，協(xié)作規(guī)劃層可以是一臺(tái)或幾臺(tái)移動(dòng)機(jī)器人甚至包括不可移動(dòng)的計(jì)算處理平臺(tái)或人類共同組成，要求有較強(qiáng)的通訊能力、計(jì)算能力和存儲(chǔ)能力，可稱之為指揮者。協(xié)作規(guī)劃層為整個(gè)團(tuán)隊(duì)的最高控制中心，負(fù)責(zé)系統(tǒng)的全局規(guī)劃、任務(wù)分配、角色任命，對(duì)協(xié)調(diào)層直接管理。

分布式任務(wù)分配的具體步驟如下:首先，任務(wù)規(guī)劃，通過控制中心向多機(jī)器人系統(tǒng)的中央機(jī)器人下達(dá)任務(wù)，任務(wù)進(jìn)入任務(wù)規(guī)劃模塊，協(xié)作規(guī)劃模塊取得任務(wù)后，運(yùn)用知識(shí)把任務(wù)分解成多個(gè)子任務(wù);第二步，將多個(gè)子任務(wù)隨機(jī)發(fā)布給MRS 中的多個(gè)機(jī)器人;第三步，MRS 中的機(jī)器人運(yùn)用群體智能算法求解最優(yōu)分配，從而確定任務(wù)的接收者，接收任務(wù)的同時(shí)發(fā)送信息反饋其它機(jī)器人;最后，機(jī)器人接收任后會(huì)根據(jù)自己的角色和所要完成的任務(wù)，利用傳感器采集的周圍環(huán)境信息等，采用基于行為的控制方法規(guī)劃自己的路徑，確定機(jī)器人運(yùn)動(dòng)的速度和角度。

2 改進(jìn)的蟻群算法

蟻群算法具有問題求解的快速性、全局最優(yōu)特性及在優(yōu)化過程初期解的合理性等特點(diǎn)，可以解決任務(wù)分配問題，在任務(wù)分配過程，主要考慮如何發(fā)揮系統(tǒng)的性能，將任務(wù)最優(yōu)分配，實(shí)現(xiàn)系統(tǒng)最小代價(jià)。

2.1 算法思想

本文采用蟻群算法實(shí)現(xiàn)任務(wù)分配，用螞蟻代表任務(wù)，機(jī)器人為任務(wù)的接收者。假設(shè)任務(wù)的個(gè)數(shù)為m，機(jī)器人的數(shù)目為n，PTkij(t)表示在t 時(shí)刻任務(wù)Tk由機(jī)器人i 轉(zhuǎn)移到機(jī)器人j 的狀態(tài)轉(zhuǎn)移概率:

式中，Rc為任務(wù)i 的候選機(jī)器人集合;α 為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性，反映了任務(wù)在轉(zhuǎn)移過程中所積累的信息對(duì)任務(wù)的轉(zhuǎn)移所起的作用;β 為期望啟發(fā)式因子，表示能見度的相對(duì)重要性，反映了任務(wù)在轉(zhuǎn)移過程中啟發(fā)信息在任務(wù)轉(zhuǎn)移路徑的選擇中受重視程度。ηj(t)為啟發(fā)函數(shù):

式中Dj(Tk)表示機(jī)器人j 與任務(wù)Tk之間距離。τij(t)表示t 時(shí)刻在i 和j 連線上殘留的信息素值;所有任務(wù)都完成一次求解，即完成一次循壞，從而可尋找出任務(wù)的最優(yōu)執(zhí)行者，并按下式更新信息素值:

式(3)中Δτij(t)(Q 為常數(shù)表示信息強(qiáng)度)表示Tk和Rj之間的信息素增強(qiáng)。其中:

根據(jù)上述計(jì)算公式，計(jì)算出任務(wù)Tk與機(jī)器人之間的信息素，信息素強(qiáng)度表示著機(jī)器人與任務(wù)間的適應(yīng)度，信息素與機(jī)器人完成任務(wù)的代價(jià)及距離有關(guān)。因此，多個(gè)任務(wù)可根據(jù)信息素值進(jìn)行分配。

2.2 算法的改進(jìn)

上述算法中，只考慮了機(jī)器人到任務(wù)之間的距離，從而導(dǎo)致了分配結(jié)果出現(xiàn)“就近”問題。本文所考慮的任務(wù)分配要避免該問題，因此需對(duì)基本算法進(jìn)行改進(jìn)。

基于蟻群算法的多機(jī)器人任務(wù)分配中，轉(zhuǎn)移概率僅決定了機(jī)器人接收任務(wù)的優(yōu)先順序，由于機(jī)器人的能力在計(jì)算轉(zhuǎn)移概率時(shí)是未知的，而機(jī)器人與任務(wù)的距離是已知的，因此轉(zhuǎn)移概率的啟發(fā)函數(shù)僅與距離有關(guān);任務(wù)分配的直接影響因素是信息素，因此在對(duì)信息素更新時(shí)應(yīng)加入機(jī)器人能力的影響。也就是改進(jìn)Δτij(t)表達(dá)式，寫成如下形式:

式(5)中costj(Tk)表示的是機(jī)器人完成任務(wù)所花代價(jià);Q1，Q2表示完成任務(wù)的代價(jià)和所行走距離在信息素中所占的比例。

采用改進(jìn)后的信息素更新規(guī)則，需要從計(jì)算的結(jié)果的尋找最優(yōu)分配方案，當(dāng)機(jī)器人數(shù)目為N 時(shí)，任務(wù)數(shù)目為M(M ＜N)，時(shí)間復(fù)雜度為O(N!)，因此，當(dāng)機(jī)器人和任務(wù)數(shù)目較多時(shí)，機(jī)器人在搜索過程將非常耗時(shí)，以至于算法不夠高效。面對(duì)這種局面，提出一種快速高效搜索算法，在分布式多機(jī)器人系統(tǒng)中，任務(wù)的最后一個(gè)接收者負(fù)責(zé)計(jì)算任務(wù)的分配最優(yōu)搜索，從而實(shí)現(xiàn)最優(yōu)分配。最優(yōu)搜索算法思想如下:

(1)為每個(gè)任務(wù)選取最優(yōu)分配的機(jī)器人，時(shí)間復(fù)雜度為O(M* N);

(2)檢查是否有多個(gè)任務(wù)分配給了同一個(gè)機(jī)器人，若否則轉(zhuǎn)第(4)步;時(shí)間復(fù)雜度為O(M);

(3)對(duì)于多個(gè)任務(wù)分配給了同一個(gè)機(jī)器人，將這些任務(wù)的次優(yōu)分配納入搜索，綜合考慮這些任務(wù)的最優(yōu)和次優(yōu)來分配。轉(zhuǎn)第(2)步;時(shí)間復(fù)雜度最大為O(M!);

(4)通知任務(wù)的最終接收者完成任務(wù)。

改進(jìn)的算法時(shí)間復(fù)雜度較小。因此該算法比普通算法更適合用于搜索最優(yōu)的多任務(wù)分配方案。

2.3 算法實(shí)現(xiàn)

綜上所述，基于蟻群算法的任務(wù)分配具體實(shí)現(xiàn)步驟如下:

(1)參數(shù)初始化。令時(shí)間t =0，循環(huán)次數(shù)N =0，將m 個(gè)任務(wù)隨機(jī)置于n 個(gè)機(jī)器人上，令初始信息量τij(0)為常數(shù)，Δτk

ij(0)=0;(2)接收到任務(wù)的機(jī)器人i 根據(jù)任務(wù)Tk所需的能力Etk及約束條件計(jì)算代價(jià)costk(Tk)及收益值，然后根據(jù)轉(zhuǎn)移概率PTkij(t)從Rc中選擇一個(gè)機(jī)器人，重復(fù)該步驟，直到Rc中機(jī)器人都計(jì)算出相應(yīng)的代價(jià)及收益值;

(3)根據(jù)任務(wù)Tk對(duì)應(yīng)的分配方案，計(jì)算最大收益值及最小代價(jià)分配方案;

(4)根據(jù)全局信息素更新規(guī)則式(3)更新分配方案對(duì)應(yīng)的信息素的強(qiáng)度;

(5)選擇當(dāng)前任務(wù)分配計(jì)劃與全局最優(yōu)分配計(jì)劃進(jìn)行比較，若優(yōu)于全局最優(yōu)分配計(jì)劃，則用當(dāng)前任務(wù)分配計(jì)劃更新全局最優(yōu)分配計(jì)劃;令t=t+1，N=N+1;

(6)當(dāng)N≤Nmax時(shí)，繼續(xù)從(2)執(zhí)行;

(7)查找計(jì)算結(jié)果，輸出最優(yōu)分配方案。

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

基于上述算法思想，采用Matlab 仿真平臺(tái)進(jìn)行算法驗(yàn)證。仿真環(huán)境設(shè)定在一個(gè)100 ×100m 的區(qū)域，隨機(jī)分布著20 個(gè)機(jī)器人，以及10 個(gè)任務(wù)。機(jī)器人均擁有完成任務(wù)的能力，約定每個(gè)任務(wù)均由單機(jī)器人來完成。對(duì)機(jī)器人的描述(表1)主要是位置、能力及完成任務(wù)所花代價(jià);任務(wù)的描述(表2)主要是任務(wù)的位置及對(duì)機(jī)器人最小能力要求。

表1 機(jī)器人描述

表2 任務(wù)描述

表1 的數(shù)據(jù)中，多個(gè)機(jī)器人存在差異;表2 的數(shù)據(jù)中，任務(wù)對(duì)機(jī)器人的能力要求不同。基于以上數(shù)據(jù)，編寫程序進(jìn)行仿真，基本算法參數(shù)設(shè)置為α=1，β=3，Q=2，NC_max =300;改進(jìn)的算法參數(shù)設(shè)置為α=1，β=3，Q1=2，Q2=5，NC_max =300，算法仿真結(jié)果如圖2 所示。

圖2 基本算法分配結(jié)果(a)及改進(jìn)算法分配結(jié)果(b)

圖2a 可以很直觀地看到基本蟻群算法任務(wù)的分配，分配結(jié)果如表3 所示;圖2b 可以很直觀地看到改進(jìn)的蟻群算法任務(wù)分配，分配結(jié)果如表4 所示。

表3 基本蟻群算法的多機(jī)器人任務(wù)分配結(jié)果

表4 改進(jìn)蟻群算法的多機(jī)器人任務(wù)分配結(jié)果

通過對(duì)表3 和表4 的數(shù)據(jù)進(jìn)行分析，可以得出，采用基本算法完成設(shè)定的任務(wù)所花的代價(jià)為892;改進(jìn)的蟻群算法完成設(shè)定的作務(wù)所花的代價(jià)為806;由此可知完成相同的任務(wù)，文中改進(jìn)的蟻群算法所花總的代價(jià)較小，實(shí)現(xiàn)了全局近似最優(yōu)分配。

4 結(jié)論

文中對(duì)多機(jī)器人任務(wù)分配系統(tǒng)進(jìn)行了描述，針對(duì)多機(jī)器任務(wù)分配問題，提出了一種對(duì)基本蟻群算法的改進(jìn)算法，編寫算法代碼，運(yùn)用Matlab 平臺(tái)仿真，對(duì)比基本算法和改進(jìn)算法的仿真結(jié)果，改進(jìn)的蟻群算法在多任務(wù)分配中所花代價(jià)最小。從而得出文中改進(jìn)的任務(wù)分配算法實(shí)現(xiàn)了全局近似最優(yōu)的多任務(wù)分配。

［1］柳林，季秀才，鄭志強(qiáng). 基于市場(chǎng)法及能力分類的MRTA方法［J］. 機(jī)器人，2006(3):337.

［2］張崳，劉淑華. MRTA 的研究與進(jìn)展［J］. 智能系統(tǒng)學(xué)報(bào)，2008(2):115.

［3］齊心躍，田彥濤，楊茂，等. 基于市場(chǎng)機(jī)制的多機(jī)器人救火任務(wù)分配策略［J］. 吉林大學(xué)學(xué)報(bào):信息科學(xué)版，2009，27(5):506.

［4］姜健，閆繼宏，臧希喆，等. 基于信息素的多機(jī)器人協(xié)作任務(wù)分配［J］. 計(jì)算機(jī)工程與應(yīng)用，2008(2):19.

［5］M.Dias and A.Stentz，"Opportunistic optimization for market-based multi robot control"［J］，IEEE International Conference on Intelligent Robots and Systems，2002:2714.

［6］Y.Y.DING，Y.HE，and J.P. JIANG，"Multi-Robot Cooperation Method Based on the Ant Algorithm"［J］，ROBOT，2003，25(5):414.