路徑規(guī)劃算法研究

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

l  Dijkstra 算法：

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

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

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

l  A*算法：

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

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

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

l  D*算法：

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

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

l  模擬退火算法：

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

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

l  遺傳算法：

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

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

l  蟻群算法：

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

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

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

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

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

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

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

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

l  Bug 算法：

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

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

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

l  向量勢(shì)直方圖法：

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

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

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

動(dòng)態(tài)窗口法的基本思想是對(duì)當(dāng)前的小車(chē)計(jì)算下一時(shí)刻可能的速度空間，對(duì)速度空間中的每一組速度進(jìn)行軌跡預(yù)測(cè)，通過(guò)當(dāng)前速度和預(yù)測(cè)的軌跡點(diǎn)對(duì)速度進(jìn)行評(píng)估，在速度空間中選取評(píng)價(jià)最 高的速度作為下一時(shí)刻的速度。

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

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

l  人工勢(shì)場(chǎng)法：

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

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

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

智能體編隊(duì)控制算法

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

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

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

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

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

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

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

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

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

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

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

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

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

l  人工勢(shì)場(chǎng)算法：

人工勢(shì)場(chǎng)算法利用虛擬的勢(shì)場(chǎng)來(lái)引導(dǎo)車(chē)輛移動(dòng)和形成編隊(duì)。每個(gè)車(chē)輛感知周?chē)系K物和其他車(chē)輛，并根據(jù)勢(shì)場(chǎng)的梯度調(diào)整自身運(yùn)動(dòng)，以實(shí)現(xiàn)編隊(duì)的穩(wěn)定和收斂。

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

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

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

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

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