移動巡檢機器人全局路徑規劃方法分析綜述1.1變電站巡檢機器人巡檢過程機器人巡檢過程實質上是機器人找到從其當前位置到檢查點的最佳路線的過程。這里所說的最佳路徑是指在道路上沒有障礙物的最短路徑，即機器人在初次規劃路徑和進行檢查時沒有遇到障礙物，并且進行正常檢查；如果機器人在檢查過程中遇到障礙物并且無法避免，則機器人會認為路徑已阻塞并重新啟動。由于任務要求，下一個計劃的路徑可能不是原始地圖中最短的路徑，但它必須是可到達的路徑。在檢查開始之前，機器人首先在工作人員手動控制下巡視要檢查的地點一周，以便對檢查地點進行地圖建模。地圖建模的本質是將SLAM算法用于從激光傳感器接收的數據。基于激光雷達SLAM建好的是一種柵格地圖。柵格地圖可以將實際環境的位置鄧希賢奧維一個個小格子。在相同的比例尺坐標系中，所有節點都有自己的唯一坐標。柵格圖必須編碼。所有自由節點形成地圖上的“自由區”。在“自由區”中，所有要檢查的點和起點都一個接一個地連接在一起，形成一個加權的“圖形”，權重位于節點和節點之間。檢查路徑規劃經過轉換，以找到圖中頂點之間的最短路徑。1.2圖論介紹在數學中，我們用一個二元組(V圖論是數學的一個分支。它使用圖形作為研究對象。它的概念和結果來自多種來源。它源于探索一些困難的數學游戲，例如Euler解決的“七橋”問題。同時，一些游戲難題在人們中廣為流傳，例如迷宮，博弈和棋盤上馬的最短路線。圖論于1847年首次用于工程學，當時它被用于分析電路網絡。后來其作用越來越突出。隨著科學界的不斷深入探索，圖論已成為諸多問題的密匙。1.3全局路徑規劃方法每種路徑規劃方法都有其自身的優缺點。到目前為止，還沒有可應用于所有環境和移動機器人系統的全局路徑規劃方法。但是，將不同的規劃方法結合起來并利用各自的優勢往往可以在路徑規劃中取得良好的效果，并已成為當前路徑規劃方法的發展方向。下面將簡單的介紹幾種穆齊安應用于各種領域的路徑規劃算法。

1.1.1Dijkstra算法Dijkstra算法是經典的單源搜索算法，用于圖搜索中的最短路徑，它使用連續更新當前狀態下每個起點V到達終點S最短距離的方式完成搜索任務。傳統Dijkstra算法的基本思想是，首先要有一個帶有權值的有向圖，如圖3-1所示，然后設置三個集合T、S、V，三個集合間的數學關系可以表示為：T=S∪V這個公式中T表示的是點的集合，S表示的是以搜索點的集合。S的初始狀態為僅含有起點的集合，V的初始狀態為除源點以外的所有點的集合。在路徑搜索過程中，隨著迭代次數的增加，S集合繼續增長，而V集合繼續縮小。從源點開始，所有可訪問的節點都從V記錄傳輸到S記錄。圖3-1帶權值有向圖1.1.2A＊算法A*算法的實現要要知道從起點到當前點的成本，而且還要知道從當前節點到終點的預測成本。它是一種深度算法。它在某種程度上類似于Dijkstra，但是引入了預期成本會導致提供啟發式信息并給出搜索方向。A*算法的基本思想是，選擇一個評估函數，計算路徑中每個節點的評估函數值，如果接下來要選擇行走的點是該節點，則計算從起點經過該節點，并最終到達終點的估計值，每次選擇最佳估計值的節點后，繼續發散搜索，直到搜尋到目標節點，確定出最短路徑。可以用以下表達式進行描述:f(n)=g(n)+?(n)其中，f(n)是點n處的評估函數，其函數值是由g(n)和h(n)兩部分函數值構成的;g(n)是從路徑起始點到達當前點n的已知路徑的長度，是一個確定值;h(n)是當前點n到目標節點的預測值，是不確定的。A*算法的關鍵是估計函數h(n)的選取，h(n)的選擇與實際環境有很大一部分關系，估計值與實際值越接近，搜索效果越好，并且所選擇的原則是該函數的估計值不大于實際值，以確保最終路徑為最小距離。運行A*算法時，要創建兩個表：OPEN和CLOSE。待識別的相鄰節點存儲在OPEN表中，而已識別的節點存儲在CLSOE表中。每次將OPEN表中f(i)函數值最小的點傳輸到CLOSE表中，同時更新OPEN表，當前節點記錄并稱之為父節點，這與Dijkstra算法很相似。A*算法在理論上是花費時間最短的，但是也有缺點：它的空間增長是指數級別的；當目標點數量較大時，A*算法會導致運算的冗余和函數的復雜化。1.1.3遺傳算法遺傳算法是一種用于模擬生物進化的算法。這是可以組織和適應自身的全局優化路徑搜索方法。搜索路徑中使用的遺傳算法的基本思想是首先創建一個初始路徑種群。初始種群由許多隨機產生的染色體組成。每個染色體都是一條包含路徑節點的路徑。每個染色體的編碼點數目可以不同，但??是必須遵循以下原則：（1）每個染色體的起點和終點必須是計劃路線的起點和終點。（2）每一條染色體上的片段一定只能展現唯一的一次。（3）確保每個染色體都可以形成無碰撞的路徑。建立初始種群后，有必要根據特定的環境和移動機器人系統創建適應度函數，評估路徑并為優勝劣汰而開始選擇模式。對選定的優勢種群進行進化操作，包括交叉和突變，評估并進一步選擇它們，并將它們循環，直到滿足終止條件并選擇具有最大適應性的最佳解決方案，并且此規劃路徑結束。如今，遺傳算法已廣泛應用于路徑規劃領域。它是一種智能的隨機搜索算法。它不需要了解問題的所有特征，可以簡化更復雜的問題，并且具有良好的魯棒性。而且該方法簡單，易于理解且易于使用。在遺傳算法中，道路最優化選擇取決于種群的開始形態。人口越大，迭代過程中的分集性能越好，算法過早成熟的可能性就越小，準確性也越高。1.1.4模擬退火算法1953年，Metropolis首次提出了模擬輝光算法。由于其與一般組合優化問題的相似性，Kirkpatrick于1983年將其成功應用于組優化領域。模擬退火算法使用基于蒙特卡洛迭代法的隨機搜索方法來找到一組最佳組合。模擬退火算法的基本思想是模擬固體的物理退火過程，并且必須首先將固體的溫度提高到一定程度。此時，固體中的分子處于無序和劇烈攪拌的狀態，內部分子的分布遵循吉布斯分布。其中，ρ(ri)為第1個分子的概率密度；E(ri)為第物體里的分子運動活性會逐漸降低伴隨著溫度的冷卻，并且分子會向著熵減的程度進行。冷卻過程中的溫度控制非常重要。如果冷卻過程太短，則會發生淬火，并且能量不會達到最低水平。物理退火的實現步驟和組合優化解這兩個問題機器相似。模擬輝光算法基于的是高溫狀態，并假設根據Metropolis掃描原理生成的新狀態。當冷卻時，重復采樣過程，計算能量函數，最后獲得最佳或幾乎最佳解，即組合優化問題的最佳組合。表3-1顯示了物理退火過程與解決組合優化問題的過程之間的比較。表3-1物理退火過程與組合優化解決比較物理退火組合優化物理內部某一狀態一組解物體基