邵偉偉，吳玉秀，范冬冬

（安徽工業(yè)大學，安徽 馬鞍山 243002）

隨著機器人技術的發(fā)展，機器人已經(jīng)不再是只會機械的執(zhí)行指令的傳統(tǒng)機器人，其正朝著智能化、多樣化和大眾化的方向發(fā)展。智能機器人運用了多學科前沿的研究理論與成果，進入新世紀以來機器人技術得到飛速的提升，因其具有高效性、精準性、實用性等，它們已經(jīng)被廣泛的運用到工業(yè)生產(chǎn)、軍事領域等各行業(yè)中。機器人技術是國家科技實力的體現(xiàn)，以機器人為代表的人工智能將引領著下一代的產(chǎn)業(yè)革命，因此各國政府紛紛增加它們對機器人行業(yè)的投入。

智能化的移動機器人將代表著機器人今后的發(fā)展趨勢，作為研究者重點研究的對象——移動機器人路徑規(guī)劃技術[1]，也隨著機器人技術快速的發(fā)展而發(fā)展，本文簡要的論述幾種常用的路徑規(guī)劃方法。

1 路徑規(guī)劃技術的簡介

移動機器人通過視覺傳感器、聲吶傳感器等裝置感知工作環(huán)境以及移動機器人的狀態(tài)，使它能在存在障礙物的工作環(huán)境中快速搜尋出一條從設定的起點到目標點的最優(yōu)無碰路徑，該技術即為路徑規(guī)劃技術[2]。路徑規(guī)劃不是純粹性的追求一條距離最短的路徑，而是根據(jù)具體的環(huán)境和人們的要求做出合理的決策，從而規(guī)劃出一條最優(yōu)路線[3]。目前人們對路徑規(guī)劃技術的研究主要是如下三個方面：（1）移動機器人在給定的全局環(huán)境中行走，必須避開各種靜態(tài)（或動態(tài)）的障礙物，一路無碰撞的到達目標點；（2）機器人在向目標行進的過程中，運用傳感器等裝置探測出前方路徑存在的不確定因素，能在短時間之內(nèi)應對由各種原因所造成的誤差并予以修正；（3）根據(jù)人們的具體要求，搜索出一條最優(yōu)行走路線。現(xiàn)階段研究者按照不同標準對路徑規(guī)劃技術算法進行歸類，使之分成不同模型，本文采取最常用的以規(guī)劃目標為分類標準的規(guī)劃方式對路徑規(guī)劃技術進行論述。

2 全局路徑規(guī)劃的方法

研究者按照機器人在移動之前是否完感知機器人的工作環(huán)境，將路徑規(guī)劃分為全局路徑規(guī)劃與局部路徑規(guī)劃，全局路徑規(guī)劃的工作環(huán)境已知，局部路徑規(guī)劃的工作環(huán)境未知或只知道一部分的工作環(huán)境，但是這兩種模型之間卻無實質(zhì)區(qū)別，它們之間的規(guī)劃方法在經(jīng)過改進后可以相互轉(zhuǎn)換[4]。

全局路徑規(guī)劃常用的方法如下:道路圖規(guī)劃方法、圖搜索法以及快速擴展隨機樹算法等。

2.1 道路圖規(guī)劃方法

道路圖規(guī)劃方法是一種比較直觀的路徑規(guī)劃方法，它可以根據(jù)障礙物的形狀對機器人前進的空間實施分解從而進行最優(yōu)無碰規(guī)劃，通過把分解得到的路徑連接起來，通過算法尋找出一條最優(yōu)的無碰平滑曲線，常用的道路圖規(guī)劃方法有可視圖法、Voronoi圖法等[5]。

可視圖法：把機器人看成一個大小、形狀可以忽略的質(zhì)點，把移動機器人的起點、每個障礙物的頂點以及目標點通過直線連接在一起，而連接在一起的直線不能穿越障礙物，由此可以獲得一張無碰撞的路徑圖，即為可視圖[6]。利用可視圖可以清晰明了的得到一些無碰路徑，通常采用優(yōu)化算法可以淘汰一些沒必要的直線從而使可視圖法搜索路徑的時間變的短一些，路徑規(guī)劃器從可視圖中選取一條最優(yōu)路徑作為移動機器人的規(guī)劃路徑。圖1為可視圖。

圖1 可視圖

因可視圖法簡單明了，易于操作，通常在離散空間中，移動機器人在路徑規(guī)劃時常采用可視圖法。雖然可視圖法性能優(yōu)異，但它有以下缺點制約著它的使用：（1）隨著障礙物數(shù)量增加，尤其是在環(huán)境空間中增加復雜的多邊形障礙物，其頂點較多，使可視圖法的連線增多，加大了其復雜性，致使其優(yōu)點喪失；（2）任何機器人都不可能是大小不計的質(zhì)點，當機器人行走在利用可視圖法規(guī)劃的路徑中，因為規(guī)劃的模型中把機器人看成質(zhì)點，所以當機器人靠近障礙物時就有可能碰撞障礙物，通常的解決方法是把障礙物體積適當?shù)呐蚧蛘咝薷穆窂诫x障礙物的距離，這會使規(guī)劃出的路徑不是最優(yōu)路徑[7]。

Voronoi圖法：Voronoi圖法與可視圖法的不同，它的規(guī)劃理念是讓機器人與障礙物的間距最大，從而使機器人遠離障礙物[8]。采用Voronoi圖時，路徑規(guī)劃器通過算法選取自由空間中的點，計算它們距離障礙物最近的距離，根據(jù)障礙物的形狀，畫出與障礙物等距離的直線或曲線，經(jīng)過多次取點畫線，所得到的完整封閉曲線圖即為Voronoi圖，通過算法在Voronoi圖中選取一條最優(yōu)路徑即為規(guī)劃的路徑。雖然Voronoi圖法規(guī)劃出的路徑不是最短路徑，但它所規(guī)劃出的路徑不會有碰撞現(xiàn)象，其安全性強。

圖2 Voronoi圖

2.2 圖搜索法

基于圖搜索法的路徑規(guī)劃規(guī)劃技術也常常被人采用，它與可視圖法一樣簡單清晰，常用的圖搜索法有柵格法等。

柵格法：柵格法是將移動機器人工作的空間劃分成多個相互連接的規(guī)則柵格，柵格通常分為自由柵格與障礙柵格，沒有障礙物的柵格稱為自由柵格，而有障礙物的柵格稱為障礙柵格。柵格通常采用直角坐標法或標號法進行標識，常采用四叉樹表示，根據(jù)障礙柵格積累值CV(certainly Value)的大小，采用控制算法計算，避開CV值較大的障礙柵格，從而得到一條無碰的最優(yōu)路徑[9]，其中積累值CV表示柵格中存在障礙物的可信度。

柵格法在構(gòu)造柵格的過程中，會有一定的局限性，如果柵格構(gòu)建的過大，其精準性就會下降，雖然路徑規(guī)劃的時間短，但極有可能找不到路徑；如果柵格構(gòu)建的過小，導致模型的分辨率過高，這樣就會加大了路徑規(guī)劃器的計算量，使路徑規(guī)劃的時間過長，這些都是不允許的?，F(xiàn)階段的一種解決辦法是采用適當放大的柵格進行規(guī)劃，如果在柵格里發(fā)現(xiàn)障礙物則再把該柵格給細分成多個小柵格，再進行路徑規(guī)劃，如果在柵格里沒發(fā)現(xiàn)障礙物則對此柵格不做細分，進行正常的路徑規(guī)劃，這就很好的解決了柵格的分辨率問題。

2.3 快速擴展隨機樹算法

快速擴展隨機樹算法 （RRT算法）：在自由空間中，把機器人的初始出發(fā)點看成隨機樹的根節(jié)點，在約束條件限制下采用隨機函數(shù)生成新節(jié)點，使新節(jié)點與上一個節(jié)點之間的連線不穿過障礙物，該連線作為樹干，新節(jié)點作為父節(jié)點繼續(xù)產(chǎn)生新的節(jié)點，并構(gòu)造出新的樹干，直至產(chǎn)生的新節(jié)點與目標點相重合時，隨機樹的構(gòu)造結(jié)束，在此過程中產(chǎn)生的從出發(fā)點到目標點的樹干即為規(guī)劃的路徑[10]。圖3為快速擴展隨機樹的構(gòu)造過程。

RRT算法采用了最優(yōu)控制理論使其相比于其它搜索方法具有較強的搜索特性，能夠合理的規(guī)劃出一條無碰路徑，RRT算法運用在復雜的高維空間中的優(yōu)勢更為明顯。RRT算法同其它算法一樣，也有一些缺點：（1）因為由RRT算法所規(guī)劃的路徑具有一定的隨機性，所以由它規(guī)劃的路徑常常會出現(xiàn)不平滑的現(xiàn)象，因此在實際應用中采用了非完整性約束的機器人則不能使用RRT算法進行規(guī)劃；（2）由RRT算法規(guī)劃出的路徑通常都具有隨機性，因此會導致規(guī)劃出的路徑往往不是最優(yōu)的路徑；（3）RRT算法一般運用在已知的全局環(huán)境模型中，它不適用于動態(tài)環(huán)境的規(guī)劃。針對上述缺點，現(xiàn)在有許多研究者采用不同的算法對RRT算法進行改進，或采用RRT算法與其它算法合用，從而讓它更加適用于路徑規(guī)劃。

圖3 快速擴展隨機樹的構(gòu)造過程

3 局部路徑規(guī)劃的方法

局部路徑規(guī)劃常用的方法如下:遺傳算法、人工勢場法與滾動窗口法等。

3.1 遺傳算法

在上世紀60年代提出遺傳算法后，人們不斷的對遺傳算法進行改進，現(xiàn)階段遺傳算法已經(jīng)應用到許多學科，它在路徑規(guī)劃中的應用也日趨成熟[11]。遺傳算法采用模擬自然界的遺傳機制，在進化過程中尋找最優(yōu)解，從而找到最優(yōu)路徑，其原理如下：在自由空間中，生成多條路徑，將路徑中的一些點采用二進制編碼法或采用積木塊編碼法對其進行編碼，編碼完成后形成群體，再通過遺傳操作進行計算，常用的遺傳算子有：選擇算子、交叉算子、復制算子和變異算子，采用適應函數(shù)進行篩選所得到的值，產(chǎn)生新的節(jié)點，構(gòu)成子路徑。在群體多次進化后，便可得到最優(yōu)解，即得到平滑的最優(yōu)路徑，遺傳算法的流程圖如圖4。

圖4 遺傳算法流程圖

遺傳算法與大多數(shù)采用單點搜索的控制算法不同，它采用多點搜索從而使遺傳算法能解決一些算法不能解決的問題，使遺傳算法能得到近似全局最優(yōu)解，進而避免陷入局部最優(yōu)解。同其它的算法一樣，遺傳算法也存在著缺陷，遺傳算法容易過早的收斂導致 “早熟”，使路徑規(guī)劃失敗[12]；另外，遺傳算法所用時間比其它算法普遍偏長，而且它的效率偏低也是一個不能忽略的問題。

3.2 人工勢場法

人工勢場法是通過在機器人工作的空間里構(gòu)造一種虛擬的力場，使目標點與障礙物分別對移動的機器人產(chǎn)引斥力和斥力。在構(gòu)造人工勢場時，通常把機器人看作一個大小不計的質(zhì)點，在引力場與斥力場的共同影響下使機器人以平滑路徑走向目標點[13]。人工勢場法的原理如下：在機器人行進過程中，機器人搜索到附近有障礙物時，倘若機器人和障礙物的距離R大于障礙物的影響距離r，斥力可以忽略不計；若R小于r時，F(xiàn)與r成反比，當R→0時，則F→∞，所以機器人在運動的過程中不會出現(xiàn)碰撞現(xiàn)象。機器人在引力場和斥力場的共同作用下，最終走向目標點，由此規(guī)劃出的路徑則是一條無碰的最優(yōu)路徑。

雖然人工勢場法所得到的路徑是一條無碰路徑，但它自身也存在著一些局限性，例如因為對周圍的感知能力有限會產(chǎn)生局部極小值，有時甚至在一些凹形障礙物附近，呈現(xiàn)出振蕩現(xiàn)象，產(chǎn)生“死鎖”效應。針對以上人工勢場法產(chǎn)生的缺陷，人們在出現(xiàn)上述局部空間中，通常會增加一個虛擬的障礙物使之產(chǎn)生斥力場，與之前形成的合力場形成新的合力場，使機器人逃脫“陷阱”，從而減少“死鎖”對路徑規(guī)劃所產(chǎn)生的不良影響。

3.3 滾動窗口法

如果機器人工作在未知的動態(tài)環(huán)境中，滾動窗口法相比于一般的局部規(guī)劃算法適應性更強[14]。通常機器人在前進過程中，每前行一步就不斷的通過傳感器檢測去周圍障礙物信息，然后在機器人的滾窗中實時更新障礙物信息，并在滾窗中設置一個子目標，采用一些算法實時的規(guī)劃機器人在窗口中的路徑，使之能夠無碰的到達子目標，到達子目標后，根據(jù)新的滾窗信息，再設置下一個子目標，并完成路徑規(guī)劃，直至到達目標點，這一過程即為滾動窗口法[15]。

滾動窗口法對動態(tài)的障礙物常常采用場景預測的方法進行預判，從而找出一片安全區(qū)域供機器人行走，所以該方法的實時性很強，這也是滾動窗口法優(yōu)于其它算法的地方。一般情況下，滾動窗口法常和其它算法一起運用到路徑規(guī)劃中，從而使機器人能夠規(guī)劃出最佳路徑。

4 總結(jié)與展望

現(xiàn)階段傳感器性能的提升以及人們對各種新型算法的開發(fā)，使得機器人路徑規(guī)劃技術的精度越來越高，技術越來越成熟。上述的全局路徑規(guī)劃算法和局部路徑規(guī)劃算法雖然取得了較多的成果，但它們自身卻存在這各種各樣的缺點亟待解決。對于它們的缺點，可針對其自身的算法進行更改，或者在同一路徑規(guī)劃中，采用多種路徑規(guī)劃的方法相互結(jié)合進行路徑規(guī)劃，這樣就可以揚長避短，把誤差控制在最小。

現(xiàn)階段人們對智能算法的研究逐漸深入，隨著模擬退火算法、免疫克隆選擇算法、禁忌搜索等智能算法在路徑規(guī)劃中應用的深入，使得路徑規(guī)劃技術更加高效化、智能化，智能算法將代表著未來路徑規(guī)劃技術的發(fā)展方向，它對路徑規(guī)劃技術的快速發(fā)展將起到推動作用。

機器人在完成路徑規(guī)劃后，通常會得到一些不規(guī)則的曲線，這對機器人前行來說，會產(chǎn)生一些不利的影響，例如：機器人需要停車轉(zhuǎn)向，甚至有時得倒車轉(zhuǎn)向才能完整的貼合路徑行走，既耽誤了機器人的前行時間，又會讓機器人因來回停車轉(zhuǎn)向而危害機器人的電動機，這一點是需要注意的。雖然通過一定的環(huán)境模型能規(guī)劃出移動機器人的行走路徑，但在規(guī)劃完路徑后需要再通過一些算法把機器人的路徑變的平滑起來，使之滿足應用要求。