全局路徑規(guī)劃算法

l  Dijkstra 算法：

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

Dijkstra 算法的優(yōu)點是能夠找到最短路徑，適用于無負(fù)權(quán)邊的圖；缺點是時間復(fù)雜度較高，無法處理負(fù)權(quán)邊的情況。

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

l  A*算法：

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

引入了啟發(fā)式函數(shù)的權(quán)重系數(shù)來提高A*算法的搜索效率。最終實現(xiàn)了A*和DWA 算法的融合，使路徑更平滑，提高了算法的避障性能。

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

l  D*算法：

D*算法通過不斷更新路徑的代價和啟發(fā)式估計值來適應(yīng)環(huán)境的變化。D*算法首先從目標(biāo)節(jié)點開始，根據(jù)當(dāng)前的代價和啟發(fā)式估計值選擇最優(yōu)的鄰居節(jié)點，并更新路徑和代價信息。當(dāng)環(huán)境發(fā)生變化時，D*算法會重新評估路徑，并通過局部的增量更新來快速修正路徑。這種增量的更新策略使得D*算法適用于實時的路徑規(guī)劃應(yīng)用。

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

l  模擬退火算法：

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

在人工勢場法中融合模擬退火算法，當(dāng)傳統(tǒng)人工勢場法陷入局部最小值時，通過模擬退火法跳出當(dāng)前局部最小值區(qū)域。

l  遺傳算法：

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

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

l  蟻群算法：

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

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

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

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

l  粒子群優(yōu)化算法：

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

提出了一種基于粒子群優(yōu)化和反應(yīng)避障的編隊控制系統(tǒng)。在領(lǐng)航跟隨法中，通過粒子群優(yōu)化實現(xiàn)領(lǐng)航者軌跡規(guī)劃。領(lǐng)航者軌跡規(guī)劃完成后，并不能保證跟隨者的軌跡不會與障礙物發(fā)生碰撞，因此在編隊控制中加入了跟隨者反應(yīng)避障系統(tǒng)，實現(xiàn)了編隊避障。

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

l  Bug 算法：

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

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

將深度學(xué)習(xí)算法和路徑規(guī)劃技術(shù)相結(jié)合，提出了一種基于深層卷積神經(jīng)網(wǎng)絡(luò)和改進Bug 算法的機器人避障方法。]針對傳統(tǒng)人工勢場算法易陷入局部極值的問題，引入Bug 算法，保證算法的全局性能。

l  向量勢直方圖法：

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

采用向量場直方圖和拓?fù)涞貓D相結(jié)合的方法,實現(xiàn)AGV 的快速部署。

l  動態(tài)窗口法：

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

使用改進后的動態(tài)窗口法實現(xiàn)了阿克曼機器人的局部路徑規(guī)劃。在傳統(tǒng)的編隊保持方案中加入動態(tài)窗口方法使編隊穩(wěn)定地到達目標(biāo)點。

提出了一種新的基于跳點搜索的優(yōu)化A*算法和動態(tài)窗口法的融合算法。

l  人工勢場法：

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

將引力作用閾值引入引力勢場函數(shù)，解決引力過大問題；在斥力勢場函數(shù)中引入目標(biāo)點與移動機器人之間的距離，解決目標(biāo)不可達問題；根據(jù)環(huán)境復(fù)雜度，提出了自適應(yīng)速度調(diào)節(jié)機制；針對局部極小值問題，分別提出了APF-v1 和APF-v2 兩種構(gòu)建虛擬目標(biāo)點的方法，引導(dǎo)移動機器人走出陷阱區(qū)域。

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

智能體編隊控制算法

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

l  領(lǐng)航跟隨者算法：

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

提出了一種基于時延補償?shù)念I(lǐng)航跟隨編隊控制方案。

在領(lǐng)航跟隨編隊控制算法中設(shè)置了動態(tài)的φ值,當(dāng)編隊的領(lǐng)航者改變方向(或者遇到障礙物改變方向)時,φ值即變?yōu)閯討B(tài)的,隨著領(lǐng)航者角速度的變化而變化,從而使跟隨者路徑更加平滑,隊形的保持更加可靠。

提出了一種虛擬結(jié)構(gòu)法和領(lǐng)航跟隨法相結(jié)合的機器人協(xié)同編隊算法。對整體的控制主要實現(xiàn)對領(lǐng)航機器人的控制，而對于該整體內(nèi)部，已知所有領(lǐng)航機器人的位置信息就能得到所有跟隨機器人的目標(biāo)位置，設(shè)計了控制器，控制所有跟隨機器人跟蹤各自的目標(biāo)位置，從而實現(xiàn)多機器人的協(xié)同編隊控制。

l  虛擬結(jié)構(gòu)算法：

虛擬結(jié)構(gòu)算法基于預(yù)定義的幾何結(jié)構(gòu)或模式，使車輛之間保持特定的相對位置和距離。這些算法可以基于幾何約束或相對運動規(guī)則來生成編隊的運動軌跡，以實現(xiàn)編隊的形態(tài)控制。

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

l  分布式協(xié)同算法：

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

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

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

l  人工勢場算法：

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

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

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

l  模型預(yù)測控制算法：

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

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