在現代倉儲、物流和制造業中，自動導引車（AGV）的身影日益普遍。它們如同勤勞的工蟻，在復雜的環境中自主穿梭，高效地完成物料搬運任務。而支撐AGV實現智能導航的核心技術之一，便是路徑規劃。特別是當環境并非一成不變時，動態路徑規劃能力就顯得至關重要。本文將深入探討幾種主流的動態路徑規劃算法（如A、Dijkstra、RRT等），并解析它們如何在AGV行業中大顯身手。

為何需要動態路徑規劃？

1.簡介

傳統的靜態路徑規劃假設環境是完全已知的，并且在AGV執行任務期間保持不變。然而，現實世界充滿了變數：

●突然出現的臨時障礙物（如掉落的貨物、行人或其他車輛）

●變化的交通管制區域

●需要臨時調整的目標點或任務

在這些情況下，AGV需要具備實時感知環境變化并快速重新規劃路徑的能力，這就是動態路徑規劃的用武之地。它賦予了AGV“隨機應變”的智慧，確保其在復雜多變的環境中依然能夠安全、高效地運行。

主流路徑規劃算法解析

1.Dijkstra算法：全局最優的基石

Dijkstra算法是一種經典的圖搜索算法，用于查找圖中單個源點到所有其他頂點的最短路徑。

●核心思想：

從起點開始，像水波紋一樣向外擴散。每次訪問當前距離起點最近的未訪問節點，并更新其鄰居的距離。

●過程：

○初始化： 起點距離設為0，其他點設為無窮大。創建待訪問節點的優先隊列（按距離排序）。

○迭代：從隊列取出距離最小的節點 u。

○松弛：對 u 的每個鄰居 v，若經 u 到 v 的路徑更短，則更新 v 的距離并加入隊列。

○標記：標記 u 為已訪問。

○重復：直到目標節點被取出，或隊列為空。

●AGV小車應用：

○優點： 保證找到全局最短路徑（邊權非負時）。

○缺點： 搜索范圍大，無方向性，計算效率較低（尤其在大地圖）。動態障礙物需重算全局路徑，實時性差。

○定位： 常作其他算法（如A*）基礎，或在環境簡單時使用。

↑Dijkstra算法從起點開始，像波紋一樣逐層探索節點

2.A* 算法：啟發式的智慧導航

A*（A-Star）算法是對Dijkstra算法的優化，它引入了啟發式信息來引導搜索方向，從而更快地找到目標。

●核心思想： 選擇下一個訪問節點時，同時考慮：

○g(n)： 從起始點到節點n的實際路徑成本。

○h(n)： 從節點n到目標的估計成本（啟發函數，如曼哈頓/歐氏距離）。

○評估函數：f(n) = g(n) + h(n)

○關鍵要求：h(n)需滿足可采納性（估計值≤實際值）和一致性，以保證找到最優解。

●過程： 類似于Dijkstra，類似Dijkstra，但優先隊列按f(n)排序，優先擴展f(n)最小的節點，使搜索更有方向性地朝向目標。

●AGV應用：

○優點：在啟發函數滿足條件時，保證最優路徑且通常比Dijkstra效率高得多。廣泛用于AGV全局路徑規劃。

○缺點： 性能受啟發函數選擇影響；內存消耗可能大；環境頻繁變化時仍需重規劃。

○動態變種： 為應對動態環境，有D*, LPA*, D* Lite等算法。它們能在環境變化時增量式更新路徑（而非完全重算），顯著提高響應速度。D* Lite是AGV動態避障常用算法。

↑A*算法在啟發函數引導下，搜索區域更集中地朝向目標點擴展，而不是盲目擴散

3.RRT* 算法：擁抱隨機性與優化

RRT* (Rapidly-exploring Random Tree Star) 一種基于采樣的路徑規劃算法，特別適合高維空間和復雜約束（如車輛運動學）。

●核心思想：

通過在狀態空間隨機采樣，逐步生長一棵從起點開始的樹來探索空間。RRT*是RRT的優化版，增加了重連接 (Rewiring) 步驟，使路徑能漸近最優（采樣點越多，路徑越接近最優）。

●過程：

○采樣： 在狀態空間中隨機生成點 x_rand。

○查找最近鄰： 在樹中找到離 x_rand 最近的節點 x_nearest。

○擴展（Steer）： 從 x_nearest 向 x_rand 延伸一個步長（避開障礙），得到新節點 x_new。

○選擇父節點（RRT* 特有）：在 x_new 附近搜索節點，選擇能使 x_new 從起點總路徑成本最小的節點 x_min 作為其父節點（需無碰撞）。

○重連接（Rewire - RRT* 特有）： 在 x_new 附近搜索節點，若通過 x_new 連接能降低其總路徑成本，則更新這些節點的父節點為 x_new。

○添加： 將 x_new 及其連接邊加入樹中。

○重復： 直到樹擴展到目標區域附近。

●AGV應用：

○優點： 處理高維狀態（姿態、速度等）和復雜約束能力強；不需要顯式環境地圖；概率完備性（存在路徑則最終能找到）；RRT具有漸近最優性。

○缺點： 路徑非嚴格最優（除非無限采樣）；路徑可能不平滑（需后處理）；性能對參數敏感；收斂可能較慢。

○動態變種： 如 Dynamic RRT，通過移除/更新樹中與動態障礙物碰撞的部分并繼續生長來實現重規劃。

↑RRT*樹從起點開始隨機生長，探索空間

AGV小車中的動態路徑規劃實踐

# AGV避障應用場景

在實際的AGV應用中，通常不會只使用單一算法，而是結合使用：

1.全局路徑規劃：

使用A或其變種（如D Lite）或有時是優化后的Dijkstra，在已知的地圖上規劃出一條從起點到終點的全局最優或次優路徑。這條路徑通常比較宏觀。

↑全局路徑（虛線）

2.局部路徑規劃/動態避障：

AGV小車在沿著全局路徑行駛時，通過傳感器（如激光雷達、攝像頭）實時感知周圍環境。一旦檢測到未預料到的障礙物（靜態或動態），局部規劃器（可能基于DWA - Dynamic Window Approach, TEB - Timed Elastic Band, 或快速重規劃的A/RRT變種）會介入，在全局路徑的指引下，生成一條短期的、安全的、符合車輛運動學約束的局部避障路徑。

↑全局路徑（虛線）、突然出現的障礙物(黑色輪廓)

3.路徑跟蹤：

控制算法負責精確地沿著規劃好的路徑（無論是全局還是局部）驅動AGV行駛。

這種分層規劃的策略兼顧了全局最優性和局部實時性。D Lite等算法因其高效的增量式重規劃能力，在處理局部動態變化時表現尤為出色。RRT及其變種則在處理復雜環境和運動約束時更具優勢。

↑更改全局路徑

挑戰與未來趨勢

# 挑戰

盡管動態路徑規劃技術取得了長足進步，但在AGV行業應用中仍面臨挑戰：

●實時性要求： 尤其是在高速運行或密集交通場景下，算法需要在毫秒級完成計算。

●環境不確定性： 傳感器噪聲、定位誤差、動態障礙物預測的困難。

●多AGV協調： 避免沖突、死鎖，實現高效協作。

●復雜運動學約束： 考慮AGV的尺寸、轉彎半徑、加減速性能。

# 未來趨勢

未來，動態路徑規劃將朝著更智能、更高效的方向發展：

●機器學習融合： 利用強化學習、模仿學習等方法讓AGV自主學習更優的導航策略。

●預測性規劃： 預測其他動態障礙物（如行人、車輛）的意圖和軌跡，提前規劃。

●語義理解： 讓AGV理解環境中的語義信息（如“人行道”、“充電區”），做出更符合場景的決策。

●人機協作： 在人機共存的環境中，實現更安全、自然的交互與避讓。

# 結語

Dijkstra、A、RRT及其動態變種，是AGV小車動態路徑規劃算法庫的核心工具。它們如同AGV的“智能之眼”和“動態之舵”，使其能在復雜環境中靈活穿梭、高效作業。理解這些算法的原理和特點，對推動AGV技術乃至整個自動化領域的發展至關重要。隨著算法演進和算力提升，未來的AGV必將更加智能、可靠和高效。

作為智能物流解決方案領域的企業，AiTEN海豚之星始終聚焦“智慧工廠”場景，深度整合技術創新與行業需求，已為全球200余家制造業客戶提供全方位服務：依托全系列搬運機器人產品矩陣覆蓋多樣化搬運場景，自研行業級智能調度系統實現多設備高效協同，并通過覆蓋售前規劃、部署實施到運維優化的全生命周期服務體系，助力企業實現物流智能化轉型，持續賦能制造業數字化升級與高質量發展。

審核編輯 黃宇