融合改進A*和DWA算法的物流機器人自主導航及路徑規劃研究

摘要：本文提出了一種融合改進A*算法和DWA算法的物流機器人自主導航及路徑規劃方法。改進A*算法引入航向角策略和Floyd算法優化，生成平滑高效的全局路徑；改進DWA算法引入全局路徑因素和自適應窗口機制，實現實時避障與全局引導。實驗結果表明，這種融合改進算法相比傳統A*和DWA算法，任務完成率提高8.2%，平均用時縮短14.4%，平均能耗降低21.7%，顯著提升了物流機器人在復雜動態環境中的導航性能。

關鍵詞：物流機器人；A*算法；DWA算法；自主導航；路徑規劃

引言

隨著物流行業的快速發展，物流機器人在倉儲、配送等環節發揮著越來越重要的作用。然而，復雜多變的物流環境對物流機器人的自主導航和路徑規劃能力提出了更高要求。傳統算法在動態未知環境中適應性不足，智能優化算法的實時性和收斂性有待提高。本文旨在解決上述問題，提出一種融合改進A*和DWA算法的路徑規劃方法，以提高物流機器人導航的安全性和效率。

1. 現階段物流機器人自主導航與路徑規劃算法存在的問題

物流機器人需要在復雜、動態的環境中實現高效、安全的導航與路徑規劃，相關要求對其自主性和智能化水平提出了一些挑戰。傳統算法和采樣算法對動態未知環境的適應性不強，實時避障能力有限；智能優化算法的實時性和收斂性還有待提高，參數調試較為復雜；大部分研究對算法改進后的計算效率和路徑質量缺乏定量分析與對比[1]。針對上述問題，本文從提高物流機器人導航規劃的安全性與高效性出發，提出了改進A*和DWA算法相結合的路徑規劃策略。

2. 融合改進A*與DWA算法的路徑規劃方法

2.1 A*算法改進

2.1.1 引入航向角策略

傳統A*算法在搜索最優路徑時，只考慮了當前節點到目標節點的估計代價，而忽略了節點間連接路徑的方向變化，導致生成的路徑往往存在大量冗余節點，路徑平滑度差。針對上述問題，研究在A*算法中引入航向角的概念，通過評估相鄰節點間的夾角來優化路徑的生成過程。

設當前節點為ni，其父節點為ni-1，可擴展的子節點為。定義航向角為連接和的夾角，如圖1所示。

航向角可通過計算得到公式1：

（1）

引入航向角后，子節點的估計代價可表示為公式2：

（2）

其中，為起點到的實際代價，為到目標點的估計代價，w為航向角權重因子。通過合理設置權重因子w，可以控制航向角對節點擴展的影響程度。w值越大，算法越傾向于選擇與當前運動方向一致的節點，生成的路徑越平滑；w值越小，算法越傾向于選擇距離目標點最近的節點，生成的路徑越短。因此，w值的選取需要在路徑長度和平滑度之間進行權衡[2]。

2.1.2 Floyd算法優化路徑

盡管引入航向角策略后，A*算法生成的路徑得到了一定程度的平滑，但仍然存在一些冗余節點，導致路徑長度不夠理想。為了進一步優化路徑，研究在A*算法的基礎上，采用Floyd算法對生成的路徑進行二次處理。

Floyd算法是一種基于動態規劃的多源最短路徑算法，可以在O（n3）的時間復雜度內求出任意兩點之間的最短路徑。設改進A*算法生成的初始路徑為P0={n0，n1，…，nm}，其中n0為起點，nm為終點，m為路徑節點數。首先，根據路徑P0構建一個（m+1）×（m+1）的鄰接矩陣D，矩陣元素dij表示路徑節點ni和nj之間的歐幾里得距離，當ni和nj不直接相連時，dij=∞。

Floyd算法對于路徑上的任意兩個節點ni和nj，如果經過中間節點nk（i<k<j）使得路徑距離更短，即dij>dik+dkj，則更新dij=dik+dkj，同時記錄ni到nj到的最短路徑應經過nk。算法需初始化距離矩陣D和路徑矩陣P，然后循環遍歷中間節點nk={k=0，1…，m}，在此基礎上循環遍歷節點對（ni，nj）（i，j=0，1…，m）。如果dij>dik+dkj，則更新dij=dik+dkj，并設pij=k，并根據矩陣P提取任意兩個節點間的最短路徑。Floyd算法處理后，便可得到路徑上任意兩個節點間的最短路徑，從而實現對原始路徑的壓縮與平滑[3]。

2.2 DWA算法改進

在動態環境下，單純依靠全局路徑規劃難以應對突發障礙，容易導致機器人碰撞等危險情況。為了使機器人能夠在局部動態環境中靈活避障，同時兼顧全局路徑的引導，研究在DWA算法的基礎上進行了針對性的改進和優化。

傳統DWA算法通過在機器人速度空間中采樣獲得一系列可行速度，并評價每個采樣速度的效用，從中選取最優速度作為下一時刻的控制指令。評價函數通常包含方向、速度和距離三個因素，分別表示為（ν）、和，則采樣速度的效用如公式3所示：

（3）

其中，為三個因素的權重系數。然而，傳統DWA算法在評價速度時，只考慮了局部信息，容易使機器人偏離全局最優路徑。為了增強DWA算法的全局引導能力，研究在評價函數中引入全局路徑因素，表示采樣速度下機器人預測位置距離全局路徑的偏離程度，偏離越小，該項得分越高[4]。同時為了提高避障的安全性，還對距離因素進行了細化，考慮了機器人與障礙物的相對速度，引入碰撞時間項Tc。改進后的DWA評價函數如公式4所示：

（4）

其中，為四個因素的權重系數。在速度采樣時，傳統DWA算法采用等間隔的網格采樣方式，采樣粒度較粗，導致控制輸出不夠平滑。研究采用了基于概率分布的非均勻采樣策略，在局部最優速度附近進行細粒度采樣，在其他區域進行粗粒度采樣，從而在保證實時性的同時提高了速度選擇的精度。

2.3 融合改進算法設計實現

為實現物流機器人在復雜環境中的自主導航，本文提出了一種融合改進A*算法和改進DWA算法的路徑規劃方法。該方法以改進A*算法為核心，生成全局最優路徑，并結合改進DWA算法進行局部動態避障，實現了全局路徑引導下的實時避障，算法融合策略如圖2所示。

融合策略分為五個步驟：

（1）離線階段，利用改進A*算法在靜態地圖中規劃出起點到目標點的全局最優路徑。引入航向角因素，評估相鄰節點間的夾角，優先選擇與當前節點方向一致的節點，生成平滑路徑，然后采用Floyd算法對路徑進行二次優化，壓縮冗余節點，縮短路徑長度。

（2）機器人開始執行任務后，進入在線導航階段。利用傳感器實時獲取周圍環境信息，并與靜態地圖進行融合，構建局部代價地圖。代價地圖中包含靜態障礙物信息和動態障礙物信息，用于DWA算法的碰撞檢測。

（3）根據當前機器人位置和局部代價地圖，在改進DWA算法框架下進行速度采樣和評價。評價函數包括方向、速度、距離和全局路徑四個因素，其中全局路徑因素用于衡量采樣速度下機器人的預測位置與全局路徑的偏離程度。

（4）評價函數為每個采樣速度賦予效用值，選取效用最高的速度作為下一控制周期的速度指令，輸出到機器人底層控制器執行。機器人在局部路徑上運動的同時，實時進行障礙物檢測和避障決策。

（5）隨著機器人不斷運動，更新當前位置和局部代價地圖，重復步驟（3）和步驟（4，直到到達目標點或出現無法避障的情況。如果出現無法避障，則須返回步驟（1，重新規劃全局路徑。

為加快算法的收斂速度，減少無效搜索，研究在改進DWA算法的基礎上，設計了自適應窗口調整機制[5]。根據機器人與最近障礙物的距離，動態調整速度空間的搜索范圍，距離障礙物越近，搜索窗口越小，反之則越大。同時，在窗口內采用非均勻采樣，提高局部最優速度附近的采樣密度，自適應窗口示意如圖3所示。

3. 融合改進算法的物流機器人導航規劃實驗分析

為驗證融合改進A*和DWA算法的路徑規劃方法的有效性和優越性，本文在物流機器人平臺上開展了導航規劃實驗。實驗在完整的物流場景中進行，包含多個揀貨點和配送站，機器人需要根據訂單依次經過各個目標點，同時避開動態障礙。實驗對比了融合改進算法與傳統A*+DWA算法在任務完成率、平均用時和平均能耗三個指標上的差異。其中，平均用時反映了路徑的時間優化程度，平均能耗反映了路徑的平滑度和速度變化的劇烈程度，兩種算法的綜合導航實驗結果對比如表1所示。

從表1可以看出，融合改進算法相比傳統算法，任務完成率提高了8.2%，平均用時縮短了約14.4%，平均能耗降低了約21.7%，整體導航性能大幅提升。這得益于全局路徑的持續優化和局部路徑的自適應調整，使得機器人能夠在動態環境中高效、靈活地完成導航任務。結果證明，融合改進A*和DWA算法的路徑規劃方法在綜合導航性能上顯著優于傳統算法，該方法能夠使物流機器人在復雜動態環境中實現高效、平滑、安全的自主導航，顯著提高了物流作業效率和智能化水平。

結語

本文提出的融合改進A*和DWA算法的物流機器人自主導航及路徑規劃方法，有效解決了傳統算法在復雜動態環境中的局限性。未來研究可進一步探索算法在更復雜環境下的適應性，如多機器人協同導航、動態目標追蹤等場景。此外，還可結合深度學習等人工智能技術，提高算法的環境感知和決策能力。本研究為物流機器人在復雜動態環境中實現高效、安全、智能的自主導航提供了新的技術支持，對推動物流行業智能化升級具有重要意義。

參考文獻：

[1]薛光輝，劉爽，王梓杰，等.基于改進概率路線圖算法的煤礦機器人路徑規劃方法[J].工礦自動化，2023，49（6）：175-181.

[2]郭志軍，尹亞昆，李亦軒，等.融合改進A～*和TEB算法的移動機器人路徑規劃[J].河南科技大學學報（自然科學版），2023，44（4）：57-65，7.

[3]常見，任雁.基于改進遺傳算法的機器人路徑規劃[J].組合機床與自動化加工技術，2023（2）：23-27.

[4]趙倩楠，黃宜慶.融合A～*蟻群和動態窗口法的機器人路徑規劃[J].電子測量與儀器學報，2023，37（2）：28-38.

[5]王鶴靜，王麗娜.機器人路徑規劃算法綜述[J].桂林理工大學學報，2023，43（1）：137-147.

作者簡介：黃以成，碩士研究生，工程師，研究方向：自動控制、項目管理。