??最近幫同學做個東西，但是問題在于是之前從沒接觸過的領域–移動機器人軌跡規(guī)劃，雖然也是搞機器人的，但是對 AGV 那邊的情況是一無所知，這次能完成也算是挑戰(zhàn)成功。此次任務目的是多輛AGV小車搬運貨物，保證搬運總時間最短并且小車與貨物之間，小車與小車之間無碰撞。

0 引言

??單 AGV 的路徑規(guī)劃是基礎，單 AGV 的路徑規(guī)劃是指在已知起點和終點，所在環(huán)境地圖存在多個貨物的情況下，為存取貨物的 AGV 規(guī)劃一條符合要求的高效且最優(yōu)路徑。所以需要研究的問題有兩個：AGV 運行環(huán)境建模和 AGV 路徑規(guī)劃算法。
??而在實際應用中，因為單臺 AGV 運輸量有限，不能滿足多任務高效的運輸任務。所以在大多數(shù)倉庫中，多 AGV 運輸是必不可少的。AGVS 系統(tǒng)調度可以概括為：在一個倉庫中，有多個貨物放在不同起始位置，需要使用多個 AGV 將這些貨物運輸?shù)讲煌哪繕宋恢?，并使得整體運輸效率保持較高水平。多 AGV 調度系統(tǒng)在運行過程中需要解決的問題：AGVS 的路徑規(guī)劃、多任務的分配、動態(tài)的調度規(guī)劃。

1 地圖環(huán)境建模

??采用柵格地圖法作為 AGV 的運行環(huán)境，其原理是建立一個二維數(shù)組，用不同的數(shù)值代表不同的含義，基于任務要求，建立好后的柵格地圖如下：

??多AGV運行環(huán)境圖包括出發(fā)區(qū)、充電區(qū)、監(jiān)測區(qū)、貨物A的兩個生產(chǎn)區(qū)、貨物B的三個生產(chǎn)區(qū)、貨物A的兩個入庫點，貨物B的兩個入庫點。貨物的顏色代表了對應顏色的小車需要完成的任務，本文的研究場景為：多 AGV 在接收到搬運任務后，會按照規(guī)劃好的最優(yōu)揀選路徑從當前位置出發(fā)，前往貨物點取貨物，再送到對應的出貨站臺，然后前往下一個貨物點取貨物，再去對應的出貨站臺，在執(zhí)行完所有搬運任務后，返回初始位置。

2 AGVS的路徑規(guī)劃算法

??A*算法是一種全局規(guī)劃算法，可以根據(jù)給定的起點和目標點的位置在全局的地圖上規(guī)劃出一條最優(yōu)路徑。A*算法是將地圖虛擬化，劃分成一個個小方塊，從起點開始搜索周圍的點，然后選出一個新的點作為起點進行搜索，重復進行該過程直到找到終點。其優(yōu)點是能夠實現(xiàn)靜態(tài)環(huán)境中的最優(yōu)路徑搜索，由于評價函數(shù)的存在，可以減少對邊緣節(jié)點的搜索，因此選用A*算法作為路徑規(guī)劃的算法。
??傳統(tǒng)的 A*算法主要將總長度最短作為優(yōu)化目標。但一味的追求長度最短，將會導致 AGV 在行駛過程中頻繁的轉向，由于轉彎會進行加速和減速的過程，時間成本要比直線行駛高出許多，而且使整體路徑不夠平滑。針對此問題，其中一個改進策略是在原有的 A*算法啟發(fā)函數(shù)上增加轉彎代價，以減少一些不必要的轉彎。改進后的 A*算法為
$$f\left(n\right)=g\left(n\right)+h\left(n\right)+k$$式中，$h\left(n\right)$ 是啟發(fā)函數(shù)，采用曼哈頓距離，$k$ 是轉彎代價。

3 動態(tài)的調度規(guī)劃

??對于單 AGV 搬運來說，只用 A*算法能夠滿足任務要求，但當多個 AGV 在系統(tǒng)內(nèi)同時運行時，如果只按照單車搬運路徑規(guī)劃算法對每個 AGV 的揀選路徑進行規(guī)劃，而沒有考慮多個 AGV 之間的相互影響，則可能出現(xiàn)幾臺 AGV 之間發(fā)生沖突和死鎖的現(xiàn)象，基于此，提出一種時間窗算法來解決此類問題。
??時間窗原理是 AGV 在通過某個節(jié)點或者某段路徑時的時間段，根據(jù)節(jié)點或路徑被 AGV 的占用情況來協(xié)調 AGV 的路徑規(guī)劃情況，合理安排 AGV 的行走路徑和通過各節(jié)點或路徑的時間點，后一個 AGV 的路徑規(guī)劃建立在前面已經(jīng)規(guī)劃好路徑的 AGV 的時間窗基礎上，從而避免小車之間發(fā)生沖突。
??此時需要對 AGV 運作情況做一些假設：

??基于以上假設，可以得到小車在經(jīng)過每個節(jié)點時的路徑信息與時間信息，從而進行時間窗規(guī)劃，避免小車沖突。

3.1 對于小車沖突類型的解決方式

??小車之間的沖突類型主要包括：節(jié)點沖突（十字沖突）、相向節(jié)點沖突、相向沖突三種

對應的沖突解決方式定義如下：

注： 在判斷小車是需要水平避障還是垂直避障的時候，還需要在沖突點進行判斷是否發(fā)生過轉彎。

4 多任務的分配 - JADE算法

??排好順序的任務合理的分配叫做多任務分配。通常來說，完成多任務分配的功能，首先需要明確任務分配的目標，可以使用 AGV 行駛最短路程作為單一指標，也可以使用 AGV 執(zhí)行任務時間最少和距離最短等多重目標作為指標。這里采用任務總時間 $T$ 作為指標。
??在以上的尋優(yōu)算法中進行考慮，由于LBPADE算法適用于多維函數(shù)，先排除。將其他三個函數(shù)在相同條件下進行測試，發(fā)現(xiàn)算法精度：MGDE>=JADE>RNODE. 由于一些原因，這里先采用JADE算法。
??JADE算法是一種優(yōu)化算法，是DE算法的改進。JADE是通過使用可選的外部歸檔實施新的變異策略，外部歸檔利用歷史數(shù)據(jù)提供進度方向信息。并以自適應方式更新控制參數(shù) F,Cr 來提高優(yōu)化性能，JADE與DE相似的地方不再贅述（初始化，交叉，選擇），JADE只改變了變異階段，另外還將F和Cr參數(shù)自適應了。
帶外部存檔的變異策略：DE/current-to-pbest with external archive：

上式中，${\tilde{\mathbf{x}}}_{r2,g}$ 表示選取自當前群體和外部歸檔的∪集中，即有一部分個體是從外部歸檔中選擇的，外部歸檔與此時此刻的群體不相似，擴大了群體的多樣性，避免陷入局部最優(yōu)。歸檔操作非常簡單，歸檔文件初始化為空。然后，在每代之后，將選擇過程中失敗的父解添加到存檔中。如果歸檔大小超過某個閾值，則從歸檔中隨機刪除一些解決方案以使歸檔大小保持在某個值。
??然后對交叉因子 $CR$ 和變異因子 $F$ 進行參數(shù)自適應，$CR$ 采用平均值策略，$F$ 采用 Lehmer 均值策略，此處不細說。

5 仿真結果與分析

運行效果如下：

由仿真結果可以看出，本次仿真達到了研究目的，仿真實驗成功。

??JADE迭代曲線如下，種群規(guī)模50，在迭代至6次左右進入收斂狀態(tài)，找到了最佳任務分配方案與最小花費時間值。

總結

??本文以多 AGV 為研究對象，研究了多 AGV 在搬運作業(yè)中的路徑規(guī)劃問題，利用A*算法實現(xiàn)了多 AGV 的最短路徑規(guī)劃，同時引入時間窗算法，使得多 AGV 系統(tǒng)的沖突問題得以解決，最后利用優(yōu)化算法JADE，對路徑規(guī)劃總時間進行尋優(yōu)迭代，找到了最佳分配方案與最小花費時間，實現(xiàn)了多 AGV 系統(tǒng)的全局無沖突路徑規(guī)劃。

??通過此次學習，學到了路徑規(guī)劃算法A*找最短路徑，時間窗算法避免小車沖突，優(yōu)化算法迭代尋優(yōu)（JADE、RNODE、LBPADE、MGDE），此次學習收獲頗豐，感謝陳同學提供的機會同時也感謝自己。文章來源地址http://www.zghlxwxcb.cn/news/detail-687498.html

到了這里，關于【移動機器人】基于JADE改進差分算法的多AGV路徑規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！