基于快速非支配排序的多機器人任務分配方法*

蔡帛良 魏長赟 張鵬鵬

（河海大學機電工程學院 常州 213022）

1 引言

貨物分揀與運輸是智能倉儲系統的重要環節，是未來社會物聯網系統的重要組成部分。對于未來智能倉儲系統，多機器人系統能夠通過協作，有效提高貨物分揀效率，降低包裹搬運時間。但是，多機器人系統在同一空間工作，容易產生任務干涉和沖突，從而導致死鎖等難題。因此，需要研究智能倉儲系統中多機器人的任務分配及調度問題。

多機器人系統在智能倉儲系統中的任務可以描述為服務器接收訂單信息，根據訂單信息生成貨物坐標圖，并通過算法為每個機器人分配任務及取貨順序，多個機器人從起點出發，按照系統分配取貨順序依次取貨并返回終點提交貨物。通常可以將此類任務轉化為Multi-TSP（Multi-Traveling-salesman-problem）問題。

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

圖1 多機器人的智能倉儲分揀系統

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

2 多機器人的任務分配模型

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

綜上所述，對于此多目標Multi-TSP問題，有如下優化目標：

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

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

且對Multi-TSP問題有：

所有機器人必須從指定起點出發，且對其他所有節點嚴格訪問一次后返回起點vn。即對于除出發點以外的點集U=V{vn}，有

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

上述各式中式（1）為本算法的優化目標，式（2）～（4）構成了該問題的約束條件。

3 基于非支配排序的多目標遺傳算法

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

利用遺傳算法求解問題，需要對個體基因進行編碼，采用斷點標記法對基因進行編碼。步驟如下：

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

2）將斷點n+1，n+2…n+m-2與1，2，…n組合為基因序列，并在計算S時候將編號為n+1…n+m-2的節點指向起點O，從而將問題轉化為TSP問題進行求解；

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

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

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

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

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

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

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

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

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

算法1 支配賦級算法

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

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

其基本算法如下：

算法2 擁擠度排序算法

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

4 算法測試

4.1 算例描述

本文采用TSPLIB數據集的eil類（eil51）和Kro類（Kro_100、Kro_150、Kro_A200）作為測試數據集，分別在不同容量的數據集上進行不同機器人數目的橫向對比，并測試傳統Multi-TSP任務分配算法、將多目標優化參量整合后的Multi-TSP算法（SFO）和本文所述非支配排序的多目標任務分配算法，并以最長距離和平均距離之差與總路徑的比值為評價標準進行評判。

4.2 計算結果

由于優化目的為最小化多機器人系統總路程并減少多機器人系統的距離方差，選擇機器人各組最長距離和最大路徑偏差占比作為評判標準，以此作為衡量該算法對任務分配均衡性能和最長執行時間的標準。

采用Python 3.6.5進行編程，在CPU為3.5GHz，內存為6GB的臺式機上進行測試，測試結果如圖3所示。

圖3 100節點下不同機器人最大子路徑

圖4 150節點下不同機器人最大子路徑

圖5 200節點下不同機器人最大子路徑

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

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

由表3統計結果，各機器人最大路徑和平均路徑的差值均小于平均路徑的2%，從而保證運動路徑較小機器人因為運動路徑較大的機器人工作時間過長而出現閑置的概率較低。

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

圖6 每代最優個體得分曲線

圖7 全局最優解分數變化曲線

4.3 對比分析

為證明該任務分配算法的均衡性，本節采用eil51數據集，與傳統單目標Multi-TSP算法和SFO算法進行比較，并分別以平均路徑，總路程和最大子路徑為評價標準。

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

圖8 總路徑長度

圖9 平均路徑長度

圖10 最大子路徑

圖11 三種算法的目標特征散點圖

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

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

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

同時獲得了在eil51下的實驗結果的對比圖。

圖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

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

5 結語

基于快速非支配排序的多目標優化遺傳算法較傳統Multi-tsp算法具有機器人利用率高，最大運行時間短的特點，可以提高智能倉儲系統的實際工作效率，本文為多目標智能倉儲機器人的路徑規劃構建對應的優化目標函數組，并結合非支配排序算法和精英策略以及種群重啟和精英庫策略設計了遺傳算法。實驗結果表明，上述算法路徑尋優性能，路徑均衡性能均優于傳統Multi-TSP算法。

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

本文對多優化目標的多機器人靜態任務分配問題進行了研究，但未對實際路徑網絡時變性問題進行研究，這是實際生產生活中更為常見的問題，因此需要針對這類問題進行進一步研究。