周 菁，慕德俊

（西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安710072）

多機(jī)器人系統(tǒng)任務(wù)分配概率模型研究?

周 菁，慕德俊

（西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安710072）

建立系統(tǒng)的概率模型是描述和分析自組織多機(jī)器人系統(tǒng)的一條新思路。運(yùn)用包括隨機(jī)過程、矩陣論和線性代數(shù)等數(shù)學(xué)方法建立自組織多機(jī)器人系統(tǒng)的任務(wù)分配模型，克服了現(xiàn)存模型對任務(wù)類型數(shù)目無可擴(kuò)展性的缺點(diǎn)。為了驗(yàn)證模型的一般性和有效性，以時(shí)間離散狀態(tài)連續(xù)的馬爾科夫鏈的極限分布作為任務(wù)分配的理論結(jié)果，優(yōu)點(diǎn)是可以預(yù)測多機(jī)器人系統(tǒng)任務(wù)分配的長期穩(wěn)定行為。任務(wù)分配的目的是保持執(zhí)行任意一種任務(wù)的機(jī)器人數(shù)量占機(jī)器人總數(shù)的比例與該種任務(wù)所占總?cè)蝿?wù)量的比例相等。仿真實(shí)驗(yàn)的結(jié)論也說明了任務(wù)分配模型可以達(dá)到理想的分配效果。

多機(jī)器人系統(tǒng)；任務(wù)分配；概率模型

1 引 言

作為多機(jī)器人系統(tǒng)（Multi-robot system，MRS）協(xié)作的重要研究內(nèi)容之一，多機(jī)器人任務(wù)分配（Multi-robot task allocation，MRTA）要解決系統(tǒng)中機(jī)器人到子任務(wù)的對應(yīng)關(guān)系問題，也就是說要決定分配機(jī)器人x去執(zhí)行子任務(wù)y，以及確定分配給子任務(wù)y的機(jī)器人x的數(shù)量［1-2］。任務(wù)分配是整個(gè)多機(jī)器人系統(tǒng)通暢運(yùn)行的基礎(chǔ)。如何在保障系統(tǒng)對任務(wù)目標(biāo)的執(zhí)行結(jié)果與效率的同時(shí)，避免由機(jī)器人之間或由機(jī)器人與環(huán)境之間產(chǎn)生沖突所造成的損失［3］是很多學(xué)者的興趣點(diǎn)，它對系統(tǒng)工作性能起到?jīng)Q定性影響，因此直接影響生產(chǎn)率。

Gerkey［4］提出任務(wù)分配問題的形式化和類別定義，并進(jìn)行了理論上的解析，將任務(wù)分配問題描述為一個(gè)最優(yōu)化問題，通過定義效用函數(shù)，將使其和最大作為機(jī)器人任務(wù)分配的目標(biāo)。目前，針對MRTA問題的解決方法主要分為集中式和分布式任務(wù)分配方法兩類。其中基于匈牙利算法的方法是比較典型的集中式任務(wù)分配方法［5-6］。集中式方法的計(jì)算量通常隨任務(wù)的復(fù)雜程度呈指數(shù)形式增長。因而不適合于解決大規(guī)模任務(wù)分配問題。因此在實(shí)際應(yīng)用中具有一定的局限性［7］，比較適合于解決中、小規(guī)模的靜態(tài)任務(wù)分配問題。

在分布式任務(wù)分配方法中，一般情況下，個(gè)體機(jī)器人沒有關(guān)于任務(wù)的全局知識，而是分別根據(jù)自身傳感器得到的局部信息進(jìn)行計(jì)算和規(guī)劃，整個(gè)系統(tǒng)的性能不僅與個(gè)體密切相關(guān)，更依賴于所有個(gè)體的綜合效應(yīng)。常用的分布式任務(wù)分配方法有基于市場機(jī)制的方法［8-9］，拍賣算法［10］和群合作法［11-14］等。自組織合作是最典型的多機(jī)器人群合作方式，這方面的研究工作有許多，如用于復(fù)雜物品收集和搬運(yùn)工作的理論和仿真［11-12］，Kube和Zhang［13-14］在一個(gè)由五個(gè)物理機(jī)器人組成的系統(tǒng)上實(shí)現(xiàn)了突現(xiàn)控制策略（emergent control strategy），該多機(jī)器人系統(tǒng)的任務(wù)是找到和推動(dòng)一個(gè)盒子。

2 自組織多機(jī)器人系統(tǒng)任務(wù)分配問題

由Lerman等人［15-17］的研究可知，在一個(gè)具有有限個(gè)子任務(wù)的工作中，在固定大小的工作場地中機(jī)器人數(shù)量越多、則機(jī)器人相互避碰的次數(shù)越多、損耗時(shí)間越長、機(jī)器人的平均效率越低。而一般來說某種子任務(wù)的數(shù)量越大、其占用工作環(huán)境的空間也越大、可容納的機(jī)器人數(shù)量也越多、需要的工作量也越大、因此應(yīng)該分配較多的機(jī)器人執(zhí)行該項(xiàng)子任務(wù)，反之亦然。順著這條思路：我們應(yīng)該保持在機(jī)器人系統(tǒng)對全局任務(wù)的執(zhí)行中，在完成子任務(wù)的同時(shí)，還要確保正在執(zhí)行各種子任務(wù)的機(jī)器人數(shù)量占機(jī)器人總數(shù)量的比例與該種子任務(wù)占總?cè)蝿?wù)量的比例相等，以此可以減少碰撞和同類資源爭搶，從而提高多機(jī)器人系統(tǒng)平均效率。多機(jī)器人系統(tǒng)屬高度松散系統(tǒng)，為其建立精確動(dòng)力學(xué)模型十分困難，而且任務(wù)環(huán)境復(fù)雜，存在諸多不確定性，在關(guān)于多機(jī)器人系統(tǒng)研究中絕大多數(shù)工作是實(shí)踐經(jīng)驗(yàn)性的。自組織多機(jī)器人系統(tǒng)也存在同樣的問題。由于系統(tǒng)宏觀層面的行為具有涌現(xiàn)特性，一直以來都缺乏有效手段對自組織系統(tǒng)進(jìn)行分析。雖然，研究者也可以用現(xiàn)場實(shí)驗(yàn)來分析自組織系統(tǒng)，了解各種設(shè)計(jì)參數(shù)對系統(tǒng)宏觀行為的作用和影響，但這些方法耗時(shí)太長，費(fèi)用太高。建立系統(tǒng)的概率模型［18-19］是描述和分析自組織系統(tǒng)的一條可行思路。

近年來，關(guān)于自組織多機(jī)器人系統(tǒng)任務(wù)分配的研究成果都是圍繞特定范例的研究［17，20-21］，因此不具備可重用性和可擴(kuò)展性。比如對兩種類型任務(wù)的分配方法［17］改進(jìn)工作［20］，經(jīng)過觀察，我們不難看出其所用任務(wù)分配模型［17，20］只適用于兩種類型的任務(wù)。模型［17］描述機(jī)器人個(gè)體動(dòng)態(tài)性時(shí)所使用的是一階微分方程，并使用一階微分方程的通解求解，模型［20］使用拉氏變換求解，這兩種方法的優(yōu)點(diǎn)是簡單，但簡單的東西往往也具有局限性。當(dāng)任務(wù)類型多于兩種時(shí)，比如三種，六種等，該方法將沒辦法處理，因此克服模型的局限性使探索新方法成為必要工作。

運(yùn)用包括隨機(jī)過程、矩陣論和線性代數(shù)等數(shù)學(xué)方法建立新的任務(wù)分配模型，克服現(xiàn)存模型無可擴(kuò)展性的缺點(diǎn)，從而使新模型能適應(yīng)今后工業(yè)領(lǐng)域的各種需要。為了驗(yàn)證模型的一般性和有效性，仍以Lerman等人［17，21］的任務(wù)分配研究為背景。任務(wù)是抽象的，可以具體化為任意工作，任務(wù)類型被擴(kuò)展到了更多，以三種、六種為例，任務(wù)分配的目的是保持執(zhí)行第i種任務(wù)的機(jī)器人數(shù)占機(jī)器人總數(shù)的比例與該種子任務(wù)所占總?cè)蝿?wù)量的比例相等，以減少碰撞和資源爭搶。我們重點(diǎn)研究多機(jī)器人系統(tǒng)群集行為的宏觀表達(dá)，因此需要幾十甚至幾百個(gè)機(jī)器人組成的系統(tǒng)，鑒于物理實(shí)驗(yàn)條件的限制，我們使用仿真環(huán)境進(jìn)行結(jié)果驗(yàn)證。

3 多機(jī)器人系統(tǒng)宏觀模型

3.1 機(jī)器人的局部觀察

現(xiàn)假設(shè)在自組織多機(jī)器人系統(tǒng)的任務(wù)分配中，總共有三種類型的待收集物品，這里將它們稱為紅色、綠色和藍(lán)色物品，分別用字符‘R’，‘G’，‘B’表示，任務(wù)集合為I：｛R，G，B｝。這三種物品在工作區(qū)域C中均勻分布，且三種物品在場地中的數(shù)量為MR，MG和MB，其屬于在任務(wù)分配中機(jī)器人事先不知道的全局知識，機(jī)器人需要通過對環(huán)境的局部觀察來估計(jì)它們。

假設(shè)機(jī)器人觀察一個(gè)物品需耗時(shí)τ秒，則在hτ秒內(nèi)總共觀察到h個(gè)物品，其中h也是機(jī)器人滾動(dòng)歷史窗口的長度。我們可以視τ為系統(tǒng)縮放因子，令τ為單位長度，這樣就可以通過歸一化將其忽略掉。

已知MR，MG和MB分別表示在工作區(qū)域中三種物品的數(shù)量，并且總數(shù)為。對于進(jìn)行局部觀察的機(jī)器人來說，在時(shí)間區(qū)域［t-h，t］內(nèi)，機(jī)器人觀察到mR個(gè)紅色物品，mG個(gè)綠色物品和mB個(gè)藍(lán)色物品的概率可以由三個(gè)泊松分布的乘積表示，由公式（1）給出：

其中對于z∈I，λZ是mZ的均值，當(dāng)MZ不隨時(shí)間改變時(shí)，有λZ＝αMZh。

3.2 描述個(gè)體動(dòng)態(tài)性的隨機(jī)主方程

假設(shè)由一個(gè)時(shí)間連續(xù)狀態(tài)離散的馬爾可夫鏈ξ（t）表示在時(shí)刻t機(jī)器人所處的狀態(tài)，ξ（t）的狀態(tài)空間為I：｛R，G，B｝。在時(shí)刻t機(jī)器人處于狀態(tài)空間I中任何一個(gè)狀態(tài)j的概率用PR（t），PG（t），PB（t）表示，它們是狀態(tài)概率向量的三個(gè)分量，有P（t）＝［PR（t），PG（t），PB（t）］。對于個(gè)體機(jī)器人處于狀態(tài)j的概率Pj（t）而言，控制其演化的是馬爾可夫鏈ξ（t）的主方程，它是一個(gè)“增益—損失”方程，其形式由公式（2）給出：

對公式（2）的右邊乘以系數(shù)ε，可以控制機(jī)器人狀態(tài)轉(zhuǎn)移的速率，再將（2）寫成一階微分方程組的形式，得到公式（3）：

為了運(yùn)算方便，將（3）寫成矩陣方程形式，由公式（4）給出：

3.3 轉(zhuǎn)移速率矩陣

轉(zhuǎn)移速率應(yīng)該反映第z種（z∈I）任務(wù)在全體任務(wù)中的比例信息，將到達(dá)狀態(tài)z的轉(zhuǎn)移速率簡稱為qz，即qz∝Mz／M0。機(jī)器人用局部估計(jì)Kloc＝｛mR，mG，mB｝代替全局知識Kglobal＝｛MR，MG，MB｝。假設(shè)在任意時(shí)刻的真實(shí)歷史窗口｛mR，mG，mB｝，都能在描述所有可能觀察實(shí)例的分布中找到其對應(yīng)的概率，我們對隨機(jī)主方程取關(guān)于全部歷史的平均運(yùn)算，此時(shí)對多機(jī)器人系統(tǒng)中的任意一個(gè)機(jī)器人，當(dāng)主方程變?yōu)楹暧^的速率方程（rate equation）［17，21］時(shí)，我們可以對其求解。描述所有可能觀察的分布是由一個(gè)聯(lián)合概率密度函數(shù)（joint pdf）定義的，由公式（1）給出。我們對公式（4）取關(guān)于所有歷史的平均［17，21］，得到公式（5）：

為了求解公式（6）中的a，b，c，我們定義輔助函數(shù)F（x，z）：

對于公式（7），我們先對F（x，z）求導(dǎo)再求積分可以得到F（x，z）的另一種表達(dá)式：

將x＝1，0分別代入由公式（7）和公式（8）給出的F（x，z）兩種表達(dá)式，再相減，就可以得到a，b，c的解：

其中假設(shè)Mz不隨時(shí)間改變，令Mz是工作場中任務(wù)總數(shù)量，則有，并且μz是任務(wù)z在M0中的初始比例。因此（5）中轉(zhuǎn)移速率矩陣的形式為：

3.4 狀態(tài)概率向量的解

為了求解矩陣指數(shù)函數(shù)Φ（t）＝eεwt，接下來我們證明W＝PDP-1并且D是可對角化矩陣，Φ（t）是馬爾可夫鏈ξ（t）的狀態(tài)轉(zhuǎn)移矩陣。

引理3.4［22］：對于具有任意階數(shù)的矩陣，如果每個(gè)特征根的代數(shù)重?cái)?shù)等于其幾何重?cái)?shù)，該矩陣是可對角化矩陣。

定理3.4：對于矩陣W，總存在有一個(gè)可逆矩陣P和一個(gè)對角矩陣D，并且有P-1WP＝D，其中

證明：W的特征方程為det（λE-W）＝λ（λ＋a＋b＋c）2＝0，因此W有兩個(gè)不同的特征根λ1＝0，λ2＝-（a＋b＋c）。λ1的代數(shù)重?cái)?shù)是m1＝1，其幾何重?cái)?shù)是d1＝n-rank（λ1E-W）＝3-2＝1，因此m1＝d1。同理λ2的代數(shù)重?cái)?shù)是m2＝2，其幾何重?cái)?shù)是d2＝n-rank（λ2E-W）＝3-1＝2，因此m2＝d2。由引理3.4可得W是可對角化矩陣。接下來我們推導(dǎo)矩陣P的形式。因?yàn)榫仃嘍的對角元素是矩陣W的特征根，并且P由三個(gè)線性無關(guān)的特征向量按相應(yīng)特征值的順序排列組成。對于λ1＝0特征向量為，該特征向量的特征空間E1具有一個(gè)基η1。對于λ2＝-（a＋b＋c）特征向量為，該特征向量的特征空間E2具有兩個(gè)基η2，η3。令t1＝1，有λ1的特征向量t1η1，其為P的一個(gè)列向量。令，將的兩組值分別代入向量乘法，可以構(gòu)造λ2的兩個(gè)線性無關(guān)的特征向量。因此將對應(yīng)于λ1和λ2的三個(gè)線性無關(guān)的特征向量按順序排可得矩陣P的三個(gè)列向量，因此矩陣：

所以P-1WP＝D。證畢

狀態(tài)轉(zhuǎn)移矩陣Φ（t）＝eεwt表示P（0）到P（t）的轉(zhuǎn)移矩陣。將矩陣P和P-1的表達(dá)式代入Φ（t）的計(jì)算式中我們可以得到：

令P（0）＝［x0y0z0］，將公式（12）代入公式（11），可得狀態(tài)概率向量的解析表達(dá)式：

3.5 穩(wěn)態(tài)分析

狀態(tài)轉(zhuǎn)移矩陣Φ（t）的不變分布為：

由公式（13）知馬爾可夫過程ξ（t）的極限分布為：

推論3.5：模型的可擴(kuò)展性。下面說明所提出的用于任務(wù)分配的多機(jī)器人系統(tǒng)宏觀模型具有可擴(kuò)展性。設(shè)有六種類型的任務(wù)，則任務(wù)集合為J：｛1，2，3，4，5，6｝，此時(shí)聯(lián)合密度函數(shù)（1）可擴(kuò)展為。到達(dá)狀態(tài)j的轉(zhuǎn)移速率為，且，對于任務(wù)集合J由（5）擴(kuò)展可得：

用定理3.4的方法可以算得狀態(tài)轉(zhuǎn)移矩陣

令P（0）＝［x1…xj…x6］，狀態(tài)概率向量為：

4 仿真實(shí)驗(yàn)

將多機(jī)器人系統(tǒng)所承擔(dān)的工作具體化為機(jī)器人“將不同種類物體按比例歸置在指定地點(diǎn)”，其中任務(wù)類型為三種，有m＝3，用‘R，G，B’表示，即任務(wù)集合為｛R，G，B｝，任務(wù)總數(shù)為M0。假設(shè)機(jī)器人的工作場景如圖1所示，場地中任務(wù)的類型由場地內(nèi)圓圈的大小區(qū)分（具體有，R類任務(wù)——最小號圓圈，B類任務(wù)——最大號圓圈，G類任務(wù)——中號圓圈）。場地內(nèi)共有n0個(gè)機(jī)器人，記作Robot1到Robot n0。狀態(tài)轉(zhuǎn)移函數(shù)的值由公式（18）給出。依此，機(jī)器人選擇三種類型任務(wù)中的一種，獲取后放置在歸置地點(diǎn)Sm，其中歸置地點(diǎn)與任務(wù)類型的對應(yīng)關(guān)系為S1→R，S2→G，S3→B。當(dāng)在場地中有一個(gè)任務(wù)被機(jī)器人獲取放置在歸置地點(diǎn)之后，場外機(jī)器人Robot0（機(jī)械臂）會放置一個(gè)相同類型的任務(wù)在場地中，因此工作場內(nèi)的各任務(wù)總數(shù)M0是維持不變的。機(jī)器人系統(tǒng)的目標(biāo)介紹如下：在系統(tǒng)達(dá)到穩(wěn)衡態(tài)之后任意足夠長的時(shí)間段T內(nèi)，機(jī)器人系統(tǒng)按P（t）的穩(wěn)恒值將不同類型的任務(wù)歸置在指定地點(diǎn)Sm，其數(shù)量為，總數(shù)為N0。給定工作時(shí)間T，系統(tǒng)可以產(chǎn)生三個(gè)任務(wù)歸置組，或各歸置組的混合（T，N0）作為分配結(jié)果，其中N0既可以比M0小，也可以是比M0大很多的值，理想分配結(jié)果是當(dāng)T→∞時(shí)，有。

在MATLAB環(huán)境下開發(fā)了仿真器，對于三種類型的任務(wù)，所有機(jī)器人都具有相同的感知能力和任務(wù)執(zhí)行能力。每個(gè)機(jī)器人都通過局部觀察將任務(wù)類型存儲在長度為h的歷史窗口內(nèi)。假設(shè)兩次觀察之間的時(shí)間間隔Tob＝10s，因此狀態(tài)轉(zhuǎn)換率為ε＝1／Tob＝0.1。由物理硬件決定的機(jī)器人感知范圍的參數(shù)α＝0.05。由于機(jī)器人沒有關(guān)于任務(wù)數(shù)量的全局知識Mz（z∈I），它們使用歷史窗口收集的局部估計(jì)值mz來計(jì)算轉(zhuǎn)移方程的值：

圖1 多機(jī)器人“按比例歸置”任務(wù)的工作場景示意圖

在實(shí)驗(yàn)中機(jī)器人的個(gè)數(shù)m0＝30。將所有機(jī)器人看做一個(gè)整體，計(jì)算每秒屬于任務(wù)狀態(tài)z（z∈I）的機(jī)器人在m0的即時(shí)比例，記作Pz（t），其中是屬于任務(wù)狀態(tài)z的機(jī)器人數(shù)量，Pz（t）是公式（13）中矢量P（t）的分量。在實(shí)驗(yàn)中三種任務(wù)的數(shù)量設(shè)置為（MR，MG，MB）＝（25，15，5），歷史窗口長度h＝50，機(jī)器人總數(shù)為m0＝30，實(shí)驗(yàn)總共進(jìn)行了十次，每次持續(xù)10000秒。比例結(jié)果的值由圖2給出。圖2（a）是十次實(shí)驗(yàn)的平均結(jié)果圖，其中三條軌跡實(shí)線按從上到下的順序依次是R-robot，G-robot和B-robot（z-robot表示處于任務(wù)狀態(tài)z也就是要執(zhí)行第z種任務(wù)的機(jī)器人）在m0中所占比例的實(shí)驗(yàn)值，三條虛線分別代表它們相應(yīng)的理論值，由公式（13）計(jì)算得到。圖2（b）是實(shí)驗(yàn)前2000秒的數(shù)據(jù)圖，每100秒繪制一個(gè)誤差棒，代表10次實(shí)驗(yàn)的標(biāo)準(zhǔn)差。實(shí)驗(yàn)軌跡P′z（t）對理論軌跡Pz（t）有較好的逼近效果，當(dāng)t→∞時(shí)機(jī)器人處于任意狀態(tài)的概率值等于任務(wù)的初始比例，即，達(dá)到了理想分配結(jié)果。

圖2 R-robot，G-robot和B-robot在總體中所占比例隨時(shí)間變化的軌跡，h＝50，m0＝30，（MR，MG，MB）＝（25，15，5）

5 結(jié)束語

運(yùn)用包括隨機(jī)過程、矩陣論和線性代數(shù)等數(shù)學(xué)方法建立自組織多機(jī)器人系統(tǒng)的任務(wù)分配模型，克服了現(xiàn)存模型對任務(wù)類型數(shù)無可擴(kuò)展性的缺點(diǎn)。以時(shí)間離散狀態(tài)連續(xù)的馬爾科夫鏈的極限分布作為任務(wù)分配的理論結(jié)果，證明了新模型具有一般性和正確性，可以預(yù)測機(jī)器人系統(tǒng)長期的穩(wěn)定行為。不但從理論上證明了任務(wù)分配模型可以達(dá)到理想的分配結(jié)果，仿真實(shí)驗(yàn)結(jié)論也說明了任務(wù)分配模型的有效性和正確性，能達(dá)到任務(wù)分配的目的——保持執(zhí)行任意一種任務(wù)的機(jī)器人數(shù)量占機(jī)器人總數(shù)的比例與該種任務(wù)所占總?cè)蝿?wù)量的比例相等。

［1］Maja JMatari，Gaurav S Sukhatme，Esben H stergaard.Multi-Robot Task Allocation in Uncertain Environments［J］.Autonomous Robots，2003，14（2-3）：255-263.

［2］Gerkey B P，Mataric M J.A formal analysis and taxonomy of task allocation in multi-robot systems［J］.Intl.Journal of Robotics Research，2004，23（9）：939-954.

［3］原魁，李園，房立新.多移動(dòng)機(jī)器人系統(tǒng)研究發(fā)展近況［J］.自動(dòng)化學(xué)報(bào)，2007，33（8）：785-794.

［4］Gerkey B P，Mataric M J.Multi-robot task allocation：analyzing the complexity and optimality of key architectures［C］.In Proc.of the IEEE Intl.Conference on Robotics and Automation，Taipei，Taiwan，Piscataway，New Jersey，USA，IEEE Press，2003.

［5］JAlonso-Mora，A Breitenmoser，M Rufli，et al.Multi-Robot System for Artistic Pattern Formation［C］.In Proc.of the IEEE Intl.Conference on Robotics and Automation，Shanghai，China，Piscataway，New Jersey，USA，IEEE Press，2011.

［6］LLiu，D A Shell.Assessing Optimal Assignment under Uncertainty：An Interval-based Algorithm［J］.Intl.J.Robotic Res.，2011，30（7）：936-953.

［7］Chris Jones，Dylan Shell，Maja JMataric，et al.Principled Approaches to the Design of Multi-Robot Systems［C］.In Proc.of IEEE／RSJ Intl.Conference on Intelligent Robots and Systems，Sendai，Japan，Piscataway，New Jersey，USA，IEEE Press，2004.

［8］Kalra N，F(xiàn)erguson D，Stentz A.Hoplites：amarket-based framework for planned tight coordination in multi-robot teams［C］.In Proc.of the Intl.Conf.on Robotics and Automation，Barcelona，Spain，Piscataway，New Jersey，USA，IEEE Press，2005.

［9］Kose H，Tatlidede U，Mericli C，et al.Q-learning based market-drivenmulti-agent collaboration in robot soccer［C］.In Proc.of the Turkish Symposium on Artificial Intelligence and Neural Networks，Izmir，Turkey，Piscataway，New Jersey，USA，IEEE Press，2004.

［10］D P Bertsekas.Auction Algorithms for network flow Problems：A tutorial introduction［J］.Computational Optimization and Applications，1992，1（1）：7-66.

［11］M Rubenstein，A Cabrera，JWerfel.Collective Transport of Complex Objects by Simple Robots：Theory and Experiments［C］.12th International Conference on Autonomous Agents and Multi-agent Systems 2013（AAMAS 2013），Saint Paul，Minnesota，USA，Red Hook，NY.，USA，Curran Associates，Inc.，2013.

［12］JDeneubourg，S Aron，SGoss，et al.The self-organizing exploratory pattern of the Argentine ant［J］.Journal of Insect Behavior，1990，3（2）：159-168.

［13］C R Kube，H Zhang.Collective robotic intelligence［C］.In Proc.of the Second Intl.Conference on Simulation of Adaptive Behavior On From animals to animats，Cambridge，MA，USA，MIT Press，1992.

［14］CR Kube，H Zhang.Stagnation recovery behaviours for collective robotics［C］.In Proc.of IEEE International Conference on Intelligent Robots and Systems，Munich，Germany，Piscataway，New Jersey，USA，IEEE Press，1994.

［15］K Lerman，A Galstyan.Macroscopic analysis of adaptive task allocation robots［C］.In Proc.of the 2003 IEEE／RSJ Interactional Conference on Intelligent Robots and Systems，Las Vegas，Nevada，USA，Piscataway，New Jersey，USA，IEEE Press，2003.

［16］Kristina Lerman，Aram Galstyan.Mathematicalmodel of foraging in a group of robots：Effect of interference［J］.Autonomous Robots，2002，13（2）：127-141.

［17］K Lerman，M J Mataric.Analysis of Dynamic Task Allocation in Multi-Robot Systems［J］.Intl.Journal of RoboticsResearch，March 2006，25（3）：225-241.

［18］A Martinoli，K Easton.Modeling swarm robotic systems［C］.Experimental Robotics VIII：Proceedings of the 8th International Symposium on Experimental Robotics（ISER 02），Sant Angelo，Italy，Springer-Verlag，Berlin Heidelberg，2003.

［19］W Agassounon，A Martinoli.A macroscopic model of an aggregation experiment using embodied agents in groups of time-varying sizes［C］.In Proc.of the IEEE Conf.on System，man and Cybernetics SMC-02，Hammamet，Tunisia，Piscataway，New Jersey，USA，IEEE Press，2002.

［20］董煬斌.多機(jī)器人系統(tǒng)的協(xié)作研究［D］.浙江：浙江大學(xué)，2006.

［21］A Galstyan，K Lerman.Analysis of a stochastic model of adaptive task allocation in robots［J］.Engineering Self-Organising Systems：Methodologies and Applications，2005：167-179.

［22］David Poole.Linear Algebra：A Modern Introduction 3rd Ed［M］.Pacific Grove，California，United States，Brooks／Cole，May 25，2010.

Study on Probability Model of Multi-robot System on Task Allocation

ZHOU Jing，MU De-jun
（School of Automation，Northwestern Polytechnical University，Xi’an 710072，China）

The macroscopic probability modeling is a new way to describe and analyze the selforganizingmulti-robot system.Themathematicalmethod of stochastic process theory，matrix theory and linear algebra are used tomodel the task allocation of self-organizingmulti-robot system and overcome the drawbacks of existing models，which has no scalability to the number of task types.The limit distribution of state-discrete time-continuous Markov chain is used as the theoretical result of task allocation，which takes advantage of predicting long-term behavior of robot system.The purpose of task allocation is to keep the proportion of the robots in arbitrary tasks to total robots being equal to that of performed tasks to total tasks.The simulation results show that the macroscopic probability model for multi-robot task allocation can complete the desired assignment of tasks.

Multi-robot system；Task allocation；Probabilitymodeling

10.3969／j.issn.1002-2279.2014.03.022

TP242

：A

：1002-2279（2014）03-0077-07

國家自然科學(xué)基金（61203233）；航空科學(xué)基金（2012ZC53042）；教育部高校博士點(diǎn)基金（20126102110036）

周菁（1983-），女，西安市人，博士研究生，主研方向：智能機(jī)器人，控制科學(xué)與工程。

2014-01-20