動態倉儲環境下的多機器人路徑規劃方法

楊世團 于寶成，2* 吳云韜,2

1(智能機器人湖北省重點實驗室 湖北 武漢 430205)1(武漢工程大學計算機科學與工程學院 湖北 武漢 430205)

0 引 言

目前世界各工業國普遍把改造物流結構、降低物流成本作為企業在競爭中的重要措施[1]。為適應現代生產需要，物流正向著現代化的方向發展，智能倉儲應運而生。而路徑規劃是現代智能倉儲的關鍵技術。在機器人路徑規劃問題上，王秀紅等[2]使用復雜對角線距離來作為A*算法當前點到目標點的估計距離，顯著減少了A*算法搜索節點的數目。陳敏等[3]針對快速擴展隨機樹(RRT)算法的最近鄰函數添加了角度約束，解決了差動機器人運動學約束問題。盧月品等[4]針對狹窄環境下遺傳算法初代種群難以有效初始化的問題，提出了以Dijkstra算法為基準路徑的種群初始化方法，并引入全局通行度和路徑安全度概念，降低了算法時間復雜度，提高了獲得路徑的安全度。但上述方法都是針對單機器人靜態地圖環境的方法，而在倉儲環境下由于機器人運動環境比較狹窄，隨著環境中工作機器人數目的增多，各機器人對于其他工作中的機器人就是移動的障礙物，路網極易發生擁塞死鎖問題。針對這一問題，Liu等[5]提出了一種基于遺傳算法的離線、在線兩階段調度策略，當機器人間發生路線沖突時調用在線路徑規劃重新為小車規劃路徑，但存在反應滯后問題。劉敬一等[6]提出了基于邊的時間窗模型，依據各機器人進出各邊時間窗，保證不同任務間的時間窗發生重疊，但對各邊的時間窗約束降低了系統的魯棒性。程傳奇等[7]提出了一種融合改進A*算法和動態窗口法的全局動態路徑規劃方法，可實時避障，但A*算法的計算復雜度隨空間維數增加呈指數增加。王雷等[8]將全局路徑規劃與局部路徑規劃相結合，并且根據機器人與動態障礙物碰撞類型的不同，提出了相應的避碰策略，利用自適應遺傳算法求解機器人動態路徑規劃問題。劉二輝等[9]基于相連的路徑片段組成的三角形建立使路徑縮短的啟發式變異規則，對遺傳操作的每一代最優解進行模擬退火操作，顯著提升了算法動態環境下的路徑尋優能力，但方法計算復雜，實時性較差。

基于以上文獻，遺傳算法在求解動態路徑規劃問題時具有較強的魯棒性。本文著眼于倉儲環境下多機器人運動的擁塞死鎖以及路徑規劃算法的收斂速度問題，在文獻[4]、文獻[8]、文獻[9]對遺傳算法靜態路徑規劃研究的基礎上，提出了以路網實時狀態表建立的小車單任務耗時模型為遺傳操作評價指標，利用改進的遺傳算法來搜索當前路網最優路徑的方法。首先使用循環加障礙點的Dijkstra方法創建初始種群；然后在每一代種群中使用以單任務耗時模型為基礎的路徑評價函數進行選擇、交叉等遺傳操作，利用擁塞懲罰函數在迭代過程中不斷剔除擁塞路徑；同時增加路徑合法性檢查(路徑是否連續)使搜索都在可行解空間內。經MATLAB仿真實驗驗證，本文所用方法能有效找到當前時間最優路徑的同時避免了路網擁塞死鎖問題，并提高了算法的收斂速度，具有較強的系統魯棒性。

1 環境建模與問題描述

根據倉儲環境的實際應用場景構建倉儲機器人運動的空間模型如圖1所示。主要分為三個功能區域：小車停靠區、貨架區、分揀區[10]。貨架和空間中的一些設備作為小車路徑規劃的障礙點，貨架間的空白環境為小車的運動環境。我們將倉儲環境離散為柵格地圖，每個柵格代表空間的不同位置，使用數字標識如圖2所示，相鄰柵格的連線構成了小車運動的路徑。同時為方便計算柵格間的距離，根據標記點的數字建立平面直角坐標系，若有地圖中每行有mx個柵格，則柵格標記數字Ni與坐標點(xi,yi)的映射關系為:

圖1 倉儲環境模型圖

圖2 倉儲環境柵格圖

(1)

1.1 擁塞死鎖問題分析

在多機器人任務執行運動過程中，由于每個柵格點同一時間之內只能有一個機器人通過，那么相對狹窄的運動環境可能會產生多種路徑沖突情況如圖3，這些路徑沖突情況會嚴重影響機器人的搬運效率，針對這些路徑沖突情況需要我們為搬運小車制定交通規則去處理，與現實交通規則類似，具體避讓規則為：(1) 準備進入路口的小車讓已在路口之中的小車先行；(2) 轉彎車輛讓直行車輛先行；(3) 右轉車輛讓左轉車輛先行；(4) 同向行駛的小車后方車輛減速排隊。而機器人依據上述交通規則通過上述路徑沖突區域時，在此期間可能會集聚更多的機器人在此區域中，這樣機器人避讓過程中又產生新的沖突情況，從而導致路網中該區域長時間的阻塞甚至死鎖情況的發生。

圖3 幾種常見的路徑沖突

1.2 單任務耗時模型

結合上述的運動環境和對擁塞死鎖問題的分析，我們以點到點的小車行駛時間最短為目標，結合實際小車的運動參數(行進速度、轉動速度等)建立了小車點到點的任務耗時模型。首先路徑的長度和轉彎時間是任務耗時的重要指標，另外考慮前文對擁塞死鎖問題的分析，為避免新規劃小車進入擁塞區域，我們使用如圖4所示的路網狀態表實時記錄小車占用的柵格情況，即依據小車實時返回的位置信息，當前小車所在的柵格即是被占用狀態，無小車占用的柵格為空閑狀態。在為小車規劃路徑時，若有正在執行任務的小車出現在新規劃的路徑柵格里，則為此新路徑增加額外的阻塞懲罰值。據此單任務耗時模型的數學描述為:

圖4 某時刻路網狀態表及阻塞懲罰路徑示例

O=Tz+Tt+WTG

(2)

式中：Tz是在路網中正常行駛需要的時間，我們以小車通過一個柵格的時間為單位，正常運行的時間即為路徑長度；Tt表示小車耗費的轉彎時間；WTG表示迭代過程中的第G代個體在當前路網狀態下的阻塞懲罰函數值。各參數計算公式如下:

(3)

(4)

WTG=S×ΦG

(5)

式中：n為路徑中的柵格點數量；(xi,yi)為路徑中的第i個點的坐標；w表示小車轉動的角度，小車每次轉動的角度不會超過180°；S表示迭代過程中當前路網狀態表下路徑中包含的小車個數；Φ取常數1.001;G表示迭代過程中的當前代數。WTG隨迭代次數的增加而呈指數級增加，這樣無論是新規劃小車的路徑還是系統檢測到死鎖情況發生之后重新為小車規劃的路徑，都以避開正在執行任務的小車為目的，從而避免擁塞死鎖情況的發生。

模型約束條件如下：

(1) 路網頂點數遠大于小車數量；

(2) 每個柵格點只能容納一輛小車；

(3) 每個任務只能由一輛小車完成。

2 基于單任務耗時模型的改進遺傳算法

遺傳算法是依據遺傳學生物進化機理的計算模型，具有內在的隱并行性和更好的全局尋優能力，已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工智能等領域。它是現代有關智能計算中的關鍵技術[11]。本文提出改進的遺傳算法(improved genetic algorithm,IGA)來解決倉儲調度中的擁塞問題。使用Dijkstra算法生成遺傳操作對象，將搜索空間約束在可行的解空間之中；使用考慮擁塞控制的單任務耗時模型為基礎的適應度函數，從而得到全局最優解。算法流程如圖5所示。

圖5 遺傳算法流程

2.1 路徑個體描述

路徑個體由從起始點到目的點相連的無障礙柵格點組成，為避免出現環路，路徑中每個柵格點只能出現一次，如在12×12柵格環境中柵格1到柵格29的路徑個體[1,2,3,4,5,6,18,29]。而且由于起始點與終點的不同，路徑個體的長度也會不同，因此在路徑個體的編碼上采用變長度的字符串編碼。如對于12×12的柵格地圖，柵格點數字最大為244，因此次使用8位定長的二進制碼來表示柵格點數字,那么上例柵格1到柵格29個體的基因型為[00000001 00000010 00000011 00000100 00000101 00000110 00010010 00011101]。根據地圖環境大小變化可以方便地選擇不同長度的二進制字符串對路徑中的柵格標記數字進行編碼。

2.2 種群初始化

2.2.1生成加權地圖

使用Dijkstra算法生成到目標點的路徑，需要建立柵格各個頂點之間的加權地圖：

步驟1設總柵格數為n,初始化n×n的矩陣，根據個頂點數字轉換成的坐標填入各頂點之間的歐氏距離。

步驟3將為障礙點的頂點到其他任何頂點、其他頂點到為障礙頂點的值設為N無窮大，表示障礙點不可達。

步驟4輸出當前矩陣即為路網各頂點間的加權圖。

2.2.2生成初始化種群

與文獻[12]完全隨機的創建初始化種群不同，本文采用循環使用Dijkstra算法的方法去創建初始化種群，根據起始點縱坐標與目標點縱坐標的差值創建大小不同的種群，保證了每個個體及其后代都是潛在的最優解。而完全隨機頂點構成的路徑個體大部分是不合法/連續的，需要我們在算法中加入約束去選出合法/連續的路徑個體，這不僅增加了算法的計算復雜度，也會對算法的收斂速度產生很大影響。為保證每條個體的差異性，每生成一條路徑后將此路徑的中點放入路網障礙點集合中，完成種群初始化之后再還原初始地圖。具體流程如圖6所示。

圖6 初始化種群

2.3 適應度函數

適應度函數被用來描述種群個體的優劣，是遺傳算法選擇算子的操作依據，決定了個體的生存能力。本文中的最優解即完成任務耗時最短的路徑。因此以前文所提的單任務耗時模型為基礎的路徑個體適應度函數如下：

Fi(P)=Omax-Oi

(6)

式中:Fi(P)為種群P中第i個路徑個體的適應度；Omax為種群P的最大耗時；Oi為種群P第i個路徑個體耗時。

2.4 選擇算子

選擇過程體現遺傳算法適者生存的基本準則，通過遺傳選擇接近于最優的個體最終使算法收斂于最優解。本文采用輪盤賭法與優替劣組合選擇策略，具體為：首先計算種群中各個個體適應度占整個種群適應度的比例Vi，如式(7)所示，每次疊加一個個體的比例并記錄當前數值即為輪盤標記值，從小到大排列種群大小個隨機數，逐個取出隨機數與以第一個加入的個體的輪盤標記值對比，若小于該標記值則將該個體取出放入下一代，接下來對比下一個標記值；若大于則取第二個隨機數，與該標記值對比，直到隨機數小于輪盤標記值，取出輪盤標記值對應的個體。

(7)

2.5 交叉及變異

選擇算子一定程度上推動種群趨于高適應度，但也會損失種群的多樣性，可能導致算法最終收斂于局部最優解，發生早熟現象。因此需要進行交叉、變異操作來抑制早熟現象。交叉是父代個體之間以交叉概率Pc兩兩交換部分基因生成新的個體來增加種群多樣性。本文使用重復點交叉方法如圖7所示，具體為：從當前種群中依次取出兩個個體，判斷兩者之間重復點的個數為m；如果隨機數rand小于交叉概率Pc且重復點個數m大于0，則隨機選擇m個交叉點中的一個，交換父本、母本從交叉點之后的后半段。

圖7 個體交叉示意圖

變異操作是在選擇、交叉操作的后面進行的。對于種群中的每一個個體，每次生成一個隨機數rand，判斷與變異概率Px的大小；如果小于Px，則隨機選擇該路徑一點改變為該點相鄰的八個點中的一個，并使用Dijkdstra算法連接變異點與原來路徑，避免因變異產生中斷路徑。

2.6 終止條件

終止條件決定程序是否繼續執行。終止條件判定種群是否已經進化成熟/或得了全局最優解且不再有進化趨勢。具體為：達到最大終止代數100代；算法運行時間超過20 s；連續50代最優適應度值沒有變化。滿足上述條件之一即終止程序。

3 實驗分析

為了驗證算法的有效性，使用MATLAB做了實驗仿真，構建了四個障礙點占比分別為20%、30%、40%、50%的20×20柵格地圖作為實驗環境，將小車理想化為一個質點，每次選取10個通路上的隨機位置作為當前工作中小車所在位置，記錄到路網狀態表中，對地圖指定目標點做路徑規劃實驗。其中實驗平臺參數為：Intel core i7 8700處理器，8 GB運行內存。

3.1 實驗參數

在遺傳算法的基本運行參數選取上，種群規模是根據起始點和終點動態選取的，交叉概率一般取0.4～1.00，本文取0.8；變異概率一般取0.001～0.1，由于初始種群已經趨于高適應度，所以相對提高變異概率，本文取0.1。

3.2 實驗思路

本文的實現目標為：(1) 得到無碰撞的小車路徑；(2) 避免發生路網擁塞；(3) 加快算法收斂速度。本文的實驗思路為：(1) 準備了多個路網復雜程度不同的地圖來檢驗算法不同環境下的搜索能力；(2) 模擬常見的路徑沖突情況，檢驗算法避免路網阻塞的能力；(3) 最后與文獻[2]啟發式動態搜索算法A*、文獻[3]中改進的快速擴展隨機(IRRT)在運算時間、最優路徑長度、轉彎個數等指標上做了對比實驗來檢驗算法的性能。

3.2 實驗結果分析

實驗具體結果如下：由圖8和表1可知分別為兩種遺傳算法在30%、40%、50%、60%障礙點下的路徑規劃結果,可以看出不同復雜程度的路網環境下都實現了預期目標，表明了本文算法在不同復雜程度路網環境下的搜索能力，具有較強的系統魯棒性。且由于RRT算法所搜方向的隨機性，本文方法相較于文獻[3]中改進的RRT算法在轉彎個數有明顯減少。

(a) 環境1

表1 本文方法在四種環境下的具體實驗結果

圖9則展示了四個環境下50次實驗的適應度值隨迭代次數變化的情況，可以看出在障礙點較為稀疏的環境1、環境2下，算法基本在15～20代之間收斂于最優解，在障礙點較為密集的環境3、環境4下基本能在35～40代左右收斂于最優解，而且最終種群的平均適應度與最優適應度保持一致。

(a) 環境1

圖10為倉儲環境中兩種常見路徑沖突情況下的路線規劃效果。黑色點模擬正在工作中的AGV小車，灰色點為新規劃小車的起始點。可見不考慮路網擁塞的文獻[2]中改進A*算法、文獻[3]中改進RRT算法仍會將小車引向擁塞區域，而本文算法則會盡量繞過擁塞區域，避免使擁塞區域情況惡化，但在此情況下增加了路徑長度。

(a) 相向沖突下的阻塞避免

最后與文獻[2]啟發式動態搜索算法A*、文獻[3]中改進的快速擴展隨機(IRRT)在各個環境下就路徑長度、轉彎個數、運算時間等指標進行了對比實驗。表2-表5分別為四種環境下最遠距離的兩點進行50次重復路徑規劃實驗的詳細數據。由數據可知本文所提算法由于躲避任務中工作的小車，在最終長度上相較于改進A*算法有所損失，而且損失程度隨著環境復雜程度增加而更加明顯，但由于在遺傳操作過程中增加了路徑合法性檢查和轉彎控制，算法在運算速度和路徑轉彎控制上優勢明顯。

表2 環境1下實驗結果

表3 環境2下實驗結果

表4 環境3下實驗結果

表5 環境4下實驗結果

4 結 語

本文針對單層倉儲環境提出了一種基于小車單任務耗時模型的改進遺傳算法，所提方法實現了在不同復雜程度的路網環境下路徑規劃能力，有效地避開擁塞路段，收斂速度大大提高。在路徑轉彎控制以及運算速度上，所提方法優勢明顯。后續將針對更為復雜的多層電梯倉儲環境，探索適用于該環境下的自動引導車最優調度算法。