移動巡檢機器人全局路徑規(guī)劃方法分析2800字

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

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