基于混合算法的多機(jī)器人協(xié)作任務(wù)均衡規(guī)劃研究*

王喜敏，袁 杰

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

0 引言

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

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

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

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

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

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

1.1 優(yōu)化目標(biāo)

1）適應(yīng)度值1.機(jī)器人集合完成任務(wù)所行走的總距離：

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

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

1.2 約束條件

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

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

1.3 對(duì)多移動(dòng)機(jī)器人系統(tǒng)的任務(wù)規(guī)劃問題作如下假設(shè)

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

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

3）機(jī)器人在各自目標(biāo)任務(wù)位置處執(zhí)行任務(wù)消耗的代價(jià)忽略不計(jì)；

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

2 算法介紹

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

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

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

2.1 多機(jī)器人協(xié)作任務(wù)分配

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

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

圖1 適應(yīng)度值聚類過程

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

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

步驟3：在種群中隨機(jī)選擇m個(gè)個(gè)體作為聚類中心，并計(jì)算該m個(gè)聚類中心的適應(yīng)度值1；

步驟4：計(jì)算種群中個(gè)體的適應(yīng)度值1與m個(gè)聚類中心的適應(yīng)度值取差值絕對(duì)值，選擇差值絕對(duì)值最小的作為聚類中心，同時(shí)將當(dāng)前個(gè)體歸為此類；

步驟5：計(jì)算類中個(gè)體適應(yīng)度值的平均值，將類中適應(yīng)度值與平均值最接近的個(gè)體定為新的聚類中心；

步驟6：保證所有任務(wù)點(diǎn)分配到不同的類中，否則，重復(fù)步驟4.

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

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

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

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

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

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

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

3.1 算法設(shè)計(jì)

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

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

圖4 交叉操作

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

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

4.2 實(shí)例驗(yàn)證及結(jié)果

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

表1 測(cè)試實(shí)例

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

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

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

根據(jù)10個(gè)機(jī)器人完成對(duì)應(yīng)任務(wù)所需成本代價(jià)分別為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，得出本文改進(jìn)算法的平均均衡度為9.69%、平均差異度為2.848%、平均偏差率為1.997%.SMA算法的平均均衡度為14.059%、平均差異度為3.483%、平均偏差率為3.312%.經(jīng)比較分析，本文算法任務(wù)均衡規(guī)劃結(jié)果均衡度相對(duì)提高，機(jī)器人之間的成本代價(jià)差異程度相對(duì)較小，任務(wù)成本代價(jià)相對(duì)平衡，保證了機(jī)器人之間任務(wù)的均衡性，表明本文算法在均衡機(jī)器人任務(wù)代價(jià)上具有較好的均衡性.

4.3 算法性能分析

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

4.3.1 均衡性評(píng)估指標(biāo)

1）任務(wù)均衡度：

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

2）平均偏差率：

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

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

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

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

圖7 不同實(shí)例的迭代收斂曲線

圖7（b）是實(shí)例eil101中機(jī)器人數(shù)量為4時(shí)的任務(wù)規(guī)劃結(jié)果，收斂曲線的迭代早期為20時(shí)，本文算法約為195，而SMA算法約為200，前者起初找到全部最優(yōu)值相對(duì)較優(yōu)，所需要的迭代次數(shù)較少，收斂速度相對(duì)較快；本文算法尋得全局最優(yōu)值為182.5，而SMA算法尋得全局最優(yōu)值為184，精度提高約0.82%，可以得知本文算法在尋優(yōu)精度方面效果較佳.圖7（d）是實(shí)例eil101中機(jī)器人數(shù)量為10時(shí)的任務(wù)規(guī)劃結(jié)果，本文算法在迭代次數(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%.綜上所述，本文算法在不同實(shí)例中的搜索效率具有不同程度的提高，相對(duì)SMA算法，本文算法收斂效果較佳，全局搜索效果較好.本文算法的收斂曲線均位于SMA算法的下方，在算法收斂早期快速搜索到全局最優(yōu)值的迭代次數(shù)相對(duì)較少、最優(yōu)值精度相對(duì)較高.

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

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

表4 機(jī)器人團(tuán)隊(duì)任務(wù)規(guī)劃總路徑

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

表5 均衡性評(píng)估指標(biāo)

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

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

圖9 實(shí)例eil51、eil76和eil101不同算法總距離對(duì)比

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

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

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

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

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

圖10 實(shí)例eil51、eil101路徑分布圖

5 結(jié)論

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