路徑規劃

路徑規劃是運動規劃的主要研究內容之一。運動規劃由路徑規劃和軌跡規劃組成，連線起點位置和終點位置的序列點或曲線稱之為路徑，構成路徑的策略稱之為路徑規劃。

路徑規劃在很多領域都具有廣泛的套用。在高新科技領域的套用有：機器人的自主無碰行動；無人機的避障突防飛行；巡航飛彈躲避雷達搜尋、防反彈襲擊、完成突防爆破任務等。在日常生活領域的套用有：GPS導航；基於GIS系統的道路規劃;城市道路網規劃導航等。在決策管理領域的套用有：物流管理中的車輛問題(VRP)及類似的資源管理資源配置問題。通信技術領域的路由問題等。凡是可拓撲為點線網路的規劃問題基本上都可以採用路徑規劃的方法解決。

基本介紹

• 中文名：路徑規劃
• 外文名：Path Planning
• 類目：電子信息技術
• 套用領域：高科技、日常生活、物流管理等
• 常用算法：Dijkstra算法、遺傳算法等

路徑規劃問題分類

根據對環境信息的把握程度可把路徑規劃劃分為基於先驗完全信息的全局路徑規劃和基於感測器信息的局部路徑規劃。其中，從獲取障礙物信息是靜態或是動態的角度看，全局路徑規劃屬於靜態規劃(又稱離線規劃)，局部路徑規劃屬於動態規劃(又稱線上規劃)。全局路徑規劃需要掌握所有的環境信息，根據環境地圖的所有信息進行路徑規劃；局部路徑規劃只需要由感測器實時採集環境信息，了解環境地圖信息，然後確定出所在地圖的位置及其局部的障礙物分布情況，從而可以選出從當前結點到某一子目標結點的最優路徑。

根據所研究環境的信息特點，路徑規劃還可分為離散域範圍內的路徑規劃問題和連續域範圍內的路徑規劃問題。離散域範圍內的路徑規劃問題屬於一維靜態最佳化問題，相當於環境信息簡化後的路線最佳化問題；而連續域範圍內的路徑規劃問題則是連續性多維動態環境下的問題。

路徑規劃的一般步驟

一般的連續域範圍內路徑規劃問題，如機器人、飛行器等的動態路徑規劃問題，其一般步驟主要包括環境建模、路徑搜尋、路徑平滑三個環節。

（1）環境建模。環境建模是路徑規劃的重要環節，目的是建立一個便於計算機進行路徑規劃所使用的環境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間，實現相互間的映射。

（2）路徑搜尋。路徑搜尋階段是在環境模型的基礎上套用相應算法尋找一條行走路徑，使預定的性能函式獲得最優值。

（3）路徑平滑。通過相應算法搜尋出的路徑並不一定是一條運動體可以行走的可行路徑，需要作進一步處理與平滑才能使其成為一條實際可行的路徑。

對於離散域範圍內的路徑規劃問題，或者在環境建模或路徑搜尋前己經做好路徑可行性分析的問題，路徑平滑環節可以省去。

常用算法

路徑規劃的方法有很多，根據其自身優缺點，其適用範圍也各不相同。根據對各領域常用路徑規划算法的研究，按照各種算法發現先後時序及算法基本原理，將算法大致分為四類:傳統算法、圖形學的方法、智慧型仿生學算法和其他算法。

傳統算法

傳統的路徑規划算法有：模擬退火算法、人工勢場法、模糊邏輯算法、禁忌搜尋算法等。

（1）模擬退火算法（Simulated Annealing），簡稱SA)是一種適用於大規模組合最佳化問題的有效近似算法。它模仿固體物質的退火過程，通過設定初溫、初態和降溫率控制溫度的不斷下降，結合機率突跳特性，利用解空間的鄰域結構進行隨機搜尋。具有描述簡單、使用靈活、運行效率高、初始條件限制少等優點，但存在著收斂速度慢、隨機性等缺陷，參數設定是套用過程中的關鍵環節。

（2）人工勢場法是一種虛擬力法。它模仿引力斥力下的物體運動，目標點和運動體間為引力，運動體和障礙物間為斥力，通過建立引力場斥力場函式進行路徑尋優。優點是規劃出來的路徑平滑安全、描述簡單等，但是存在局部最優的問題，引力場的設計是算法能否成功套用的關鍵。

（3）模糊邏輯算法網模擬駕駛員的駕駛經驗，將生理上的感知和動作結合起來，根據系統實時的感測器信息，通過查表得到規劃信息，從而實現路徑規劃。算法符合人類思維習慣，免去數學建模，也便於將專家知識轉換為控制信號，具有很好的一致性、穩定性和連續性。但總結模糊規則比較困難，而且一旦確定模糊規則線上調整困難，應變性差。最優的隸屬度函式、控制規則及線上調整方法是最大難題。

（4）禁忌搜尋算法（TS）是一種全局逐步尋優算法，是對人類智力過程的一種模擬。通過引入一個靈活的存儲結構和相應的晉級規則來避免與會搜尋，並通過藐視準則來赦免一些被緊急的優良狀態，以實現全局最佳化。

圖形學的方法

傳統算法在解決實際問題時往往存在著建模難的問題，圖形學的方法則提供了建模的基本方法，但是圖形學的方法普遍存在著搜尋能力的不足，往往需要結合專門的搜尋算法。圖形學的方法有：C空間法、柵格法、自由空間法、voronoi圖法等。

（1）C空間法又稱可視圖空間法，即在運動空間中擴展障礙物為多邊形，以起始點、終點和所有多邊形頂點間的可行直線連線（不穿過障礙物的連線）為路徑範圍來搜尋最短路徑。C空間法的優點是直觀，容易求得最短路徑；缺點是一旦起始點和目標點發生改變，就要重新構造可視圖，缺乏靈活性。即其局部路徑規劃能力差，適用於全局路徑規劃和連續域範圍內的路徑規劃。尤其適用於全局路徑規劃中的環境建模。

（2）自由空間法針對可視圖法應變性差的缺陷，採用預先定義的基本形狀（如廣義錐形，凸多邊形等）構造自由空間，並將自由空間表示為連通圖，然後通過對圖的搜尋來進行路徑規劃。由於起始點和終點改變時，只相當於它們在己構造的自由空間中位置變化，只需重新定位，而不需要整個圖的重繪。缺點是障礙物多時將加大算法的複雜度，算法實現困難。

（3）柵格（grid）法，即用編碼的柵格來表示地圖，把包含障礙物的柵格標記為障礙柵格，反之則為自由柵格，以此為基礎作路徑搜尋。柵格法一般作為路徑規劃的環境建模技術來用，作為路徑規劃的方法它很難解決複雜環境信息的問題，一般需要與其他智慧型算法相結合。

（4） voronoi圖是關於空間鄰近關係的一種基礎數據結構。它是用一些被稱為元素的基本圖形來劃分空間，以每兩點間的中垂線來確定元素的邊，最終把整個空間劃分成結構緊湊的voronoi圖，而後運用算法對多邊形的邊所構成的路徑網進行最優搜尋。優點是把障礙物包圍在元素中，能實現有效避障，缺點圖的重繪比較費時，因而不適用於大型動態環境。

智慧型仿生學算法

處理複雜動態環境信息情況下的路徑規劃問題時，來自於自然界的啟示往往能起到很好的作用。智慧型仿生學算法就是人們通過仿生學研究，發現的算法，常用到的有:蟻群算法、神經網路算法、粒子群算法、遺傳算法等。

（1）蟻群算法，（Ant Colony Algorithm簡稱ACA）的思想來自於對蟻群覓食行為的探索，每個螞蟻覓食時都會在走過的道路上留下一定濃度的信息素，相同時間內最短的路徑上由於螞蟻遍歷的次數多而信息素濃度高，加上後來的螞蟻在選擇路徑時會以信息素濃度為依據，起到正反饋作用，因此信息素濃度高的最短路徑很快就會被發現。算法通過疊代來模擬蟻群覓食的行為達到目的。具有良好的全局最佳化能力、本質上的並行性、易於用計算機實現等優點，但計算量大、易陷入局部最優解，不過可通過加入精英蟻等方法改進。

（2）神經網路算法是人工智慧領域中的一種非常優秀的算法，它主要模擬動物神經網路行為，進行分散式並行信息處理。但它在路徑規劃中的套用卻並不成功，因為路徑規劃中複雜多變的環境很難用數學公式進行描述，如果用神經網路去預測學習樣本分布空間以外的點，其效果必然是非常差。儘管神經網路具有優秀的學習能力，但是泛化能力差是其致命缺點。但因其學習能力強魯棒性好，它與其他算法的結合套用己經成為路徑規劃領域研究的熱點。

（3）遺傳算法（Genetic Algorithms，簡稱GA）是當代人工智慧科學的一個重要研究分支，是一種模擬達爾文遺傳選擇和自然淘汰的生物進化過程中的計算模型。它的思想源於生物遺傳學和適者生存的自然規律，是按照基因遺傳學原理而實現的一種疊代過程的搜尋算法。最大的優點是易於與其他算法相結合，並充分發揮自身疊代的優勢，缺點是運算效率不高，不如蟻群算法有先天優勢，但其改進算法也是目前研究的熱點。

路徑規劃套用

路徑規劃的套用領域非常廣泛，如：機器人機械臂的路徑規劃、飛行器航跡規劃、巡航飛彈路徑規劃、旅行商問題（TSP）以及其衍生的各種車輛（VRP）路徑規劃、虛擬裝配路徑規劃、基於道路網的路徑規劃、電子地圖GPS導航路徑搜尋與規劃、路由問題等。

離散域範圍內的最短路徑規劃問題

屬於離散域範圍內最短路徑規劃的問題有：基於道路網的路徑規劃問題、電子地圖CPS導航路徑搜尋規劃問題、路由問題等。

（1）基於道路網和基於電子地圖GPS導航的路徑規劃都可視作基於GIS (Geographical Information System)的路徑規劃問題。這些問題的解決都是從複雜的數據信息中提取出所需道路信息，以路口為節點，道路信息為路徑信息，構造出複雜的路徑信息拓撲網路，將起始點和目標點定位為這個拓撲網路上兩個節點，而後運用路徑搜尋算法進行最短路徑尋優規劃。

（2）路由問題屬於通信技術領域研究的重點。路由問題的主要功能是使數據信息順利地從源節點傳送到目標節點。根據Qos的設計需求，可在路徑上設定不同的權重，定義路徑參數。在網路拓撲結構中穩定高效地搜尋最優路徑，快速聚合。實時地進行網路擁堵控制，根據具體情況進行動態路由選擇。

（3）從最短路徑規劃的角度看，這一類問題的特點大同小異，都是在己知路徑信息(節點數，路徑參數信息，拓撲結構等)情況下，從己知起始節點到目標節點的最優路徑路徑規劃問題，路徑信息多為靜態信息，即使有信息變動，智慧型算法也有足夠的能力進行及時的應變規劃。常用的算法有：Dijkstra算法、A*搜尋算法、模擬退火算法、蟻群算法、遺傳算法、粒子群算法、Floyd算法、Fallback算法等。

離散域範圍內的遍歷式最優路徑問題

屬於離散域範圍內遍歷式最優路徑的問題有：虛擬裝配路徑規劃、旅行商問題(TSP)以及其衍生的各種車輛問題(VRP)和物流問題等。由於虛擬裝配路徑規劃的核心是裝配序列規劃問題，而序列規劃問題屬於典型的TSP問題。

這類問題的一般特點是:己知路徑信息為靜態信息，對於腳踏車輛問題，起始點唯一，最終目標節點為起始點，中間有多個子目標節點。要求車輛以最短的路徑從起始點出發，遍歷所有子目標節點後，回到起始點。當然，有的問題是以最短時間或最少費用等為規劃目標，這樣的路徑規劃問題可把相應路徑信息調整為路徑時間信息或路徑費用信息，對應節點不變。此外，也有多車輛、多起點、考慮載重等因素的整體調控問題，此類問題是基於腳踏車輛路徑規劃問題的延展套用。

解決此類路徑問題的常用智慧型算法有：蟻群算法、禁忌搜尋算法、模擬退火算法、神經網路算法、遺傳算法、粒子群算法等。

連續域範圍內的全局路徑規劃問題

屬於連續域範圍內全局路徑規劃圖的問題有:機器人機械臂自主移動路徑規劃、無人機飛行器航跡規劃、巡航飛彈航跡規劃等。從路徑規劃角度來看，這類問題都是己知環境信息，且環境信息為靜態信息的情況下，如何在安全範圍內避開障礙物找到到達目的地的最短路徑問題。

解決此類問題通常依靠智慧型算法與環境建模結合使用。直接套用於此類問題的路徑規划算法有：可視圖法、自由空間法、Voronoi圖法、柵格法、懲罰函式法、模擬退火算法等。間接套用的智慧型算法有：A*搜尋算法、蟻群算法、遺傳算法、粒子群算法、人工勢場法等。

連續域範圍內的局部路徑規劃問題

連續域範圍內的局部路徑規劃和全局路徑規劃套用領域基本相同，它們在其套用領域內而對的環境不同，解決的問題也不同。局部規劃而對的是動態的實時的環境信息，屬於線上規劃，對算法要求實時性好、高效、穩定，是目前研究的熱點。

套用於此類問題的路徑規划算法有：蟻群算法、遺傳算法、粒子群算法、A*搜尋算法、人工勢場法、量子粒子群算法、神經網路算法等。

連續域範圍內的遍歷式路徑規劃問題

連續域範圍內的遍歷式路徑規劃主要套用於：清潔機器人、草坪修剪機、掃雷機器人、搜救機器人、礦藏探測器等。其特點是：機器人需用最短的路徑去覆蓋所工作區域的每個角落，要求最大的覆蓋率和最小的重複率。解決此類問題需先進行環境建模，最常用的方法是柵格法，後來Neumann de Carvalho R等人發明了模板模型法。

解決此類問題的常用算法有:神經網路算法、A*算法、遺傳算法、粒子群算法、蟻群算法等。

路徑規劃的未來發展

隨著科學技術的不斷發展，路徑規劃技術而對的環境將更為複雜多變。這就要求路徑規划算法要具有迅速回響複雜環境變化的能力。這不是目前單個或單方而算法所能解決問題，因此在未來的路徑規劃技術中，除了研究發現新的路徑規划算法外，還有以下幾方而值得關註：

（1）先進路徑規划算法的改進。任何一種算法在實際套用過程中都要而對諸多困難，特別是自身的局限性。例如：A*算法作為一種啟發式搜尋算法具有魯棒性好，快速回響的特點，但是套用於實際中還是存在弊端，對於A*算法套用於無人機航跡規劃時的弊端，李季等提出了改進A*算法，解決了A*算法難以滿足直飛限制並且有飛機最小轉彎半徑等約束的局限性這一問題。

（2）路徑規划算法的有效結合（即混合算法）。任何的單一路徑規划算法都不可能解決所有實際套用中的路徑規劃問題，特別是在而對交叉學科的新問題時，研究新算法的難度大，路徑規划算法間的優勢互補為解決這一問題提供了可能。對於多空間站路徑規劃問題，金飛虎等把蟻群算法和神經網路方法相結合解決了這一問題，並避免了單純運用神經網路算法時出現的局部最小問題。

（3）環境建模技術和路徑規划算法的結合。而對複雜的二維甚至三維連續動態環境信息時，算法所能做的是有限的，好的建模技術和優秀路徑規划算法相結合將成為解決這一問題的一種方法。如柵格法和蟻群算法的結合， C空間法和Dijkstra算法的結合等。

（4）多智慧型體並聯路徑規划算法設計。隨著科學技術的套用發展，多智慧型體並行協作己經得到套用。其中，多機器人協作和雙機械臂協作中的路徑衝突問題日漸為人們所關注，如何實現其無碰路徑規劃將成為日後研究的熱點之一。