1 引言

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

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

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

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

模版匹配路徑規(guī)劃方法原理簡單，在匹配成功時效果較好，但該方法的致命缺陷是依賴機(jī)器人的過去經(jīng)驗(yàn)，如果案例庫中沒有足夠的路徑模版，就可能找不到與當(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ù)的基本思想是將機(jī)器人在環(huán)境中的運(yùn)動視為一種機(jī)器人在虛擬的人工受力場中的運(yùn)動。障礙物對機(jī)器人產(chǎn)生斥力，目標(biāo)點(diǎn)對機(jī)器人產(chǎn)生引力，引力和斥力的合力作為機(jī)器人的控制力，從而控制機(jī)器人避開障礙物而到達(dá)目標(biāo)位置。

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

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

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

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

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

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

圖1 切線圖法與Voronoi圖法

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

圖2 梯形柵格分解示意圖

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

地圖構(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)建集成的清潔機(jī)器人完全覆蓋路徑規(guī)劃技術(shù)(CCPP)等。

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

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

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

人工智能技術(shù)應(yīng)用于移動機(jī)器人路徑規(guī)劃，增強(qiáng)了機(jī)器人的“智能”特性，克服了許多傳統(tǒng)規(guī)劃方法的不足，但該方法也有不足之處，有關(guān)遺傳優(yōu)化與蟻群算法路徑規(guī)劃技術(shù)主要針對路徑規(guī)劃中的部分問題，利用進(jìn)化計(jì)算進(jìn)行優(yōu)化處理，并與其他路徑規(guī)劃方法結(jié)合在一起使用，單獨(dú)完成路徑規(guī)劃任務(wù)的情況較少。信息融合技術(shù)主要應(yīng)用于機(jī)器人傳感器信號處理方面，而非直接的路徑規(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ī)劃的實(shí)時性，生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃雖然實(shí)時性較好，但其輸入激勵與抑制的設(shè)定也存在人為不確定因素。

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

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

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

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

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

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

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

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

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

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

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

6.5 空中機(jī)器人與水下機(jī)器人的研究

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

7 結(jié)論

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