基于改進(jìn)A*算法的四向穿梭車路徑規(guī)劃

余嘉雄，白紅星

(1.浙江凱樂士科技有限公司，浙江 嘉興 314000；2.武漢大學(xué)，湖北 武漢 430072)

0 引言

跨巷道多層四向穿梭車倉(cāng)儲(chǔ)系統(tǒng)(以下簡(jiǎn)稱多穿庫(kù))是一種密集存儲(chǔ)系統(tǒng)，與普通立體倉(cāng)庫(kù)相比，可以多層多區(qū)域并行作業(yè)，通過提升機(jī)連接各層，提高單位時(shí)間出庫(kù)總量，縮短分揀時(shí)間，被廣泛應(yīng)用于“貨到人”訂單揀選模式。

在密集倉(cāng)儲(chǔ)系統(tǒng)中，常用的搬運(yùn)設(shè)備為智能件箱式四向穿梭車(以下簡(jiǎn)稱穿梭車)，它是一種智能的搬運(yùn)設(shè)備，結(jié)合編碼器、光電傳感器和攝像頭等技術(shù)實(shí)現(xiàn)實(shí)時(shí)位置的精確定位及貨物與車體姿態(tài)檢測(cè)；而倉(cāng)儲(chǔ)系統(tǒng)中的智能化穿梭庫(kù)調(diào)度系統(tǒng)，則負(fù)責(zé)根據(jù)任務(wù)類型進(jìn)行組合，調(diào)度穿梭車進(jìn)行循環(huán)式作業(yè)，確保整體作業(yè)效率。由于穿梭車無(wú)需人員操作，運(yùn)行速度快且智能化程度高，適用于各種物流存儲(chǔ)系統(tǒng)，能夠促進(jìn)單元物料快速實(shí)現(xiàn)自動(dòng)輸送，但這在很大程度上取決于系統(tǒng)執(zhí)行復(fù)合作業(yè)的路徑是否合理。

對(duì)于穿梭車路徑規(guī)劃問題，當(dāng)前應(yīng)用較為廣泛的方法為改進(jìn)自動(dòng)導(dǎo)引運(yùn)輸車AGV路徑規(guī)劃方法。然而，穿梭車是基于軌道行進(jìn)的高速運(yùn)行物流搬運(yùn)設(shè)備，其軌道與AGV路網(wǎng)布局差異大，穿梭車無(wú)法具備AGV近距離跟隨、短距離剎車和就近可變換通道的能力，因而其路徑規(guī)劃與AGV有類似的地方，同時(shí)也存在較大的差異。

劉國(guó)棟[1]提出了多 AGV 調(diào)度系統(tǒng)中的兩階段動(dòng)態(tài)路徑規(guī)劃方法，被國(guó)內(nèi)AGV廠商在實(shí)際應(yīng)用中廣泛采用，但是這種方法在路徑規(guī)劃時(shí)沒有考慮正在執(zhí)行任務(wù)車輛路徑之間的相互影響，使得對(duì)地圖以單向路徑為主，降低了系統(tǒng)靈活性，而且也增加了系統(tǒng)實(shí)時(shí)路徑?jīng)_突處理的難度與復(fù)雜程度。張喜妹[2]對(duì)多臺(tái)類Kiva機(jī)器人的碰撞問題給出了處理機(jī)制。Sharon等[3]使用CBS方法(conflict-based search)對(duì)多車路徑進(jìn)行規(guī)劃，適用于小規(guī)模的路徑?jīng)_突情形，時(shí)間粒度小對(duì)軟硬件要求高，實(shí)際應(yīng)用中困難較大。李偉光等[4]提出基于改進(jìn)A*算法的AGV路徑規(guī)劃，通過增加轉(zhuǎn)彎因子，降低AGV的轉(zhuǎn)彎次數(shù)，提升路徑優(yōu)化效果。萬(wàn)千[5]在基于CBS算法的物流分揀多AGV路勁規(guī)劃的研究中，對(duì)基于沖突的多車路徑規(guī)劃的方法進(jìn)行了優(yōu)化。楊瑋[6]、周奇才[7]、聶峰[8]等提出了對(duì)雙載式多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑優(yōu)化研究，實(shí)現(xiàn)了多路徑的優(yōu)化方法，分別從多種應(yīng)用場(chǎng)景角度設(shè)計(jì)優(yōu)化算法。冉文學(xué)等[9]實(shí)現(xiàn)了動(dòng)態(tài)立體倉(cāng)庫(kù)中穿梭車貨到人多目標(biāo)揀選路徑的優(yōu)化，將禁忌搜索算法應(yīng)用到穿梭車揀選路徑優(yōu)化中。

本文從穿梭車庫(kù)控制軟件系統(tǒng)中路徑搜索實(shí)際應(yīng)用出發(fā)，提出了一種改進(jìn)A*算法的路徑規(guī)劃算法，在搜索過程盡量減少各車在各路徑節(jié)點(diǎn)行駛范圍內(nèi)與其他車輛的路徑的點(diǎn)交叉與邊沖突，既保證系統(tǒng)路徑搜索時(shí)效要求，同時(shí)降低實(shí)時(shí)路徑?jīng)_突處理規(guī)則的復(fù)雜程度，在穿梭車不同時(shí)間搜索路徑時(shí)，動(dòng)態(tài)考慮路徑占用情況，從而保證整個(gè)系統(tǒng)的穩(wěn)定高效運(yùn)行。

1 問題描述

跨巷道多層穿梭車庫(kù)，分別由穿梭車、入庫(kù)提升機(jī)、出庫(kù)提升機(jī)、層入庫(kù)暫存位、層出庫(kù)暫存位、縱向/橫向移動(dòng)通道、出/入庫(kù)提升機(jī)、換層提升機(jī)及存儲(chǔ)貨位構(gòu)成,具體如圖1所示。

圖1 多穿庫(kù)平面布局

穿梭車行駛最大速度為4 m/s，加速度為2 m/s2。由于其速度快，減速停止距離大，因此，采用分段定位的方式進(jìn)行定位，將路徑分段執(zhí)行并進(jìn)行路徑資源的占用與釋放，而在停止位進(jìn)行路徑狀態(tài)更新與位置校對(duì)。

多穿庫(kù)路徑規(guī)劃需要解決的難題之一，是在任務(wù)聚集時(shí)，多輛穿梭車路徑干涉問題。因此，期望能考慮正在執(zhí)行任務(wù)的車的路徑基礎(chǔ)上，找出其干涉少、轉(zhuǎn)彎少的路徑，而不是單純的最短路徑(路徑干涉會(huì)有等待)。

而在路徑干涉檢測(cè)中，如果只考慮2點(diǎn)之間最短路徑，不考慮各穿梭車當(dāng)前位置，則路徑干涉過多，使得結(jié)果不理想。因此，需要對(duì)各車位置進(jìn)行區(qū)分以及其占用路徑情況，進(jìn)行動(dòng)態(tài)路徑規(guī)劃，所得結(jié)果更加合理。

對(duì)于穿梭車之間的路徑干涉，分為如下3種情況：

a.路徑成環(huán)，多個(gè)車輛運(yùn)行形成多條路徑，從而得到有向環(huán)，路徑成環(huán)后造成路徑封閉，從而不能進(jìn)行后續(xù)工作。

b.點(diǎn)沖突，從不同方向在相同點(diǎn)發(fā)生碰撞。

c.邊沖突，在相反位置路過2個(gè)點(diǎn)連邊。

2 最大可靠路

在有向圖網(wǎng)絡(luò)中，往往需要利用已知的各邊的可靠性概率，求出指定起始點(diǎn)S到目標(biāo)點(diǎn)T的1條可靠性概率達(dá)到最大的路，此路稱為由S到T的最大可靠路[10]。

在網(wǎng)絡(luò)G中，各頂點(diǎn)間有向路完好概率為0≤pi,j≤1，定義為

(1)

為了利用最短路求解方法，2點(diǎn)之間距離矩陣為A=(ai,j)n×n，將pi,j做如下變換，即

(2)

ai,j中初始值為a0(除為0的值與∞外)，并根據(jù)點(diǎn)邊占用情況進(jìn)行處理。

多輛穿梭車路徑干涉時(shí)，需對(duì)有向路的完好概率進(jìn)行調(diào)整，實(shí)際應(yīng)用時(shí)，保證車輛數(shù)增加初始階段權(quán)值變化大，后續(xù)逐漸平緩，避免后續(xù)任務(wù)找不到路。

在最大可靠路基礎(chǔ)上，做了一些調(diào)整，即將點(diǎn)所經(jīng)過的邊數(shù)進(jìn)行匯總。

將對(duì)各路徑中所有經(jīng)過的邊i→j即從i點(diǎn)出發(fā)到j(luò)點(diǎn)的邊，進(jìn)行總數(shù)量統(tǒng)計(jì)，對(duì)每條路徑分別計(jì)算組成的邊并進(jìn)行匯總：Bi,j=Bi,j+1，而反向邊為Bj,i=Bj,i+tmpR。

將沖突次數(shù)進(jìn)行如下變換，即

(3)

對(duì)于距離矩陣A=(ai,j)n×n，ai,i=0。根據(jù)地圖規(guī)模，設(shè)定N值，滿足路徑點(diǎn)對(duì)于多輛穿梭車占用敏感程度的要求。

3 改進(jìn)A*算法

A*算法是目前應(yīng)用最多的一種路徑查找和圖形遍歷算法?？蓽?zhǔn)確進(jìn)行查找和篩選，算法性能優(yōu)越。各節(jié)點(diǎn)級(jí)別由A*算法表示為

f(n)=g(n)+h(n)

(4)

f(n)為節(jié)點(diǎn)Vn的綜合優(yōu)先級(jí)；g(n)為節(jié)點(diǎn)Vn距離起點(diǎn)的代價(jià)；h(n)為節(jié)點(diǎn)Vn距離終點(diǎn)的預(yù)計(jì)代價(jià)。

穿梭車主要向4個(gè)方位運(yùn)行，通過曼哈頓距離表示為

(5)

在柵格地圖中，使用RCA(對(duì)于當(dāng)前點(diǎn)的狀態(tài)描述，R為地圖行標(biāo)，C為地圖列標(biāo)，A為方向)方式記錄位置與狀態(tài)，點(diǎn)的狀態(tài)增加了方向A維度。方向記錄方式如圖2所示，如S(3,2,2)→T(2,2,2)為由S點(diǎn)(第3行第2列，方向向上)出發(fā)移動(dòng)到T點(diǎn)(第2行第2列，方向向上)。

圖2 穿梭車行駛方向示例

3.1 路徑搜索基本思路

a.使用RCA方式進(jìn)行記錄位置與狀態(tài)，點(diǎn)的狀態(tài)增加了方向維度，使用A*的迭代結(jié)構(gòu)進(jìn)行計(jì)算。

b.在增加新點(diǎn)時(shí)，只考慮2點(diǎn)之間的鄰接屬性，不考慮方向，方向由起點(diǎn)到終點(diǎn)來(lái)確定，2點(diǎn)之間距離通過距離矩陣計(jì)算，轉(zhuǎn)彎通過起點(diǎn)與目標(biāo)點(diǎn)方向差異進(jìn)行計(jì)算得出，避免了考慮方向維度產(chǎn)生的大量解的情況，減少轉(zhuǎn)彎數(shù)量以及由于轉(zhuǎn)彎計(jì)算產(chǎn)生的額外的距離值。

c.在新添加點(diǎn)時(shí)，添加其他車輛路徑點(diǎn)約束沖突檢測(cè)(邊重合與邊沖突數(shù)量)，計(jì)算重合邊數(shù)及沖突邊數(shù)，并根據(jù)函數(shù)計(jì)算添加的額外距離值。

d.終點(diǎn)方向通過最終方向與終點(diǎn)需要方向進(jìn)行1次調(diào)整，使得最終方向與終點(diǎn)方向一致。

3.2 兩點(diǎn)間距離以及沖突、轉(zhuǎn)彎的額外增加距離值計(jì)算

數(shù)據(jù)說明，fromNode為每次迭代搜索時(shí)的一小段路徑的出發(fā)點(diǎn)，toNode為每次迭代搜索時(shí)的一小段路徑的目標(biāo)點(diǎn)，startNode為整個(gè)任務(wù)的起點(diǎn)，goalNode為任務(wù)的終點(diǎn)。

a.距離值計(jì)算。

根據(jù)距離矩陣計(jì)算fromNode到toNode點(diǎn)的距離，即

D=A(fromNode,toNode)

(6)

b.邊值計(jì)算與距離矩陣更新。

對(duì)路徑邊f(xié)romNode→toNode進(jìn)行數(shù)量統(tǒng)計(jì)：

M(fromNode,toNode)=M(fromNode,toNode)+1

(7)

A(fromNode,toNode)=

(8)

計(jì)算有向邊toNode→fromNode的總數(shù)量，InverseEdgeWeight為反向邊變數(shù)放大權(quán)值，為常數(shù)，具體計(jì)算式為

M(toNode,fromNode)=M(toNode,fromNode)+

InverseEdgeWeight

(9)

通過將反向邊的數(shù)量放大，從而將其在距離矩陣計(jì)算中統(tǒng)一處理，使得在搜索過程中，自動(dòng)避開反向的邊。但是在一定有反向邊情形下，會(huì)選擇反向邊較少的路徑。距離矩陣計(jì)算式為

A(toNode,fromNode)=

(10)

c.轉(zhuǎn)彎距離值計(jì)算如式(12)所示：

(11)

transCost=a0×(1+transFlag)

(12)

d.f、g、h值的計(jì)算。

首先，根據(jù)距離矩陣計(jì)算fromNode到toNode點(diǎn)的距離，即：

D=A(fromNode,toNode)

(13)

g(toNode)=D+transCost+g(fromNode)

(14)

其次，計(jì)算啟發(fā)函數(shù)值，由于采用曼哈頓距離，需要對(duì)其進(jìn)行外加權(quán)值，才能與當(dāng)前距離在同一量級(jí)進(jìn)行比較，因此，其值取曼哈頓距離與距離D的乘積，即

(15)

toNodex、goalNodex為toNode、goalNode點(diǎn)x方向坐標(biāo)；toNodey、goalNodey為toNode、goalNode點(diǎn)y方向坐標(biāo)；g(toNode)為toNode距離起點(diǎn)的已尋路徑的距離值；h(toNode)為toNode距離終點(diǎn)的預(yù)估的距離值，即

f(toNode)=g(toNode)+h(toNode)

(16)

3.3 任務(wù)路徑搜索算法流程

在系統(tǒng)實(shí)際執(zhí)行中，任務(wù)是不間斷進(jìn)入的，分別在不同時(shí)間進(jìn)行搜索任務(wù)路徑，而不是同時(shí)進(jìn)行各任務(wù)路徑的搜索。因此，多個(gè)任務(wù)分別進(jìn)行搜索時(shí)，其任務(wù)搜索流程如圖3所示。

圖3 多車任務(wù)搜索流程

在每次任務(wù)搜索中，單任務(wù)搜索算法流程如圖4所示。

圖4 單車任務(wù)搜索算法流程

4 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證本文方法的有效性，在MATLAB中進(jìn)行了仿真。以圖5所示穿梭車地圖為例，分別通過改進(jìn)A*算法生成每個(gè)機(jī)器人的路徑，黑色正方形表示穿梭車庫(kù)的貨架貨位(車不能進(jìn)入)。穿梭車根據(jù)任務(wù)下發(fā)先后時(shí)間確定其路徑搜索順序，主要考慮的元素為：

a.路徑中邊沖突數(shù)量，即車輛路徑行駛的反向邊數(shù)量。

b.轉(zhuǎn)彎次數(shù)。

c.路徑點(diǎn)沖突數(shù)量，即重復(fù)經(jīng)過的點(diǎn)數(shù)量。

在穿梭車執(zhí)行任務(wù)中，邊沖突需要更換路徑才能繼續(xù)執(zhí)行任務(wù)，花費(fèi)時(shí)間較長(zhǎng)，轉(zhuǎn)彎也需花費(fèi)較長(zhǎng)時(shí)間，點(diǎn)沖突則需進(jìn)行等待，因此，結(jié)果比對(duì)中，主要參考這3個(gè)元素。對(duì)于穿梭車運(yùn)行過程，有如下簡(jiǎn)單規(guī)則：

a.1段路徑只能直行(橫向或縱向)。

b.行駛路徑段資源獨(dú)占。運(yùn)行1段路徑，不能有其他車輛在此路段有相同的路徑節(jié)點(diǎn)，即獨(dú)占路徑段上的所有節(jié)點(diǎn)資源。

c.路徑段上節(jié)點(diǎn)資源釋放為行駛的當(dāng)前段路徑，穿梭車停在終點(diǎn)時(shí)，釋放其他點(diǎn)資源。

選取2個(gè)任務(wù)情形進(jìn)行比較，分別為：[13,26]→[3,14]，[8,5]→[18,26](點(diǎn)分別由行數(shù)與列數(shù)進(jìn)行組合表示)，其結(jié)果如圖5所示。

圖5 算法雙車路徑示例

根據(jù)穿梭車行駛規(guī)則，對(duì)上述路徑進(jìn)行行駛過程分解。由于A*與Dijkstra路徑相同，所以只對(duì)A*與改進(jìn)A*算法進(jìn)行分析比較(后續(xù)距離單位為網(wǎng)格地圖中方格之間的總長(zhǎng)度，方格邊長(zhǎng)均為1)，具體結(jié)果如表1所示。

表1 2車路徑運(yùn)行解析

在A*搜索路徑情形下， 2號(hào)穿梭車需等待1號(hào)穿梭車在N2點(diǎn)釋放路徑點(diǎn)資源時(shí)，才能開始執(zhí)行任務(wù)，因此，整體完成距離變長(zhǎng)，計(jì)算并運(yùn)行距離數(shù)為25；在改進(jìn)A*算法搜索路徑情形下，2輛車路徑?jīng)]有干涉點(diǎn)，因此，可以同時(shí)并行運(yùn)行，并運(yùn)行距離數(shù)為19。比較分析結(jié)果如表2所示。

表2 2車路徑數(shù)據(jù)比較

在多穿庫(kù)系統(tǒng)實(shí)際執(zhí)行過程中，根據(jù)穿梭車運(yùn)行規(guī)則，車輛路徑之間的距離最少，參考意義不是最優(yōu)先的，因?yàn)槁窂街g存在交叉的或者某段路徑邊沖突，則使得實(shí)際執(zhí)行中等待加長(zhǎng)，且多輛車路徑交叉嚴(yán)重時(shí)，還會(huì)造成路徑之間死鎖。因此，實(shí)際執(zhí)行中需要參考穿梭車之間路徑邊沖突數(shù)量、轉(zhuǎn)彎數(shù)量以及路徑點(diǎn)重復(fù)程度，使得等待時(shí)間變少，整體執(zhí)行效率提高。

由表2可知，采用改進(jìn)A*算法后，穿梭車的路徑在邊沖突數(shù)量、轉(zhuǎn)彎數(shù)以及并行行駛時(shí)間上明顯優(yōu)于其他方法搜索的路徑，可顯著提高整體運(yùn)行效率。

由于邊沖突可能會(huì)產(chǎn)生重新搜索路徑(換路策略，不在本文討論范圍內(nèi))，因此在實(shí)驗(yàn)中，未統(tǒng)計(jì)時(shí)間并行運(yùn)行中的時(shí)間長(zhǎng)度。隨機(jī)產(chǎn)生任務(wù)(每種情況隨機(jī)100次任務(wù))，根據(jù)車數(shù)與產(chǎn)生任務(wù)數(shù)量進(jìn)行結(jié)果比較(取均值)。進(jìn)行數(shù)據(jù)模擬，參數(shù)設(shè)置為a0=0.9，InverseEdgeWeight=100，N=30。模擬結(jié)果統(tǒng)計(jì)如表3所示。

從表3可知，改進(jìn)A*算法可有效減少邊沖突數(shù)量。隨著車輛數(shù)量增加情形下，各算法對(duì)于邊沖突數(shù)量均有增加，但是改進(jìn)A*算法的增加數(shù)量顯著少于其他算法，而對(duì)于計(jì)算時(shí)間的增加相對(duì)于A*算法來(lái)說增加很少，差別在毫秒級(jí)，因此在實(shí)際應(yīng)用中有較好的適應(yīng)性。

表3 模擬實(shí)驗(yàn)各算法數(shù)據(jù)結(jié)果比較

5 結(jié)束語(yǔ)

通過產(chǎn)生大量隨機(jī)任務(wù)，使用改進(jìn)A*改進(jìn)算法進(jìn)行穿梭車庫(kù)多車路徑規(guī)劃，較好地解決了當(dāng)前單獨(dú)使用A*方法存在的路徑方向沖突、路徑轉(zhuǎn)彎數(shù)量不可控的問題，驗(yàn)證了改進(jìn)算法快速、有效性。通過調(diào)整配置權(quán)重參數(shù)方法，可以很好地應(yīng)用于實(shí)際的穿梭車調(diào)度系統(tǒng)中。而在算法中，可以通過改變沖突變數(shù)與轉(zhuǎn)彎數(shù)權(quán)值方式，重新計(jì)算距離矩陣，達(dá)到改變其優(yōu)先順序的目的，因此，在實(shí)現(xiàn)過程中可通過參數(shù)調(diào)整，較好地適應(yīng)不同實(shí)際布局情形下對(duì)結(jié)果的要求。算法中存在一些可優(yōu)化的地方，加入時(shí)間窗后，可以更精確地對(duì)路徑交叉的部分進(jìn)行控制，從而使等待時(shí)間降低到最少，提高多穿庫(kù)整體運(yùn)行效率。對(duì)于穿梭車庫(kù)路徑規(guī)劃問題的研究，能夠?yàn)橄涫搅Ⅲw庫(kù)提供一定的理論基礎(chǔ)與思路，提高穿梭車的效率，并為大規(guī)模穿梭車庫(kù)調(diào)度系統(tǒng)研發(fā)與應(yīng)用提供借鑒，具有較強(qiáng)的應(yīng)用價(jià)值和現(xiàn)實(shí)意義。