發(fā)布時間：2021-01-02 01:51

　　本文描繪了物流機器人的路徑規(guī)劃問題。針對標(biāo)準(zhǔn)A*算法的路徑規(guī)劃時間長、計算節(jié)點多的問題,提出了在標(biāo)準(zhǔn)A*算法的基礎(chǔ)山,使用改進的雙向搜索的A*算法。通過使用MATLAB進行仿真和實驗平臺進行實驗對標(biāo)準(zhǔn)A*算法和優(yōu)化后的A*算法進行了對比,結(jié)果表明:改進的A*算法比標(biāo)準(zhǔn)的A*算法進行路徑規(guī)劃的時間更短,并且使用的節(jié)點更少。 

【文章來源】：軟件. 2020年03期

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

【部分圖文】：

標(biāo)準(zhǔn)A*算法仿真結(jié)果Fig.2SimulationresultsofthestandardA-staralgorithm

圖Fig.1ImprovedA-staralgorithmflowchart兩個，一個是使用頭尾雙向搜索的辦法進行節(jié)點的擴展；另一個是選取最低g值的臨近點作為前驅(qū)，并增加啟發(fā)函數(shù)值權(quán)重。為了驗證改進后的A*算法的性能，本文使用MATLAB分別對標(biāo)準(zhǔn)A*算法和改進后的A*算法進行仿真實驗。標(biāo)準(zhǔn)A*算法和改進后的A*算法的仿真結(jié)果分別如圖2和圖3所示。OPEN集障礙物路徑CLOSE集目標(biāo)點起始點圖2標(biāo)準(zhǔn)A*算法仿真結(jié)果Fig.2SimulationresultsofthestandardA-staralgorithm目標(biāo)點OPEN集路徑障礙物起始點圖3改進的A*算法仿真結(jié)果Fig.3ImprovedA-staralgorithmsimulationresults在標(biāo)準(zhǔn)A*算法和改進的A*算法中，進行仿真的柵格地圖的大小為20×20的，綠色的網(wǎng)格表示路徑規(guī)劃的起始點，其位置可以用坐標(biāo)（1,1）表示，紅色的網(wǎng)格表示路徑規(guī)劃的目標(biāo)點，其位置可以使用坐標(biāo)（20,20）表示，黑色網(wǎng)格表示柵格地圖中的障礙物，黃色網(wǎng)格代表OPEN集合的節(jié)點，藍色網(wǎng)格代表CLOSE集合的節(jié)點。靚藍色表示最終搜索到的路徑。為了驗證改進后的A*算法的有效性，分別在上圖柵格地圖中選取50組不同的的起始點和目標(biāo)點進行算法的對比，主要從三個方面驗證改進后算法的有效性，路徑規(guī)劃時間、路徑規(guī)劃長度和擴展節(jié)點數(shù)目，結(jié)果圖4至6所示。將標(biāo)準(zhǔn)A*算法與改進后的A*算法的搜索時間和搜索路徑長度以及擴展節(jié)點數(shù)目進行統(tǒng)計，結(jié)果顯示在表1中。通過上述圖和表可以得到，通過使用雙向A*算法和確定一個初始化的較大的g值，取消CLOSE集，將最低g值得臨近點作為前驅(qū)，并增加啟發(fā)函圖4標(biāo)準(zhǔn)A*算法與改進后的A*算法搜索時間比較Fig.4ComparisonofthesearchtimebetweenthestandardandtheimprovedA-staral

?格代表CLOSE集合的節(jié)點。靚藍色表示最終搜索到的路徑。為了驗證改進后的A*算法的有效性，分別在上圖柵格地圖中選取50組不同的的起始點和目標(biāo)點進行算法的對比，主要從三個方面驗證改進后算法的有效性，路徑規(guī)劃時間、路徑規(guī)劃長度和擴展節(jié)點數(shù)目，結(jié)果圖4至6所示。將標(biāo)準(zhǔn)A*算法與改進后的A*算法的搜索時間和搜索路徑長度以及擴展節(jié)點數(shù)目進行統(tǒng)計，結(jié)果顯示在表1中。通過上述圖和表可以得到，通過使用雙向A*算法和確定一個初始化的較大的g值，取消CLOSE集，將最低g值得臨近點作為前驅(qū)，并增加啟發(fā)函圖4標(biāo)準(zhǔn)A*算法與改進后的A*算法搜索時間比較Fig.4ComparisonofthesearchtimebetweenthestandardandtheimprovedA-staralgorithm

【參考文獻】：
期刊論文
[1]基于改進A*算法的移動機器人路徑規(guī)劃[J]. 趙曉,王錚,黃程侃,趙燕偉.  機器人. 2018(06)
[2]基于改進A*算法的最優(yōu)路徑搜索[J]. 朱云虹,袁一.  計算機技術(shù)與發(fā)展. 2018(04)
[3]基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃[J]. 王殿君.  清華大學(xué)學(xué)報(自然科學(xué)版). 2012(08)
[4]機器人導(dǎo)航系統(tǒng)中的路徑規(guī)劃算法[J]. 黃玉清,梁靚.  微計算機信息. 2006(20)
[5]雙向啟發(fā)式圖搜索算法BFFRA[J]. 王士同.  電子學(xué)報. 1990(06)

碩士論文
[1]基于2D激光雷達的移動機器人關(guān)鍵技術(shù)研究[D]. 胡志遠.廣西大學(xué) 2017
[2]基于ROS的移動機器人自主定位與導(dǎo)航方法研究[D]. 王強.浙江工業(yè)大學(xué) 2017



本文編號：2952412