摘   要： 移動機器人路徑規(guī)劃技術是機器人研究領域中的核心技術之一。通過對全局路徑規(guī)劃和局部路徑規(guī)劃中各種方法的分析，指出了各種方法的優(yōu)點和不足以及改進的辦法，并對移動機器人路徑規(guī)劃技術的發(fā)展趨勢進行了展望。
關鍵詞： 移動機器人； 路徑規(guī)劃； 遺傳算法

    移動機器人是裝備了機械腿、輪子、關節(jié)、抓握器等執(zhí)行器以及控制器來完成特定任務的一種實體智能體。近年來，隨著科學技術的飛快發(fā)展，移動機器人在工業(yè)、農(nóng)業(yè)、醫(yī)療、服務、航空和軍事等領域得到了廣泛的應用，已成為學術研究的重點。在移動機器人的研究中，導航研究是核心，而路徑規(guī)劃是機器人導航研究的重要環(huán)節(jié)之一。在機器人執(zhí)行任務時，要求機器人在工作環(huán)境中（有障礙物或無障礙物）能根據(jù)一定的評價標準搜索一條從起始地點到目標地點的最優(yōu)或次優(yōu)路徑[1]。移動機器人的路徑規(guī)劃根據(jù)環(huán)境是否已知可分為基于地圖的全局路徑規(guī)劃和基于傳感器的局部路徑規(guī)劃。
1全局路徑規(guī)劃
1.1柵格分解法
    柵格分解法是目前廣泛研究的路徑規(guī)劃方法之一。該方法把移動機器人的運動環(huán)境分解為多個簡單的柵格并根據(jù)它們是否被障礙物占據(jù)來進行狀態(tài)描述，障礙物柵格和非障礙物柵格具有不同的標識值，它能快速直觀地融合傳感器信息。但是為了得到比較精確的規(guī)劃結(jié)果，必須將環(huán)境劃分為較小的柵格，這就導致存儲空間增大，在大規(guī)模環(huán)境下路徑規(guī)劃的計算復雜程度將加大。為了克服柵格表示的存儲空間問題，邰宜斌提了一種四叉樹分割方法[2]，該算法遞歸地把環(huán)境分解為大小不一的矩形區(qū)域，這些矩形區(qū)域或者完全被障礙物占據(jù)，或者是完全自由可行的。每次遞歸都將一個較大的柵格劃分為4個較小的柵格，取得了較好的計算效果。另外柵格分解法隨著機器人自由度的增加會出現(xiàn)“維數(shù)災難”問題，不適用于解決多自由度機器人在復雜環(huán)境中的路徑規(guī)劃。Frank在2004年提出了概率柵格分解算法，在該算法中引入隨機采樣，可使多自由度機器人在復雜環(huán)境中快速找到一條可行路徑。2006年呂太之等在概率柵格分解算法的基礎上引入了Anytime算法，將隨機采樣應用到柵格分解算法中，使算法效率得到了提高，但是受環(huán)境信息和隨機采樣的影響比較大[3]。
1.2拓撲法
    拓撲法主要包括三部分：劃分狀態(tài)空間、構(gòu)建特征網(wǎng)、在特征網(wǎng)上搜索路徑。拓撲法的基本要素是節(jié)點和邊，用節(jié)點表示某個特定的位置，用邊表示這些位置之間的聯(lián)系，可以用G=(V,E)描述空間的特征，其中V表示頂點集合，E表示連接頂點的邊集合[4]。利用該方法可縮小搜索空間，使得存儲需求小，適合于大規(guī)模環(huán)境的路徑規(guī)劃，但是構(gòu)建特征網(wǎng)的過程比較復雜，而且當障礙物增加時如何將增加的節(jié)點與已有節(jié)點進行節(jié)點匹配是一個難點。2005年，王力虎等提出了一種適用于清掃機器人的區(qū)域充滿拓撲算法，用傳感器感知環(huán)境信息以建立環(huán)境的拓撲地圖，機器人可以利用搜索圖的方法搜索環(huán)境，可達到環(huán)境的有效覆蓋，但在搜索時沒有具體體現(xiàn)節(jié)點間的距離、清掃覆蓋率等信息，使得搜索效率不是很高[5]。2006年，種琤等提出了一種基于掃描法的構(gòu)造環(huán)境拓撲圖方法，利用啟發(fā)式函數(shù)法實現(xiàn)對所構(gòu)建拓撲圖的擴展，采用了逐步構(gòu)建環(huán)境拓撲圖的方式，實現(xiàn)了在線構(gòu)建,可應用于任意工作環(huán)境，且計算復雜度低，但此算法不能保證搜索到最優(yōu)路徑[6]。
1.3懲罰函數(shù)法
    在機器人運行環(huán)境中因為有障礙物，使得機器人的路徑規(guī)劃成為一個有約束的問題，懲罰函數(shù)法將這個有約束的問題轉(zhuǎn)化為一系列無約束極小化問題，再通過解決這些無約束問題獲得原約束問題的最優(yōu)解[7]。柳在鑫、王進戈等在2009年將機器人的路徑規(guī)劃問題轉(zhuǎn)化為一類帶有不等式約束條件的非線性極小化問題，并采用懲罰函數(shù)法來求解此類問題，該方法原理簡單，算法易行，使用范圍廣[8]。
2 局部路徑規(guī)劃
2.1人工勢場法
    人工勢場法是機器人局部路徑規(guī)劃中最經(jīng)典的方法，該方法是由Khatib在1986年提出的，它的基本原理是：把機器人在工作環(huán)境中的運動看作是在一個人造受力場中的運動，其中目標對機器人產(chǎn)生引力，障礙物對機器人產(chǎn)生斥力，機器人在這兩類力的合力作用下向目標前進[9]，該合力就是機器人的加速度力，可用來控制機器人的運動方向，利用人工勢場法進行機器人的路徑規(guī)劃,計算簡單，所規(guī)劃的路徑光滑，有較好的實時性，但會因為局部最小值而導致目標點不能到達。近幾年來國內(nèi)陸續(xù)有學者提出了一些改進方法。2006年，劉義等提出了修改斥力函數(shù)法，用來解決局部最小值問題[10]。哈爾濱工業(yè)大學的張建英等提出了添加附加控制力的方法，即當機器人在障礙物附近振蕩，無法離開障礙物時，給機器人施加一個控制力，使機器人繞過障礙物向目標位置前進，但通過此方法規(guī)劃的路徑在障礙物邊緣有抖動現(xiàn)象產(chǎn)生[11]。
2.2遺傳算法
    遺傳算法(GA)的概念最初是由Bagley和Rosengerg于1967年在其博士論文中首先提出了的。在1975年美國Michigan大學的J. Holland教授把它寫到了專著《Adaptation in Natural and Artificial Systems》中，此后GA才逐漸為人所知，并且廣泛應用到控制、規(guī)劃、優(yōu)化設計等方面。利用GA算法對移動機器人進行路徑規(guī)劃的基本步驟為：
　 (1)選擇編碼方式，并將路徑用編碼表示；
　 (2)產(chǎn)生初始群體；
　 (3)確定適應度函數(shù)并根據(jù)適應度函數(shù)計算初始群體的適應度值；
　 (4)如果不滿足條件，{選擇、交換、變異、計算新一代群體的適應性值}；
　 (5)輸出結(jié)果。
    遺傳算法直接對移動機器人的路徑進行操作，采用概率化的尋優(yōu)方法，自適應地調(diào)整搜索方向，不采用確定性搜索規(guī)則，易于并行化，但對于未知復雜環(huán)境，利用遺傳算法進行路徑規(guī)劃時運算速度慢，而且需要占據(jù)大量的存儲空間。近幾年許多研究學者提出了一些改進后的遺傳算法，例如王洲等提出了移動機器人在靜態(tài)障礙物環(huán)境中路徑規(guī)劃的新方法，該方法設計了5個遺傳算子（選擇、交叉、變異、刪除、插入），并且提出了新的變異算子、插入算子和刪除算子，加快了較好個體在群體中的傳播，提高了路徑搜索速度和解的精度[12]。對于遺傳算法的改進，王新杰等將其與圖搜索法相結(jié)合，用Dijkstra算法王求得初始路徑，再利用遺傳算法的一系列選擇、交叉、變異操作來優(yōu)化路徑，這種方法減少了搜索的盲目性，不會產(chǎn)生無效路徑[13]。當機器人處于靜動態(tài)障礙物同時存在的環(huán)境中時，盧瑾等在機器人路徑規(guī)劃時引入了雙重遺傳算法機制，第一重算法針對靜態(tài)障礙物環(huán)境，第二重算法針對動態(tài)障礙物環(huán)境，兩重算法采用不同的適應度函數(shù)作為評價標準，通過改進操作算子、引入優(yōu)化算子，可快速有效地找到同時能避開靜動態(tài)障礙物的最優(yōu)路徑，仿真結(jié)果驗證了該方法的有效性。但對于動態(tài)的、未知復雜環(huán)境下的路徑規(guī)劃沒有進行驗證[14]。
2.3模擬退火算法
　模擬退火算法（SA）依據(jù)固體退火原理，固體在加溫時，內(nèi)部粒子運動隨溫升增強，變?yōu)闊o序狀，再進行退火，粒子運動減弱并漸趨有序，最后達到穩(wěn)定。把機器人在未知環(huán)境中的運動看作是粒子的布朗運動，可以對其隨機性的擾動應用模擬退火算法來引導機器人向勢能最小的方向運動，從而實現(xiàn)機器人在線的路徑規(guī)劃[4,15]。利用SA進行移動機器人路徑規(guī)劃的一般步驟如下：
　 (1)初始化運行參數(shù)，給定起始點、終止點及初始搜索方向；
　 (2)確定勢能函數(shù)和方向函數(shù)，對k=1，…，L（迭代次數(shù)）做第(3)至(6)步；
　 (3)產(chǎn)生新解；
    (4)建立局部尋優(yōu)評估函數(shù)，計算增量；
　 (5)若增量小于零則接受新解作為新的當前解，否則根據(jù)Metropolis以概率e-ΔE/(kT)接受新解作為新的當前解；
　 (6)輸出最優(yōu)解。
    模擬退火算法與初始值無關，具有描述簡單、使用靈活、魯棒性強等優(yōu)點，當退火速度慢時執(zhí)行時間長、收斂速度慢，得到的解性能比較好，當退火速度快時可能得不到最優(yōu)解。對于模擬退火算法的改進可以從采用并行搜索結(jié)構(gòu)、改進對溫度的控制方式、設計合適的評估函數(shù)等方面進行。王仲民等在用模擬退火算法對移動機器人進行路徑規(guī)劃時減少了路徑搜索過程中所出現(xiàn)冗余路徑點的數(shù)量，重新生成路徑，生成后的路徑減少了迂回，有效提高了算法的收斂速度[16]。
2.4蟻群算法
    蟻群算法是由Dorigo M在1991年提出的,主要應用于旅行商問題（TSP）、調(diào)度問題（JSP）、車輛路線問題（GCP）[17]，近年來一些學者例如Liu G利用蟻群算法進行機器人路徑規(guī)劃的研究[18],利用蟻群算法進行移動機器人路徑規(guī)劃的一般步驟如下：
　 (1)建立環(huán)境模型；
　 (2)建立巢穴鄰近區(qū)和食物氣味區(qū)；
　 (3)在鄰近區(qū)放足夠多的螞蟻；
　 (4)每只螞蟻方向函數(shù)選擇行走柵格；
　 (5)若產(chǎn)生無效路徑則刪除，否則直到螞蟻到達食物終點；
　 (6)調(diào)整有效路徑并保存最優(yōu)路徑；
    (7)更改有效路徑的信息。
    重復(3)~(7)直到達到某個迭代次數(shù)，結(jié)束整個算法[4]。
    蟻群算法由于采用啟發(fā)式搜索，容易陷入早熟，而很難發(fā)現(xiàn)其他更優(yōu)路徑，可以結(jié)合啟發(fā)式搜索和隨機搜索的方法進行改進。例如楊志曉等提出了一種改進的蟻群算法，該算法在對機器人進行路徑規(guī)劃時引入了優(yōu)先級和起始目標導引函數(shù)，采用狀態(tài)轉(zhuǎn)移概率和優(yōu)先級的組合優(yōu)化方法來平衡各路徑的信息量，算法在初始階段的搜索范圍大，有效避免了早熟現(xiàn)象，算法在后期根據(jù)起始目標導引函數(shù)來尋求最優(yōu)路徑[19]。
3 混合路徑規(guī)劃方法
    混合路徑規(guī)劃方法是結(jié)合一種或兩種算法的優(yōu)點，相互之間取長補短，以提高規(guī)劃效率。鄭秀敏等在2007年提出了一種柵格法-模擬退火法，即用柵格法表示環(huán)境信息，利用模擬退火算法進行局部路徑規(guī)劃，使路徑跳出局部極小值，到達目標位置[20]。
    黃席樾等在對移動機器人進行靜態(tài)路徑規(guī)劃時提出了一種基于神經(jīng)網(wǎng)絡模型的遺傳算法和模擬退火算法相結(jié)合的方法，對環(huán)境采用神經(jīng)網(wǎng)絡模型表示，利用中間路徑點不在障礙物內(nèi)的約束條件建立與神經(jīng)網(wǎng)絡的輸出關系，編碼時把無碰撞作為約束條件，把最短路徑作為適應度函數(shù)選擇的條件，仿真結(jié)果表明,該方法在路徑規(guī)劃時收斂性好,有效地提高了路徑規(guī)劃的質(zhì)量[21]。杜宗宗等在移動機器人的路徑規(guī)劃中運用模擬退火算法對遺傳算法進行優(yōu)化，并將避開障礙物的初始種群生成方法和基于啟發(fā)式知識的遺傳算子的設計方法應用其中，避免了遺傳算法收斂較慢、局部尋優(yōu)能力差、易陷入局部極值點等缺點，使得遺傳算法和模擬退火算法在路徑規(guī)劃中達到優(yōu)勢互補的目的；仿真結(jié)果表明，在種群規(guī)模較大且進化代數(shù)充足的情況下，該算法的成功率更高、平均代價值更小、路徑長度更短[22]。
    續(xù)欣瑩等提出了一種基于人工免疫勢場法的移動機器人路徑規(guī)劃算法，該算法在生成初始路徑群后將路徑長度作為適應度函數(shù)，通過免疫操作進行路徑優(yōu)勝劣汰的選擇，有效防止了“早熟收斂”現(xiàn)象的產(chǎn)生，仿真結(jié)果表明了該算法的有效性[23]。
    國海濤等提出了一種結(jié)合螞蟻算法與遺傳算法的機器人路徑規(guī)劃方法，先用柵格法對機器人的運動空間建模，然后用螞蟻算法進行全局搜索，搜索出一條導航路徑，再對該路徑上的點用遺傳算法進行調(diào)節(jié)，最后得到近似最優(yōu)路徑，仿真結(jié)果表明該方法能使機器人快速規(guī)劃出路徑，具有操作簡單、不會陷入局部最優(yōu)等優(yōu)點[24]。肖本賢等提出了一種在復雜環(huán)境中機器人路徑規(guī)劃的新方法，該方法為了縮小最優(yōu)解的范圍采用隨機搜索和重點搜索相結(jié)合的搜索方式，同時采用最大-最小螞蟻系統(tǒng)MMAS算法[25,26]的思想動態(tài)調(diào)整路徑上的信息激素，縮短了搜索時間，大大減小了陷入局部解的概率[27]。
4 展望
    (1)對環(huán)境的感知技術。機器人必須通過傳感器感知環(huán)境的信息，處理器通過處理這些傳感器信息后，進一步?jīng)Q策機器人的具體行為。如何正確地感知環(huán)境信息，關鍵在傳感器，只有先進的傳感器才能有效地采集環(huán)境信息，從而提高機器人動作的準確性。目前超聲波、激光雷達、視覺等傳感器在移動機器人中得到了實際應用，但是這些傳感器都有一定的局限性，例如超聲波傳感器的檢測范圍取決于其使用的波長和頻率，視覺傳感器所獲得圖像的清晰和細膩程度取決于分辨率，分辨率越高圖像越清晰，但所需的存儲空間就越大，圖像分析和處理速度就越慢。所以對移動機器人的環(huán)境感知技術將是未來移動機器人研究的一個突出方面。
    (2)多傳感器信息融合技術。多傳感器信息融合的目的是提高系統(tǒng)的可靠性和魯棒性，在移動機器人路徑規(guī)劃中，傳感器起了很重要的作用，多傳感器所獲得的信息具有冗余性、互補性、協(xié)同性，可對現(xiàn)場環(huán)境進行快速并行分析，有利于機器人快速找到有效路徑。但是多傳感器信息融合技術還存在很多難題，例如如何減小信息融合的錯誤率、如何提高信息融合的實時性、如何建立有效的信息融合質(zhì)量評價機制等。
    (3)群體機器人的路徑規(guī)劃技術。群體機器人在協(xié)作工作時都希望能找到一條無碰撞、最快到達目標的路徑，群體機器人路徑規(guī)劃既要考慮避障又要考慮機器人之間的相互協(xié)作，在路徑規(guī)劃上難度將增加，另外當目標點移動時還要考慮目標的位置信息和速度信息，整個路徑規(guī)劃將更加復雜，這方面研究是今后研究的重點。
    目前，對移動機器人的路徑規(guī)劃研究提出了很多方法，但尚未形成統(tǒng)一和完善的體系，還有許多關鍵問題例如機器人運動環(huán)境建模、機器人導航控制器的學習和優(yōu)化、實時故障診斷、實時運動規(guī)劃與控制等技術問題亟待解決和完善。
參考文獻
[1] 李磊，葉濤，譚民,等.移動機器人技術研究現(xiàn)狀與未來[J].機器人，2002，24（5）：475-480.
[2] 邰宜斌，席裕庚.一種機器人路徑規(guī)劃的新方法[J].上海交通大學學報，1996，30（4）：94-100.
[3] 呂太之，趙春霞.基于改進概率柵格分解的路徑規(guī)劃[J].計算機工程，2007，33（21）：160-165.
[4] 蔡自興，賀漢根，陳虹.未知環(huán)境中移動機器人導航控制理論與方法[M].北京：科學出版社，2009.
[5] 王力虎，張海洪.室內(nèi)清掃機器人區(qū)域充滿拓撲算法[J].機械工程師，2005(1)：17-19.
[6] 種琤，陳陽舟,崔平遠，等.基于掃描法在線構(gòu)造拓撲圖的路經(jīng)規(guī)劃算法[J].計算機仿真，2006，23(4)：147-150.
[7] 靖民，梁迎春．機械優(yōu)化設計[M]． 北京：機械工業(yè)出版社，2007：145-150．
[8] 柳在鑫， 王進戈,王強，等．利用漸開線的足球機器人射門算法研究[J].西安交通大學學報，2009，43(1)：95-98．
[9] KHATIB. Real-time obstacle for manipulators and mobile robot[J]. The International Journal of Robotic Research, 1986,5(1):90-98.
[10] 劉義，張宇.基于改進人工勢場法的移動機器人局部路徑規(guī)劃的研究[J].現(xiàn)代機械，2006（6）：48-49.
[11] 張建英，趙志萍，劉暾.基于人工勢場法的機器人路徑規(guī)劃(J).哈爾濱工業(yè)大學學報，2006，38(8)：1306-1309.
[12] 王洲，張毅，楊銳敏，等.基于遺傳算法的移動機器人路徑規(guī)劃[J].微計算機信息，2008，24(26)：187-189.
[13] 王新杰, 武秋俊.基于改進遺傳算法的移動機器人路徑規(guī)劃[J].煤礦機械，2008，29(4)：28-30.
[14] 盧瑾，柳東勇.基于雙重遺傳算法機制的路徑規(guī)劃[J].系統(tǒng)仿真學報，2008，20(8)：2048-2051.
[15] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by Simulated Annealing[J].Science, 1983,220(4598):671-680.
[16] 王仲民，岳宏,劉繼巖.基于改進模擬退火算法的移動機器人路徑規(guī)劃[J].計算機工程與應用，2005，41(19)：59-60,82.
[17] DORIGO M, BONABEAU E. Ant algorithms and stigmergy [J].Future Generation Computer Systems, 2000(16):851-871.
[18] LIU G. The ant algorithm for solving robot path planning problem[C].Third International Conf.on Information Technology any Applications, 2005(ICITA2005),2005,2(4-7):25-27.
[19] 楊志曉,郭勝國.基于改進蟻群算法的機器人路徑規(guī)劃算法[J].微計算機信息，2008，24(20)：252-253.
[20] 鄭秀敏，顧大鵬，劉相術.基于柵格法-模擬退火法的機器人路徑規(guī)劃[J].機器人技術，2007，23（2）：247-248.
[21] 黃席樾,蔣卓強.基于遺傳模擬退火算法的靜態(tài)路徑規(guī)劃研究[J].重慶工學院學報(自然科學版)，2007，21(6)：53-57.
[22] 杜宗宗，劉國棟.基于遺傳模擬退火算法的移動機器人路徑規(guī)劃[J].計算機仿真，2009，26(12)：118-121.
[23] 續(xù)欣瑩,謝裙，謝克明.基于人工免疫勢場法的移動機器人路徑規(guī)劃[J].北京工業(yè)大學學報，2008，34(10)：1116-1119.
[24] 國海濤, 朱慶保，司應濤.一種螞蟻遺傳融合的機器人路徑規(guī)劃新算法[J].小型微型計算機系統(tǒng)，2008，29(10)：1838-1840.
[25] DORIGO M, GAMBARDELLA L M, MIDDENORF,et al.Guest editorial:special section on ant colony optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(4):317-319.
[26] STUTZLE T, HOOS H. MAX-MIN ant system[J]. Future  Generation Computer Systems,2000,16(9):889-914.
[27] 肖本賢,劉剛,余雷.基于MMAS的機器人路徑規(guī)劃[J].合肥工業(yè)大學學報,2008,31(1):63-67.