皇甫淑云 唐守鋒 童紫原

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

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

DOIDOI：10.11907/rjdk.181628

中圖分類(lèi)號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

2.1.4 可視圖法

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法融合與分析

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

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

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

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

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

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

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

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

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

4 移動(dòng)機(jī)器人路徑規(guī)劃發(fā)展趨勢(shì)

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 鮑慶勇，李舜酩，沈峘，等.自主移動(dòng)機(jī)器人局部路徑規(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] 戴博，肖曉明，蔡自興.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望[J]. 控制工程，2005，12（3）：198-202.

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

[6] 康亮. 自主移動(dòng)機(jī)器人運(yùn)動(dòng)規(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] 趙曉東，鮑方. 清潔機(jī)器人路徑規(guī)劃算法研究綜述[J]. 機(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] 徐曉東. 移動(dòng)機(jī)器人幾何—拓?fù)浠旌系貓D構(gòu)建及定位研究[D]. 大連：大連理工大學(xué)，2005.

[11] 馬麗莎. 基于數(shù)字高程模型柵格地圖的移動(dòng)機(jī)器人路徑規(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òng)機(jī)器人導(dǎo)航技術(shù)現(xiàn)狀與展望[J]. 河南科技，2014 （17）：132-133.

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

[15] 蔡漫漫.自主式移動(dòng)機(jī)器人路徑規(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)境建模的移動(dòng)機(jī)器人路徑規(guī)劃[J].機(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] 歐陽(yáng)鑫玉，楊曙光.基于勢(shì)場(chǎng)柵格法的移動(dòng)機(jī)器人避障路徑規(guī)劃[J].控制工程，2014，21（1）：134-137.

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

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

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

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

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

[25] 周文明，張崇巍.基于模糊神經(jīng)網(wǎng)絡(luò)勢(shì)場(chǎng)法的機(jī)器人動(dòng)態(tài)路徑規(guī)劃[J].微型機(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] 朱大奇.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（7）：961-967.

（責(zé)任編輯：杜能鋼）