邢孟陽(yáng)，杜嘉豪，吳竟啟，束 磊，郭中陽(yáng)

（1上海工程技術(shù)大學(xué) 機(jī)械與汽車(chē)工程學(xué)院，上海 201620；2江蘇超力電器有限公司，江蘇 鎮(zhèn)江 212321）

0 引 言

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

上述方法在解決特定問(wèn)題時(shí)具有良好的表現(xiàn)，但也存在著不足，如文獻(xiàn)［1］中提到的方法，其搜索范圍局限于車(chē)輛周?chē)?，不能夠?qū)崿F(xiàn)全局搜索、全局規(guī)劃。文獻(xiàn)［2］中采用改進(jìn)新型遺傳算法，但該算法中起關(guān)鍵作用的適應(yīng)度函數(shù)的選取難度較大，選取不當(dāng)容易導(dǎo)致局部收斂，無(wú)法達(dá)到全局最優(yōu)，且該算法參數(shù)較多，難以控制。因此本文選擇對(duì)傳統(tǒng)A算法進(jìn)行改進(jìn)優(yōu)化，改進(jìn)后的A算法不僅在搜索效率方面比其它算法更具優(yōu)勢(shì)，而且其所規(guī)劃的路徑對(duì)于駕駛員來(lái)說(shuō)更加適宜，改進(jìn)的算法控制簡(jiǎn)單，適合規(guī)?；茝V應(yīng)用。

1 A*算法原理

A算法是一種啟發(fā)式搜索算法。在狀態(tài)空間中，首先對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最佳位置，然后從該位置再繼續(xù)進(jìn)行搜索，直至到達(dá)目標(biāo)位置。算法實(shí)現(xiàn)流程圖如圖1所示。

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

研究可得計(jì)算公式如下：

其中，（）是從初始位置經(jīng)由節(jié)點(diǎn)（即現(xiàn)在所處位置）到達(dá)目標(biāo)位置的估計(jì)距離；（）表示從初始狀態(tài)到節(jié)點(diǎn)實(shí)際走過(guò)的距離；（）是從節(jié)點(diǎn)到目標(biāo)位置的最佳路徑的估計(jì)距離。

從式（1）中可以看出若要獲取最佳路徑，（）的選取十分關(guān)鍵。假設(shè)（）代表節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的距離，那么（）與（）之間的關(guān)系可以表示如下：

（1）（）（）。此時(shí)，可以得到全局最佳路徑，但這將導(dǎo)致搜索的節(jié)點(diǎn)過(guò)多，計(jì)算量過(guò)大，降低搜索效率。

（2）（）（）。即預(yù)估距離（）與實(shí)際距離（）相等，此時(shí)，算法的搜索過(guò)程將會(huì)嚴(yán)格按照最短距離進(jìn)行搜索，這時(shí)拓展節(jié)點(diǎn)少，搜索效率相對(duì)較高，但路徑未必是最佳。

（3）（）（）。此時(shí)，算法所需要搜索的節(jié)點(diǎn)少，提高了搜索效率，但容易導(dǎo)致算法局部收斂，從而無(wú)法得到全局最優(yōu)路徑規(guī)劃。

2 對(duì)A*算法的優(yōu)化

2.1 引入權(quán)重系數(shù)

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

（）的引入可以為（）帶來(lái)更大的權(quán)重，通過(guò)合理設(shè)置（）的值，使算法能夠兼顧搜索效率和路徑長(zhǎng)度。

2.2 拐角優(yōu)化

拐角優(yōu)化示意如圖2所示。圖2中，綠色和黃色小點(diǎn)分別代表起點(diǎn)和終點(diǎn)，由起點(diǎn)至終點(diǎn)有圖2中的1和2兩種最短路徑，對(duì)于算法而言，這2種路徑在長(zhǎng)度上并無(wú)差別，但考慮現(xiàn)實(shí)場(chǎng)景，對(duì)比1和2兩種路徑就會(huì)發(fā)現(xiàn)，路徑1要比路徑2多一次轉(zhuǎn)向，而過(guò)多轉(zhuǎn)向會(huì)給駕駛?cè)藥?lái)不良體驗(yàn)，因此在路徑規(guī)劃中應(yīng)予以避免。

圖2 拐角優(yōu)化示意圖Fig.2 Corner optimization schematic diagram

3 模型的構(gòu)建

為了更加真實(shí)還原停車(chē)場(chǎng)環(huán)境，研究中基于數(shù)字仿真軟件測(cè)試平臺(tái)構(gòu)建了一個(gè)如圖3所示的40×40的復(fù)雜停車(chē)場(chǎng)柵格地圖。圖3中，黑色的方格代表車(chē)位，考慮到在停車(chē)場(chǎng)中，車(chē)位的大小是基本一致的，故可用統(tǒng)一的變量來(lái)表示，停車(chē)場(chǎng)內(nèi)部的道路是圍繞著車(chē)位進(jìn)行規(guī)劃的，因此可以用車(chē)位間隙來(lái)表示道路。由于A算法是通過(guò)先計(jì)算初始位置與節(jié)點(diǎn)間的實(shí)際距離和節(jié)點(diǎn)到目標(biāo)位置的估計(jì)距離，然后進(jìn)行比較排序來(lái)實(shí)現(xiàn)拓展和路徑規(guī)劃的，因此就可以將每次拓展的代價(jià)設(shè)定為統(tǒng)一量，這樣在計(jì)算的時(shí)候能夠減小運(yùn)算量，提高算法搜索效率。

4 仿真驗(yàn)證

本次仿真實(shí)驗(yàn)采用對(duì)比實(shí)驗(yàn)的方法，基于數(shù)字仿真軟件測(cè)試平臺(tái)，在相同條件下對(duì)傳統(tǒng)A算法、改進(jìn)A算法、Dijkstra算法、BFS算法進(jìn)行對(duì)比實(shí)驗(yàn)。仿真實(shí)驗(yàn)結(jié)果如圖3～圖6所示。路徑規(guī)劃時(shí)間對(duì)比結(jié)果見(jiàn)表1，轉(zhuǎn)彎次數(shù)統(tǒng)計(jì)結(jié)果見(jiàn)表2。

圖3 傳統(tǒng)A*算法Fig.3 Traditional A*algorithm

圖4 改進(jìn)A*算法Fig.4 Improved A*algorithm

圖5 Dijkstra算法Fig.5 Dijkstra algorithm

圖6 BFS算法Fig.6 BFS algorithm

表1 路徑規(guī)劃時(shí)間對(duì)比表Tab.1 Comparison of routine planning time s

表2 轉(zhuǎn)彎次數(shù)統(tǒng)計(jì)表Tab.2 Statistical table of turns

5 仿真結(jié)果分析

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

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

本文針對(duì)復(fù)雜停車(chē)環(huán)境中停車(chē)、尋車(chē)?yán)щy問(wèn)題展開(kāi)深入研究，選擇對(duì)路徑規(guī)劃中比較成熟的A算法進(jìn)行優(yōu)化應(yīng)用，傳統(tǒng)的A算法是靜態(tài)的規(guī)劃，拓展節(jié)點(diǎn)相對(duì)較多，搜索效率相對(duì)較低，其規(guī)劃出的路徑相比啟發(fā)式A算法而言存在不夠平滑，不夠人性化等缺點(diǎn)。因此本文通過(guò)引入權(quán)重系數(shù)，提高節(jié)點(diǎn)與目標(biāo)點(diǎn)距離在算法中的權(quán)重來(lái)對(duì)算法進(jìn)行改進(jìn)。在實(shí)驗(yàn)測(cè)試中，研究發(fā)現(xiàn)算法在路徑規(guī)劃中可能會(huì)在相同距離條件下規(guī)劃出多次轉(zhuǎn)向路徑，會(huì)給實(shí)際使用過(guò)程帶來(lái)不良體驗(yàn)，因此通過(guò)在算法程序中加入拐角修正，使算法規(guī)劃出的路徑更加平滑，更加人性化，這些優(yōu)化能夠給實(shí)際使用者帶來(lái)舒適的體驗(yàn)。未來(lái)還需解決在路徑規(guī)劃中全局規(guī)劃、全局控制的問(wèn)題，如需要將路徑規(guī)劃與車(chē)輛自主導(dǎo)航控制相結(jié)合，如此一來(lái)所規(guī)劃的路徑需要更加精細(xì)化，同時(shí)還要考慮到停車(chē)場(chǎng)內(nèi)可能出現(xiàn)的會(huì)車(chē)、錯(cuò)車(chē)、行人、擁堵等復(fù)雜狀況，及時(shí)引導(dǎo)車(chē)輛，避免危險(xiǎn)發(fā)生。