基于當代學習離散粒子群算法的多機器人任務分配

(中南大學 信息科學與工程學院 長沙 410083)

摘 要：針對多機器人協(xié)同控制中的任務分配問題，首先綜合考慮機器人完成任務的效率、機器人自身能力以及任務本身性質各因素，建立了多機器人任務分配的數(shù)學模型。而后提出一種基于當代學習機制的離散粒子群算法進行高效求解，該算法設計了準確的粒子運動方程，并加入擾動算子保持粒子多樣性，使其迅速跳出局部最優(yōu)，增加了算法空間探索能力。實驗結果表明：在小規(guī)模任務數(shù)情況下，算法能精確尋到最優(yōu)，穩(wěn)定性表現(xiàn)極佳且優(yōu)于現(xiàn)有算法。在中大規(guī)模任務數(shù)情況下算法也表現(xiàn)出強尋優(yōu)能力，實驗驗證了模型的合理性和算法的優(yōu)越性。

關鍵詞：多機器人； 離散粒子群； 任務分配； 擾動因子

中圖分類號：TP242文獻標志碼：A

文章編號：1001-3695(2009)05-1691-04

Multirobot mission assignment based on current learning

discrete particle swarm optimization algorithm

YU Lingli CAI Zixing

(School of Information Science Engineering Central South University Changsha 410083 China)

Abstract:Multirobot mission assignment mathematical model was established firstly which considered three factors comprehensively: executing mission efficiency robot ability and mission properties. This paper proposed current learning discrete particle swarm optimization algorithm(CLDPSO) to solve multirobot mission assignment with highly efficiently. The algorithm designed an exact particles kinetic equation. When decreased algorithm diversity to a certain threshold，added a perturbation operator to jump out local optimum quickly and to improve the search ability. The experiment results show that CLDPSO can reach the best result and its stability is the best among existing algorithms when the number of missions is small scale. When the number of missions is middle or large scale the searching optimization ability is also strong. Those experiments prove that the model is reasonably and CLDPSO algorithm is the advantage.

Key words：multirobot; current learning discrete particle swarm; mission assignment; perturbation factor

0 引言

多機器人任務分配系統(tǒng)目的是試圖讓多個機器人通過協(xié)作，來完成單個機器人無法完成的任務，并提高完成任務的總體性能，所以在國防和經(jīng)濟建設中具有廣泛的應用前景。任務分配的各種模型和方法相繼涌現(xiàn)，為簡化多機器人系統(tǒng)任務分配問題的求解，國內外學者常常應用一些技術將問題分解或轉換成一個或幾個已經(jīng)研究過的基本問題，再采用相對比較成熟的基本理論和方法，以得到最優(yōu)解或滿意解。這些基本理論和方法有：基于市場機制的任務分配方法，以經(jīng)濟理論為基礎的市場效率觀點，通過價格浮動反映資源供需狀況的動態(tài)變化，供需均衡實現(xiàn)優(yōu)化分配。Liu等人^[1]采用市場機制設計了一種對于松散合作任務進行分配的方法，并討論了機器人、任務數(shù)目以及與任務完成時間的關系。另外，基于市場機制的任務分配算法文獻[2~5]也相繼提出。基于合同網(wǎng)協(xié)議的任務分配方法，主要思想是使用通信手段對每一問題的求解進行協(xié)商，避免沖突。為提高多機器人任務分配方法的通用性和實用性，根據(jù)多機器人任務特點，文獻[6]提出了分布式多機器人協(xié)作任務分配策略。Parker^[7]在MIT開發(fā)了一種基于行為的多機器人分布式合作結構ALLICANCE以及相應具有參數(shù)學習能力的系統(tǒng)LALLICANCE^[8]，采用基于激勵行為的任務分配機制，提高了多機器人系統(tǒng)的通用性和容錯性。文獻[9]中，針對機器人和任務都具有異構性質，并在執(zhí)行的過程中可能動態(tài)產(chǎn)生新任務的問題，提出了一種形式化描述的方法。Murphy等人^[10]提出利用情感計算模型在傳感—馬達級(反應式)修改主動行為，從而無須集中規(guī)劃即可產(chǎn)生團隊的社會行為，并極大降低了通信需求。Matchell^[11]提出的基于自然界中物種協(xié)進化機制的協(xié)作協(xié)進化方法有可能獲得優(yōu)化的任務分配性能。當多機器人任務分配是一類規(guī)模很大的組合優(yōu)化問題時，難以在規(guī)定時間內獲得問題的最優(yōu)解，同時多機器人任務分配的強耦合性也增加了問題求解的難度。因此本文利用群智能仿生算法解決多機器人任務分配問題。

社會性動物的妙處在于個體的行為很簡單，但當它們協(xié)同工作時，卻能夠突現(xiàn)出非常復雜的智能行為特征。粒子群優(yōu)化算法主要模擬鳥集群飛行覓食行為，通過鳥群的集體協(xié)作達到尋優(yōu)目的。首先由Kennedy等人^[12]提出，在PSO算法中每個粒子利用自身、歷史最優(yōu)位置和整個粒子群的全局最優(yōu)解提供的信息，在解空間內不斷飛行，實現(xiàn)尋找最優(yōu)解的目的。粒子群優(yōu)化算法已成功地應用于求解連續(xù)域問題，但對離散域特別是路由規(guī)劃和組合優(yōu)化問題研究的卻還不多。文獻[12]提出了一種離散的二進制版本的PSO，定義粒子速度為“粒子位置的改變概率”，此方法表明經(jīng)過改造的PSO算法解決了離散函數(shù)的優(yōu)化問題。Clerc^[13]針對TSP問題實現(xiàn)了一個具體的DPSO算法，定義速度為交換的列表，并對其他量及運算法則進行了定義，但沒有考慮離散量運算規(guī)律的不同，與其他算法相比仍有較大的差距。文獻[14~16]也利用了交換列表的規(guī)律，并定義了不同的離散量運算規(guī)則，但由于缺少增加局部搜索能力的思考，算法僅在小維數(shù)TSP問題上作了仿真。但其算法已表現(xiàn)出很強的進化特征，證明了PSO在求解離散優(yōu)化問題的可行性。離散粒子群算法也可以視為變異與交叉的結合體，同時也可混入模擬退火的思想，在一定閾值內也可接受變壞解^[17，18]。本文提出了一種基于當代學習能力的新型粒子群進化方程，使得算法穩(wěn)定性增強；當多樣性低于閾值時加入了擾動算子，使其迅速跳出局部最優(yōu)，高效地找到多機器人任務分配的最優(yōu)解。

1 多機器人協(xié)同任務分配的數(shù)學模型

假設m個機器人R1，R2，…，Rm需要完成n個任務點T1，T2，…，Tn（m≤n），第i個機器人最多可以完成ri(i=1，2，…，m)個任務，而任務Tj最多只需sj(j=1，2，…，n)個機器人來完成；由于完成任務具有一定的風險性，設機器人Ri能成功完成任務Tj的概率為pij(i=1，2，…，m; j=1，2，…，n)，求取最佳的任務分配方式，使得機器人完成全部任務的失敗概率最小？

min F=∑nj=1∏mi=1(1-pijxij)

（1）

s.t. ∑nj=1xij≤ri；i=1，2，…，m（2）

∑mi=1xij≤sj； j=1，2，…，n（3）

設定如果分配了機器人i完成任務j時則xij=1；否則xij=0。當ri=1(i=1，2，…，m)，sj=1(j=1，2，…，n)時上述問題轉換為指派問題。對于一般的優(yōu)化問題，實質是非線性整數(shù)規(guī)劃問題，屬于NPhard問題。又因為有了式（2）（3）的約束條件，此問題轉換為帶約束條件的組合優(yōu)化問題，所以對多機器人協(xié)同任務分配問題求解提出了更

高的要求。

2 求解多機器人協(xié)同任務分配問題的當代學習粒子群算法

粒子群優(yōu)化算法每次迭代中，所有粒子移動搜索全局最優(yōu)解，粒子的速度和位置由式（4）（5）更新式確定。

Vt+1i=ωVti+C1r and()(Pti-Xti)+C2r and()(Ptg-Xti)

(4)

Xt+1i=Xti+Vt+1i(5)

粒子群優(yōu)化算法已成功應用于求解連續(xù)域問題，但對于離散域特別是分配規(guī)劃問題的研究還比較少。本文將DPSO運算規(guī)則形象地理解為圖1矢量形式：兩位置相減得到一個速度如圖1(a)；速度的數(shù)乘產(chǎn)生另外一個速度如圖1(b)；兩個速度的相加得到另一個速度如圖1(c)；位置與速度相加，即位置的移動，得到一個新的位置如圖1(d)所示。

本文基于粒子群成功的社會學習能力和個體學習能力，提出粒子群當代學習能力以改進DPSO運動方程，使算法穩(wěn)定性得到較大改進。當多樣性低于閾值時加入了擾動算子使其易跳出局部最優(yōu)，保持個體的進化能力。

1)位置的定義 本文在位置編碼方式上盡量滿足約束條件式（2）（3），這樣可以簡化將式（1）~（3）轉換為罰函數(shù)形式如式（6）的計算難度。本文定義粒子位置x是∑i×ri個自然數(shù)的一個排列(i=1 2，…，m)，直接表示一個可行解或是一種多機器人的任務分配方案。

min ∑nj=1∏mi=1(1-pijxij）+M∑mi=1[min(0，ri-∑nj=1xij)]2+

N∑nj=1[min(0，sj-∑mi=1xij)]2 (6)

2）粒子速度的定義 速度v是一個與位置同維的向量，其作用是改變粒子的位置。

3）速度的數(shù)乘運算 本文定義V=c1V c2，把維看做是循環(huán)數(shù)據(jù)，左乘c1表示從c1位置開始，右乘c2表示至c2上一位置結束，在這之間的維的速度取原有值，其余位置值為0。c1c2為隨機產(chǎn)生的數(shù)（c2>c1），把V視為一個循環(huán)鏈表。當c1為速度最后維數(shù)據(jù)時，c2等價于c2-k×length (V)。這就使粒子速度均衡地向最佳方向飛行，也免去了c參數(shù)選取所帶來的問題，可以用式（7）表示速度數(shù)乘的運算規(guī)則。

vi=vii∈[c1，c2)0其他（7）

4）位置與速度的加法運算 該運算體現(xiàn)了粒子位置的變化，使粒子進入到一個新的位置。新位置的操作可由式（8）決定。 

swap(xi，vi) vi≠0vi=0(8)

5）位置的減法運算 兩位置相減得到一個速度，可以用式（9）來表示： 

vi=0x1，i=x2，ix2其他（9）

6）速度的加法運算 兩個速度相加得到一個新的速度，v=v1+v2。其中vi分量定義為式（10），因此速度加法不再滿足交換律。

vi=vli(vli≠0 v2i-0)‖(v1i≠0 V2i≠0 rand＜0.5)v2i 其他（10）

7）融入當代學習的粒子運動方程 從社會心理學的觀點來看，學習因子C1表示個體學習自身成功行為的能力，稱為認知因子；C2表示學習社會成功行為的能力，稱為社會因子，它們保證搜索到Pbest和lbest為中心的領域所有范圍。研究測試了兩種極端情況，即單社會模型和單認知模型，發(fā)現(xiàn)這兩個因子對DPSO算法成功搜索到最優(yōu)值都是必需的。本文利用每次迭代過程中每一代的最優(yōu)值Cbest(current best)，再次影響搜索的效果，C3表示學習當代潮流成功行為的能力，稱為時代因子。實現(xiàn)方法是進一步改進粒子運動方程，如式(11)所示，新定義一個當前代粒子最優(yōu)位置Pct，使得粒子在向當前代的最優(yōu)值進行逼近同時也向個體最優(yōu)和全局最優(yōu)逼近靠攏。另外，由于DPSO的特殊性，采用分段計算方式會比式(12)(13)的效果好，因為速度對位置上的各維數(shù)據(jù)的作用會互相影響。

X′t=Xt+ωVt

X″t=X′t+C3(Pct-X′t)

Xt=X″t+C1(Plt-X″t)

Xt+1=Xt+C2(Pgt-Xt)（11）

vt+1=[wkvt] [c3(Pc，tΘPt] [c1(Pl，tΘ Pt)]

[c2(Pg，tΘPt)] (12)

xt+1=xt(wkvt+1)（13）

8）求解多機器人協(xié)同任務分配的當代學習離散粒子群算法步驟 a）設定粒子數(shù)nParticle ，最大迭代次數(shù)maxIteration，設置機器人數(shù)nRobot及每個機器人最多能完成的任務數(shù)ri。定義概率矩陣Peff，隨機產(chǎn)生粒子的初始位置和初始速度使其滿足式(2)(3)約束條件，即進行可行解的初始化。b)根據(jù)概率矩陣Peff計算出式（1）當前位置的適應值fitness（多機器人協(xié)同任務分配問題的解矩陣X=(xij)m×n可根據(jù)位置的編碼順序來定，機器人i對應ri個編碼位置，機器人i完成任務數(shù)如果小于ri，則其他位補0或其他標志符。X只表示任務j分配給第i個機器人，不代表完成任務的先后順序）；設置當前適應值為個體極值particle_best，當前極值位置為particle_ best_pos。根據(jù)各個粒子個體極值計算全局極值global_best與位置global_best_pos。c)設置最大迭代次數(shù)maxIteration，進入迭代循環(huán)。對當前每一個粒子，按照以上四種運算規(guī)則和融入當代學習的粒子運動方程（11）的順序進行運算。d)根據(jù)當前位置curSwarm計算fitness的值。e)計算各個粒子的多樣性。如果各粒子多樣性小于0.2，加入擾動算子，即隨機產(chǎn)生新的速度，加入到當前位置，避免過早進入局部最優(yōu)。f)更新各個粒子最優(yōu)值particle_ best，找出最優(yōu)值相應位置particle_best_pos。根據(jù)各粒子的極值，找出全局極值global_best和位置global_best_ pos。g)計算每次迭代粒子群的平均多樣性。curIteration=curIteration+1。h)輸出結果，畫出任務分配示意圖。

3 算法測試與分析

3.1 小規(guī)模任務分配與其他算法比較

設有4個機器人分配6個任務T1，T2，…，T6，每個機器人最多完成（2，1，2，1）個任務，對每個任務最多需要1個機器人來完成即可。任務成功完成概率Pij如表1所示。

基于當代學習的離散粒子群算法設置參數(shù)為nParticle= 30，maxIteration=50，進行100次測試，結果如表2所示。

本文推薦的算法對小規(guī)模的任務分配問題穩(wěn)定性極佳，而且能高效尋求到分配最優(yōu)值，優(yōu)于文獻[18]中的最佳算法。圖2說明最優(yōu)解迭代中算法的收斂變化情況。圖3是這次迭代中的多樣性情況分析，可看出多樣性均大于0.2。

3.2 中大規(guī)模任務分配算法的實現(xiàn)

對中大規(guī)模的任務分配問題進行仿真驗證，本文選用標準TSP庫中標準測試數(shù)據(jù)eil51和eil101進行測試和分析，總任務數(shù)分別為51和101個，若設機器人數(shù)目nRobot均為4個，初始位置設為[20，20][30，30][40，40][50，50]，每個任務最多只需1個機器人完成；設其完成任務成功概率Pij可以如式(14)(15)定義，設離機器人越遠的任務完成的概率越小，設Dmax表示機器人i與所有任務間最大的距離，dij為機器人i與任務j的距離。多機器人協(xié)同任務分配是個實際問題，所以將Pij的范圍歸一化到經(jīng)驗值0.4~0.9，如式(15)所示。當代學習離散粒子群算法設置參數(shù)為nParticle= 50，maxIteration=500，進行了10次測試，結果如表3所示。圖4與5分別為51個任務和101個任務時當代學習離散粒子群算法迭代收斂過程；圖6和7分別為51個任務和101個任務時當代學習離散粒子群算法迭代的多樣性，可知在迭代后期粒子仍保持一定的多樣性；圖8和9為多機器人任務分配結果。其中同種形狀為一組任務分配結果，大型號圖形為機器人初始坐標，可看出分配結果符合一般實際需求。表3為當代學習離散粒子群算法求解大規(guī)模任

4 結束語

本文針對多機器人協(xié)同控制中的任務分配問題進行數(shù)學建模，所建立模型綜合考慮了機器人完成任務的成功概率、機器人自身能力（即該機器人最多能完成幾個任務）以及任務本身的性質（該任務最多需要幾個機器人完成）等因素。設計出比較準確的表達方式，使得粒子與可行解對應，提出了當代學習離散粒子群協(xié)同任務分配算法。該算法適用于任務數(shù)n=∑i×ri(i=1，2，…，m)的情況，亦可適用于n≠∑i×ri(i=1，2，…，m)情況，只需對編碼方式進行改進。本文研究的任務分配模型和算法可以直接應用于集中式多機器人協(xié)同控制中，模型合理有效，算法簡單易于實現(xiàn)，且CLDPSO算法能在運行的任意時刻中止，得到當前最優(yōu)的可行解，這使得算法能夠適應于尋求可行解而非最優(yōu)解的實時或近實時任務分配問題中。

參考文獻：

［1］LIU L WANG L ZHENG Z Q et al. A learning market based layered multirobot architecture[C]//Proc ofIEEE International Conference on Robotics and Automation.Piscataway:IEEE Press，2004:3417-3422.

[2]DIAS M B STENTZ A. Opportunistic optimization for marketbased multirobot control[C]//Proc ofInternational Conference on Intelligent Robots and Systems. Lausanne Piscataway NJ:IEEE Press 2002: 2714-2720.

[3]STENTZ A DIAS M B. A free market architecture for coordinating multiple robots[R]. Pittsburgh:Robotics Institute Carnegie Mellon University 1999.

[4]DIAS M B STENTZ A. A market approach to multirobot coordination[R]. Pittsburgh:Robotics Institute Carnegie Mellon University 2001.

[5]ZLOT R STENTZ A DIAS M B，et al. Multirobot exploration controlled by a market economy[C]//Proc of IEEE International Conference on Robotics and Automation. Washington DC:IEEE Press 1999:3016-3023.

[6]董煬斌，蔣靜坪，何衍.基于適應度的多機器人任務分配策略[J].浙江大學學報：工學版，2007，41(2):272-277.

[7]PARKER L E. LAllicance: taskoriented multirobot learning in behavior based systems[J]. Advanced Robotics 1997，11(4):305-322.

[8]PARKER L E. Alliance: an architecture for fault tolerant multirobot cooperation[J]. IEEE Trans on Robotics and Automation 1998，14(2):220-240.

[9]柳林，季秀才，鄭志強.基于市場法及能力分類的多機器人任務分配方法[J].機器人 2006 28(3):337-343.

[10]MURPHY LISETTI IRISH et al. Emotionbased control of cooperating heterogeneous mobile robots[J]. IEEE Trans on Robotics and Automation 2002，18(5):744-757.

[11]POTTER M A De JONG K A. A cooperative coevolutionary approach to function optimization[C]//Parallel Problem Solving from Nature. London UK: SpringerVerlag，1994: 249-257.

[12]KENNEDY J EBERHART R C. A discrete binary version of the particle swarm algorithm[C]//Proc ofWorld Multi Conference on Systemic Cybernetics and Informatics.Piscataway，NJ: IEEE Service Center 1997:4104-4109.

[13]CLERC M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization[C]//Proc ofIEEE Congress on Evolutionary Computation. Washington DC:IEEE Press 1999:1951-1957.

[14]黃嵐，王康平，周春光，等. 粒子群優(yōu)化算法求解旅行商問題[J].吉林大學學報:理學版，2003，41(4):477-480.

[15]肖健梅，李軍軍，王錫淮. 改進微粒群優(yōu)化算法求解旅行商問題[J]. 計算機工程與應用，2004，35：50-52.

[16]王翠茹，張江維，王明，等. 改進粒子群優(yōu)化算法求解旅行商問題[J]. 華北電力大學學報，2005，32(6):57-59.

[17]高尚，韓斌，吳小俊，等. 求解旅行商問題的混合粒子群優(yōu)化算法[J]. 控制與決策，2004，19(11)：1286-1289.

[18]高尚，楊靜宇. 武器—目標分配問題的粒子群優(yōu)化算法[J]. 系統(tǒng)工程與電子技術，2005，27(7)：1250-1253.

[19]JIN Y MINAI A A POLYCARPOU M M. Cooperative realtime search and task allocation in teams of UAVs[C]//Proc of the 42th IEEE Conference on Decision and Control. Hawaii USA:[s.n.] 2003:7-13.

[20]BLUM C ROLI A. Metaheuristics in combinatorial optimization: overview and conceptual comparison[J].ACM Computing Surveys 2003，35(3):268-308.

[21]鐘一文，才榮英. 求解二次分配問題的離散粒子群優(yōu)化算法[J]. 自動化學報，2007，33(8):871-874.