顧冬雷 李曉格 王碩

（1 南京模擬技術(shù)研究所，南京，210016; 2中國科學(xué)院自動(dòng)化研究所，北京，100190）

0 引言

近年來，勘察、目標(biāo)獲取、搜索與援救、監(jiān)督、環(huán)境監(jiān)測等方面廣泛的應(yīng)用需求使移動(dòng)機(jī)器人技術(shù)得到快速發(fā)展。其中，導(dǎo)航技術(shù)是移動(dòng)機(jī)器人研究的核心技術(shù)之一，而路徑規(guī)劃是導(dǎo)航的基本環(huán)節(jié)。

機(jī)器人路徑規(guī)劃的基本思想是依據(jù)某種性能指標(biāo)（如時(shí)間最短、能量最少、路徑最短等），尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞最優(yōu)或近似最優(yōu)的路徑[1]。本文從全局規(guī)劃和局部規(guī)劃兩個(gè)方面對一些路徑規(guī)劃常用算法進(jìn)行介紹。

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

全局路徑規(guī)劃是在作業(yè)環(huán)境中，基于先驗(yàn)?zāi)Ｐ鸵?guī)劃從起始點(diǎn)到目標(biāo)點(diǎn)的路徑，也稱為靜態(tài)路徑規(guī)劃，主要包括可視圖法、柵格解耦法、概率路徑圖法、拓?fù)浞?、神?jīng)網(wǎng)絡(luò)法等。

1.1 可視圖法

可視圖法利用機(jī)器人的最短路徑是擦著多邊形障礙物的頂點(diǎn)的思想，將機(jī)器人看成一個(gè)點(diǎn)，把起始點(diǎn)、目標(biāo)點(diǎn)和多邊形障礙物的所有頂點(diǎn)用線段連接起來，同時(shí)刪除穿過障礙物的線組成可視圖，再搜索最短路徑[2]。該方法應(yīng)用于二維路徑規(guī)劃問題中，則是能在O(N2)的時(shí)間內(nèi)完成最短路徑搜索，其中N為障礙物的數(shù)量（下同）。

可視圖法沒有考慮到機(jī)器人本身的形狀、大小，易造成與障礙物的碰撞，同時(shí)隨著障礙物的增多，或障礙物的不規(guī)則性而導(dǎo)致圖中的頂點(diǎn)集過大，計(jì)算復(fù)雜性增加，搜索時(shí)間長?？梢晥D法最初由斯坦福大學(xué)的Nilsson提出，Kuwata和How[3]將該方法推廣到三維情形，障礙物用多面體表示，得到的路徑不一定是最優(yōu)的。

1.2 Voronoi圖法

Voronoi圖法的基本思想是首先產(chǎn)生與障礙物多邊形所有的邊等距離的Voronoi邊，并將所有Voronoi邊的交點(diǎn)組成頂點(diǎn)集；再通過與可視圖類似的搜索最短路徑邊的方法來規(guī)劃路徑。

Voronoi圖法的時(shí)間復(fù)雜度為O(NlogN)，能夠保證機(jī)器人以最大的安全度到達(dá)目標(biāo)，但卻導(dǎo)致機(jī)器人到目標(biāo)位置的路徑增長，從而不是最優(yōu)的路徑。這是一個(gè)二維算法，肖秦琨等研究了三維空間Voronoi圖法[4]，Choset 和Burdick將其推廣到多維空間并進(jìn)行了改進(jìn)[5]。

1.3 柵格解耦法

柵格解耦法是目前應(yīng)用最廣泛的路徑規(guī)劃方法。該方法將環(huán)境空間解耦成一系列相互連接但不重疊的網(wǎng)格單元，從而得到一個(gè)連通圖，每個(gè)柵格都被賦予一個(gè)累積值，用來描述該柵格中存在障礙物的可信度，累積值越高則存在障礙物的可能性越大，最后通過優(yōu)化算法來搜索柵格中的最短連通路徑。

柵格劃分的方法可以分為精確柵格解耦法和近似柵格解耦法[6]。精確柵格解耦法將自由空間劃分成小的凸多邊形或凸多面體，得到的環(huán)境空間與原環(huán)境空間精確相等。常見的精確柵格解耦法有梯形柵格解耦法，時(shí)間復(fù)雜性為O(NlogN)，不是最優(yōu)解；臨界曲線柵格解耦法，時(shí)間復(fù)雜度為O(N2logN)，得到的也不是最優(yōu)解。近似柵格解耦法有矩形柵格解耦法和2m叉樹柵格解耦法 （四叉樹、八叉樹[7]）等。柵格法在三維路徑規(guī)劃中也有應(yīng)用[8-9]，小波變換法、多分辨率方法等常用于柵格算法的改進(jìn)[10-11]。

可視圖法、Voronoi圖法和柵格解耦法都是把區(qū)域劃分成不同的網(wǎng)格空間，找到機(jī)器人可達(dá)的網(wǎng)格（節(jié)點(diǎn)）以及網(wǎng)格間聯(lián)系（邊），構(gòu)成滿足一定拓?fù)浣Y(jié)構(gòu)的圖[10]，因此，A*算法[11]、Dijkstra算法、寬度優(yōu)先、深度優(yōu)先搜索算法等常用于解決圖搜索問題，且算法的效率與存儲(chǔ)圖的數(shù)據(jù)結(jié)構(gòu)存在一定的關(guān)系。

1.4 概率路徑圖法（PRM）

概率路徑圖法最初由Kavraki等[12]提出，是一種基于采樣的規(guī)劃方法，與傳統(tǒng)方法的不同，它以某種概率來構(gòu)建圖。PRM算法概率完備并且收斂，但不是近似最優(yōu)，與空間維數(shù)和復(fù)雜度無關(guān)。Karaman和Frazzoli系統(tǒng)地分析并改善了基于采樣的PRM算法[13]。此外，Bohlin和Kavraki解決了狹長通道內(nèi)PRM算法不易收斂的問題[14]。

1.5 拓?fù)浞?/h3>

拓?fù)浞ɑ舅枷胧菍h(huán)境空間分割成若干個(gè)具有拓?fù)涮卣鞯淖涌臻g，并根據(jù)子空間的聯(lián)通性建立拓?fù)渚W(wǎng)絡(luò)。在此拓?fù)渚W(wǎng)絡(luò)上，機(jī)器人搜索到目標(biāo)位置的拓?fù)渎窂剑偻ㄟ^拓?fù)渎窂絹碛?jì)算幾何路徑，完成路徑規(guī)劃的任務(wù)。

拓?fù)浞ㄖ饕褂媒稻S法，將高維空間中的求路徑問題轉(zhuǎn)化為低維拓?fù)淇臻g的連通性判別問題。拓?fù)浞ǖ膬?yōu)勢是利用拓?fù)涮卣骺s小搜索空間，提高了搜索效率。但算法中空間劃分及拓?fù)渚W(wǎng)絡(luò)建立的復(fù)雜程度隨障礙物的數(shù)目增多而增大。對于結(jié)構(gòu)簡單的拓?fù)渚W(wǎng)絡(luò)，一般可采用寬度優(yōu)先、深度優(yōu)先算法，復(fù)雜網(wǎng)絡(luò)則多采用A*算法、S*算法等。

1.6 神經(jīng)網(wǎng)絡(luò)法

神經(jīng)網(wǎng)絡(luò)方法應(yīng)用于機(jī)器人路徑規(guī)劃中，通過定義整條路徑的總能量函數(shù)，利用網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)和模擬退火方法等產(chǎn)生移動(dòng)路徑點(diǎn)，使其朝著能量減少的方向運(yùn)動(dòng)，最終獲得總能量最小的路徑。神經(jīng)網(wǎng)絡(luò)方法比較靈活，可以解決可視圖法不能解決的圓形障礙物問題[12]。其中，生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的實(shí)時(shí)性較好，大多數(shù)的神經(jīng)網(wǎng)絡(luò)由于存在學(xué)習(xí)樣本難以獲取的問題而存在滯后性。

2 局部路徑規(guī)劃方法及其他規(guī)劃方法

局部規(guī)劃是在作業(yè)環(huán)境中，基于對周圍環(huán)境的感知進(jìn)行路徑規(guī)劃。主要算法有人工勢場法、快速擴(kuò)展隨機(jī)搜索樹法（RRT）、模糊邏輯算法等，其他規(guī)劃算法還有遺傳算法、蟻群算法、粒子群算法等。

2.1 人工勢場法

人工勢場法最初由Khatib和Mampey[15]提出，基本思想是用一個(gè)勢函數(shù)來描述機(jī)器人環(huán)境空間，機(jī)器人作為一個(gè)粒子受到勢力，目標(biāo)點(diǎn)有最低勢能對機(jī)器人產(chǎn)生吸引力，同時(shí)障礙物對機(jī)器人產(chǎn)生排斥力。

人工勢場法結(jié)構(gòu)簡單，便于底層實(shí)時(shí)控制，在實(shí)時(shí)避障和平滑的軌跡控制方面得到了廣泛應(yīng)用，其不足在于存在局部最優(yōu)解，容易產(chǎn)生死鎖現(xiàn)象，因而可能使移動(dòng)機(jī)器人在到達(dá)目標(biāo)點(diǎn)之前就停留在局部最優(yōu)點(diǎn)。

Koren和Borenstein[16]指出虛擬力場法存在局部極小陷阱區(qū)域、在相近障礙物間找不到路徑等不足。針對這些不足，出現(xiàn)了利用圖搜索辦法、調(diào)和函數(shù)及啟發(fā)函數(shù)等方法[17]。

2.2 快速擴(kuò)展隨機(jī)搜索樹法（RRT）

快速擴(kuò)展隨機(jī)搜索樹法最初由LaValle[18]提出，先對供參考用的主題框架進(jìn)行隨機(jī)搜索，再擴(kuò)展到通過隨機(jī)采樣得到的構(gòu)造空間。這是一種基于采樣的方法，利用了單查詢機(jī)制，用于當(dāng)機(jī)器人從一個(gè)環(huán)境移動(dòng)到另一個(gè)環(huán)境的情形。

RRT算法可以解決環(huán)境模型的先驗(yàn)知識(shí)未知或者建模困難問題，可用于實(shí)時(shí)在線規(guī)劃。但該方法只應(yīng)用在完整約束問題中，沒有考慮到動(dòng)力學(xué)約束問題。

2.3 遺傳算法

遺傳算法是以自然遺傳機(jī)制和自然選擇等生物進(jìn)化理論為基礎(chǔ)的一類隨機(jī)優(yōu)化搜索算法。通過模擬生物進(jìn)化過程中的選擇、交叉和變異等機(jī)制進(jìn)行搜索，可以并行執(zhí)行，適用于全局搜索。

遺傳算法由于是一種多點(diǎn)搜索算法，所以有可能搜索到全局最優(yōu)解，缺點(diǎn)是運(yùn)算速度不快，存儲(chǔ)空間和運(yùn)算時(shí)間較多。

2.4 粒子群算法

粒子群是由Kennedy[19]從鳥類捕食行為中受到啟發(fā)而提出的一種基于群體的智能隨機(jī)優(yōu)化算法。粒子群算法具有收斂速度快、參數(shù)設(shè)置簡單、算法簡單、容易編程實(shí)現(xiàn)和魯棒性強(qiáng)等特點(diǎn)，但是容易陷入局部極值點(diǎn)，而且對參數(shù)設(shè)置依賴性比較高。

2.5 模糊邏輯算法

模糊邏輯是二值邏輯的推廣，是對經(jīng)典的二值邏輯的模糊化。利用模糊邏輯進(jìn)行路徑規(guī)劃，能夠一定程度上處理局部極小問題，同時(shí)通過對環(huán)境信息的模糊化，可降低對移動(dòng)機(jī)器人定位精度的要求。

由于模糊邏輯算法依據(jù)的是經(jīng)驗(yàn)，但經(jīng)驗(yàn)不一定準(zhǔn)確，這是該方法的缺陷。此外，模糊隸屬度函數(shù)、控制規(guī)則的設(shè)計(jì)也是其中需要重點(diǎn)考慮的問題。

2.6 蟻群算法

Colorni, Dorigo等[20]提出了一種可并行計(jì)算、魯棒的模擬進(jìn)化算法——蟻群算法，該方法具有較好的最優(yōu)解發(fā)現(xiàn)能力，在路徑規(guī)劃中有一定的應(yīng)用。但是，蟻群算法用于機(jī)器人路徑規(guī)劃時(shí)，存在算法耗時(shí)、容易出現(xiàn)停滯現(xiàn)象、收斂慢等問題。

2.7 其他算法

除了上面提到的方法，還有很多其他規(guī)劃方法，如模型預(yù)測方法或滾動(dòng)優(yōu)化法（RHC）和線性規(guī)劃方法等基于數(shù)學(xué)優(yōu)化的方法、啟發(fā)式算法、基于反應(yīng)式規(guī)劃的方法、慎思規(guī)劃、全局與局部路徑規(guī)劃相結(jié)合的方法、針對不確定性動(dòng)態(tài)環(huán)境的路徑規(guī)劃方法等。

3 總結(jié)

隨著智能移動(dòng)機(jī)器人應(yīng)用的快速增長，移動(dòng)機(jī)器人導(dǎo)航技術(shù)中的路徑規(guī)劃方法也越來越多被關(guān)注，并獲得應(yīng)用。本文對機(jī)器人路徑規(guī)劃的主要方法進(jìn)行了歸納介紹。

在規(guī)劃方法的實(shí)際應(yīng)用中，全局規(guī)劃和局部規(guī)劃相結(jié)合是一個(gè)比較合理的策略。規(guī)劃方法的選取應(yīng)依據(jù)機(jī)器人的實(shí)際計(jì)算能力、實(shí)時(shí)性要求、外部環(huán)境等因素綜合考慮，以滿足實(shí)際應(yīng)用需求。

至謝

感謝國家科技支撐計(jì)劃（No.2013BAK03B00）對本項(xiàng)目的資助。

[1]Li L, Ye T, Tan M, et al. Present State and Future Development of Mobile Robot Technology Research[J]. Robot, 2002, 24(5): 475-480.

[2]Goerzen C, Kong Z, Mettler B. A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance[J]. Journal of Intelligent and Robotic Systems, 2010, 57(1-4): 65-100.

[3]Kuwata Y, How J. Three Dimensional Receding Horizon Control for UAVs[C]. AIAA Guidance, Navigation, and Control Conference and Exhibit. 2004: 2100-2113.

[4]肖秦琨, 高曉光. 基于空間改進(jìn)型 Voronoi 圖的路徑規(guī)劃研究[J]. 自然科學(xué)進(jìn)展, 2006, 16(2): 232-237.

[5]Choset H, Burdick J. Sensor-based Exploration: The Hierarchical Generalized Voronoi Graph[J]. The International Journal of Robotics Research, 2000, 19(2): 96-125.

[6]Cai C, Ferrari S. Information-driven Sensor Path Planning by Approximate Cell Decomposition[J]. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 2009, 39(3): 672-689.

[7]Cocaud C, Jnifene A, Kim B. Environment Mapping Using Hybrid Octree Knowledge for UAV Trajectory Planning[J]. Canadian Journal of Remote Sensing, 2008, 34(4): 405-417.

[8]Williams M, Jones D I. A Rapid Method for Planning Paths in Three Dimensions for a Small Aerial Robot[J]. Robotica, 2001, 19(2): 125-135.

[9]Tsenkov P, Howlett J K, Whalley M, et al. A System for 3d Autonomous Rotorcraft Navigation in Urban Environments[C]. AIAA Guidance, Navigation and Control Conference and Exhibit, Honolulu, HI. 2008.

[10]LaValle S M. Robot Motion Planning: A Game-theoretic Foundation[J]. Algorithmica, 2000, 26(3-4): 430-465.

[11]Dechter R, Pearl J. Generalized best-1st Search Strategies and the Optimality of A*[J]. Journal of the ACM, 1985, 32(3): 505-536.

[12]Kavraki L E, Svestka P, Latombe J C, et al. Probabilistic Roadmaps for Path Planning in High-dimensional Configuration Spaces[J]. IEEE Transactions on Robotics and Automation , 1996, 12(4): 566-580.

[13]Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.

[14]Bohlin R, Kavraki E E. Path planning using lazy PRM[C]. IEEE International Conference on Robotics and Automation, 2000: 521-528.

[15]Khatib O, Mampey L M. Fonction D é cision-Commande d'un Robot Manipulateur [R]. DERA-CERT, Toulouse, France, 1978, 2(7): 156.

[16]Koren Y, Borenstein J. Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation[C]. IEEE International Conference on Robotics and Automation, 1991: 1398-1404.

[17]Zelek J S. Dynamic Path Planning[C]. IEEE International Conference on Systems, Man and Cybernetics, 1995: 1285-1290.

[18]LaValle S M. Rapidly-Exploring Random Trees: A New Tool for Path Planning[R]. Technical Report TR 98-11, Computer Science Deptartment, Iowa State University, 1998.

[19]Poli R, Kennedy J, Blackwell T. Particle Swarm Optimization[J]. Swarm Intelligence, 2007, 1(1): 33-57.

[20]Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[C]. Proceedings of the First European Conference on Artificial Life, 1991: 134-142.