緊致化智能停車系統(tǒng)的運(yùn)行沖突控制*

施玉璋 王正國

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

0 引言

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

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

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

1 系統(tǒng)描述

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

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

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

圖2 抓取機(jī)器人

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

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

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

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

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

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

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

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

2.1 環(huán)境建模

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

2.2 單移動小車運(yùn)行路徑

2.2.1 基礎(chǔ)A*算法

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

圖4 A 星算法流程圖

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

2.2.2 改進(jìn)的A*算法

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

1）實(shí)際意義上路徑效果更佳

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

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

2）搜索效率更高

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

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

2.2.3 路徑評價(jià)

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

3 運(yùn)行沖突分析及控制

3.1 運(yùn)行沖突類型

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

圖5 相向沖突示意圖

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

圖6 追及沖突示意圖

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

3.2 運(yùn)行沖突控制

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ī)則：沖突時(shí)的理論剩余行程時(shí)間越短優(yōu)先級越高；

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

3.2.2 預(yù)處理階段

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

1）時(shí)間窗初始化

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

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

①啟/制動時(shí)節(jié)點(diǎn)n1的時(shí)間窗為

②加速運(yùn)行時(shí)節(jié)點(diǎn)n1的時(shí)間窗為

③加速-勻速運(yùn)行時(shí)節(jié)點(diǎn)n1的時(shí)間窗為

④勻速運(yùn)行時(shí)節(jié)點(diǎn)n1的時(shí)間窗為

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

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

2）時(shí)間窗檢測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.3 實(shí)時(shí)處理階段

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

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

4 實(shí)驗(yàn)驗(yàn)證分析

4.1 路徑規(guī)劃實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

圖13 改進(jìn)前后路徑節(jié)點(diǎn)負(fù)載

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

4.2 運(yùn)行沖突控制實(shí)驗(yàn)

4.2.1 有效性驗(yàn)證

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

表2 運(yùn)行測試案例

表3 實(shí)驗(yàn)運(yùn)行參數(shù)

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

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

圖14 測試案例運(yùn)行路徑

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

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

圖15 沖突2 的時(shí)間窗示意圖

4.2.2 控制性能分析

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

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

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

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

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

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

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

5 結(jié)論

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