目錄
路徑規劃問題分類
根據對環境信息的把握程度可把路徑規劃劃分為基于先驗信息的全局路徑規劃和基于傳感器信息的局部路徑規劃。其中，從獲取障礙物信息是靜態或是動態的角度看，全局路徑規劃屬于靜態規劃(又稱離線規劃)，局部路徑規劃屬于動態規劃(又稱在線規劃)。全局路徑規劃需要掌握所有的環境信息，根據環境地圖的所有信息進行路徑規劃；局部路徑規劃只需要由傳感器實時采集環境信息，了解環境地圖信息，然后確定出所在地圖的位置及其局部的障礙物分布情況，從而可以選出從當前結點到某一子目標結點的路徑。
根據所研究環境的信息特點，路徑規劃還可分為離散域范圍內的路徑規劃問題和連續域范圍內的路徑規劃問題。離散域范圍內的路徑規劃問題屬于一維靜態優化問題，相當于環境信息簡化后的路線優化問題；而連續域范圍內的路徑規劃問題則是連續性多維動態環境下的問題。[1]
路徑規劃一般步驟
一般的連續域范圍內路徑規劃問題，如機器人、飛行器等的動態路徑規劃問題，其一般步驟主要包括環境建模、路徑搜索、路徑平滑三個環節。
（1）環境建模。環境建模是路徑規劃的重要環節，目的是建立一個便于計算機進行路徑規劃所使用的環境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間，實現相互間的映射。
（2）路徑搜索。路徑搜索階段是在環境模型的基礎上應用相應算法尋找一條行走路徑，使預定的性能函數獲得值。
（3）路徑平滑。通過相應算法搜索出的路徑并不一定是一條運動體可以行走的可行路徑，需要作進一步處理與平滑才能使其成為一條實際可行的路徑。
對于離散域范圍內的路徑規劃問題，或者在環境建模或路徑搜索前已經做好路徑可行性分析的問題，路徑平滑環節可以省去。
路徑規劃常用算法
路徑規劃的方法有很多，根據其自身優缺點，其適用范圍也各不相同。根據對各領域常用路徑規劃算法的研究，按照各種算法發現先后時序及算法基本原理，將算法大致分為四類:傳統算法、圖形學的方法、智能仿生學算法和其他算法。[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*算法、遺傳算法、粒子群算法、蟻群算法等。
路徑規劃未來發展
隨著科學技術的不斷發展，路徑規劃技術而對的環境將更為復雜多變。這就要求路徑規劃算法要具有迅速響應復雜環境變化的能力。這不是單個或單方而算法所能解決問題，因此在未來的路徑規劃技術中，除了研究發現新的路徑規劃算法外，還有以下幾方而值得關注：[4]
（1）*路徑規劃算法的改進。任何一種算法在實際應用過程中都要而對諸多困難，特別是自身的局限性。例如：A*算法作為一種啟發式搜索算法具有魯棒性好，快速響應的特點，但是應用于實際中還是存在弊端，對于A*算法應用于無人機航跡規劃時的弊端，李季等提出了改進A*算法，解決了A*算法難以滿足直飛限制并且有飛機最小轉彎半徑等約束的局限性這一問題。
（2）路徑規劃算法的有效結合（即混合算法）。任何的單一路徑規劃算法都不可能解決所有實際應用中的路徑規劃問題，特別是在而對交叉學科的新問題時，研究新算法的難度大，路徑規劃算法間的優勢互補為解決這一問題提供了可能。對于多空間站路徑規劃問題，金飛虎等把蟻群算法和神經網絡方法相結合解決了這一問題，并避免了單純運用神經網絡算法時出現的局部最小問題。
（3）環境建模技術和路徑規劃算法的結合。而對復雜的二維甚至三維連續動態環境信息時，算法所能做的是有限的，好的建模技術和優秀路徑規劃算法相結合將成為解決這一問題的一種方法。如柵格法和蟻群算法的結合， C空間法和Dijkstra算法的結合等。
（4）多智能體并聯路徑規劃算法設計。隨著科學技術的應用發展，多智能體并行協作已經得到應用。其中，多機器人協作和雙機械臂協作中的路徑沖突問題日漸為人們所關注，如何實現其無碰路徑規劃將成為日后研究的熱點之一。
參考資料
目錄