基于遺傳算法的多移動機器人協同調度方案

陳鵬慧，蔡　瓊，彭華順

?

基于遺傳算法的多移動機器人協同調度方案

陳鵬慧，蔡瓊，彭華順

摘 要：針對柔性制造系統（FMS）中多移動機器人的協同調度問題，提出了一種基于遺傳算法(GA)的協同調度優化方案。首先，將非搶占式任務和移動機器人的動作編碼成一個染色體。然后，對染色體進行交叉、突變過程，以產生新染色體，并對不符合要求的染色體進行修復。再后，以總完成時間作為適應度值來評估染色體的質量，并選擇下一代的母體。重復迭代過程，獲得最優染色體，實現最小化任務完成時間。實驗結果表明，該方案能夠獲得最優的調度方案，非常適用于具有制造和運輸任務的機器人調度應用。

關鍵詞：移動機器人；協同調度；遺傳算法；最小化任務完成時間

0　引言

移動機器人已廣泛應用于工業領域。移動機器人通過安裝在移動平臺上的機器人機械手臂和視覺系統擴展了工業機器人的應用領域[1]。因此，移動機器人不僅能像自動搬運車那樣運輸材料或零件，而且還能執行工業任務，例如機床的安裝等。因此，移動機器人是一種具有靈活性和適應性的制造助手，其很容易適應新任務且能彌補傳統機器人有限的可變性[2]。然而，隨著車間移動機器人數量和機器人任務的增加，怎樣合理調度機器人工作，避免產生碰撞和閑置，對提高機器人的利用率具有重要意義[3]。

移動機器人調度問題一般應用于柔性制造系統（Flexib -le Manufacturing Systems, FMS）[4]，以一種高效方式利用移動機器人，以最短的工作時間完成任務。目前，學者對FMS下自動搬運車運輸任務的調度進行了大量研究。例如，文獻[5]在FMS中考慮機床和移動機器人調度，提出了一種動態規劃模型來實現最優化生產和車輛調度。文獻[6]使用混合整數規劃（Mixed Integer Programming，MIP）公式來求解這種最優化問題。

盡管在FMS中存在一些與移動機器人調度相關的研究，但對能夠完成運輸和制造功能的移動機器人調度的研究較少。本文中移動機器人能靈活的在制造任務和運輸任務之間切換，且允許可以中斷制造任務而完成運輸任務。文獻[7]提出了一種MIP模型來處理與本文考慮問題很接近的問題。然而，其假設無論何時發生搶占式調度，任何移動機器人僅能執行一次運輸任務。

本文針對FMS中的應用，提出一種基于遺傳算法（Gene -tic Algorithm，GA）的多個移動機器人調度方案。首先，將非搶占式任務和移動機器人的動作編碼成一個染色體，染色體中基因的個數為所有任務中操作的數量。然后，對染色體進行交叉、突變和修復過程。再后，以總完成時間作為適應度值來選擇下一代的母體，進行再次遺傳過程。最終獲得最優染色體，實現任務完成時間最短。實驗結果表明，本文方案能夠獲得最優的調度方案。

1　問題描述

柔性制造系統（FMS）是一種能夠生產不同類型零件的自動生產系統。FMS一般包括自動化機床、材料搬運設備（例如自動搬運車或移動機器人），和一臺中央控制器。與自動搬運車相比，移動機器人提供了更高等級的靈活性，不僅能運輸零件，而且能完成制造任務[8]。本文考慮一個包含移動機器人和機床站的FMS，系統的典型布局如圖1所示：

圖1　FMS中移動機器人的典型布局

在FMS中，將任務分為兩類：非搶占式任務和搶占式任務。非搶占式任務為執行任務過程不能中斷，直到任務完成。相反，對于搶占式任務，在任務執行過程中允許多次暫停去執行其他任務，并可返回繼續執行該任務。在制造過程中，每種搶占式任務由移動機器人在特定機床上完成。當執行搶占式任務時，移動機器人可能會在一些時間內被調度去完成一些非搶占式的運輸任務。每個移動機器人暫時中斷搶占式任務時，其能完成多個的運輸任務。描述了一種搶占情況下的例子如圖2所示：

圖2　描述搶占式任務過程

所以，為了最大化利用機器人，需要一種有效的機器人調度機制。

機器人調度機制的主要目的是尋找能夠最小化完工時間的最佳調度方案。為了構建機床和移動機器人的調度機制，設定以下假設：

（1）在調度過程的開始階段，位于機床上的每種任務的第一次操作是可用的（操作為一個任務中的子任務）。

（2）預先知道每種零件的運輸線路。

（3）每個移動機器人在同一時間僅能運輸一種零件。（4）輸入和輸出緩沖空間足夠大。

（5）運輸時間與機床相關且是確定的。

（6）裝貨和卸貨時間包含在載貨運輸時間中。

（7）處理時間是確定的。

（8）本文不考慮交通阻塞、移動機器人擁堵、機床故障或破舊等情況。

機床和移動機器人的調度問題是一個NP困難問題[9]，且隨著問題規模的增加（例如任務數量、機床或移動機器人數量的增加），計算時間會成指數增長。所以，需要一種優化算法來求解調度問題。為此，本文提出一種基于GA的調度機制，在滿足一些實際約束條件下，最小化完工時間。

3　基于GA的協同調度機制

GA是一種模擬自然進化過程來尋找最優解的人工智能技術[10]，本文基于GA開發了一種機器人調度機制。本文采用的GA的流程圖如圖3所示：

圖3　本文GA算法流程圖

包括以下主要步驟：染色體編碼和初始化；染色體解碼和適應度評估；交叉、突變、選擇過程和修復過程。

3.1 染色體編碼和初始化

以一個染色體表示一個調度方案，染色體由非搶占式任務序列和移動機器人編碼形成，染色體中的每個基因由兩部分組成。第一部分表示非搶占式任務和操作，第二部分表示移動機器人執行運輸任務。如果第一部分包括任何首次操作，則表示不存在傳輸任務，因為在調度的開始階段，位于機床上的操作是可用的，所以基因的第二部分可能為0值。染色體的長度等于非搶占式操作的總數。圖4描述了一個包含3種任務的6種操作、3臺機床和1臺移動機器人的調度方案的染色體編碼例子，如圖4所示：

圖4　染色體編碼結構舉例

圖4中染色體第一個基因“11,0”表示在M1機床上執行任務1的制造操作1；第三個基因“12,1”表示在M1機床上移動機器人執行任務1中的空車運輸操作2；第五個基因“22,2”表示在M2機床上移動機器人執行任務2中的載貨運輸操作2。

在初始化階段，隨機生成初始化種群中的染色體。通過基因構建每個染色體。為基因的第一部分分配一種合理操作。如果該合理操作是首次操作，則基因第二部分為 0。否則，隨機選擇移動機器人。本文初始化染色體種群的過程，如圖5所示：

圖5　染色體初始化過程

3.2 染色體解碼和適應度評估

在初始化染色體之后，需要以總執行時間為適應度值，對染色體進行解碼并評估其適應度，用于之后的遺傳過程。本文解碼和適應度評估過程如圖6所示：

圖6　染色體解碼和適應度計算過程

具體描述如下。

步驟1：解碼基因的輸入信息，例如非搶占式任務、機床和移動機器人。

步驟2：獲得以下信息：分配給運輸任務的移動機器人到達機床的時間；移動機器人上一次運輸的目的地機床；處理搶占式任務的機床；處理上一個任務的機床；分配處理該任務的機床；以及位于該機床的最后一個任務。

步驟3：當搶占式任務暫停時，更新移動機器人處理的搶占式任務信息，同時更新總處理時間。

步驟4：根據第2步獲取的信息調度位于分配機床上的非搶占式任務。然后檢查當前基因是否為染色體的最后一個基因。如果不是，返回第1步。否則，檢查是否完成所有搶占任務。如果沒有，返回步驟5，否則，返回步驟6。

步驟5：更新未完成的搶占式任務和它們的完成時間。

步驟6：計算染色體的適應度，適應度等于所有非搶占式和搶占式任務的最大完工時間。

3.3 遺傳和修復過程

遺傳過程包含交叉、突變和選擇過程，用于產生每代的新后代。根據比例選擇法選擇父代染色體，以交叉率為Pc對兩個父代染色體進行交叉過程，進而產生后代。再執行突變率為Pm的突變過程，使染色體隨機發生變化。其中，根據本文染色體的編碼結構，本文設定2次突變。第1次突變是在染色體上隨機選擇兩個突變點且交換這兩個的位置，第2次突變是隨機選擇一個移動機器人來代替基因中分配移動機器人，2次突變過程如圖7所示：

圖7　突變操作

由于突變過程產生的染色體可能不合理。因此，需要修復過程來修復這些染色體。修復過程通過交換屬于相同任務的位置信息來產生有效序列。最后，根據選擇過程，選擇優良染色體用于后續迭代的繁殖過程，最終獲得最佳解。

4　實驗及分析

本文構建一個實驗場景，包含5臺機床、5種任務的9種操作，其中7個操作是非搶占式操作，其它操作是搶占式操作。考慮具有2臺移動機器人，實驗場景的布局如圖1所示。每個任務的處理時間和任務之間的優先級關系如表1所示：

表1　任務描述

移動機器人從一臺機床到另一臺機床的運輸時間如表2所示：

表2　移動機器人的運輸時間(單位時間)

對GA參數，設定種群大小為50，交叉概率為Pc=0.6，突變概率為Pm=0.1，迭代次數為200。在VB.NET上完成算法的編程，并運行在配置為Intel? Core i5 2.67GHz 處理器、4GB RAM的PC機上。

通過仿真實驗，經過200次迭代，本文算法獲取的最佳解決方案為：11,0-21,0-22,2-31,0-12,1-23,2-32,1。另外，本文算法的計算時間低于1秒。最佳方案中機器人執行任務的甘特圖如圖8所示：

圖8　最佳解決方案的甘特圖

圖8中深色方框表示搶占式任務，其它表示非搶占式任務，實線箭頭表示載貨運輸，虛線箭頭表示空車移動。

從圖 8可以看出，完成所有任務的時間或完工時間為164個單位時間。另外，機器人R1兩次中斷它的搶占式操作41來完成非搶占式運輸任務12和32。中斷將搶占式操作44分為3個子段。另一方面，機器人R2在返回它的機床之前，為了完成兩次連續運輸任務，即非搶占式操作 22 和23，機器人R2終端搶占式操作51一次。實驗結果表明，本文算法生成的解決方案具有有效性。

由于目前還沒有與文本研究對象完全一致的方法，只有文獻[14]與本文最為相似，本文將其提出的MIP模型用于本文場景，最終獲得的完成時間為285個小時，比本文方案多了近20個小時。這是因為其方案中的移動機器人不能在中斷搶占式任務期間完成多次運輸任務，這也不太符合實際情況。綜上說明，本文方案能夠獲得最小完成時間的方案，且適合用于實際車間調度情況。

5　總結

本文研究了在FMS中考慮搶占式任務，機床和移動機器人的最優調度問題。本文研究中的機器人可以暫停正在執行的搶占式任務，來完成可能的多個非搶占式運輸任務。本文基于GA來尋找一種能最小化完工時間的解決方案。實驗結果表明，本文獲得的調度方案具有最短的完工時間，為管理器制定任務層決策提供有力依據。

在今后研究中，將進行具有大量數據場景的實驗。并嘗試開發一種重調度機制來處理實時干擾問題，例如機床或機器人的損壞。

參考文獻

[1] 陳衛東, 朱奇光. 基于模糊算法的移動機器人路徑規劃[J]. 電子學報, 2011, 39(4):971-974.

[2] 房芳, 馬旭東, 錢堃,等. 智能環境下移動機器人任務規劃與執行系統架構設計[J].東南大學學報:(自然科學版), 2012, 42(1): 182-185.

[3] Dang Q V, Nielsen I. Simultaneous scheduling of machines and mobile robots[J]. Communications in Computer & Information Science, 2013, 36(5): 118-128.

[4] 李誠, 李爽, 馮毅萍,等. 基于時間Petri網和啟發式搜索的柔性制造系統調度算法[J]. 上海交通大學學報, 2015, 49(5): 708-713.

[5] Roh H K, Kim Y D. Due-date based loading and scheduling methods for a flexible manufacturing system with an automatic tool transporter[J]. International Journal of Production Research, 2010, 35(11): 2989-3004.

[6] Zarghami S. Exact Mixed Integer Programming for Integrated Scheduling and Process Planning in Flexible Environment[J].Journal of Optimization in Industrial Engineering, 2014, 37(6): 136-145.

[7] Nielsen I, Dang Q V, Nielsen P, et al. Scheduling of mobile robots with preemptive tasks[J]. Advances in Intelligent Systems & Computing, 2014, 29(4): 19-27.

[8] 趙金周, 袁建新. 基于遠程柔性制造系統的物料分配實驗設計[J]. 開封大學學報, 2010, 24(2): 90-93.

[9] 沈博聞, 于寧波, 劉景泰. 倉儲物流機器人集群的智能調度和路徑規劃[J]. 智能系統學報, 2014,9(6): 659-664.

[10] Choi J H, Kim J S, Jin H J, et al. Multi-Objective Genetic Algorithm based on Multi-Robot Positions for Scheduling Problems[J]. Journal of the Korean Society for Precision Engineering, 2014, 31(8): 689-696.

中圖分類號：TP242

文獻標志碼：A

文章編號：1007-757X(2016)07-0034-05

收稿日期：（2016.03.28）

基金項目：湖南省自然科學基金項目（14JJ7071）

作者簡介：陳鵬慧（1982-），女（漢），岳陽人，湖南信息職業技術學院，電子工程學院，講師，碩士，研究領域：機器人、智能控制，長沙，410200蔡 瓊（1982-），女（漢），益陽人，湖南信息職業技術學院，電子工程學院，講師，碩士，研究領域：智能控制，長沙，410200彭華順（1979-），男（漢），邵陽人，湖南信息職業技術學院，電子工程學院，講師，博士研究生，研究領域：機器人控制，長沙，410200

Multiple Mobile Robots Coordination Scheduling Scheme Based on Genetic Algorithm

Chen Penghui1, Cai Qiong1, Peng Huashun2
(1 Hunan College of Information, school of Electronic Engineering, Changsha 410200, China) 2 College of Electrical and Information Engineering, Hunan University, Changsha, 410082, China)

Abstract:For the issues that the cooperative scheduling problem of multiple mobile robots in flexible manufacturing system (FMS), a collaborative scheduling optimization scheme based on genetic algorithm (GA) is proposed. First, the non preemptive task and the movement of the robot are encoded into a chromosome. Then, the crossover and mutation process of the chromosome is carried out to generate the new chromosome, and repair the chromosome that does not meet the requirements. After that, the total completion time is used as the fitness value to evaluate the quality of the chromosome, and select the next generation of the population. Repeated iterative process, to obtain the optimal chromosome, and to achieve the task of minimizing the completion time. Experimental results show that the proposed scheme can obtain the optimal scheduling scheme, which is very suitable for robot scheduling applications with manufacturing and transportation tasks.

Key words:Mobile Robots; Coordination Scheduling; Genetic Algorithm; Minimize the Task Completion Time