張 原， 陳宇軒， 魏璐璐

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

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

引言

隨著機(jī)器人產(chǎn)業(yè)的迅猛發(fā)展， 國內(nèi)的一些企業(yè)也在積極開發(fā)AGV業(yè)務(wù). 在2016年底第三屆世界互聯(lián)網(wǎng)大會(huì)期間， 針對(duì)車位緊張、停車難的問題， ?？低旳GV智能泊車系統(tǒng)提出全新的停車體驗(yàn)， 通過AGV智能泊車， 停車數(shù)量增加40%以上， 而且運(yùn)營期間， 智能泊車AGV根據(jù)電量閾值和任務(wù)緊密程度自主進(jìn)行充電任務(wù)， 不需要認(rèn)為干預(yù)， 保證停車場(chǎng)的正常運(yùn)營，大大縮減了用戶停車、取車時(shí)間[1-4].

?？低旳GV采用視覺和慣性雙導(dǎo)航技術(shù)實(shí)現(xiàn)自主定位， 定位精度誤差小于5 mm； 采用4組舵輪差速驅(qū)動(dòng)， 支持前進(jìn)、后退、平移、旋轉(zhuǎn)等運(yùn)動(dòng)控制， 運(yùn)動(dòng)過程平滑柔順； 激光雷達(dá)監(jiān)測(cè)蔽障， 前/后急停按鈕安全防護(hù)， 實(shí)現(xiàn)安全可靠的運(yùn)動(dòng)控制； 可完成各類汽車的升舉、搬運(yùn)、旋轉(zhuǎn)、下放. 該方案的實(shí)施， 用戶只需將車輛放置在指定位置， 出入庫任務(wù)交由AGV完成， 省去用戶的停車時(shí)間以及節(jié)約取車等待時(shí)間.

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

1 停車場(chǎng)環(huán)境和AGV模型建立

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

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

圖1 停車場(chǎng)環(huán)境建模

圖2 AGV移動(dòng)方向

2 停車算法設(shè)計(jì)

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

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

2.1 車位預(yù)處理

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

1) 計(jì)算每個(gè)車位離出入口的總距離， 并進(jìn)行降序排序.

根據(jù)公式(1)計(jì)算每輛車的優(yōu)先級(jí)系數(shù)，

其中，W是車重量，是待入庫車的平均重量， 是T車的停車時(shí)間， 是待入庫車的平均停車時(shí)間，α、β是比重系數(shù)，P是該輛車的優(yōu)先級(jí).

2) 建立任務(wù)隊(duì)列， 若任務(wù)隊(duì)列為空， 直接分配車位；否則， 根據(jù)車的優(yōu)先級(jí)排列任務(wù)隊(duì)列， 依次輸出預(yù)留車位.

2.2 二維A*算法的路徑規(guī)劃

A*是在Dijkstra的基礎(chǔ)上一種啟發(fā)式的局部優(yōu)化算法， 所謂的"啟發(fā)式"， 就是對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估， 也就對(duì)當(dāng)前位置離目標(biāo)的距離節(jié)點(diǎn)進(jìn)行評(píng)估. A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑的最有效的搜索方法[12-14]， 很好的應(yīng)用在停車場(chǎng)存在固定障礙物的路徑規(guī)劃中， 啟發(fā)的估價(jià)函數(shù)表示式(2).

A*算法的基本思想是:

(1)建立兩個(gè)列表存放節(jié)點(diǎn)數(shù)據(jù)， 分別為open列表和close列表， 首先將源節(jié)點(diǎn)放入open列表；

(2)將f值最小的點(diǎn)作為當(dāng)前節(jié)點(diǎn)， 并從open列表中刪除， 添加到close列表；

(3)如果當(dāng)前節(jié)點(diǎn)為終點(diǎn)節(jié)點(diǎn)， 則結(jié)束搜索；

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

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

由于建模的AGV只有前后左右四個(gè)方向， 所以在遍歷當(dāng)前節(jié)點(diǎn)的臨近節(jié)點(diǎn)時(shí)， 只需遍歷當(dāng)前節(jié)點(diǎn)上下左右的四個(gè)臨近節(jié)點(diǎn)， 若存在停車路徑， A*算法通過父指針由目標(biāo)節(jié)點(diǎn)回到初始節(jié)點(diǎn)完成路徑規(guī)劃.

2.3 三維A*算法的路徑優(yōu)化

2.3.1 可達(dá)點(diǎn)判斷

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

2.3.2 啟發(fā)函數(shù)的改進(jìn)

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

圖3 可達(dá)點(diǎn)判斷流程圖

圖4 A*算法路徑規(guī)劃

本文對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)， 在曼哈頓函數(shù)的基礎(chǔ)上， 修改在Y軸的比例系數(shù)， 使得在路徑規(guī)劃的時(shí)候，優(yōu)先選擇在Y軸方向的柵格， 改進(jìn)后的啟發(fā)函數(shù)如式(3):

其中，θ＞1，θ為 Y 軸的比例系數(shù)， 規(guī)劃路徑時(shí)， 優(yōu)先搜索Y軸方向的空閑柵格， 可以在一定程度上有效的減少路徑重疊， 避免增加路徑長度的代價(jià)， 加快了路徑搜索的同時(shí)也更容易獲得更優(yōu)路徑， 改進(jìn)后的1號(hào)AGV和2號(hào)AGV的路徑如圖5所示， 選擇可達(dá)點(diǎn)時(shí)， 優(yōu)先選擇在Y軸方向的柵格有效的減少了路徑重疊的發(fā)生， 同時(shí)減少了運(yùn)算時(shí)間， 獲得優(yōu)化路徑.

圖5 改進(jìn)啟發(fā)函數(shù)的路徑規(guī)劃

2.3.3 三維最優(yōu)路徑求解

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

三維A*算法和傳統(tǒng)A*算法相比關(guān)鍵因素在于增加了時(shí)間因素， 將等待時(shí)間加入啟發(fā)函數(shù)， 綜合路徑距離和等待時(shí)間兩個(gè)因素進(jìn)而規(guī)劃出入庫和出庫任務(wù)的最佳路徑， 以提高錯(cuò)綜復(fù)雜的大型停車場(chǎng)的運(yùn)營效率.

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

算法流程圖如圖6所示.

圖6 延時(shí)最優(yōu)路徑流程圖

三維A*算法算法將等待時(shí)間加入最優(yōu)路徑的判斷條件， 僅通過一個(gè)任務(wù)延時(shí)變量就優(yōu)化了路徑， 算法簡(jiǎn)單利于實(shí)現(xiàn)， 對(duì)停車場(chǎng)的運(yùn)營效率的提升具有較大實(shí)際意義.

3 算法驗(yàn)證仿真

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

采用改進(jìn)后的三維A*算法對(duì)存在多個(gè)出入庫任務(wù)的情景進(jìn)行仿真， 以驗(yàn)證算法的可行性.

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

圖7 當(dāng)前停車場(chǎng)狀態(tài)

表1 路徑長度和消耗時(shí)間數(shù)據(jù)

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

3.2 三維A*算法效率分析

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

三維A*算法的停車場(chǎng)管理效率主要取決于啟發(fā)函數(shù)里θ值的選擇， 針對(duì)不同的θ值， 針對(duì)圖7模型停車場(chǎng)， 在處理一定數(shù)量車輛的入出庫任務(wù)進(jìn)行仿真， 與傳統(tǒng)停車場(chǎng)的效率進(jìn)行對(duì)比， 結(jié)果如表2所示.

表2 AGV智能停車場(chǎng)和傳統(tǒng)停車場(chǎng)效率對(duì)比(單位: t)

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

4 結(jié)束語

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