基于改進A*算法的復雜停車場路徑規劃

邢孟陽，杜嘉豪，吳竟啟，束 磊，郭中陽

（1上海工程技術大學 機械與汽車工程學院，上海 201620；2江蘇超力電器有限公司，江蘇 鎮江 212321）

0 引 言

近年來，汽車保有量激增的同時，停車需求也急劇增長，為了滿足停車需要，許多停車場都采用多層建筑結構，且建筑內部都十分復雜。在多層地下停車場中，由于缺少光線和標志物，駕駛員在其內部較易丟失方向感，這給停車和尋車均帶來一定困難。為解決這個問題，研究學者做了大量的工作。李榮達等人采用圖像識別和處理的方法，首先車載相機采集車輛周圍環境圖像，然后對圖像進行透視處理，進而在不同灰度值下進行分割，提取出車位特征，最后通過霍夫變換提取出車位線，從而得到車位信息。該方法對于車載相機視覺范圍內的車位信息具有良好的判別能力，為駕駛員提供了有效駕駛輔助。王雪松等人設計了一種改進的新型遺傳算法，通過將相關領域知識融入到遺傳的過程中，在不影響路徑規劃效率的同時，利用優化算子對算法進行優化，該方法能夠有效提高利用遺傳算法改進的路徑規劃效率。趙江等人在A算法基礎上，引入了幾何方法進行優化，其主要過程為：首先提取路徑上所有的節點，然后刪除其中的冗余節點以及可替換的拐點，最終將起點、必要拐點、終點連接成為一條最優路徑，該方法有效縮短所規劃路徑的長度且減少了轉向次數。華洪等人針對傳統A算法局限于應用在靜態環境下的全局中，在求解路徑規劃問題時存在搜索效率低，路徑不平滑等問題進行了以下優化：對全局路徑節點進行優化，對冗余節點要按規則進行刪除，同時也可以按照規則新增必要節點，從而不僅使所規劃的路徑更加合理，而且還提高了搜索效率。Zhang等人提出一種結合Dijkstra和蟻群算法的融合算法，首先利用Dijkstra算法搜索效率高的特點，生成備選最優規劃路徑，然后利用蟻群算法具有信息反饋的優點，在備選路徑中篩選出最優路徑，該路徑即為全局最優規劃路徑，最后設計實驗方案，并通過數字仿真軟件進行仿真測試，驗證了該融合算法的優越性。

上述方法在解決特定問題時具有良好的表現，但也存在著不足，如文獻［1］中提到的方法，其搜索范圍局限于車輛周圍，不能夠實現全局搜索、全局規劃。文獻［2］中采用改進新型遺傳算法，但該算法中起關鍵作用的適應度函數的選取難度較大，選取不當容易導致局部收斂，無法達到全局最優，且該算法參數較多，難以控制。因此本文選擇對傳統A算法進行改進優化，改進后的A算法不僅在搜索效率方面比其它算法更具優勢，而且其所規劃的路徑對于駕駛員來說更加適宜，改進的算法控制簡單，適合規模化推廣應用。

1 A*算法原理

A算法是一種啟發式搜索算法。在狀態空間中，首先對每一個搜索的位置進行評估，得到最佳位置，然后從該位置再繼續進行搜索，直至到達目標位置。算法實現流程圖如圖1所示。

圖1 A*算法流程圖Fig.1 Flow chart of A*algorithm

研究可得計算公式如下：

其中，（）是從初始位置經由節點（即現在所處位置）到達目標位置的估計距離；（）表示從初始狀態到節點實際走過的距離；（）是從節點到目標位置的最佳路徑的估計距離。

從式（1）中可以看出若要獲取最佳路徑，（）的選取十分關鍵。假設（）代表節點到達目標點的距離，那么（）與（）之間的關系可以表示如下：

（1）（）（）。此時，可以得到全局最佳路徑，但這將導致搜索的節點過多，計算量過大，降低搜索效率。

（2）（）（）。即預估距離（）與實際距離（）相等，此時，算法的搜索過程將會嚴格按照最短距離進行搜索，這時拓展節點少，搜索效率相對較高，但路徑未必是最佳。

（3）（）（）。此時，算法所需要搜索的節點少，提高了搜索效率，但容易導致算法局部收斂，從而無法得到全局最優路徑規劃。

2 對A*算法的優化

2.1 引入權重系數

A算法是在Dijkstra算法和BFS算法基礎上，融合了二者的優點而成，由前文對算法的剖析可以了解，A算法中起最關鍵作用的是（），故當公式（1）中的（）值為0，此時A算法演變成為Dijkstra算法，而Dijkstra算法的優勢就在于能夠保證找到全局最短的路徑，但是卻需要遍歷所有節點，故而會降低搜索效率。當公式中的（）要比（）大得多時，A算法中就相當于只有（）在起作用，此刻A算法就演變成為BFS算法，這個時候算法將嚴格按照拓展節點最短距離進行搜索，如此就能夠保證得到一條相對最佳路徑，但未必是最優路徑。綜上，是在傳統A算法中引入權重系數（），原算法公式中的（）變成（）（），這里的（）≥1，由此得到改進后的算法用公式可表示為：

（）的引入可以為（）帶來更大的權重，通過合理設置（）的值，使算法能夠兼顧搜索效率和路徑長度。

2.2 拐角優化

拐角優化示意如圖2所示。圖2中，綠色和黃色小點分別代表起點和終點，由起點至終點有圖2中的1和2兩種最短路徑，對于算法而言，這2種路徑在長度上并無差別，但考慮現實場景，對比1和2兩種路徑就會發現，路徑1要比路徑2多一次轉向，而過多轉向會給駕駛人帶來不良體驗，因此在路徑規劃中應予以避免。

圖2 拐角優化示意圖Fig.2 Corner optimization schematic diagram

3 模型的構建

為了更加真實還原停車場環境，研究中基于數字仿真軟件測試平臺構建了一個如圖3所示的40×40的復雜停車場柵格地圖。圖3中，黑色的方格代表車位，考慮到在停車場中，車位的大小是基本一致的，故可用統一的變量來表示，停車場內部的道路是圍繞著車位進行規劃的，因此可以用車位間隙來表示道路。由于A算法是通過先計算初始位置與節點間的實際距離和節點到目標位置的估計距離，然后進行比較排序來實現拓展和路徑規劃的，因此就可以將每次拓展的代價設定為統一量，這樣在計算的時候能夠減小運算量，提高算法搜索效率。

4 仿真驗證

本次仿真實驗采用對比實驗的方法，基于數字仿真軟件測試平臺，在相同條件下對傳統A算法、改進A算法、Dijkstra算法、BFS算法進行對比實驗。仿真實驗結果如圖3～圖6所示。路徑規劃時間對比結果見表1，轉彎次數統計結果見表2。

圖3 傳統A*算法Fig.3 Traditional A*algorithm

圖4 改進A*算法Fig.4 Improved A*algorithm

圖5 Dijkstra算法Fig.5 Dijkstra algorithm

圖6 BFS算法Fig.6 BFS algorithm

表1 路徑規劃時間對比表Tab.1 Comparison of routine planning time s

表2 轉彎次數統計表Tab.2 Statistical table of turns

5 仿真結果分析

對比4種算法路徑規劃圖，分析仿真實驗結果可知，改進A算法的路徑和傳統A算法有明顯區別，主要在于路徑的平滑度，改進A算法要明顯優于傳統A算法，在路徑長度方面，兩者是相同的，這是由于初始位置和目標位置間的路徑是固定的，因此改進A算法和傳統A算法、以及BFS算法都搜索到了基于各自搜索規則所能達到的最短路徑，而Dijkstra算法所規劃的路徑和其它3種算法都不相同，這是由于Dijkstra算法采用邊緣拓展且向所有方向進行，拓展面積大，因此規劃了一條最短的路徑，但并不是最佳路徑。從表1可以看出，改進A算法在搜索速度方便要比傳統A算法和Dijkstra算法快，但比BFS算法要慢，究其原因分析可知，這是由于改進A算法要從全局考慮路徑所造成的。從表2可知，路徑規劃中拐彎次數最少的是改進A算法，7次拐彎已經是所能達到的極限，這說明本次研究對算法的拐角優化發揮了作用。從實驗結果分析，綜合考慮路徑平滑度、搜索時間、轉彎次數三項關鍵指標，改進A算法與其它3種算法相比具有良好的優越性。

6 結束語

本文針對復雜停車環境中停車、尋車困難問題展開深入研究，選擇對路徑規劃中比較成熟的A算法進行優化應用，傳統的A算法是靜態的規劃，拓展節點相對較多，搜索效率相對較低，其規劃出的路徑相比啟發式A算法而言存在不夠平滑，不夠人性化等缺點。因此本文通過引入權重系數，提高節點與目標點距離在算法中的權重來對算法進行改進。在實驗測試中，研究發現算法在路徑規劃中可能會在相同距離條件下規劃出多次轉向路徑，會給實際使用過程帶來不良體驗，因此通過在算法程序中加入拐角修正，使算法規劃出的路徑更加平滑，更加人性化，這些優化能夠給實際使用者帶來舒適的體驗。未來還需解決在路徑規劃中全局規劃、全局控制的問題，如需要將路徑規劃與車輛自主導航控制相結合，如此一來所規劃的路徑需要更加精細化，同時還要考慮到停車場內可能出現的會車、錯車、行人、擁堵等復雜狀況，及時引導車輛，避免危險發生。