停車場車位自動化排布設計及優化

許哲陽，張易誠，沈 煒

（浙江理工大學 計算機科學與技術學院，杭州 310018）

0 引言

目前大多數關于車位排布問題的研究都是將其看成一個帶有約束條件的單一尺寸矩形排樣問題，大都采用啟發式算法，如：模擬退火算法、動態規劃、遺傳算法、進化策略等進行優化［1］。Huang 等［2］設計了一套基于模擬退火算法的針對矩形區域內車位排布問題的通用算法；利潤等［3］提出使用兩段動態規劃進行車道布局的算法；徐涵喆等人［4］提出了使用遺傳算法來解決地下車庫外圈車位排布的問題；但這些研究都僅考慮到了車位數最優的情況。為了加強便捷度的設計，余光鑫等人［5］采用進化策略，同時提出增加一個便捷度的評價體系來設計停車場。雖然得到了較好的實驗效果，但是進化策略屬于啟發式算法，通常依靠猜測和搜索來解決問題，數據利用率不高。如進化策略僅僅將當前生成的數據用作一次策略更新，待策略更新結束后就將當前生成的數據丟棄，數據利用率十分低下［6］。采用深度強化學習方法，如DQN（Deep Q-Network），使用經驗回放，將每次從環境中采樣得到的四元組數據（狀態、動作、獎勵、下一狀態）存儲到回放緩沖區中，訓練網絡的時候再從回放緩沖區中隨機采樣若干數據來進行訓練，這樣不僅可以使樣本滿足獨立假設，還可以提高數據利用率。此外，隨著大型綜合體對客戶體驗越來越重視，停車場的設計目標越來越傾向于便捷度優先而兼顧停車位數量，這樣的設計方式會更加依賴經驗數據的使用，所以深度強化學習方法相較于啟發式算法更適合去解決車位排布這種對數據利用率有要求的問題，但目前可供參考的基于深度強化學習方法來解決車位排布問題的文獻較少。

使用深度強化學習方法仍然有其局限性，隨著環境復雜性的增加，DQN 中智能體需要大量的時間和數據來學習［7］。為此，Yinlong Yuan 等［8］提出的一種新的多步提取方法，是針對深度強化學習做出的一個改進算法，與傳統的多步Q-learning 不同，多步提取方法使用了一種新的回報函數，即n個標準返回函數的平均值。在選擇當前狀態動作時，新的回報函數改變了未來獎勵的折扣，同時減少了即時獎勵的影響，多步方法更適合結合經驗重放來提高經典DRL（deep reinforcement learning）算法的性能。

本文嘗試基于優化后的深度強化學習方法，在車位排布的約束條件、初始化條件、獎勵設計、網絡結構、算法選擇等方面做出改進，以此來解決便捷度優先的車位自動化排布問題。

1 問題描述

1.1 問題定義

本文的車位自動化排布問題定義為：智能體在一個虛擬的車位場景中計算出一條最優的道路，這條道路可以讓停車場內道路便捷度最高，在此基礎上，車位數也要求盡可能多。

1.2 約束條件

停車場車位自動化排布的約束條件可以概括為以下3 點：

（1）智能體計算得出的道路不能超出虛擬環境所設定的邊界；

（2）道路與道路之間必須保證連通性，確保每條道路能到達除本身外任意一條道路；

（3）形成車位的空地必須滿足與道路相鄰的條件。

2 模型設計

2.1 網絡結構

網絡架構如圖1 所示，是有兩個隱藏層的全連接網絡，第一個隱藏層有128 個節點，第二個隱藏層有64 個節點。

圖2 最后n 步回報函數和Gt 在參數｛（γ，k）｝ 下的對比圖［8］Fig.2 In the last step，the comparison diagram of return function and Gt under ｛（γ，k）｝ parameter［8］

模型輸入包括3 部分：

（1）智能體和上下左右墻體之間的距離；

（2）以智能體為中心的5×5 范圍內的停車場狀態信息；

（3）當前智能體所前進的方向信息，初始時設置為向上。

輸出層則包含了智能體在當前位置可以選擇的4 個動作：

①當輸出為0 時，智能體策略為朝當前方向繼續前進；

②當輸出為1 時，智能體策略為在當前方向的基礎上左轉；

③當輸出為2 時，智能體策略為在當前方向的基礎上右轉；

④當輸出為3 時，智能體策略為后退。

2.2 深度強化學習算法選擇

本文使用深度強化學習中的DQN 算法來取代進化策略結合神經網絡的方法。采用進化策略和神經網絡結合的方法通常是不穩定的，甚至是發散的，而DQN 相比于進化策略結合神經網絡的方法優勢在于DQN 具有經驗回放的功能，通過將經驗數據et ＝（st，at，rt，st+1）存儲在DQN 的經驗重放內存D中，深度強化學習智能體可以記憶和重用過去的經驗，其中t是時間節點，在該時間節點下，st是狀態，at是智能體選擇的動作，st+1是t +1 時間節點的狀態，rt是從st過渡到st+1獲得的獎勵。在訓練過程中，任意兩個元組et1∈D和et2∈D之間的訓練數據弱相關。神經網絡的參數是通過隨機從D中均勻采樣小批量經驗來學習的，這有助于打破強相關更新，保證學習系統的穩定性［9］。同時用DQN 中損失函數對訓練過程進行改善，從而持續減少輸出值的較大偏差，公式（1）：

其中，θ是有限維權向量；Ε［·］是期望函數；s是當前環境的狀態；a是智能體選擇的動作；s＇是新的狀態；r是從當前狀態過渡到新狀態獲得的獎勵；U（·）是隨機抽樣函數；Q（·）是參數連續化函數。

用DQN 代替進化策略的方法不僅可以進一步提高訓練速度，而且可以顯著提高模型性能。

本文還使用了EnDQN 技術進一步優化DQN算法。與傳統的強化學習方法不同，EnDQN 引入了一個新的回報函數，定義公式（2）：

即新的回報函數是n個標準返回函數Gt，Gt+1，…，Gt+n-1的平均值。根據數學推導，新的回報函數可以分解為兩部分，分解后表示為公式（3）：

2.3 獎勵設計

在獎勵設計上，本文提出了一種高效的六車位算法，可以用極低的時間復雜度計算出虛擬地圖中便捷度最高的道路，完全取代了復雜便捷度計算方法，在時間效率上得到了質的提升。該方法具體描述如下：

當智能體經過的道路周邊有空地，且空地能滿足形成一個最便捷的六車位組如圖3 所示，即智能體所經過道路所圍成的空地剛好是一個六車位組，就給一個+6 的獎勵，本文給此獎勵乘上一個系數ω后加到總獎勵中。由于+6 的獎勵不方便對總獎勵進行車位數換算，因此ω設置為5／3，且在每一個訓練模型步數結束時，當前所得到的總獎勵會減去上一個訓練模型步數中記錄的總獎勵來得到一個獎勵差，用來及時提供每一個訓練模型步數的反饋，從而提高下一個訓練模型步數的效率。

圖3 六車位組Fig.3 Six parking lot group

獎勵差算法偽代碼如下：

由于EnDQN 算法更適合在負獎勵中進行訓練，所以每一個訓練模型步數結束后會給一個-1 的獎勵，盡可能讓800 個訓練模型步數結束后獎勵為負，可以增強負獎勵的影響。

3 實驗

3.1 仿真環境

本文使用用于自動化車位排布的環境carEnv，將地圖的網格數從10×10 和20×20 改成21×21，可以讓智能體計算出的車道完美貼合虛擬地圖邊緣，使最終效果更美觀，暫時忽略環境中的障礙物，完全把停車場當成一個空地，且用21×21 的網格展示出來。在這個環境中，存在一個智能體，為了提高樣本的多樣性，讓智能體在初始化時隨機選擇虛擬地圖邊緣的一個網格作為起始點，提升樣本隨機性，從而大幅節約隨機生成虛擬地圖的時間成本。開始訓練后，在每個時間步驟中，智能體有4 個可能的動作：0，1，2，3，分別表示為智能體以當前方向前進、向左轉、向右轉以及向后退，當時間步驟大于等于800 時退出。

本文的模型均在11th Gen Intel（R）Core（TM）i7-1165G7 ＠2.80 GHz 1.69 GHz 上進行訓練。

3.2 實驗驗證

在進化策略結合神經網絡實驗中，種群大小設置為50，σ為0.1，學習率設置為0.05，總代數為800代。平均獎勵基線圖如圖4 所示。

圖4 進化策略（ES）+神經網絡（NN）的平均獎勵基線圖Fig.4 Average reward baseline of evolutionary strategy（ES）+neural network（NN）

在DQN 算法和EnDQN 算法實驗中，學習率設置為0.000 1，經驗重放內存的大小是40 000元組。對內存進行采樣，以每一步更新網絡，批處理大小為64。每次目標網絡更新之間的步數是800。在多步學習中，n的值是一個敏感的超參數，本文只給出了n∈［1，2］的結果，n ＝1 表示DQN 算法，n ＝2 表示EnDQN 算法。

DQN、EnDQN 和進化策略結合神經網絡算法的實驗中得到的平均獎勵基線比較如圖5 所示。

圖5 DQN、EnDQN 和進化策略（ES）+神經網絡（NN）的平均獎勵基線比較圖Fig.5 Comparison chart of average reward baseline of DQN，EnDQN and evolutionary strategy（ES）+neural network（NN）

EnDQN 算法的平均獎勵會明顯優于進化策略和神經網絡的結合，同時在訓練超過500 輪后其基線顯著優于DQN 算法，這主要是因為進化策略本身就是一個數據利用率較差的方法，而作為經典深度強化學習算法之一的DQN 算法又過度依賴于經驗重放，在每個數據元組中，只考慮單個獎勵信號，這同樣導致其學習過程中存在數據利用率較低的問題，特別是當獎勵信號稀疏時。而EnDQN 方法使用了一個新的回報函數，改變了未來獎勵的折扣，在選擇當前狀態行為時不再強調當前獎勵是主要影響因素。因此在每次更新中，可以使用多步獎勵信號，使得所選擇的獎勵信號更加有效。但當參數n較大時，每個元組∈D內的數據相關性將變得更弱，EnDQN 算法的性能將被削弱，因此選擇一個合適的參數值是很重要的。

各方法每輪訓練的耗時、訓練過程中的最高獎勵值、利用訓練800 輪的模型進行推理所得到的空地格子數和車位數量見表1。

表1 算法對比表Tab.1 Comparison table of algorithm

從表1 中可以看出，在時間方面，同樣的獎勵設計下，EnDQN 算法的運行時間快于進化策略和神經網絡的結合，很大程度上減少工程上的時間消耗，尤其是在環境非常復雜的現實工程問題中；同時根據EnDQN 算法經驗來看，實驗效果理論上要比DQN的效果高出較多，但是在本文實驗的結果來看，效果只是有提升，并沒有特別大的改善。

EnDQN 在800 輪訓練中得到的道路空地效果如圖6 所示，預期可達到的效果如圖7 所示，不難看出圖6 與圖7 十分接近，可見本文使用的EnDQN 算法在地下車庫車位規劃問題上取得了較好的效果。

圖6 EnDQN 在800 輪訓練中得到的道路空地效果圖Fig.6 EnDQN's effect picture of road open space obtained in 800 rounds of training

圖7 EnDQN 在800 輪訓練中預期可達到的效果圖Fig.7 EnDQN's expected effect in 800 rounds of training

本文將EnDQN 在800 輪訓練中預期得到的效果圖轉換成真實場景如圖8 所示。

圖8 EnDQN 在800 輪訓練中預期得到的真實場景圖Fig.8 EnDQN's expected real scene renderings in 800 rounds of training

4 結束語

本文設計了一種新的停車場車位自動化排布模型，嘗試將一種新的多步學習方法EnDQN 應用于該模型中，并在carEnv 停車場仿真環境中評估了該方法的性能。實驗結果表明，該模型非常高效且EnDQN 大幅優于現有的進化策略和神經網絡結合的方法。在未來，計劃設計一種更合理的獎勵函數來進一步優化EnDQN 算法在停車場車位自動化排布設計上的性能。