呂晟巖 顧海毅 黃沖

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

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

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

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

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

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

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

1.2 人工勢(shì)場(chǎng)路徑規(guī)劃

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

1.3 快速擴(kuò)展隨機(jī)樹(shù)路徑規(guī)劃

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

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

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

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

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

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

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

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

3.總結(jié)

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

參考文獻(xiàn)：

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

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

項(xiàng)目來(lái)源：

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