緊致化智能停車系統的運行沖突控制*

施玉璋 王正國

武漢理工大學交通與物流工程學院 武漢 430000

0 引言

隨著社會的發展，近年來我國汽車保有量持續增加，停車難的問題日益顯著，高效利用停車資源，使停車系統平穩高效運行已成為當前亟待解決的問題，故緊致化智能停車系統（Smart Compact Automated Parking System，SCAP 系統）應運而生。該系統由移動小車在存儲通道上方四向移動以完成車輛的水平運行，減少了傳統機械式立體車庫水平運行時所需的巷道及移動以騰出空間的時間，有效提高了土地利用率和運行效率。移動小車四向移動容易導致運行沖突發生，影響系統的平穩高效運行。

為解決此類問題，文獻[1]提出了動態路徑規劃的算法框架，為停車系統上多機器人小車的實時并發定義了一個最小障礙物的策略；文獻[2]針對智能電梯停車庫，在系統中AGV 的最短可行路徑上實時更新時間窗以實現無碰撞運行；針對應用廣泛的平面移動式立體車庫，文獻[3]基于全局最優路徑使用動態窗口法，預測移動設備在采樣速度下將要前進的軌跡和方向，以實現避障運行；文獻[4]則給出了不安全狀態下基于時間窗算法的RGV 運行沖突控制策略。目前，國內外學者主要通過Petri 網、時間窗迭代和動態窗口法實現存取系統的運行沖突控制[5-10]。

目前，針對停車系統運行沖突控制的研究較少，無法直接遷移至SCAP 系統，且常使用等待或重規劃的方法，容易導致系統運行不平穩，且造成較長延遲，影響系統運行效率。本文將結合以往研究，在使用改進A*算法為移動小車規劃最佳路徑的基礎上，提出了時間窗的3 種操作，以速度控制為主，在盡量不影響運行效率的同時實現移動小車的無沖突運行。

1 系統描述

圖1 為SCAP 系統的示意圖，其存取車操作通過電梯垂直運行車輛，移動小車提升并四向移動水平運行車輛完成，且二者相互獨立。

圖1 緊致化智能停車系統結構

傳統SCAP 系統一般以單移動小車配備于單列存儲通道，但容易導致需求與資源不匹配而造成浪費，故引入如圖2 的抓取機器人為移動小車，通過前后夾持架、輪胎夾持等實現平面上的四向移動，從而合理調整系統資源配置。此為未來SCAP 系統發展的主要趨勢，本文將基于此進行研究分析。

圖2 抓取機器人

圖3 所示為實現SCAP 系統中多移動小車的無沖突運行，其調度流程為：

圖3 移動小車運行調度總流程

Step1：為移動小車規劃初始路徑；

Step2：預處理階段，判斷并控制移動小車規劃路徑上的運行沖突；

Step3：實時運行階段，判斷移動小車是否到達終點；若到達，跳轉至Step5；

Step4：監測移動小車的實時運行信息，實時控制移動小車運行沖突；

Step5：多移動小車調度結束。

2 移動小車路徑規劃

2.1 環境建模

規劃SCAP 系統中移動小車的初始運行路徑，首先需將作業環境信息表示為數字化地圖即環境建模。結合移動小車作業環境特點，將基于以下假設使用柵格地圖構建環境模型：1）柵格地圖的分割單位為存儲通道，即1 個柵格點表示1 個存儲通道；2）柵格點不表示實際尺寸；3）柵格點以0 和1 分別表示不可/可通行；4）每個柵格點僅可容納一輛移動小車；5）環境地圖中，以白色和黑色分別表示可/不可通行，其余顏色表示在搜尋路徑時被訪問。

2.2 單移動小車運行路徑

2.2.1 基礎A*算法

A*算法是由P.E.Hart 等[11]提出的，是靜態路網中，一種基于已知路徑信息即式(1)向外擴展的典型的最短路徑搜索算法，其流程如圖4 所示。

圖4 A 星算法流程圖

式中：f(n)為從起點經由節點n到達終點的路徑代價估計值，包含起點到節點n的路徑代價實際值g(n)和節點n到終點的啟發距離函數h(n)；h(n)為當前節點到終點的實際成本。

2.2.2 改進的A*算法

為移動小車規劃最佳初始路徑，將從以下幾方面改進A*算法：

1）實際意義上路徑效果更佳

路徑少轉向：SCAP 系統中移動小車通過制動后啟動實現轉向，需長時間占用轉向節點，且耗能更多。因此將為擴展節點的啟發距離增加轉彎懲罰系數tp，以降低轉向選擇。

路徑避免擁堵路段：使用傳統A*算法為多任務規劃路徑時，各節點使用頻數不均衡，部分節點高頻使用，增加了擁堵和沖突的發生概率。因此，獲取并實時更新路徑節點n的使用頻數即擁堵值c(n)，并根據c(n)增加擁堵懲罰系數cp。

2）搜索效率更高

傳統A*算法需耗費大量時間搜尋路徑，其f(n)中g(n)和h(n)分別表示Dijkstra 算法的準確性和BSF 的快速性，加入權重比例x以合理分配二者比例，可把握準確性與速度的均衡，提高路徑搜索效率。

綜上，改進A*算法的f(n)為式(2)；同時考慮運行通道的實際尺寸如式(3)。

2.2.3 路徑評價

綜合考慮路徑運行距離l(n)，拐彎數w(n)，平均擁堵值d(n)及路徑搜索時間t以評價路徑，并使用minmax 歸一化各評價指標為lr(n)、wr(n)、dr(n)和tr，歸一化的最值為相同環境下各指標的最值。路徑評價函數為

3 運行沖突分析及控制

3.1 運行沖突類型

運行沖突是指移動小車在同一時間爭奪同一路徑節點從而造成阻塞的情形。由于SCAP 系統中移動小車可四向移動，故運行沖突可分為相向沖突、追及沖突以及節點沖突。相向沖突如圖5 所示，指多移動小車相向運行以爭奪同一路徑節點，可分為交叉相向沖突和對立相向沖突。

圖5 相向沖突示意圖

追及沖突如圖6 所示，指多移動小車在同一運行路徑上追及運行以爭奪同一路徑節點；節點沖突如圖7 所示，移動小車的路徑節點被障礙物占用，使無法通行，僅在實時運行中發生。

圖6 追及沖突示意圖

圖7 節點沖突示意圖

3.2 運行沖突控制

3.2.1 移動小車優先級判定規則

SCAP 系統單層環境中存在多移動小車，按性質可分為存取移動小車、空載移動小車和障礙移動小車。為避免障礙移動小車造成系統局部癱瘓，故其優先級為最高；其次為存取移動小車，最低為空載移動小車。同類移動小車則按下述規則判定優先級：

FCFS（First Come First Serviced）規則：遵循任務發起越早優先級越高的原則；

SRRT（Shortest Remaining Running Time）規則：沖突時的理論剩余行程時間越短優先級越高；

RD（Random Determination）規則：若按上述規則無法判定，則隨機確定。

3.2.2 預處理階段

在預處理階段，基于沖突時移動小車的優先級判定，提出時間窗的3 種操作，完成移動小車的運行沖突控制。

1）時間窗初始化

時間窗指移動小車從開始進入到開始離開路徑節點時所占用的時間段。由初始規劃路徑NVi＝{ns，…，nm，…，ne}，初始化移動小車Vi的時間窗為WVi＝{wm＝[tmin，tmout]}。ns為路徑起點，ne為目標點，WVi為Vi各路徑節點的時間窗集合，tmin和tmout為進入和離開nm的時間點。

初始化時間窗應考慮加減速過程。系統運行通道的長度和寬度分別為l和w，通過節點nm時，統一表示直線運行、轉彎制動和啟動距離為lm、lmb和lma。

①啟/制動時節點n1的時間窗為

②加速運行時節點n1的時間窗為

③加速-勻速運行時節點n1的時間窗為

④勻速運行時節點n1的時間窗為

⑤轉彎運行時節點n1的時間窗為

由以上計算公式可得到可初始化移動小車在不同運行類型下的節點時間窗，v0和v為進入節點的初始速度和勻速運行速度。

2）時間窗檢測

時間窗檢測用于判斷沖突是否存在及存在類型，通過判斷移動小車的時間窗是否重疊，路徑NVi是否連續重疊，以及運行方向進行判斷。

若時間窗WVi和WVj在節點nm重疊，則表明移動小車Vi和Vj在同一時間點爭奪節點nm，判定Vi和Vj存在沖突；若Vi和Vj在沖突節點nm后路徑離散重疊，即Vi和Vj在nm處不存在相同或相反的重疊路徑，故Vi和Vj存在交叉相向沖突。若連續重疊，且運行方向相反，則Vi和Vj存在對立相向沖突；反之則為追及沖突。

3）時間窗重規劃

時間窗檢測后，將使用時間窗重規劃控制存在的運行沖突。

傳統運行沖突主要通過重規劃路徑或停止等待進行控制，但停止等待下移動小車需不斷地啟制動，增加了運行能耗，且易導致運行環境的不穩定；而路徑重規劃則不僅增加啟停次數，且會偏離原最佳路線，增加延遲時間。

定義：（Vi，Vj，…，Vm）共n輛移動小車在節點nk處發生沖突；沖突時將移動小車按優先級從高到低排序為0，1…，i，…，（n-1）。優先級i的移動小車為Vpi，Vpi在nk的上一路徑節點為，Vpi進入路徑節點nk的時間為tpik。

為盡可能減少其余節點的時間窗變化，時間窗重規劃將盡量于節點nk-1完成。時間窗重規劃包含2 種操作策略：

①策略1（速度調控策略） 指調節Vp(i+1)在節點 的速度變化曲線，使Vp(i+1)到達nk時Vpi已離開，且Vp(i+1)進入和離開節點的速度不變，以避免新沖突的產生。

速度調控策略是基于SCAP 系統中移動小車勻速運行速度v較小，能在較短時間和距離內完成加減速的特點所提出的，如圖8 所示，其實質為拉伸Vp(i+1)在的時間窗而避免資源爭奪。

圖8 速度調控策略下的時間窗重規劃示意圖

速度調控存在2 種情況。情況1：Vp(i+1)在節點處啟動，即為路徑起點或轉彎點，此時僅需使Vp(i+1)在處等待一段時間后再啟動即可；情況2：Vp(i+1)在節點處直線運行，直線運行時Vp(i+1)在處可能存在勻速或加速后勻速運行2 種情況。此時調控Vp(i+1)的速度，使其在上低速運行以拉伸時間窗。當勻速運行時：使Vp(i+1)在處以其加速度a減速至vm，再低速運行時間tm實現等待，最終再加速至v即可，其速度變化曲線如圖9a 所示，遵循路程相等原則，速度調控的各參數值需滿足式(5)和式(6)，即

圖9 速度調控曲線

加速后勻速運行是勻速運行的特殊情況，需使Vp(i+1)以原速度勻速運行時間tm，再提升至速度v即可，其速度變化曲線如圖9b。遵循路程相等原則，速度調控的各參數值需滿足式(7)和式(8)，即

速度調控策略可控制交叉相向沖突和追及沖突，追及沖突下需使追及移動小車速度小于等于被追及移動小車，以避免新沖突。

②策略2（路徑重規劃策略） 即速度調控下仍存在少數無法徹底控制的運行沖突，故應使用路徑重規劃策略，其實質是重規劃Vp(i+1)在節點后的時間窗，以避免沖突。

路徑重規劃即根據當前環境，視沖突節點nk為障礙物，以節點為起點，為Vp(i+1)重新規劃至終點的路徑，并精簡路徑以避免“回頭路”。

3.2.3 實時處理階段

在實時處理階段，移動小車可由自身傳感器在節點處檢測到沖突現象，此時將在處為移動小車重新規劃至終點的路徑。極少數情況下若沖突無法解決，則移動小車將緊急制動并發出報警，由人工介入處理。

預處理階段在很大程度上減少實時運行沖突的發生，經過2 階段處理，可基本實現SCAP 系統中移動小車穩定高效的安全運行。

4 實驗驗證分析

4.1 路徑規劃實驗

為驗證改進A*算法規劃路徑的優越性，將在不同環境下實驗并由式(4)評估路徑。

考慮實際應用規模及發展趨勢，以15×15 的SCAP系統運行環境為例，并考慮3 種典型環境，即1）稀疏環境：障礙物較少且稀疏分布，存在于存取頻率較低時；2）狹窄環境：障礙物較多，且緊密相連，出現在存取高峰期；3）凹形環境：障礙物較少，但存在U 形分布的障礙物，存在于區域存取頻繁時，目前多文獻均進行了針對性研究。

各環境下，改進前后A*算法規劃的路徑及評價如表1 和圖10 ～圖12，直觀表示運行距離為（nx，ny），即沿x軸和y軸經過的節點數。

表1 3 種典型環境下路徑規劃對比

圖10 稀疏環境下的路徑規劃

圖11 狹窄環境下的路徑規劃

圖12 凹形環境下的路徑規劃

由表1 和圖10 ～圖12 可知，在不同環境下，改進前后的A*算法均可為移動小車規劃最短路徑，但改進后的路徑在轉向數和節點使用均衡上都有明顯提升，且避免了對無用節點的盲目搜索，提高了路徑的搜索效率。

以改進前后的A*算法進行相同的多任務路徑規劃，各節點的使用頻數如圖13，直觀表明改進的A*算法節點使用更均衡，且降低了路徑負載峰值，有效減少了運行沖突發生的可能性。

圖13 改進前后路徑節點負載

綜上所述，改進的A*算法能有效提升系統運行效率，減少系統耗能，同時盡可能避免了移動小車運行沖突發生的可能性。

4.2 運行沖突控制實驗

4.2.1 有效性驗證

基于最佳路徑規劃，構建運行測試案例如表2 所示；作運行沖突控制實驗，實驗參數如表3 所示。

表2 運行測試案例

表3 實驗運行參數

檢測并控制運行沖突，并人為添加節點沖突，可獲取運行路徑如圖14，運行沖突發生級控制情況如表4所示。

表4 測試案例運行沖突發生及控制情況

圖14 測試案例運行路徑

由圖14 和表4 可知，各測試案例均順利到達運行終點，且速度調控策略下，移動小車的延遲時間較短，路徑重規劃下延遲時間則與實際運行路徑相關。

圖15 為沖突2 下節點時間窗示意圖，表明了速度調控策略下，移動小車將緊密相連通過沖突節點，節點不存在空閑狀態，故延遲時間為不改變運行路徑下的最短延遲時間。

圖15 沖突2 的時間窗示意圖

4.2.2 控制性能分析

運行沖突的控制性能主要表現在延遲時間和啟停次數。延遲時間越短，系統運行效率越高；啟停次數越多，移動小車啟制動更頻繁，不僅耗能增大，還容易導致系統運行不穩定。

為表明速度調控策略的優越性，將其與以往研究常用的路徑重規劃和停止等待進行比較。為避免偶然情況，比較不同方法下多次運行沖突的控制性能如圖16，以移動小車5 為例的速度變化曲線如圖17。

圖16 不同策略下控制性能比較

圖17 不同控制策略下的速度變化曲線

結合圖16 和圖17，速度調控策略的控制性能有顯著優越性，其主要原因是在路徑重規劃下，大多需增加轉向以避免沖突，而轉向將耗費較長運行時間和增加啟停次數；在停止等待時，重新啟動需增加延遲時間和啟停次數。

在性能比較實驗中，存在少數情況下速度調控并非最優，如路徑重規劃下精簡“回頭路”，前期沖突控制延遲時間較久而避免了后續沖突等。

綜上所述，以速度控制為主的時間窗運行沖突控制能有效完成對運行沖突的檢測和控制，且較以往方法有顯著優越性。

5 結論

本文基于SCAP 系統對多移動小車調度流程，使用A*算法為移動小車規劃初始路徑，并提出了移動小車優先級判定下基于時間窗模型的運行沖突控制方法，并通過實驗分析了控制方法的有效性和優越性和實際可行性。最終結果表明，本文研究在最短路徑基礎上，有效控制運行沖突，且較以往方法，該方法能有效提升系統的運行效率，減少系統耗能，有顯著的優越性。