移動(dòng)機(jī)器人導(dǎo)航的路徑規(guī)劃策略*

張廣帥，韋建軍，劉銓權(quán)，王春寶，，3※，王 同，毛志賢，羅承開

（1.廣西科技大學(xué)機(jī)械與交通工程學(xué)院，廣西柳州 545000；2.深圳市老年醫(yī)學(xué)研究所，廣東深圳 518035；3.深圳大學(xué)第一附屬醫(yī)院，廣東深圳 518035）

0 引言

路徑規(guī)劃指智能機(jī)器人能夠在自由位形空間中尋找一條無(wú)碰撞路徑使其從起始位置到達(dá)目標(biāo)位置的運(yùn)動(dòng)，即滿足一定約束條件的優(yōu)化問(wèn)題。智能機(jī)器人在娛樂(lè)、醫(yī)療、采礦、救援、物流等方面得到了廣泛的應(yīng)用，其結(jié)構(gòu)簡(jiǎn)單，造價(jià)成本低，能夠自主完成任務(wù)。因此，研究智能機(jī)器人技術(shù)具有重要的意義。

近些年來(lái)，隨著科學(xué)技術(shù)和移動(dòng)智能領(lǐng)域不斷發(fā)展，智能移動(dòng)機(jī)器人成為當(dāng)下研究學(xué)者討論熱點(diǎn)話題。國(guó)內(nèi)外專家和研究學(xué)者在其領(lǐng)域取得了較大的突破，但這類研究綜述極少，而最近相關(guān)的綜述只列舉出一些路徑規(guī)劃簡(jiǎn)要的分析，缺乏國(guó)內(nèi)外最新的研究成果［1－5］。與現(xiàn)有的綜述不同，本文從算法的完備性和概率完備性兩方面進(jìn)行分析，重點(diǎn)列舉了典型算法的具體原理和最新的研究成果。

本文在閱讀當(dāng)前最新研究成果的基礎(chǔ)上，論述算法完備性和概率完備性兩大類路徑規(guī)劃方法，列舉出各類典型算法的最新進(jìn)展并概述其優(yōu)缺點(diǎn)。最后對(duì)各類算法現(xiàn)有研究分析和總結(jié)，展望未來(lái)智能機(jī)器人發(fā)展的趨勢(shì)。

1 路徑規(guī)劃算法的描述

1.1 路徑定義

路徑規(guī)劃是由智能機(jī)器人自身攜帶的傳感器探索環(huán)境空間信息、障礙物分配信息等一系列的約束條件作出的行為規(guī)劃。智能機(jī)器人在環(huán)境空間中的運(yùn)動(dòng)大致按照“任務(wù)——感知——建?！?guī)劃——執(zhí)行”的過(guò)程依次進(jìn)行［6］，如圖1所示。智能機(jī)器人運(yùn)動(dòng)過(guò)程中，安全路徑規(guī)劃（檢測(cè)障礙和避開障礙）是智能機(jī)器人的核心部分。因此，在簡(jiǎn)單和復(fù)雜的環(huán)境中實(shí)現(xiàn)智能機(jī)器人路徑規(guī)劃具有重要意義。

圖1 移動(dòng)機(jī)器人運(yùn)動(dòng)過(guò)程

1.2 路徑規(guī)劃的研究方案

通過(guò)對(duì)空間離散化處理將智能路徑規(guī)劃方法分為完備性和概率完備性兩類［7］，如圖2所示。完備性是指若在空間中起點(diǎn)位置與目標(biāo)位置之間有可行路徑解存在，那么一定可得路徑解；若得不到路徑可行解則說(shuō)明空間不存在解，典型的方法有Voronoi圖法、A*、螞蟻算法等。概率完備性是指若空間中起始位置與目標(biāo)位置之間有可行解存在，只要搜索足夠長(zhǎng)的時(shí)間一定可以得到可行解，典型的算法有RRT和PRM算法。

圖2 路徑規(guī)劃方案

1.3 性能分析

表1所示為常見(jiàn)路徑算法的比較，并分析各類算法的優(yōu)缺點(diǎn)及適用范圍。

表1 路徑算法對(duì)比

2 完備性路徑規(guī)劃

2.1 行車圖法

行車圖法是由障礙物的幾何形狀進(jìn)行空間分解，采用一維曲線網(wǎng)格表示環(huán)境空間中的連通性，加入起始位置與目標(biāo)位置后，在一維無(wú)向連通圖中尋找一條無(wú)碰撞路徑?？梢晥D法和Voronoi圖法是兩種典型方法。

可視圖法由所有連接可見(jiàn)頂點(diǎn)對(duì)的邊組成，其初始位置和目標(biāo)位置也可作為定點(diǎn)，如圖3（a）所示。Voronoi圖法是可視圖法的一種延伸，其規(guī)劃思想是取障礙物間的中間點(diǎn)，最大化障礙物與機(jī)器人之間的距離，如圖3（b）所示。

圖3 行車圖法

可視圖法路徑規(guī)劃原理簡(jiǎn)單，特別適用于描述多邊形物體，但該方法所得路徑過(guò)于靠近障礙物，路徑規(guī)劃的安全系數(shù)不高。劉婭［8］提出凹凸點(diǎn)法克服路徑的平滑性問(wèn)題，智能移動(dòng)機(jī)器人運(yùn)動(dòng)至障礙物邊緣突然方向變化導(dǎo)致能量消耗，該方法通過(guò)線段相交線和節(jié)點(diǎn)凹凸性判斷簡(jiǎn)化障礙物的環(huán)繞、嵌套等復(fù)雜變化，提高了路徑規(guī)劃效率，改善了路徑平滑性。Bhattacharya P［9］提出尺寸虛擬放大算法，在路徑規(guī)劃過(guò)程中將智能機(jī)器人結(jié)構(gòu)尺寸虛擬放大，使其減少接觸障礙物區(qū)域，提高安全系數(shù)。許斯軍［10］提出采用切線圖法對(duì)環(huán)境空間進(jìn)行可視圖建模，通過(guò)目標(biāo)導(dǎo)向啟發(fā)函數(shù)計(jì)算通路路徑。采用膨脹算法對(duì)各個(gè)通路路徑進(jìn)行迭代，減少了智能移動(dòng)機(jī)器人與障礙物的接觸區(qū)域。

相對(duì)于可視圖法，Voronoi圖法的安全系數(shù)高，但存在路徑長(zhǎng)度缺陷。張景昱［11］提出區(qū)域分割Voronoi圖法，利用傳感器的感知能力對(duì)區(qū)域進(jìn)行精準(zhǔn)劃分，根據(jù)區(qū)域內(nèi)障礙物的數(shù)量對(duì)區(qū)域賦予不同權(quán)重，利用權(quán)重值的大小填補(bǔ)Voronoi圖法的覆蓋空洞，該算法可以覆蓋整個(gè)環(huán)境空間。Masehian E［12］提出勢(shì)場(chǎng)法與Voronoi相結(jié)合路徑規(guī)劃方法，將障礙物間中間點(diǎn)進(jìn)行約束處理并作為吸引磁場(chǎng)方向，智能機(jī)器人在吸引磁場(chǎng)的作用下自主運(yùn)動(dòng)，采用局部路徑磁場(chǎng)對(duì)路徑的平滑性有很大的提高。朱利［13］提出一種基于Voronoi圖質(zhì)心多無(wú)人機(jī)協(xié)同區(qū)域算法，通過(guò)創(chuàng)建數(shù)學(xué)模型建立評(píng)估指標(biāo)，針對(duì)動(dòng)態(tài)環(huán)境變化提出DCPS策略，該策略將V圖質(zhì)心用于引導(dǎo)無(wú)人機(jī)朝向目標(biāo)點(diǎn)運(yùn)動(dòng)，從而提高搜索效率，提高算法的計(jì)算效率。

2.2 單元分解法

1968年，W E Howden首次將單元分解法應(yīng)用于早期移動(dòng)機(jī)器人發(fā)展中，是一種最常見(jiàn)的環(huán)境建模方法。單元分解法核心思想是將位形空間劃分為若干個(gè)小的區(qū)域，每個(gè)區(qū)域作為一個(gè)單元，單元之間的相鄰關(guān)系為邊構(gòu)成一張連通圖。單元分解法共有三種典型方法：精確單元分解、近似單元分解和可變大小單元分解。

精確單元?jiǎng)澐謾C(jī)器人無(wú)需考慮每個(gè)單元的具體位置，只需考慮如何從一個(gè)單元移動(dòng)至另一單元即可，如圖4（a）所示；近似單元分解需考慮環(huán)境的疏密度和物體形狀的復(fù)雜程度如圖4（b）所示；可變大小單元分解是近似單元分解的一種改進(jìn)方式，將環(huán)境空間遞歸劃分為4個(gè)大小的子區(qū)域，直到每個(gè)子區(qū)域所包含的基本元素完全被占（用“1”表示）或完全空閑（用“0”表示），如圖4（c）所示。

圖4 單元分解法

單元分解法計(jì)算原理簡(jiǎn)單，但環(huán)境的清晰度與單元數(shù)量相關(guān)，若單元數(shù)量較多時(shí)，環(huán)境信息較清楚，而此時(shí)需要較大的存儲(chǔ)空間，規(guī)劃速度降低；若單元數(shù)量較少時(shí)，無(wú)法描述整個(gè)環(huán)境信息，精確度難以保證。Zelinsky［14］提出距離變換單元算法，該算法將環(huán)境空間構(gòu)建成一個(gè)數(shù)值距離結(jié)構(gòu)地圖，將當(dāng)前移動(dòng)位置單元與未覆蓋單元建立關(guān)聯(lián)路徑，探索選擇所有無(wú)障礙路徑柵格，由代價(jià)函數(shù)評(píng)估無(wú)障礙路徑并選取最優(yōu)路徑。于洪斌等［15］提出記憶單元法，采用單元分解法劃分環(huán)境空間時(shí)，對(duì)單元節(jié)點(diǎn)添加記憶力算法，使兩單元節(jié)點(diǎn)之間建立一定的內(nèi)在關(guān)系并形成記憶力反饋信息，通過(guò)反饋信息最終形成一條最優(yōu)路徑。劉慶周等［16］提出A*柵格法，采用單元分解法建立環(huán)境空間模型，通過(guò)A*算法評(píng)估公式對(duì)單元路徑節(jié)點(diǎn)進(jìn)行評(píng)估，使路徑規(guī)劃更具有傾向性，提高路徑規(guī)劃效率。王文學(xué)［17］將單元Morphin

算法應(yīng)用于城市復(fù)雜環(huán)境中，Morphin算法設(shè)置一組運(yùn)動(dòng)基元確定可達(dá)狀態(tài)并構(gòu)建搜索樹，使其可以在同一柵格內(nèi)建立多個(gè)搜索節(jié)點(diǎn)，能夠很好地處理動(dòng)態(tài)環(huán)境的不確定性，提高了路徑平滑性。Borenstein等［18］提出柵格向量直方圖法，如圖5所示。采用近似單元分解法構(gòu)建環(huán)境地圖，通過(guò)機(jī)器人自身配備的傳感器檢測(cè)每個(gè)柵格加權(quán)值變化，識(shí)別所有可以讓移動(dòng)機(jī)器人通過(guò)的無(wú)障礙通道并對(duì)每個(gè)通道計(jì)算移動(dòng)成本，選擇最佳路徑。

圖5 檢測(cè)加權(quán)值

2.3 A*算法

A*算法是基于優(yōu)先級(jí)定義的廣度優(yōu)先搜索算法，由評(píng)估函數(shù)在連通圖中尋找最優(yōu)路徑，如圖6所示。A*算法采用代價(jià)函數(shù)評(píng)估節(jié)點(diǎn)的質(zhì)量，算法將代價(jià)函數(shù)最小值作為下一擴(kuò)展節(jié)點(diǎn)，以此進(jìn)行疊加直至目標(biāo)點(diǎn)。

圖6 A*算法

A*算法可以遍歷所有可到達(dá)的節(jié)點(diǎn)，易于實(shí)現(xiàn)和計(jì)算，因此被廣泛應(yīng)用于各種路徑規(guī)劃問(wèn)題；但A*算法采用曼哈頓距離和歐里幾何距離算法存在搜索節(jié)點(diǎn)過(guò)多、路徑平滑性差、只適用靜態(tài)環(huán)境搜索等一系列問(wèn)題。針對(duì)A*只適用于靜態(tài)路徑規(guī)劃，2004年Koenig和Likhachev提出一種參考人工智能增量搜索LPA*算法將其用于最短路徑動(dòng)態(tài)搜索。但此方法只針對(duì)起始點(diǎn)和目標(biāo)點(diǎn)固定的情況。

張浩杰等［19］提出變維度增量啟發(fā)式（AD*算法）路徑規(guī)劃方法，將移動(dòng)機(jī)器人運(yùn)動(dòng)過(guò)程中受到幾何運(yùn)動(dòng)約束區(qū)域采用高維狀態(tài)空間，無(wú)影響的區(qū)域采用低維狀態(tài)空間，并引入比例因子ε（ε＞1）修正評(píng)估函數(shù)。實(shí)現(xiàn)了算法的增量性和實(shí)時(shí)性。王維［20］提出一種路徑指數(shù)加權(quán)A*算法，其算法將當(dāng)前節(jié)點(diǎn)的估計(jì)值占實(shí)際路徑值的比重進(jìn)行分析加權(quán)。比重加權(quán)值隨當(dāng)前結(jié)點(diǎn)距目標(biāo)節(jié)點(diǎn)的不同而進(jìn)行變化，通過(guò)加權(quán)值變化給予移動(dòng)機(jī)器人不同運(yùn)動(dòng)速度，提高了路徑規(guī)劃效率。趙曉等［21］提出跳點(diǎn)搜索A*算法，采用跳點(diǎn)代替A*算法中openlist和closelist中產(chǎn)生的不必要節(jié)點(diǎn)，并在路徑拐點(diǎn)處加入自身調(diào)整位姿的運(yùn)動(dòng)參量，使得路徑平滑性和規(guī)劃速度得到了很大的改善。Peng等［22］提出A*存儲(chǔ)數(shù)組算法，采用儲(chǔ)存數(shù)組的方式儲(chǔ)存A*數(shù)組元素，當(dāng)使用數(shù)組元素中某一元素時(shí)可以一次性操作完成對(duì)指定數(shù)組單元的訪問(wèn)，提高了算法的效率。周蘇［23］提出彈性帶氣泡A*算法。過(guò)彈性帶的收縮力消除路徑中過(guò)多的冗余點(diǎn)和松弛力；設(shè)置一個(gè)氣泡閾值Pp，當(dāng)彈性帶收縮至氣泡閾值時(shí)，局部區(qū)域停止收縮，局部路徑為最優(yōu)路徑。整個(gè)收縮舒張過(guò)程中，氣泡隨著彈性帶的伸縮變化進(jìn)行刪除和添加且氣泡之間相互重疊，使得整個(gè)路徑在氣泡范圍內(nèi)保證路徑無(wú)碰撞。

王洪斌［24］提出勢(shì)場(chǎng)A*算法同時(shí)實(shí)現(xiàn)靜態(tài)和動(dòng)態(tài)路徑規(guī)劃，通過(guò)A*算法實(shí)現(xiàn)初始靜態(tài)路徑尋優(yōu)規(guī)劃，當(dāng)某節(jié)點(diǎn)發(fā)生改變時(shí)采用勢(shì)場(chǎng)法對(duì)其動(dòng)態(tài)路徑進(jìn)行規(guī)劃。采用勢(shì)場(chǎng)A*算法實(shí)現(xiàn)了靜動(dòng)態(tài)的結(jié)合，能夠很好地處理存在的冗余點(diǎn)、轉(zhuǎn)折次數(shù)多問(wèn)題，使路徑達(dá)到最優(yōu)狀態(tài)。晁永生等［25］提出采用增量式A*算法將路徑規(guī)劃分成兩個(gè)階段。第一階段采用A*算法搜索靜態(tài)下障礙物信息，第二階段采用增量式A*算法搜索動(dòng)態(tài)障礙物信息，將兩者結(jié)合實(shí)現(xiàn)局部路徑和全局路徑規(guī)劃。Kaplan A［26］提出動(dòng)態(tài)窗口與A*算法結(jié)合思想來(lái)實(shí)現(xiàn)復(fù)雜環(huán)境的動(dòng)態(tài)路徑規(guī)劃。該算法通過(guò)選取多個(gè)目標(biāo)點(diǎn)提高算法效率，并利用目標(biāo)優(yōu)先級(jí)判定最短路徑，采用動(dòng)態(tài)窗口法追擊動(dòng)態(tài)目標(biāo)點(diǎn)，使其能夠成功獲得移動(dòng)目標(biāo)點(diǎn)。

2.4 勢(shì)場(chǎng)法

勢(shì)場(chǎng)法基本思想根據(jù)路徑目標(biāo)點(diǎn)對(duì)移動(dòng)機(jī)器人產(chǎn)生吸引力，障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生排斥力，將吸引力和排斥力的合力構(gòu)成移動(dòng)機(jī)器人的控制率，如圖7所示。

圖7 勢(shì)場(chǎng)法

由勢(shì)場(chǎng)法可得吸引磁場(chǎng)產(chǎn)生的吸引力隨著目標(biāo)點(diǎn)靠近逐漸減小，到達(dá)目標(biāo)點(diǎn)后吸引力為0；排斥磁場(chǎng)產(chǎn)生的排斥力隨著障礙物靠近而增大，當(dāng)障礙物距離大于預(yù)定閾值，排斥力為0。若目標(biāo)點(diǎn)與障礙物之間距離較近時(shí)，易受到吸引磁場(chǎng)和排斥磁場(chǎng)反復(fù)作用，容易產(chǎn)生震蕩和死鎖現(xiàn)象。

丁家如［27］提出增加虛擬子目標(biāo)勢(shì)場(chǎng)法，使其與原目標(biāo)點(diǎn)共同作用解決勢(shì)場(chǎng)法所存在的局部最小問(wèn)題。算法增加虛擬目標(biāo)點(diǎn)后，移動(dòng)機(jī)器人受到虛擬子目標(biāo)和實(shí)際目標(biāo)聯(lián)合作用使其吸引力大于排斥力，擺脫局部最小。翟紅生［28］提出一種相對(duì)速度勢(shì)場(chǎng)法，結(jié)合量子粒子群算法對(duì)吸引力勢(shì)場(chǎng)增益系數(shù)Ka和排斥勢(shì)場(chǎng)增益系數(shù)Kr進(jìn)行一定的修正，使其擺脫局部最小，該算法結(jié)構(gòu)簡(jiǎn)單、實(shí)現(xiàn)了有效避障，提高了規(guī)劃性能。王萌［29］提出采用附加控制力的勢(shì)場(chǎng)法，使機(jī)器人能夠迅速跳出局部最小值。該算法將機(jī)器人當(dāng)前位置與目標(biāo)點(diǎn)位置間的相對(duì)距離關(guān)系添加至排斥函數(shù)中，實(shí)現(xiàn)對(duì)原有斥力函數(shù)改進(jìn)。

陳金鑫［30］提出斥力偏轉(zhuǎn)模型勢(shì)場(chǎng)法，該算法采用調(diào)節(jié)斥力的指向和自適應(yīng)調(diào)節(jié)斥力系數(shù)，改變斥力與引力的夾角使其迅速跳出局部極小狀態(tài)，避免局部最小的同時(shí)減少了路徑規(guī)劃的長(zhǎng)度。何兆楚［31］提出RRT勢(shì)場(chǎng)法算法，其算法利用勢(shì)場(chǎng)法進(jìn)行局部路徑規(guī)劃，當(dāng)局部路徑出現(xiàn)震蕩和死鎖現(xiàn)象時(shí)，采用RRT（快速擴(kuò)展樹隨機(jī)算法）自適應(yīng)選擇臨時(shí)點(diǎn)，使得搜索過(guò)程跳出局部震蕩和最優(yōu)狀態(tài)；當(dāng)路徑跳出局部震蕩狀態(tài)后再切換至勢(shì)場(chǎng)法，反復(fù)進(jìn)行迭代直至到達(dá)目標(biāo)點(diǎn)。

2.5 螞蟻算法

蟻群算法是一種基于群體動(dòng)物覓食的一種智能搜索方法，采用一個(gè)螞蟻的行走路徑表示待優(yōu)化問(wèn)題的一個(gè)可行解，將整個(gè)螞蟻群體所有行走路徑作為待優(yōu)化問(wèn)題的解空間，用螞蟻群體收斂選擇的路徑作為問(wèn)題的優(yōu)化解，如圖8所示。

圖8 螞蟻搜索示意圖

螞蟻算法在路徑規(guī)劃過(guò)程中，問(wèn)題的解隨優(yōu)化過(guò)程同步變化，因此可以適應(yīng)問(wèn)題的動(dòng)態(tài)性。但在計(jì)算過(guò)程中存在計(jì)算量大，求解時(shí)間較長(zhǎng)，而且調(diào)整參數(shù)依靠經(jīng)驗(yàn)進(jìn)行反復(fù)調(diào)試，不同的環(huán)境模式需要適配不同的參數(shù)要求，易陷入過(guò)早收斂和局部最優(yōu)。

謝智慧［32］提出比例初始化信息素螞蟻算法，采用該方法將信息素的初始值按比例減少，即靠近起始點(diǎn)與目標(biāo)點(diǎn)連線附近信息素初始值取值大，而偏遠(yuǎn)區(qū)域的初始值較小，避免螞蟻算法盲目搜索和局部路徑交叉問(wèn)題，提高算法初期搜索效率。徐梁等［33］提出限制信息素取值螞蟻算法，通過(guò)限制蟻群信息素的取值范圍，擴(kuò)大搜索空間，從而避免了算法過(guò)早收斂，同時(shí)還提出自適應(yīng)調(diào)節(jié)信息揮發(fā)系數(shù)ρ提高算法的全局性和算法的收斂速度。劉國(guó)寶［34］引入精英螞蟻策略算法，每次迭代完成后，只求解結(jié)果中排名較前的幾個(gè)精英螞蟻用于信息的更新，將精英螞蟻所行走路徑按照代價(jià)函數(shù)排序并賦予不同的權(quán)重值，實(shí)現(xiàn)了全局最優(yōu)基礎(chǔ)上局部最優(yōu)。Jiao Z［35］提出一種零點(diǎn)定理不均勻分配初始信息素的蟻群算法，不同位置的柵格賦予不同的初始信息素，靠近目標(biāo)點(diǎn)的柵格信息素濃度高，引導(dǎo)螞蟻朝向目標(biāo)點(diǎn)探索，減少路徑盲目搜索，提高全局尋優(yōu)能力和搜索效率。屈鴻等［36］提出調(diào)整轉(zhuǎn)移概率蟻群算法，該方法引入隨機(jī)選擇機(jī)制以增加解的多樣性，排除障礙節(jié)點(diǎn)和已留信息素節(jié)點(diǎn)；引入懲罰函數(shù)對(duì)死鎖邊上的信息素進(jìn)行懲罰解決螞蟻算法所存在的死鎖問(wèn)題并提高了全局避障能力。

劉建華等［37］提出勢(shì)場(chǎng)蟻群算法，將吸引力和排斥力的合力作為一群信息素的擴(kuò)散方向，使得蟻群算法的搜索方向具有傾向性。黃辰［38］提出在一種基于動(dòng)態(tài)反饋式A*蟻群算法。采用簡(jiǎn)化A*算法優(yōu)化蟻群算法減少初期搜索的盲目性，加快蟻群算法初期的搜索效率；采用閉環(huán)反饋思想實(shí)現(xiàn)算法提高路徑的適應(yīng)能力，提高了路徑搜索效率，解決了算法的局部最小和死鎖現(xiàn)象。

2.6 粒子群算法

1995年由Eberhart博士和Kennedy博士提出粒子群算法，其思想來(lái)源是受到自然界中群居生物遷徙或覓食時(shí)所表現(xiàn)出的社會(huì)行為。粒子群算法將優(yōu)化問(wèn)題的解看作一個(gè)在自由搜索空間中的鳥，通過(guò)鳥類飛行不斷調(diào)節(jié)自身所在的位置來(lái)找到食物的源頭。

粒子群算法被提出后廣泛應(yīng)用于數(shù)據(jù)挖掘、信號(hào)處理和路徑規(guī)劃等各類問(wèn)題的優(yōu)化求解。算法易于實(shí)現(xiàn)、收斂速度快、優(yōu)化效率高和魯棒性好。但算法也存在易陷入局部最優(yōu)和收斂速度慢的缺陷。

當(dāng)前對(duì)于粒子群算法的研究主要針對(duì)粒子的運(yùn)動(dòng)軌跡和算法的收斂性的分析。魏勇［39］將差分進(jìn)化算法引入至粒子群算法中，當(dāng)算法在規(guī)劃過(guò)程中出現(xiàn)停滯時(shí)，引入差分進(jìn)化算法動(dòng)態(tài)調(diào)整變異概率和縮放因子增加種群算法的多樣性，擴(kuò)大算法的搜索范圍，該方法并討論了隨機(jī)性對(duì)粒子運(yùn)動(dòng)軌跡的影響。Dantzig［40］提出量子粒子群算法，采用量子粒子群算法對(duì)初始粒子進(jìn)行交叉操作提高算法的全局尋優(yōu)能力，通過(guò)粒子的變異操作提高局部尋優(yōu)能力。梁靜［41］交叉策略的動(dòng)態(tài)多組群粒子群優(yōu)化算法，該算法將整個(gè)種群分成多個(gè)小的種群，分別在小種群之間進(jìn)行尋優(yōu)求解，采用迭代的方法將小種群內(nèi)的最優(yōu)解進(jìn)行疊加，尋找全局最優(yōu)解。劉艷紅［42］提出指數(shù)權(quán)重粒子群算法，采用MAKLINK建立自由空間模型，采用Dijkstra算法搜索無(wú)碰撞路徑，將其權(quán)重加入粒子群算法中，取最短路徑。該算法與其他改進(jìn)粒子算法不同，該算法并不是向最優(yōu)粒子進(jìn)行學(xué)習(xí)，而是選擇粒子適應(yīng)度的平均值學(xué)習(xí)，該改進(jìn)算法避免了局部最優(yōu)，提高了粒子的多樣性。

Poli［43］在進(jìn)行速度更新的基礎(chǔ)上添加了有界隨機(jī)擾動(dòng)變量和臨近粒子信息，該方法能夠通過(guò)對(duì)粒子的速度更新引入變異機(jī)制保持粒子尋優(yōu)的多樣性，防止算法收斂過(guò)早。Fernande［44］通過(guò)分析粒子群算法將其看做一個(gè)隨機(jī)阻尼彈簧系統(tǒng)，建立動(dòng)態(tài)方程分析其穩(wěn)定性和局部收斂性，提出多目標(biāo)粒子群算法，引入環(huán)境適應(yīng)因子和配對(duì)選擇機(jī)制選擇個(gè)體最優(yōu)和全局最優(yōu)增強(qiáng)算法的局部最優(yōu)和全局最優(yōu)搜索能力。Soleimani［45］提出一種慣性權(quán)重隨機(jī)取值的粒子群算法減少其影響程度，通過(guò)隨機(jī)取值保持了粒子群的多樣性，并在迭代過(guò)程中動(dòng)態(tài)調(diào)節(jié)學(xué)習(xí)因子避免算法過(guò)早收斂。

2.7 遺傳算法

20世紀(jì)70年代，美國(guó)密歇根大學(xué)J Holland教授首次提出遺傳算法，遺傳算法是根據(jù)大自然生物進(jìn)化規(guī)律而設(shè)計(jì)提出，針對(duì)自然選擇和遺傳時(shí)發(fā)生的交叉和變異設(shè)計(jì)生物進(jìn)化過(guò)程的計(jì)算模型，并融合優(yōu)勝劣汰自然準(zhǔn)則選擇每一代的候選解，最終從候選解中搜索最優(yōu)解，遺傳算法的構(gòu)建圖如9所示。

圖9 遺傳算法

遺傳算法實(shí)現(xiàn)方式簡(jiǎn)單，受外界的影響較小，可以發(fā)揮自身的迭代的優(yōu)勢(shì)，可以與其他算法融合使用，具有很好的自組織性和學(xué)習(xí)性；但該方法運(yùn)算過(guò)程中一些后續(xù)不需要的種群給計(jì)算提升難度使得計(jì)算效率不高、搜索效率低，收斂速度慢，易陷入局部最優(yōu)解。

MONTIEL［46］提出遺傳算法在選擇操作中引入模擬退火法增加種群多樣性，提高路徑尋優(yōu)能力，并結(jié)合交叉、變異算子自調(diào)整策略，使得種群個(gè)體之間存在較大的差異。該算法不僅提高了收斂速度，而且可以使算法跳出局部最優(yōu)。武小年［47］提出遺傳算法與蟻群算法結(jié)合的路徑規(guī)劃算法。通過(guò)改變遺傳算法中種群初始化因子使得節(jié)點(diǎn)搜索時(shí)更趨向于目標(biāo)路徑，提高初始種群的規(guī)劃效率，對(duì)變異過(guò)程中變異節(jié)點(diǎn)進(jìn)行限制，避免產(chǎn)生路徑不連續(xù)。余文曌［48］在無(wú)人艇規(guī)劃過(guò)程中在遺傳算法上添加彈性網(wǎng)格概念。通過(guò)動(dòng)態(tài)變換調(diào)整網(wǎng)格局部密度，設(shè)計(jì)自適應(yīng)變異概率，根據(jù)路徑網(wǎng)格的離散程度自適應(yīng)調(diào)整大小，提高各代路徑的多樣化。該算法減小了搜索空間，提高了路徑算法的多樣性。

胡爾兵［49］在遺傳算法的基礎(chǔ)上提出了余弦自適度函數(shù)，在進(jìn)化前期交叉概率和變異概率較大，防止算法發(fā)生早熟收斂現(xiàn)象，在進(jìn)化后期要求較低的交叉概率和變異概率，以避免最優(yōu)個(gè)體的丟失。

3 概率完備路徑規(guī)劃

3.1 PRM算法（Probabilistic roadmap）

20世紀(jì)90年代初期，M H Over－mars提出PRM算法，PRM算法基本思想是通過(guò)隨機(jī)采樣和碰撞檢測(cè)找到位形空間中的路徑點(diǎn)和無(wú)碰路徑，如圖10所示。首先對(duì)環(huán)境空間進(jìn)行采點(diǎn)，連接環(huán)境空間中相鄰的節(jié)點(diǎn)并刪除節(jié)點(diǎn)連線之間有障礙的路徑，加入起始點(diǎn)和終止點(diǎn)，從連通圖中尋找一條從起始點(diǎn)到終止點(diǎn)最優(yōu)的路徑。

圖10 PRM連通

PRM算法簡(jiǎn)化了對(duì)環(huán)境的解析計(jì)算，可以快速構(gòu)建得到連通圖，而且適用于高緯度自由位形空間的規(guī)劃，是一個(gè)近似完備的路徑規(guī)劃方法，但PRM采用均勻采樣策略，當(dāng)環(huán)境空間處于相對(duì)較窄的通道時(shí)，均勻采點(diǎn)落在無(wú)障礙通道的采樣點(diǎn)較少，使其無(wú)法連接兩側(cè)的子圖，對(duì)算法的連通性產(chǎn)生了一定的影響。

譚建豪［50］提出一種障礙物邊界采樣點(diǎn)的PRM算法，該算法提取障礙物的邊界點(diǎn)并將其作為確定采樣點(diǎn)，基于自由位形空間的采樣點(diǎn)與障礙物邊界采樣點(diǎn)建立最優(yōu)可行區(qū)域以解決PRM算法采樣點(diǎn)全局分散問(wèn)題，提高了路徑規(guī)劃效率。李敏［51］提出一種基于距離變換PRM路徑規(guī)劃算法。該算法采用PRM算法在自由位形空間中采點(diǎn)，使用距離變換對(duì)空間中的點(diǎn)賦值（其值為該點(diǎn)與障礙物的距離），從而構(gòu)成距離變換地圖。通過(guò)距離變換地圖平均值反映障礙物在空間中的稠密程度并確定環(huán)境空間中采樣點(diǎn)的個(gè)數(shù)。由距離變換值判斷不同的區(qū)域障礙物分布情況分別采用不同的采樣點(diǎn)策略，使得窄通道采樣點(diǎn)較密集，寬通道采樣點(diǎn)稀疏。劉洋［52］提出在勢(shì)場(chǎng)PRM算法，傳統(tǒng)PRM算法在采樣姿態(tài)進(jìn)行膨脹檢測(cè)時(shí)，落在障礙物上的采樣點(diǎn)舍棄，而改進(jìn)后算法將障礙物看做一個(gè)排斥磁場(chǎng)，當(dāng)采樣點(diǎn)落在障礙物空間內(nèi)時(shí)，采樣點(diǎn)受到斥力作用使其向自由空間運(yùn)動(dòng)，直至將采樣點(diǎn)完全排斥出障礙物，從而增加窄通道空間采樣點(diǎn)數(shù)目，實(shí)現(xiàn)最優(yōu)路徑聯(lián)通。采用排斥磁場(chǎng)易造成取樣點(diǎn)不均勻和路徑偏離現(xiàn)象。

魏念?。?3］提出一種改進(jìn)PRM算法，采用Douglas－Peucker算法對(duì)PRM初始路徑關(guān)鍵采樣點(diǎn)提取，使用關(guān)鍵節(jié)點(diǎn)代替路徑中的初始空間采樣點(diǎn)，減少環(huán)境空間采樣點(diǎn)的個(gè)數(shù)。采用Clothoid曲線對(duì)路徑進(jìn)行平滑性處理，使其從起始點(diǎn)至目標(biāo)點(diǎn)路徑拐點(diǎn)個(gè)數(shù)少，路徑更平滑。LUO C［54］采用神經(jīng)網(wǎng)絡(luò)PRM算法，通過(guò)神經(jīng)網(wǎng)絡(luò)活動(dòng)產(chǎn)生的活性值加快相鄰采樣點(diǎn)路徑的創(chuàng)建，使其路徑規(guī)劃效率有了很大程度的提高，并采用二分法判斷是否在占該區(qū)域內(nèi)，若在障礙區(qū)域內(nèi)路徑刪除，若不在占該區(qū)域內(nèi)則保留，實(shí)現(xiàn)最優(yōu)路徑規(guī)劃。提高了路徑規(guī)劃的效率，減少了規(guī)劃的時(shí)間。

3.2 RRT算法（Rapidly－Exploring Random Tree）

1998年美國(guó)愛(ài)荷華州立大學(xué)Steven M.lavalle提出基于節(jié)點(diǎn)采樣的快速擴(kuò)展隨機(jī)樹（Rapidly－Exploring Random Tree，RRT）算法。RRT算法的基本思想采用樹形式的連通圖方法，其擴(kuò)展過(guò)程如圖11所示，以起始點(diǎn)Q（init）為樹的根節(jié)點(diǎn)建立搜索樹，在狀態(tài)空間中隨機(jī)采樣某一狀態(tài)用于引導(dǎo)搜索樹的擴(kuò)張，此狀態(tài)稱為Q（rand），在已建立的搜索樹查找與Q（rand）距離最接近的點(diǎn)Q（near），以Q（near）和Q（rand）建立一個(gè)新的輸入u，以當(dāng)前Q（near）作為輸入狀態(tài)x，根據(jù)系統(tǒng)方程x＝f（x，u）得到下一個(gè)狀態(tài)Q（new），對(duì)Q（new）進(jìn)行無(wú)碰撞檢測(cè)，如果檢測(cè)無(wú)沖突，則將Q（new）加入至搜索樹中，實(shí)現(xiàn)整個(gè)擴(kuò)張過(guò)程。

圖11 RRT算法

基于節(jié)點(diǎn)采樣的RRT算法建模簡(jiǎn)單，容易添加非完整約束條件，在復(fù)雜環(huán)境中具有很靈活的搜索能力，但算法存在節(jié)點(diǎn)利用率低，路徑不穩(wěn)定等因素影響。

楊也［55］提出了勢(shì)場(chǎng)RRT算法，其算法通過(guò)增加引力分量的形式引導(dǎo)隨機(jī)樹朝向目標(biāo)方向生長(zhǎng)，使得RRT算法生長(zhǎng)方向具有目標(biāo)偏向性，減少隨機(jī)樹搜索的隨機(jī)性。肖支才［56］提出一種基于循環(huán)尋優(yōu)的RRT算法。該算法在RRT算法的基礎(chǔ)上引入了長(zhǎng)度代價(jià)約束，對(duì)擴(kuò)展樹的生長(zhǎng)進(jìn)行約束，通過(guò)長(zhǎng)度代價(jià)函數(shù)可以有效去除RRT樹無(wú)用搜索路徑，反復(fù)進(jìn)行迭代后得到全局最優(yōu)路徑。該算法提高了節(jié)點(diǎn)的利用率、加快路徑規(guī)劃效率。KalisiakM［57］等提出RRT－blossom算法，該算法采用回歸約束函數(shù)控制隨機(jī)樹生長(zhǎng)節(jié)點(diǎn)，降低隨機(jī)樹在搜索前期重復(fù)路徑搜索的可能，約束函數(shù)將被約束的點(diǎn)設(shè)為休眠點(diǎn)，若隨機(jī)數(shù)擴(kuò)展未能發(fā)現(xiàn)目標(biāo)點(diǎn)，則對(duì)休眠點(diǎn)小范圍的搜索，保證全局概率完整性，增加了對(duì)未知空間的探索。徐娜［58］提出目標(biāo)偏向策略算法，即在路徑搜索前設(shè)定一個(gè)目標(biāo)偏向概率閾值Pp，目標(biāo)偏向概率閾值Pp控制隨機(jī)樹生長(zhǎng)的偏向性，減少采樣過(guò)程的目標(biāo)計(jì)算量，靈活改變采樣區(qū)域的大小，目標(biāo)的搜索性強(qiáng)，使得偏向概率閾值Pp控制下獲得最佳路徑規(guī)劃。

Cheng［59］提出擴(kuò)展函數(shù)訓(xùn)練環(huán)境模型RRT算法，該方法根據(jù)不同環(huán)境標(biāo)準(zhǔn)設(shè)定環(huán)境訓(xùn)練模型，其距離障礙物遠(yuǎn)的點(diǎn)約束條件少，擴(kuò)展樹的擴(kuò)展概率大；而距離障礙物近的點(diǎn)約束條件多，被刪除的概率大。通過(guò)隨機(jī)樹多次路徑搜索后，使其路徑節(jié)點(diǎn)之間建立一定內(nèi)在關(guān)系，從而提高路徑搜索效率和路徑規(guī)劃質(zhì)量。文獻(xiàn)［60］提出雙向RRT算法，該算法在起始點(diǎn)和目標(biāo)點(diǎn)同時(shí)生成兩顆RRT樹，以終點(diǎn)和起點(diǎn)作為RRT樹的初始點(diǎn)進(jìn)行相向搜索，直到兩棵擴(kuò)展樹葉子互相連接，搜索過(guò)程中通過(guò)評(píng)估函數(shù)選擇最優(yōu)路徑，該算法提高了搜索速度，節(jié)約搜索時(shí)間。

4 算法概括

表2所示為以上算法特征和優(yōu)缺點(diǎn)的歸納總結(jié)。

表2 改進(jìn)算法的特征及優(yōu)缺點(diǎn)

續(xù)表2

5 移動(dòng)機(jī)器人展望

當(dāng)前，路徑規(guī)劃技術(shù)已經(jīng)取得了顯著的成果，但在具體實(shí)施路徑規(guī)劃方法過(guò)程中發(fā)現(xiàn)了其存在的局限性。如螞蟻算法參數(shù)調(diào)試需要長(zhǎng)期人工經(jīng)驗(yàn)和收斂過(guò)早等問(wèn)題、PRM空間隨機(jī)采點(diǎn)不均勻等一系列問(wèn)題。因此，根據(jù)研究學(xué)者當(dāng)前的研究和未來(lái)的發(fā)展趨勢(shì)，目前移動(dòng)機(jī)器人技術(shù)研究主要集中在以下幾個(gè)方面。

5.1 更高智能化

隨著科學(xué)技術(shù)的發(fā)展，智能機(jī)器人有著越來(lái)越廣闊的發(fā)展前景，更智能化是機(jī)器人發(fā)展的必然趨勢(shì)。機(jī)器人能夠融合傳感器采集信息、處理信息、加強(qiáng)對(duì)未知環(huán)境空間探索，以調(diào)整運(yùn)動(dòng)狀態(tài)迅速到達(dá)目標(biāo)點(diǎn)，對(duì)環(huán)境變化適應(yīng)能力強(qiáng)，能夠在愈加復(fù)雜的環(huán)境中完成復(fù)雜任務(wù)的能力。因此，研究更高水平的智能化機(jī)器人是未來(lái)機(jī)器人技術(shù)發(fā)展的一個(gè)趨勢(shì)。

5.2 更優(yōu)化路徑方案

如今，智能機(jī)器人技術(shù)被廣泛應(yīng)用于多個(gè)領(lǐng)域，機(jī)器人領(lǐng)域?qū)W者們一直致力于研究更好的路徑規(guī)劃方案滿足移動(dòng)機(jī)器人自身約束條件。但運(yùn)動(dòng)過(guò)程中，智能機(jī)器人受到速度、加速度和自身運(yùn)動(dòng)條件的限制等各方面因素的影響，使其運(yùn)動(dòng)軌跡受到一定程度的影響。因此研究一種路徑優(yōu)化方案使其路徑節(jié)點(diǎn)數(shù)量少、路徑轉(zhuǎn)折點(diǎn)少、運(yùn)動(dòng)軌跡平滑、連續(xù)性好等特點(diǎn)滿足非完整機(jī)器人運(yùn)動(dòng)約束條件具有重要意義。

5.3 新路徑算法的研究

單一路徑規(guī)劃方法總是存在的一定的缺陷，使其實(shí)際運(yùn)動(dòng)過(guò)程中存在一定的局限性。因此，將不同算法之間優(yōu)勢(shì)互補(bǔ)，形成一種新的算法體系，實(shí)現(xiàn)機(jī)器人領(lǐng)域突破性進(jìn)展。例如，RRT算法與勢(shì)場(chǎng)法、A*算法與螞蟻算法等一些算法的結(jié)合。另外，智能機(jī)器人是一種跨領(lǐng)域的學(xué)科，因此引入其他學(xué)科的研究也是未來(lái)發(fā)展的一個(gè)方向。

5.4 多機(jī)器人協(xié)作

隨著智能機(jī)器人工作環(huán)境改變，單機(jī)器人作業(yè)在大部分情況不能滿足任務(wù)工作的需求，因此多機(jī)器人協(xié)作是機(jī)器人領(lǐng)域未來(lái)發(fā)展的必然趨勢(shì)。單智能機(jī)器人自身安裝的傳感器和通信設(shè)備往往有一定的精度和范圍，只由單一的通信設(shè)備難以保證環(huán)境空間的完整性和可靠性，因此采用多機(jī)器人相互協(xié)作共同完成任務(wù)，既可以發(fā)揮單個(gè)機(jī)器人的特點(diǎn)，又能通過(guò)多機(jī)器人之間通信描述環(huán)境信息的完整性，并能夠快速分析實(shí)時(shí)環(huán)境信息并獲取可靠結(jié)果。因此，如何建立多移動(dòng)機(jī)器人之間的信息聯(lián)系、分析如何靈活多變且高效地完成工作成為了研究學(xué)者需要探索的問(wèn)題。

6 結(jié)束語(yǔ)

路徑規(guī)劃技術(shù)是智能移動(dòng)機(jī)器人領(lǐng)域的一個(gè)重要分支，采用良好的路徑規(guī)劃方法可以提高效率，節(jié)約時(shí)間，減少人力物力的投入。本文從完備性和概率完備兩部分展開詳細(xì)的介紹，分析機(jī)器人領(lǐng)域研究學(xué)者如何采用最優(yōu)的路徑規(guī)劃方法來(lái)實(shí)現(xiàn)高效、最優(yōu)、低成本的路徑規(guī)劃方案。并對(duì)智能機(jī)器人未來(lái)發(fā)展趨勢(shì)進(jìn)行探究和展望，對(duì)當(dāng)前機(jī)器人技術(shù)的研究和發(fā)展具有一定的參考價(jià)值。