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

【文章來(lái)源】：測(cè)繪科學(xué)技術(shù)學(xué)報(bào). 2019,36(02)北大核心

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

【部分圖文】：

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

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

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

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

博士論文
[1]無(wú)人駕駛車輛運(yùn)動(dòng)障礙物檢測(cè)、預(yù)測(cè)和避撞方法研究[D]. 辛煜.中國(guó)科學(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è)計(jì)及算法研究[D]. 姜艷.復(fù)旦大學(xué) 2008
[5]越野機(jī)動(dòng)的通道分析模型研究[D]. 張真.解放軍信息工程大學(xué) 2006



本文編號(hào)：3130027