王瀟霆 張易誠(chéng) 沈煒

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

關(guān)鍵詞： 地下車庫(kù)； 車位排布； 獎(jiǎng)勵(lì)機(jī)制； 探索策略； 區(qū)域劃分

中圖分類號(hào)：TU248.3? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

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

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

1 模型建立

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

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

1.2 基于獎(jiǎng)勵(lì)機(jī)制的探索策略

1.2.1 獎(jiǎng)勵(lì)機(jī)制

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

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

⑴ 如果當(dāng)前位置已被探索過(guò)，獎(jiǎng)勵(lì)設(shè)為0。

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

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

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

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

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

[Rs=k=1Trk]? ⑴

1.2.2 探索策略

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

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

⑵ 計(jì)算[Sn]向前后左右四個(gè)方向行進(jìn)能獲得的獎(jiǎng)勵(lì)[ru]，[rd]，[rl]，[rr]。

⑶ 選擇獎(jiǎng)勵(lì)最大的方向?yàn)閇Sn]行進(jìn)方向，當(dāng)獎(jiǎng)勵(lì)相同時(shí)優(yōu)先級(jí)關(guān)系為[ru>rl=rr>rd]。

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

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

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

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

1.3.1 區(qū)域劃分算法

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

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

1.3.2 車位排布策略

區(qū)域集合[Arec]包括了邊界區(qū)域[Abor]（圖4黑色區(qū)域）和非邊界區(qū)域[Ain]（圖4白色區(qū)域）。對(duì)于[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]。）和過(guò)道模塊集合[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ū)域的短邊開(kāi)始掃描劃分[P]和[R]，得到的[P]模塊能夠排放更多的車位。

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

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

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

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

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

2 實(shí)驗(yàn)驗(yàn)證

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

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

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

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

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

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

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

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

[7] 楊羊.基于強(qiáng)化學(xué)習(xí)的持續(xù)集成測(cè)試用例優(yōu)先排序獎(jiǎng)勵(lì)機(jī)制研究[D].北京：北京化工大學(xué)，2022.

[8] 何柳柳，楊羊，李征，等.面向持續(xù)集成測(cè)試優(yōu)化的強(qiáng)化學(xué)習(xí)獎(jiǎng)勵(lì)機(jī)制[J].軟件學(xué)報(bào)，2019，30（5）：1438-1449.

[9] 余光鑫.基于強(qiáng)化學(xué)習(xí)的地下車庫(kù)生成式設(shè)計(jì)研究[D].廣東：華南理工大學(xué)，2020.