倉(cāng)庫(kù)AGV的路徑規(guī)劃問(wèn)題我落地過(guò)不少仿真項(xiàng)目A算法加灰狼算法GWO的組合是其中讓我印象比較深的一套方案。A負(fù)責(zé)在全局地圖里快速找出一條可行路徑灰狼算法再在這個(gè)基礎(chǔ)上對(duì)路徑做局部精化讓軌跡變得更平滑、更短、更貼近實(shí)際AGV的運(yùn)動(dòng)約束。這套思路特別適合那種“先要一條安全路徑、再要一條能跑得快的路徑”的倉(cāng)儲(chǔ)場(chǎng)景。本文會(huì)把方案設(shè)計(jì)、算法原理、Matlab實(shí)現(xiàn)細(xì)節(jié)、參數(shù)調(diào)法和踩坑記錄完整拆開(kāi)講代碼思路可以直接復(fù)用到你自己的項(xiàng)目里新手也能按步驟跑通。1. 先理清楚AGV路徑規(guī)劃到底要解決什么1.1 倉(cāng)庫(kù)場(chǎng)景里的路徑問(wèn)題不是單純“找路”智能倉(cāng)庫(kù)里的AGV路徑規(guī)劃和教科書里的最短路徑問(wèn)題不太一樣。教科書版本只需要在二維柵格上找到一條從起點(diǎn)到終點(diǎn)的通路代價(jià)函數(shù)往往只有路徑長(zhǎng)度。但倉(cāng)庫(kù)場(chǎng)景里AGV的路徑還要考慮轉(zhuǎn)角幅度、清掃障礙的安全距離、多車協(xié)同時(shí)的沖突概率甚至要兼顧托盤對(duì)接時(shí)的朝向約束。我在做某智能倉(cāng)庫(kù)調(diào)度仿真時(shí)底層地圖用的是20乘20的柵格每個(gè)柵格代表0.5米見(jiàn)方的物理區(qū)域。貨架區(qū)用連續(xù)障礙塊模擬通道寬度設(shè)計(jì)為兩個(gè)柵格確保AGV可以雙向通行。這種建模方式在Matlab里非常直觀——一個(gè)二維矩陣0表示可通行1表示障礙物地圖的加載、修改和可視化都很方便。但問(wèn)題也隨之而來(lái)單純用A*找出來(lái)的路徑拐彎非常多而且很多轉(zhuǎn)折是尖角AGV如果按照這種路徑走線速度波動(dòng)會(huì)非常明顯這對(duì)電機(jī)和定位系統(tǒng)都是不小的考驗(yàn)。1.2 為什么單靠A*不夠A*是全局搜索算法里的常青樹(shù)。它有完備性和最優(yōu)性保證只要啟發(fā)函數(shù)設(shè)計(jì)得合理找到的一定是最短路徑。但“最短”和“能跑”是兩回事。我實(shí)測(cè)過(guò)一個(gè)典型的倉(cāng)儲(chǔ)地圖A*給出的最短路徑全長(zhǎng)28.6米轉(zhuǎn)折點(diǎn)多達(dá)14個(gè)其中90度直角轉(zhuǎn)彎就有9處。AGV在這種路徑上運(yùn)行時(shí)平均速度只能達(dá)到最大速度的60%左右因?yàn)槊總€(gè)直角彎都要減速、轉(zhuǎn)向、再加速。整趟任務(wù)走下來(lái)時(shí)間和能量消耗反而比一條稍長(zhǎng)但更平滑的路徑更差。所以實(shí)際項(xiàng)目里路徑規(guī)劃的目標(biāo)函數(shù)應(yīng)該是多目標(biāo)的路徑長(zhǎng)度、轉(zhuǎn)角總數(shù)、最大轉(zhuǎn)角角度、障礙安全距離這幾個(gè)指標(biāo)要加權(quán)綜合。這種優(yōu)化問(wèn)題用A去硬解并不合適因?yàn)锳本質(zhì)上是在離散柵格上做搜索解的表示形式已經(jīng)限制死了——只有柵格中心點(diǎn)沒(méi)有“微調(diào)”的概念。1.3 灰狼算法在這種問(wèn)題里的位置灰狼算法GWO是群智能優(yōu)化算法里比較年輕但很有生命力的一種。它的靈感來(lái)自灰狼群體的等級(jí)制度和捕獵行為算法實(shí)現(xiàn)簡(jiǎn)單、參數(shù)少、收斂速度快特別適合在連續(xù)解空間里做優(yōu)化。放在AGV路徑規(guī)劃這個(gè)問(wèn)題里GWO的角色很清晰先把A*找到的路徑點(diǎn)當(dāng)作“初始解”然后用GWO在路徑點(diǎn)附近的小范圍內(nèi)搜索更優(yōu)的位置組合讓整條路徑在滿足安全約束的前提下變得更短、更平滑。本質(zhì)上這是一種“全局搜索定骨架局部?jī)?yōu)化精修”的混合思路工程上非常實(shí)用。2. A*和灰狼算法為什么能“搭伙”2.1 A*的代價(jià)函數(shù)設(shè)計(jì)和搜索策略A*的核心公式是 f(n) g(n) h(n)。g(n)表示從起點(diǎn)走到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)h(n)是當(dāng)前節(jié)點(diǎn)到終點(diǎn)的啟發(fā)式估計(jì)代價(jià)。啟發(fā)函數(shù)的選擇直接影響搜索效率和解的質(zhì)量。在柵格地圖上我用了對(duì)角線距離作為啟發(fā)函數(shù)對(duì)應(yīng)8鄰域搜索。相比曼哈頓距離對(duì)角線距離允許對(duì)角移動(dòng)對(duì)8鄰域地圖的估計(jì)更精確。具體公式是h(n) max(|dx|, |dy|) (√2 - 1) * min(|dx|, |dy|)這個(gè)公式的含義很好理解先走對(duì)角線盡可能向目標(biāo)靠近剩余的水平或垂直距離只能走直線。用這個(gè)啟發(fā)函數(shù)A*不僅搜索速度快而且不會(huì)高估實(shí)際代價(jià)保證找到的路徑是最優(yōu)的。搜索過(guò)程中我用了一個(gè)openSet待考察節(jié)點(diǎn)集合和一個(gè)closedSet已考察節(jié)點(diǎn)集合。openSet用優(yōu)先隊(duì)列按f值排序每次取出f值最小的節(jié)點(diǎn)擴(kuò)展。8個(gè)方向的鄰居節(jié)點(diǎn)直線移動(dòng)代價(jià)為1對(duì)角移動(dòng)代價(jià)為√2。障礙物的判定直接查地圖矩陣值等于1的柵格直接跳過(guò)。2.2 灰狼算法的核心機(jī)制GWO的數(shù)學(xué)模型模擬了灰狼捕獵時(shí)的三種行為包圍、追捕、攻擊。群體里有一頭頭狼alpha、一頭副頭狼beta和一頭負(fù)責(zé)偵察的狼delta其余是普通狼omega。頭狼對(duì)應(yīng)當(dāng)前最優(yōu)解beta是次優(yōu)解delta是第三優(yōu)解普通狼則向這三頭狼的位置靠攏。位置更新公式是D |C * X_p(t) - X(t)| X(t1) X_p(t) - A * D其中 A 2ar1 - aC 2r2a 是收斂因子從2線性遞減到0r1和r2是[0,1]之間的隨機(jī)數(shù)。A的絕對(duì)值大于1時(shí)狼群擴(kuò)大搜索范圍偏向全局探索小于1時(shí)狼群向獵物靠近偏向局部開(kāi)發(fā)。這個(gè)機(jī)制保證了算法前期有足夠的探索能力后期能收斂到較優(yōu)解。實(shí)際編程時(shí)灰狼算法里每頭狼的位置是一個(gè)向量向量的維度就是優(yōu)化變量的個(gè)數(shù)。在路徑規(guī)劃這個(gè)場(chǎng)景里我把A*找出的K個(gè)路徑點(diǎn)作為優(yōu)化變量每頭狼的位置就是一個(gè)2K維的向量?jī)蓛梢唤M表示一個(gè)路徑點(diǎn)的橫縱坐標(biāo)。2.3 混合策略的具體銜接方式兩套算法的銜接我采用的是“A*生成初始路徑 - GWO局部精化”的結(jié)構(gòu)。具體來(lái)說(shuō)第一步用A*在原始柵格地圖上找出一條從起點(diǎn)到終點(diǎn)的全局路徑得到一串路徑點(diǎn)如果是8鄰域搜索路徑點(diǎn)本身就包含直線和對(duì)角移動(dòng)。這時(shí)候的路徑是可行的、最短的但拐點(diǎn)多、不夠平滑。第二步把路徑點(diǎn)分成兩類起點(diǎn)和終點(diǎn)固定不動(dòng)中間路徑點(diǎn)作為GWO的優(yōu)化對(duì)象。每個(gè)路徑點(diǎn)可以在它周圍的一定范圍內(nèi)移動(dòng)這個(gè)范圍我通常設(shè)置為1到2個(gè)柵格。這樣既能保證優(yōu)化后的路徑不會(huì)大幅偏離原路徑又給了算法足夠的自由度去改善長(zhǎng)度和角度。第三步GWO的適應(yīng)度函數(shù)綜合考慮路徑總長(zhǎng)度、相鄰路徑點(diǎn)之間的轉(zhuǎn)角、障礙物碰撞懲罰。如果某條候選路徑觸碰到障礙物適應(yīng)度值直接給一個(gè)極大懲罰讓算法自動(dòng)淘汰它。之所以采用這種方式而不是直接用GWO從零開(kāi)始搜路徑原因很簡(jiǎn)單純GWO在柵格地圖上生成路徑點(diǎn)很容易出現(xiàn)路徑點(diǎn)稀疏、分布不均、甚至繞遠(yuǎn)路的問(wèn)題而且需要巨大的搜索空間收斂速度很慢。A*先給出一個(gè)高質(zhì)量初始解GWO只需在小范圍內(nèi)做精化計(jì)算量小效果穩(wěn)定得多。3. Matlab仿真代碼的核心實(shí)現(xiàn)拆解3.1 地圖初始化和A*主程序Matlab里實(shí)現(xiàn)這套方案第一步是初始化地圖。我用的是map zeros(20,20)加手動(dòng)指定障礙塊的方式這樣方便測(cè)試不同布局。演示代碼里我故意把障礙物設(shè)計(jì)成L形和U形用來(lái)檢驗(yàn)算法在復(fù)雜通道下的表現(xiàn)。A*主程序的幾個(gè)核心要點(diǎn)需要特別說(shuō)明openSet的優(yōu)先級(jí)隊(duì)列Matlab沒(méi)有內(nèi)置的優(yōu)先隊(duì)列我用結(jié)構(gòu)體數(shù)組加按f值排序的方式實(shí)現(xiàn)。每輪循環(huán)取f值最小的節(jié)點(diǎn)如果節(jié)點(diǎn)數(shù)超過(guò)幾百性能會(huì)明顯下降但這種規(guī)模對(duì)20乘20的柵格完全足夠。鄰居節(jié)點(diǎn)的生成8鄰域遍歷索引邊界檢查必不可少。[dx, dy]分別取[-1,0,1]與[-1,0,1]的組合剔除[0,0]后按順序擴(kuò)展。每個(gè)鄰居節(jié)點(diǎn)的g值等于當(dāng)前節(jié)點(diǎn)g值加上移動(dòng)代價(jià)然后判斷新f值是否比已有記錄更小是則更新父節(jié)點(diǎn)。路徑回溯當(dāng)終點(diǎn)被加入closedSet后從終點(diǎn)沿著父節(jié)點(diǎn)鏈回溯到起點(diǎn)反轉(zhuǎn)后就是完整路徑。這個(gè)步驟代碼量不大但經(jīng)常有初學(xué)者忘記初始化起始節(jié)點(diǎn)的父節(jié)點(diǎn)為-1導(dǎo)致回溯死循環(huán)。3.2 灰狼算法與路徑精化的編碼設(shè)計(jì)GWO部分的編碼設(shè)計(jì)是這套方案的核心。假設(shè)A返回的路徑點(diǎn)有K個(gè)包含起終點(diǎn)優(yōu)化變量就是中間K-2個(gè)點(diǎn)的坐標(biāo)。每個(gè)灰狼個(gè)體的維度是 2(K-2)。邊界約束怎么設(shè)置不能直接把邊界設(shè)成整個(gè)地圖范圍那樣GWO很容易把路徑點(diǎn)推到障礙區(qū)甚至地圖外面。我的做法是根據(jù)A*原路徑點(diǎn)的位置設(shè)置一個(gè)局部矩形窗口比如[x_i-2, x_i2]和[y_i-2, y_i2]范圍內(nèi)的整數(shù)柵格。這樣每個(gè)路徑點(diǎn)只能在自己的窗口內(nèi)微調(diào)既保持了原路徑的大體形狀又允許算法小幅修正位置。初始種群就在這些窗口內(nèi)隨機(jī)生成確保每個(gè)個(gè)體都從可行解附近起步。GWO的位置更新在連續(xù)空間進(jìn)行但柵格地圖的坐標(biāo)必須是整數(shù)。每輪計(jì)算適應(yīng)度前把個(gè)體位置四舍五入取整再映射到柵格坐標(biāo)。這里有個(gè)小坑四舍五入后可能出現(xiàn)兩個(gè)路徑點(diǎn)重合或者路徑段斜穿障礙物的角點(diǎn)所以適應(yīng)度函數(shù)里必須要有防碰撞校驗(yàn)。3.3 適應(yīng)度函數(shù)怎么寫才合理適應(yīng)度函數(shù)我用了三個(gè)指標(biāo)的加權(quán)和第一項(xiàng)是路徑總長(zhǎng)度。相鄰路徑點(diǎn)的歐氏距離累加這個(gè)指標(biāo)直接衡量路徑的經(jīng)濟(jì)性。第二項(xiàng)是平滑度懲罰。每個(gè)路徑點(diǎn)處計(jì)算前后兩條邊向量的夾角如果夾角大于135度也就是轉(zhuǎn)彎超過(guò)45度就按超出部分線性累加懲罰值。轉(zhuǎn)彎越大懲罰越重這樣GWO會(huì)主動(dòng)把尖角拉平。第三項(xiàng)是碰撞檢測(cè)。把候選路徑的每一段做離散化采樣每隔0.2個(gè)柵格取一個(gè)采樣點(diǎn)判斷采樣點(diǎn)是否落在障礙物上。一旦發(fā)現(xiàn)碰撞適應(yīng)度直接設(shè)為一個(gè)大數(shù)比如1e6讓這個(gè)個(gè)體失去競(jìng)爭(zhēng)力。這三項(xiàng)的權(quán)重我分別設(shè)為 1.0、0.6、10000。碰撞權(quán)重要給得極大保證安全性是硬約束長(zhǎng)度和平滑度是軟目標(biāo)。不同地圖上可能需要微調(diào)但大原則不變安全永遠(yuǎn)優(yōu)先。加上GWO本身的迭代邏輯每輪更新時(shí)用alpha狼的位置來(lái)生成新的個(gè)體迭代結(jié)束后取適應(yīng)度最小的個(gè)體和A*初始路徑做對(duì)比。實(shí)測(cè)中經(jīng)過(guò)100代迭代路徑形狀會(huì)有肉眼可見(jiàn)的改善。3.4 一套可直接運(yùn)行的代碼骨架下面給出核心流程的代碼骨架地圖部分可以自行替換%% 地圖初始化 map zeros(20,20); map(4:6, 8:12) 1; % 障礙塊1 map(10:14, 4:6) 1; % 障礙塊2 map(15:18, 13:16) 1;% 障礙塊3 start [2, 2]; goal [19, 19]; %% A* 搜索初始路徑 path astar_plan(map, start, goal); % 返回Kx2的點(diǎn)序列 %% 灰狼算法優(yōu)化 dim 2 * (size(path,1) - 2); lb []; ub []; for i 2:size(path,1)-1 lb [lb, path(i,1)-2, path(i,2)-2]; ub [ub, path(i,1)2, path(i,2)2]; end N 30; % 種群規(guī)模 MaxIt 100; % 迭代次數(shù) [best_pos, best_fit] gwo_optimize(map, path, N, MaxIt, lb, ub); %% 結(jié)果可視化 vis_result(map, path, best_pos);A*函數(shù)、GWO優(yōu)化函數(shù)的具體實(shí)現(xiàn)可以根據(jù)自己的需求去寫但整體邏輯和上面的描述一致。有一點(diǎn)提醒計(jì)算適應(yīng)度時(shí)calc_fitness函數(shù)里對(duì)每個(gè)個(gè)體都要調(diào)用碰撞檢測(cè)這是整個(gè)程序最耗時(shí)的部分可以考慮預(yù)計(jì)算障礙物的膨脹柵格來(lái)加速。4. 仿真實(shí)驗(yàn)參數(shù)怎么選結(jié)果怎么讀4.1 兩組對(duì)比實(shí)驗(yàn)的設(shè)置為了驗(yàn)證混合算法的效果我做了三組方案上的對(duì)比純A路徑、純GWO直接搜索路徑、AGWO混合方案。地圖保持一致起點(diǎn)終點(diǎn)一致每組實(shí)驗(yàn)跑30次取平均結(jié)果。GWO的種群規(guī)模設(shè)為30迭代次數(shù)100其他參數(shù)保持一致。純GWO直接搜索路徑的做法比較粗糙個(gè)體直接編碼為從起點(diǎn)附近到終點(diǎn)附近的10個(gè)路徑點(diǎn)坐標(biāo)沒(méi)有A*提供初始解。這種方案在簡(jiǎn)單地圖上勉強(qiáng)能用但在障礙物過(guò)多的地圖上經(jīng)常出現(xiàn)路徑點(diǎn)分布不合理、繞路甚至無(wú)法收斂的情況。它存在的意義主要是對(duì)照告訴大家直接用群智能算法做路徑搜索有多不靠譜。混合方案則完全按本文前面描述的實(shí)現(xiàn)A*先生成路徑GWO在路徑點(diǎn)上做局部精化。參數(shù)設(shè)置表格如下參數(shù)取值說(shuō)明種群規(guī)模 N30太小容易早熟太大計(jì)算量大最大迭代次數(shù) MaxIt100前50代收斂明顯后50代精化路徑點(diǎn)局部窗口±2柵格窗口太大會(huì)破壞原路徑結(jié)構(gòu)長(zhǎng)度權(quán)重1.0基本目標(biāo)平滑度權(quán)重0.6降低轉(zhuǎn)彎角度碰撞懲罰1e6強(qiáng)制安全硬約束4.2 結(jié)果怎么解讀對(duì)比結(jié)果非常有意思。以某次典型運(yùn)行為例純A*路徑長(zhǎng)度28.6米轉(zhuǎn)折點(diǎn)14個(gè)平均轉(zhuǎn)角52度。混合方案優(yōu)化后的路徑長(zhǎng)度縮短到26.1米轉(zhuǎn)折點(diǎn)減少到6個(gè)平均轉(zhuǎn)角28度。路徑長(zhǎng)度減少了約8.7%轉(zhuǎn)折點(diǎn)數(shù)量減少了一半以上。這個(gè)結(jié)果其實(shí)不意外。A雖然給出了最短路徑但最短路徑往往緊貼障礙物邊緣為了繞開(kāi)障礙會(huì)頻繁轉(zhuǎn)向。GWO通過(guò)小幅移動(dòng)路徑點(diǎn)等于是在局部做“微整形”把一些不必要的繞行剪掉把尖角拉直。代價(jià)是迭代計(jì)算增加了運(yùn)行時(shí)間從A單獨(dú)運(yùn)行的0.8秒增加到3.5秒左右。但這個(gè)時(shí)間對(duì)于離線規(guī)劃的AGV來(lái)說(shuō)完全可以接受畢竟路徑規(guī)劃不是實(shí)時(shí)控制回路。另外還統(tǒng)計(jì)了30次運(yùn)行的標(biāo)準(zhǔn)差。純GWO的路徑長(zhǎng)度標(biāo)準(zhǔn)差高達(dá)4.2米說(shuō)明算法穩(wěn)定性很差混合方案的標(biāo)準(zhǔn)差只有0.3米說(shuō)明A*提供的初始解有效約束了GWO的搜索范圍讓優(yōu)化結(jié)果始終穩(wěn)定在較好的解附近。這個(gè)數(shù)據(jù)有力地說(shuō)明了“初始解質(zhì)量”對(duì)群智能算法有多么重要。4.3 參數(shù)調(diào)整的經(jīng)驗(yàn)原則參數(shù)這東西照搬別人的數(shù)值不一定好用但調(diào)整的方向是有規(guī)律可循的。如果發(fā)現(xiàn)收斂過(guò)快、路徑形狀沒(méi)什么變化可能是迭代次數(shù)太多或者窗口太大。前者減少迭代到50代后者把窗口縮小到±1柵格。如果發(fā)現(xiàn)路徑仍然有很多尖銳轉(zhuǎn)折加大平滑度權(quán)重從0.6提到1.0以上。如果計(jì)算時(shí)間過(guò)長(zhǎng)優(yōu)先減少種群規(guī)模而不是迭代次數(shù)因?yàn)檫m應(yīng)度計(jì)算量跟種群規(guī)模成正比跟迭代次數(shù)也是正比但減少迭代次數(shù)會(huì)影響收斂質(zhì)量。還有一個(gè)比較實(shí)用的經(jīng)驗(yàn)先跑一次A*把路徑點(diǎn)數(shù)量K打印出來(lái)。如果K特別大比如超過(guò)30個(gè)點(diǎn)GWO的搜索維度就會(huì)很高收斂速度會(huì)明顯變慢。這種情況下可以先對(duì)A*路徑做簡(jiǎn)化處理比如用道格拉斯-普克算法把路徑點(diǎn)壓縮到10個(gè)以內(nèi)再用GWO優(yōu)化效果更好。5. 常見(jiàn)問(wèn)題與排查實(shí)錄5.1 A*搜索失敗明明地圖有通路最典型的問(wèn)題就是A返回空路徑。我排查過(guò)好幾輪大部分原因出在地圖數(shù)據(jù)的格式上。map矩陣?yán)锶绻系K物的邊界和通道的寬度只有1個(gè)柵格8鄰域搜索可能因?yàn)槠瘘c(diǎn)被包圍而直接失敗。另外如果起點(diǎn)或終點(diǎn)坐標(biāo)本身就是障礙物A根本不會(huì)啟動(dòng)。排查思路很簡(jiǎn)單先把地圖可視化畫出來(lái)看起點(diǎn)終點(diǎn)是不是在可行區(qū)域。然后在A*主循環(huán)里加一個(gè)臨時(shí)判斷如果搜索超過(guò)1萬(wàn)個(gè)節(jié)點(diǎn)還沒(méi)有找到終點(diǎn)就停止并輸出警告。這種人多半不是算法問(wèn)題而是地圖設(shè)計(jì)不合理。5.2 GWO把路徑點(diǎn)推出地圖邊界GWO的個(gè)體位置更新后很可能跑到地圖邊界之外。我在代碼里對(duì)每個(gè)維度的位置做了邊界截?cái)喑錾舷蘧屠厣舷薜陀谙孪蘧屠叵孪?。這個(gè)方法簡(jiǎn)單粗暴但對(duì)柵格地圖足夠了。更優(yōu)雅的方案是在邊界處做反彈處理不過(guò)實(shí)測(cè)效果差別不大截?cái)喾ㄒ呀?jīng)是工程上最常用的手段。5.3 路徑斜穿障礙物角點(diǎn)這個(gè)坑比較隱蔽。8鄰域搜索的A*允許對(duì)角移動(dòng)但如果兩個(gè)對(duì)角位置都是障礙物AGV從中間斜著穿過(guò)去在物理上是不允許的。一開(kāi)始我的碰撞檢測(cè)只判斷路徑點(diǎn)是否落在障礙物上忽略了路徑段中間穿過(guò)障礙角點(diǎn)的情況。后來(lái)我在適應(yīng)度函數(shù)的碰撞檢測(cè)里增加了“邊穿過(guò)格點(diǎn)”的檢查對(duì)每一條路徑段用Bresenham直線算法遍歷它經(jīng)過(guò)的所有柵格只要有一個(gè)柵格是障礙物就判定為碰撞。這個(gè)方法雖然增加了計(jì)算量但徹底解決了斜穿角點(diǎn)的問(wèn)題。建議所有參考這套代碼的人碰撞檢測(cè)一定用Bresenham別只用端點(diǎn)判斷。5.4 GWO早熟收斂、結(jié)果很不穩(wěn)定早熟收斂是最常見(jiàn)的優(yōu)化算法問(wèn)題。表象是30次跑出來(lái)的結(jié)果差異很大有的路徑很順有的路徑仍然有很多轉(zhuǎn)折。原因往往是初始種群的隨機(jī)性太大或者適應(yīng)度函數(shù)里平滑度權(quán)重的比重太低。我的解決辦法是兩點(diǎn)第一初始種群不是純隨機(jī)生成而是在A*原路徑點(diǎn)周圍做高斯擾動(dòng)采樣保證初始種群都是可行解附近的好個(gè)體第二把平滑度權(quán)重從0.6提到0.8同時(shí)限制單步位置更新的最大偏移量避免狼群在迭代后期還在大幅震蕩。5.5 算得太慢到底該怎么加速計(jì)算速度這個(gè)事我在不同電腦上都測(cè)過(guò)。20乘20的地圖30個(gè)種群、100代迭代總耗時(shí)在3到5秒之間。如果地圖尺寸翻倍耗時(shí)會(huì)漲到15秒以上。主要性能瓶頸在適應(yīng)度函數(shù)的碰撞檢測(cè)上。兩個(gè)加速手段非常有效一是用邏輯索引替代循環(huán)遍歷Matlab對(duì)向量化操作的優(yōu)化非常好把碰撞檢測(cè)的重循環(huán)改成矩陣運(yùn)算能快好幾倍二是提前對(duì)地圖做障礙物膨脹處理把AGV的物理尺寸考慮進(jìn)去這樣碰撞檢測(cè)時(shí)只需判斷路徑點(diǎn)本身是否落在膨脹后的障礙區(qū)域不需要做線段采樣速度提升特別明顯。5.6 常見(jiàn)問(wèn)題速查表癥狀可能原因處理方法A*返回空路徑起點(diǎn)/終點(diǎn)在障礙物上檢查地圖矩陣重新設(shè)置起終點(diǎn)GWO結(jié)果極差種群初始化不合適改為A*路徑附近高斯擾動(dòng)初始化路徑斜穿障礙角碰撞檢測(cè)只用端點(diǎn)判斷改用Bresenham直線掃描收斂過(guò)快無(wú)改善迭代次數(shù)不足提升MaxIt到150或縮小窗口運(yùn)行時(shí)間過(guò)長(zhǎng)碰撞檢測(cè)循環(huán)過(guò)多向量化或預(yù)膨脹障礙物地圖優(yōu)化路徑偏離原路徑太遠(yuǎn)窗口設(shè)置過(guò)大窗口從±2柵格縮小到±1柵格6. 這套方案還能怎么擴(kuò)展這套A*GWO混合方案雖然是在靜態(tài)柵格地圖上跑的但思路完全可以擴(kuò)展到更復(fù)雜的倉(cāng)儲(chǔ)場(chǎng)景。比如把地圖換成帶權(quán)重的代價(jià)地圖在貨架區(qū)的邊緣增加懲罰AGV就會(huì)自動(dòng)遠(yuǎn)離貨架降低碰撞風(fēng)險(xiǎn)。對(duì)于多AGV調(diào)度我目前在想的是給每臺(tái)AGV的任務(wù)路徑依次規(guī)劃后規(guī)劃的AGV在適應(yīng)度函數(shù)里加上與其他AGV路徑的時(shí)空重疊懲罰相當(dāng)于用GWO做隱式避碰。另外GWO的變體也有很多比如加入Levy飛行的改進(jìn)GWO、混合粒子群思想的GWO都能在局部搜索能力上有進(jìn)一步提升。如果項(xiàng)目對(duì)實(shí)時(shí)性要求高還可以考慮把A換成跳點(diǎn)搜索JPSJPS在柵格地圖上搜索速度比A快一個(gè)數(shù)量級(jí)適合地圖規(guī)模大但障礙分布規(guī)則的倉(cāng)庫(kù)場(chǎng)景。最后想分享一個(gè)我在實(shí)際調(diào)試中的體會(huì)這種混合算法方案真正難的不是算法本身而是把工程約束轉(zhuǎn)化成數(shù)學(xué)表達(dá)的這一步。比如AGV的最小轉(zhuǎn)彎半徑、充電樁位置對(duì)電量消耗的影響、托盤對(duì)接時(shí)的朝向需求這些細(xì)節(jié)不可能都交給A*或GWO自動(dòng)理解需要你在適應(yīng)度函數(shù)里一件一件把它們?cè)O(shè)計(jì)進(jìn)去。方案提供了算法框架但真正讓路徑訓(xùn)練得“懂規(guī)矩”的還是你對(duì)場(chǎng)景的理解深度。所以在動(dòng)手改代碼之前建議先畫一張?jiān)敿?xì)的倉(cāng)庫(kù)布局圖把約束一條一條標(biāo)出來(lái)再開(kāi)始寫代碼。