秦 鋒，吳 健，張學(xué)鋒，趙晶麗

1(安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，馬鞍山 243032)

2(滁州職業(yè)技術(shù)學(xué)院 信息工程系，滁州 239000)

引言

導(dǎo)航系統(tǒng)中的一項(xiàng)重要技術(shù)路徑規(guī)劃算法現(xiàn)已成為被廣泛運(yùn)用的核心，屬于智能出行研究的熱點(diǎn)問題.大批學(xué)者圍繞Dijkstra 算法提出了很多改進(jìn)措施，例如最常見的A*算法.除了經(jīng)典算法之外，還有遺傳算法、蟻群算法、粒子群優(yōu)化算法等等.文獻(xiàn)[1]對Dijkstra 經(jīng)典算法做了研究工作，算法采用傳統(tǒng)遍歷模式搜索全局地圖網(wǎng)格上的節(jié)點(diǎn)，當(dāng)網(wǎng)格中存在大量節(jié)點(diǎn)時(shí)，由于算法的盲目搜索會(huì)造成大量冗余節(jié)點(diǎn)被遍歷，此時(shí)的算法效率非常低下[2].以傳統(tǒng)Dijkstra 算法作基礎(chǔ)，A*算法于1980年被Nilsson 首先提出[3]，該算法是一種利用啟發(fā)式信息函數(shù)作支撐的全局路徑規(guī)劃算法，算法明顯優(yōu)勢在于擴(kuò)展當(dāng)前節(jié)點(diǎn)之前已經(jīng)引入了全局路網(wǎng)信息作為啟發(fā)信息，用來權(quán)衡下一個(gè)最優(yōu)路徑節(jié)點(diǎn)的位置.在擴(kuò)展過程中需要不斷的迭代計(jì)算所有候選節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)的估價(jià)成本，估價(jià)成本越接近實(shí)際耗費(fèi)成本則該條路徑越準(zhǔn)確.在文獻(xiàn)[4]中引入用類橢圓型作為限制區(qū)域，但計(jì)算復(fù)雜度大幅度提高.文獻(xiàn)[5]中又進(jìn)一步修改限制區(qū)域類型為矩形，降低了運(yùn)行時(shí)間.在遍歷結(jié)構(gòu)確定的情況下，采用空間換時(shí)間的優(yōu)化策略.王士同等人[6]紅色首先提出了啟發(fā)式雙向搜索路徑規(guī)劃算法，并通過實(shí)驗(yàn)論證了該算法的可行性.李清權(quán)等人[7]紅色在傳統(tǒng)算法上進(jìn)行改進(jìn)，改進(jìn)出一種立足于節(jié)點(diǎn)搜索的雙向A*啟發(fā)式路徑規(guī)劃算法.本質(zhì)上A*算法屬于最佳優(yōu)先算法范疇[8]，但該算法也存在明顯的缺點(diǎn)，當(dāng)存在多個(gè)最小值時(shí)或者路網(wǎng)中道路疏密程度不均時(shí)A*算法并不能保證搜索的路徑為最優(yōu)，會(huì)出現(xiàn)文獻(xiàn)[9]所論述的停滯不前的無限循環(huán).并且傳統(tǒng)A*算法在提高搜索精度的同時(shí)需要柵格地圖被分割的更小，為此帶來的另一大缺點(diǎn)即搜索時(shí)間會(huì)成指數(shù)級別的增長，因此本文在后續(xù)的改進(jìn)措施中引入了二叉堆進(jìn)行優(yōu)化.同樣估價(jià)函數(shù)的合理性也成為A*算法的一大缺點(diǎn)，會(huì)直接影響搜索效率.本文作者在研究過程中發(fā)現(xiàn)大部分的全局靜態(tài)路網(wǎng)規(guī)劃中障礙物節(jié)點(diǎn)信息總是保持不變，因此在規(guī)劃路徑之前系統(tǒng)即可提前預(yù)處理地圖信息將障礙物的鄰節(jié)點(diǎn)信息存入內(nèi)存，以便在同樣環(huán)境地圖規(guī)劃中直接通過鍵值對索引相應(yīng)的鄰節(jié)點(diǎn)信息，避免了重復(fù)遍歷地圖的繁瑣程序.針對傳統(tǒng)A*算法存在的缺點(diǎn)，本文對A*算法提出了改進(jìn)措施意圖提高算法效率和精度.引入預(yù)處理模式以及對遍歷結(jié)構(gòu)進(jìn)行優(yōu)化，其次對啟發(fā)函數(shù)式進(jìn)行歸一化操作消除不同量綱之間產(chǎn)生的影響.同時(shí)在前文提及的雙向搜索基礎(chǔ)上引入堆結(jié)構(gòu)作為效率較高的優(yōu)先級序列進(jìn)一步為路徑規(guī)劃提速.實(shí)驗(yàn)結(jié)果表明了改進(jìn)算法的可行性與合理性.

1 路徑規(guī)劃問題概述

1.1 路徑規(guī)劃的分類

路徑規(guī)劃按照環(huán)境情況可分為全局路徑規(guī)劃和局部路徑規(guī)劃.全局路徑規(guī)劃代表地圖環(huán)境信息全部已知的情況，而局部路徑規(guī)劃則為環(huán)境部分未知或者完全未知需要自身感知力進(jìn)行實(shí)時(shí)獲取.另外環(huán)境情況又可分為靜態(tài)和動(dòng)態(tài)，至此路徑規(guī)劃最終細(xì)分為如下四類，分別為全局靜態(tài)路徑規(guī)劃、全局動(dòng)態(tài)路徑規(guī)劃、局部動(dòng)態(tài)路徑規(guī)劃、局部靜態(tài)路徑規(guī)劃.全局靜態(tài)路徑規(guī)劃主要包含構(gòu)型空間法、自由空間法、柵格法.局部靜態(tài)路徑規(guī)劃主要包含人工勢場法、模糊邏輯算法.本文選用的是基于柵格法的全局靜態(tài)路徑規(guī)劃.

1.2 路徑規(guī)劃的步驟

路徑規(guī)劃的整體結(jié)構(gòu)基于算法具體功能實(shí)現(xiàn)，按照“整體感知-地圖建模-最優(yōu)路徑規(guī)劃-算法執(zhí)行操作”的過程依次執(zhí)行[10].首先對整體環(huán)境信息執(zhí)行初始化操作，依據(jù)節(jié)點(diǎn)和障礙物特性選擇合適的地圖.其次對整張地圖進(jìn)行建模操作，建模核心是需要與路徑規(guī)劃操作相適應(yīng)，地圖必須能夠高效的存儲(chǔ)、提取、更新節(jié)點(diǎn)信息.本文將物體的移動(dòng)軌跡細(xì)分化變?yōu)閱蝹€(gè)方向上的路徑信息，將其離散化后路徑信息便被保存在了柵格地圖中.選用柵格地圖的原因在于相對于別的地圖建模其更具位置唯一性，因此在每個(gè)柵格節(jié)點(diǎn)中忽略物體的在任意方向上的微小偏移，只參考節(jié)點(diǎn)四周4 鄰域或者8 鄰域的方向信息便于操作[11-13]，圖1所示.地圖利用矩陣模式存儲(chǔ)節(jié)點(diǎn)，查找任意節(jié)點(diǎn)的行列數(shù)即可得知該節(jié)點(diǎn)具體信息.建立柵格模型后，需要對地圖模型整體進(jìn)行完整編碼標(biāo)記信息，常見的用0 或1 代表當(dāng)前節(jié)點(diǎn)有無障礙，編碼標(biāo)記完成之后還需要對地圖環(huán)境做幾個(gè)既定的準(zhǔn)則，如限定障礙物的位置和大小不變，柵格必須保證統(tǒng)一尺寸大小等.建模完成后配合改進(jìn)過后的算法對整張地圖進(jìn)行路線規(guī)劃，最后回溯拼接之前遍歷過的節(jié)點(diǎn)即得到一條規(guī)劃完成的路徑.

圖1 節(jié)點(diǎn)運(yùn)動(dòng)方向

1.3 Dijkstra 算法

Dijkstra 算法目的為找出從圖中的某個(gè)頂點(diǎn)出發(fā)到達(dá)另一個(gè)頂點(diǎn)所經(jīng)過邊的權(quán)重之和最小的那一條路徑.算法采用貪心策略模式使用廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑.主要思想如下，首先引入一個(gè)向量M，它的的每個(gè)分量M[i]代表從起始頂點(diǎn)V開始到其他各個(gè)頂點(diǎn)V[i]的距離.若V到V[i]有弧則將M[i]設(shè)為弧上的權(quán)值.顯然M[j]=Min{M|Vi∈V}即從起始頂點(diǎn)出發(fā)到頂點(diǎn)Vj距離最短的一條路徑，此時(shí)路徑為(V,Vj).接著定義一個(gè)存放從起始點(diǎn)V出發(fā)的最短路徑的頂點(diǎn)集合S.則下一條距離最優(yōu)的路徑必然為M[j]=Min{M[i]|Vi∈V-S}，M[i]為弧(V,Vi)上的權(quán)值或者為M[k](Vk∈S)和弧(Vk,Vi)權(quán)值總和(k為S中的一個(gè)頂點(diǎn)).直到遍歷完整張地圖網(wǎng)絡(luò)之后，算法根據(jù)局部最優(yōu)準(zhǔn)則選出一條最優(yōu)路徑，但是缺點(diǎn)在于整個(gè)搜索過程屬于盲目搜索只關(guān)注實(shí)際耗價(jià)值沒有考慮到待選節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)所造成的影響，因此規(guī)劃過程將耗費(fèi)大量的時(shí)間.

1.4 跳點(diǎn)算法

近年來研究人員推出了一種高效尋路算法Jump Point Search，也就是所謂的跳點(diǎn)算法.其本質(zhì)針對有序序列查找跳點(diǎn)與二分法類似，主要思想就是大范圍跳躍式搜索柵格網(wǎng)絡(luò)中對稱的路徑，只把其中的跳躍點(diǎn)當(dāng)作待搜索的柵格節(jié)點(diǎn).其明顯優(yōu)勢在于大幅度減少openlist中的待選節(jié)點(diǎn)得益于在固定間隔的跳躍搜索過程中已經(jīng)剔除了網(wǎng)格地圖中大量無用節(jié)點(diǎn).具體的實(shí)現(xiàn)大致涉及到兩個(gè)方面，第一步先遍歷openlist 表篩選出一個(gè)最優(yōu)節(jié)點(diǎn)，然后從幾個(gè)既定好的方向展開搜索，將每個(gè)方向獲得的跳點(diǎn)加入到openlist 表中.第二步在之前得到的各個(gè)方向上的跳點(diǎn)中篩選出代價(jià)最小的跳點(diǎn)作為新的起始點(diǎn)，從該點(diǎn)開始繼續(xù)向既定方向展開搜索.重復(fù)以上兩步操作，直到終點(diǎn)被存入到openlist 表中，尋路結(jié)束.但該算法仍然存在一些不可避免的限制因素，首先對地圖要求條件較高必須是規(guī)則的柵格型地圖，不支持復(fù)雜地形，網(wǎng)格節(jié)點(diǎn)不能帶權(quán)重，但相比傳統(tǒng)A*算法，其算法效率已經(jīng)提高了一倍左右.

1.5 傳統(tǒng)A＊算法

A*算法引入啟發(fā)函數(shù)h(n)對全局信息進(jìn)行估價(jià)，算法主要表達(dá)式:f(n)=g(n)+h(n)，其中f(n)為初始狀態(tài)經(jīng)過狀態(tài)n到達(dá)目標(biāo)狀態(tài)的代價(jià)估計(jì)，g(n)為初始狀態(tài)到達(dá)狀態(tài)n的移動(dòng)耗費(fèi)，h(n)為狀態(tài)n到達(dá)目標(biāo)狀態(tài)的將此估價(jià)作為最佳路徑可能性的量度.算法中關(guān)鍵的是兩個(gè)list 列表，用于存儲(chǔ)已經(jīng)遍歷和未遍歷的柵格節(jié)點(diǎn)，同時(shí)配合啟發(fā)函數(shù)對地圖上任意柵格節(jié)點(diǎn)距目標(biāo)節(jié)點(diǎn)的距離進(jìn)行有效估價(jià)，估價(jià)值越接近實(shí)際耗費(fèi)，在四鄰域或八鄰域的情況下則會(huì)更好的尋找搜索方向.最低估計(jì)代價(jià).A*算法步驟如下描述:

Step 1.將起始點(diǎn)加入openlist，并初始化openlist 和closedlist.

Step 2.openlist 若為空，結(jié)束算法.若不為空，計(jì)算最小的點(diǎn)，將該節(jié)點(diǎn)添加到最優(yōu)路徑上.

Step 3.對當(dāng)前處理的節(jié)點(diǎn)，以4 方向或者8 方向計(jì)算鄰節(jié)點(diǎn)，遍歷closedlist 和openlist，若均不包含鄰節(jié)點(diǎn)，則將其加入openlist.

Step 4.循環(huán)執(zhí)行Step 2 和Step 3 到算法結(jié)束，回溯遍歷之前拓展選中的路徑，則路徑規(guī)劃完成.

其中一般選用曼哈頓距離、歐式距離或者切比雪夫距離(當(dāng)h(n)=0時(shí)，A*算法將變?yōu)镈ijkstra 算法)，

2 改進(jìn)雙向預(yù)處理A*算法概述

綜合上述傳統(tǒng)算法的優(yōu)缺點(diǎn)，本文提出改進(jìn)策略提高算法效率.以經(jīng)典A*算法為基礎(chǔ)，先執(zhí)行雙向搜索策略從起點(diǎn)終點(diǎn)同時(shí)開始搜索，對算法中的角度和方向因子實(shí)現(xiàn)歸一化處理以消除不同量綱對節(jié)點(diǎn)參數(shù)所帶來的影響.同時(shí)提出改進(jìn)的算法結(jié)構(gòu)，將柵格地圖中的障礙物信息預(yù)處理存入內(nèi)存以減少資源消耗，并且對遍歷數(shù)組時(shí)的節(jié)點(diǎn)添加布爾類型的判定信息，初始化地圖后可直接依據(jù)此判定信息對節(jié)點(diǎn)是否在兩個(gè)列表中進(jìn)行判定而無須再做重復(fù)性的遍歷操作，進(jìn)一步提高算法效率.

2.1 并行化處理

引入并行化處理模式即實(shí)現(xiàn)雙向搜索算法，該模式將搜索過程分解為前向后向兩個(gè)獨(dú)立的搜索進(jìn)程，起點(diǎn)終點(diǎn)分別作為對方向的目標(biāo)節(jié)點(diǎn).雙向搜索核心思路在于終止條件的判定，在理想狀態(tài)下兩條搜索路徑會(huì)在地圖路徑中心點(diǎn)相遇，此時(shí)兩個(gè)方向上的openlist中出現(xiàn)重復(fù)的節(jié)點(diǎn)即可判定規(guī)劃完成，這樣做可大大減少單向遍歷搜索所耗費(fèi)的時(shí)間和空間資源.

2.2 矢量化和歸一化的改進(jìn)

A*算法在傳統(tǒng)估價(jià)函數(shù)的影響下，只會(huì)單一的進(jìn)行往返搜索生成大量的搜索節(jié)點(diǎn).而在實(shí)際情況中當(dāng)前節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)的估價(jià)值一定不大于實(shí)際路徑耗費(fèi)值，因此需要加快當(dāng)前節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)的收斂速度即增大估價(jià)函數(shù)h(n)的權(quán)值.考慮到大部分的權(quán)值設(shè)定都視具體的地圖情況例如地圖大小，障礙物數(shù)量，地形因素而定因此具有片面性.并且當(dāng)前節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)的估價(jià)距離占實(shí)際距離的比重與當(dāng)前節(jié)點(diǎn)在地圖中的位置相關(guān).本文在前文基礎(chǔ)上，在當(dāng)前節(jié)點(diǎn)遠(yuǎn)離目標(biāo)點(diǎn)，此時(shí)估價(jià)值低于實(shí)際值，增大權(quán)重.相對應(yīng)的當(dāng)前節(jié)點(diǎn)靠近目標(biāo)點(diǎn)時(shí)，當(dāng)前估價(jià)值接近實(shí)際值，相對應(yīng)的降低權(quán)重.因此本文引入以指數(shù)衰減方式的權(quán)重因子，對傳統(tǒng)A*算法表達(dá)式做出如下修改.公式為:

式中的w1與w2分別為距離和角度的權(quán)重系數(shù)，其取值范圍分別為0.55-0.65 和0.35-0.45[15].L表示當(dāng)前節(jié)點(diǎn)距目標(biāo)點(diǎn)的距離值，α表示起點(diǎn)至當(dāng)前節(jié)點(diǎn)連線的線段與當(dāng)前節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)連線線段的夾角值.根據(jù)地圖大小引入權(quán)重系數(shù)的優(yōu)勢在于，同時(shí)權(quán)衡距離信息與方向信息，加快搜索進(jìn)程.由于不同的評價(jià)標(biāo)準(zhǔn)具有不同的量綱，為了消除指標(biāo)之間量綱的影響，需要進(jìn)行數(shù)據(jù)歸一化標(biāo)準(zhǔn)處理，保留其本身所有特性，但是減少參數(shù)大小產(chǎn)生的影響，歸一化大大加快了梯度下降求最優(yōu)解的速度.針對本文的思路，對h(n)估價(jià)函數(shù)的距離和角度因子進(jìn)行歸一化處理，對遍歷進(jìn)行提速.本文對文獻(xiàn)[19]的估價(jià)函數(shù)提出改進(jìn)，采用Z-score 標(biāo)準(zhǔn)化方法對距離和角度消除量綱影響因素，標(biāo)準(zhǔn)化公式為:

其中，μ為所有樣本數(shù)據(jù)的均值，σ為所有樣本數(shù)據(jù)的標(biāo)準(zhǔn)差.將距離和角度因子代入(n代表鄰節(jié)點(diǎn)的數(shù)量)公式中:

此時(shí)h?(n)修改為

原算法f(n)改進(jìn)為

式(10)意義在于當(dāng)估價(jià)函數(shù)h?(n)數(shù)值較大時(shí)，權(quán)重因子增大同時(shí)g(n)占比重減小，當(dāng)前節(jié)點(diǎn)加速向目標(biāo)節(jié)點(diǎn)收斂.當(dāng)h?(n)較小時(shí)，權(quán)重因子也隨之減小反之g(n)占比重增大.當(dāng)權(quán)重因子逼近1時(shí)表明當(dāng)前節(jié)點(diǎn)已經(jīng)靠近目標(biāo)點(diǎn).仿真實(shí)驗(yàn)中表2的數(shù)據(jù)結(jié)果表明相比于文獻(xiàn)[19]的A*算法和跳點(diǎn)算法，搜索節(jié)點(diǎn)數(shù)和搜索時(shí)長有明顯降低，實(shí)時(shí)性有顯著提高.同時(shí)參照幾張運(yùn)行效果截圖，表明在距離和角度這兩個(gè)權(quán)重系數(shù)的影響下，搜索深度明顯減少，搜索方向被顯著的約束在更趨向于目標(biāo)點(diǎn)的方向上證明了該公式的可行性.

2.3 基于堆結(jié)構(gòu)的完全排序

傳統(tǒng)A*算法中，計(jì)算機(jī)性能耗費(fèi)關(guān)乎地圖大小和反復(fù)遍歷openlist中F值最小點(diǎn)這兩個(gè)因素，所以路徑規(guī)劃耗費(fèi)的時(shí)長和所達(dá)到的精度取決于算法中存儲(chǔ)列表方式的設(shè)計(jì).本文在傳統(tǒng)A*算法中引入二叉堆.二叉堆實(shí)則是以堆結(jié)構(gòu)存在的一種特殊的樹，可以保證數(shù)據(jù)結(jié)構(gòu)的有序性以提高搜索效率，是一種優(yōu)先級序列.它的優(yōu)點(diǎn)在于在堆結(jié)構(gòu)中子節(jié)點(diǎn)與父節(jié)點(diǎn)的鍵值總是以一種特定的有序關(guān)系相聯(lián)系，由此帶來的好處是在計(jì)算過程中并不需要直接得到完整的全局有序信息，而只需要全局節(jié)點(diǎn)的極值以避免造成不必要的資源浪費(fèi).本文中堆結(jié)構(gòu)被用于優(yōu)化從開啟列表移除節(jié)點(diǎn)數(shù)據(jù)，向關(guān)閉列表添加節(jié)點(diǎn)數(shù)據(jù)，可以保證兩個(gè)列表始終保持內(nèi)部數(shù)據(jù)有序.本文引入的二叉堆結(jié)構(gòu)主要涉及向open 列表添加新元素和在切換至close 列表后從堆頂刪除F 值最小的元素.添加元素操作主要步驟為，首先將起始節(jié)點(diǎn)添加至open 列表，同時(shí)計(jì)算新元素的G、H、F值并將新元素添加至開啟列表的底端，然后依次比較該元素和該元素的父節(jié)點(diǎn)直到該元素到達(dá)表中正確的位置.刪除操作主要步驟為在刪除某個(gè)元素之后將當(dāng)前的末元素移動(dòng)至堆頂端，依次比較該元素和它兩個(gè)子節(jié)點(diǎn)元素的F值，如果該元素的F耗價(jià)值高于其兩個(gè)子節(jié)點(diǎn)則交換它與其中較低F值的節(jié)點(diǎn)，重復(fù)該過程直到該元素找到在堆中的相應(yīng)位置.

實(shí)現(xiàn)二叉堆主要偽代碼如下:

算法1.向堆中添加新元素獲取表最后一位下標(biāo)；last←open.length-1；while (last ＞ 1)half←last；與父節(jié)點(diǎn)比較F 值大??；If(open[last].F＞=open[half].F)THEN break；在表中與父節(jié)點(diǎn)調(diào)換位置；temporary←open[last]；open[last]←open[half]；open[half]←temporary；

算法2.從堆中刪除元素將堆底端元素移至堆頂；open[1]←open[last]；重新獲得堆末位元素下標(biāo)last←open.length-1；head←1；先比較堆頂節(jié)點(diǎn)兩個(gè)子節(jié)點(diǎn)F 值大小，找出較小F 值的子節(jié)點(diǎn)；childMin←open[child1].F＜o(jì)pen[child2].F?child1:child2；比較父節(jié)點(diǎn)與較小子節(jié)點(diǎn)F 值大??；IF(open[head].F＜=open[childMin].F THEN break；若父節(jié)點(diǎn)F 值大于子節(jié)點(diǎn)F 值，則交換位置；temporary←open[head]；open[head]←open[childMin]；open[childMin]←temporary；交換父節(jié)點(diǎn)與較小子節(jié)點(diǎn)的位置；head=childMin；

2.4 實(shí)現(xiàn)預(yù)處理結(jié)構(gòu)

前面已經(jīng)提及采用并行二叉堆且加入矢量化因子已經(jīng)提高了計(jì)算性能，但優(yōu)化的實(shí)質(zhì)大多數(shù)是空間換時(shí)間，因?yàn)樵谌朱o態(tài)地圖中障礙物信息保持不變并且鄰域柵格的耗價(jià)值也是不變的，但如果每次尋路時(shí)都去計(jì)算鄰節(jié)點(diǎn)網(wǎng)格是否存在障礙物則會(huì)消耗大量時(shí)間.因此把算法中部分過程的計(jì)算先執(zhí)行預(yù)處理后存入內(nèi)存.本文首先對障礙物鄰節(jié)點(diǎn)進(jìn)行預(yù)計(jì)算，對當(dāng)前節(jié)點(diǎn)首先判斷該節(jié)點(diǎn)周圍是否存在障礙物并同時(shí)計(jì)算鄰域柵格的耗價(jià)值.具體步驟如下，首先為所有的節(jié)點(diǎn)添加一個(gè)新的代表鄰節(jié)點(diǎn)的數(shù)組AdjNodeArray，同時(shí)構(gòu)造新的鄰節(jié)點(diǎn)耗費(fèi)值數(shù)組AdjNodeCost，這兩個(gè)數(shù)組是為了初始化時(shí)存入鄰域的節(jié)點(diǎn)信息.保證AdjNodeArray[i]與AdjNodeCost[i]兩個(gè)數(shù)組的映射關(guān)系以便于在查詢某個(gè)鄰域節(jié)點(diǎn)時(shí)可直接對應(yīng)查找其耗價(jià)值.其次在地圖初始化的過程中，先進(jìn)行預(yù)處理操作遍歷所有的地圖網(wǎng)格，找出地圖中節(jié)點(diǎn)標(biāo)記編號(hào)為0(柵格地圖中障礙物編號(hào)為1，非障礙物為0)的所有非障礙方格節(jié)點(diǎn)存入鄰節(jié)點(diǎn)AdjNodeArray，同時(shí)計(jì)算鄰節(jié)點(diǎn)耗費(fèi)值映射存入AdjNodeCost.最后涉及到具體尋路過程需要判斷當(dāng)前節(jié)點(diǎn)附近鄰節(jié)點(diǎn)信息時(shí)，直接從鄰節(jié)點(diǎn)數(shù)組AdjNodeArray中讀取當(dāng)前節(jié)點(diǎn)的屬性值就能得知此節(jié)點(diǎn)周圍鄰節(jié)點(diǎn)的全部屬性值而無需再重復(fù)計(jì)算.例如在預(yù)處理地圖之后尋路過程中需判定二維坐標(biāo)號(hào)為(6，9)的當(dāng)前節(jié)點(diǎn)信息以及下一節(jié)點(diǎn)的選擇情況，只需要先在鄰節(jié)點(diǎn)數(shù)組找到當(dāng)前點(diǎn)判定是否為非障礙物節(jié)點(diǎn)，并根據(jù)映射關(guān)系就可直接得到該節(jié)點(diǎn)的鄰節(jié)點(diǎn)耗價(jià)值，接著相應(yīng)的通過估價(jià)函數(shù)選擇下一步行進(jìn)的路徑節(jié)點(diǎn)，重復(fù)以上操作直至找到終點(diǎn).預(yù)處理大大縮減每次遍歷地圖計(jì)算計(jì)算節(jié)點(diǎn)信息的時(shí)間.另外算法結(jié)構(gòu)中每次搜索數(shù)組采用的常規(guī)遍歷操作indexof 實(shí)際占用了大量的運(yùn)算時(shí)間，本文同樣對數(shù)組遍歷進(jìn)行優(yōu)化，對每個(gè)節(jié)點(diǎn)賦予布爾類型屬性isopen 和isclosed作為標(biāo)記信息，每次對當(dāng)前節(jié)點(diǎn)進(jìn)行push 操作時(shí)，在openlist中設(shè)置當(dāng)前節(jié)點(diǎn)的布爾屬性isopen 為true，當(dāng)下一步操作將該節(jié)點(diǎn)移出開啟列表后，同時(shí)更改isopen 值為false，這樣處理的優(yōu)勢在于，判斷當(dāng)前節(jié)點(diǎn)是否在openlist中，只需要對應(yīng)的獲取它的布爾值即可.同理可以判斷節(jié)點(diǎn)是否存在于closedlist中.

3 實(shí)驗(yàn)結(jié)果對比分析

為了驗(yàn)證改進(jìn)A*算法的實(shí)際效果，本文設(shè)置不同的對照組在柵格地圖中進(jìn)行大量的數(shù)據(jù)測試.實(shí)驗(yàn)環(huán)境為Intel Core i5，Win10，8 GB 內(nèi)存，采用Matlab 2012a 編譯.

3.1 實(shí)驗(yàn)過程

本文建立一個(gè)20×30的柵格地圖，將起始點(diǎn)與終點(diǎn)設(shè)定在柵格地圖的(2，2)，(20，30)坐標(biāo)處.如圖2所示.

應(yīng)用本文改進(jìn)A*算法對圖2所示地圖模型進(jìn)行計(jì)算，選取權(quán)重系數(shù)w為0.59 首先進(jìn)行第一次預(yù)處理將地圖信息存入內(nèi)存，預(yù)處理完成后進(jìn)行第二次路徑規(guī)劃，運(yùn)行結(jié)果如表1所示.

其次保持地圖環(huán)境不變，選用其它傳統(tǒng)算法同樣對該地圖進(jìn)行仿真計(jì)算，得出多組結(jié)果如表2所示.其中，M和E分別代表選用曼哈頓距離或歐式距離，Dijkstra 與跳點(diǎn)算法不區(qū)分鄰域數(shù)及選用的距離函數(shù).部分程序運(yùn)行截圖如圖3所示.

圖2 柵格地圖

圖3中圖(a)、(b)、(c)、(d)依次是改進(jìn)A*算法分別計(jì)算8 鄰域歐式距離，4 鄰域曼哈頓距離，4 鄰域歐式距離運(yùn)行效果截圖，圖中黑色實(shí)心圓點(diǎn)為起點(diǎn)與終點(diǎn)，粗體黑色實(shí)線為規(guī)劃路線，斜向黑色實(shí)線表示本次規(guī)劃所遍歷的節(jié)點(diǎn)方格.以及Dijkstra 算法運(yùn)行效果截圖.

表1 預(yù)處理前后運(yùn)行效率對比

表2 不同算法運(yùn)行效率對比

圖3 幾種規(guī)劃算法運(yùn)行效果截圖

3.2 計(jì)算效率對比

從表2 可以看出，在相同的地圖環(huán)境下，本文改進(jìn)的A*算法所仿真得到的路徑相比于文獻(xiàn)[19]的A*算法和跳點(diǎn)算法，雖然路徑長度有一定程度的增加，但因?yàn)槠錃w一化的方向和角度因子，以及對數(shù)組遍歷的優(yōu)化，使得遍歷節(jié)點(diǎn)數(shù)比例降低，尤其在4 鄰域的條件下節(jié)點(diǎn)數(shù)下降趨勢更為明顯，數(shù)據(jù)表明在8 鄰域標(biāo)準(zhǔn)下，本文改進(jìn)過后的算法相比于Dijkstra，文獻(xiàn)[19]的A*，跳點(diǎn)算法節(jié)點(diǎn)數(shù)分別下降48.93%，9.01%，35.05%.在4 鄰域標(biāo)準(zhǔn)下分別下降35.21%，24.31%，17.60%.證明了改進(jìn)A*算法的矢量化與歸一化處理能夠有效的降低搜索節(jié)點(diǎn)數(shù).同時(shí)，搜索時(shí)長較A*算法與跳點(diǎn)算法都有不同程度的提升，8 鄰域條件下相比于文獻(xiàn)[19]A*與跳點(diǎn)算法，時(shí)長分別降低35% 和18.75%，4 鄰域條件下，時(shí)長分別降低65%和39.13%，由此可以證明引入堆結(jié)構(gòu)可大幅度降低遍歷時(shí)長.同樣表1 可以看出第一次預(yù)處理地圖信息之后的第二次遍歷時(shí)長在8 鄰域和4 鄰域的標(biāo)準(zhǔn)下分別下降27.78%與6.67%，表明對地圖節(jié)點(diǎn)的預(yù)處理操作提前處理節(jié)點(diǎn)附近的障礙物信息并且進(jìn)行內(nèi)存預(yù)存儲(chǔ)以及對數(shù)組添加布爾型標(biāo)記信息的優(yōu)化，都能有效降低后續(xù)遍歷時(shí)長.

4 結(jié)束語

如今以啟發(fā)式搜索為核心的A*算法在導(dǎo)航尋路規(guī)劃領(lǐng)域得到了廣泛的應(yīng)用.結(jié)合經(jīng)典A*算法與本文的雙向預(yù)處理改進(jìn)A*算法，本文算法在規(guī)劃時(shí)長方面更具優(yōu)勢，得益于改進(jìn)的預(yù)處理算法結(jié)構(gòu)以及權(quán)重系數(shù)對歸一化處理后的方向距離因子的收斂加速特性，運(yùn)行實(shí)驗(yàn)結(jié)果表明本文改進(jìn)算法規(guī)劃路徑的可行性.