移動機器人路徑規(guī)劃算法的研究優(yōu)化

呂晟巖 顧海毅 黃沖

摘要：移動機器人的路徑規(guī)劃技術(shù)是機器人研究非常重要的研究內(nèi)容。本文介紹了移動機器人路徑規(guī)劃的相關(guān)概念并介紹了當(dāng)前國內(nèi)外的研究進展，并對比了傳統(tǒng)和現(xiàn)代機器人關(guān)于其路徑規(guī)劃的研究差異，對今后的路徑規(guī)劃算法研究具有一定參考價值。

關(guān)鍵詞：移動機器人;路徑規(guī)劃算法;螢火蟲自由變異

近年來，國內(nèi)外針對智能移動機器人室內(nèi)移動路徑算法方面的應(yīng)用積極展開了相關(guān)的課題研究，并取得了相當(dāng)卓越的成果。英國人休伯特·布茲（Hubert Cecil Booth）在1901年發(fā)明了真空吸塵器，成為掃地機器人的前世。 2002年9月，iRobot公司于推出的Roomba是掃地機器人發(fā)展史上的里程碑式事件。從2015年左右開始發(fā)展，國內(nèi)倉儲機器人行業(yè)的熱度從來沒有真正降溫過。美國德雷克賽爾大學(xué)學(xué)生發(fā)明可用于核事故中拯救人類的機器人，它可以從雙腳行進的方式轉(zhuǎn)換至四足行進的方式，并擁有極其強壯的雙手可用于抓取物體和攀爬臺階。移動機器人路徑規(guī)劃主要需要實現(xiàn)點對點的可行路徑、障礙物的繞行、行走路徑的優(yōu)化，使得選擇的路徑是所有可行路徑中最短最平滑的。本文分別從傳統(tǒng)和現(xiàn)代的機器人路徑規(guī)劃兩個方面進行研究介紹。

1.傳統(tǒng)機器人移動路徑規(guī)劃方式

關(guān)于移動機器人的路徑規(guī)劃有很多種方式，然而機器人路徑規(guī)劃中所選取路徑的運行效率和選取軌道的好壞，對機器人最終的任務(wù)完成情況都起著決定性的作用。一般由于機器人移動的空間環(huán)境約束，關(guān)于其路徑規(guī)劃一般會分為離散和連續(xù)路徑規(guī)劃兩種方式。

1.1 A*算法路徑規(guī)劃

A*算法是移動機器人路徑規(guī)劃領(lǐng)域非常經(jīng)典的一種規(guī)劃方式，應(yīng)用與此機器人的移動路徑主要由估值函數(shù)來決定。A*算法的具體運行原理是從機器人的運動起始點作為初始點，以此搜索周圍的八個節(jié)點，然后運用估價函數(shù)計算八個節(jié)點的最低代價值的點作為下個運行節(jié)點，之后以此循環(huán)過程直至到達終止點。

1.2 人工勢場路徑規(guī)劃

人工勢場法是由Khatib在二十世紀(jì)提出，其基本的實現(xiàn)方法是將機器人的路徑規(guī)劃同磁場相結(jié)合，同時將人工勢場函數(shù)用作機器人的環(huán)境模擬狀態(tài)。并將終止點的吸引磁場，和運行過程中的潛在運行障礙物體的排斥磁場，兩相復(fù)合作為參照指標(biāo)。人工勢場由于其實時能力和控制簡潔的優(yōu)勢在機器人路徑規(guī)劃領(lǐng)域應(yīng)用廣泛。

1.3 快速擴展隨機樹路徑規(guī)劃

這是一種搜索算法，其實在采集樣本的基礎(chǔ)上進行路徑規(guī)劃，一般適用于三維空間的目標(biāo)搜尋。其設(shè)計原理是將空間中的某點作為起始點，然后規(guī)定一定原則，在原則約束下以起始點來確定一個新的節(jié)點，重復(fù)直至找到目標(biāo)終止點?？焖匐S機樹算法是一種較為迅捷搜索的方式，其優(yōu)點明顯，主要體現(xiàn)在其較強的搜索能力，并且運用快速拓展隨機樹的路徑規(guī)劃對路徑運行環(huán)境沒有限制要求。但是在動態(tài)環(huán)境中會有一定局限性。

2. 現(xiàn)代機器人移動路徑規(guī)劃方式

2.1蟻群算法路徑規(guī)劃

蟻群算法是在20世紀(jì)90年代由Macro Dorigo提出，這是一種利用隨機搜索的方法，螞蟻外出覓食總是會體現(xiàn)覓食路線趨向最優(yōu)選擇的趨向性?；舅悸肥茄芯堪l(fā)現(xiàn)螞蟻在外出的時候會在行走的路線上，對路線進行標(biāo)記，并發(fā)出信息素告示其他螞蟻，螞蟻會有對同類的信息素感知的能力，并會根據(jù)信息素的濃度高低進行選擇，在眾多路線中，螞蟻會選擇信息濃度最高的線路，形成正態(tài)反饋，從而濃度高的線路，信息素濃度會越來越高，濃度低的線路信息素會越來越少，最終蟻群由于正反饋機制，會選擇最優(yōu)的線路。

2.2 遺傳算法路徑規(guī)劃

該算法是以基因?qū)W原理為理論基礎(chǔ)，對路線選擇進行優(yōu)化。運用該算法，首先會先隨機產(chǎn)生一個初始點，在設(shè)定的選擇函數(shù)，還有環(huán)境條件等多種條件的綜合約束下，選擇最優(yōu)的路徑規(guī)劃。該種方式借鑒了進化論的觀點，將即將解決的問題比作一個種群，再各種函數(shù)條件的約束下，種群不斷發(fā)展繁衍，在繁衍的過程中實現(xiàn)物種的進化，最終實現(xiàn)優(yōu)勝劣汰的目標(biāo)。該種方法特點是有向且高效，不同以往無向的搜索方式，因此能夠選擇最優(yōu)的搜索方向，進而能較快的選擇出最優(yōu)的路徑規(guī)劃。但是該種方法需要的約束條件比較多，需要的參數(shù)也比較多，在復(fù)雜的路徑環(huán)境下容易出現(xiàn)錯誤。

2.3 粒子群算法路徑規(guī)劃

粒子群算法是在20世紀(jì)末提出，該算法是一種現(xiàn)代的路徑優(yōu)化算法，該算法借鑒了鳥類外出覓食或者飛行過程中，之間的通行方式。粒子群算法是將空間中的某一個地點作為初始點，然后在設(shè)定的函數(shù)條件判斷下，決定該點是否是有利點，然后在同類群體的路徑記憶進行篩選，選擇最優(yōu)路徑。粒子群的路徑規(guī)劃方法有很多優(yōu)點，其中最為突出的優(yōu)點是該法需要的參數(shù)約束條件比較少，系統(tǒng)的運行效率、反應(yīng)能力比較高;缺點是粒子群算法的路徑規(guī)劃在全局域環(huán)境路徑判斷較好，但是在局部環(huán)境的反應(yīng)上比較差。但是粒子群算法的運行簡單、收斂迅速、參數(shù)約束較少等眾多優(yōu)點，是現(xiàn)在機器人路徑規(guī)劃領(lǐng)域一個熱點研究方向。

3.總結(jié)

移動機器人的路徑規(guī)劃是為了幫機器人規(guī)劃線路從起點最終到達終點，并且所選擇的路徑運行方式能避開路徑中的障礙物，且路徑選擇達到最佳。本文對移動機器人路徑規(guī)劃算法應(yīng)用方式的發(fā)展做了一個介紹，希望能對以后移動機器人的路徑規(guī)劃發(fā)展起到一定參考意義。

參考文獻：

[1]Feiyi Xu，Haolun Li，Chi-Man Pun，Haidong Hu，Yujie Li，Yurong Song，Hao Gao. A new global best guided artificial bee colony algorithm with application in robot path planning[J]. Applied Soft Computing Journal，2020，88.

[2]韓顏，許燕，周建平.粒子群-蟻群融合算法的機器人路徑規(guī)劃[J].組合機床與自動化加工技術(shù)，2020（02）：47-50.

[3]李海彬，沈顯慶.改進蟻群算法的路徑規(guī)劃研究[J].電子測試，2020（03）：38-39+87.

項目來源：

本文系江蘇大學(xué)2019年度大學(xué)生科研立項項目，項目編號18A088