路徑規劃算法研究

全局路徑規劃算法

l  Dijkstra 算法：

Dijkstra 算法通過逐步更新節點的最短距離來找到起點到目標節點的最短路徑，通過維護一個優先隊列來選擇當前最短距離的節點進行擴展，在找到目標節點或者遍歷完所有節點后才停止重復之前的操作。

Dijkstra 算法的優點是能夠找到最短路徑，適用于無負權邊的圖；缺點是時間復雜度較高，無法處理負權邊的情況。

使用RRT 和Dijkstra 算法融合避障:使用RRT 算法得到可行路徑，并將這個可行區域擴張，類似膨脹操作，再對可行區域進行柵格化，在柵格地圖中通過Dijkstra 算法找到最短路徑。

l  A*算法：

A*算法利用一個估計函數（啟發函數）來預測從當前節點到目標節點的最 佳路徑，以減少搜索的開銷。通過選擇代價最小的節點進行擴展，直到找到目標節點或搜索完整個圖。

引入了啟發式函數的權重系數來提高A*算法的搜索效率。最終實現了A*和DWA 算法的融合，使路徑更平滑，提高了算法的避障性能。

提出一種基于時間窗模型的動態路徑規劃方法，用來對多輛AGV 小車進行實時路徑規劃。每一輛AGV 小車單獨使用A*算法進行路徑規劃，當路徑與障礙物重疊時，實時更改道路權重，重新進行路徑規劃，這樣就實現了實時避障。該算法在動態環境下有良好的適應性和魯棒性。

l  D*算法：

D*算法通過不斷更新路徑的代價和啟發式估計值來適應環境的變化。D*算法首先從目標節點開始，根據當前的代價和啟發式估計值選擇最優的鄰居節點，并更新路徑和代價信息。當環境發生變化時，D*算法會重新評估路徑，并通過局部的增量更新來快速修正路徑。這種增量的更新策略使得D*算法適用于實時的路徑規劃應用。

針對D*算法遍歷節點過多、路徑規劃搜索緩慢的缺陷，從算法融合的思想出發，提出一種基于跳轉搜索策略的改進D*算法。在靜態規劃過程中，采用跳轉搜索策略代替原有D*算法的節點擴展策略。改進后的算法可以在路徑規劃過程中減少70%的路徑節點數，提高規劃速度。

l  模擬退火算法：

模擬退火算法基本思想源自固體退火過程，通過模擬固體從高溫到低溫的冷卻過程，以一定概率接受劣解，從而避免陷入局部最優解。算法通過隨機擾動當前解并根據目標函數的變化情況進行接受或拒絕的決策，逐步降低溫度直到收斂到最優解，具有全局搜索能力和對局部最優解的逃逸能力。

在人工勢場法中融合模擬退火算法，當傳統人工勢場法陷入局部最小值時，通過模擬退火法跳出當前局部最小值區域。

l  遺傳算法：

遺傳算法通過模擬自然界的遺傳機制，利用基因編碼和遺傳操作來搜索問題的最優解。算法將解空間中的每一組解都抽象化為算法中的個體，個體在交叉、變異和選擇等操作下就像是接受自然界的自然選擇。優 秀的個體在生存和繁衍上占據較大優勢，隨著時間推移，優勝劣汰，最終存活的大都是較為優 秀的解。

提出一種改進遺傳算法用于巡檢路徑規劃，首先采用拓撲圖對機器人工作環境進行建模，然后采用特殊的交叉算子、自適應變異算子和淘汰算子，對每一代被淘汰的個體進行逆轉變異并將產生的新個體重新加入種群，隨迭代次數調整變異概率，從而對連續的規劃空間直接進行尋優。文獻[7]以工廠中零件需求時間窗為約束條件，最短時間為規劃目標，使用遺傳算法得到AGV 小車的最優運輸路線。

l  蟻群算法：

蟻群算法通過模擬螞蟻在路徑選擇過程中的信息素沉積和揮發行為，來尋找最優解。蟻群算法在對地圖搜索過程中，在搜索過的區域增加信息素，信息素越高，說明來過的螞蟻越多。在后續的搜索過程中基于當前地圖信息素選擇下一位置。

在考慮傳統蟻群算法搜索路徑時存在找到收斂速度慢、拐點多且不能動態避障等問題，提出一種基于拉普拉斯分布與動態窗口融合的蟻群算法來解決機器人路徑規劃。

提出了一種用于AGV 路徑規劃的雙種群蟻群算法:該算法引入差異化信息素初始值，修改啟發函數并在信息素更新時對最優及最差路徑進行獎懲；以改進策略為基礎，引入自適應步長搜索策略，通過具有差異化步長的兩個種群相互協作加強算法尋優能力和搜索效率；針對死鎖問題，提出了將符合條件的單元格視為障礙物的“填充陷阱”策略。

提出了一種解決多AGV 路徑規劃問題的方法。對每一輛AGV 小車的初始路徑分別使用蟻群算法進行優化。對于多輛AGV 小車，使用通過采用多AGV 沖突解決策略。這種策略可以在路途最短和路徑最光滑的基礎上，避開沖突，最終實現多車避障。該方法融合了蟻群算法的優勢，能夠有效地生成高質量的初始路徑，并通過沖突解決策略避免了沖突的發生。

l  粒子群優化算法：

粒子群優化算法通過模擬魚或者鳥在魚群或者鳥群中的搜索和協作行為來得到最優解。算法將每一個解抽象化為一個粒子，每一個粒子在解空間中的運動同時受到個體最優和全局最優的影響，粒子在將自身當前狀態與當前最優解對比后獲得更優的搜索方向。

提出了一種基于粒子群優化和反應避障的編隊控制系統。在領航跟隨法中，通過粒子群優化實現領航者軌跡規劃。領航者軌跡規劃完成后，并不能保證跟隨者的軌跡不會與障礙物發生碰撞，因此在編隊控制中加入了跟隨者反應避障系統，實現了編隊避障。

基于傳感器信息的局部路徑規劃算法

l  Bug 算法：

Bug1 算法的基本思想是當小車面前沒有障礙物時，小車將直線走向目標點。當遇到障礙物時，小車將沿著障礙物邊沿移動，直到可以繼續按直線走向目標點。

Bug2 算法的基本思想是當小車面前沒有障礙物時，小車將直線走向目標點。當遇到障礙物時，小車將沿著障礙物邊沿移動，直到到達與初始位置和目標點連接的直線相交的位置時，停止繞行，繼續按照原來的直線走向目標點。

將深度學習算法和路徑規劃技術相結合，提出了一種基于深層卷積神經網絡和改進Bug 算法的機器人避障方法。]針對傳統人工勢場算法易陷入局部極值的問題，引入Bug 算法，保證算法的全局性能。

l  向量勢直方圖法：

向量勢直方圖法環境用網格表示，每個單元賦值表示該單元有障礙的可能性，在每一步環境信息轉化為1 維直方圖，引入代價函數值G，為所有可以通過的方向賦值選擇具有最小代價函數值G 的方向。G=a·目標方向+b ·輪轉動角度+c ·原運動方向。

采用向量場直方圖和拓撲地圖相結合的方法,實現AGV 的快速部署。

l  動態窗口法：

動態窗口法的基本思想是對當前的小車計算下一時刻可能的速度空間，對速度空間中的每一組速度進行軌跡預測，通過當前速度和預測的軌跡點對速度進行評估，在速度空間中選取評價最 高的速度作為下一時刻的速度。

使用改進后的動態窗口法實現了阿克曼機器人的局部路徑規劃。在傳統的編隊保持方案中加入動態窗口方法使編隊穩定地到達目標點。

提出了一種新的基于跳點搜索的優化A*算法和動態窗口法的融合算法。

l  人工勢場法：

人工勢場法的核心思想是人為構造引力場和斥力場。障礙物將對被控對象產生一個斥力，斥力方向由障礙物指向被控對象，這個斥力的大小與被控對象同障礙物之間的距離有關。目標點將對被控對象產生一個吸引力，引力方向由被控對象指向目標點，引力的大小與被控對象同目標點之間的距離有關。被控對象在引力和斥力的共同作用下，遠離障礙物，靠近目標點，最終完成路徑規劃。

將引力作用閾值引入引力勢場函數，解決引力過大問題；在斥力勢場函數中引入目標點與移動機器人之間的距離，解決目標不可達問題；根據環境復雜度，提出了自適應速度調節機制；針對局部極小值問題，分別提出了APF-v1 和APF-v2 兩種構建虛擬目標點的方法，引導移動機器人走出陷阱區域。

通過針對多智能體系統在避障過程中出現的問題，結合使用鴿群搜索算法和人工勢場法，對于車隊隊形控制使用領航跟隨法，最終實現在一定編隊隊形下的避障任務。這一算法可以較為良好的保持避障過程中車隊的隊形，并且避免了傳統人工勢場法中的局部最優解問題。最終的仿真實驗結果顯示，使用這種方法進行避障任務的平均避障時間相比傳統方法提高了約20.96%。

智能體編隊控制算法

編隊控制算法是一種用于多個無人車或機器人形成有序編隊的控制算法。這些算法旨在使多個車輛按照特定的形態和行為規則進行協同操作，以實現任務分配、路徑跟蹤和相互協調等功能。以下是幾種常見的編隊控制算法：

l  領航跟隨者算法：

領航跟隨者算法的基本思想是將車隊中的一些小車看作是領航者，另一些小車看作是跟隨者。我們能預先知道領航者的位姿信息與當前速度，也能知道初始跟隨者與領航者之間的位置關系。對領航者的位姿信息和當前速度通過跟隨者與領航者之間的位置關系可以得到跟隨者當前理論上的位姿與速度。

提出了一種基于時延補償的領航跟隨編隊控制方案。

在領航跟隨編隊控制算法中設置了動態的φ值,當編隊的領航者改變方向(或者遇到障礙物改變方向)時,φ值即變為動態的,隨著領航者角速度的變化而變化,從而使跟隨者路徑更加平滑,隊形的保持更加可靠。

提出了一種虛擬結構法和領航跟隨法相結合的機器人協同編隊算法。對整體的控制主要實現對領航機器人的控制，而對于該整體內部，已知所有領航機器人的位置信息就能得到所有跟隨機器人的目標位置，設計了控制器，控制所有跟隨機器人跟蹤各自的目標位置，從而實現多機器人的協同編隊控制。

l  虛擬結構算法：

虛擬結構算法基于預定義的幾何結構或模式，使車輛之間保持特定的相對位置和距離。這些算法可以基于幾何約束或相對運動規則來生成編隊的運動軌跡，以實現編隊的形態控制。

以虛擬結構為框架,在編隊控制算法里加入隊形反饋,鄰近的分散編隊控制器之間進行通信和協調,使得編隊控制器既能控制編隊機動運動速度,又能在編隊機動過程中較好地維持隊形。

l  分布式協同算法：

這類算法允許車輛之間通過局部通信和信息交換進行協同操作。車輛根據周圍車輛的狀態和位置信息，自主地調整自己的速度和軌跡，以保持編隊的協調性和一致性。

提出了一種基于布谷鳥搜索算法的多智能體自動避障方法，用于提高多智能體在避障任務中的效果。通過智能體之間的協作和信息共享，利用布谷鳥搜索算法進行路徑搜索和優化，實現了高效的避障策略。這種方法為多智能體系統在復雜環境中的避障任務提供了有效解決方案。

針對多智能體編隊飛行問題,提出一種新的基于對偶分解的分布式算法,以實現協同航跡規劃。這種算法只需相鄰智能體間的通信，在智能體與外界信息受到阻礙的情況下使用這種算法也能很好地保持原有編隊飛行。

l  人工勢場算法：

人工勢場算法利用虛擬的勢場來引導車輛移動和形成編隊。每個車輛感知周圍障礙物和其他車輛，并根據勢場的梯度調整自身運動，以實現編隊的穩定和收斂。

提出了一種新的人工勢場方法，用于實現智能體之間的隊形控制，并滿足期望的距離和方位角。通過設計合適的勢場函數，可以在多智能體系統中引導智能體在給定的隊形中運動。該方法考慮了智能體之間的相互作用，并根據期望的距離和方位角設置合適的勢場梯度，使得智能體能夠自主調整位置和姿態，以達到預期的隊形目標。

通過引入這種人工勢場方法，研究者成功地實現了智能體之間的協同運動和隊形控制，為多智能體系統的協調行為提供了一種有效的解決方案。針對動態環境中多智能體編隊避障問題,提出了一種基于人工勢場法與布谷鳥搜索算法相結合的編隊避障方法。

l  模型預測控制算法：

模型預測控制算法依據小車的自身的運動學模型來預測車輛的未來的位姿與速度信息，然后采取預先設定的控制策略來實現編隊目標。為研究基于模型預測原理的路徑跟蹤控制器,建立了三自由度車輛動力學模型。

基于模型預測控制算法設計了智能車輛橫向運動控制器.這些編隊控制算法可根據具體的應用場景和要求進行選擇和調整。它們旨在實現車輛之間的協同操作，提高編隊的運動效率、安全性和魯棒性。