皇甫淑云 唐守鋒 童紫原

摘要：自主移動機器人路徑規(guī)劃問題是智能控制和機器人學(xué)研究的核心內(nèi)容之一。系統(tǒng)分析了當前移動機器人路徑規(guī)劃方法的主要研究成果。對移動機器人路徑規(guī)劃模型進行描述，介紹了人工勢場法等傳統(tǒng)方法，闡述遺傳算法等智能算法，討論了算法融合問題，對移動機器人路徑規(guī)劃的發(fā)展趨勢進行了展望。

關(guān)鍵詞：路徑規(guī)劃；傳統(tǒng)規(guī)劃；智能規(guī)劃；算法融合；移動機器人

DOIDOI：10.11907/rjdk.181628

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2018）010-0001-05

英文摘要Abstract：The path planning problem of autonomous mobile robots is one of the core contents of intelligent control and robotics research， and it is a global research hotspot in recent years. This paper systematically summarizes the main research results of the current mobile robot path planning methods， which are mainly divided into two categories： traditional methods and intelligent methods. Firstly， the path planning model of mobile robot is described. Secondly， the traditional methods such as the artificial potential field method are introduced. The intelligent algorithms such as genetic algorithms are summarized， and the fusion of the algorithms is also discussed. Finally， the development trend of path planning for mobile robots is predicted.

英文關(guān)鍵詞Key Words：path planning；traditional planning；intelligent planning；deep integration；mobile robot

0 引言

機器人技術(shù)是現(xiàn)代科學(xué)理論與實踐綜合交叉的成果。20世紀60年代末，斯坦福研究院（SRI）研制了自主移動機器人，路徑規(guī)劃方法是其關(guān)鍵核心技術(shù)[1]。移動機器人路徑規(guī)劃技術(shù)，就是機器人在遵循一些優(yōu)化指標（比如時間最短、路程最優(yōu)和能耗最低等）前提下，在運行環(huán)境中規(guī)劃出從起始點到目標點不發(fā)生碰撞的最優(yōu)路徑[2]。

移動機器人路徑規(guī)劃實質(zhì)上是滿足一定約束條件的優(yōu)化問題，其算法設(shè)計過程具有復(fù)雜性、隨機性、多目標性和多約束性等特點[3]。根據(jù)路徑規(guī)劃環(huán)境是否隨時間變化，將移動機器人的路徑規(guī)劃分為動態(tài)規(guī)劃和靜態(tài)規(guī)劃[4]。根據(jù)機器人路徑規(guī)劃的目標范圍，又可分為全局路徑規(guī)劃和局部路徑規(guī)劃。本文在移動機器人路徑規(guī)劃模型基礎(chǔ)上，將路徑規(guī)劃方法分為傳統(tǒng)方法和智能方法，闡述各種方法的優(yōu)缺點，討論算法的深度融合問題，并對移動機器人路徑規(guī)劃發(fā)展趨勢進行展望。

1 移動機器人路徑規(guī)劃模型

在移動機器人的二維或三維工作空間中，解決路徑規(guī)劃問題必須定義物體（包括障礙物和機器人）的幾何模型[5]。路徑規(guī)劃問題最初研究的是二維空間（如地面機器人），根據(jù)能量守恒原理，利用二維空間的輻射熱傳導(dǎo)方程建模進行路徑規(guī)劃問題的求解[6]。

2.1.4 可視圖法

可視圖法（Visibility Graph ，VG）由Nilsson[11]于1968年提出，常用于多邊形障礙物的工作環(huán)境。首先，將環(huán)境中多邊形或不規(guī)則障礙物分解為多個矩形，機器人視為一個質(zhì)點（忽略機器人大小和外形），然后將機器人起點和矩形組成的障礙物各頂點以及目標位置點用線段連接，連接的線段不能穿過矩形障礙物，最后得到所有的遍歷路徑，如圖4所示。

利用可視圖法構(gòu)建環(huán)境地圖簡單方便，能夠搜索到最短路徑，適合障礙物較少且不發(fā)生改變的環(huán)境。當障礙物位置和個數(shù)發(fā)生變化時，就需要重新構(gòu)建環(huán)境地圖，且計算量隨著障礙物個數(shù)的增加而變大。針對以上不足，學(xué)者提出了Voronoi圖法[12]和切線圖法[13]。

2.2 智能路徑規(guī)劃方法

近年來，路徑規(guī)劃問題在求解過程中變得復(fù)雜化，具有較強的隨機性，仿生智能算法應(yīng)運而生并取得了長足發(fā)展。

2.2.1 基于遺傳算法的機器人路徑規(guī)劃

遺傳算法（Genetic Algorithm ，GA）是模擬自然界生物進化提出的一種智能算法[14]。算法核心思想是模擬生物在自然環(huán)境中不斷進化時，個體之間遺傳、雜交、變異和自然選擇等現(xiàn)象。遺傳算法求解路徑規(guī)劃是將路段描述成一系列中途點，并將其轉(zhuǎn)換為二進制串。首先將路徑群體初始化，其次進行遺傳操作（如選擇、交叉、復(fù)制、變異），最后經(jīng)過若干代進化后停止進化，根據(jù)規(guī)劃要求完成解空間搜索，輸出當前最優(yōu)個體[15]，見圖5。

遺傳算法具有全局搜索能力強、魯棒性好和操作簡單等優(yōu)點，但當算法編碼較長時，會導(dǎo)致收斂速度慢、計算量大，故不適合求解復(fù)雜的路徑規(guī)劃問題。

2.2.2 基于人工神經(jīng)網(wǎng)絡(luò)算法的機器人路徑規(guī)劃

人工神經(jīng)網(wǎng)絡(luò)算法（Artificial Neural Network，ANN）在20世紀40年代后期出現(xiàn) [16]。如圖6所示，人工神經(jīng)網(wǎng)絡(luò)是一種非線性網(wǎng)絡(luò)系統(tǒng)，模擬大腦中相互連接的神經(jīng)元網(wǎng)絡(luò)，具備并行性和分布式特點。該方法不僅用于路徑規(guī)劃，還應(yīng)用于環(huán)境建模、傳感器信息交互融合、機器人系統(tǒng)控制等領(lǐng)域[17]。

人工神經(jīng)網(wǎng)絡(luò)算法采取分布式計算，擁有較強的實時性和學(xué)習性。求解路徑規(guī)劃問題時，計算量少且收斂速度快，容易實現(xiàn)。但由于算法初期反饋信息不足，需要經(jīng)過一段時間的權(quán)重調(diào)整才能得到理想的優(yōu)化結(jié)果。

2.2.3 基于模糊邏輯法的機器人路徑規(guī)劃

模糊邏輯法（Fuzzy Logic， FL）采用反射機制模擬駕駛員的駕駛經(jīng)驗，利用不同類型的傳感器感知障礙物和機器人狀態(tài)，通過模糊規(guī)則控制機器人尋徑速度和轉(zhuǎn)向角度，從而實現(xiàn)局部路徑規(guī)劃。H Chang等[18]建立一個模糊推理模型解決機器人路徑規(guī)劃問題，具體步驟如圖7所示。

利用模糊邏輯法進行機器人路徑規(guī)劃，可在動態(tài)環(huán)境中迅速規(guī)劃出有效路徑，即對環(huán)境有較強的適應(yīng)性。但隨著障礙物增多，該方法計算量也會增大，搜索效率變低。

2.3 算法融合與分析

如何將算法深度融合以提高避障效率，取得尋徑的最佳效果，是當前移動機器人路徑規(guī)劃問題的重點。

2.3.1 傳統(tǒng)方法結(jié)合

傳統(tǒng)的柵格地圖法、人工勢場法、可視圖法和拓撲圖法等不適用于所有情況下的路徑規(guī)劃問題，每種算法都有局限性。根據(jù)傳統(tǒng)方法特點，一些學(xué)者相繼提出改進或派生算法，證明了在某些特定條件下算法的實用性，有效提高了路徑規(guī)劃效率。針對傳統(tǒng)人工勢場法局部極值問題和目標不可達問題，歐陽鑫玉等[19]先在斥力勢場函數(shù)中增加最小安全距離，建立改進人工勢場模型，然后采用柵格法對改進的人工勢場法作輔助決策，使機器人盡快脫離局部極小值并成功到達目標點。

2.3.2 智能有效方法結(jié)合

隨著三維空間對移動機器人的需求增加，傳統(tǒng)方法的實時性降低，計算量加大，一系列智能有效規(guī)劃算法被提出。例如，關(guān)于遺傳算法與蟻群算法的路徑規(guī)劃問題，單獨使用的情況較少，一般利用進化計算進行優(yōu)化處理，再與其它算法結(jié)合完成路徑規(guī)劃任務(wù)。潘昕等[20]針對三維空間中水下潛航器（AUV）的全局路徑規(guī)劃存在時間較長、搜索效率低等問題，提出了一種基于遺傳螞蟻混合算法。王輝等[21]針對智能停車庫自動導(dǎo)引運輸車（AGV）存取路徑規(guī)劃問題，提出了一種基于粒子群遺傳算法的自適應(yīng)混合算法，具有較好的收斂性和較強的全局搜索能力。

2.3.3 傳統(tǒng)方法與智能方法結(jié)合

人工智能系統(tǒng)的日益成熟推動了傳統(tǒng)方法與智能方法的結(jié)合，如柵格法與遺傳算法、粒子群算法等的融合，人工勢場法與蟻群算法、遺傳算法以及ANN等的融合。盧路秋[22]提出了基于多階模糊系統(tǒng)人工勢場路徑規(guī)劃方法，設(shè)計了沖突消解策略，減少了路徑規(guī)劃時間和長度。劉亮[23]提出了勢場蟻群路徑規(guī)劃算法，初期引入勢力場啟發(fā)信息影響系數(shù)，降低蟻群搜索的隨機性，增強勢力場函數(shù)的引導(dǎo)作用，后期則相反。該方法避免了早熟現(xiàn)象，搜索時間短，精度較高。姜英杰等[24]利用柵格遺傳算法對變電站巡檢機器人進行全局路徑規(guī)劃。周文明等[25]針對移動機器人局部路徑規(guī)劃問題，改進勢力場函數(shù)，引入神經(jīng)網(wǎng)絡(luò)模糊系統(tǒng)，使系統(tǒng)速度加快、魯棒性好。 3 算法對比與分析

目前在移動機器人路徑規(guī)劃領(lǐng)域，傳統(tǒng)方法由于簡單實用仍是首選，但傳統(tǒng)方法在路徑優(yōu)化及路徑搜索方面尚待完善，比如基于采樣的改進算法[26]（RRT*）。不同于其它傳統(tǒng)方法，人工勢場法在實時動態(tài)環(huán)境中易于實現(xiàn)，且規(guī)劃效果良好，但容易出現(xiàn)目標不可達和局部極值問題。

人工智能技術(shù)應(yīng)用于路徑規(guī)劃，克服了傳統(tǒng)方法的不足。基于生物智能的路徑規(guī)劃方法不需建立復(fù)雜的環(huán)境模型，收斂穩(wěn)定且為隨機搜索，大大提高了尋優(yōu)效率，比如遺傳算法、蟻群算法和粒子群算法等自然啟發(fā)法能用于復(fù)雜環(huán)境下的路徑規(guī)劃問題，但自然啟發(fā)法計算代價高、耗時長。神經(jīng)網(wǎng)絡(luò)法是另一種智能算法，它模擬生物的神經(jīng)結(jié)構(gòu)處理信息，具有信息分布式存儲和并行處理特點，但實時性一般。因此，為了取得最佳路徑規(guī)劃效果，以上方法通常相互結(jié)合，如傳統(tǒng)算法、智能算法和混合算法等。移動機器人路徑規(guī)劃方法性能比較如表1所示。

4 移動機器人路徑規(guī)劃發(fā)展趨勢

移動機器人路徑規(guī)劃研究已取得顯著進展，但在某些領(lǐng)域仍具有一定的局限性，一些核心技術(shù)如工作環(huán)境建模、導(dǎo)航定位和故障檢測等亟需開發(fā)。根據(jù)過去的研究情況和發(fā)展趨勢，筆者認為未來自主移動機器人路徑規(guī)劃技術(shù)發(fā)展方向有以下幾個方面：

（1）多機器人協(xié)調(diào)作業(yè)。對于復(fù)雜的環(huán)境，單個機器人路徑規(guī)劃技術(shù)已不能滿足任務(wù)需求，使用多機器人移動具有良好的安全性、可靠性和協(xié)調(diào)性。

（2）硬件系統(tǒng)更新?lián)Q代。隨著科技的發(fā)展，使用高速度處理芯片（如ARM、DSP和FPGA等）將提高規(guī)劃效率，大大節(jié)省路徑規(guī)劃計算和檢測時間。

（3）多傳感器信息融合技術(shù)。通過合理利用多個傳感器采集、處理信息，提高機器人路徑規(guī)劃的魯棒性和精準性。如空中無人機編隊飛行、足球機器人比賽和水下機器人的合作搜救與觀察等[27]。

（4）新的智能算法或混合算法。路徑規(guī)劃方法應(yīng)擁有良好的實時性和響應(yīng)速度，能夠適合各種復(fù)雜場景。目前智能算法優(yōu)于傳統(tǒng)算法，具有自組織、自學(xué)習等優(yōu)點，但單一的智能算法會有全局搜索能力不強、容易陷入局部最優(yōu)解等不足。將多種智能算法有效結(jié)合可以取長補短，改善優(yōu)化效果。探索新的智能算法是路徑規(guī)劃技術(shù)發(fā)展的方向之一。

（5）高維環(huán)境和復(fù)雜環(huán)境下的路徑規(guī)劃技術(shù)。將二維空間的大量路徑規(guī)劃方法推廣到三維空間，但機器人在三維空間中的運動學(xué)和動力學(xué)約束及環(huán)境建模問題很復(fù)雜，部分算法難以擴展。

（6）不斷提高衡量路徑規(guī)劃優(yōu)劣的相關(guān)性能指標。這些性能指標由算法的實時性、準確性和可達性組成。移動機器人所處的環(huán)境是不斷變化的，如果算法沒有良好的實時性能，在遇到突然出現(xiàn)的障礙物時就會反應(yīng)遲緩，無法完成避障。高效及準確性可使機器人快速準確到達目標點，減少搜索時間，提高路徑規(guī)劃算法效率?？蛇_性是路徑規(guī)劃最基本的要求，如果通過算法搜索出的路徑不具備可達性，則該路徑毫無意義。

5 結(jié)語

路徑規(guī)劃技術(shù)是國內(nèi)外學(xué)者的研究熱點。本文在移動機器人路徑規(guī)劃模型基礎(chǔ)上，將路徑規(guī)劃方法分為傳統(tǒng)方法和智能方法，闡述了各種方法的優(yōu)缺點，并討論了算法的深度融合問題，比較了幾種典型方法性能，最后展望了移動機器人路徑規(guī)劃發(fā)展趨勢，以期為當前智能移動機器人路徑規(guī)劃技術(shù)的發(fā)展與研究提供參考。

參考文獻：

[1] 鮑慶勇，李舜酩，沈峘，等.自主移動機器人局部路徑規(guī)劃綜述[J].傳感器與微系統(tǒng)，2009，28（9）：1-4.

[2] FRAZZOLI E， DAHLEH M A， FERON E. Real-time motion planning for agile autonomous vehicles[J]. American Control Conference，2001. Proceedings of the IEEE，2001，25（1）：43-49.

[3] SU W， MENG R， YU C. A study on soccer robot path planning with fuzzy artificial potential Field[J].International Conference on Computing， Control and Industrial Engineering. IEEE Computer Society， 2010，1（7）：386-390.

[4] 戴博，肖曉明，蔡自興.移動機器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望[J]. 控制工程，2005，12（3）：198-202.

[5] 成偉明，唐振民，趙春霞，等. 移動機器人路徑規(guī)劃中的圖方法應(yīng)用綜述[J]. 工程圖學(xué)學(xué)報，2008（4）：6-14.

[6] 康亮. 自主移動機器人運動規(guī)劃的若干算法研究[D]. 南京：南京理工大學(xué)，2009.

[7] HE X， CHEN L. Path planning based on grid-potential fields[J]. International Conference on Computer Science and Software Engineering. IEEE，2008（2）：1114-1116.

[8] 趙曉東，鮑方. 清潔機器人路徑規(guī)劃算法研究綜述[J]. 機電工程，2013，30（11）：1440-1444.

[9] SARIFF N， BUNIYAMIN N. An overview of autonomous mobile robot path planning algorithm[C].4th Student Conference on Research and Development， 2006：183-188.

[10] 徐曉東. 移動機器人幾何—拓撲混合地圖構(gòu)建及定位研究[D]. 大連：大連理工大學(xué)，2005.

[11] 馬麗莎. 基于數(shù)字高程模型柵格地圖的移動機器人路徑規(guī)劃研究[D].杭州：浙江大學(xué)，2012.

[12] TAKAHASHI O， SCHILING R J. Motion planning in a plane using generalized Voronoi diagrams[J]. IEEE Transactions on Robotics & Automation，1989，5（2）：143-150.

[13] 吳天明.移動機器人導(dǎo)航技術(shù)現(xiàn)狀與展望[J]. 河南科技，2014 （17）：132-133.

[14] 鞏敦衛(wèi)，朱美強，郭西進.一種新的基于混沌變異解決早熟收斂的遺傳算法[J]. 控制與決策，2003，18（6）：686-689.

[15] 蔡漫漫.自主式移動機器人路徑規(guī)劃算法研究[D].青島：青島科技大學(xué)，2017.

[16] YE J. Tracking control of a nonholonomic mobile robot using compound cosine function neural networks[J]. Intelligent Service Robotics，2013，6（4）：191-198.

[17] 劉曉磊，蔣林，金祖飛，等.非結(jié)構(gòu)化環(huán)境中基于柵格法環(huán)境建模的移動機器人路徑規(guī)劃[J].機床與液壓，2016，44（17）：1-7.

[18] CHANG H， JIN T. Command fusion based fuzzy controller design for moving obstacle avoidance of mobile robot[M].Future Information Communication Technology and Application. Springer Netherlands，2013：905-913.

[19] 歐陽鑫玉，楊曙光.基于勢場柵格法的移動機器人避障路徑規(guī)劃[J].控制工程，2014，21（1）：134-137.

[20] 潘昕，吳旭升，侯新國，等.基于遺傳螞蟻混合算法的AUV全局路徑規(guī)劃[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2017，45（5）：45-49.

[21] 王輝，朱龍彪，朱天成，等.基于粒子群遺傳算法的泊車系統(tǒng)路徑規(guī)劃研究[J].工程設(shè)計學(xué)報，2016，23（2）：195-200.

[22] 盧路秋.基于模糊人工勢場法的多移動機器人路徑規(guī)劃研究[D].天津：天津工業(yè)大學(xué)，2015.

[23] 劉亮.基于勢場蟻群算法的移動機器人路徑規(guī)劃研究[D].南昌：南昌大學(xué)，2013.

[24] 姜英杰，呂學(xué)勤，段利偉.柵格遺傳算法的變電站巡檢機器人路徑規(guī)劃[J].科技與創(chuàng)新，2015（6）：12-14.

[25] 周文明，張崇巍.基于模糊神經(jīng)網(wǎng)絡(luò)勢場法的機器人動態(tài)路徑規(guī)劃[J].微型機與應(yīng)用，2011，30（11）：89-91.

[26] ELBANELBANHAWI M，SIMIC M. Sampling-based robot motion planning：a review[J]. IEEE Access，2014，2（1）：56-77.

[27] 朱大奇.移動機器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（7）：961-967.

（責任編輯：杜能鋼）