融合改進A*和DWA算法的物流機器人自主導(dǎo)航及路徑規(guī)劃研究

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

關(guān)鍵詞：物流機器人；A*算法；DWA算法；自主導(dǎo)航；路徑規(guī)劃

引言

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

1. 現(xiàn)階段物流機器人自主導(dǎo)航與路徑規(guī)劃算法存在的問題

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

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

2.1 A*算法改進

2.1.1 引入航向角策略

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

設(shè)當(dāng)前節(jié)點為ni，其父節(jié)點為ni-1，可擴展的子節(jié)點為。定義航向角為連接和的夾角，如圖1所示。

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

（1）

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

（2）

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

2.1.2 Floyd算法優(yōu)化路徑

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

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

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

2.2 DWA算法改進

在動態(tài)環(huán)境下，單純依靠全局路徑規(guī)劃難以應(yīng)對突發(fā)障礙，容易導(dǎo)致機器人碰撞等危險情況。為了使機器人能夠在局部動態(tài)環(huán)境中靈活避障，同時兼顧全局路徑的引導(dǎo)，研究在DWA算法的基礎(chǔ)上進行了針對性的改進和優(yōu)化。

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

（3）

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

（4）

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

2.3 融合改進算法設(shè)計實現(xiàn)

為實現(xiàn)物流機器人在復(fù)雜環(huán)境中的自主導(dǎo)航，本文提出了一種融合改進A*算法和改進DWA算法的路徑規(guī)劃方法。該方法以改進A*算法為核心，生成全局最優(yōu)路徑，并結(jié)合改進DWA算法進行局部動態(tài)避障，實現(xiàn)了全局路徑引導(dǎo)下的實時避障，算法融合策略如圖2所示。

融合策略分為五個步驟：

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

（2）機器人開始執(zhí)行任務(wù)后，進入在線導(dǎo)航階段。利用傳感器實時獲取周圍環(huán)境信息，并與靜態(tài)地圖進行融合，構(gòu)建局部代價地圖。代價地圖中包含靜態(tài)障礙物信息和動態(tài)障礙物信息，用于DWA算法的碰撞檢測。

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

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

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

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

3. 融合改進算法的物流機器人導(dǎo)航規(guī)劃實驗分析

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

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

結(jié)語

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

參考文獻：

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

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

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

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

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

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