基于改進(jìn)的A*算法集裝箱碼頭自動(dòng)導(dǎo)引小車路徑規(guī)劃研究*

曹 瑩 陳沿伊 馮 睿

(武漢理工大學(xué)交通學(xué)院1) 武漢 430063) (武漢理工大學(xué)物流工程學(xué)院2) 武漢 430063)

0 引 言

提高港口通過能力有兩種方法:①外延擴(kuò)大，增加碼頭泊位數(shù)量，擴(kuò)大堆場(chǎng)面積等，此方法不確定因素多，投入成本巨大，花費(fèi)時(shí)間較長，短期內(nèi)一般不予采用；②增加港口內(nèi)涵，采取先進(jìn)機(jī)械設(shè)備，加快港口的集疏運(yùn)能力，智能化管理技術(shù)優(yōu)化分工，加強(qiáng)協(xié)作關(guān)系，把船、車作業(yè)納入規(guī)范，實(shí)行系統(tǒng)化管理.我國集裝箱碼頭土地資源很難再擴(kuò)大，一般多為優(yōu)化集裝箱碼頭裝卸工藝流程來提高港口通過能力.根據(jù)港口企業(yè)統(tǒng)計(jì)，集裝箱碼頭水平運(yùn)輸已成為集裝箱裝卸工藝中的瓶頸，且集裝箱運(yùn)輸費(fèi)用已成為集裝箱碼頭運(yùn)營成本中最大的支出.

當(dāng)前集裝箱碼頭最先進(jìn)的水平運(yùn)輸機(jī)械設(shè)備是自動(dòng)導(dǎo)引小車(AGV)，其運(yùn)輸管理系統(tǒng)的核心部分是AGV路徑規(guī)劃，優(yōu)化AGV路徑規(guī)劃可極大提高港口工作效率和港口吞吐量.自動(dòng)化機(jī)器領(lǐng)域不同于人類領(lǐng)域，需要對(duì)所有AGV可能出現(xiàn)的行為進(jìn)行事先編程.因此，環(huán)境的復(fù)雜性使得集裝箱碼頭總會(huì)出現(xiàn)不可預(yù)測(cè)的情況，利用引入碰撞因子的A*算法研究碼頭AGV路徑規(guī)劃問題，在時(shí)間和空間上均提高了AGV搜索路徑的科學(xué)性，降低了系統(tǒng)的不可預(yù)測(cè)性，貨損率及物流成本降低，實(shí)現(xiàn)了對(duì)港口的智能化管理.

AGV路徑規(guī)劃主要是運(yùn)用數(shù)學(xué)歸納法建立整數(shù)規(guī)劃模型、動(dòng)態(tài)規(guī)劃模型、petri網(wǎng)模型等隨著生產(chǎn)力的發(fā)展，新型高效的調(diào)度原則在不斷地提出，比如Enrico等[1]采用割平面法對(duì)AGV進(jìn)行調(diào)度，將碼頭分成多個(gè)獨(dú)立的小區(qū)域，不同區(qū)域內(nèi)根據(jù)任務(wù)數(shù)量分配對(duì)應(yīng)數(shù)量AGV獨(dú)立實(shí)行調(diào)度；Hamed等[2]在動(dòng)態(tài)作業(yè)中構(gòu)建了一種最大流量的啟發(fā)式算法，建立動(dòng)態(tài)規(guī)劃模型，實(shí)時(shí)確定AGV的需求量，但在實(shí)際應(yīng)用中，港口生產(chǎn)工序復(fù)雜，網(wǎng)絡(luò)數(shù)據(jù)處理時(shí)間長；A*是一種新型的啟發(fā)性算法，能夠快速高效的求得近似最優(yōu)解，楊璐等[3]通過傳感器技術(shù)和A*算法，當(dāng)AGV遇到障礙物時(shí)可立即重新規(guī)劃路徑，提高了A*算法可采納性；針對(duì)AGV規(guī)劃路徑時(shí)避免發(fā)生碰撞的研究，Chin等[4-5]采用FIFO原則和低速區(qū)設(shè)置的原則，減少AGV發(fā)生的碰撞.針對(duì)多輛AGV同時(shí)運(yùn)行時(shí)發(fā)生的沖突碰撞問題，Mohammad等[6]以AGV完成任務(wù)時(shí)間最短為目標(biāo),建立蟻群算法模型，減少了AGV發(fā)車頻率，達(dá)到減少相互碰撞的可能性.針對(duì)單回訪路線，張煜等[7]提出了AGV運(yùn)行途中交叉口區(qū)域設(shè)置模糊控制緩沖帶，以此來避免擁堵碰撞.目前國內(nèi)外均沒有將A*算法與避免碰撞結(jié)合的方法，本文將基于A*算法路徑規(guī)劃時(shí)引入碰撞因子，規(guī)劃出避免碰撞的最佳路徑.

1 傳統(tǒng)A*算法基本原理

A*算法屬于人工智能范疇中具有明顯啟發(fā)式特征的搜索算法，因?yàn)槠渌俣瓤?、靈活度高并且對(duì)各種路狀適應(yīng)性強(qiáng)，是路徑規(guī)劃常用的工具.A*算法通過將初始起點(diǎn)與中間節(jié)點(diǎn)的實(shí)際距離函數(shù)以及中間節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的啟發(fā)式函數(shù)兩方面結(jié)合分析當(dāng)前節(jié)點(diǎn).

A*算法的評(píng)價(jià)函數(shù)為

f(k)=g(k)+h(k)

(1)

式中：f(k)為初始點(diǎn)、節(jié)點(diǎn)k,以及目標(biāo)節(jié)點(diǎn)三者間所有距離的評(píng)價(jià)函數(shù)；g(k)為初始節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)k之間的實(shí)際距離函數(shù)；h(k)為節(jié)點(diǎn)k到達(dá)目標(biāo)節(jié)點(diǎn)最優(yōu)路徑的估計(jì)距離函數(shù)，也可稱為啟發(fā)函數(shù).

啟發(fā)函數(shù)在A*算法中起著關(guān)鍵性作用，決定算法準(zhǔn)確性的高低.若h(k)=0，即f(k)=g(k)，則 A*算法就轉(zhuǎn)換成Dijkstra算法；若g(k)=0,即f(k)=h(k),則A*算法轉(zhuǎn)化為貪婪算法.若h(k)低于g(k)，則A*算法經(jīng)過擴(kuò)展得到的結(jié)點(diǎn)數(shù)量就會(huì)增加，此時(shí)的算法的運(yùn)行速率就會(huì)降低；若h(k)相于g(k)，此時(shí)算法可以最快的搜索到最佳路徑同時(shí)還不會(huì)進(jìn)行額外拓展；若h(k)高于g(k)，此時(shí)可能無法尋找到最優(yōu)路徑，但是算法的運(yùn)行速率提升了.

計(jì)算在二維平面中的兩節(jié)點(diǎn)(X1,Y1),(X2,Y2)之間的距離函數(shù)主要有切比雪夫距離、曼哈頓距離和歐氏距離最短距離.結(jié)合港口實(shí)際情況，AGV小車運(yùn)行途中一定會(huì)遇到不可避免的障礙物，所以不采用切比雪夫距離.在傳統(tǒng)8領(lǐng)域A*算法中，豎直方向和水平方向歐式距離和曼哈頓距離計(jì)算結(jié)果是相同的，而在對(duì)角線方向上歐式距離計(jì)算結(jié)果與實(shí)際情況的偏差較曼哈頓計(jì)算結(jié)果誤差較小，所以歐式距離更能滿足實(shí)驗(yàn)的要求，為

(2)

傳統(tǒng)A*算法實(shí)現(xiàn)的具體步驟見圖1.

圖1 A*算法流程圖

2 改進(jìn)的A*算法原理

2.1 柵格地圖設(shè)置

在AGV路徑規(guī)劃系統(tǒng)中，獲取環(huán)境地圖是路徑規(guī)劃的前提，由于柵格地圖環(huán)境表達(dá)直觀，地圖構(gòu)建簡(jiǎn)單方便，在AGV路徑規(guī)劃系統(tǒng)中，對(duì)環(huán)境地圖的描述形式通常使用柵格地圖.柵格地圖又稱單元分解地圖，是把實(shí)際復(fù)雜的工作環(huán)境轉(zhuǎn)變成為一個(gè)二維平面數(shù)組，其具體操作如下：首先將環(huán)境的分割為一個(gè)個(gè)柵格，根據(jù)環(huán)境實(shí)際情況對(duì)存在障礙物的柵格定義為障礙柵格，否則定義為通行柵格，再對(duì)可能使用到的柵格做概率標(biāo)記.

在柵格地圖中，信息傳遞的精度取決于柵格的精度，柵格過大信息傳遞不準(zhǔn)確，柵格過小會(huì)大大增加計(jì)算的復(fù)雜程度.在構(gòu)建柵格地圖時(shí)，若實(shí)際地圖的長為a，寬為b，則柵格的面積S為a×b.再根據(jù)港口實(shí)際使用的AGV車身大小(設(shè)AGV長L,寬為D)，將大柵格分割成一個(gè)個(gè)小格，則柵格的行數(shù)為X=a/L，列數(shù)為Y=b/L，計(jì)算結(jié)果均向上取整，且一個(gè)小格視為AGV運(yùn)行的最小單元.

2.2 引入碰撞威脅改進(jìn)原理

A*算法規(guī)劃出的路徑不僅要符合AGV運(yùn)行安全規(guī)范，避免與障礙物發(fā)生碰撞，還要保證路徑轉(zhuǎn)折點(diǎn)較少.若規(guī)劃路徑轉(zhuǎn)折較多意味著AGV算法在實(shí)際運(yùn)行途中需要多次改變運(yùn)行方向，AGV在轉(zhuǎn)向時(shí)速度降低，這不僅會(huì)降低作業(yè)效率，而且還會(huì)增加AGV的安全風(fēng)險(xiǎn).因此提出啟發(fā)函數(shù)引入碰撞威脅因子，以此來解決折點(diǎn)較多、碰撞威脅較大的問題，進(jìn)一步提高A*算法規(guī)劃路徑的可采用性.

A*算法評(píng)價(jià)函數(shù)f(k)中的啟發(fā)式函數(shù)h(k)是指從AGV當(dāng)前位置k到目標(biāo)節(jié)點(diǎn)B的估計(jì)行駛的總距離，但在實(shí)際AGV的路徑中應(yīng)包括估計(jì)距離hs(k)和碰撞威脅ht(k)兩部分，并根據(jù)港口實(shí)際情況加入權(quán)數(shù)w調(diào)節(jié)兩者的平衡，其表達(dá)式為

h(k)=wshs(k)+wtht(k)

(3)

式中：k為AGV當(dāng)前位置；s為估計(jì)距離；t為碰撞威脅；hs(k)為路徑節(jié)點(diǎn)位置間距離的累加，即AGV當(dāng)前節(jié)點(diǎn)位置k到上一節(jié)點(diǎn)位置k-1的距離；例如：hs(1)為起點(diǎn)到節(jié)點(diǎn)1的距離，hs(2)為hs(1)加上節(jié)點(diǎn)1與節(jié)點(diǎn)2之間的估計(jì)距離，即hs(2)=hs(1)+s2；ht(k)為當(dāng)前節(jié)點(diǎn)位置的碰撞威脅的累加，即上一節(jié)點(diǎn)所有碰撞威脅ht(k-1)與當(dāng)前節(jié)點(diǎn)時(shí)可能與障礙物發(fā)生的碰撞成本；例如：ht(1)為起點(diǎn)到節(jié)點(diǎn)1的碰撞威脅，ht(2)為ht(1)加上節(jié)點(diǎn)2與當(dāng)前可能與障礙物發(fā)生的碰撞成本，即ht(2)=ht(1)+t2；ws為已行駛距離在啟發(fā)式函數(shù)h(k)的占比；wt為碰撞威脅在啟發(fā)式函數(shù)h(k)的占比.

AGV與障礙物發(fā)生的碰撞威脅可通過AGV安全報(bào)警系統(tǒng)中的外側(cè)輪廓點(diǎn)與障礙物間的距離進(jìn)行量化.定義Tk為AGV與障礙物發(fā)生碰撞的威脅，AGV安全警報(bào)系統(tǒng)中的外側(cè)輪廓特征點(diǎn)到障礙物距離為d，AGV設(shè)定的安全距離為dsafe.當(dāng)AGV到障礙物的距離均大于安全距離時(shí)(d≥dsafe)，可認(rèn)為當(dāng)前節(jié)點(diǎn)與障礙物發(fā)生碰撞的概率為0；當(dāng)AGV到障礙物的距離的最小值小于安全距離時(shí)(d

(4)

從起始點(diǎn)到AGV當(dāng)前位置k的所有碰撞威脅Tk(i=0,1,2,…,k)，則碰撞威脅為

(5)

綜上所述，改進(jìn)的A*算法評(píng)價(jià)函數(shù)為

f(k)=g(k)+wshs(k)+wtht(k)

(6)

改進(jìn)后的A*算法的啟發(fā)式函數(shù)h(k)包括估計(jì)距離hs(k)和碰撞威脅ht(k)兩部分,流程圖見圖2.

圖2 加入碰撞威脅后的流程圖

3 案例分析

3.1 洋山深水港介紹

洋山深水港區(qū)坐落于浙江省嵊泗崎嶇列島，是我國首個(gè)海島式人工碼頭，同時(shí)也是目前世界上最大的集裝箱港口.其岸線長約為2.8 km，平均陸域縱深約500 m，總用地面積223.16萬m2，碼頭前沿自然水深大部分在11～15 m，港區(qū)全年可作業(yè)天數(shù)在315 d以上.建有五個(gè)5萬t級(jí)泊位，兩個(gè)7萬t級(jí)泊位，碼頭強(qiáng)度結(jié)構(gòu)均按15萬t級(jí)集裝箱船舶設(shè)計(jì)建造.港口作業(yè)采用采用了垂岸式的作業(yè)線、高密度堆垛方式，極大地提高了土地資源與海岸線資源的利用程度.碼頭內(nèi)部交通流自東向西，集裝箱卡車進(jìn)港后單向行駛，根據(jù)貨物的特性在堆場(chǎng)外側(cè)設(shè)立不同的裝卸區(qū)域，高效的完成集裝箱的轉(zhuǎn)運(yùn)工作.

目前配備“雙小車集裝箱裝卸橋+AGV+自動(dòng)軌道式龍門起重機(jī)(ARMG)”的裝卸工藝方案，主要裝卸環(huán)節(jié)均實(shí)現(xiàn)了全電力驅(qū)動(dòng)，提高了能源利用效率，降低了能耗，減小了廢氣和噪聲對(duì)環(huán)境的影響.配有10臺(tái)雙小車集裝箱岸橋、38臺(tái)自動(dòng)軌道式龍門吊，以及50輛自動(dòng)引導(dǎo)小車.AGV為長為15.878 m、寬為2.85 m，設(shè)最大行馳速度30 km/h，連續(xù)里程110 km，續(xù)行時(shí)間8 h，額定載重量為61 t，滿載重量為74.5 t其中，每臺(tái)AGV平均1 h可完成40 TEU的水平運(yùn)輸作業(yè).

3.2 實(shí)驗(yàn)過程及結(jié)果

在MatLab2016b的實(shí)驗(yàn)環(huán)境條件下，根據(jù)洋山深水港四期實(shí)際布局，選擇50 000 t泊位，配備兩臺(tái)岸橋，集裝箱分配于堆場(chǎng)一個(gè)危險(xiǎn)品堆場(chǎng)和四個(gè)普通集裝箱堆場(chǎng)，港內(nèi)水平運(yùn)輸均由AGV完成，最終由港外集裝箱卡車運(yùn)出.將一個(gè)小格視為AGV運(yùn)行的最小單元，則柵格地圖尺寸選擇45×30；柵格地圖采用直角坐標(biāo)標(biāo)記，設(shè)左下角為坐標(biāo)原點(diǎn)(0,0)，水平向右為X軸正半軸，豎直向上為Y軸正半軸，每一個(gè)柵格都可由唯一直角坐標(biāo)(X,Y)表示.柵格地圖中的障礙柵格和通行柵格根據(jù)洋山深水港四期碼頭特征選擇，其中障礙物包括堆場(chǎng)箱位區(qū)、裝卸區(qū)等固定功能區(qū)域、港區(qū)有關(guān)的安全標(biāo)示和港區(qū)內(nèi)其他機(jī)械設(shè)施，實(shí)驗(yàn)中選取小圓圈標(biāo)注障礙柵格，見圖3～4.

圖3 洋山深水港仿真實(shí)驗(yàn)柵格地圖

圖4 路徑規(guī)劃仿真實(shí)驗(yàn)對(duì)比圖

在改進(jìn)的A*算法中預(yù)先設(shè)定估計(jì)距離成本和碰撞威脅成本兩部分的權(quán)數(shù)分別為0.7和0.3[8].根據(jù)洋山深水港相關(guān)規(guī)定，AGV與障礙物的安全距離為2.5 m，即可設(shè)定為為0.2個(gè)柵格.

表1為傳統(tǒng)A*算法與改進(jìn)后的A*算法主要參數(shù)對(duì)比，goal-distance為不考慮障礙物存在，從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的直線距離.同組實(shí)驗(yàn)只中改變了障礙物的數(shù)量與位置，其余參數(shù)保證不變，所以goal-distance是相等的.path-cost為A*算法規(guī)劃出路徑的實(shí)際距離.由于改進(jìn)A*算法的估計(jì)距離成本函數(shù)更復(fù)雜，擴(kuò)展節(jié)點(diǎn)更多，規(guī)劃路徑所用的時(shí)間有所增加，但在實(shí)際運(yùn)行中規(guī)劃路徑變短、AGV改變方向次數(shù)減少會(huì)使得AGV完成任務(wù)的總體時(shí)間減少.

表1 傳統(tǒng)A*算法與改進(jìn)后的A*算法主要參數(shù)對(duì)比

通過改變洋山港AGV起始點(diǎn)位置及不同環(huán)境中，設(shè)計(jì)多組實(shí)驗(yàn)，仿真結(jié)果見圖5～8，表2對(duì)比了傳統(tǒng)A*算法與引入碰撞威脅因子的A*算法主要參數(shù).

圖5 第一組路徑規(guī)劃仿真實(shí)驗(yàn)

圖6 第二組路徑規(guī)劃仿真實(shí)驗(yàn)

圖7 第三組路徑規(guī)劃仿真實(shí)驗(yàn)

圖8 第四組路徑規(guī)劃仿真實(shí)驗(yàn)

表2 傳統(tǒng)A*算法與引入碰撞因子的A*算法主要參數(shù)對(duì)比

引入碰撞因子的A*算法引入碰撞威脅因子后，擴(kuò)展節(jié)點(diǎn)增加，其搜索的結(jié)果更加精準(zhǔn)，其規(guī)劃的路徑轉(zhuǎn)折點(diǎn)較少，路徑更加平滑，AGV拐彎次數(shù)更少，有效的保證了貨物和車輛的安全，由表2可知，改進(jìn)后的A*算法規(guī)劃距離縮短1 m，規(guī)劃時(shí)間增加約為0.04 s，整體效率提高顯著，有利于AGV的自動(dòng)運(yùn)行.

4 結(jié) 束 語

針對(duì)A*算法規(guī)劃出的路徑發(fā)生碰撞的可能性較大，往往規(guī)劃出的路徑在港口實(shí)際運(yùn)行中不是最優(yōu)解，提出了引入碰撞威脅因子的A*算法，最后通過在matlab 2016b環(huán)境下的仿真實(shí)驗(yàn)，驗(yàn)證了改進(jìn)A*算法思路上的可行性和合理性.通過上海洋山深水港實(shí)際案例，設(shè)計(jì)仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)的A*算法的具有一定實(shí)用性.

需要指出本文在柵格地圖設(shè)置中存在的不足，將一個(gè)小格視為AGV運(yùn)行的最小單元，地圖的精度還有待進(jìn)一步提高；且本文僅設(shè)置了通行柵格和障礙柵格，對(duì)于一些可移動(dòng)障礙物實(shí)AGV也許只需稍加等待便可按初始最佳路徑行駛，無需二次規(guī)劃路徑，若能在柵格地圖中加入一些特殊障礙柵格，并引用時(shí)間窗的思想，對(duì)AGV運(yùn)行路徑進(jìn)行實(shí)時(shí)動(dòng)態(tài)規(guī)劃，可進(jìn)一步提搞AGV的容錯(cuò)性.