王瀟霆 張易誠 沈煒

摘? 要： 在地下車庫排布車位，往往受到車庫輪廓、障礙物和連通性等條件約束，本文設(shè)計并實現(xiàn)了一種基于探索策略和區(qū)域劃分的車位排布方案。探索策略借鑒了強化學習的思想，通過設(shè)置獎勵機制使智能體在地下車庫環(huán)境中進行主路的鋪設(shè)；區(qū)域劃分算法可以在保證不堵塞車道情況下得到盡可能多的車位數(shù)量。本文算法能夠在短時間內(nèi)獲得車位排布結(jié)果，幫助設(shè)計師減輕工作量，提高項目收益。

關(guān)鍵詞： 地下車庫； 車位排布； 獎勵機制； 探索策略； 區(qū)域劃分

中圖分類號：TU248.3? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）09-54-05

Research on parking arrangement algorithm for underground

garage based on reinforcement learning

Wang Xiaoting， Zhang Yicheng， Shen Wei

（School of Computer Science and Technology （School of Artificial Intelligence）， Zhejiang Sci-Tech University， Hangzhou， Zhejiang 310018， China）

Abstract： In underground garages， parking spaces are often constrained by garage contours， obstacles， connectivity and other conditions. In this paper， a parking arrangement scheme based on exploration strategy and regional division is designed and implemented. The exploration strategy draws on the idea of reinforcement learning， and makes the agent lay the main road in the underground garage environment by setting up a reward mechanism. The regional division algorithm can get as many parking spaces as possible without blocking the lanes. The proposed algorithm can obtain the results of parking arrangement in a short time， which can help designers reduce workload and improve project income.

Key words： underground garage; parking space arrangement; reward mechanism; exploration strategy; regional division

0 引言

隨著城市化的進程不斷加快，城市的土地資源緊缺問題日益嚴重[1]。怎樣才能充分利用停車資源、增加經(jīng)濟效應(yīng)[2]成為了城市發(fā)展的一個重要問題。目前已有許多專家學者對如何在地下車庫中獲得更多的車位問題進行了深入探究[3]。對于車庫輪廓為不規(guī)則形狀的停車場，徐涵喆等[4]提出了一種基于遺傳算法的外圈車位排布啟發(fā)式算法解決外圈車位排布問題；黃逸彬等[5]提出了基于圖形分割的城市地下車庫車位排布優(yōu)化方法處理復(fù)雜輪廓內(nèi)部整排車位的排車角度問題；對于主樓空隙內(nèi)的車位排布方案，馮嘉宇等[6]提出了一種基于分離障礙物的地下車庫車位排布算法。但是目前這些研究在障礙物數(shù)量多、分布不規(guī)律情況下，想要始終保證車道之間的連通性會非常困難。

因此，為了在諸多約束條件下最大程度地利用地下停車場資源，使車位數(shù)量最大化，本文提出一種基于探索策略和區(qū)域劃分算法的模型。該模型參考了強化學習的思想[7-9]，通過設(shè)置的獎勵機制使智能體在地下車庫環(huán)境中進行主路的鋪設(shè)，接著運用區(qū)域劃分算法劃分區(qū)域并排布車位。本文模型能適用于任意復(fù)雜的地下車庫圖，并且能有效地處理車道連通性問題，降低無效車位存在的概率。算法最終能夠得出所有車位的坐標并可視化呈現(xiàn)，輔助人工設(shè)計。

1 模型建立

1.1 車庫環(huán)境網(wǎng)格化處理

為了清晰地描述并記錄車庫中每個位置的狀態(tài)，本文對車庫環(huán)境進行了網(wǎng)格化處理。該方法使用網(wǎng)格記錄位置狀態(tài)，這樣狀態(tài)的更新操作就變得十分容易。網(wǎng)格化處理步驟如下：首先求出地下車庫外輪廓最小矩形閉包，之后對閉包進行切割，根據(jù)切割精度確定狀態(tài)矩陣[Sstate]的行和列。當網(wǎng)格處于有障礙物時，其值設(shè)為-1；當處于邊界外時，其值設(shè)為-2；當處于空曠區(qū)域，其值設(shè)為0；當網(wǎng)格已被鋪設(shè)為過道時，其值設(shè)為1。環(huán)境網(wǎng)格化處理初始結(jié)果如圖1所示。

1.2 基于獎勵機制的探索策略

1.2.1 獎勵機制

為了引導(dǎo)智能體在環(huán)境中進行有效的探索，獎勵的設(shè)置會非常關(guān)鍵，合理的獎勵機制能使智能體在探索中獲得的獎勵最大化。地下車庫中有許多約束條件會影響最終的車位排列結(jié)果，把這些條件進行網(wǎng)格化處理后得到集合[Zw]，記[Zw=A，B，c，d，E]，其中[A]為車庫邊界的網(wǎng)格集合，記[A=a1，a2，…，an]，[B]為車庫環(huán)境內(nèi)障礙物最小閉包的網(wǎng)格集合，記[B=b1，b2，…，bn]，[c]為車位寬度所占網(wǎng)格數(shù)量，[d]為車位長度所占網(wǎng)格數(shù)量，[E]為車庫環(huán)境內(nèi)相交道路的網(wǎng)格集合，記[E=e1，e2，…，en]。約束條件之間關(guān)系簡單描述為：①[B]和[E]必須存在于[A]的內(nèi)部；②[B]和[E]在車庫環(huán)境內(nèi)始終不存在交集。

當智能體進行過道鋪設(shè)時，在[Sstate]中的位置記為[Sn]，考慮到[Zw]和排列過程中的車位數(shù)量問題，最理想的情況為過道兩側(cè)都排上車位，所以[Sn]距離[A]和[B]為[d]時最佳。因此獎勵的設(shè)置如下：

⑴ 如果當前位置已被探索過，獎勵設(shè)為0。

⑵ 當智能體選擇某一方向進行移動時，[Sn]的其中一側(cè)與障礙物或邊界距離為一個車位長度，即中間剛好能排豎向車位，得到+200獎勵。

⑶ 當[Sn]與[A]、[B]處于圖2（a）情況時，由于繼續(xù)前進能到達⑵中的理想位置，所以在此位置關(guān)系下設(shè)置+50獎勵來鼓勵走直線。

⑷ 由于基于獎勵機制的探索策略主要實現(xiàn)的是在地下車庫中沿著障礙物或邊界進行主路鋪設(shè)，所以當智能體的當前位置離障礙物或邊界的距離過遠時，智能體就脫離了主路鋪設(shè)的路線，可能會導(dǎo)致過多的車庫面積未被利用，這種情況下設(shè)置-50獎勵作為懲罰。

⑸ 當兩條平行車道的位置關(guān)系處于圖2（b）時，過道之間距離過窄，至多只能排橫向車位。這種情況會造成大量面積浪費，所以給予-50獎勵。

在車庫環(huán)境中獲得的累計獎勵[Rs]公式如下（其中[T]為智能體在環(huán)境中所行進最大步數(shù)，[rk]為智能體第[k]步所獲獎勵大小。）：

[Rs=k=1Trk]? ⑴

1.2.2 探索策略

本文通過基于獎勵機制的探索策略來實現(xiàn)地下車庫的主路劃分，并初步解決區(qū)域間存在的車道連通性問題。智能體根據(jù)上文所設(shè)的獎勵在環(huán)境中進行探索，要使得到的獎勵最大化，策略至關(guān)重要。因此策略設(shè)置如下：

⑴ 設(shè)置多起點的探索策略。設(shè)定每個起點的探索步數(shù)，解決探索不全面的問題。

⑵ 計算[Sn]向前后左右四個方向行進能獲得的獎勵[ru]，[rd]，[rl]，[rr]。

⑶ 選擇獎勵最大的方向為[Sn]行進方向，當獎勵相同時優(yōu)先級關(guān)系為[ru>rl=rr>rd]。

把策略函數(shù)記為[Qs'n，a]，其表示執(zhí)行動作[a]后從狀態(tài)[Sn]轉(zhuǎn)移到[S’n]獲得的獎勵大小，所以下一步的動作選擇如公式⑵所示。

[a'=GargmaxQs'n，a]? ⑵

[argmaxQs'n，a]為下一個狀態(tài)[S’n]中所有可執(zhí)行動作[a]對應(yīng)的最大獎勵值。[G]函數(shù)實現(xiàn)了獎勵與對應(yīng)動作之間的轉(zhuǎn)換。得到的探索結(jié)果如圖3所示。

1.3 區(qū)域劃分算法及其車位排布策略

1.3.1 區(qū)域劃分算法

[Sn]在對主路進行鋪設(shè)的過程中，狀態(tài)矩陣[Sstate]中空地位置不斷地在進行[0→1]的更新，主路鋪設(shè)完畢后得到了最終的[Sstate]矩陣，其中值為0的位置為空地，表示可以排布車位。本小節(jié)討論如何對空地進行區(qū)域的劃分，使得區(qū)域內(nèi)排布的車位達到盡可能最優(yōu)的情況。

區(qū)域劃分問題實際上也可轉(zhuǎn)換為在狀態(tài)矩陣中求最大矩形問題，矩形劃分越大，內(nèi)部排列的車位也就更多。算法簡單描述為首先遍歷[Sstate]中所有的位置，開始找連續(xù)值為0的區(qū)域，即最大矩形區(qū)域，隨后給符合條件的區(qū)域相應(yīng)位置更新為-3，表示已經(jīng)遍歷過。以此類推，重復(fù)上述步驟，直到新的區(qū)域已不滿足條件后停止遍歷，最后得到了區(qū)域集合[Arec=A1，A2，A3，…，An]，區(qū)域劃分結(jié)果如圖4所示。

1.3.2 車位排布策略

區(qū)域集合[Arec]包括了邊界區(qū)域[Abor]（圖4黑色區(qū)域）和非邊界區(qū)域[Ain]（圖4白色區(qū)域）。對于[Ain]區(qū)域，可以把它分為車位模塊集合[P]（種類：①豎車位模塊集合[P1]，記[P1=P（1）1，P（2）1，…，P（n）1]；②橫車位模塊集合[P2]，記[P2=P（1）2，P（2）2，…，P（n）2]。）和過道模塊集合[R]，記[R=R1，R2，…，Rn]。模塊之間關(guān)系滿足：

[P?Ain，R?Ain，P1∈P，P2∈P] ⑶

[P（n）1∈P1，P（n）2∈P2，Rn∈R] ⑷

[?P（n）1∩?Rn=?，?P（n）2∩?Rn=?，?P（n）1∩?P（n）2=?] ⑸

車位的排布策略如下：

⑴ 沿著區(qū)域的短邊開始掃描劃分[P]和[R]，得到的[P]模塊能夠排放更多的車位。

⑵ 遵循區(qū)域內(nèi)每劃分兩條[P]，劃一條[R]的規(guī)則，使在保證連通性的情況下[P]模塊數(shù)量盡可能多。

⑶ 車位模塊選擇優(yōu)先級為[P1]>[P2]，當[P2]模塊無法放置時則劃分結(jié)束。

⑷ 得到劃分后所有的[P]模塊集合，根據(jù)每條[P]模塊的頂點坐標從左至右開始排布車位。

[Ain]區(qū)域劃分及車位排列如圖5所示。

由于經(jīng)過區(qū)域劃分得到的矩形與真實的地下車庫輪廓間存在空隙，這會導(dǎo)致過多的面積被浪費。所以對于邊界區(qū)域的處理，參考了徐涵喆等[4]提出的外圈車位排布啟發(fā)式算法，該文章對邊界區(qū)域的車位模塊定義了水平式和垂直式兩種類型。為了增加邊界車位的數(shù)量，本文又提出了一種基于水平式與垂直式的組合類型模塊排列方法來解決外圈車位排布問題。該方法實際步驟如下。①對外圈每條邊使用垂直式模塊。②在垂直式模塊內(nèi)排布兩種類型的車位（a.水平式車位，b.垂直式車位）。③如圖6（c）所示，兩種車位類型排布優(yōu)先級為b>a，當出現(xiàn)b與障礙物發(fā)生碰撞或道路堵塞情況時，即道路R1與障礙物有重疊，會進行b[→]a的替換。④每條邊遍歷完畢后，得到外圈所有車位坐標。

2 實驗驗證

實驗使用了七張不同的標準CAD工程圖紙對本文模型進行驗證和分析，圖紙包括了用地紅線、主樓、坡道等約束條件。車位的長度設(shè)置為6米，寬度2.5米，道路寬度設(shè)置為6米，承重柱寬度為0.5米，地下車庫網(wǎng)格化的分割精度設(shè)為0.5米。實驗環(huán)境采用4核、3.40GHZ處理器、內(nèi)存為16GB的計算機，基于Python3.8編程環(huán)境，通過Pyautocad庫連接Autocad軟件并讀取其中的CAD圖紙屬性，最后使用Matplotlib庫對圖紙屬性和算法結(jié)果進行可視化分析。

為驗證算法的有效性，對比了馮嘉宇等[6]提出的基于分離障礙物的地下車庫車位排布算法（記A算法）和人工排布的車位數(shù)量。結(jié)果如表1所示。

編號1～7使用了和A算法相同的CAD圖紙，從實驗結(jié)果看，本文算法的車位數(shù)量和運行時間都有明顯提升。結(jié)合表1、圖7和圖8可發(fā)現(xiàn)：①本文算法外圈使用了組合車位模塊后，車位數(shù)量明顯增多。②遺傳算法具有不穩(wěn)定性，會陷入局部最優(yōu)解，有收斂速度慢等問題，而本文算法效率比較高且穩(wěn)定，算法花費的時間大幅度降低。③通過實驗發(fā)現(xiàn)對于復(fù)雜的車庫結(jié)構(gòu)如圖紙6，使用A算法中的像素切割方法劃分車位模塊，會存在較嚴重的連通性問題，部分車位會因為道路堵塞而被定義為無效車位。而本文算法為了盡可能的減少無效車位的個數(shù)，首先會使用探索策略劃分出了主路，初步解決了車道間的連通性問題。而后使用區(qū)域劃分算法，判斷區(qū)域模塊之間是否相鄰，如果為相鄰模塊，則再細分車道。如圖9所示，本文算法對于處理復(fù)雜的車庫結(jié)構(gòu)也會得到比較理想的效果。（注：處理閉包內(nèi)的主樓障礙物空隙間的車位排布問題，主要參考了馮嘉宇等[6]提出的基于分離障礙物的地下車庫車位排布算法文章。）

3 結(jié)束語

本文對地下車庫的車位排布問題建立如下算法模型：使用基于獎勵機制的探索策略和區(qū)域劃分算法對地下車庫進行車位模塊的劃分，隨后根據(jù)車位排布策略在車位模塊內(nèi)排布車位，得到最終車位排布結(jié)果。在CAD工程圖紙的約束條件下使用該算法，利用Matplotlib庫對算法結(jié)果進行了可視化，得出了如下結(jié)論：①經(jīng)過本文模型的處理，可以保證因連通性問題而導(dǎo)致的無效車位盡可能少。②對外圈模塊使用本文提出的組合類型車位模塊，在車位數(shù)量上會優(yōu)于徐涵喆等[4]提出的水平式或者垂直式車位模塊，從而進一步提高了項目的收益。③馮嘉宇等[6]提出觀點中，由于遺傳算法具有不穩(wěn)定性、收斂速度慢等問題，所以在時間上開銷比較大，但使用本文模型可以解決該類問題，在使用相同圖紙情況下，所用時間能減少1/2左右。

參考文獻（References）：

[1] 王欣.地下車庫設(shè)計的合理性及經(jīng)濟性分析[J].中國建筑裝飾裝修，2022（17）：147-149.

[2] 劉帥，牛家興，曾麗雯，等.地下車庫柱網(wǎng)及結(jié)構(gòu)選型綜合經(jīng)濟技術(shù)分析[J].工程建設(shè)與設(shè)計，2021（12）：4-6.

[3] 谷錦彪.基于駕駛?cè)诵袨樘匦缘耐＼囄灰?guī)劃方法研究[D].安徽：合肥工業(yè)大學，2017.

[4] 徐涵喆，黃逸彬，楊赫，等.基于規(guī)則的城市地下車庫外圈車位排布啟發(fā)式算法[J].北京郵電大學學報，2019，42（4）：102-108.

[5] 黃逸彬，楊赫，周鐘秉，等.基于圖形分割的城市地下車庫車位排布優(yōu)化方法[J].北京郵電大學學報，2020，43（4）：7-14.

[6] 馮嘉宇，王瀟霆，沈煒.基于分離障礙物的地下車庫車位排布算法[J].智能計算機與應(yīng)用，2023，13（1）：25-30.

[7] 楊羊.基于強化學習的持續(xù)集成測試用例優(yōu)先排序獎勵機制研究[D].北京：北京化工大學，2022.

[8] 何柳柳，楊羊，李征，等.面向持續(xù)集成測試優(yōu)化的強化學習獎勵機制[J].軟件學報，2019，30（5）：1438-1449.

[9] 余光鑫.基于強化學習的地下車庫生成式設(shè)計研究[D].廣東：華南理工大學，2020.