基于快速非支配排序的多機(jī)器人任務(wù)分配方法*

蔡帛良 魏長赟 張鵬鵬

（河海大學(xué)機(jī)電工程學(xué)院 常州 213022）

1 引言

貨物分揀與運(yùn)輸是智能倉儲系統(tǒng)的重要環(huán)節(jié)，是未來社會物聯(lián)網(wǎng)系統(tǒng)的重要組成部分。對于未來智能倉儲系統(tǒng)，多機(jī)器人系統(tǒng)能夠通過協(xié)作，有效提高貨物分揀效率，降低包裹搬運(yùn)時間。但是，多機(jī)器人系統(tǒng)在同一空間工作，容易產(chǎn)生任務(wù)干涉和沖突，從而導(dǎo)致死鎖等難題。因此，需要研究智能倉儲系統(tǒng)中多機(jī)器人的任務(wù)分配及調(diào)度問題。

多機(jī)器人系統(tǒng)在智能倉儲系統(tǒng)中的任務(wù)可以描述為服務(wù)器接收訂單信息，根據(jù)訂單信息生成貨物坐標(biāo)圖，并通過算法為每個機(jī)器人分配任務(wù)及取貨順序，多個機(jī)器人從起點(diǎn)出發(fā)，按照系統(tǒng)分配取貨順序依次取貨并返回終點(diǎn)提交貨物。通?？梢詫⒋祟惾蝿?wù)轉(zhuǎn)化為Multi-TSP（Multi-Traveling-salesman-problem）問題。

但由于現(xiàn)代多機(jī)器人系統(tǒng)任務(wù)分配算法都是以求解最小路程為總目標(biāo)，這導(dǎo)致每個機(jī)器人的任務(wù)分配不均衡，最終導(dǎo)致分揀時發(fā)生有某幾個機(jī)器人長時間等待一個機(jī)器人返回的情況，實(shí)際分揀效率低下。針對此問題，本文提出以均衡各機(jī)器人路徑和最小總體路徑為目的的多目標(biāo)Multi-TSP問題，即在解空間中尋找符合Pareto支配條件的解的問題，但該問題由于該類問題求解空間大，求解復(fù)雜，被歸類為NP-hard問題［1］。

圖1 多機(jī)器人的智能倉儲分揀系統(tǒng)

通常用于求解NP問題的啟發(fā)式算法有粒子群算法（PSO）、蟻群算法（ACO）、禁忌搜索算法（TS）、退火算法（SAA）和遺傳算法（GA），但由于多目標(biāo)優(yōu)化問題在復(fù)雜問題下解空間龐大，以及傳統(tǒng)優(yōu)化算法的自身局限，使得各類優(yōu)化算法均很難獲得Pareto解，近年來，基于遺傳算法的多目標(biāo)進(jìn)化算法（MOEA）逐漸成為解決多目標(biāo)優(yōu)化問題的重要方式［2］。

2 多機(jī)器人的任務(wù)分配模型

針對上述多目標(biāo)Multi-TSP問題，可以歸納為：對于給定階為N的圖G={V，E}，安排m個機(jī)器人對節(jié)點(diǎn)集V進(jìn)行遍歷，使得除出發(fā)點(diǎn)vn∈V以外的所有節(jié)點(diǎn)均有且僅有一個機(jī)器人通過，且路徑之和最小，各機(jī)器人路徑方差最小。

綜上所述，對于此多目標(biāo)Multi-TSP問題，有如下優(yōu)化目標(biāo)：

式中：S為所有機(jī)器人路徑總長度；Si為第i個機(jī)器人的路徑總長度；Savg為各機(jī)器人長度均值。

其中Si是根據(jù)機(jī)器人i的路徑Pi={Ui，Ei}并按照圖G的鄰接矩陣D（G）計算的路徑序列節(jié)點(diǎn)距離之和，即

且對Multi-TSP問題有：

所有機(jī)器人必須從指定起點(diǎn)出發(fā)，且對其他所有節(jié)點(diǎn)嚴(yán)格訪問一次后返回起點(diǎn)vn。即對于除出發(fā)點(diǎn)以外的點(diǎn)集U=V{vn}，有

且每組有效解必須包含m條平凡子路徑，即

上述各式中式（1）為本算法的優(yōu)化目標(biāo)，式（2）～（4）構(gòu)成了該問題的約束條件。

3 基于非支配排序的多目標(biāo)遺傳算法

遺傳算法（Genetic Algorithm，GA）是模擬進(jìn)化論中種群進(jìn)化過程的計算模型，通過特定方式編碼種群個體的基因序列，并利用適應(yīng)適應(yīng)函數(shù)計算個體適應(yīng)度，通過篩選種群獲得父代個體，產(chǎn)生下一代，并逐代向Pareto解靠近［2］。GA算法自20世紀(jì)60年代被提出到現(xiàn)在，被廣泛用于各類NP問題的求解中，引入了諸多附加機(jī)制以保證算法計算速度及收斂性，例如退火機(jī)制，精英策略等，已經(jīng)在許多組合優(yōu)化問題上獲得顯著成果，Kim等提出了SPEA2+算法［3］，采用線性空間網(wǎng)格劃分的方法來維持子代種群的多樣性，以避免陷入局部最優(yōu)解；Deb等提出引入精英策略的NSGA-II算法［4］，通過改進(jìn)的快速非支配排序算法和精英策略用來篩選較優(yōu)個體并保持種群多樣性，避免種群早熟的同時，保證種群快速收斂。

利用遺傳算法求解問題，需要對個體基因進(jìn)行編碼，采用斷點(diǎn)標(biāo)記法對基因進(jìn)行編碼。步驟如下：

1）將集合V中的非起始點(diǎn)標(biāo)記為1，2，…n-1，將起始點(diǎn)標(biāo)記為n，并添加m-2個斷點(diǎn)并將其編號為n+1，n+2…n+m-2；

2）將斷點(diǎn)n+1，n+2…n+m-2與1，2，…n組合為基因序列，并在計算S時候?qū)⒕幪枮閚+1…n+m-2的節(jié)點(diǎn)指向起點(diǎn)O，從而將問題轉(zhuǎn)化為TSP問題進(jìn)行求解；

3）為防止n+1…n+m-2前后相連，保證每條機(jī)器人路徑均為平凡子路徑，在G的鄰接矩陣D中應(yīng)有dnn=∞，以保證進(jìn)化過程中斷點(diǎn)相連的個體被淘汰。

通過GA算法求解單目標(biāo)Multi-TSP問題可以得到較優(yōu)解，但在多目標(biāo)Multi-TSP問題中，不同的適應(yīng)度函數(shù)與子代的篩選策略對算法的收斂性具有較大影響。

3.1 帶有精英庫的種群重啟策略

針對遺傳算法無法避免陷入局部最優(yōu)值的缺點(diǎn)，本文提出了一種帶有精英庫的種群重啟策略，即對于每次計算，在種群達(dá)到收斂條件時，重新初始化種群，并將達(dá)到收斂條件的優(yōu)質(zhì)解個體納入精英庫，達(dá)到使用精英庫進(jìn)行進(jìn)化的條件時，將精英庫作為新的種群繼續(xù)迭代，從而提高算法收斂到Pareto解的概率。其基本流程圖如圖2所示。

圖2 帶有精英庫的種群重啟策略下的遺傳算法流程圖

3.2 基于快速非支配排序子代選擇方法

基于快速非支配排序（Fastnon-Demined Sort）策略和精英策略的遺傳算法（NSGA-II）［1］是 由Kalyanmoy Deb針對多目標(biāo)優(yōu)化問題提出的優(yōu)化算法，與傳統(tǒng)的單目標(biāo)模型按照得分篩選優(yōu)質(zhì)個體不同，NSGA-II對多目標(biāo)優(yōu)化問題中的每個優(yōu)化特征進(jìn)行綜合考察，引入了支配排序和擁擠度計算的概念，通過非支配排序策略獲得較優(yōu)個體，利用擁擠度策略保證種群多樣性，并將父代中的較優(yōu)個體直接引入子代，避免了種群較優(yōu)解的丟失，從而增加種群收斂到Pareto解的概率。

3.3 快速非支配排序算法的支配賦級策略

非支配排序是來對具有多個目標(biāo)參量個體進(jìn)行排序的策略，在NSGA-II中，每個個體都具有被支配集合Ni和支配解集合Si，其中Ni表示當(dāng)前種群中支配個體i的個體集合，Si表示被個體i支配的個體集合。

算法1 支配賦級算法

3.4 快速非支配排序算法的擁擠度計算策略

為保正非支配排序策略選擇的父代種群具有多樣性，避免將種群中的優(yōu)化分量相近的個體納入父代，提高種群早熟并陷入局部Pareto解的概率，Kalyanmoy Deb提出了同支配等級間個體的擁擠度排序策略。其中個體i的擁擠度Ci被定義為距離個體i最近的兩個個體j，k的特征矢量(f1，f2)的差之和，即

其基本算法如下：

算法2 擁擠度排序算法

NSGA-II算法選取子代個體主要優(yōu)先通過支配序，同等支配序下優(yōu)先選擇擁擠度小的個體。

4 算法測試

4.1 算例描述

本文采用TSPLIB數(shù)據(jù)集的eil類（eil51）和Kro類（Kro_100、Kro_150、Kro_A200）作為測試數(shù)據(jù)集，分別在不同容量的數(shù)據(jù)集上進(jìn)行不同機(jī)器人數(shù)目的橫向?qū)Ρ?，并測試傳統(tǒng)Multi-TSP任務(wù)分配算法、將多目標(biāo)優(yōu)化參量整合后的Multi-TSP算法（SFO）和本文所述非支配排序的多目標(biāo)任務(wù)分配算法，并以最長距離和平均距離之差與總路徑的比值為評價標(biāo)準(zhǔn)進(jìn)行評判。

4.2 計算結(jié)果

由于優(yōu)化目的為最小化多機(jī)器人系統(tǒng)總路程并減少多機(jī)器人系統(tǒng)的距離方差，選擇機(jī)器人各組最長距離和最大路徑偏差占比作為評判標(biāo)準(zhǔn)，以此作為衡量該算法對任務(wù)分配均衡性能和最長執(zhí)行時間的標(biāo)準(zhǔn)。

采用Python 3.6.5進(jìn)行編程，在CPU為3.5GHz，內(nèi)存為6GB的臺式機(jī)上進(jìn)行測試，測試結(jié)果如圖3所示。

圖3 100節(jié)點(diǎn)下不同機(jī)器人最大子路徑

圖4 150節(jié)點(diǎn)下不同機(jī)器人最大子路徑

圖5 200節(jié)點(diǎn)下不同機(jī)器人最大子路徑

由圖2、圖3、圖4可知，隨著參與運(yùn)輸機(jī)器人數(shù)目的增加，可以有效降低各運(yùn)輸機(jī)器人運(yùn)輸路徑長度，從而降低運(yùn)輸時間，并有效減少各機(jī)器人的任務(wù)負(fù)載。

表3 各機(jī)器人最大路徑偏差占百分比

由表3統(tǒng)計結(jié)果，各機(jī)器人最大路徑和平均路徑的差值均小于平均路徑的2%，從而保證運(yùn)動路徑較小機(jī)器人因為運(yùn)動路徑較大的機(jī)器人工作時間過長而出現(xiàn)閑置的概率較低。

得到種群的計算收斂圖如下，從圖中可知種群共進(jìn)行了5次重啟，并在最后的精英庫重啟中（680代后）獲得了新的最優(yōu)值。

圖6 每代最優(yōu)個體得分曲線

圖7 全局最優(yōu)解分?jǐn)?shù)變化曲線

4.3 對比分析

為證明該任務(wù)分配算法的均衡性，本節(jié)采用eil51數(shù)據(jù)集，與傳統(tǒng)單目標(biāo)Multi-TSP算法和SFO算法進(jìn)行比較，并分別以平均路徑，總路程和最大子路徑為評價標(biāo)準(zhǔn)。

從上述各圖中可知，隨著機(jī)器人數(shù)目的增加，機(jī)器人組的總路徑長度增大，平均路徑均下降，但傳統(tǒng)Multi-TSP算法的最大路程時間遠(yuǎn)高于本文提出的任務(wù)分配算法，而SFO算法的總路徑遠(yuǎn)高于前兩者，最大子路徑和平均路徑數(shù)值性能劣于本文提出的改進(jìn)的NSGA-II算法。

圖8 總路徑長度

圖9 平均路徑長度

圖10 最大子路徑

圖11 三種算法的目標(biāo)特征散點(diǎn)圖

從圖11可以看出，SFO算法的劣勢在于在實(shí)際計算過程中，采用了犧牲路徑總長度，以獲取最小方差的算法，這導(dǎo)致了總路程過大。

表4 三種算法最大子路徑偏差

從表4可知，傳統(tǒng)Multi-TSP的計算結(jié)果中，最大子路徑偏（即最大子路徑和平均路徑之差）差明顯高于機(jī)器人平均路徑，這導(dǎo)致機(jī)器人組的工作負(fù)載極不平衡和效率低下，而SFO算法下機(jī)器人的路徑偏差極小，但這是通過提高較短路徑距離而實(shí)現(xiàn)的，從圖7可知，SFO算法的總路徑長度遠(yuǎn)高于傳統(tǒng)Multi-TSP和NSGA-II算法，這導(dǎo)致了實(shí)際路徑的增大。而基于快速非支配排序的進(jìn)化算法則可以平衡計算結(jié)果，保證機(jī)器人組負(fù)載平衡，保證智能倉儲物流系統(tǒng)的高效運(yùn)行。

同時獲得了在eil51下的實(shí)驗結(jié)果的對比圖。

圖13 NormalMTSPwith 4 robots

圖14 NormalMTSPwith 6 robots

圖15 Improved NSGA-IIwith 2 robots

圖16 Improved NSGA-IIwith 4 robots

圖17 Improved NSGA-IIwith 6 robots

從上述各圖可以看出，較常規(guī)Multi-TSP問題，本文提出的改進(jìn)的NSGA-II算法為多機(jī)器人系統(tǒng)提供有效的任務(wù)劃分，降低多機(jī)器人任務(wù)干涉和沖突的概率。

5 結(jié)語

基于快速非支配排序的多目標(biāo)優(yōu)化遺傳算法較傳統(tǒng)Multi-tsp算法具有機(jī)器人利用率高，最大運(yùn)行時間短的特點(diǎn)，可以提高智能倉儲系統(tǒng)的實(shí)際工作效率，本文為多目標(biāo)智能倉儲機(jī)器人的路徑規(guī)劃構(gòu)建對應(yīng)的優(yōu)化目標(biāo)函數(shù)組，并結(jié)合非支配排序算法和精英策略以及種群重啟和精英庫策略設(shè)計了遺傳算法。實(shí)驗結(jié)果表明，上述算法路徑尋優(yōu)性能，路徑均衡性能均優(yōu)于傳統(tǒng)Multi-TSP算法。

從本文研究結(jié)果可知，在遺傳算法中，種群達(dá)到早熟后，重置種群可以使種群繼續(xù)保持尋優(yōu)特性，并具有較大的概率獲得Pareto解，同時存儲歷代收斂種群的精英個體進(jìn)行優(yōu)化可以更好地獲得Pareto解。

本文對多優(yōu)化目標(biāo)的多機(jī)器人靜態(tài)任務(wù)分配問題進(jìn)行了研究，但未對實(shí)際路徑網(wǎng)絡(luò)時變性問題進(jìn)行研究，這是實(shí)際生產(chǎn)生活中更為常見的問題，因此需要針對這類問題進(jìn)行進(jìn)一步研究。