關(guān)于室內(nèi)停車場(chǎng)的路徑規(guī)劃算法與導(dǎo)航

趙柯柯 韓雨瀟 王曉瑩 孟凱

摘要：該研究的目的是確保在一個(gè)確定的停車場(chǎng)內(nèi)，在任何一個(gè)可行道路上指定一個(gè)起點(diǎn)（人），指定一個(gè)終點(diǎn)（車），通過我們的路徑規(guī)劃算法，就能找到一條從該起點(diǎn)到終點(diǎn)的可行的通路。該算法以坐標(biāo)集合的形式傳遞數(shù)據(jù)，結(jié)果將在我們自主開發(fā)的app上顯示出來。該研究為汽車用戶提供了便捷的使用平臺(tái)，具有一定的實(shí)際應(yīng)用價(jià)值。

關(guān)鍵詞：停車場(chǎng)；路徑規(guī)劃算法；app

中圖分類號(hào)：TP399 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）25-0218-02

近年來，室外定位和基于位置的服務(wù)已經(jīng)成熟，基于GPS和地圖的位置服務(wù)被廣泛應(yīng)用，并成為各種移動(dòng)設(shè)備被使用最多的應(yīng)用之一。但對(duì)于室內(nèi)環(huán)境，GPS信號(hào)就顯得極其微弱甚至無影無蹤。在室外定位技術(shù)已經(jīng)相當(dāng)成熟的條件下，卻無法解決室內(nèi)的這一問題，而現(xiàn)在的室內(nèi)定位技術(shù)遠(yuǎn)遠(yuǎn)不夠完善。隨著人民的生活水平的提高，各種機(jī)動(dòng)車數(shù)量的迅猛增長(zhǎng)，現(xiàn)今在商場(chǎng)、購物中心等大型停車場(chǎng)，停車難和找車難是一般車主十分頭疼的兩個(gè)問題。我們進(jìn)行的《基于Wifi室內(nèi)定位技術(shù)的停車場(chǎng)應(yīng)用》項(xiàng)目就是為了最大可能的滿足大眾這一需求。

人人都可以在搭建過Wifi定位系統(tǒng)的地下停車場(chǎng)，短時(shí)間內(nèi)找到一個(gè)地下停車場(chǎng)的空停車位，并精確記錄自己的車位所在，從而引導(dǎo)用戶返回時(shí)快速找到自己的車，省去在迷宮一樣的地下停車場(chǎng)停車和找車的煩惱。該系統(tǒng)主要解決用戶對(duì)室內(nèi)定位精度，覆蓋范圍，可靠性，功耗和響應(yīng)時(shí)間五個(gè)方面的需求，主要應(yīng)用場(chǎng)景是大型商場(chǎng)的地下停車場(chǎng)。

該項(xiàng)目中有至關(guān)重要的一步，即在已知車和人的位置的情況下，怎樣進(jìn)行路徑的規(guī)劃，尋找可行路徑，以更大程度的節(jié)約時(shí)間。在閱讀大量文獻(xiàn)和進(jìn)行了許多次實(shí)驗(yàn)的情況下，我們?cè)O(shè)計(jì)了一種相對(duì)簡(jiǎn)單又實(shí)用的算法。本文模擬了幾組數(shù)據(jù)，意在說明該算法的正確性和可執(zhí)行性。數(shù)據(jù)將以坐標(biāo)集合的形式給出，規(guī)劃出可行路徑，并將計(jì)算出來的路徑在我們?cè)O(shè)計(jì)的app上顯示出來。

1 算法原理

先選取地圖上的關(guān)鍵點(diǎn)，一切都圍繞關(guān)鍵點(diǎn)來實(shí)施。將每條橫主干道以及縱主干道的所有的交匯點(diǎn)（即拐彎點(diǎn)）作為關(guān)鍵點(diǎn)。分析得知所有的可行點(diǎn)都至少在橫主干道或者縱主干道上，甚至在橫主干道和縱主干道的交匯點(diǎn)即關(guān)鍵點(diǎn)上，所以第一步要將起點(diǎn)以及終點(diǎn)移動(dòng)到離之最近的關(guān)鍵點(diǎn)上，如果已經(jīng)在關(guān)鍵點(diǎn)上則不用移動(dòng)，這樣一來我們的起點(diǎn)和終點(diǎn)就都位于關(guān)鍵點(diǎn)上了。第二步是判斷這兩個(gè)關(guān)鍵點(diǎn)的相對(duì)位置關(guān)系，然后找到他們之間的中間關(guān)鍵點(diǎn)。最后將起點(diǎn)、終點(diǎn)和中間的關(guān)鍵點(diǎn)這幾個(gè)點(diǎn)連接起來，即找到了可行的通路。

2 算法主要函數(shù)解釋

路線最終以坐標(biāo)集合的形式給出。該算法用結(jié)構(gòu)體來表示坐標(biāo)，采用棧來存儲(chǔ)路線的坐標(biāo)集合，并在路徑選擇時(shí)選擇總路徑總長(zhǎng)度最短的坐標(biāo)集合。首先需判斷起點(diǎn)和終點(diǎn)位置的橫、縱坐標(biāo)哪一個(gè)在干路上，再選擇離起點(diǎn)最近的兩個(gè)關(guān)鍵點(diǎn)以及離終點(diǎn)最近的兩個(gè)關(guān)鍵點(diǎn)，然后用一個(gè)結(jié)構(gòu)體來表示這2x2四條路線的長(zhǎng)度及坐標(biāo)。比較這四條路徑的長(zhǎng)度，選擇最短的一條路線壓入棧中，即為所求的路線。

用兩個(gè)一維數(shù)組來存儲(chǔ)干路上的關(guān)鍵點(diǎn)。用X來存儲(chǔ)關(guān)鍵點(diǎn)的橫坐標(biāo)，Y來存儲(chǔ)關(guān)鍵點(diǎn)的縱坐標(biāo)。首先用status SeatJudge（int X[]，int Y[]，postype cur，int lenx，int leny）這個(gè)函數(shù)來判斷起點(diǎn)和終點(diǎn)屬于哪種情況，分三種：橫坐標(biāo)在干路上，縱坐標(biāo)在干路上，橫縱坐標(biāo)都在干路上。然后用postype* RoutChoose（int X[]，int Y[]，postype cur，int lenx，int leny）來選擇離起點(diǎn)或終點(diǎn)最近的兩個(gè)關(guān)鍵點(diǎn)。例如，如果起點(diǎn)的橫坐標(biāo)在干路上，則調(diào)用postype* Row_equal（postype cur，int Y[]，int leny）這個(gè)函數(shù)，cur表示起點(diǎn)，Y表示關(guān)鍵點(diǎn)縱坐標(biāo)集合，leny表示Y的元素個(gè)數(shù)；在關(guān)鍵點(diǎn)的縱坐標(biāo)數(shù)組Y中選取離起點(diǎn)最近的兩個(gè)關(guān)鍵點(diǎn)，并存入坐標(biāo)結(jié)構(gòu)體數(shù)組keypoint中，然后需要將兩個(gè)關(guān)鍵點(diǎn)的離起點(diǎn)的長(zhǎng)度分別存入keypoint的兩個(gè)結(jié)構(gòu)體元素中，這樣做的原因是為了找出最短路徑。接下來postype KeyPoint（postype key1，postype key2）這個(gè)函數(shù)是確定干路上的兩個(gè)關(guān)鍵點(diǎn)后選擇兩個(gè)關(guān)鍵點(diǎn)之間的轉(zhuǎn)折關(guān)鍵點(diǎn)。最重要的函數(shù)是void PrintRoute（int X[]，int Y[]，postype start，postype end，int lenx，int leny），以這個(gè)函數(shù)來確定最終路徑。Start表示起點(diǎn)坐標(biāo)，end表示終點(diǎn)坐標(biāo)，lenx和leny分別表示數(shù)組X和Y的長(zhǎng)度。

算法的優(yōu)點(diǎn)在于將停車場(chǎng)抽象成一個(gè)個(gè)小方塊，忽略了線路，從而使算法實(shí)現(xiàn)起來更容易，而關(guān)于停車場(chǎng)路徑的擴(kuò)充，則由路徑的模擬來完成。

3 算法流程圖

算法流程圖如下：

4 App實(shí)現(xiàn)原理

使用Android Studio工具開發(fā)Android app，配置java環(huán)境以及Android studio SDK完成Android Studio的安裝。首先根據(jù)我們實(shí)地考察的停車場(chǎng)，繪制了一個(gè)10x8的簡(jiǎn)易虛擬矩形停車區(qū)域，然后通過讀取路徑規(guī)劃算法生成的關(guān)鍵點(diǎn)文件來獲取關(guān)鍵點(diǎn)坐標(biāo)從而進(jìn)行連線，從而達(dá)到從起始點(diǎn)到目的地點(diǎn)的路徑繪制。

5 開發(fā)工具優(yōu)勢(shì)

Microsoft Visual Studio2008于2007年11月發(fā)布，是第一款用于Windows Presentation Foundation （WPF）的擁有可視化設(shè)計(jì)器的應(yīng)用程序，它帶有對(duì)齊線和事件選項(xiàng)卡，允許進(jìn)行 RAD 風(fēng)格的程序開發(fā)。它還通過用于 Outlook 和 Fluent 菜單的設(shè)計(jì)器來支持開發(fā)人員在 2007Microsoft Office System 中進(jìn)行程序開發(fā)。對(duì)于多專業(yè)團(tuán)隊(duì)，Visual Studio Team System 提高了可伸縮性，包括支持連續(xù)集成。

通過對(duì)VS2008的學(xué)習(xí)和應(yīng)用，基本了解了VS 的強(qiáng)大功能，其提供的窗口模式、視圖模式、編程模式極大地方便了用戶的使用， 可以使用 C++、C#、VB、VC 等語言進(jìn)行編程，為不同用戶提供了便捷。通過不同的方法達(dá)到了同樣的目的，學(xué)習(xí)編程語言是一個(gè)積累的過程， VS2008知識(shí)一個(gè)工具，利用好它我們就能達(dá)到寫軟件的目的，為自己的編程提供便捷！

6 模擬研究

7 結(jié)束語

本文首先對(duì)已經(jīng)存在的相關(guān)產(chǎn)品進(jìn)行了試用和分析，發(fā)現(xiàn)在信號(hào)并不好的室內(nèi)停車場(chǎng)幾乎沒有什么幫助，于是在查找了大量文獻(xiàn)和進(jìn)行了多次實(shí)地考察后，我們提出了自己的想法并進(jìn)行了相關(guān)研究。由于在現(xiàn)實(shí)生活中，停車場(chǎng)的布局并不單一，所以我們對(duì)此進(jìn)行了簡(jiǎn)化，并在此基礎(chǔ)上做路徑規(guī)劃，進(jìn)一步開發(fā)app將結(jié)果顯示出來。最后通過幾組數(shù)據(jù)的模擬研究說明該算法的正確性和該app的可用性。但是本文并未對(duì)導(dǎo)航的精確度進(jìn)行深入研究，這將是今后研究的重點(diǎn)。

參考文獻(xiàn)：

[1] 謝娟.路徑規(guī)劃算法的研究及應(yīng)用[D].電子科技大學(xué)，2015.

[2] 田明星.路徑規(guī)劃在車輛導(dǎo)航系統(tǒng)中的應(yīng)用研究[D].北京交通大學(xué)，2009.

[3] 楊俊成，李淑霞，蔡增玉.路徑規(guī)劃算法的研究與發(fā)展[J].控制工程，2017（9）.

[4] 于珊.Android App快速開發(fā)平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)[D].西安電子科技大學(xué)，2013.

[5] 黃永正.Android平臺(tái)App開發(fā)輔助工具的研究與實(shí)現(xiàn)[D].北京郵電大學(xué)，2015.

[6] 韓雪，丁林花，賀紅凱，等.基于Android的城市停車場(chǎng)導(dǎo)航APP[J].電腦編程技巧與維護(hù)，2016（7）.

【通聯(lián)編輯：代影】