多機器人系統任務分配概率模型研究?

周 菁，慕德俊

（西北工業大學自動化學院，西安710072）

多機器人系統任務分配概率模型研究?

周 菁，慕德俊

（西北工業大學自動化學院，西安710072）

建立系統的概率模型是描述和分析自組織多機器人系統的一條新思路。運用包括隨機過程、矩陣論和線性代數等數學方法建立自組織多機器人系統的任務分配模型，克服了現存模型對任務類型數目無可擴展性的缺點。為了驗證模型的一般性和有效性，以時間離散狀態連續的馬爾科夫鏈的極限分布作為任務分配的理論結果，優點是可以預測多機器人系統任務分配的長期穩定行為。任務分配的目的是保持執行任意一種任務的機器人數量占機器人總數的比例與該種任務所占總任務量的比例相等。仿真實驗的結論也說明了任務分配模型可以達到理想的分配效果。

多機器人系統；任務分配；概率模型

1 引 言

作為多機器人系統（Multi-robot system，MRS）協作的重要研究內容之一，多機器人任務分配（Multi-robot task allocation，MRTA）要解決系統中機器人到子任務的對應關系問題，也就是說要決定分配機器人x去執行子任務y，以及確定分配給子任務y的機器人x的數量［1-2］。任務分配是整個多機器人系統通暢運行的基礎。如何在保障系統對任務目標的執行結果與效率的同時，避免由機器人之間或由機器人與環境之間產生沖突所造成的損失［3］是很多學者的興趣點，它對系統工作性能起到決定性影響，因此直接影響生產率。

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

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

2 自組織多機器人系統任務分配問題

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

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

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

3 多機器人系統宏觀模型

3.1 機器人的局部觀察

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

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

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

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

3.2 描述個體動態性的隨機主方程

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

對公式（2）的右邊乘以系數ε，可以控制機器人狀態轉移的速率，再將（2）寫成一階微分方程組的形式，得到公式（3）：

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

3.3 轉移速率矩陣

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

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

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

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

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

3.4 狀態概率向量的解

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

引理3.4［22］：對于具有任意階數的矩陣，如果每個特征根的代數重數等于其幾何重數，該矩陣是可對角化矩陣。

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

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

所以P-1WP＝D。證畢

狀態轉移矩陣Φ（t）＝eεwt表示P（0）到P（t）的轉移矩陣。將矩陣P和P-1的表達式代入Φ（t）的計算式中我們可以得到：

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

3.5 穩態分析

狀態轉移矩陣Φ（t）的不變分布為：

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

推論3.5：模型的可擴展性。下面說明所提出的用于任務分配的多機器人系統宏觀模型具有可擴展性。設有六種類型的任務，則任務集合為J：｛1，2，3，4，5，6｝，此時聯合密度函數（1）可擴展為。到達狀態j的轉移速率為，且，對于任務集合J由（5）擴展可得：

用定理3.4的方法可以算得狀態轉移矩陣

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

4 仿真實驗

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

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

圖1 多機器人“按比例歸置”任務的工作場景示意圖

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

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

5 結束語

運用包括隨機過程、矩陣論和線性代數等數學方法建立自組織多機器人系統的任務分配模型，克服了現存模型對任務類型數無可擴展性的缺點。以時間離散狀態連續的馬爾科夫鏈的極限分布作為任務分配的理論結果，證明了新模型具有一般性和正確性，可以預測機器人系統長期的穩定行為。不但從理論上證明了任務分配模型可以達到理想的分配結果，仿真實驗結論也說明了任務分配模型的有效性和正確性，能達到任務分配的目的——保持執行任意一種任務的機器人數量占機器人總數的比例與該種任務所占總任務量的比例相等。

［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］原魁，李園，房立新.多移動機器人系統研究發展近況［J］.自動化學報，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，Ferguson 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］董煬斌.多機器人系統的協作研究［D］.浙江：浙江大學，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

國家自然科學基金（61203233）；航空科學基金（2012ZC53042）；教育部高校博士點基金（20126102110036）

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

2014-01-20