A^*啟發(fā)算法是最優(yōu)路徑規(guī)劃問題中最有效的算法之一,在路徑規(guī)劃問題中得到廣泛應(yīng)用。針對多值柵格環(huán)境下的最優(yōu)路徑規(guī)劃的效率問題,對A^*算法在搜索策略上做了如下改進(jìn):一是提出了兩種新的啟發(fā)函數(shù);二是提出了新的A^*雙向搜索算法。實(shí)驗(yàn)表明改進(jìn)算法求得的路徑為最優(yōu)路徑,搜索效率比傳統(tǒng)的Dijkstra算法有顯著提升,雙向A^*算法比單向A^*算法效率有明顯提高。 

【文章來源】：測繪科學(xué)技術(shù)學(xué)報. 2019,36(02)北大核心

【文章頁數(shù)】：7 頁

【部分圖文】：

通行成本圖1．1新啟發(fā)函數(shù)

Dijkstra算法大幅縮小且具有指向性，主要沿著起點(diǎn)至終點(diǎn)的最優(yōu)路徑進(jìn)行擴(kuò)展，原因是加入了終點(diǎn)的啟發(fā)信息;方法3比方法2的搜索范圍更小，搜索范圍更收斂于最優(yōu)路徑，原因是對角啟發(fā)函數(shù)攜帶的啟發(fā)信息比動態(tài)啟發(fā)函數(shù)多;方法4、方法5分別比方法2、方法3具有更小和更收斂的搜索范圍，原因是加入了雙向搜索算法。圖3改進(jìn)算法相對方法1的搜索點(diǎn)數(shù)效率提升比圖4改進(jìn)算法相對方法1的搜索時間效率提升比圖5方法3相對于方法2的效率提升比圖6方法4相對方法2的效率提升比圖7方法5相對方法3的效率提升比圖3～圖7為各算法的效率提升對比圖。圖3～圖5表明兩種新啟發(fā)函數(shù)都使算法效率顯著提升。當(dāng)網(wǎng)格距離較大時，動態(tài)啟發(fā)函數(shù)效率提升比達(dá)到76%，對角啟發(fā)函數(shù)效率提升比達(dá)到82%;且對角啟發(fā)函數(shù)比動態(tài)啟發(fā)函數(shù)更有效，當(dāng)距離較大時，前者比后者效率大約提升20%。由于數(shù)據(jù)的非隨機(jī)分布性，導(dǎo)致效率提升比曲線發(fā)生波動。從圖6和圖7可以看出，雙向搜索對單向搜索的效率提升比隨著起止點(diǎn)網(wǎng)格距離變大而波動性變大。當(dāng)起止點(diǎn)網(wǎng)格距離較大時，雙向搜索效率對于單向搜索明顯提升，提升值達(dá)到30%左右;當(dāng)起止點(diǎn)網(wǎng)格距離較小時，前者搜索點(diǎn)數(shù)比后者少，但兩者時間效率差不多。原因是雙向搜索判斷是否達(dá)到終止條件的時間和搜索柵格時間數(shù)量級相近，效率提升比曲線波動大的原因是通行成本數(shù)據(jù)的非隨機(jī)分布。圖3和圖4表明綜合改進(jìn)后的算法(方法4和方法5)比改進(jìn)前算法的效率有了顯著提升。搜索時間效率提升比隨著起止點(diǎn)網(wǎng)格距離的增大波動性增大，最后趨于穩(wěn)定，達(dá)到86%左右。3結(jié)?

Dijkstra算法大幅縮小且具有指向性，主要沿著起點(diǎn)至終點(diǎn)的最優(yōu)路徑進(jìn)行擴(kuò)展，原因是加入了終點(diǎn)的啟發(fā)信息;方法3比方法2的搜索范圍更小，搜索范圍更收斂于最優(yōu)路徑，原因是對角啟發(fā)函數(shù)攜帶的啟發(fā)信息比動態(tài)啟發(fā)函數(shù)多;方法4、方法5分別比方法2、方法3具有更小和更收斂的搜索范圍，原因是加入了雙向搜索算法。圖3改進(jìn)算法相對方法1的搜索點(diǎn)數(shù)效率提升比圖4改進(jìn)算法相對方法1的搜索時間效率提升比圖5方法3相對于方法2的效率提升比圖6方法4相對方法2的效率提升比圖7方法5相對方法3的效率提升比圖3～圖7為各算法的效率提升對比圖。圖3～圖5表明兩種新啟發(fā)函數(shù)都使算法效率顯著提升。當(dāng)網(wǎng)格距離較大時，動態(tài)啟發(fā)函數(shù)效率提升比達(dá)到76%，對角啟發(fā)函數(shù)效率提升比達(dá)到82%;且對角啟發(fā)函數(shù)比動態(tài)啟發(fā)函數(shù)更有效，當(dāng)距離較大時，前者比后者效率大約提升20%。由于數(shù)據(jù)的非隨機(jī)分布性，導(dǎo)致效率提升比曲線發(fā)生波動。從圖6和圖7可以看出，雙向搜索對單向搜索的效率提升比隨著起止點(diǎn)網(wǎng)格距離變大而波動性變大。當(dāng)起止點(diǎn)網(wǎng)格距離較大時，雙向搜索效率對于單向搜索明顯提升，提升值達(dá)到30%左右;當(dāng)起止點(diǎn)網(wǎng)格距離較小時，前者搜索點(diǎn)數(shù)比后者少，但兩者時間效率差不多。原因是雙向搜索判斷是否達(dá)到終止條件的時間和搜索柵格時間數(shù)量級相近，效率提升比曲線波動大的原因是通行成本數(shù)據(jù)的非隨機(jī)分布。圖3和圖4表明綜合改進(jìn)后的算法(方法4和方法5)比改進(jìn)前算法的效率有了顯著提升。搜索時間效率提升比隨著起止點(diǎn)網(wǎng)格距離的增大波動性增大，最后趨于穩(wěn)定，達(dá)到86%左右。3結(jié)?

【參考文獻(xiàn)】：
期刊論文
[1]基于A*算法優(yōu)化的月面巡視器路徑規(guī)劃研究[J]. 王楷文,彭松,劉少創(chuàng),李海飛.  航天器工程. 2019(01)
[2]一種兼顧全局與局部特性的機(jī)器人動態(tài)路徑規(guī)劃算法[J]. 張旭,程傳奇,郝向陽,李建勝,胡鵬.  測繪科學(xué)技術(shù)學(xué)報. 2018(03)
[3]基于改進(jìn)A*算法的移動機(jī)器人安全路徑規(guī)劃[J]. 張紅梅,李明龍,楊樂.  計算機(jī)仿真. 2018(04)
[4]基于鄰接節(jié)點(diǎn)聚合的多層級MQA-A*路徑規(guī)劃算法[J]. 楊肖寧,程承旗,陳波,童曉沖,何靜.  地理信息世界. 2018(01)
[5]摩托化機(jī)動路徑規(guī)劃的改進(jìn)A*算法[J]. 劉凱,呂曉華,李愛光,周全.  測繪科學(xué)技術(shù)學(xué)報. 2017(05)
[6]地形坡度對越野機(jī)動時間影響分析[J]. 袁仁進(jìn),陳剛,王冰冰.  地理信息世界. 2017(06)
[7]計算機(jī)兵棋中越野機(jī)動路徑網(wǎng)絡(luò)分析[J]. 張欣,李培寧,顧明強(qiáng).  地理空間信息. 2017(03)
[8]A*算法的改進(jìn)及并行化[J]. 熊壬浩,劉羽.  計算機(jī)應(yīng)用. 2015(07)
[9]一種利用改進(jìn)A*算法的無人機(jī)航跡規(guī)劃[J]. 占偉偉,王偉,陳能成,王超.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2015(03)
[10]面向路徑優(yōu)化的變分辨率柵格成本表面模型建模方法[J]. 劉震,余洋,李建松,肖少輝.  測繪學(xué)報. 2014(05)

博士論文
[1]無人駕駛車輛運(yùn)動障礙物檢測、預(yù)測和避撞方法研究[D]. 辛煜.中國科學(xué)技術(shù)大學(xué) 2014

碩士論文
[1]復(fù)雜約束條件下航跡規(guī)劃方法研究[D]. 董世建.北京理工大學(xué) 2016
[2]基于改進(jìn)A*算法的游戲地圖尋徑的研究[D]. 周小鏡.西南大學(xué) 2011
[3]路徑規(guī)劃在車輛導(dǎo)航系統(tǒng)中的應(yīng)用研究[D]. 田明星.北京交通大學(xué) 2009
[4]快速路徑尋優(yōu)的GIS網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)設(shè)計及算法研究[D]. 姜艷.復(fù)旦大學(xué) 2008
[5]越野機(jī)動的通道分析模型研究[D]. 張真.解放軍信息工程大學(xué) 2006



本文編號：3130027