施玉璋 王正國

武漢理工大學(xué)交通與物流工程學(xué)院 武漢 430000

0 引言

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

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

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

1 系統(tǒng)描述

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

圖1 緊致化智能停車系統(tǒng)結(jié)構(gòu)

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

圖2 抓取機器人

圖3 所示為實現(xiàn)SCAP 系統(tǒng)中多移動小車的無沖突運行，其調(diào)度流程為：

圖3 移動小車運行調(diào)度總流程

Step1：為移動小車規(guī)劃初始路徑；

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

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

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

Step5：多移動小車調(diào)度結(jié)束。

2 移動小車路徑規(guī)劃

2.1 環(huán)境建模

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

2.2 單移動小車運行路徑

2.2.1 基礎(chǔ)A*算法

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

圖4 A 星算法流程圖

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

2.2.2 改進的A*算法

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

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

路徑少轉(zhuǎn)向：SCAP 系統(tǒng)中移動小車通過制動后啟動實現(xiàn)轉(zhuǎn)向，需長時間占用轉(zhuǎn)向節(jié)點，且耗能更多。因此將為擴展節(jié)點的啟發(fā)距離增加轉(zhuǎn)彎懲罰系數(shù)tp，以降低轉(zhuǎn)向選擇。

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

2）搜索效率更高

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

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

2.2.3 路徑評價

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

3 運行沖突分析及控制

3.1 運行沖突類型

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

圖5 相向沖突示意圖

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

圖6 追及沖突示意圖

圖7 節(jié)點沖突示意圖

3.2 運行沖突控制

3.2.1 移動小車優(yōu)先級判定規(guī)則

SCAP 系統(tǒng)單層環(huán)境中存在多移動小車，按性質(zhì)可分為存取移動小車、空載移動小車和障礙移動小車。為避免障礙移動小車造成系統(tǒng)局部癱瘓，故其優(yōu)先級為最高；其次為存取移動小車，最低為空載移動小車。同類移動小車則按下述規(guī)則判定優(yōu)先級：

FCFS（First Come First Serviced）規(guī)則：遵循任務(wù)發(fā)起越早優(yōu)先級越高的原則；

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

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

3.2.2 預(yù)處理階段

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

1）時間窗初始化

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

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

①啟/制動時節(jié)點n1的時間窗為

②加速運行時節(jié)點n1的時間窗為

③加速-勻速運行時節(jié)點n1的時間窗為

④勻速運行時節(jié)點n1的時間窗為

⑤轉(zhuǎn)彎運行時節(jié)點n1的時間窗為

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

2）時間窗檢測

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

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

3）時間窗重規(guī)劃

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

傳統(tǒng)運行沖突主要通過重規(guī)劃路徑或停止等待進行控制，但停止等待下移動小車需不斷地啟制動，增加了運行能耗，且易導(dǎo)致運行環(huán)境的不穩(wěn)定；而路徑重規(guī)劃則不僅增加啟停次數(shù)，且會偏離原最佳路線，增加延遲時間。

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

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

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

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

圖8 速度調(diào)控策略下的時間窗重規(guī)劃示意圖

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

圖9 速度調(diào)控曲線

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

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

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

路徑重規(guī)劃即根據(jù)當(dāng)前環(huán)境，視沖突節(jié)點nk為障礙物，以節(jié)點為起點，為Vp(i+1)重新規(guī)劃至終點的路徑，并精簡路徑以避免“回頭路”。

3.2.3 實時處理階段

在實時處理階段，移動小車可由自身傳感器在節(jié)點處檢測到?jīng)_突現(xiàn)象，此時將在處為移動小車重新規(guī)劃至終點的路徑。極少數(shù)情況下若沖突無法解決，則移動小車將緊急制動并發(fā)出報警，由人工介入處理。

預(yù)處理階段在很大程度上減少實時運行沖突的發(fā)生，經(jīng)過2 階段處理，可基本實現(xiàn)SCAP 系統(tǒng)中移動小車穩(wěn)定高效的安全運行。

4 實驗驗證分析

4.1 路徑規(guī)劃實驗

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

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

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

表1 3 種典型環(huán)境下路徑規(guī)劃對比

圖10 稀疏環(huán)境下的路徑規(guī)劃

圖11 狹窄環(huán)境下的路徑規(guī)劃

圖12 凹形環(huán)境下的路徑規(guī)劃

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

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

圖13 改進前后路徑節(jié)點負載

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

4.2 運行沖突控制實驗

4.2.1 有效性驗證

基于最佳路徑規(guī)劃，構(gòu)建運行測試案例如表2 所示；作運行沖突控制實驗，實驗參數(shù)如表3 所示。

表2 運行測試案例

表3 實驗運行參數(shù)

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

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

圖14 測試案例運行路徑

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

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

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

4.2.2 控制性能分析

運行沖突的控制性能主要表現(xiàn)在延遲時間和啟停次數(shù)。延遲時間越短，系統(tǒng)運行效率越高；啟停次數(shù)越多，移動小車啟制動更頻繁，不僅耗能增大，還容易導(dǎo)致系統(tǒng)運行不穩(wěn)定。

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

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

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

結(jié)合圖16 和圖17，速度調(diào)控策略的控制性能有顯著優(yōu)越性，其主要原因是在路徑重規(guī)劃下，大多需增加轉(zhuǎn)向以避免沖突，而轉(zhuǎn)向?qū)⒑馁M較長運行時間和增加啟停次數(shù)；在停止等待時，重新啟動需增加延遲時間和啟停次數(shù)。

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

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

5 結(jié)論

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