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

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

0 引言

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

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

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

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

1.1 路徑定義

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

圖1 移動機器人運動過程

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

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

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

1.3 性能分析

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

表1 路徑算法對比

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

2.1 行車圖法

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

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

圖3 行車圖法

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

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

2.2 單元分解法

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

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

圖4 單元分解法

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

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

圖5 檢測加權值

2.3 A*算法

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

圖6 A*算法

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

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

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

2.4 勢場法

勢場法基本思想根據路徑目標點對移動機器人產生吸引力，障礙物對移動機器人產生排斥力，將吸引力和排斥力的合力構成移動機器人的控制率，如圖7所示。

圖7 勢場法

由勢場法可得吸引磁場產生的吸引力隨著目標點靠近逐漸減小，到達目標點后吸引力為0；排斥磁場產生的排斥力隨著障礙物靠近而增大，當障礙物距離大于預定閾值，排斥力為0。若目標點與障礙物之間距離較近時，易受到吸引磁場和排斥磁場反復作用，容易產生震蕩和死鎖現象。

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

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

2.5 螞蟻算法

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

圖8 螞蟻搜索示意圖

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

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

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

2.6 粒子群算法

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

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

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

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

2.7 遺傳算法

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

圖9 遺傳算法

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

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

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

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

3.1 PRM算法（Probabilistic roadmap）

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

圖10 PRM連通

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

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

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

3.2 RRT算法（Rapidly－Exploring Random Tree）

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

圖11 RRT算法

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

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

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

4 算法概括

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

表2 改進算法的特征及優(yōu)缺點

續(xù)表2

5 移動機器人展望

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

5.1 更高智能化

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

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

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

5.3 新路徑算法的研究

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

5.4 多機器人協作

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

6 結束語

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