基于遺傳算法的倉儲機器人多目標路徑規劃方法

辜 勇，段晶晶，袁源乙，蘇宇霞

（武漢理工大學 物流工程學院，湖北 武漢 430063）

1 引言

智能倉庫中移動機器人有助于促進倉庫無人化操作及自動化運轉。隨著市場不斷擴大，單個機器人難以滿足日益復雜、繁多的任務需求，多機器人協同作業系統[1]應運而生，其具有更強的魯棒性和環境適應性。其中多機器人的路徑規劃[2]是實現當前多機器人系統在智能倉儲中應用的研究熱點。智能倉庫中多機器人路徑規劃是指，在倉庫復雜動態環境下多倉儲機器人能夠無碰撞、快速地完成揀選任務。根據多機器人路徑規劃的特點，該問題可以轉化為多維旅行商問題（Multidimensional Traveling Salesman Problem,MTSP）[3]。相對于旅行商問題（Traveling Salesman Problem,TSP），多個TSP的單純疊加不能構成MTSP的全局最優解，還需要考慮多機器人相互之間的協調、避碰。因此本文提出一種基于遺傳算法和A*算法相結合的混合算法解決倉儲機器人多目標路徑規劃問題。

多機器人路徑規劃屬于NP-hard問題，主要解決算法有：傳統算法[4]、智能優化算法[5]和其它算法等。其中遺傳算法[6]是一種典型的智能算法，它通過模擬生物體遺傳變異得到優勢種群的過程來解決問題，具有隨機并行搜索能力，能夠快速搜索尋找全局最優解。Bajrami,等[7]針對封閉條件下的靜態和動態障礙物環境，利用遺傳算法進行路徑規劃取得較好效果。裴以建,等[8]在遺傳過程中增加插入算子、刪除算子，使得機器人得到優化后的無障礙路徑。但大多數算法并不適應多機器人協同系統，未從整體出發，將多機器人路徑沖突與整體路徑規劃進行結合。

機器人行駛過程中，避免相互之間的局部動態沖突是多機器人規劃的關鍵問題。可采用交通規則[9]規定倉庫行駛方向，從而降低沖突發生數目，但犧牲了倉庫通道的利用率，而且仍存在不可避免的沖突。也可采用速度調整法[10]，借助增大或降低機器人速率等策略來避開沖突，該方法對系統性能要求比較高。夏清松,等[11]通過對機器人進行優先級排序，化解不同類型路徑沖突。通過以上文獻分析可知，優先級法雖然簡單易行、效率較高，但忽視了從減少路徑沖突數目的角度考慮問題。在實際路徑規劃中，A*算法[12]作為一種啟發式算法，通過啟發函數將搜索方向指向目標點，該算法對環境信息敏感，能直接有效應對動態環境下路徑規劃問題，根據優先級不同可迅速調整路徑。

本文從多機器人協調配合出發，利用A*算法規劃各機器人兩兩目標點之間的最優路徑，并結合不同機器人的優先級得到全局路徑；然后引入改進遺傳算法調整目標節點遍歷序列和化解路徑沖突方式，以實現多機器人路徑規劃全局最優。

2 環境建模

合理的倉庫環境建模方法有助于后續路徑規劃算法的設計。本文利用柵格建模法，提出一個高效、可重構的自動化倉庫模型，如圖1所示。倉庫由貨架、揀選臺、停放點和可行道路四部分組成，劃分成30×30的柵格。倉庫正中間擺放立體貨架用來容納倉儲貨物，是倉庫的主體部分；倉庫左側均勻分布4個分揀臺，機器人將貨物搬運到這里進行分揀；倉庫左下方為機器人停放點，為機器人充電或暫時停放空閑機器人。倉庫中空白柵格是行駛道路，每排貨架之間、每列貨架之間均為單車道。

智能倉庫的作業流程為：每個倉儲機器人都有n個揀選任務，分布在不同的貨架節點，各機器人需遍歷其目標節點完成揀選任務。倉儲物流機器人在收到出貨指令后快速響應，揀選所需貨物，然后包裝出庫。

圖1 倉庫地圖模型

3 節點間路徑規劃

在智能倉庫中，每個機器人根據目標任務，需要規劃無碰撞、高效率的路徑進行揀選作業。基本思路是用A*算法計算兩兩節點之間的路徑，按照目標節點的遍歷順序，得到單個機器人的全局路徑規劃；然后檢查機器人路徑間是否存在沖突。若存在沖突，則利用優先級法化解沖突，再繼續檢查是否存在新沖突，直到所有路徑之間無沖突產生。

3.1 A＊算法

本文采用A*算法進行路徑尋優。該算法設置open表和close表，搜索過程從初始節點出發，將其相鄰節點加入open表；通過估算相鄰節點的路徑代價f(n)，選擇f(n)最小的節點更新為當前節點，加入close表；重復該過程，直到到達目標節點。f(n)的計算公式是：

其中，g(n)指從初始節點移動到當前節點n的代價，h(n)指從當前節點n移動到目標節點所需的代價。兩者之和為f(n)，指經過當前節點n的總路徑代價。

3.2 沖突類型及化解

本文假設：（1）倉庫道路均為雙向單車道，僅允許單個機器人通過，可雙向行駛；（2）各機器人的行駛速度保持不變，避免相互之間發生追趕沖突；（3）機器人運行過程中不會出現意外故障；（4）每單位時間可行駛單位柵格距離，即1個單位路徑長度；（5）每個機器人執行多個目標任務，且每個任務只能由單個機器人完成。

在實際過程中多個機器人同時運行作業，其中兩個或多個機器人同時到達某位置，便會產生沖突。若沖突不能被及時化解消除，甚至會造成路徑死鎖。路徑沖突可分為以下3種典型類別：（1）相向沖突：指兩機器人在同車道相向行駛，其行駛方向呈180°夾角，兩者在同一時刻到達某節點。若發生該沖突，任一機器人暫停都會造成路徑堵塞。必須將其中一個機器人重新規劃路徑行駛，才能消除沖突。（2）交叉沖突：指兩個機器人的行駛方向呈90°夾角，同一時刻到達交叉路口某節點。化解該沖突可采用暫停策略，例如機器人Robot1在t時刻占用沖突節點，另一個機器人Robot2暫停等待；等到t+1時刻，Robot1已經安全通過，Robot2再占用沖突節點。結果是兩個機器人的總行駛路徑不變，僅增加一個單位的總行駛時間。（3）復合沖突：指相向沖突和交叉沖突同一時刻在同一個節點發生。具體如圖2所示。

圖2 路徑沖突類型

3.3 優先級

優先級是根據一定的準則或目標，給發生路徑沖突的機器人指定先后順序，有序化解路徑沖突。優先級高的機器人占據沖突位置，繼續按照原路徑行駛；優先級低的機器人可以選擇暫停，等待其他機器人行駛過后，再繼續前進；優先級低的機器人也可重新規劃路徑，避免路徑沖突的發生。化解沖突過程中，優先級的確定準則對倉庫總運行效率有著重要影響。

各機器人在全局路徑規劃過程中，忽略其他機器人動態變化。因此不僅會與其他機器人產生沖突，而且應對路徑沖突而調整路徑后，會造成新的沖突。例如，在時刻t時，Robot1、Robot2、Robot3的初始規劃路徑如圖3（a）所示，各機器人在倉庫內同時向各自目標行駛。可以預見全局路徑規劃中，在t+2時Robot1與Robot2發生沖突，在t+5時Robot1與Robot3發生沖突。當正常行駛到t+2時，需要確定Robot1和Robot2的優先級priority，此時有兩種優先級順序：（1）priority1>priority2，那么Robot1和Robot2按照圖3（b）順序通過路口。之后在t+5時，再消除Rrobot1和Robot3之間的路徑沖突，如圖3（c）所示。（2）priority1

依據上述分析，本文提出圍繞動態路徑規劃中的路徑沖突數目，決定優先級大小。將某機器人在全局路徑規劃中與其他機器人形成的沖突數目，命名為該機器人的基本沖突數目conflict_basic。另外，假定其他機器人的路徑均不變化，令該機器人作為次優先級，造成的新沖突數目稱為conflict_add。因此，本文提出機器人的總沖突數目為all_conflict，由式（2）得到。該值越大，機器人的優先級越低；相反，優先級越高。

因此，解決路徑沖突問題，首先應計算沖突中各機器人的總沖突數目，沖突數越小，優先級越高；若兩者沖突次數相同，則隨機選擇某機器人作為高優先級。

4 改進遺傳算法

隨著目標節點的增多，倉儲機器人的多目標點路徑規劃的復雜度也顯著提升。本節利用遺傳算法調節目標節點的遍歷序列，根據問題的具體特征對變量進行編碼，然后采用選擇、交叉、變異等遺傳操作，重復迭代后得到最優或次優解。

圖3 消除沖突序列圖

4.1 多目標任務規劃建模

假設robot(i)的揀貨任務有n個目標任務，將揀選目標隨機排列順序，得到分揀順序為Ti1,Ti2,...,Tin，其中任意兩個分揀節點Tix,Tiy之間的路徑為Ci(Tx,Ty)。robot(i)有n!種方式遍歷所有目標節點。

按照上文中A*算法計算各目標節點之間的路徑，可以得到robot(i)的距離矩陣Di：

在各機器人遍歷目標節點的基礎上，化解局部路徑沖突，才能得到可行的全局路徑長度，繼而轉化為遺傳算法中目標函數Z，即：

式中，L表示多機器人消除局部路徑沖突后，完成全部目標任務所需的路徑長度；v表示機器人勻速行駛速度。twait表示各機器人為解決路徑沖突所耗費的總等待時間。

4.2 符號矩陣編碼法

常見編碼方式包括二進制編碼法、矩陣編碼法、浮點編碼法、符號編碼法等。符號編碼法是指將個體染色體的基因值取為符號集，如{A1,A2,...,B1,B2,...}。矩陣編碼法是指用矩陣的形式表示染色體基因。

根據問題特性，結合符號編碼和矩陣編碼的優點，創新編碼方式，提出符號矩陣編碼法。一方面，本問題中多目標節點各不相同，具有唯一性，可采用符號代表目標任務節點；另一方面，每個機器人的任務已分配完成，相互之間獨立，利用矩陣將多個機器人的目標節點進行組合排列。

將robot(i)的n個目標節點隨機分布排列為其中共有m個robot，可以組成單個染色體，即：

式中，chrom(k)表示第k個染色體，是m×n維矩陣，每一行表示單個機器人的目標任務節點。

4.3 遺傳操作

在遺傳過程中，“選擇”操作選擇優勢個體、“交叉”操作交換個體的染色體基因、“變異”操作指個體染色體基因突變，產生新個體。這三種遺傳操作幫助優勢群體基因存活下來。與此對應的是選擇算子、交叉算子和變異算子。

（1）選擇操作。本文利用輪盤賭選擇法，根據各個個體的適應度大小來決定該個體基因保留的可能性，適應度越大，被選擇的概率就越大；反之亦然。某個體適應度為fi，種群大小為NP，則它被選擇的概率為：

（2）交叉算子。常見交叉算子主要有：單點交叉、兩點交叉、多點交叉等。由于本文中每個個體染色體包含多個目標節點，每個robot的目標節點為一行，行與行之間不相同。因此選擇多點交叉算子。即在個體染色體矩陣編碼中的每行都選擇交叉點，然后兩兩個體配對交叉。

（3）變異算子。本文采用實值變異方式，把相應的基因用取值范圍內的其他隨機基因代替。

4.4 算法流程圖

針對倉儲機器人群的多目標點路徑規劃，融合改進優先級策略和遺傳算法，可以得到本文的算法流程。首先建立各個移動機器人關于目標節點的路徑信息表；然后依照改進優先級法計算總行駛時間，并轉化為遺傳算法中種群的個體適應度；對種群進行選擇、交叉、變異操作；經過數次迭代，得到最優個體，即為最優路徑規劃結果。如圖4所示。

圖4 流程圖

5 模型仿真實驗

為驗證本文算法改進的有效性，在圖1倉庫地圖模型的基礎上，將本文提出的基于遺傳算法的倉儲機器人多目標路徑規劃方法（簡稱算法1）與基于常規優先級法的路徑規劃算法[11]（簡稱算法2）以及交通規則下的路徑規劃算法[9]（簡稱算法3）進行比較，證明基于遺傳算法的倉儲機器人多目標路徑規劃算法能有效提高多倉儲機器人系統的運行效率。其中算法2和算法3均為目前普遍使用的先規劃最短路徑，再進行動態路徑規劃的算法。

仿真實驗基于相同數量的機器人，運用不同規劃算法，執行不同任務數量，比較算法的路徑規劃長度和行駛時間。機器人數量為5，目標任務數量依次為15，20，25，30，35，40。其中算法1由于基于遺傳算法，每次運行結果可能不盡相同。因此每個任務量都運行100次后，選擇眾數作為算法1的實驗結果。算法的路徑長度對比結果如圖5所示。

圖5 不同算法的路徑長度比較

首先比較不同算法規劃的路徑長度。總的來說，隨著任務量的增加，總路徑長度均呈上升趨勢。在任務量較少時，路徑之間的沖突較少，算法1和算法2的路徑長度幾乎沒有差別，算法3因交通限制致使繞路行駛，導致路徑較長。隨著任務量逐漸增加，算法1逐漸優于算法2。這是由于路徑沖突數目的增加，算法1通過計算沖突數目和路徑長度，調整了目標節點的序列，從而有效縮短了路徑長度。算法3隨任務量的增加，多機器人之間由于交通規則存在，路徑沖突對其影響不大，所以路徑長度增長緩慢，后期優于算法2。

對3種算法的行駛時間進行比較，具體如圖6所示。總趨勢和圖5的路徑長度趨勢相似，呈上升態勢。由于算法1能有效減少路徑沖突數目，且路徑長度并沒有太大變化，從而節約了更多的時間，因此在總行駛時間方面的優勢更加明顯。

圖6 不同算法的總行駛時間比較

6 結束語

本文針對智能倉庫多機器人協調分揀作業過程，提出一種基于遺傳算法的倉儲機器人多目標點路徑規劃方法。根據機器人間路徑沖突類型以及總沖突數目，調整優先級排序化解沖突；然后將多目標規劃與機器人路徑規劃進行融合，運用遺傳算法從全局出發，調整倉庫總體運行效率。最后通過仿真實驗，驗證了該方法的可行性和高效性。.