生產車間多AGV運輸系統能耗優化路徑規劃算法

中圖分類號：U468.2 文獻標志碼：B DOI：10.19710/J.cnki.1003-8817.20250216

Energy Consumption Optimization Path Planning Algorithm for Multi-AGV Transportation Systems in Production Workshops

Xu Jiaxiang， Wang Ning （SchoolofAutomotive Studies，Tongji University，Shanghai201804）

Abstract：To reduce the overall energy consumption of multi-Automated Guided Vehicle （AGV） transportation systems inautomobileproduction workshops，an energy-saving path algorithmfor multi-AGV systems in complex obstacle environments，namedE-CBS，isproposed.Firstof all，anAGV energyconsumption model isestablished， taking intoacountfactorssuchasload，steering，startingandstopping.Then，bymodifyingtheheuristicfunctionand enhancingthe node information structure and the expansion mode，a single AGV path planning algorithm named EEA （204號 is proposed to avoid path entrapment in complex obstacle-distributedareas.Using EEA*as the underlying algorithm， the E-CBS algorithm is constructed by establishing a constraint alocation mechanism thatconsiders dynamic priorities. Finally，multiplesetsof simulation experimentsinrandom scenariosareconducted，and theresultsshow thatthe improved algorithms can reduce the system's energy consumption by 14.02% to 17.16%

Keywords：AGV，Energyconsumptionoptimization，Improved A^* ，Conflict-basedsearch

1前言

目前，自動導引車（AutomatedGuidedVehicle，AGV）已成為智能制造和智慧物流的核心設備。多AGV協同作業成為汽車制造車間、倉儲、港口等復雜場景的主流運輸模式。目前，多AGV路徑規劃研究多以完工時間或運輸距離為優化目標，關于能耗優化的研究較少[2]。當多臺AGV并行運行時，規劃算法不合理會導致路徑沖突，造成AGV頻繁停車等待或多次轉向、掉頭等，增加電機啟停及姿態調整等無效能耗，因此，多AGV路徑規劃算法存在大量能耗優化空間[3]。

目前，針對AGV能耗優化的研究多集中于單AGV節能路徑規劃。張浩杰等4根據四輪差速驅動機器人的運動學約束建立了能耗模型，主要考慮電機能耗而忽略了其他能耗的影響。江磊等[]根據AGV能耗模型更改A*算法的啟發式函數，并通過改進節點搜索算法使路徑單位距離能耗降低的同時提升了求解效率。Zhang等提出了一種基于阿克曼搜索算法的節能路徑規劃方法，通過150張隨機生成的地圖和實車測試，驗證了算法的有效性。

多AGV系統節能路徑規劃可視為多智能體尋路（Multi-AgentPathFinding，MAPF）問題的實例，由于MAPF的狀態空間隨智能體數量的增加呈指數級增長，尋找最優解是一個非確定性多項式時間（NondeterministicPolynomial time，NP）難的問題。Li等8基于能量約束蟻群優化算法實現單機器人能量最優路徑規劃，再結合優先無沖突策略和路徑無沖突策略實現MAPF問題求解。宋栓軍等基于時間窗對多AGV系統環境拓撲圖中的路徑進行判定，并以系統能耗最低為目標構建沖突消解模型，試驗結果表明，該策略可兼顧路徑長度和能耗的優化目標。陳晶晶等在部分連通拓撲圖上使用非支配排序遺傳算法求解初始節能路徑，再利用構建動態優先級策略進行主動避撞。上述研究聚焦結構化地圖的路徑節點求解，忽略了障礙物分布與形狀等幾何細節，難以反映真實生產車間的復雜環境。Sharon等提出一種基于沖突搜索的算法（Conflict-basedSearch，CBS），能夠在復雜環境中查找比聯合 A^* 算法更少的狀態空間，同時滿足全局最優性。后續研究獲得眾多CBS的改進算法，如GCBS[12]及EECBS[13]，代表了MAPF領域的先進水平，但將其應用于能耗優化的研究較少。

針對上述問題，本文以隨機障礙物分布地圖中的多AGV運輸系統為研究對象，建立了多因素影響下的AGV能耗模型，提出了節能A*（Energy-Efficient A^* ，EEA*）算法，并將其應用于CBS算法底層，通過設計考慮載質量、路徑長度及沖突數量的動態優先級沖突消解策略，獲得適用于多AGV系統的節能路徑規劃（CBSConsideringEnergyCon-sumption，E-CBS）算法，最后通過仿真驗證了算法的有效性。

2 問題描述與建模

2.1多AGV系統節能路徑規劃問題定義

多AGV系統節能路徑規劃是指在同一環境中為多臺并行運輸的AGV規劃無沖突的節能路徑，確保所有路徑在時間和空間上不發生沖突，并以系統總體的能量消耗作為優化目標。

2.2環境、路徑、沖突與約束的定義

車間柵格地圖可用二維矩陣表達，其中，每個元素對應1個網格單元的狀態，即：

式中： M 為柵格圖； W 和 H 分別為柵格圖的寬度和高度； m_ij 為第 i 行第 j 列網格的屬性值，其中0代表自由空間，1則代表障礙物。

為便于描述路徑信息，選取地圖左下角作為坐標系原點，使用 m（x，y） 表示 m 網格的 x 坐標與 y 坐標。每臺AGV a_k 都有唯一的起點 s_k∈M 和目標點 g_k∈M AGV的路徑是一組時間序列，表示其在每一個時間步的位置，如AGV a_k 的路徑 π_k= {s_k，p₁，p₂，…，g_k}，p₁，p₂，p₃… 為不同時間步下AGV的空間位置。

當2臺AGV在同一時間步到達同一網格時，將造成頂點沖突， c_v=（a_k，a_l，m，t） 表示 AGVa_k 與AGVa_l 在時間步 Φ_t 同時到達了網格 m 造成沖突。而當2臺AGV在柵格圖的環境中在相鄰的2個網格互換位置則會造成邊沖突， c_e=（a_k，a_l，m，m^′，t） 表示AGVa_k 在時間步 Φ_t 到時間步 （t+1） 之間，從網格 Ω_m 到達相鄰的網格 m^′ ，而 a_l 則從網格 m^′ 到達網格 m 。為求解無沖突的路徑，需為造成沖突的AGV添加路徑約束， ct_v=（a_k，m，t） 表示不允許 a_k 在時間步 Φ_t 到達網格 m ，以 ct_e=（a_k，（m，m^′），t） 表示不允許 a_k 在時間步 χ_t 到時間步 （Ω_t+1） 從網格 m 到達相鄰的網格 m^′ 。

2.3 問題假設

為便于求解問題，研究問題與建模包含如下假設：

a.每臺AGV在離散的網格上移動，每一步可移動到相鄰位置或停留；

b.每臺AGV的載質量不超過限定載荷，且每次僅能搬運1個貨物；

c.AGV能夠持續工作，直到完成指定搬運任務，不存在途中充電的情況；

d.不考慮貨物體積和AGV裝卸貨時間；

e.AGV行駛時車輪不打滑且僅存在直行和轉彎2種運動軌跡，加減速僅發生在直行路段且加速度恒定不變。

2.4AGV能耗模型

結合眾多研究，可將AGV能耗模型劃分為克服地面摩擦力做功的能耗、地面起伏勢能變化的能耗、加速獲得動能的能耗、轉彎調整方向的能耗以及控制器等電子零部件的能耗，其中，由于車間地面較為平坦，勢能能耗可忽略不計。研究選取了輪式驅動AGV模型，其勻速轉彎方式如圖1所示。

圖1輪式驅動AGV轉彎示意

AGV克服地面滾動摩擦力產生的能耗為運動能耗 E_move ，計算如下：

式中 ξ：μ^Δ 為地面滾動摩擦力系數， m 為AGV載質量（含自重）， g 為重力加速度， l_i 為路徑 π 中第 i 個時間步的位移長度。

當AGV直線位移時，位移長度即為網格寬度l_i=d ，當AGV處于轉彎位移時，轉彎半徑 則 ，當AGV等待時，則位移為0。取 n_straight 為直線行駛的時間步次數， n_turn 為轉彎行駛的時間步次數， n_stay 為等待的時間步次數，代人式（2）得：

AGV在轉彎過程中除克服摩擦力做功外，還需轉彎調整方向，此過程產生的能耗為轉向能耗E_um 。令I為AGV的轉動慣量， ω 為平均轉彎角速度，則轉向能耗為：

AGV在運輸過程中遇到臨時障礙或由于路徑沖突而必須等待時，從靜止加速獲得動能產生的能耗為啟動能耗 E_start 。令 v 為AGV的額定速度，n_start 為AGV從靜止狀態到運行狀態的啟動加速次數，則啟動能耗計算可簡化為：

控制器等其他電子零部件產生的能耗為待機能耗，其會在AGV執行搬運任務期間持續產生，令P_s 為平均待機功率 ?n_total 為時間步總數 ?，Δt 為單時間步長，則待機能耗 E_waste 為：

結合式（2）～式（6）可得AGV總能耗 E 為：

式（7）中，滾阻系數、重力加速度等均為常數，則AGV能耗模型是關于載質量（及轉動慣量）、直行次數、轉彎次數、啟停次數、等待次數及時間步總數的函數。

3多AGV系統節能路徑規劃

3.1考慮能耗因素的成本啟發函數

A*算法是一種高效的啟發式搜索算法，廣泛應用于路徑規劃和圖形遍歷。為使 A^* 算法能夠規劃出能耗最優路徑，通過引入能耗因素來調整啟發式函數，引導算法擴展能耗最低的節點[14]。 A^* 算法的成本啟發函數為：

f（n）=g（n）+h（n）

式中： 為從起點 σ_s 到節點 n 的實際成本， h（n） 為節點 n 到目標節點 g 的估計成本。

根據式（6）計算節點實際能耗成本，使用 π^s，n= （s，p₁，p₂，...，n） 表示起點 s 到節點 n 的已規劃的路徑，則節點 n 的實際能耗為：

估計成本函數則采用哈密頓距離進行路徑長度的估算，節點 n（x₁，y₁） 到目標節點 g（x₂，y₂） 的預估路徑長度 S（n） 為：

由于估計成本函數僅用于啟發節點搜索的方向，因此，為簡化計算，忽略了轉彎能耗和啟停能耗，得到估計代價函數為：

h（n）=（P_sΔt+μmgd）S（n）

綜上，能耗優化目標下的改進 A^* 算法的成本啟發函數為：

3.2節能 A^* 算法 {EEA^*

在原始 A^* 算法結構中，計算當前節點 n 的能耗成本啟發函數 f（n） 時，需回溯起點 s 到節點 n 的路徑。為提高計算效率，本文提出一種新的算法流程，即在節點存儲時保存5個信息：當前節點的 f 值 ?g 值、時間步值、父節點坐標及當前節點坐標。

EEA*在進行節點擴展時，根據父節點、當前節點與鄰居節點三者坐標的序列計算能耗增量，再將其與當前節點 Π_g 值相加得到擴展節點的能耗，時間步值則用于滿足路徑約束條件。記三者坐標分別為father （x₀，y₀） 、current （x₁，y₁） 、neighbor （x₂，y₂）_o 本文中設定柵格圖為4聯通網絡，即每個節點的鄰居節點有5個（包含原地等待），網格的移動方式如圖2所示。網格移動的方向向量為：

dx₁，dy₁=x₁-x₀，y₁-y₀

dx₂，dy₂=x₂-x₁，y₂-y₁

當 （x₁，y₁）=（x₂，y₂） 時，AGV將處于待機狀態，僅產生待機能耗。當 （x₁，y₁）≠（x₂，y₂） 且 （x₀，y₀）= （x₁，y₁） 時，AGV將由待機狀態轉變為運動狀態，產生啟動能耗和運動能耗（為簡化計算視為直行運動）。當 （x₀，y₀）≠（x₁，y₁） 且 （x₁，y₁）≠（x₂，y₂） 時，可根據方向向量判斷該鄰居節點是否進行轉彎運動，即當 dx₁?dy₂=dx₂?dy₁ 時，AGV直行，當dx₁?dy₂≠dx₂?dy₁ 時，則進行轉彎運動。能耗增量

計算公式為：

圖2 網格移動方式示意

在能耗增量計算公式的基礎上，EEA*算法流程如圖3所示，其中，OPEN表使用最小堆的數據結構進行維護，CLOSED表以鍵值對結構進行存儲，若未查詢到元素則返回。通過在節點搜索過程中保留短期歷史節點的信息，EEA*算法能夠在節點擴展中快速篩選出局部能耗最優的節點，進而減少計算量，提高了計算效率。

圖3EEA*算法流程

3.3基于CBS的多AGV節能路徑規劃算法 （E-CBS）

E-CBS算法沿用了CBS的層次化設計，其高層搜索用于管理全局沖突，通過約束樹（ConstraintTree，CT）分解路徑沖突及生成約束條件；低層搜索則使用EEA*算法獨立規劃每個智能體在約束條件下的能耗最優路徑。

通過約束樹進行節點擴展時，會檢測路徑集存在的沖突（頂點沖突及邊沖突），并為造成沖突的智能體生成約束，通過分支策略生成子節點，每個子節點代表一種沖突解決方案。通過約束樹快速擴展節點，逐步消除所有沖突，最終得到可行路徑集。為實現多AGV系統節能路徑規劃，將能耗因素納人考慮范圍，設AGV總數為 N ，E-CBS擴展約束樹節點時的目標函數為：

E-CBS算法在擴展約束樹節點時采取最佳優先搜索（Best-FirstSearch，BFS）策略，即在約束樹節點擴展的順序上，根據節點路徑集的能耗成本函數總和排序。CBS根據檢測到沖突的順序進行消解，在沖突消解的過程中可能會由于新路徑與原有路徑產生新的沖突而導致其他AGV增加新的能耗。為降低此類情況造成的影響，E-CBS采取考慮AGV載質量、路徑距離及沖突數量的動態優先級策略，使質量較大、剩余路徑較長及沖突較少的AGV盡量保持初始的能耗最優路徑，沖突相關的其他AGV則在不同約束樹節點中繞路或等待。優先級數學模型 DP_i（n） 為：

式中： m_i 為第 i 臺AGV的載質量， m_max 為AGV系統中最大載質量， L（π_i^s，n） 為第 i 臺AGV從起點 s 至節點 n 的路徑長度， L（π_i） 為其路徑總長度， cⁱ 為第 i 臺AGV造成的路徑沖突數量， w₁?w₂?w₃∈（0，1） 分別為載質量、剩余路徑長度、沖突數量的權重系數。

AGV的 DP_i 值越低則越優先添加路徑約束。

綜上，多AGV系統節能路徑規劃算法E-CBS流程如圖4所示。

圖4E-CBS算法流程

4仿真試驗及結果討論

4.1單AGV能耗優化算法驗證

為驗證EEA*算法的有效性，選取了不同障礙物密度及不同尺寸的網格地圖進行仿真驗證。AGV及試驗相關參數如表1所示。所有仿真試驗均在采用Windows11系統23h2版本的計算機，其CPU配置為intel（R）Corei7-13620H，主頻為2.4GHz ，運行內存為 16GB 。

第1輪試驗選擇了 20m×20m 尺寸的柵格圖，分別選取 10%～30% 的障礙物密度，各進行100次隨機生成障礙物位置的仿真，AGV起點與終點分別設置在地圖的左下角與右上角，質量均設定為 1000kg ，試驗結果如圖5所示。由圖5可知，EEA*算法節能效率主要集中于 6%～22% ，不同組試驗的平均節能效率的變化波動為 12.15%。

16.44% ，隨障礙物密度增加呈現輕微下降趨勢。第2輪試驗障礙物密度固定為 20% ，選取不同地圖尺寸進行仿真，結果如圖6所示。由圖6可知，平均節能效率由 14.19% 至 20.35% 逐步遞增，與地圖尺寸呈現明顯的正相關性。從算法原理的角度分析，在較低的障礙物密度和較大的網格尺寸下，AGV起點至終點的可行區域較廣，為EEA*算法提供了較大的能耗優化空間，而在密集障礙物及小尺寸地圖中，僅有一條路徑甚至沒有可行解，無法進行能耗優化。圖7為EEA*算法改進前、后的計算時間對比，并與傳統A*算法進行了比較，驗證了新流程對計算效率提升的有效性。

圖5不同障礙物密度下EEA*節能效率變化

圖6不同地圖尺寸下EEA*節能效率變化

圖7不同地圖尺寸下計算時間變化

為直觀說明EEA*算法的能耗優化方式，在障礙物密度為 20% 、尺寸為 20m×20m 的地圖進行隨機試驗的路徑規劃，結果如圖8a所示，其中，黑色網格表示障礙物，圓點表示AGV起始點，三角形表示終點，AGV0與AGV1不同的線條樣式分別代表傳統 A^* 算法與EEA*算法規劃的路徑。圖8b與圖8c為不同障礙物密度和地圖尺寸的路徑對比結果，表2為3次試驗的能耗與時間步對比。

圖8不同仿真條件下的路徑對比

通過對比觀察圖8中的路徑，結合表2數據進行分析，可發現EEA*算法大幅減少了轉彎次數。盡管在路徑的中期生成階段，EEA*算法選擇的節點到目標點的距離相較于傳統 A^* 算法更長，但從全局能耗的角度評估，其能夠避免陷入障礙物密集區域從而實現更低的能量消耗，能耗降低 7.8% ～21.24% 。時間步方面則與傳統 A^* 規劃基本持平，說明EEA*算法可避免造成額外的時間成本。

4.2多AGV能耗優化算法驗證

對多AGV能耗優化算法E-CBS算法進行驗證，選擇4臺AGV在不同障礙物密度下的隨機網格地圖中分別進行100次仿真，起終點分別設置在地圖的4個頂點（0，0）、（19，0）、（19，19）、（0，19）及對角頂點，質量分別設置為 2 000kg?2 500kg ，權重系數 w₁，w₂，w₃ 均為0.3，其他試驗參數如表1所示。為證明E-CBS沖突消解策略的有效性，對照算法除CBS外，還選擇EEA*算法進行單AGV的路徑規劃，再使用時間窗算法進行沖突消解[15]，試驗結果如圖9與表3所示。

圖9不同障礙物密度下的多AGV算法節能效果比較

從任意一組試驗結果來看，由于時間窗算法和E-CBS算法的底層均采用EEA*算法，因此，能夠減少大量的無效轉向能耗。而E-CBS的路徑沖突消解策略能夠搜索更多可能性，在啟停能耗方面實現了進一步優化，最終3組試驗能耗分別降低17.16%.16.35%.14.02% ，證明了其路徑沖突消解策略的有效性。從時間成本角度分析，在較低障礙物密度下，E-CBS算法能夠保持與CBS算法同樣的性能，而時間窗算法則由于等待策略會產生額外的時間成本。

為直觀說明E-CBS的有效性，隨機選取一次試驗結果進行路徑對比。圖10a為CBS算法的路徑規劃結果，經過4次迭代得到的約束為 Ψ_ctv= （a₀，（6，13）） ，19）， （a₁，（6，6），19）] ，因此，AGVO選擇了在（6，12）處轉彎，AGV1則直接選擇了另一條時間步相同但不經過（6.6的路徑。圖10b、圖10c分別為時間窗算法、E-CBS算法的路徑規劃結果，沖突檢測結果為 c_v=（a₁，a₃，（13，13），19） ，時間窗算法選擇令AGV1在（14，13）處進行等待，造成了額外的啟停能耗，同時AGV1的等待占據了AGV3的路徑，導致其必須采取繞路策略，造成了新的轉向能耗。E-CBS算法在進行沖突消解時對比了多個節點的路徑集，選擇了另一條能耗成本較低且滿足約束的路徑，從而避免了等待及繞路的發生。

表4為不同算法規劃下4臺AGV的能耗及時間步的對比。時間窗及E-CBS算法在能耗方面均獲得大幅優化，整體的能耗優化效率分別達到22.43%.25.48% 。而在時間步方面，時間窗算法由于采取了等待和繞道策略，增加了額外的時間消耗，E-CBS算法則實現了時間成本不變。綜上，E-CBS算法能夠在不同復雜場景下實現有效穩定的能耗優化，同時能夠有效避免總體時間成本的增加。

圖10多AGV算法規劃路徑對比

表4多AGV算法規劃結果時間步及能耗對比

5 結束語

本文對復雜場景下多AGV系統的節能路徑規劃問題進行研究，建立了考慮載質量、轉向與啟停等多影響因素的AGV能耗模型，并以能耗優化為目標對 A^* 算法的啟發式函數及節點擴展流程進行優化，提出了單AGV節能路徑規劃算法EEA*，避免路徑陷入障礙物密集區域，減少了轉彎次數。

面向多AGV系統，將EEA*作為算法底層，并通過改進碰撞檢測與約束分配機制構建了E-CBS算法。經過多組隨機障礙物場景的仿真驗證，E-CBS算法在保證較高節能效率的同時，在時間優化方面也優于時間窗算法。后續研究中，可在提高算法求解效率和應對動態障礙物場景等方面進一步改進。

參考文獻：

[1]趙學健，葉昊，賈偉，等.AGV路徑規劃及避障算法研究綜述[J].小型微型計算機系統，2024，45（3）：529-541.

[2]王贊，馬榮，唐思源.基于改進鯨魚優化算法的AGV柔性作業車間多目標優化調度[J].現代制造工程，2024（7）： 17-25.

[3]WUM，YEONGCF，SUELM，etal.AReview onEner-gyEfficiency in Autonomous Mobile Robots[J].Robotic In-telligence and Automation，2023，43（6）： 648-668.

[4]張浩杰，張玉東，梁榮敏，等.改進 A^* 算法的機器人能耗最優路徑規劃方法[J].系統工程與電子技術，2023，45（2）： 513-520.

[5]江磊，賈文友，劉莉，等.能耗最優下輪式移動機器人作業路徑規劃的最優節點 A^* 算法[J].機械科學與技術，2023（6）： 949-955.

[6]ZHANGHJ，ZHANGYD，LIUCK，etal.EnergyEffi-cientPathPlanningforAutonomousGroundVehicleswithAckermann Steering[J]. Robotics and Autonomous Sys-tems，2023，162.

[7] GAOJQ，LIYJ，LIXY，etal.AReview ofGraph-BasedMulti-Agent Pathfinding Solvers：From Classical to Be-yond Classical[J].Knowledge-Based Systems，2024，283.

[8]LIP，YANGLW.Conflict-Free and Energy-EfficientPathPlanningforMulti-RobotsBasedonPriorityFree antColony Optimization[J]. Mathematical Biosciences and En-gineering，2022，20（2）：3528-3565.

[9]宋栓軍，呂森.考慮能耗的多AGV系統路徑沖突解決策略[J].輕工機械，2022（1）： 78-84+90 #

[10]陳晶晶，方葉祥，王文鳳.考慮能耗的多AGV系統無沖突路徑規劃[J].組合機床與自動化加工技術，2023（12）： 56-60.

[11]SHARON G，STERNR，FELNER A，et al.Conflict-Based Search for Optimal Multi-Agent Pathfinding[J].Artificial Intelligence，2015，219： 40-66.

[12]BARER M，SHARONG，STERN R， et al. SuboptimalVariantsoftheConflict-Based Search AlgorithmfortheMulti-Agent PathfindingProblem[J].Proceedings of theTwenty-first European Conference on Artificial Intelli-gence，2014：961-962.

[13]LIJY，RUMLW，KOENIGS.EECBS：ABounded-Sub-optimal SearchforMulti-AgentPath Finding[J].Proceed-ings of the AAAI Conference on Artificial Intelligence，2021，35（14）：12353-12362.

[14]李曉東，童亮，陳梓寧，等.能耗優化的移動機器人路徑規劃方法[J]北京信息科技大學學報（自然科學版），2024，39（1）：28-36.

[15]宋佳.基于Dijkstra算法的AGV綠色節能路徑規劃研究[D].南昌：南昌大學，2022.