1 引言

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

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

2 模版匹配路徑規(guī)劃技術

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

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

3 人工勢場路徑規(guī)劃技術

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

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

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

4 地圖構建路徑規(guī)劃技術

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

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

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

圖1 切線圖法與Voronoi圖法

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

圖2 梯形柵格分解示意圖

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

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

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

5 人工智能路徑規(guī)劃技術

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

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

圖3 基于生物啟發(fā)神經(jīng)網(wǎng)絡路徑規(guī)劃

6 移動機器人路徑規(guī)劃技術展望

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

6.1 新的路徑規(guī)劃方法的研究

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

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

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

6.3 多機器人任務分配、通信協(xié)作及路徑規(guī)劃的研究

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

6.4 高維環(huán)境中移動機器人路徑規(guī)劃的研究

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

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

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

7 結論

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