1 引言

所謂移動機器人路徑規劃技術，就是機器人根據自身傳感器對環境的感知，自行規劃出一條安全的運行路線，同時高效完成作業任務．移動機器人路徑規劃主要解決3個問題：1）使機器人能從初始點運動到目標點；2）用一定的算法使機器人能繞開障礙物，并且經過某些必須經過的點完成相應的作業任務；3）在完成以上任務的前提下，盡量優化機器人運行軌跡，機器人路徑規劃技術是智能移動機器人研究的核心內容之一，它起始于20世紀70年代，迄今為止，己有大量的研究成果報道，部分學者從機器人對環境感知的角度，將移動機器人路徑規劃方法分為3種類型。基于環境模型的規劃方法、基于事例學習的規劃方法和基于行為的路徑規劃方法；從機器人路徑規劃的目標范圍看，又可分為全局路徑規劃和局部路徑規劃；從規劃環境是否隨時間變化方面看，還可分為靜態路徑規劃和動態路徑規劃。

本文從移動機器人路徑規劃的具體算法與策略上，將移動機器人路徑規劃技術概括為以下4類：模版匹配路徑規劃技術、人工勢場路徑規劃技術、地圖構建路徑規劃技術和人工智能路徑規劃技術，分別對這幾種方法進行總結與評價，展望了移動機器人路徑規劃的未來發展方向。

2 模版匹配路徑規劃技術

模版匹配方法是將機器人當前狀態與過去經歷相比較，找到最接近的狀態，修改這一狀態下的路徑，便可得到一條新的路徑，即首先利用路徑規劃所用到的或已產生的信息建立一個模版庫，庫中的任一模版包含每一次規劃的環境信息和路徑信息，這些模版可通過特定的索引取得；隨后將當前規劃任務和環境信息與模版庫中的模版進行匹配，以尋找出一個最優匹配模版；然后對該模版進行修正，并以此作為最后的結果，模版匹配技術在環境確定情況下，有較好的應用效果，如Vasudevan等提出的基于案例的自治水下機器人(AUV)路徑規劃方法，Liu等提出的清潔機器人的模版匹配路徑規劃方法，為了提高模版匹配路徑規劃技術對環境變化的適應性，部分學者提出了將模版匹配與神經網絡學習相結合的方法，如Ram等將基于事例的在線匹配和增強式學習相結合，提高了模版匹配規劃方法中機器人的自適應性能，使機器人能部分地適應環境的變化，以及Arleo等將環境模版與神經網絡學習相結合的路徑規劃方法等。

模版匹配路徑規劃方法原理簡單，在匹配成功時效果較好，但該方法的致命缺陷是依賴機器人的過去經驗，如果案例庫中沒有足夠的路徑模版，就可能找不到與當前狀態相匹配的路徑；同時該方法主要針對靜態環境的路徑規劃，一旦環境動態變化，則較難找到匹配的路徑模版，這些不足嚴重限制了模版匹配路徑規劃技術的深入研究與推廣應用，因此模版匹配要具有足夠匹配的案例（路徑）及對環境變化的適應性。

3 人工勢場路徑規劃技術

人工勢場路徑規劃技術的基本思想是將機器人在環境中的運動視為一種機器人在虛擬的人工受力場中的運動。障礙物對機器人產生斥力，目標點對機器人產生引力，引力和斥力的合力作為機器人的控制力，從而控制機器人避開障礙物而到達目標位置。

早期人工勢場路徑規劃研究是一種靜態環境的人工勢場，即將障礙物和目標物均看成是靜態不變的，機器人僅根據靜態環境中障礙物和目標物的具體位置規劃運動路徑，不考慮它們的移動速度。然而，現實世界中的環境往往是動態的，障礙物和目標物都可能是移動的，為了解決動態環境中機器人的路徑規劃問題，Fujimura等提出一種相對動態的人工勢場方法，將時間看成規劃模型的一維參量，而移動的障礙物在擴展的模型中仍被看成是靜態的，這樣動態路徑規劃仍可運用靜態路徑規劃方法加以實現。該方法存在的主要問題是假設機器人的軌跡總是已知的，但這一點在現實世界中難以實現，對此，Ko等將障礙物的速度參量引入到斥力勢函數的構造中，提出動態環境中的路徑規劃策略，并給出了仿真結果，但是，該方法的兩個假設使其與實際的動態環境存在距離：1）僅考慮環境中障礙物的運動速度，未考慮機器人的運動速度；2）認為障礙物與機器人之間的相對速度是固定不變的，這不是完整的動態環境，對于動態路徑規劃問題來說，與機器人避障相關的主要是機器人與障礙物之間的相對位置和相對速度，而非絕對位置和速度，對此，Ge等將機器人與目標物的相對位置與相對速度引入吸引勢函數，將機器人與障礙物的相對位置與相對速度引入排斥勢函數，提出動態環境下的機器人路徑規劃算法，并將該算法應用于全方位足球移動機器人的路徑規劃中，取得了比較滿意的仿真與實驗結果．Dennis等在此基礎上，進一步考慮到多障礙物的路徑規劃和人工勢場路徑規劃的局部極小問題，提出移動機器人“能見度勢場”的概念，給出一種障礙物削減策略，以解決多障礙物路徑規劃產生的計算量激增問題，最近，Jaradat等將模糊理論與人工勢場技術相結合，提出模糊人工勢場算法，并與機器人動力學模型相結合，給出了相對完整的移動機器人路徑規劃與驅動控制方法。

人工勢場路徑規劃技術原理簡單，便于底層的實時控制，在機器人的實時避障和平滑軌跡控制等方面得到了廣泛研究。但人工勢場路徑規劃方法通常存在局部極小點，盡管也有不少針對局部極小的改進方法，但到目前為止，仍未找到完全滿意的答案。另外，在引力和斥力場設計時存在人為不確定因素，在障礙物較多時還存在計算量過大等問題，這些因素的存在限制了人工勢場路徑規劃方法的廣泛應用。應用中的難點是動態環境中引力場與斥力場的設計、局部極小問題的解決。

4 地圖構建路徑規劃技術

地圖構建路徑規劃技術，是按照機器人自身傳感器搜索的障礙物信息，將機器人周圍區域劃分為不同的網格空間（如自由空間和限制空間等），計算網格空間的障礙物占有情況，再依據一定規則確定最優路徑，地圖構建又分為路標法和柵格法，也稱單元分解法。前者是構造一幅由標志點和連接邊線組成的機器人可行路徑圖，如可視線方法、切線圖方法、Voronoi圖方法和概率圖展開法等。

可視圖法將機器人看成一個點，機器人、目標點和多邊形障礙物的各頂點進行組合連接，并保證這些直線均不與障礙物相交，便形成一張圖，稱為可視圖，由于任意兩直線的頂點都是可見的，從起點沿著這些直線到達目標點的所有路徑均是運動物體的無碰路徑，路徑規劃就是搜索從起點到目標點經過這些可視直線的最短距離問題；切線圖法和Voronoi圖法對可視圖法進行了改造，切線圖法以多邊形障礙物模型為基礎，任意形狀障礙物用近似多邊形替代，在自由空間中構造切線圖，因此從起始點到目標點機器人是沿著切線行走，即機器人必須幾乎接近障礙物行走，路徑較短，但如果控制過程中產生位置誤差，移動機器人碰撞的可能性會很高，Voronoi圖由一系列的直線段和拋物線段構成，直線由兩個障礙物的頂點或兩個障礙物的邊定義生成，直線段上所有點必須距離障礙物的頂點或障礙物的邊相等，拋物線段由一個障礙物的頂點和一個障礙物的邊定義生成，拋物線段同樣要求與障礙物頂點和障礙物的邊有相同距離，與切線法相比，Voronoi圖法從起始節點到目標節點的路徑將會增長，但采用這種控制方式時，即使產生位置誤差，移動機器人

也不會碰到障礙物，安全性較高，圖1為切線圖法與Voronoi圖法示意圖。

圖1 切線圖法與Voronoi圖法

柵格法是將機器人周圍空間分解為相互連接且不重疊的空間單元；柵格(cell)，由這些柵格構成一個連通圖，依據障礙物占有情況，在此圖上搜索一條從起始柵格到目標柵格無碰撞的最優路徑．這其中根據柵格處理方法的不同，又分為精確柵格法和近似柵格法，后者也稱概率柵格法。精確柵格法是將自由空間分解成多個不重疊的單元，這些單元的組合與原自由空間精確相等，如圖2就是常用的一種精確柵格分解法一一梯形柵格分解。

圖2 梯形柵格分解示意圖

與精確柵格法不同，近似柵格法的所有柵格都是預定的形狀，通常為矩形，整個環境被分割成多個較大的矩形，每個矩形之間都是連續的，典型的方法是“四叉樹”法，如果大矩形內部包含障礙物或者邊界，則將其分割成4個小矩形，對所有稍大的柵格都進行這種劃分，然后在劃分的最后界限內形成的小柵格間重復執行該程序，直到達到解的界限為止。

地圖構建法直觀明了，它常與其他路徑規劃方法集成使用，如Araujo提出的ART神經網絡的地圖構建路徑規劃算法，Najjaran提出的卡爾曼濾波器的地圖構建路徑規劃，Yang等提出的基于生物啟發神經網絡與地圖構建集成的清潔機器人完全覆蓋路徑規劃技術(CCPP)等。

目前，地圖構建技術已引起機器人研究領域的廣泛關注，成為移動機器人路徑規劃的研究熱點之一，但機器人傳感器信息資源有限，使得網格地圖障礙物信息很難計算與處理，同時由于機器人要動態快速地更新地圖數據，在網格數較多、分辨率較高時難以保證路徑規劃的實時性，因此，地圖構建方法必須在地圖網格分辨率與路徑規劃實時性上尋求平衡。

5 人工智能路徑規劃技術

人工智能路徑規劃技術是將現代人工智能技術應用于移動機器人的路徑規劃中，如人工神經網絡、進化計算、模糊邏輯與信息融合等。遺傳算法是最早應用于組合優化問題的智能優化算法，該算法及其派生算法在機器人路徑規劃研究領域已得到應用，在蟻群算法較好解決旅行商問題(TSP)的基礎上，許多學者進一步將蟻群優化算法引入到水下機器人(UV)的路徑規劃研究中。最近，徐玉如等考慮了海流因素的影響，提出了一種基于遺傳算法和粒子群優化(PSO)算法的AUV全局路徑規劃思想，由于模糊邏輯和信息融合技術在不確定性信息處理方面有極好的表現，且移動機器人傳感器采集的環境信息存在不確定性和不完整性，使得模糊邏輯和信息融合技術在移動機器人路徑規劃中有較好的應用，如Lang等針對全覆蓋路徑規劃提出的移動機器人模糊路徑規劃方法，Perez等提出的基于速度場的模糊路徑規劃方法等，Zun等提出基于信息融合技術的移動機器人和無人機的路徑規劃與避碰方法。神經網絡作為人工智能的重要內容，在移動機器人路徑規劃研究中得到了廣泛關注，如Ghatee等將Hopfield神經網絡應用到路徑距離的優化中；Zhu等將自組織SOM神經網絡應用到多任務多機器人的任務分配與路徑規劃中，近年來加拿大學者Simon提出一種新的生物啟發動態神經網絡模型，將神經網絡的神經元與二維規劃空間的離散坐標對應起來，通過規定障礙物和非障礙物對神經元輸入激勵和抑制的不同，直接計算相關神經元的輸出，由此判定機器人的運行方向，由于該神經網絡不需要學習訓練過程，路徑規劃實時性好，同時利用神經網絡本身的快速衰減特性，較好地解決了機器人路徑規劃的死區問題。圖3為用于局部路徑規劃的生物啟發神經網絡結構圖，圖中所示為機器人（處于神經元處）傳感器的感受半徑，每個神經元與環境位置坐標對應，動態計算機器人鄰近神經元輸出，機器人根據神經元輸出大小決定下一步運行目標，從而實現安全的路徑規劃。

人工智能技術應用于移動機器人路徑規劃，增強了機器人的“智能”特性，克服了許多傳統規劃方法的不足，但該方法也有不足之處，有關遺傳優化與蟻群算法路徑規劃技術主要針對路徑規劃中的部分問題，利用進化計算進行優化處理，并與其他路徑規劃方法結合在一起使用，單獨完成路徑規劃任務的情況較少。信息融合技術主要應用于機器人傳感器信號處理方面，而非直接的路徑規劃策略，對神經網絡路徑規劃而言，大多數神經網絡路徑規劃均存在規劃知識的學習過程，不僅存在學習樣本難以獲取，而且存在學習滯后問題，從而影響神經網絡路徑規劃的實時性，生物啟發神經網絡路徑規劃雖然實時性較好，但其輸入激勵與抑制的設定也存在人為不確定因素。

圖3 基于生物啟發神經網絡路徑規劃

6 移動機器人路徑規劃技術展望

毫無疑問，移動機器人路徑規劃研究已取得了重要進展，但在具體規劃算法設計中，均有它們的局限性。如模版匹配方法過于依賴機器人過去的經驗；人工勢場路徑規劃方法通常存在局部極小點和計算量過大的問題；地圖構建與人工神經網絡技術均存在路徑規劃的實時性問題，從過去的研究狀況和機器人未來的發展需求來看，目前移動機器人路徑規劃技術研究主要集中在以下幾個方面。

6.1 新的路徑規劃方法的研究

新的路徑規劃方法研究，永遠是移動機器人路徑規劃的重要內容，主要是其結合了現代科技的發展（如新的人工智能方法、新的數理方法等），尋找易于實現，同時能避開現有方法缺點的新技術。另外，現代集成路徑規劃算法研究也是一個重要內容，即利用已有的各種規劃方法的優點，克服他們的不足。如神經網絡與地圖構建技術結合、信息融合與地圖構建技術集成、進化計算與人工勢場技術的結合等。

6.2 機器人底層控制與路徑規劃算法的結合研究

以上是從路徑規劃策略上看移動機器人路徑規劃的發展．從應用角度看，路徑規劃的研究極大多數集中在規劃算法的設計與仿真研究上，而將路徑規劃算法應用于實際的報道還很少，即使是一些實物仿真實驗，研究也較少，但理論研究最終要應用于實際，因此有關機器人底層控制與路徑規劃算法的結合研究將是它的發展方向之一，不僅要研究路徑規劃算法，而且要研究機器人的動力學控制與軌跡跟蹤，使機器人路徑規劃研究實用化、系統化。

6.3 多機器人任務分配、通信協作及路徑規劃的研究

以往有關單機器人的路徑規劃研究報道較多，而多機器人路徑規劃及相關技術研究較少，實際上，多機器人協作作業與路徑規劃在現實世界還非常常見，如足球機器人比賽、空中無人機編隊飛行、自治水下機器人的合作搜救與觀察等，它將涉及多方面研究，包括多機器人多任務分配問題、機器人之間的協作與通信問題、機器人的全局與局部路徑規劃問題、機器人傳感與控制問題等。

6.4 高維環境中移動機器人路徑規劃的研究

從路徑規劃的環境描述來看，針對二維平面環境的路徑規劃研究較多，而三維環境下的路徑規劃研究較少，但是，大多數機器人作業與運行是在三維空間中進行的，如飛行機器人、水下機器人等。因此，加強三維環境中移動機器人路徑規劃技術的研究是機器人技術實際應用的需要，也是移動機器人路徑規劃技術的發展方向之一。

6.5 空中機器人與水下機器人的研究

從具體的研究對象來看，移動機器人路徑規劃大多是針對陸地工作的智能機器人展開路徑規劃研究，如足球機器人、清掃機器人、收割機器人等；而針對空中飛行機器人和自治水下機器人的研究較少。陸地機器人一般是處于溫和的現實世界，而空中機器人與水下機器人面臨的外部環境非常惡劣，傳感器資源更加有限，甚至會面臨一種敵對的不確定的危險環境，因此，他們的路徑規劃與避險研究更加困難和迫切。

7 結論

智能移動機器人路徑規劃問題一直是機器人研究的核心內容之一，本文從模版匹配路徑規劃、人工勢場路徑規劃、地圖構建路徑規劃和人工智能路徑規劃4個方面，對移動機器人路徑規劃技術研究現狀及其未來發展進行系統的總結與評價，對移動機器人技術目前的研究與未來的發展將有一定的參考價值。