帶時間窗的車間搬運機器人路徑優化建模及算法研究

任劍鋒, 葉春明, 楊 楓

(1.上海理工大學 管理學院,上海 200083; 2.河南財經政法大學 計算機與信息工程學院,河南 鄭州 450018)

0 引言

“中國制造2025”戰略指出我國要大力推進信息化和工業化深度融合，加速推進生產過程智能化進程[1]；眾所周知，車間是生產制造的關鍵環節，提高車間智能化管理水平，挖掘潛能、節約成本、降低能耗是學術界和工業界共同關心的課題。

以客戶為中心，小規模、高靈敏度的個性化生產模式成為當前搶占市場、贏得客戶的有力工具，車間搬運機器人的大量引進改變了以傳送帶進行物料配送的大規模生產模式，可在車間中準確高效地完成配送任務；多臺搬運機器人則可組成柔性配送系統，并可以隨著生產工藝流程的調整及時變更配送路徑，使同一條生產線上能夠同時加工多種產品，極大地提高了生產的柔性程度，生產效率得到很大提高，但同時人們也發現機器人的高額投資卻與收益不成比例，如何充分挖掘機器人的生產潛能成為新的研究熱點。合理分配機器人數量，改變機器人單一配送或回收任務為同時執行配送和回收任務，將機器人單獨作業升級為多機器人同時作業模式；如此以來，我們就要考慮車間生產過程中存在的需求、供應、設備故障和其他類型的各種不確定干擾因素；另外，多機器人作業模式下，還要考慮機器人與障礙物或其他機器人之間可能存在的碰撞問題，合理設置避障機制。本文正是以車間場景下搬運機器人面對同時配送和回收任務為背景，以機器人數量、運輸成本和時間懲罰成本的加權和為目標，解決機器人路徑優化問題建模及算法研究。

遺傳算法較早被用來求解機器人路徑優化問題，Panchu等用遺傳算法求解機器人的作業完成時間最小問題[2]；李妍峰等根據接收到的動態信息來進行機器人路徑優化[3]；也有學者提出基于遺傳算法來優化任務點的順序[4]，通過優化和模擬完成任務的時間來確定機器人在連續點之間的最短路徑[5]；雙種群遺傳蟻群算法也被用來求解該問題[6]，也有學者使用改進遺傳算法求解類似問題[7～9]；通過對遺傳算法在求解機器人路徑優化問題分析發現，該算法在可以求解得到小規模機器人路徑優化問題的最優值，但收斂速度較慢，難以很好滿足車間生產模式下的敏捷需求。蟻群算法也被成功應用于機器人路徑優化問題，裴振兵等提出用改進蟻群算法求解機器人避障問題[10]；趙宏才等提出建立α和β的互鎖關系來定義信息素更新規則[11]，也有學者提出基于蟻群算法求解高質量的配送路線問題[12]；王輝等提出用改進蟻群算法求解泊車系統路徑優化問題[13]；張建同等提出用混合蟻群算法求解卡車路徑規劃問題[14]；也有學者提出一種求解路徑優化問題的混合蟻群算法[15]；分析發現，蟻群算法在求解機器人路徑優化問題時具有魯棒性較強、分布式特征明顯、可靠性高等優點，缺點則是會以一定概率陷入局部最優解。強化學習[16]算法近年來也被應用于路徑優化問題，于乃功等采用改進后的Q學習算法求解并取得了很好的效果[17]；高樂等提出一種改進的Q學習算法應用在多障礙環境下機器人的路徑規劃問題[18]；還有學者設計了一種改進的模糊Q學習算法求解路徑規劃策略問題[19]。還有學者用螢火蟲優化算法進行車輛路徑優化問題求解[20]；以及采用禁忌搜索算法求解車輛路徑優化問題[21,22]，對本文問題研究也提供了一定的啟發。

綜上，國內外學者對機器人或類似研究對象的路徑優化問題有較為深入的研究，在理論、模型和算法方面也取得了豐碩的成果，但在車間特定場景下同時進行配送和回收任務的多機器人作業路徑優化問題研究成果并不多見；同時，相關研究多采用遺傳算法、蟻群算法等智能仿生算法，用強化學習算法解決車間場景的機器人路徑優化問題更是少見；同時，已有成果考慮的多為靜態環境下的路徑優化問題，并不符合車間場景下不確定因素眾多的實際情形。比如車間生產環境下存在的動態障礙物出現、機器人自身性能波動、緊急訂單插入、加工設備故障等動態因素；因此，本文提出一種強化學習遺傳蟻群算法進行問題求解，結合蟻群算法的魯棒性強、高可靠性等優點，同時引入遺傳算子的交叉、變異機制跳出局部最優解，同時將強化學習算法對環境變化的感知能力有機結合起來，有效彌補單一算法的缺點和不足；全局路徑通過嵌入遺傳算子的蟻群算法求解，局部子路徑通過強化學習算法求解，同時在子路經上捕捉車間動態出現的碰撞信息，并實現動態避障，最終求出以總成本最低為目標的路徑優化問題。

1 問題描述

車間生產中每種產品所需的配件不同，每臺加工設備均要及時供給物料，同時要及時取走該加工設備上已加工的產品，否則就會造成庫存增加甚至導致設備暫停，對于高精尖且需要較長預熱時間的設備，頻繁關停或空轉均會造成成本增加，甚至對設備造成損害。

在車間場景下，本文構建了多機器人的柔性搬運系統，根據生產車間存在眾多不確定因素的實際情形，本文考慮在時間窗內為加工設備提供配送和回收服務，以確保加工設備及時得到物料供應，同時取走工位上的加工成品，通過時間窗口來降低車間不確定因素帶來負面影響；故將搬運機器人對每臺加工設備的到達時間設置為時間窗[Eti,Lti]，同時明確搬運機器人對每臺設備的服務時長。

車間內部每臺設備之間有一定的物理距離，可以確保搬運機器人能夠穿梭行駛，且假定每臺設備的位置和配送中心的位置、每臺搬運機器人的最大運載能力已知，并且機器人的最大運載能力大于每臺加工設備的單次配送或回收量。每臺設備只能由一臺機器人服務。為使問題簡化，搬運機器人的電力續航能力較強，不再考慮機器人的最大運行距離問題。根據物料配送和產品回收的任務情況，合理安排搬運機器人的數量，要求完成物料配送和產品回收任務的同時，還要使每臺加工設備在時間窗內得到服務，實現機器人數量即基本成本、運輸成本和時間懲罰成本加權總成本最小。車間只設置一個配送-回收中心，機器人在完成配送-回收任務之后均返回中心，形成閉合的運行軌跡，如圖1所示。

圖1 配送路徑示意圖

車間環境下機器人的配送問題路徑優化與一般的pickup-delivery問題相比，因為車間環境狹小、設備價值較高因素，要考慮機器人與其他機器人或障礙物之間可能發生的碰撞問題，避免因碰撞而導致末端執行工具的損壞，可能發生碰撞時，機器人傳感器及時發送信號給控制系統，進而緊急調整配送路徑；因此，結合車間環境下的配送回收問題特殊性，動態避障問題是本文在設計算法時加入強化學習部分的主要原因。

2 模型構建

車間有R臺最大運載能力均為Q的搬運機器人在時間窗[Eti,Lti]為M臺加工設備提供配送-回收服務。

Eti表示機器人對設備i的最早開始服務時間，Lti表示最遲服務時間。

ti表示機器人到達設備i的時間，并在完成對設備i的服務后經時間tij運行至下一個服務對象j，到達時間為tj，wi表示機器人對設備i的服務時長。

Qrij表示機器人r從設備i到j的過程中是否產生碰撞。

di表示該設備需要的配送量，pi表示該設備需要的回收量，eij表示機器人在經過設備i之后的配送總量，之后前往j設備；fij表示機器人在經過設備i后的回收總量，之后前往j設備；且任何時候機器人的配送量與回收量之和不能超過機器人的最大運載能力；配送-回收中心和各加工設備的空間位置已知，并用相應的坐標表示，用dij表示從加工設備i到設備j的距離，決策變量xijr和yir定義如下。

問題的數學模型如下:

(1)

(13)

該模型中式(1)表示目標函數，即車間總的配送-回收成本最低；式(2)表示所有機器人均從配送-回收中心出發；式(3)表示機器人完成任務之后返回配送-回收中心；式(4)、(5)和(6)表示有且僅有一臺機器人到達某一設備，并提供服務；式(7)、(8)和(9)表示服務時間約束；式(10)表示設備所需的物料配送量約束；(11)表示設備所需產品回收量約束；(12)表示機器人的運載能力限制，(13)中Qij值為1表示從機器人r從設備i到j的過程中是否產生碰撞，0表示未產生碰撞。

3 算法設計

3.1 位置掃描

采用掃描法來獲取加工設備的位置，即用極坐標來表示加工設備的位置，隨機選取某一設備位置為起始點，將其角度設為零度，以機器人的最大運載能力為限制條件進行設備節點分割，得到若干符合運載量限制的子區域，取子區域的幾何中心并設置為虛擬節點。

3.2 節點選擇策略

(14)

3.3 信息素更新策略

信息素的更新方式至關重要，信息素更新過快，會導致“早熟”而陷入局部最優，更新過慢則會降低收斂速度。因此，本算法中的信息素更新方式根據路徑的適應度值來動態更新信息素的方式，如式(15)。

(15)

其中Q′為常數，適應度值較小的路徑上信息素增加量大，反之，信息素增加量小；大量實驗證明，式(15)的信息素更新方式可以有效提高收斂速度。

3.4 編碼

本算法中采用路徑表示法編碼，每個可行解編碼即表示經過的節點序列，對于有n臺加工設備的車間，m臺機器人來執行配送-回收任務的問題，用0到n+m-1共n+m個數字編碼為(0-x1-x2-…-xn+m-1)，0表示配送-回收中心，在編碼中第一臺機器人用0表示，其余機器人則用n+1,n+2,…,n+m-1表示。之所以第一臺機器人也用編碼中的0表示，是為了減少編碼長度，同時不影響編碼的結構特征和信息表達。

如車間有10臺加工設備，4臺機器人參與服務，則編碼0-3-5-11-2-7-8-12-4-6-1-13-9-10表示一個可行序列，編碼序列表達的配送-回收子序列為:

機器人1服務路線：O-3-5-0

機器人2服務路線：O-2-7-8-0

機器人3服務路線：O-4-6-1-0

機器人4服務路線：O-9-10-0

根據機器人路徑優化的特點，為保留染色體的優秀基因，可行解的較優染色體采用如下的交叉策略，設兩組染色體分別為A1和A2。

(1)隨機生成染色體交叉的起始位置和交叉段長度如下：

本文中交叉策略保留染色體中的優秀基因片段，并且可以加快收斂到最優解，缺點是容易陷入局部最優；實驗證明，遺傳算子在變異過程中可以對信息素產生明顯的擾動作用，跳出局部最優解。

3.5 動態避障策略

本算法中采用強化學習算法來求解子路徑的優化及動態避障問題。

(1)狀態迭代

本算法中構造的狀態值函數迭代方程為：

V(sk)←V(sk)+α[rk+1+γV(sk+1)-V(sk)]

(16)

即:V(sk)←αrk+1+γV(sk+1)+(1-α)V(sk)

(17)

其中α為學習率，γ為折扣因子，V(sk)為當前狀態值，V(sk+1)為下一狀態值，通過式(16)的反復迭代，最終使方程收斂到最大狀態值，進而得到最優路徑[23]。

將配送-回收中心抽象為節點0，在服務子路徑中的加工設備抽象為中間節點①→，將終點也抽象為節點0(即只有一個配送-回收中心)，如圖2所示。

圖2 強化學習路徑尋優示意圖

從出發節點0開始前往子路徑上的任意其他節點，例如路線0→①→③表示從配送中心出發首先前往節點1服務，然后再前往節點3服務，以此類推，節點①與節點①之間沒有連線，表示不允許從該節點仍回到該節點。

本問題中動態選擇路徑的過程中不存在狀態轉移的概率模型，因此選用Q-learning算法，將路徑長度作為強化學習迭代過程中的獎勵值；同時，因為本文要解決有時間窗和服務時間的機器人配送-回收問題，因此，將每個加工設備上的服務時間作為該節點的狀態值，并采用貪婪策略選擇路徑，如式(18)所示。

(18)

算法流程如圖3所示。

圖3 強化學習遺傳蟻群算法流程

(2)動態避障

車間環境下的障礙物一般可分為長期靜態障礙物、臨時靜態障礙物和臨時動態障礙物共三類；因前兩類的研究已較為成熟，本文主要以臨時動態障礙物為研究對象，通過強化學習算法感知超聲波、紅外等傳感器數據來實現動態避障[24]。

如圖4所示的問題，在常規情況下算法按照約束條件可以快速搜尋到最短路徑1-3-7-11-16-19-20，如果最優路徑上第11個節點動態出現障礙物，根據傳感器反饋的障礙物信息，將該節點的狀態值設為無限大，從而快速避開障礙物并搜尋到其他可行路徑1-3-7-12-16-19-20。

圖4 動態避障示意圖

圖5 避障迭代曲線

圖5表示了常規約束條件下和動態避障后的迭代曲線。通過對比可以發現，在常規情況下，強化學習算法可以快速收斂到最優值28；在障礙物出現后，強化學習算法可以迅速捕捉到節點狀態值的突然變化，在計算開銷很小的情況下實現緊急避障，并重新搜尋到最優路徑值32。

從實驗中還可以發現，假如機器人行駛在節點3與節點7之間的路徑上，此時節點11產生臨時動態障礙物，在重新規劃路徑時，不需要重新設置起始點，即障礙物出現之前的已規劃路徑不會改變，為機器人執行配送任務的連續性提供了支持。

4 模擬仿真

4.1 實驗環境及參數設置

本文在Intel i7處理器使用Matlab2017a進行實驗，其中蟻群算法的信息素重要程度因子取值為1，啟發函數重要程度因子取值為5，信息揮發因子為0.1，常系數Q為1；遺傳算法的交叉概率為0.85,變異概率為0.1,遺傳代溝為0.8；強化學習算法的學習率取值為0.1，折扣因子為0.9，三種成本參數如表1所示。

表1 成本參數表

本文將車間生產的配送-回收中心作為節點0，取其坐標值為(30，60)，車間內共有加工設備45臺，分別以相應的坐標X值和Y值表示其位置，每臺加工設備的配送量和需回收量已知，以及接受服務的最早時間和最遲時間，每臺加工設備有明確的配送和回收的服務時長，如表2所示。

表2 加工設備信息表

4.2 實驗及對比分析

用本文算法對問題進行求解，設每臺機器人的基本成本為300，每次實驗的最大迭代次數為500次，可以發現在200次迭代以后基本可以得到較滿意解，并可以得到機器人基本成本為2100，即需移動機器人7臺來完成物料配送和產品回收任務，結果如表3所示。

表3 最優配送路徑

表中SP(Service path)表示服務路徑，AC(Actual capacity)表示機器人的實際運載量，DW(Dead weight)表示最大載重量，FR(full-load ratio)表示滿載率。

同時，可求得運輸成本為1970.13；時間懲罰成本為0，即所有加工設備均可在時間窗內得到服務，總成本代價為4070.13。對每臺機器人的滿載率計算可以發現運載能力得到了充分利用。

為了進一步驗證本文算法的有效性，與Wang等[25]公開的用遺傳算法(GA)求解的20個基本算例結果進行對比，其中小規模算例(10個配送節點算例3個，20個配送節點算例2個)共5個，中等規模算例(50個配送節點)3個，大規模算例(100個配送節點)12個。基于以上基準算例，同時用Chao Wang等[26]公開的模擬退火算法(PSA)進行求解并對比。

表4和表5中的NR(Number of Robot)表示分配的機器人數量，TD(Travel Distance)表示完成配送任務的行駛距離，NO(Number of obstacles)表示在算例中隨機出現的區間[0,5]之間的動態障礙物個數。

小規模算例計算結果可以發現，使用RLGA算法對5個算例進行求解，RCdp1004算例的計算結果達到理論最優值，其余四個算例的計算結果與理論最優值相比，與理論最優值差距的平均值是0.26%，可見本算法在小規模算例中的計算結果可以很好的逼近理論最優值，如表4所示。

小規模算例RCdp1001的求解路徑如圖6所示，該算例加入動態障礙物之后的求解路徑如圖7所示。

對中等規模和大規模的15個基準算例分別采用GA、PSA和RLGA進行求解，將實驗結果分為兩種情形，第一種情形是在算例中加入了障礙物的7個算例；由表5可知，7個算例添加的障礙物平均個數是3，其TD值均較基準結果有所增加，其中GA計算結果平均增大0.33%，PSA計算結果平均增大0.27%,RLGA計算結果平均增大0.17%，在三種算法計算結果中，RLGA算法表現最好，可見RLGA算法對動態避障問題有較好的解決機制，可以將障礙物對路徑優化的帶來的干擾降到合理范圍，得到比GA和PSA優秀的結果；第二種情形是未出現障礙物的算例共8個，其中有2個算例節約了1臺機器人，同時伴隨TD值略有增加，其余6個算例中的3個算例TD值與GA算法和PSA算法計算結果相同，剩余3個算例的TD值有不同程度降低，平均降低0.34%；可見，RLGA算法可以得到更優的結果。

在算法的計算速度方面，選取小規模算例(10個配送節點)、中等規模算例(50個配送節點)、大規模算例(100個配送節點)問題的GA、PSA和RLGA算法的收斂曲線對比如圖8(a)、(b)、(c)所示。

比較發現，在求解小規模問題時，RLGA算法在收斂速度和解質量上略優于其他兩種算法；在求解中等規模和大規模問題時，RLGA算法的求解質量和速度上要明顯優于GA算法和PSA算法計算結果。

算法在解決大規模配送問題時優勢更加明顯，在考慮動態障礙物和無障礙物兩種情況下，求解質量和速度均優于其他兩種算法，表明RLGA算法的優越性。

表4 RLGA算法與理論最優值對比結果

表5 GA、PSA、RLGA算法結果

圖6 RCdp1001算例路徑

圖7 RCdp1001算例加入障礙物后路徑

圖8 GA、PSA、RLGA算法收斂曲線對比

5 結論

本文提出強化學習遺傳蟻群算法來求解車間場景下的搬運機器人路徑優化問題，引入掃描法對設備節點進行聚類劃分，將復雜問題簡化；借助強化學習的序貫決策和環境感知能力，結合蟻群算法的信息素更新策略和遺傳算法的交叉、變異機制實現車間搬運機器人同時執行配送和回收問題的路徑優化，通過與基準算例的結果比較表明算法在解質量和求解速度上的優越性。

本算法中強化學習的狀態值和獎勵值分別由加工設備所需的服務時長和路徑長度決定；實驗發現，如果設置動態的狀態值和獎勵值可以更好地體現車間實際情形，同時加入機器人行為要素，同時考慮更復雜的避障要素會進一步提升算法在理論和應用上的價值。