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

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

0 引 言

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

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

1 環(huán)境建模與問題描述

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

圖1 倉儲環(huán)境模型圖

圖2 倉儲環(huán)境柵格圖

(1)

1.1 擁塞死鎖問題分析

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

圖3 幾種常見的路徑?jīng)_突

1.2 單任務(wù)耗時模型

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

圖4 某時刻路網(wǎng)狀態(tài)表及阻塞懲罰路徑示例

O=Tz+Tt+WTG

(2)

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

(3)

(4)

WTG=S×ΦG

(5)

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

模型約束條件如下：

(1) 路網(wǎng)頂點數(shù)遠大于小車數(shù)量；

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

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

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

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

圖5 遺傳算法流程

2.1 路徑個體描述

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

2.2 種群初始化

2.2.1生成加權(quán)地圖

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

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

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

步驟4輸出當(dāng)前矩陣即為路網(wǎng)各頂點間的加權(quán)圖。

2.2.2生成初始化種群

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

圖6 初始化種群

2.3 適應(yīng)度函數(shù)

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

Fi(P)=Omax-Oi

(6)

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

2.4 選擇算子

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

(7)

2.5 交叉及變異

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

圖7 個體交叉示意圖

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

2.6 終止條件

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

3 實驗分析

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

3.1 實驗參數(shù)

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

3.2 實驗思路

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

3.2 實驗結(jié)果分析

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

(a) 環(huán)境1

表1 本文方法在四種環(huán)境下的具體實驗結(jié)果

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

(a) 環(huán)境1

圖10為倉儲環(huán)境中兩種常見路徑?jīng)_突情況下的路線規(guī)劃效果。黑色點模擬正在工作中的AGV小車，灰色點為新規(guī)劃小車的起始點?？梢姴豢紤]路網(wǎng)擁塞的文獻[2]中改進A*算法、文獻[3]中改進RRT算法仍會將小車引向擁塞區(qū)域，而本文算法則會盡量繞過擁塞區(qū)域，避免使擁塞區(qū)域情況惡化，但在此情況下增加了路徑長度。

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

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

表2 環(huán)境1下實驗結(jié)果

表3 環(huán)境2下實驗結(jié)果

表4 環(huán)境3下實驗結(jié)果

表5 環(huán)境4下實驗結(jié)果

4 結(jié) 語

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