李晨輝，王澤峰，胡德燕，胡連信，孫凱悅，崔 琳，吳 晟※

（1.哈爾濱工程大學(xué)煙臺研究（生）院，山東煙臺 264000；2.湖州師范學(xué)院信息工程學(xué)院，浙江湖州 313000；3.煙臺市海洋經(jīng)濟(jì)研究院，山東煙臺 264000；4.天津威圖測控技術(shù)有限公司，天津 300392）

0 引言

近年來，移動機(jī)器人技術(shù)得到了進(jìn)一步發(fā)展，是國家科學(xué)技術(shù)和工業(yè)自動化的重要指標(biāo)之一。機(jī)器人技術(shù)在提高社會生產(chǎn)力的過程中所占的比重也越來越大。移動機(jī)器人在工業(yè)場景和家用場景中都有著龐大的需求，具有廣闊的前景。如家庭場景下的娛樂機(jī)器人、康復(fù)機(jī)器人、服務(wù)機(jī)器人、安全保護(hù)防護(hù)機(jī)器人；在工業(yè)場景下的快遞分揀車AGV（Automated Guided Vehicle）、化學(xué)危害氣體中的有害氣體檢測機(jī)器人、在路況復(fù)雜下的人員搜救機(jī)器人。

對于移動機(jī)器人，準(zhǔn)確的導(dǎo)航對機(jī)器人至關(guān)重要，而路徑規(guī)劃是決定導(dǎo)航是否精確的重要一環(huán)。路徑規(guī)劃是在已知的應(yīng)用場景中根據(jù)初始起點和目標(biāo)點規(guī)劃出一條路徑。該路徑能夠滿足高效、安全等要求，并且能夠及時避開路徑上的各種障礙物。移動機(jī)器人的路徑規(guī)劃技術(shù)主要包括全局路徑規(guī)劃和局部路徑規(guī)劃，其核心內(nèi)容是實現(xiàn)規(guī)劃路線的平滑性和冗余性，在外部環(huán)境中能夠正確地行進(jìn)。路徑規(guī)劃主要分兩步進(jìn)行：第一步是根據(jù)靜態(tài)障礙物區(qū)域和自由可移動區(qū)域進(jìn)行全局路徑規(guī)劃，找出最優(yōu)路徑；第二步是移動機(jī)器人在目標(biāo)點行進(jìn)中，動態(tài)感知周圍的局部環(huán)境，及時通過局部規(guī)劃對障礙物進(jìn)行避障。本文闡述了從全局路徑規(guī)劃到局部路徑規(guī)劃的常用算法的應(yīng)用機(jī)制，在現(xiàn)實場景下的應(yīng)用情況，并對其算法進(jìn)行了優(yōu)缺點分析，對部分研究路徑規(guī)劃的國內(nèi)外文獻(xiàn)進(jìn)行了概述，并對其進(jìn)行了分析和討論。

1 全局路徑規(guī)劃算法對比分析

全局路徑規(guī)劃是依照當(dāng)前的靜態(tài)地圖，參考地圖上障礙物的位置和可行路徑，根據(jù)系統(tǒng)給出的出發(fā)點和目標(biāo)點，規(guī)劃出一條最優(yōu)路徑。其相關(guān)算法主要應(yīng)用于場景預(yù)知的室外環(huán)境中，面對復(fù)雜多變的地理環(huán)境，通過對算法的優(yōu)化來提高機(jī)器人路徑規(guī)劃的能力。主要包括A*算法、遺傳算法、蟻群算法、粒子群算法和快速探索隨機(jī)樹等。

1.1 A＊算法

1968年Nils Nilsson[1]提出了A＊算法，其主要用于在靜態(tài)環(huán)境中求解最短路徑，因為其屬于遍歷的確定性搜索方式，搜索過程直觀簡潔，所以是解決地圖環(huán)境預(yù)知的情況下全局路徑搜索問題的典型算法。在全局網(wǎng)絡(luò)中，A＊算法會依據(jù)擴(kuò)展節(jié)點選擇當(dāng)前“代價”最低的方塊進(jìn)行下一步搜索，直到搜索到終點，從而規(guī)劃出成本最低的路徑。A＊算法是當(dāng)前流行的比較重要的啟發(fā)式搜索算法之一，該算法廣泛應(yīng)用于單機(jī)器人的全局靜態(tài)環(huán)境中。

A＊算法示意圖如圖1所示，其中f()n是關(guān)于目的地n的估價函數(shù)，g()n是“當(dāng)前代價”，即起點到目的地n的最短路徑值；h()n是“預(yù)估代價”，即當(dāng)前移動機(jī)器人位置到目的地n的最優(yōu)路經(jīng)的啟發(fā)值。張新艷等[2]引入了基于時間因子的改進(jìn)型算法來尋找轉(zhuǎn)彎次數(shù)較少的路徑方案。

圖1 A＊算法示意圖

1.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是美國的Bre?mermann[3]于1960年提出，通過選擇和交叉變異手段，模擬達(dá)爾文的物竟天擇、適者生存的法則。在初始化階段根據(jù)表現(xiàn)的外部性狀，對種群進(jìn)行編碼，根據(jù)適用度函數(shù)評估每條路徑的適用度，參考適應(yīng)度越高，選擇的概率越大，選擇出適應(yīng)度高的路徑，低于適應(yīng)度選擇閾值的進(jìn)行淘汰處理，在已選出的路徑個體中再進(jìn)行交叉、變異，直至產(chǎn)生達(dá)到要求的路徑。遺傳算法示意圖如圖2所示。

圖2 遺傳算法示意圖

基于提高遺傳算法的全局性，減少陷入局部最優(yōu)的概率，John Hollnd探索出增加變異算子和交叉算子方法，通過模擬自然狀態(tài)下的遺傳模式并加入了選擇算子[4]。對于該算法易于過早的收斂而導(dǎo)致迭代效果不佳，Ge等[5]決定改進(jìn)原本算法：首先是通過增加了新的預(yù)測機(jī)制，不在是隨機(jī)對染色體編碼，另外也通過對適應(yīng)度函數(shù)進(jìn)行改進(jìn)，提高其評價廣度。2018年，A Z Zambom等[6]通過優(yōu)化遺傳算法的執(zhí)行策略，可在復(fù)雜環(huán)境中搜索機(jī)器人的最優(yōu)路徑。Qu等[7]設(shè)計了一種修改算子的方法，能夠較好地解決局部最優(yōu)問題，改善了遺傳算法的收斂性差，種群間交叉變異少的問題。

1.3 蟻群算法

蟻 群 算 法（Ant Colony Optimization，ACO）是Dorigol[8]基于正反饋機(jī)制提出的一種路徑規(guī)劃算法，結(jié)合真實環(huán)境下螞蟻的行為，模擬螞蟻根據(jù)信息素濃度的高低進(jìn)行路徑?jīng)Q策。根據(jù)這一特性，在覓食行為中，總能求得一條從出發(fā)點到目標(biāo)點的最優(yōu)路徑。圖3顯示了這樣一個覓食的過程。如圖所示，存在一定數(shù)量的螞蟻，設(shè)定N點為螞蟻的巢穴，F(xiàn)為螞蟻要尋找的食物。蟻群會沿著蟻穴和食物之間的直線距離移動，假設(shè)在蟻穴和食物之間出現(xiàn)了障礙物，這時螞蟻就要做出決策，是向左還是向右行進(jìn)，由于前面的螞蟻沒有留下信息素，螞蟻在兩個方向的概率是相同的。只有在有螞蟻停留的地方，就會在相應(yīng)的地段分泌一定的信息素，而且信息素會隨時間的流逝濃度逐漸變低，該物質(zhì)是蟻群進(jìn)行信息交流的載體。后面的螞蟻通過信息素的濃度來做出相應(yīng)的決策，很明顯，沿著較短距離的路徑，信息素會越來越濃，進(jìn)而吸引更多的螞蟻。

圖3 蟻群算法示意圖

為了解決蟻群算法容易陷入局部最優(yōu)點的問題，不少研究者對算法的信息素濃度進(jìn)行改進(jìn)。面對蟻群算法搜索速度慢和局部最優(yōu)，Liu等[9]在該算法基礎(chǔ)上加入信息素?fù)]發(fā)機(jī)制和自適應(yīng)搜索步長，大大減少了蟻群算法的迭代次數(shù)。基于此，Dai等[10]認(rèn)為改進(jìn)每次迭代的方法是有效的，通過改進(jìn)迭代的步長實驗表明，與傳統(tǒng)的蟻群算法相比，使得改進(jìn)的ACO迭代次數(shù)減少了2/3，快速高效地對路徑進(jìn)行規(guī)劃證明改進(jìn)的算法更有效。除此之外，對于多物流機(jī)器人的路徑規(guī)劃，楊洋等[11]認(rèn)為蟻群算法結(jié)合彈性時間窗技術(shù)，能夠?qū)崿F(xiàn)多物流機(jī)器人的路徑規(guī)劃相，經(jīng)仿真實驗表明：快速規(guī)劃的同時能夠?qū)崿F(xiàn)最優(yōu)的避障路徑。王雷等[12]針對蟻群算法容易陷入局部優(yōu)化的問題，提出了通過實時調(diào)整信息素啟發(fā)因子和預(yù)期啟發(fā)因子，自適應(yīng)地改變揮發(fā)因子。針對蟻群算法初始信息素不足和收斂速度慢和的問題。張瑋等[13]通過加入煙花蟻群混合算法來求解靜態(tài)環(huán)境下的避障問題。

1.4 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是由Kennedy和Eberhart[14]在1995年提出。粒子群算法通過不斷搜索當(dāng)前的最優(yōu)值，通過迭代不斷更新粒子的速度和位置，類似于鳥類覓食的過程。通過個體與群體成員的適當(dāng)交流，整個鳥群都能達(dá)到最終的食物源。該算法是通過模擬鳥群，單個鳥與鳥群之間的信息共享，通過計算分析優(yōu)化，求出最優(yōu)解。其基本原理是個體與群體協(xié)作和信息共享，從而獲得最優(yōu)解。它是一個以當(dāng)前搜索到的最優(yōu)值不斷更新迭代來尋找全局最優(yōu)值的算法。粒子群算法是概率型的全局路徑規(guī)劃算法，因為在迭代的過程中充滿更多的可能性。PSO通過讓單個粒子在路徑規(guī)劃空間里找出此粒子的最優(yōu)解，再將個體最優(yōu)解共享給粒子群的其他粒子，找出個體中最優(yōu)解作為全局最優(yōu)解，因此整個粒子群在搜索的過程中覆蓋的范圍更大，更容易找到全局最優(yōu)解[15]，其算法流程如圖4所示。

圖4 粒子群算法示意圖

針對粒子群算法生成因需要達(dá)到全局最優(yōu)而造成的路徑折線較多的和k-means算法易受初始中心影響等問題。Song[16]提出通過加入自適應(yīng)階段速度，來減緩機(jī)器人路徑的折線，優(yōu)化路徑平滑度，同時也提高了搜索空間的能力。湯深偉等[17]提出了基于改進(jìn)粒子群算法的k-means聚類算法，孟慶寬等[18]通過粒子群算法計算得到最優(yōu)加權(quán)因子，進(jìn)而調(diào)整控制規(guī)則實現(xiàn)導(dǎo)航車輛的自適應(yīng)控制。

針對于標(biāo)準(zhǔn)PSO算法在一些基準(zhǔn)函數(shù)上改進(jìn)，PSO算法能快速收斂但是容易陷入局部最優(yōu)的問題。王東風(fēng)等[19]基于粒子間適應(yīng)值的差異，提出對粒子位置高斯采樣均值的自適應(yīng)調(diào)整策略，減緩粒子在中心的聚集趨勢。Ma等[20]提出將雙重倉庫下機(jī)器人最短路徑問題轉(zhuǎn)變?yōu)闀r變非線性規(guī)劃問題來降低難度。Ajeil等[21]針對靜態(tài)環(huán)境下尋優(yōu)的問題，通過與GA算法、PSO算法比較，提出通過設(shè)置蟻群不同的個體的壽命的優(yōu)化算法，實驗結(jié)果表明，在路徑規(guī)劃長度的減少有顯著的效果。

1.5 快速擴(kuò)展隨機(jī)樹

快速擴(kuò)展隨機(jī)樹（Rapidly-exploring Random Trees，RRT）是通過隨機(jī)構(gòu)建空間樹來實現(xiàn)快速搜索的一種算法?；舅枷胧窃谝阎貓D上，通過給定的起始位置和目標(biāo)位置的規(guī)劃任務(wù)，在起始位置通過抽樣隨機(jī)構(gòu)建隨機(jī)無向圖，類似于樹形結(jié)構(gòu)，在無障礙區(qū)域不斷延伸樹形結(jié)構(gòu)。一般來講，路徑規(guī)劃算法都是不斷的朝著目標(biāo)位置延伸，但是由于障礙物的存在，如果不斷的指向目標(biāo)位置，會有和障礙物相撞的風(fēng)險。為解決上述問題，RRT算法主要通過隨機(jī)采樣的方法，選擇延伸方向時，會設(shè)置一定的概率朝著目標(biāo)位置生長，也有一定的概率隨機(jī)在全局地圖任意方向延伸。擴(kuò)展樹延伸分支選擇距離采樣點位置近的樹節(jié)點，并且建立延伸的樹節(jié)點是否撞到障礙物；采樣點距離擴(kuò)展樹的距離要達(dá)到設(shè)定的閾值，通過兩個約束防止發(fā)生碰撞和延伸的樹節(jié)點重復(fù)。

對于RRT算法對前期的的擴(kuò)展比較敏感，全局最優(yōu)解由于擴(kuò)展樹的結(jié)構(gòu)，導(dǎo)致收斂速度慢的問題?；诖?，N Pérez Higueras等[22]通過將強(qiáng)化學(xué)習(xí)的思想運用到RRT算法上，提出了一種改進(jìn)型算法，改進(jìn)初期的代價函數(shù)，使其在前期能夠快速的找到較優(yōu)擴(kuò)展方向，從而加快收斂速度。符秀輝等[23]通過加入對擴(kuò)展方向的自適應(yīng)策略，減少了RRT算法達(dá)到最優(yōu)路徑的迭代次數(shù)，并且對RRT算法前期存在的偏差較大的問題有了一定的改善。由于RRT算法在障礙物較多，且空間比較復(fù)雜的環(huán)境中，容易陷入局部最優(yōu)值，甚至是找不到最優(yōu)解，朱冰等[24]通過提出增加約束來調(diào)整擴(kuò)展的方向，分別設(shè)定了安全場約束和對于擴(kuò)展樹的角度進(jìn)行了限制，增強(qiáng)了RRT系統(tǒng)的魯棒性。Wang等[25]提通過卷積搭建神經(jīng)網(wǎng)絡(luò)，訓(xùn)練預(yù)測模型，提前預(yù)測擴(kuò)展樹的生長方向，提出通過卷積神經(jīng)網(wǎng)絡(luò)與RRT相結(jié)合的改進(jìn)型算法，通過提前將大量成功尋找最優(yōu)路徑數(shù)據(jù)作為訓(xùn)練集，喂入模型，每次給出最優(yōu)的多個預(yù)測的生長方，再通過RRT進(jìn)行抽樣，大大減少了隨機(jī)性較大，偏差性大的問題，提高了整體的搜索效率。

2 局部路徑規(guī)劃算法對比分析

局部路徑規(guī)劃是移動機(jī)器人執(zhí)行路徑規(guī)劃時的重要一環(huán)，對機(jī)器人自身的傳感器設(shè)備依賴性非常高。局部路徑規(guī)劃目前主要應(yīng)用于動態(tài)環(huán)境的避障，是移動機(jī)器人工作的關(guān)鍵技術(shù)之一。局部路徑規(guī)劃技術(shù)主要包括動態(tài)窗口法以及人工勢場算法。

2.1 人工勢場算法

人工勢場算法由Khatib[26]在1986年提出。該算法是基于物理學(xué)上的正負(fù)電荷機(jī)制，假設(shè)起始位置為正電荷，目標(biāo)位置設(shè)置為負(fù)電荷，障礙物則設(shè)置為正電荷。根據(jù)正負(fù)相吸引，正正相排斥原則，從而達(dá)到機(jī)器人與目標(biāo)點相吸引，與障礙物相排斥的作用。最后通過模擬由正負(fù)電荷所激發(fā)的電場，根據(jù)機(jī)器人電場中所受到的合力來改變移動方向，直至到達(dá)目標(biāo)位置。

由于動態(tài)障礙物的存在，而全局規(guī)劃算法只能在地圖上規(guī)劃，無法考慮動態(tài)障礙物，一般的局部實時避障容易偏差較大。針對傳統(tǒng)人工勢場法算法無法達(dá)到目標(biāo)和局部優(yōu)化的缺點，無人機(jī)運動避障人工勢場算法本身存在的極小值問題和局部最小值等問題。段建民等[27]為解決路徑規(guī)劃時的最優(yōu)解問題，提出了將遺傳算法與人工勢場法相融合方法，通過并行搜索方法，提高了最優(yōu)解的搜索速度。陳麟杰等[28]采用增加了無人機(jī)之間的斥力，同時定義集群的前置形心作為另一個引力源。丁家如等[29]提出了改進(jìn)人工勢場法引力函數(shù)。毛晨悅等[30]提出通過生成預(yù)規(guī)劃路徑弱化了目標(biāo)點對無人機(jī)的吸引作用，增加了路徑的連貫性。

針對傳統(tǒng)人工勢場法應(yīng)用于多坐標(biāo)系機(jī)器人避障時無法約束各關(guān)節(jié)位姿、陷入局部極小后難以逃離的問題，傳統(tǒng)人工勢場法由于局部極小點問題而導(dǎo)致規(guī)劃失敗。曹博等[31]通過在笛卡爾坐標(biāo)系內(nèi)引入引力勢場和斥力勢場，主動采用線段球體包絡(luò)盒模型，來測試碰撞模型，提高了系統(tǒng)魯棒性，降低了陷入局部最優(yōu)值的風(fēng)險。沈文君[32]提出了在改進(jìn)人工勢場函數(shù)的基礎(chǔ)上，通過修改斥力方向的方法來解決傳統(tǒng)人工勢場法下的典型局部極小點問題。

2.2 動態(tài)窗口算法

動態(tài)窗口算法（Dynamic Window Approach，DWA）首先要在其速度空間內(nèi)采取多組的速度，通過計算采樣的多組速度數(shù)據(jù)進(jìn)行模擬，模擬出在一定時間內(nèi)的軌跡，通過一種評價函數(shù)，對采樣的速度的軌跡模擬進(jìn)行評價打分，選取最優(yōu)的速度進(jìn)行執(zhí)行。DWA算法要先模擬出機(jī)器人的運動模型，根據(jù)機(jī)器人的硬件運行性能對其運動軌跡進(jìn)行模擬，主要是根據(jù)是否為全向移動機(jī)器人進(jìn)行區(qū)別。確定好機(jī)器人模型后下一步進(jìn)行速度采樣，確定機(jī)器人的最小和最大速度的限制，由于機(jī)器人的電機(jī)力矩有限，存在最大加速度限制，在模擬軌跡是實際達(dá)到的速度應(yīng)該是一個窗口速度。另外，為了保證機(jī)器人能夠避免撞到障礙物，在最大減速影響下，對其速度進(jìn)行約束限制。對速度采樣完成后，對采樣空間內(nèi)的速度通過評價函數(shù)進(jìn)行評分，記錄評價最優(yōu)的速度樣本，進(jìn)行對機(jī)器人驅(qū)動。動態(tài)窗口算法示意圖如圖5所示。

圖5 動態(tài)窗口算法示意圖

針對動態(tài)窗口法穿越稠密障礙物時存在路徑不合理、速度和安全性不能兼顧等問題，王永雄等[33]通過將其速度采樣改進(jìn)，提出將其參數(shù)自適應(yīng)的DWA算法。針對于機(jī)器人在一些特定場景下，例如：上下坡路面存在的加速度過大、造成局部的路徑偏差過大等問題，張瑜等[34]提出對采樣速度空間的運動模型進(jìn)行改進(jìn)，對其速度約束進(jìn)行優(yōu)化，然后，基于激光里程計對軌跡模擬，對其進(jìn)行融合，進(jìn)行誤差補(bǔ)償，改善了特定場景下偏差較大的問題。

基于DWA算法的移動機(jī)器人在障礙物環(huán)境比較復(fù)雜的環(huán)境下，難以選擇最優(yōu)路徑。基于此常新新等[35]提出一種改進(jìn)的DWA算法，對移動機(jī)器人避障效果進(jìn)行優(yōu)化，主要是通過激光雷達(dá)探尋到障礙物的方位，根據(jù)預(yù)先設(shè)計的優(yōu)化方位角范圍，選取在范圍內(nèi)的軌跡。改進(jìn)后的算法在較為復(fù)雜的障礙物環(huán)境下通過選擇較優(yōu)角度范圍，在一定程度上減少了需要評價的軌跡數(shù)目，運行效率有所提高。

3 分析和討論

本文主要對一些常用的路徑規(guī)劃算法進(jìn)行總結(jié)，對一些算法的優(yōu)缺點和應(yīng)用場景進(jìn)行概述，結(jié)果如表1所示。

表1 常用路徑規(guī)劃算法表

目前大部分的路徑規(guī)劃算法都已在相應(yīng)機(jī)器人上得以應(yīng)用。但在現(xiàn)實復(fù)雜環(huán)境中，一般的算法表現(xiàn)不佳，通過優(yōu)化已有的常規(guī)路徑規(guī)劃算法，已在實際應(yīng)用中比較廣泛，但只能在其特定的理想環(huán)境下進(jìn)行，在實際的場景下，會不可避免地遇到各式各樣的問題。根據(jù)移動機(jī)器人在現(xiàn)實中的需求，將常規(guī)的算法在實時性、收斂速度、魯棒性或者是路徑的平滑性等某一方面或某些方面進(jìn)行相應(yīng)的改進(jìn)，同時也要保證路徑規(guī)劃的有效性。針對算法的某一特性進(jìn)行優(yōu)化可以快速的提高性能，使其滿足現(xiàn)實需求，對算法進(jìn)行特定方面的進(jìn)行一般性的改進(jìn)在實際中應(yīng)用的較為廣泛。目前路徑規(guī)劃算法已經(jīng)不僅僅局限在單個機(jī)器人，已經(jīng)逐漸應(yīng)用到集群機(jī)器人，以及多機(jī)器人多目標(biāo)的路徑規(guī)劃上，這就提高了規(guī)劃的難度，在規(guī)劃最優(yōu)路徑的同時也要將其他機(jī)器人算入其中，對實時性、有效性、準(zhǔn)確性都有了更高的要求。

由于各種路徑規(guī)劃算法的原理不同，不同算法的應(yīng)用場景也大不相同，傳統(tǒng)的算法具有很強(qiáng)的有效性，但其在實際應(yīng)用中實用性較差，智能仿生算法一般在收斂速度方面較為迅速，但同時也易于陷入局部最優(yōu)，單獨的算法往往不能成功應(yīng)用于實際環(huán)境中，借助不同算法的優(yōu)缺點成為解決問題的關(guān)鍵。目前，基于機(jī)器學(xué)習(xí)融合路徑規(guī)劃算法的表現(xiàn)較為優(yōu)異，基于神經(jīng)網(wǎng)絡(luò)，人工智能算法的路徑規(guī)劃算法具有很大的應(yīng)用潛力。

4 結(jié)束語

本文通過研究路徑規(guī)劃算法的原理機(jī)制，分析各種算法的優(yōu)缺點，對部分的改進(jìn)算法進(jìn)行了分析，對其應(yīng)用場景進(jìn)行了闡述。目前，大部分路徑算法已廣泛應(yīng)用移動機(jī)器人的路徑規(guī)劃算法中，但當(dāng)面臨現(xiàn)實多變的場景下，移動機(jī)器人的路徑規(guī)劃仍然難以滿足復(fù)雜環(huán)境中要求。因此移動機(jī)器人在路徑效率、路線的優(yōu)化等問題上需要提高。同時對于不同算法的評價函數(shù)，大多都是對障礙物的表示進(jìn)行不同程度的簡化，通常都是近似為矩形、圓形等較為簡單的形狀，在現(xiàn)實的場景下，可能因過于簡化對搜尋最優(yōu)路徑存在影響。