楊世團(tuán) 于寶成，2* 吳云韜,2

1(智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430205)1(武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 湖北 武漢 430205)

0 引 言

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

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

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

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

圖1 倉(cāng)儲(chǔ)環(huán)境模型圖

圖2 倉(cāng)儲(chǔ)環(huán)境柵格圖

(1)

1.1 擁塞死鎖問(wèn)題分析

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

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

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

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

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

O=Tz+Tt+WTG

(2)

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

(3)

(4)

WTG=S×ΦG

(5)

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

模型約束條件如下：

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

(2) 每個(gè)柵格點(diǎn)只能容納一輛小車(chē)；

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

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

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

圖5 遺傳算法流程

2.1 路徑個(gè)體描述

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

2.2 種群初始化

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

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

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

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

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

2.2.2生成初始化種群

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

圖6 初始化種群

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

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

Fi(P)=Omax-Oi

(6)

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

2.4 選擇算子

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

(7)

2.5 交叉及變異

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

圖7 個(gè)體交叉示意圖

變異操作是在選擇、交叉操作的后面進(jìn)行的。對(duì)于種群中的每一個(gè)個(gè)體，每次生成一個(gè)隨機(jī)數(shù)rand，判斷與變異概率Px的大?。蝗绻∮赑x，則隨機(jī)選擇該路徑一點(diǎn)改變?yōu)樵擖c(diǎn)相鄰的八個(gè)點(diǎn)中的一個(gè)，并使用Dijkdstra算法連接變異點(diǎn)與原來(lái)路徑，避免因變異產(chǎn)生中斷路徑。

2.6 終止條件

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

3 實(shí)驗(yàn)分析

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

3.1 實(shí)驗(yàn)參數(shù)

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

3.2 實(shí)驗(yàn)思路

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

(a) 環(huán)境1

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

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

(a) 環(huán)境1

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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