移動機(jī)器人全局路徑規(guī)劃算法綜述

楊 韻，王成彥，巫凱旋，楊詩丹，李佳文（通信作者），翁偉濤

（1 廣東海洋大學(xué)海運(yùn)學(xué)院 廣東 湛江 524005）

（2 廣東海洋大學(xué)海洋工程學(xué)院 廣東 湛江 524005）

0 引言

20 世紀(jì)60 至70 年代，美國斯坦福研究所研制的世界上第一臺能實(shí)現(xiàn)移動的機(jī)器人——Shakey，標(biāo)志著移動機(jī)器人正式誕生，伴隨計(jì)算機(jī)技術(shù)的飛速發(fā)展，各種機(jī)器人導(dǎo)航算法不斷涌現(xiàn)，移動機(jī)器人的發(fā)展也進(jìn)入快車道。隨著自動化技術(shù)的進(jìn)步和發(fā)展，機(jī)器工作逐步取代傳統(tǒng)人力工作，移動機(jī)器人作為高科技自動化工具，可通過內(nèi)置算法完成指定工作，移動機(jī)器人工作的智能化和高效性使之在復(fù)雜的作業(yè)環(huán)境中取代人工，提高作業(yè)安全系數(shù)。

移動機(jī)器人擁有環(huán)境感知、自主定位、路徑規(guī)劃等多種高級功能，其中路徑規(guī)劃是指移動機(jī)器人利用已構(gòu)建的環(huán)境模型，通過路徑規(guī)劃算法計(jì)算得到一條或多條安全系數(shù)高、距離短、平滑的線路，從而保證移動機(jī)器人自主高效地完成路勁規(guī)劃作業(yè)任務(wù)，在救援、智慧交通、自動化生產(chǎn)、航空等領(lǐng)域具有舉足輕重的地位[1]。如圖1 所示，根據(jù)全局路徑規(guī)劃解形式，將其分為完備性規(guī)劃算法和概率完備算法兩大類，根據(jù)算法工作原理又將這兩類算法分為基于圖搜索、基于啟發(fā)式和基于采樣點(diǎn)3 類算法，并結(jié)合已有的研究成果，闡述各算法的優(yōu)勢和局限性。

1 完備性規(guī)劃算法

完備性規(guī)劃算法是指在起始點(diǎn)和目標(biāo)點(diǎn)之間有路徑解的存在，則一定可以得到路徑解；若得不到路徑解，則說明該路徑不存在[2]。現(xiàn)階段，以基于圖搜索為主的完備性規(guī)劃算法主要有：Dijkstra 算法、A*算法；以基于啟發(fā)式為主的完備性規(guī)劃算法主要有：遺傳算法、蟻群算法。

1.1 Dijkstra 算法

Dijkstra 是利用廣度優(yōu)先搜索算法有效解決有向圖最短路徑的全局路徑規(guī)劃算法。該算法設(shè)移動機(jī)器人所在的點(diǎn)為初始節(jié)點(diǎn)，遍歷剩余節(jié)點(diǎn)，將與初始節(jié)點(diǎn)距離最近的節(jié)點(diǎn)加入結(jié)點(diǎn)集合，該集合從初始節(jié)點(diǎn)向外層層擴(kuò)散，直至遍歷圖中所有節(jié)點(diǎn)，并根據(jù)路徑權(quán)重的大小找到一條初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑。

當(dāng)前國內(nèi)外研究學(xué)者重點(diǎn)研究Dijkstra 算法的模型優(yōu)化和減少遍歷節(jié)點(diǎn)數(shù)目。潘成浩等[3]針對傳統(tǒng)Dijkstra 算法難以在障礙密集型的復(fù)雜空內(nèi)搜索到最短路徑的問題，提出松弛Dijkstra 算法。柵格化作業(yè)環(huán)境，將整體環(huán)境離散化為單元環(huán)境，提高對地圖的建模效率。仿真結(jié)果顯示，與采用堆序列實(shí)現(xiàn)的Dijkstra 算法搜索速度對比，驗(yàn)證了松弛Dijkstra 算法的優(yōu)越性。

1.2 A*算法

A*算法是在Dijkstra 算法基礎(chǔ)上進(jìn)行改進(jìn)和優(yōu)化后得到的一種啟發(fā)式搜索算法，設(shè)初始節(jié)點(diǎn)為父節(jié)點(diǎn)，根據(jù)啟發(fā)式函數(shù)搜索得到當(dāng)前代價(jià)最低的節(jié)點(diǎn)作為子節(jié)點(diǎn)，直至搜索到目標(biāo)節(jié)點(diǎn)，最終規(guī)劃獲得一條代價(jià)最小的路徑，具有搜索速度快和較強(qiáng)的環(huán)境適應(yīng)力。

王紅衛(wèi)等[4]針對在柵格模型下現(xiàn)有A*算法規(guī)劃得到不平滑路徑的局限，提出前后節(jié)點(diǎn)之間無障礙物即相接，從而構(gòu)建平滑A*模型的方法。仿真結(jié)果表明，改進(jìn)后的算法在規(guī)劃的路徑長度較原算法降低約5%，折線數(shù)量減少約50%，累計(jì)轉(zhuǎn)角度數(shù)減少30%～60%。

1.3 遺傳算法

遺傳算法是一種模擬自然界物種進(jìn)化和遺傳機(jī)制的計(jì)算模型，該算法參考達(dá)爾文的“物種進(jìn)化論”和孟德爾的“生物遺傳學(xué)”，對自然選擇和遺傳因子進(jìn)行交叉、變異等遺傳現(xiàn)象進(jìn)行仿真，模擬生物朝著最優(yōu)的方向發(fā)展進(jìn)而尋找最優(yōu)解的算法，其本質(zhì)是一種基于基因遺傳學(xué)原理的全局搜索優(yōu)化算法。因其自身最大的優(yōu)點(diǎn)是能在搜索過程中自適應(yīng)迭代優(yōu)化得到路徑最優(yōu)解，因而它與其他算法相融合成為目前人工智能科學(xué)領(lǐng)域的重要研究對象，并且廣泛應(yīng)用于單一移動機(jī)器人的路徑規(guī)劃研究領(lǐng)域。

段俊花等[5]針對GA 算法存在難以解決大規(guī)模計(jì)算量而陷入“早熟”和因缺乏信息反饋而導(dǎo)致搜索速度慢等缺陷，常利用混合型的GA 算法。GA 算法結(jié)合圖搜索算法，這樣即減少了搜索的盲目性，又能優(yōu)化原單一算法，實(shí)驗(yàn)結(jié)果表明，圖搜索算法能有效刪除冗余算子，二者相結(jié)合的算法較原GA 算法在求解最優(yōu)路徑的次數(shù)上從363 次增加到492 次，尋優(yōu)概率從72.6%提升至98.4%。

1.4 蟻群算法

蟻群算法最初是從螞蟻覓食行為中獲取靈感進(jìn)而設(shè)計(jì)的一種啟發(fā)式仿生智能優(yōu)化算法。螞蟻在覓食道路上釋放信息素，隨著時(shí)間的推移，信息素濃度與路徑長度成反比，螞蟻對信息素具有感知能力，后來的螞蟻以信息素濃度大小作為判斷依據(jù)，引導(dǎo)自身運(yùn)動并找尋到最優(yōu)覓食路徑。此過程具有正反饋調(diào)節(jié)機(jī)制，因此該算法能夠快速搜索到最短路徑。

螞蟻覓食路徑優(yōu)化圖見圖2。

封聲飛等[6]針對蟻群算法發(fā)揮正反饋機(jī)制時(shí)間長、易陷入局部最優(yōu)等問題提出一種自適應(yīng)蟻群算法。該算法在蟻群算法的基礎(chǔ)上調(diào)整初始化信息素，引入轉(zhuǎn)角約束以限制算法隨機(jī)性，并對路徑尖峰進(jìn)行平滑處理。實(shí)驗(yàn)結(jié)果證明，改進(jìn)后的算法迭代次數(shù)降低至原來的1/4 到1/3，規(guī)劃得到的路徑更加平滑，保證了移動機(jī)器人運(yùn)動的平衡性。

2 概率完備算法

概率完備算法是指在起始點(diǎn)和目標(biāo)點(diǎn)之間存在路徑解，只要規(guī)劃或者搜索時(shí)間足夠長，則最終能找到一條路徑解[7]?，F(xiàn)階段，以基于采樣點(diǎn)的概率完備算法主要有：PRM 算法、RRT 算法。

2.1 PRM 算法

針對移動機(jī)器人在高維空間和復(fù)雜約束環(huán)境中運(yùn)動軌跡受到動態(tài)約束的問題，20 世紀(jì)90 年代提出了PRM（隨機(jī)路標(biāo)圖法），是概率完備算法中基于采樣點(diǎn)的全局路徑規(guī)劃算法，將連續(xù)空間轉(zhuǎn)化為離散空間，使得路徑規(guī)劃與搜索算法的準(zhǔn)確度有關(guān)而與空間復(fù)雜程度無關(guān)。劉洋等[8]針對傳統(tǒng)PRM 算法在狹窄空間難以進(jìn)行路徑規(guī)劃的缺陷，提出一種結(jié)合人工勢場的PRM 算法。該方法在地圖中引入人工勢場以增加非障礙區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)量。仿真結(jié)果顯示，改進(jìn)后的算法提高了對節(jié)點(diǎn)的空間利用率，在采樣次數(shù)不變的情況下更好地解決移動機(jī)器人在狹小空間中難以快速規(guī)劃出最優(yōu)路徑的問題。

2.2 RRT 算法

RRT 算法最初由Lavalle 提出，此算法具有靈活快速搜索的能力，且無需建立環(huán)境模型和設(shè)置任何參數(shù)，在復(fù)雜環(huán)境中具有搜索速度快的優(yōu)勢，因此在移動機(jī)器人路徑規(guī)劃技術(shù)中被廣泛使用。王坤等[9]針對RRT-Connect 在存規(guī)劃高質(zhì)量路徑時(shí)運(yùn)算時(shí)間長、隨機(jī)性大和步長不靈活等問題，提出一種基于改進(jìn)的雙向快速擴(kuò)展隨機(jī)樹算法。仿真對比實(shí)驗(yàn)顯示，改進(jìn)后的算法與原算法相比在迭代次數(shù)上減少32.3%，在規(guī)劃路徑的速度上提高了50%。

3 移動機(jī)器人全局路徑規(guī)劃技術(shù)發(fā)展趨向

3.1 多種算法融合優(yōu)勢互補(bǔ)

在現(xiàn)實(shí)應(yīng)用中，單一算法均具有局限性，僅靠一種算法難以滿足所有任務(wù)場景，但直接研究一種新的具有多功能的算法難度大。國內(nèi)外許多學(xué)者通過實(shí)驗(yàn)證明，不同算法在不同任務(wù)場景中具有差異性和各自的優(yōu)勢，因此多種算法的相互融合能更好地形成優(yōu)勢互補(bǔ)、取長補(bǔ)短，最大限度發(fā)揮各自算法的性能。

3.2 多移動機(jī)器人與智能化信息技術(shù)協(xié)同路徑規(guī)劃

隨著工業(yè)自動化和科學(xué)技術(shù)日新月異的發(fā)展，機(jī)器人被廣泛應(yīng)用于各生產(chǎn)領(lǐng)域，移動機(jī)器人的工作任務(wù)也日益復(fù)雜，單機(jī)器人已難以滿足當(dāng)今社會多元復(fù)雜的需求，因此需要多個(gè)機(jī)器人之間進(jìn)行協(xié)同規(guī)劃，在保證任務(wù)安全有序進(jìn)行的同時(shí)提高生產(chǎn)效率。在實(shí)際生產(chǎn)應(yīng)用中，單機(jī)器人無法滿足工作需求，而多機(jī)器人協(xié)作又有著單機(jī)器人無法媲美的優(yōu)勢[10]。

3.3 移動機(jī)器人傳感信息對算法敏感度的提升

傳感器是移動機(jī)器人與外界環(huán)境感知的交互信息，也是機(jī)器人系統(tǒng)控制的基礎(chǔ)。移動機(jī)器人通過安裝雙目視覺相機(jī)、激光雷達(dá)避障、GPS 等傳感器感知并獲取外界環(huán)境信息從而進(jìn)行地圖模型的構(gòu)建、識別障礙物以及提供精確的位置信息，然后算法進(jìn)行路徑規(guī)劃[11]。整個(gè)過程中，各傳感器對收集到的信息進(jìn)行分析處理，并剔除冗余信息，刪除錯(cuò)誤信息。最后，算法整合各傳感器的有效信息，建立并提高模型精度，從而提高路徑規(guī)劃算法的避障和規(guī)劃能力。

4 討論

針對上述6 種算法進(jìn)行簡要分析，羅列每個(gè)算法的優(yōu)缺點(diǎn)、規(guī)劃后的路徑是否最優(yōu)以及算法適用范圍，結(jié)果見表1。

表1 6 種全局路徑規(guī)劃算法總結(jié)表

5 結(jié)語

隨著智能技術(shù)和工業(yè)自動化的發(fā)展，移動機(jī)器人全局路徑規(guī)劃是國內(nèi)外機(jī)器人領(lǐng)域的研究熱點(diǎn)之一。本文首先簡要介紹移動機(jī)器人的產(chǎn)生與發(fā)展，然后對當(dāng)今全局路徑規(guī)劃算法的應(yīng)用領(lǐng)域及他人對算法的改進(jìn)優(yōu)化進(jìn)行綜述，最后從單一算法性能的優(yōu)化、多算法優(yōu)勢互補(bǔ)融合、多機(jī)器人協(xié)同規(guī)劃、結(jié)合傳感器信息4 個(gè)方面提出路徑規(guī)劃技術(shù)未來改進(jìn)和優(yōu)化方向的評價(jià)，作為路徑規(guī)劃算法當(dāng)前的研究及其未來發(fā)展奠定的參考依據(jù)。