基于改進A*算法的四向穿梭車路徑規劃

余嘉雄，白紅星

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

0 引言

跨巷道多層四向穿梭車倉儲系統(以下簡稱多穿庫)是一種密集存儲系統，與普通立體倉庫相比，可以多層多區域并行作業，通過提升機連接各層，提高單位時間出庫總量，縮短分揀時間，被廣泛應用于“貨到人”訂單揀選模式。

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

對于穿梭車路徑規劃問題，當前應用較為廣泛的方法為改進自動導引運輸車AGV路徑規劃方法。然而，穿梭車是基于軌道行進的高速運行物流搬運設備，其軌道與AGV路網布局差異大，穿梭車無法具備AGV近距離跟隨、短距離剎車和就近可變換通道的能力，因而其路徑規劃與AGV有類似的地方，同時也存在較大的差異。

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

本文從穿梭車庫控制軟件系統中路徑搜索實際應用出發，提出了一種改進A*算法的路徑規劃算法，在搜索過程盡量減少各車在各路徑節點行駛范圍內與其他車輛的路徑的點交叉與邊沖突，既保證系統路徑搜索時效要求，同時降低實時路徑沖突處理規則的復雜程度，在穿梭車不同時間搜索路徑時，動態考慮路徑占用情況，從而保證整個系統的穩定高效運行。

1 問題描述

跨巷道多層穿梭車庫，分別由穿梭車、入庫提升機、出庫提升機、層入庫暫存位、層出庫暫存位、縱向/橫向移動通道、出/入庫提升機、換層提升機及存儲貨位構成,具體如圖1所示。

圖1 多穿庫平面布局

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

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

而在路徑干涉檢測中，如果只考慮2點之間最短路徑，不考慮各穿梭車當前位置，則路徑干涉過多，使得結果不理想。因此，需要對各車位置進行區分以及其占用路徑情況，進行動態路徑規劃，所得結果更加合理。

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

a.路徑成環，多個車輛運行形成多條路徑，從而得到有向環，路徑成環后造成路徑封閉，從而不能進行后續工作。

b.點沖突，從不同方向在相同點發生碰撞。

c.邊沖突，在相反位置路過2個點連邊。

2 最大可靠路

在有向圖網絡中，往往需要利用已知的各邊的可靠性概率，求出指定起始點S到目標點T的1條可靠性概率達到最大的路，此路稱為由S到T的最大可靠路[10]。

在網絡G中，各頂點間有向路完好概率為0≤pi,j≤1，定義為

(1)

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

(2)

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

多輛穿梭車路徑干涉時，需對有向路的完好概率進行調整，實際應用時，保證車輛數增加初始階段權值變化大，后續逐漸平緩，避免后續任務找不到路。

在最大可靠路基礎上，做了一些調整，即將點所經過的邊數進行匯總。

將對各路徑中所有經過的邊i→j即從i點出發到j點的邊，進行總數量統計，對每條路徑分別計算組成的邊并進行匯總：Bi,j=Bi,j+1，而反向邊為Bj,i=Bj,i+tmpR。

將沖突次數進行如下變換，即

(3)

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

3 改進A*算法

A*算法是目前應用最多的一種路徑查找和圖形遍歷算法。可準確進行查找和篩選，算法性能優越。各節點級別由A*算法表示為

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

(4)

f(n)為節點Vn的綜合優先級；g(n)為節點Vn距離起點的代價；h(n)為節點Vn距離終點的預計代價。

穿梭車主要向4個方位運行，通過曼哈頓距離表示為

(5)

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

圖2 穿梭車行駛方向示例

3.1 路徑搜索基本思路

a.使用RCA方式進行記錄位置與狀態，點的狀態增加了方向維度，使用A*的迭代結構進行計算。

b.在增加新點時，只考慮2點之間的鄰接屬性，不考慮方向，方向由起點到終點來確定，2點之間距離通過距離矩陣計算，轉彎通過起點與目標點方向差異進行計算得出，避免了考慮方向維度產生的大量解的情況，減少轉彎數量以及由于轉彎計算產生的額外的距離值。

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

d.終點方向通過最終方向與終點需要方向進行1次調整，使得最終方向與終點方向一致。

3.2 兩點間距離以及沖突、轉彎的額外增加距離值計算

數據說明，fromNode為每次迭代搜索時的一小段路徑的出發點，toNode為每次迭代搜索時的一小段路徑的目標點，startNode為整個任務的起點，goalNode為任務的終點。

a.距離值計算。

根據距離矩陣計算fromNode到toNode點的距離，即

D=A(fromNode,toNode)

(6)

b.邊值計算與距離矩陣更新。

對路徑邊fromNode→toNode進行數量統計：

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

(7)

A(fromNode,toNode)=

(8)

計算有向邊toNode→fromNode的總數量，InverseEdgeWeight為反向邊變數放大權值，為常數，具體計算式為

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

InverseEdgeWeight

(9)

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

A(toNode,fromNode)=

(10)

c.轉彎距離值計算如式(12)所示：

(11)

transCost=a0×(1+transFlag)

(12)

d.f、g、h值的計算。

首先，根據距離矩陣計算fromNode到toNode點的距離，即：

D=A(fromNode,toNode)

(13)

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

(14)

其次，計算啟發函數值，由于采用曼哈頓距離，需要對其進行外加權值，才能與當前距離在同一量級進行比較，因此，其值取曼哈頓距離與距離D的乘積，即

(15)

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

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

(16)

3.3 任務路徑搜索算法流程

在系統實際執行中，任務是不間斷進入的，分別在不同時間進行搜索任務路徑，而不是同時進行各任務路徑的搜索。因此，多個任務分別進行搜索時，其任務搜索流程如圖3所示。

圖3 多車任務搜索流程

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

圖4 單車任務搜索算法流程

4 實驗仿真與分析

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

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

b.轉彎次數。

c.路徑點沖突數量，即重復經過的點數量。

在穿梭車執行任務中，邊沖突需要更換路徑才能繼續執行任務，花費時間較長，轉彎也需花費較長時間，點沖突則需進行等待，因此，結果比對中，主要參考這3個元素。對于穿梭車運行過程，有如下簡單規則：

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

b.行駛路徑段資源獨占。運行1段路徑，不能有其他車輛在此路段有相同的路徑節點，即獨占路徑段上的所有節點資源。

c.路徑段上節點資源釋放為行駛的當前段路徑，穿梭車停在終點時，釋放其他點資源。

選取2個任務情形進行比較，分別為：[13,26]→[3,14]，[8,5]→[18,26](點分別由行數與列數進行組合表示)，其結果如圖5所示。

圖5 算法雙車路徑示例

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

表1 2車路徑運行解析

在A*搜索路徑情形下， 2號穿梭車需等待1號穿梭車在N2點釋放路徑點資源時，才能開始執行任務，因此，整體完成距離變長，計算并運行距離數為25；在改進A*算法搜索路徑情形下，2輛車路徑沒有干涉點，因此，可以同時并行運行，并運行距離數為19。比較分析結果如表2所示。

表2 2車路徑數據比較

在多穿庫系統實際執行過程中，根據穿梭車運行規則，車輛路徑之間的距離最少，參考意義不是最優先的，因為路徑之間存在交叉的或者某段路徑邊沖突，則使得實際執行中等待加長，且多輛車路徑交叉嚴重時，還會造成路徑之間死鎖。因此，實際執行中需要參考穿梭車之間路徑邊沖突數量、轉彎數量以及路徑點重復程度，使得等待時間變少，整體執行效率提高。

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

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

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

表3 模擬實驗各算法數據結果比較

5 結束語

通過產生大量隨機任務，使用改進A*改進算法進行穿梭車庫多車路徑規劃，較好地解決了當前單獨使用A*方法存在的路徑方向沖突、路徑轉彎數量不可控的問題，驗證了改進算法快速、有效性。通過調整配置權重參數方法，可以很好地應用于實際的穿梭車調度系統中。而在算法中，可以通過改變沖突變數與轉彎數權值方式，重新計算距離矩陣，達到改變其優先順序的目的，因此，在實現過程中可通過參數調整，較好地適應不同實際布局情形下對結果的要求。算法中存在一些可優化的地方，加入時間窗后，可以更精確地對路徑交叉的部分進行控制，從而使等待時間降低到最少，提高多穿庫整體運行效率。對于穿梭車庫路徑規劃問題的研究，能夠為箱式立體庫提供一定的理論基礎與思路，提高穿梭車的效率，并為大規模穿梭車庫調度系統研發與應用提供借鑒，具有較強的應用價值和現實意義。