基于改進A*算法的AGV智能泊車算法①

張 原， 陳宇軒， 魏璐璐

1(西北工業大學 電子信息學院，西安 710072)

2(西安市鐵一中學，西安710054)

引言

隨著機器人產業的迅猛發展， 國內的一些企業也在積極開發AGV業務. 在2016年底第三屆世界互聯網大會期間， 針對車位緊張、停車難的問題， 海康威視AGV智能泊車系統提出全新的停車體驗， 通過AGV智能泊車， 停車數量增加40%以上， 而且運營期間， 智能泊車AGV根據電量閾值和任務緊密程度自主進行充電任務， 不需要認為干預， 保證停車場的正常運營，大大縮減了用戶停車、取車時間[1-4].

海康威視AGV采用視覺和慣性雙導航技術實現自主定位， 定位精度誤差小于5 mm； 采用4組舵輪差速驅動， 支持前進、后退、平移、旋轉等運動控制， 運動過程平滑柔順； 激光雷達監測蔽障， 前/后急停按鈕安全防護， 實現安全可靠的運動控制； 可完成各類汽車的升舉、搬運、旋轉、下放. 該方案的實施， 用戶只需將車輛放置在指定位置， 出入庫任務交由AGV完成， 省去用戶的停車時間以及節約取車等待時間.

目前各類停車場智能泊車算法只是針對單任務泊車提出解決方案， 這種情況過于理想化， 對錯綜復雜的大型停車場來說， 存在著多個出入庫任務同時進行的情況， 本文在海康威視AGV智能機器人的基礎上， 旨在解決多個AGV同時工作的情況， 提出新的解決方案: 本設計在A*算法的基礎上， 將等待時間加入啟發函數， 提出三維A*算法以解決停車場的智能泊車[5]. 在該停車場管理系統， 客戶進入停車場不需人工停車， 入庫時只需將車停到入口位置并發出入庫指令， 入庫停車任務交由AGV完成， 并且在停車場內部設有自動泊車引導系統， 采用算法規劃出到達指定車位的最優路徑， 將車送入預留車位， 進而節省車主尋找有效泊車位的時間； 客戶在出庫時， 發出出庫任務指令， 系統收到指令在最短時間內規劃出最優出庫路線， AGV將車送至出口， 完成出庫任務[6-8].

1 停車場環境和AGV模型建立

停車場環境的建模是建立一個便于AGV進行路徑規劃和使用的環境模型， 以實現AGV對出入口、障礙物、車位以及通道等標識的識別， 便于AGV控制器存儲、處理、更新和使用， 有效的規劃出入庫合理的路徑. 環境模型如圖1所示， 以左下角為原點， 每個柵格代表一個單位， 地圖中P表示車位， ×表示障礙物(B)， 右面*表示入口 (I)， 左面*表示出口 (E)， 地圖中存在唯一的出入口， 白色表示行車道路(X)， 每個車位都與行車道路(X)相鄰， 每個車位(P)只能停一輛車[9，10].

規劃出車輛出入庫的最優軌跡， 記錄在白色的柵格上， 在地圖上存儲AGV運載車輛的允許軌跡， 和障礙等相關信息， AGV的軌跡被分解為單個的移動， 每秒移動一個單位， 單個的移動軌跡被記錄在每個柵格上， 每個柵格上的移動信息規定了AGV在這個柵格的移動方向(前、后、左、右移動).

圖1 停車場環境建模

圖2 AGV移動方向

2 停車算法設計

本算法主要分為兩部分， 第一部分是車位預處理，第二部分是路徑規劃算法.

預處理車位分配預處理， 預處理中忽略了AGV的影響， 只從車位和汽車信息來計算出初步方案， 提前為每輛車計算好預留車位數， 入庫時通過預留車位數選擇合理車位， 相比安排具體車位， 這種方式能夠提高車位的利用率和停車場的效率. 通過這種預處理方式將原本的三維數據降低至二維， 大大加快了數據的處理速度， 從而可以得到較優的全局解.

2.1 車位預處理

總距離越長的庫， AGV處理時的功耗和時間代價相應也越較高， 因此提高總距離較短車庫的使用率有利于降低總體代價. 車位預處理的目的是在車入庫選擇時， 為后面的待入庫車輛預留數個更優的車位[11]， 以節省AGV載車能耗以及提升整個停車系統的效率. 車位預處理采用鏈表的存儲方式處理， 具體的步驟如下:

1) 計算每個車位離出入口的總距離， 并進行降序排序.

根據公式(1)計算每輛車的優先級系數，

其中，W是車重量，是待入庫車的平均重量， 是T車的停車時間， 是待入庫車的平均停車時間，α、β是比重系數，P是該輛車的優先級.

2) 建立任務隊列， 若任務隊列為空， 直接分配車位；否則， 根據車的優先級排列任務隊列， 依次輸出預留車位.

2.2 二維A*算法的路徑規劃

A*是在Dijkstra的基礎上一種啟發式的局部優化算法， 所謂的"啟發式"， 就是對每一個搜索的位置進行評估， 也就對當前位置離目標的距離節點進行評估. A*算法是一種靜態路網中求解最短路徑的最有效的搜索方法[12-14]， 很好的應用在停車場存在固定障礙物的路徑規劃中， 啟發的估價函數表示式(2).

A*算法的基本思想是:

(1)建立兩個列表存放節點數據， 分別為open列表和close列表， 首先將源節點放入open列表；

(2)將f值最小的點作為當前節點， 并從open列表中刪除， 添加到close列表；

(3)如果當前節點為終點節點， 則結束搜索；

(4)處理當前節點的所有臨近節點: 若已經在open列表， 再次計算g值， 與之前的g值進行比較， 以判斷是否更新父節點和g值； 若不在open列表中， 那么就添加到open列表， 若該節點為障礙物或者已經被添加至close列表， 此節點不予處理；

(5)如果open列表不為空， 轉為步驟(2).

由于建模的AGV只有前后左右四個方向， 所以在遍歷當前節點的臨近節點時， 只需遍歷當前節點上下左右的四個臨近節點， 若存在停車路徑， A*算法通過父指針由目標節點回到初始節點完成路徑規劃.

2.3 三維A*算法的路徑優化

2.3.1 可達點判斷

A*算法有效的解決了單個AGV工作的出入庫路徑規劃的問題， 但是對于大型停車場存在多個AGV同時工作的情況， 就會出現同一柵格碰撞和時間維度上相遇的沖突， 導致停車場內不必要的損失. 為了實現合理規避同時工作的AGV并且具有最短的行程時間的路徑， 解決時間沖突問題， 本文主要基于傳統二維A*算法的算法思想， 實時對周圍可達點進行判斷， 若時間發生沖突時， 使該點不可達， 而選取其他周圍臨近點，從而到達到指定車位， 完成出入庫動作.

2.3.2 啟發函數的改進

增加了柵格是否可達的判斷之后， 徹底解決了碰撞和相遇的沖突， 但在復雜的停車場內， 出入庫任務和AGV返回任務同時進行的幾率很大， 最終導致路徑規劃并不是最優路徑甚至規劃失敗. 如圖4所示， 假設停車場內同時進行1號AGV到P6車位入庫以及2號AGV返回到入口待命的任務， 采用A*算法規劃出的兩條路徑之間存在一大段的重疊， 根據可達點的判斷，如果規劃出可用路徑， 其中一條路徑必須“躲避”一個柵格才能成功規劃出路徑， 但是這種做法會增加路徑搜索長度， 對于AGV較多的大型停車場， 路徑規劃的運算時間也會急劇上升.

圖3 可達點判斷流程圖

圖4 A*算法路徑規劃

本文對啟發函數進行改進， 在曼哈頓函數的基礎上， 修改在Y軸的比例系數， 使得在路徑規劃的時候，優先選擇在Y軸方向的柵格， 改進后的啟發函數如式(3):

其中，θ＞1，θ為 Y 軸的比例系數， 規劃路徑時， 優先搜索Y軸方向的空閑柵格， 可以在一定程度上有效的減少路徑重疊， 避免增加路徑長度的代價， 加快了路徑搜索的同時也更容易獲得更優路徑， 改進后的1號AGV和2號AGV的路徑如圖5所示， 選擇可達點時， 優先選擇在Y軸方向的柵格有效的減少了路徑重疊的發生， 同時減少了運算時間， 獲得優化路徑.

圖5 改進啟發函數的路徑規劃

2.3.3 三維最優路徑求解

改進后的啟發式函數雖然在一定程度上避免了路徑重疊的問題， 但是在對于多AGV的大型停車場來說， 運動錯綜復雜， 上述方法不足以完全消除路徑重疊和路徑過長甚至規劃失敗， 為了保證停車場的正常運作， 在改進啟發函數的基礎上， 構建三維 A*算法， 本文采用任務延時機制， 路徑規劃時， 遇到重疊， 通過任務延時， 增加等待時間這一維度， 進一步判斷路徑代價，進而規劃出最優路徑.

三維A*算法和傳統A*算法相比關鍵因素在于增加了時間因素， 將等待時間加入啟發函數， 綜合路徑距離和等待時間兩個因素進而規劃出入庫和出庫任務的最佳路徑， 以提高錯綜復雜的大型停車場的運營效率.

執行路徑規劃任務時， 設置任務延時初始值為0，定義代價向量Cost(n)和最小代價向量minCost(n)， 代價向量Cost(n)是AGV從初始柵格到終點的代價， 其中包括等待時間代價W(n)和行程代價D(n)， 最小路徑代價定義為最新路徑規劃的代價和上次計算路徑代價之間的差值. 在AGV執行出入庫任務的過程中， 對周圍的點進行可達判斷， 調用三維A*算法規劃路徑， 若不可達， 否則延時一個時間單位， 重新進行規劃， 若規劃出可達路徑， 計算路徑代價和最小路徑代價， 暫存在Cost(n)和minCost(n)， 延時一個時間單位， 再次調用三維 A*算法規劃路徑， 每次迭代記錄最小路徑代價， 直至時間延時代價大于最小路徑代價， 終止循環， 返回最優路徑.則Cost(n)可以通過以下函數計算:

算法流程圖如圖6所示.

圖6 延時最優路徑流程圖

三維A*算法算法將等待時間加入最優路徑的判斷條件， 僅通過一個任務延時變量就優化了路徑， 算法簡單利于實現， 對停車場的運營效率的提升具有較大實際意義.

3 算法驗證仿真

3.1 三維A*算法有效性的仿真

采用改進后的三維A*算法對存在多個出入庫任務的情景進行仿真， 以驗證算法的可行性.

圖7為停車場在某一時刻的使用狀況， 停車場剩余8個車位空閑， 其余車位被占用， 圖中紅色代表車位已被占用. 車輛到達停車場入口的時間服從泊松分布，短時間內有4輛車順序進入停車場待進入停車場車位，并有P1、P8兩個車位的2輛車發出出庫命令. 根據車位預處理算法， 選取車位P3、P4、P9作為3輛車的待入庫車位， 采用順序執行和三維A*算法分別對6輛車的出入庫進行路徑規劃， AGV的路徑距離和執行任務時間段如表1所示， 其中s表示單位長度， t表示單位時間.

圖7 當前停車場狀態

表1 路徑長度和消耗時間數據

由表1可知， 任務順序執行任務的路徑距離為37 s， 消耗的總時間為 37 t； 三維 A*算法完成 6輛車入出庫任務的路徑距離為37 s， 消耗總時間為12 t， 三維A*算法可完成停車場的智能泊車過程. 相對于按照順序依次執行任務， 雖然總的路徑長度不變或者可能會在一定程度上增加路徑長度， 但是整個任務執行消耗時間大大減少， 這種方案更能滿足用戶的實際需要， 提高停車場的運營效率.

3.2 三維A*算法效率分析

泊車行為是由人、車和泊車位有機組成， 傳統停車場的運營效率的屬性主要包括入口至泊車的行駛距離、時間以及泊車位至用戶目的地的步行距離和時間(用戶需步行往返這個距離進行放車和取車)， 而第一個屬性主要取決于駕駛員的駕車技術和側方停車技術，所需時間因人而異， 如果駕駛技術不嫻熟， 在多任務同時進行的停車場內， 事故發生的可能性極大， 造車不必要的損失， 而基于AGV的智能停車場入出庫的任務交由AGV完成， 三維A*算法存在可達點的判斷以及規劃出的最優路徑， 不僅避免了事故的發生， 而且省去了用戶停車和返回時間； 第二個屬性， 由于用戶不同， 假設用戶的目的地都為出口處， 而AGV停車場用戶不需到達泊車位， 只需在出口處更短的時間等待， 即可提車使用， 大大提高停車場的運營效率.

三維A*算法的停車場管理效率主要取決于啟發函數里θ值的選擇， 針對不同的θ值， 針對圖7模型停車場， 在處理一定數量車輛的入出庫任務進行仿真， 與傳統停車場的效率進行對比， 結果如表2所示.

表2 AGV智能停車場和傳統停車場效率對比(單位: t)

表2中Cin表示仿真入庫任務的車輛數量，Cout表示仿真出庫任務的車輛數量，Tin表示處理入庫任務完成所需時間，Tout表示出庫任務完成所需時間. 從表中可以看出， 無論比例系數θ取值多大， AGV智能停車場的效率都明顯高于傳統停車場， 但是θ并不是越大越好，θ具體的取值根據停車場的實際布局情況而定.

4 結束語

本文在A*算法的基礎上， 提出了改進的三維A*路徑規劃算法， 通過仿真驗證了智能泊車算法的合理性和可行性， 算法可滿足智能停車場的正常運營， 且系統可預留出最優車位， 規劃出出入庫的最優路徑， 該問題的研究不僅避免了客戶對于車位選擇的盲目性，而且省去了停車時間以及節約了取車的等待時間， 有效的降低了停車場的運營成本， 并提高了停車場的運營效率智能化程度， 使得停車場內部管理更加規范化、有序化， 尤其對于車位較多的大型停場管理具有重要的實際意義.