胡廣雪 鄭亞清 韓洋祺

摘要：針對(duì)移動(dòng)機(jī)器人在不同的工作場(chǎng)景不確定性，設(shè)計(jì)了將相鄰節(jié)點(diǎn)優(yōu)先級(jí)分組與Floyd-Warshall算法相結(jié)合路徑規(guī)劃研究方法。首先，對(duì)全局規(guī)劃A* 算法相鄰節(jié)點(diǎn)優(yōu)先級(jí)分組。其次，綜合環(huán)境和路徑的情況以全局路徑的拐點(diǎn)為局部目標(biāo)點(diǎn)，采用改進(jìn)的Floyd-Warshall算法進(jìn)行局部路徑規(guī)劃，從而使規(guī)劃路徑尋路時(shí)間及轉(zhuǎn)折點(diǎn)次數(shù)優(yōu)于A*算法。最后進(jìn)行仿真驗(yàn)證，仿真結(jié)果表明：該算法有效解決復(fù)雜移動(dòng)環(huán)境的路徑規(guī)劃的問題，提高了機(jī)器人導(dǎo)航路徑規(guī)劃的準(zhǔn)確性和魯棒性。

關(guān)鍵詞：移動(dòng)機(jī)器人;改進(jìn)的A*算法;路徑規(guī)劃

1.引言

隨著智能制造技術(shù)的不斷發(fā)展，機(jī)器人在在野外探測(cè)、工業(yè)流水線制造、物流輸送等多個(gè)領(lǐng)域廣泛應(yīng)用。其中，定位和導(dǎo)航系統(tǒng)是研究機(jī)器人的核心問題。智能移動(dòng)機(jī)器人系統(tǒng)主要由環(huán)境感知、環(huán)境邏輯決策及輔助路徑規(guī)劃系統(tǒng)組成，且導(dǎo)航路徑規(guī)劃是移動(dòng)機(jī)器人性能衡量的重要指標(biāo)。目前也有一些其他導(dǎo)航定位方法，一些學(xué)者采用人工路標(biāo)定位，但此類定位方法需要提前布置導(dǎo)航的室內(nèi)場(chǎng)景[1]。[2]通過改進(jìn)A* 算法的關(guān)鍵節(jié)點(diǎn)實(shí)現(xiàn)了靜態(tài)移動(dòng)環(huán)境下的路徑規(guī)劃。[3-6]根據(jù)已知和未知環(huán)境信息進(jìn)行局部和全局路徑的規(guī)劃。[7]提出了基于二次規(guī)劃改進(jìn)的A*算法，但并未考慮移動(dòng)機(jī)器人的體積和偏轉(zhuǎn)角，實(shí)際應(yīng)用不強(qiáng)。[8]提出跳過節(jié)點(diǎn)搜索策略，減少了計(jì)算過程中訪問節(jié)點(diǎn)數(shù)，加快程序的運(yùn)行速度，但路徑中轉(zhuǎn)折點(diǎn)仍比較多。采用改進(jìn)蟻群算法搜索全局路徑點(diǎn)，但搜索節(jié)點(diǎn)數(shù)據(jù)量太大。提高控制程序運(yùn)算速度，但對(duì)行駛路徑的彎曲程度沒有考慮。

針對(duì)傳統(tǒng)算法計(jì)算量大，由于地下車庫和不同工作廠房復(fù)雜不確定性，為了提高智能移動(dòng)機(jī)器人在位置環(huán)境中精確性，本文采用改進(jìn)的A*算法進(jìn)行智能移動(dòng)機(jī)器人導(dǎo)航路徑規(guī)劃，為實(shí)現(xiàn)高效率的工作提供實(shí)現(xiàn)基礎(chǔ)。

假設(shè)智能移動(dòng)機(jī)器人M在有限個(gè)障礙物的二維柵格平面區(qū)域Y內(nèi)移動(dòng)，以Y的左下角為坐標(biāo)原點(diǎn)，以水平方向?yàn)闄M坐標(biāo)x軸，垂直方向?yàn)榭v坐標(biāo)y軸，建立如圖1直角坐標(biāo)系xOy。其中，xmax、ymax分別為橫縱坐標(biāo)軸方向上的最大值。以移動(dòng)機(jī)器人的步長(zhǎng)s對(duì)坐標(biāo)區(qū)域進(jìn)行劃分行和列的柵格數(shù)。

每個(gè)柵格有相應(yīng)的坐標(biāo)值與其一一對(duì)應(yīng)，將其序號(hào)集定義為，以坐標(biāo)區(qū)域的左上角為原點(diǎn)，由左向右、自上至下，對(duì)二維平面區(qū)域Y進(jìn)行編號(hào)，坐標(biāo)與序號(hào)之間的關(guān)系為

2.改進(jìn)的A*算法

由于傳統(tǒng)的A* 算法存在運(yùn)行求解速度較慢，當(dāng)移動(dòng)機(jī)器人從柵格A移動(dòng)到柵格B時(shí)，考慮到移動(dòng)機(jī)器人有一定的輪廓體積，因此，在紅點(diǎn)處可能會(huì)發(fā)生碰撞，從而造成移動(dòng)機(jī)器人損壞。對(duì)此，本文通過對(duì)傳統(tǒng)的A*算法節(jié)點(diǎn)的擴(kuò)展順序進(jìn)行改進(jìn)，如圖2所示。設(shè)移動(dòng)機(jī)器人當(dāng)前運(yùn)動(dòng)環(huán)境節(jié)點(diǎn)為O，周圍相鄰節(jié)點(diǎn)分別為 A、B、C、D、E、S、W、N。以便降低在實(shí)際移動(dòng)過程中與障礙物發(fā)生碰撞的概率，相鄰兩個(gè)節(jié)點(diǎn)優(yōu)先分組。

上述方法對(duì)A*算法子節(jié)點(diǎn)的選擇優(yōu)化，可以提高移動(dòng)機(jī)器人規(guī)劃路徑的安全性，但路徑規(guī)劃過程中轉(zhuǎn)折次數(shù)較多，行駛路線的不平滑難度增加很多。針對(duì)上述問題問題，在優(yōu)化選擇子節(jié)點(diǎn)的基礎(chǔ)上，將雙向平滑理念引入到Floyd-Warshall 算法中對(duì) A* 算法進(jìn)行改進(jìn)，通過建立兩點(diǎn)之間路徑長(zhǎng)度的二維數(shù)組來計(jì)算最短路徑。將雙向平滑理念引入到 Floyd-Warshall 算法中，即在優(yōu)化正向路徑的基礎(chǔ)上，加入目標(biāo)點(diǎn) T 到起始點(diǎn) K 的反向優(yōu)化。具體改進(jìn)步驟如圖3 所示。

針對(duì)改進(jìn)的A*算法優(yōu)化路徑算法，主要從以下步驟進(jìn)行仿真驗(yàn)證：對(duì)路徑中同一直線上的中間冗余節(jié)點(diǎn)進(jìn)行刪除，僅保留起始點(diǎn)K、拐點(diǎn)和目標(biāo)點(diǎn)T。刪除冗余節(jié)點(diǎn)后的移動(dòng)路徑為 K→p1→p2→p3→T。從起點(diǎn)K開始，在保留節(jié)點(diǎn)pi、pj之間每q步取一節(jié)點(diǎn)，判斷取的節(jié)點(diǎn)與上一路徑節(jié)點(diǎn)之間是否存在障礙物。若有障礙物，則當(dāng)前路徑節(jié)點(diǎn)不變;若無障礙物，則由程序計(jì)算障礙物與節(jié)點(diǎn)pi、pj連線的距離。

根據(jù)柵格的大小將規(guī)劃的路徑安全距離定義為d，當(dāng)d>dOB時(shí)，該路徑可以進(jìn)行選擇，否則該路徑不可選，加入安全距離后的路徑為K→p33→T。

3.仿真結(jié)果驗(yàn)證

為驗(yàn)證上述理論分析及改進(jìn) A* 算法規(guī)劃路徑的有效性，在 Matlab 2010a實(shí)驗(yàn)平臺(tái)下分別對(duì)傳統(tǒng)的 A*算法。其中 d = 0.8 m，q = 0.1 m，柵格大小為1 m。黑色柵格為障礙物區(qū)域，占地圖總面積為19.5%，灰色柵格為遍歷的節(jié)點(diǎn)區(qū)域，兩組柵格地圖路徑規(guī)劃結(jié)果如圖4所示。

由仿真的路徑曲線可得，傳統(tǒng)A*算法所規(guī)劃的移動(dòng)路徑存在斜穿障礙物頂點(diǎn)的不足，適應(yīng)性較差。改進(jìn)后的A*算法在設(shè)定機(jī)器人行駛的安全距離后，規(guī)劃路徑與障礙物的距離始終大于d，從而避免了移動(dòng)機(jī)器人距障礙物較近而發(fā)生碰撞的情況，提高了移動(dòng)機(jī)器人路徑行駛的安全性?；陔p向FloydWarshall改進(jìn)的A*算法折點(diǎn)的數(shù)量較傳統(tǒng)A*算法有所減少，其規(guī)劃的移動(dòng)路徑曲線更加平滑，在實(shí)際應(yīng)用中，有利于減少移動(dòng)機(jī)器人運(yùn)動(dòng)過程中的航向角，有效提高移動(dòng)機(jī)器人運(yùn)動(dòng)的平穩(wěn)性和工作效率，具有一定的實(shí)用價(jià)值。

4.結(jié)論

（1）為提高A*算法的運(yùn)行效率及移動(dòng)機(jī)器人規(guī)劃路徑的安全性，提出對(duì)子節(jié)點(diǎn)的擴(kuò)展的順序進(jìn)行優(yōu)化選擇，將8個(gè)領(lǐng)域節(jié)點(diǎn)劃分為高級(jí)組和一般組，縮短尋優(yōu)路徑的時(shí)間，避免規(guī)劃路徑存在斜穿障礙物頂點(diǎn)問題。

（2）針對(duì)傳統(tǒng)的A*算法搜索路徑轉(zhuǎn)折點(diǎn)個(gè)數(shù)多、路徑曲線不平滑等不足，采用 Floyd-Warshall算法對(duì)路徑曲線進(jìn)行雙向平滑處理，從而減少航向角的次數(shù)，改善行駛路徑的質(zhì)量。

（3）采用Floyd-Warshall算法改進(jìn)后的的A*算法，符合移動(dòng)機(jī)器人的運(yùn)動(dòng)控制，具有實(shí)際的使用價(jià)值。

參考文獻(xiàn)：

[1]黃露.基于人工路標(biāo)的室內(nèi)機(jī)器人導(dǎo)航方法研究與實(shí)現(xiàn)[D].中國科學(xué)技術(shù)大學(xué)，2017.

[2]王帥軍，胡立坤，王一飛.基于改進(jìn)D*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2020，41（4）：7.

[3]Baoye， Song， Zidong， et al. On Global Smooth Path Planning for Mobile Robots using a Novel Multimodal Delayed PSO Algorithm[J]. Cognitive Computation， 2017， 9（1）：5–17.

[4]Chen H ，F(xiàn)ei J . UAV Path Planning Based on Particle Swarm Optimization with Global Best Path Competition[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2017， 32（1）.

[5]Golda A F ，Aridha S ， Elakkiya D . Algorithmic agent for effective mobile robot navigation in an unknown environment[C]// Intelligent Agent & Multi-Agent Systems， 2009. IAMA 2009. International Conference on. IEEE， 2009.

[6]Mohtasham S K ， Abbas S . Adaptive Path Planning for Navigation and Sensing of Micro Aerial Vehicles.? 2016.

[7]楊璐， 汪博涵， 張雪潔. 基于A*算法的AGV路徑規(guī)劃研究[J]. 公路與汽運(yùn)， 2014.

[8]Pal A ， Tiwari R ， Shukla A . Modified A* Algorithm for Mobile Robot Path Planning[M]. Springer Berlin Heidelberg， 2012.