1、引言

    所謂移動機器人路徑規(guī)劃技術(shù)，就是機器人根據(jù)自身傳感器對環(huán)境的感知，自行規(guī)劃出一條安全的運行路線，同時高效完成作業(yè)任務(wù)。移動機器人路徑規(guī)劃主要解決3個問題:

　　1)使機器人能從初始點運動到目標(biāo)點；

　　2)用一定的算法使機器人能繞開障礙物，并且經(jīng)過某些必須經(jīng)過的點完成相應(yīng)的作業(yè)任務(wù)；

　　3)在完成以上任務(wù)的前提下，盡量優(yōu)化機器人運行軌跡。

　　機器人路徑規(guī)劃技術(shù)是智能移動機器人研究的核心內(nèi)容之一，它起始于20世紀(jì)70年代，迄今為止，己有大量的研究成果報道。部分學(xué)者從機器人對環(huán)境感知的角度，將移動機器人路徑規(guī)劃方法分為3種類型:

　　基于環(huán)境模型的規(guī)劃方法、基于事例學(xué)習(xí)的規(guī)劃方法和基于行為的路徑規(guī)劃方法；

　　從機器人路徑規(guī)劃的目標(biāo)范圍看，又可分為全局路徑規(guī)劃和局部路徑規(guī)劃；

　　從規(guī)劃環(huán)境是否隨時間變化方面看，還可分為靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃。

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

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

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

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

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

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

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

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

    4、地圖構(gòu)建路徑規(guī)劃技術(shù)

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

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

圖 1 切線圖法與Voronoi圖法

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

圖 2 梯形柵格分解示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    7、結(jié)論

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