面向地下停車場的尋車導航研究

周云城 楊東曉 田 歡

（1. 華設設計集團股份有限公司，江蘇 南京 210014；2. 江蘇大學，江蘇 鎮江 212013；3. 清華大學蘇州汽車研究院（相城），江蘇 蘇州 215134）

0 引言

隨著智能化設備的發展，出現了各式各樣的定位導航軟件，定位導航技術獲取方便，使用簡單，為人們的出行帶來了極大便利，智能化設備在大多數人的日常出行生活中已經變得不可或缺了[1]。然而當車輛駛入地下停車場等大面積的室內場所時，由于衛星信號受到建筑物的嚴重干擾，車輛通常難以接收到GPS/北斗信號進行定位，因此車輛已有的導航系統無法實現導航功能。尤其是當車輛位于大型的地下停車場時，由于停車場的空間較大，各區域場景相仿，標志物較少，不易分清方向，人們在尋找停車位以及尋車離場時往往會遇到一定困難。當停車場中的車流較多時，會在停車場內要安排一定的工作人員對車輛進行引導，但每個工作人員往往只負責某個固定區域，其視野有限且人員之間溝通不暢，停車場內的車流容易出現混亂的狀況甚至導致擁堵，車主尋車離場基本上只能依靠自己完成，用戶體驗較差[2]。這樣的車輛引導管理方式效率不高，停車位利用效率低，而且需要支出一定的人工費用，增加了停車場的運營成本。

1 數據處理與分析

該文對地下停車場的導航算法展開研究，與室內高精度定位技術組合在一起，可以在司機尋找車位以及尋車離場時為司機導航，減少了司機在尋車上消耗的時間，提升了車輛流通的效率，進而提高停車位的利用效率，在一定程度上可以幫助改善城市中“停車難”的狀況。在利用導航算法對停車場環境進行路徑規劃時，首先要對停車場的平面圖進行處理，對地圖的障礙物部分與道路部分進行區分，可以用黑色對障礙物部分進行標識，用白色對道路進行標識，如圖1、圖2 所示。

圖1 地下停車場平面圖

圖2 標識后的地下停車場地圖

在完成標識后，便成功地區分了地下停車場環境中的障礙物與道路，但是由于導航算法程序并不能直接對處理后的圖片進行運算處理，因此需要計算機對處理后的地圖進行讀取，并將其轉換為可以直接進行運算的數據，由于停車場是以圖片的形式進行環境輸入，并且用顏色對障礙物、道路進行區分，因此可以用圖片中各點的像素點灰度值作為存儲形式進行存儲。

程序載入地圖的圖片后，可以利用Python 常用的圖像處理庫Pillow 按照像素讀取地圖中該像素點的灰度值，并按順序將其存儲在1 個二維數組中，這樣就成功地將地圖數據以二維數組的形式存儲下來，并且二維數組中某點的序號即代表該像素點的像素坐標。其中灰度值為0（黑色）的部分代表障礙物，灰度值為255（白色）的部分代表道路。

由于圖片中并非任意點均滿足白色部分灰度值為255、黑色部分灰度值為0 的條件，因此，灰度值可能會有細微的變動，為了明確地對障礙物、道路進行區分，可以進一步地對二維數組進行簡化，對數組進行二值化處理，將數組中灰度值小于127 的部分標記為“#”，代表道路；將灰度值大于127 的部分標記為“.”，代表障礙物。

2 基于PRM 的導航算法

2.1 PRM 算法基本原理

PRM（Probabilistic Road Map）算法的基本思路是在地圖中利用隨機采樣節點構造概率路徑圖[3]，在構造出的路徑圖中使用搜索算法進行檢索，從而搜索出最短路徑，PRM 算法有2 個基本階段，即學習階段和查詢階段。

2.1.1 學習階段

學習階段的主要任務在于構造出用于路徑檢索的概率路徑圖[4]。首先要對地圖進行處理，用黑色對地圖中的障礙物部分進行標識，用白色對道路部分進行標識。完成對地圖的處理后，在地圖上隨機采樣N個節點。完成隨機采樣后，由于采樣的節點可能會位于障礙物內部，因此需要對各采樣點進行檢測，剔除其中與障礙物重疊的點。

當完成節點的碰撞檢測后，用線段將剩余的節點連在一起，連線時需要保證各節點的連線不能與障礙物重疊，為了節省計算量，縮短路徑檢索時間，各節點只連接自己鄰域范圍內的點，不太遠的點進行連接。當所有節點均完成連線后即成功完成了概率路徑圖的構造，如圖3 所示。

圖3 概率路徑圖

2.1.2 查詢階段

查詢階段的主要任務是在學習階段完成的概率路徑圖中檢索出從起始位置到達目標位置的最優路徑[5]，其具體步驟如下：1）將起點與終點分別與其在概率路徑圖中與之距離最短的點進行連接，從而將2 個點添加至學習階段構造出的路徑圖中。2）利用Dijkstra 搜索算法在完成連接的路徑圖中進行檢索，選用距離作為優化指標，查詢從起始位置到達目標位置的最短路徑，如圖4 所示。

圖4 隨機采樣點取200 個規劃出的路徑

2.2 PRM 算法優化

由于在地下停車場環境中障礙物較多，因此在隨機采樣時大部分位于障礙物內部的采樣節點都會被舍去，保留下的節點也會出現與障礙物距離過近的情況，這樣可能會導致規劃出的路徑與障礙物距離過短，即出現“貼邊”現象，并且由于各節點位置隨機，各節點的連線通常與道路中心線不平行，路徑規劃效果較差，如果增加采樣節點，則會導致運算時間大幅增長，而路徑規劃效果并不會出現明顯提升，考慮到停車場中大部分道路結構較為簡單，很少會有彎曲道路，因此可以將各路口中心點作為采樣節點集，路徑規劃效果會有大幅提升，同時解算時間也會有所縮短。可以對優化前后的算法進行簡單的對比實驗，實驗中將起點的像素坐標設為（305，380），終點的像素坐標設為（615，990），如圖5 所示。

圖5 優化PRM 算法規劃出的路徑

由表1 可以看出原始的PRM 算法在增加采樣點數量及鄰域距離后，雖然路徑規劃效果有所提升，但是路徑解算耗費的時間大幅增長。這主要是因為增加采樣點及鄰域距離后，節點的連線數量會呈幾何倍數增長，其中大部分為無效連線，算法檢測連線是否穿越障礙物時耗費了大量資源。而采樣點數量較少時，路徑規劃效果很差。需要進行大量實驗，讓采樣點數量、鄰域范圍處于一個適中的區間，使規劃效果與耗費時間之間達到一個合理的平衡。優化的PRM 算法利用檢索出的節點，避免了對大量資源進行搜索的工作，在大幅節省解算時間的同時，取得了最好的路徑規劃效果。

表1 優化前后算法數據對比

同時考慮到地下停車場道路較為狹窄，車輛在道路上難以掉頭，在初始時，車輛只能沿著車頭方向向前行駛，因此需要對車輛的初始行駛方向進行限制，可以在學習階段對路徑圖的生成過程進行修改，在節點集中對節點進行判斷，刪去與車輛位于同一道路上且處在車輛后方的節點，在構造路徑圖時，不會生成與車頭方向相悖的路徑。這樣在后續的查詢階段中便不會搜索出與車頭朝向相悖的路徑，從而確定路徑初始方向。

2.3 導航信息輸出

當駕駛者利用導航軟件進行導航時，軟件在規劃出路徑的同時會結合車輛的定位對駕駛者進行導航信息提示。在實際應用中，導航信息中通常包括2 個信息：1）距離信息。車輛與下一路口間的距離。2） 方向信息。車輛在下一路口位置上應進行何種操作，例如直行、左轉或是右轉。

在進行坐標變換之后可以通過查詢車輛定位以及下一路口位置簡單算出導航信息所需要的距離，坐標變換時為了保證精度，路口中心點的坐標變換采用像素坐標與世界坐標一一對應的方式，而起點、終點的坐標則通過計算得出。方向信息的分析則略微復雜些，其本質在于折線段的拐向判斷，判斷的基本方法是求向量積，其基本原理如圖6 所示。

在圖6 所示的簡單折線段中，要判斷A點處的拐向，可以分別將A點兩側的線段視作向量P、Q，設P向量為（x1，y1），Q向量為（x2，y2），將P、Q的向量積記作I。

圖6 簡單折線段拐向判斷

由向量積的性質可知，當I小于0 時，P在Q的逆時針方向，說明在A點處折線段向右拐，反之，當I大于0時，P位于Q的順時針方向，A點處折線段拐向朝左，I等于0 時，P與Q同向，折線段變為直線段。

利用上述基本原理可對停車場地圖中規劃路徑的方向信息進行分析，首先查詢規劃路徑中經過的路口中心節點，將起點、路口節點以及終點按順序連接在一起，將每條連線視作向量，并用像素坐標表示這些向量，求出任意相鄰2 個向量的向量積并與0 進行比較，就可以得出路徑在各路口的方向信息。

3 總結

在停車位供不應求的問題短時間內難以得到解決的大背景下，提高城市中已有停車位的利用效率是緩解“停車難”的一種有效手段，然而現有停車場的空間較大，且各區域場景相仿不易分清方向，從而在尋找停車位以及尋車離場時會存在一些困難。為此，該文在總結已有理論及技術的基礎上，對面向地下停車場的路徑規劃問題進行研究，成功對地下停車場環境進行路徑規劃并給出導航信息，在提高停車位利用效率的同時，也為駕駛者在停車場中的尋找車位、尋車離場帶來了便利。