王喜敏，袁 杰

(新疆大學 電氣工程學院，新疆 烏魯木齊 830017)

0 引言

針對多機器人協(xié)作任務規(guī)劃（Cooperative Multi-Robot Task Planning, CMRTP）問題，通過代價函數(shù)評價能夠使任務規(guī)劃結果獲取較大的系統(tǒng)效能，但必須考慮任務規(guī)劃結果的均衡性[1]，如果規(guī)劃過程中某個機器人的任務量過于繁重，將出現(xiàn)任務規(guī)劃失衡的情況，那么即使能夠獲取較大的整體效能，也會使部分機器人因任務量繁重而過早損壞，并且不利于系統(tǒng)整體執(zhí)行效率的提高.所以在滿足系統(tǒng)整體效能和移動機器人個體任務要求的基礎上，考慮機器人任務規(guī)劃的均衡性，盡量實現(xiàn)公平分配.機器人團隊高效完成整體任務時，需要平衡各機器人的工作，只專注最小化總代價往往會導致勞動力失衡，所以在協(xié)作團隊中滿足總距離最小時，最小化所有機器人最大距離同樣具有實際意義，否則會出現(xiàn)不正確的任務均衡效果.

現(xiàn)今對于CMRTP問題，熊衍捷等[2]為解決多通道資源負載均衡問題，提出基于NJW譜聚類的資源負載均衡調(diào)度算法，通過聚類劃分一定的簇數(shù)量，進行加權的K-means算法完成聚類等方法提高負載均衡度，這促使我們應用一種簡單的標準的聚類技術來解決多旅行商問題（Multiple Traveling Salesman Problem, MTSP）/均衡多機器人任務分配（Balanced Multi-Robot Task Allocation, BMRTA）問題.毛科技等[3]針對無線傳感器網(wǎng)絡的數(shù)據(jù)傳輸問題，提出能耗均衡的層次路由協(xié)議，通過劃分不同規(guī)模的簇，實現(xiàn)網(wǎng)絡能耗均衡.朱姍等[4]運用組合優(yōu)化和聚類分析理論來縮短求解空間的方法，為大規(guī)模超市中的訂單拆分問題提供了新思路.解決相關問題的同時提高求解效率，將不同算法進行融合來發(fā)揮算法的各自優(yōu)勢，克服或抑制各自的缺陷，實現(xiàn)算法優(yōu)勢互補.姚澤瑋等[5]針對移動設備多邊緣的負載均衡問題，提出粒子群遺傳算法（Particle Swarm Optimization-Genetic Algorithm, PSO-GA）融合算法，通過任務調(diào)度來最小化邊緣集合中最大的任務響應時間，縮短了邊緣的任務響應時間并改善了用戶體驗.董亞倩等[6]在引導車選址中，利用調(diào)度最小生成樹，解決任務均衡分配并優(yōu)化了行進路徑.羅海峰[7]設計一種局部搜索和大規(guī)模鄰域搜索混合搜索的方法，利用局部搜索的局部性和大規(guī)模鄰域的全局性，求解容量約束的車輛路由問題.胡士娟[8]、張碩航[9]等通過在雜草算法中引入繁殖機制產(chǎn)生的后代進行遺傳操作，解決了工作量平衡的MTSP，從而改善快遞員配送環(huán)節(jié)的任務平衡問題.Venkatesh等[10]在求解單倉庫MTSP中，提出采用人工蜂群算法最小化所有旅行商的總距離，采用基于入侵雜草優(yōu)化算法最小化所有旅行商所走的最大行駛距離.李道全等[11]考慮網(wǎng)絡區(qū)域能耗的均衡問題，改進蟻群算法提高覆蓋率和平衡網(wǎng)絡能量的消耗.Bernardino等[12]提出一種分支切割算法與局部搜索結合的混合算法獲得高質量的解.

本文在研究任務均衡規(guī)劃問題時，將CMRTP問題表述為MTSP的一個復雜變體[13]，研究如何均衡機器人團隊的所有機器人的行走距離，即如何最小化所有機器人的最長行走距離.為了能夠達到任務均衡效果，對其聚類進行改進，將機器人總距離最小作為優(yōu)化目標函數(shù)；在整體效能方面采用最小化最大路程作為目標函數(shù).基于多種群智能的算法，使用黏菌算法和交叉操作相互結合來解決局部問題；結合頭腦風暴優(yōu)化算法思想以降低問題的復雜度和求解全局問題；利用最小化最大路徑的方式求解任務規(guī)劃問題的任務均衡問題.即不斷地調(diào)整任務由哪個機器人完成，以及調(diào)整任務方案上完成任務的順序.為了保證機器人系統(tǒng)完成任務之間的均衡性，使得每個機器人完成任務的代價盡量均衡，通過分析均衡度評價機器人團隊的任務均衡性.本文分為兩個階段：第一階段通過改進K-means聚類進行初步任務分配，第二階段通過頭腦風暴優(yōu)化算法進行重規(guī)劃、任務規(guī)劃，獲得較優(yōu)的任務順序方案，以便提高機器人利用效率和任務均衡性.

1 協(xié)作任務均衡規(guī)劃問題分析與建模

多移動機器人協(xié)作任務規(guī)劃問題中，存在機器人集合R={r1,r2,···,rm}，任務集合T ={t1,t2,···,tn}，任務ti的坐標(xti,yti)，任務子集合S ={S1,S2,···,Sm}，其中Sk(k=1,2,···,m)表示第k個機器人完成任務序列集合.C是一個N×N維代價矩陣，其中cij表示機器人從任務ti到tj的距離，同時規(guī)定c(ti,ti)=0，i ∈{1,2,···,n}表示相同任務之間的代價為0；c(ti,tj)=c(tj,ti)，i ∈{1,2,···,n}表示代價矩陣C為對稱矩陣.

針對任務均衡規(guī)劃問題，CMRTP問題考慮機器人工作均衡性，將其問題轉為最小化所有機器人的最大距離更有實際意義.機器人位置、任務位置及從一個任務位置到另一個任務位置的代價矩陣是已知的.假設代價矩陣C是對稱的，目標是規(guī)劃任務和機器人，使得優(yōu)化每個機器人完成任務的代價值較小和機器人完成任務代價之間均衡度較小.

1.1 優(yōu)化目標

1）適應度值1.機器人集合完成任務所行走的總距離：

2）適應度值2.機器人行走的最長路程，目標函數(shù)為最小化最長距離：

其中：zk(k=1,2,···,m)為第k個機器人完成任務子集合Si(i=1,2,···,m)行走路程.

1.2 約束條件

針對任務均衡規(guī)劃問題，任務和機器人需要滿足以下約束條件.

其中：公式（6）和（7）表示約束所有機器人從集合出發(fā)點出發(fā)；公式（8）和（9）表示約束每個任務僅被機器人完成一次；公式（10）表示任務當前狀態(tài)，任務完成情況；公式（11）和（12）表示機器人行走路線包含起始點；公式（13）、（14）和（15）表示任務間關系.

1.3 對多移動機器人系統(tǒng)的任務規(guī)劃問題作如下假設

1）機器人工作的空間是二維平面；

2）機器人執(zhí)行任務的成本代價用機器人行走的距離長度表示；

3）機器人在各自目標任務位置處執(zhí)行任務消耗的代價忽略不計；

4）機器人從相同的集合點出發(fā)，且各機器人完成任務之后回到集合點.

2 算法介紹

黏菌算法[14]（Slime Mould Algorithm, SMA）是一種基于種群的新啟發(fā)式算法，基于黏菌在自然界中的覓食行為，類似于細菌覓食優(yōu)化算法[15].通過不斷地移動和變化，篩選出通往食物的最短路徑.Nakagaki等[16]發(fā)現(xiàn)黏菌在迷宮中覓食，自由移動形成覓食路徑，即迷宮問題的最優(yōu)解.利用SMA算法參數(shù)少、尋優(yōu)效果強的優(yōu)點，以解決網(wǎng)絡流、線性規(guī)劃、路由和運輸?shù)葐栴}[17].

頭腦風暴算法[18]（Brain Storm Optimization, BSO）與模仿生物遺傳和覓食等群體行為的演化算法不同，模擬人類通過交流互動提出新方法的頭腦風暴過程，能夠在全局探索和局部開發(fā)之間達到較好平衡[19].本質是將不同知識背景的人聚集在一起，將具有同樣或相似想法的人進行分組，選出各組的代表，在各組內(nèi)部進行新想法討論，是一種局部開發(fā)的過程；組間進行相互交流提出更廣的新想法，是一種全局探索的過程.采用聚類[20]進行分組，在對應組空間內(nèi)進行局部搜索獲取局部最優(yōu)值，在不同的組空間之間進行全局搜索獲取全局最優(yōu)值.

CMRTP問題中，執(zhí)行任務的順序是提高機器人系統(tǒng)執(zhí)行效率的關鍵.第一階段采用基于代價適應度值的改進K-means聚類技術進行任務分配.通過對代價適應度值進行聚類，不再局限于空間維度的限制，能夠減少計算量.第二階段采用了一種混合智能優(yōu)化算法，基于SMA、BSO類內(nèi)局部更新和類間全局更新個體方式、交叉操作和大規(guī)模鄰域搜索操作進行更替方法，進行任務規(guī)劃.

2.1 多機器人協(xié)作任務分配

任務分配的目標是根據(jù)機器人的使用情況，將任務集合通過分區(qū)、分組的方式分為不同區(qū)域，給機器人集合規(guī)劃不同的任務子集合來完成任務.在給定任務空間維度{x1,x2,···,xn}，假設兩個任務之間相似度可以通過其歐幾里得度量來衡量，將相似點歸為一類，同時將不相似的點區(qū)分開，首先需要假設類的個數(shù)k為已知的，并且同一個任務點只屬于某一類.因此聚類的問題就是尋找k個不相交的非空集合{S1,S2,···,Sk}，且滿足約束條件（公式(13)～(15)）.K-means算法目的是對所有任務點進行預處理，根據(jù)任務集合點的分布將任務分成m個簇，找出中心點作為優(yōu)化算法的起始點，優(yōu)化每個群.在這種情況下，該算法將一個大問題分解成幾個子問題，并求出中心點，以降低問題的復雜度.

由于K-means傳統(tǒng)思想是對數(shù)據(jù)點進行劃分，即根據(jù)每個點的位置，k個節(jié)點作為聚類中心，計算每個節(jié)點與該中心節(jié)點距離，采用將節(jié)點分配到最近的中心點的思想進行劃分，然而這樣劃分的結果導致劃分不均勻，從而導致任務均衡性相對較低.為了保證多機器人完成任務過程中任務均衡，對任務區(qū)域內(nèi)的任務成本代價適應度值進行聚類，這樣能夠減少問題的復雜度，如圖1所示.

圖1 適應度值聚類過程

步驟1：初始化任務集合、機器人集合、相關參數(shù)；

步驟2：隨機生成初始種群，計算任務點之間的距離作為距離矩陣D（見式(1)）；

步驟3：在種群中隨機選擇m個個體作為聚類中心，并計算該m個聚類中心的適應度值1；

步驟4：計算種群中個體的適應度值1與m個聚類中心的適應度值取差值絕對值，選擇差值絕對值最小的作為聚類中心，同時將當前個體歸為此類；

步驟5：計算類中個體適應度值的平均值，將類中適應度值與平均值最接近的個體定為新的聚類中心；

步驟6：保證所有任務點分配到不同的類中，否則，重復步驟4.

2.2 多機器人協(xié)作任務重規(guī)劃

針對所有任務是否完成以及是否獲得合理的規(guī)劃方案，對當前任務規(guī)劃結果進行分析，判斷當前任務規(guī)劃方案的合理性和可行性.針對何時重規(guī)劃以及如何重規(guī)劃問題，本文采用任務和目標期望值判斷依據(jù)解決任務重規(guī)劃的選擇問題.在頭腦風暴優(yōu)化算法中，對機器人內(nèi)部任務進行大規(guī)模鄰域搜索，開展任務局部重規(guī)劃，獲得局部最優(yōu)值；對機器人之間的任務進行交叉操作搜索，開展任務全局重規(guī)劃，獲得全局最優(yōu)值，以此解決重規(guī)劃問題.任務重規(guī)劃判斷流程如圖2所示.重規(guī)劃過程如圖3所示.

圖2 任務重規(guī)劃框圖

圖3 任務重規(guī)劃過程

圖3（a）中機器人內(nèi)部當前規(guī)劃方案存在均衡性較差問題，進行局部重規(guī)劃獲得較優(yōu)規(guī)劃方案.圖3（b）中機器人之間當前規(guī)劃方案存在均衡性較差問題，進行全局重規(guī)劃獲得較優(yōu)規(guī)劃方案.

3 多機器人協(xié)作任務均衡規(guī)劃算法

為獲得多移動機器人協(xié)作任務分配結果并保證所有機器人的任務均衡，每個機器人需要完成多個任務和優(yōu)化路線方案.將CMRTP問題轉化為MTSP模型求最優(yōu)解，優(yōu)化最小化機器人最長路程為最佳路線方案，使得每個機器人所走的距離都較短，從而得到總路徑相對較小和每個機器人所走路程均衡，達到任務均衡效果，再通過均衡度、差異度、偏差率進行綜合評價均衡效果優(yōu)劣.

3.1 算法設計

1）種群初始化：初始種群通常是隨機生成的，但是在保證個體多樣性的前提下，不能同時獲得較優(yōu)的收斂速度，將會出現(xiàn)算法尋優(yōu)速度慢的問題.所以本文將黏菌算法進行迭代生成的初始種群進行計算適應度值1，保留排序較優(yōu)的個體作為初始種群，減少算法的尋優(yōu)次數(shù).

2）交叉算子：根據(jù)CMRTP問題的特點設計算法，有利于改善算法的性能.引入交叉算子產(chǎn)生盡可能多的新個體，提高搜索能力.交叉操作在機器人內(nèi)部的交流是一種局部開發(fā)的過程，在機器人之間進行交流是一種全局探索的過程.交叉操作就是將親代種群的個體片段進行選擇性交換、匹配部分基因，產(chǎn)生新的高質量個體，如圖4所示.

圖4 交叉操作

3）大規(guī)模鄰域搜索操作[21－22]：remove移除算子操作中隨機選取移除的路線個數(shù)，在相鄰的路線中移除i個任務，從當前解中選擇一個任務i對任務進行初次排序，選擇第一個點.采用repair算子操作能夠得到不同類型的解，提高了解的質量.

4）擾動算子：采用隨機個體聚類中心替換的策略，計算適應度值，比較更新當前個體.大規(guī)模鄰域搜索操作對當前方案進行擾動操作，選擇最優(yōu)適應度值1作為最優(yōu)方案.

3.2 算法實現(xiàn)

基于混合算法的多機器人協(xié)作任務均衡規(guī)劃算法如圖5所示.

圖5 任務均衡規(guī)劃算法

4 實驗與分析

4.1 實驗環(huán)境與參數(shù)設置

在Windows 10操作系統(tǒng)、Matlab2020a編程軟件進行測試實驗.每個實例運行20次以確保95%的置信區(qū)間，記錄每個機器人的行走路線和行走距離.在不同機器人數(shù)量和任務數(shù)量下開展研究，通過均衡度、偏差率和差異度評估本文算法性能和任務規(guī)劃效果.種群為50，迭代次數(shù)為600，概率參數(shù)為：z=0.03、Pone=0.5、Ptwo=1-Pone、Ponecenter=0.3、Ptwocenter=0.3、ωinitial=1、ωfinal=0.對遺傳算法（Genetic Algorithm, GA）、蟻群算法[23－24]（Ant Colony Optimization, ACO）、SMA算法解決多機器人任務均衡規(guī)劃問題的規(guī)劃結果進行對比.

4.2 實例驗證及結果

為驗證所提算法的有效性，本文在TSPLIB國際標準測試庫中，選取了三個不同規(guī)模的實例，采用不同算法驗證規(guī)劃結果的均衡性，記錄相關數(shù)據(jù)并對實驗結果進行具體分析和比較.實例中列舉了不同實例和機器人數(shù)量的變化，如表1所示.

表1 測試實例

實例eil101中3、4、5、10個機器人的任務規(guī)劃優(yōu)化結果如圖6所示.圖6（a）代表機器人和任務分布，藍色方格為機器人位置，紅色圓圈為任務位置以及任務的序號.圖6（b～e）為任務規(guī)劃結果，不同顏色代表不同機器人的任務以及完成任務過程中機器人完成任務的順序.

由圖6（e）可知，不同機器人完成的任務之間沒有出現(xiàn)重復現(xiàn)象，說明每個任務只被一個機器人完成，同時展示出任務規(guī)劃后的最優(yōu)方案.可以獲得機器人分配的任務完成順序、任務數(shù)量以及成本代價，如表2所示.

表2 實例eil101、機器人數(shù)量為10的任務規(guī)劃結果

根據(jù)10個機器人完成對應任務所需成本代價分別為112.487 5、113.202 5、109.504 9、109.965 6、113.701 4、109.615 9、106.780 0、112.756 4、110.212 9、109.710 1，得出本文改進算法的平均均衡度為9.69%、平均差異度為2.848%、平均偏差率為1.997%.SMA算法的平均均衡度為14.059%、平均差異度為3.483%、平均偏差率為3.312%.經(jīng)比較分析，本文算法任務均衡規(guī)劃結果均衡度相對提高，機器人之間的成本代價差異程度相對較小，任務成本代價相對平衡，保證了機器人之間任務的均衡性，表明本文算法在均衡機器人任務代價上具有較好的均衡性.

4.3 算法性能分析

采用多個評估指標綜合評價任務均衡規(guī)劃結果的均衡性.機器人之間的行走距離的平均差異程度越小，其均衡性越好.SMA、GA、ACO和本文算法在不同實例上的任務規(guī)劃結果、記錄機器人行走最長距離的最優(yōu)值（m）和平均值（m）如表3所示.SMA和本文算法任務規(guī)劃結果的機器人團隊總路徑的最優(yōu)值（m）和平均值（m）如表4所示.本文算法和SMA算法任務規(guī)劃結果的平均偏差率PDav（%）、平均均衡度σ（%）和平均差異度CV（%）如表5所示.平均值[25]反映算法的平均優(yōu)化精度，平均值越小證明算法的優(yōu)化精度越好；最優(yōu)值越小表示優(yōu)化路徑越短.平均均衡度σ和平均差異度CV 越小，說明機器人之間行走路徑相近，任務成本代價差異程度相對較小，任務均衡性越優(yōu)，任務規(guī)劃效果就越好.平均偏差率PDav越小，表明任務規(guī)劃結果的機器人總行走距離相對誤差越小.

4.3.1 均衡性評估指標

1）任務均衡度：

其中：maxLi表示第i(i=1,2,···,m)個機器人的最長路程，minLj表示第j(j=1,2,···,m)個機器人的最短路程，i/=j，m為機器人總個數(shù).

2）平均偏差率：

其中：平均長度為20次獨立運行所得最優(yōu)解的平均值，最優(yōu)解是已知最優(yōu)解.

3）路徑長度平均差異度CV[26]反映各機器人路徑長度的差異程度：

4.3.2 本文算法的收斂效果分析

為了驗證本文算法的收斂效果，給出3個實例中不同機器人數(shù)量完成不同任務數(shù)量的規(guī)劃結果，本文算法和黏菌算法迭代到全局最優(yōu)值的收斂曲線，如圖7所示.

圖7 不同實例的迭代收斂曲線

圖7（b）是實例eil101中機器人數(shù)量為4時的任務規(guī)劃結果，收斂曲線的迭代早期為20時，本文算法約為195，而SMA算法約為200，前者起初找到全部最優(yōu)值相對較優(yōu)，所需要的迭代次數(shù)較少，收斂速度相對較快；本文算法尋得全局最優(yōu)值為182.5，而SMA算法尋得全局最優(yōu)值為184，精度提高約0.82%，可以得知本文算法在尋優(yōu)精度方面效果較佳.圖7（d）是實例eil101中機器人數(shù)量為10時的任務規(guī)劃結果，本文算法在迭代次數(shù)100內(nèi)尋得全局最優(yōu)值，在較早的迭代過程尋得全局最優(yōu)值為113.701 4，體現(xiàn)出較優(yōu)的收斂速度，而SMA算法表現(xiàn)出陷入局部最優(yōu)值的現(xiàn)象，尋得全局最優(yōu)值為115.097 7，本文算法尋得全局最優(yōu)值的精度提高約1.21%.綜上所述，本文算法在不同實例中的搜索效率具有不同程度的提高，相對SMA算法，本文算法收斂效果較佳，全局搜索效果較好.本文算法的收斂曲線均位于SMA算法的下方，在算法收斂早期快速搜索到全局最優(yōu)值的迭代次數(shù)相對較少、最優(yōu)值精度相對較高.

由表3可知，比較不同實例中機器人任務規(guī)劃的最長路徑，本文混合算法的最優(yōu)值比SMA算法解的質量高.不同實例中，本文算法收斂到全局最優(yōu)值的過程中尋得全局最優(yōu)值相對較優(yōu)，而SMA算法迭代對應適應度值與本文算法比較顯出最優(yōu)解的劣勢.通過表4進行綜合分析，改進算法不論最長路徑最優(yōu)值還是團隊最優(yōu)值都有不同程度提高.表4中本文算法最優(yōu)解以及平均解都比SMA算法的解的質量高.結合表5中平均均衡度σ、平均差異度CV、平均偏差率PDav指標，可知本文算法的機器人總行走距離相對誤差小，保證了算法解的均衡.

表3 機器人任務規(guī)劃最長距離

表4 機器人團隊任務規(guī)劃總路徑

由表5可知，從平均均衡度σ分析，評估了最長行走距離和最短行走距離之間的差異，在任務數(shù)量較少安排機器人較少的情況下平均均衡度σ都在3%左右，機器人數(shù)量為5時，相對SMA算法提高了4%左右，均衡性相對較優(yōu)；實例eil51-10中，機器人數(shù)量較多時平均σ在20%左右，本文算法在尋找最優(yōu)任務規(guī)劃效果上均衡性從31%降到28%，均衡性有所提高；實例eil101-10中，平均均衡度σ從14.059%降低到9.690%，最長行走距離和最短行走距離差距縮短，任務規(guī)劃效果合理.從平均差異度CV 分析，評估了機器人團隊中所有機器人行走距離之間的差異程度，很好地展現(xiàn)了機器人之間的差距，從不同實例得出本文算法在實例eil51-10中提高6%左右，其它情況下提高1%左右，將所有機器人之間的差異程度降到相對較低，本文算法的平均差異度CV 相比SMA算法更小，進一步保證了機器人之間良好的均衡性.從平均偏差率PDav分析，將所有機器人的整體效益進行對比，本文算法相比SMA算法具有更小的平均偏差率，說明更接近最優(yōu)值，取得規(guī)劃效果較佳.

表5 均衡性評估指標

SMA、GA、ACO、本文算法在不同實例中的任務規(guī)劃結果和任務規(guī)劃結果的機器人最大距離對比柱狀圖如圖8所示；總距離對比柱狀圖如圖9所示.圖中不同顏色代表不同算法數(shù)據(jù)值：橘色柱形為GA、綠色柱形為ACO、紫色柱形為SMA、黃色柱形為本文算法.

圖8 實例eil51、eil76和eil101不同算法最優(yōu)值對比

圖9 實例eil51、eil76和eil101不同算法總距離對比

由圖8可知，黃色柱形的最大距離最優(yōu)值最高點均位于其它算法的下方，說明比較后的最大距離相對較小，全局最優(yōu)值相對較優(yōu)，優(yōu)化路線方案效果明顯.

由圖9可知，黃色柱形與其它顏色柱形進行比較，總距離整體較低，總距離值相對較小，體現(xiàn)出本文算法在全局搜索方面的優(yōu)越性.可以看出本文算法的機器人最長距離最優(yōu)解要比其它算法的最優(yōu)解較優(yōu)；獲得機器人團隊總距離也小于其它算法的值.綜上所述，改進算法的尋優(yōu)效果優(yōu)于其它比較算法，任務規(guī)劃結果較優(yōu).

4.3.3 任務規(guī)劃結果的均衡性分析

為了驗證任務均衡性能的好壞，獲取本文算法在不同實例中的最優(yōu)均衡規(guī)劃結果的路程分布如圖10所示.不同顏色代表任務規(guī)劃中機器人的行走距離，進而計算每個機器人之間的行走距離的均衡度和路徑長度平均差異度.

圖10（a）代表實例eil51中機器人數(shù)量為3時，機器人1的行走路程為158.993 5，機器人2的行走路程為159.571 5，機器人3的行走路程為158.236 2，平均均衡度σ為1.874%，路徑長度平均差異度CV 為0.540%，平均偏差率PDav為1.383%，機器人之間任務成本代價相對差異在2%以下，均衡效果與SMA算法相比有所提高.圖10（b）代表機器人數(shù)量為10時的路徑分布，平均均衡度σ為28.500%，路徑長度平均差異度CV 為2.848%，平均均衡度大的原因是任務數(shù)量少的情況下安排的機器人數(shù)量多，使得出現(xiàn)總體規(guī)劃效果差的現(xiàn)象，通過路徑長度平均差異度CV 分析，本文算法的路徑長度平均差異度為2.848%，而SMA算法相對較高，均衡效果劣于本文算法，本文算法任務規(guī)劃結果相對合理.圖10（c）代表實例eil101中機器人數(shù)量為10時，機器人1行走路程為112.487 5，機器人2行走路程為113.202 5，機器人3行走路程為109.504 9，機器人4行走路程為109.965 6，機器人5行走路程為113.701 4，機器人6行走路程為109.615 9，機器人7行走路程為106.780 0，機器人8行走路程為112.756 4，機器人9行走路程為110.212 9，機器人10行走路程為109.710 1，平均均衡度σ為9.690%，路徑長度平均差異度CV 為2.848%，平均偏差率PDav為1.997%.SMA算法中平均均衡度為14.059%，路徑長度平均差異度CV 為3.483%，平均偏差率PDav為3.312%，與本文算法比較相對較高，成本代價差異大，造成在機器人之間任務均衡效果不佳.

圖10 實例eil51、eil101路徑分布圖

5 結論

在解決多移動機器人任務均衡規(guī)劃問題中，為了使機器人的工作量相對接近，機器人之間任務均衡，同時提高機器人團體效益.本文在任務分配問題中采用基于適應度值的K-means聚類進行分類，減少了計算復雜度；利用黏菌算法三階段搜索策略提高了求解問題的全局搜索能力，利用頭腦風暴算法的機器人內(nèi)進行局部更新操作和機器人間進行全局更新操作對任務子集合進行重規(guī)劃，任務集合內(nèi)進行任務規(guī)劃，獲取較優(yōu)任務路線方案；采用交叉操作和大規(guī)模鄰域搜索操作提高了該任務規(guī)劃算法的全局搜索和局部搜索能力.實驗結果表明：基于混合優(yōu)化算法的任務均衡規(guī)劃方法能夠合理均衡規(guī)劃多移動機器人系統(tǒng)中的任務和機器人，機器人之間的路徑成本代價平均差異度相比SMA算法低，體現(xiàn)出成本代價之間的均衡效果較優(yōu)，能實現(xiàn)多移動機器人的均衡規(guī)劃，提升完成任務效率.所提出的算法在多移動機器人任務均衡規(guī)劃問題中具有較好的均衡性.