在現(xiàn)代倉(cāng)儲(chǔ)、物流和制造業(yè)中，自動(dòng)導(dǎo)引車（AGV）的身影日益普遍。它們?nèi)缤趧诘墓は?，在?fù)雜的環(huán)境中自主穿梭，高效地完成物料搬運(yùn)任務(wù)。而支撐AGV實(shí)現(xiàn)智能導(dǎo)航的核心技術(shù)之一，便是路徑規(guī)劃。特別是當(dāng)環(huán)境并非一成不變時(shí)，動(dòng)態(tài)路徑規(guī)劃能力就顯得至關(guān)重要。本文將深入探討幾種主流的動(dòng)態(tài)路徑規(guī)劃算法（如A、Dijkstra、RRT等），并解析它們?nèi)绾卧贏GV行業(yè)中大顯身手。

為何需要?jiǎng)討B(tài)路徑規(guī)劃？

1.簡(jiǎn)介

傳統(tǒng)的靜態(tài)路徑規(guī)劃假設(shè)環(huán)境是完全已知的，并且在AGV執(zhí)行任務(wù)期間保持不變。然而，現(xiàn)實(shí)世界充滿了變數(shù)：

●突然出現(xiàn)的臨時(shí)障礙物（如掉落的貨物、行人或其他車輛）

●變化的交通管制區(qū)域

●需要臨時(shí)調(diào)整的目標(biāo)點(diǎn)或任務(wù)

在這些情況下，AGV需要具備實(shí)時(shí)感知環(huán)境變化并快速重新規(guī)劃路徑的能力，這就是動(dòng)態(tài)路徑規(guī)劃的用武之地。它賦予了AGV“隨機(jī)應(yīng)變”的智慧，確保其在復(fù)雜多變的環(huán)境中依然能夠安全、高效地運(yùn)行。

主流路徑規(guī)劃算法解析

1.Dijkstra算法：全局最優(yōu)的基石

Dijkstra算法是一種經(jīng)典的圖搜索算法，用于查找圖中單個(gè)源點(diǎn)到所有其他頂點(diǎn)的最短路徑。

●核心思想：

從起點(diǎn)開始，像水波紋一樣向外擴(kuò)散。每次訪問(wèn)當(dāng)前距離起點(diǎn)最近的未訪問(wèn)節(jié)點(diǎn)，并更新其鄰居的距離。

●過(guò)程：

○初始化： 起點(diǎn)距離設(shè)為0，其他點(diǎn)設(shè)為無(wú)窮大。創(chuàng)建待訪問(wèn)節(jié)點(diǎn)的優(yōu)先隊(duì)列（按距離排序）。

○迭代：從隊(duì)列取出距離最小的節(jié)點(diǎn) u。

○松弛：對(duì) u 的每個(gè)鄰居 v，若經(jīng) u 到 v 的路徑更短，則更新 v 的距離并加入隊(duì)列。

○標(biāo)記：標(biāo)記 u 為已訪問(wèn)。

○重復(fù)：直到目標(biāo)節(jié)點(diǎn)被取出，或隊(duì)列為空。

●AGV小車應(yīng)用：

○優(yōu)點(diǎn)： 保證找到全局最短路徑（邊權(quán)非負(fù)時(shí)）。

○缺點(diǎn)： 搜索范圍大，無(wú)方向性，計(jì)算效率較低（尤其在大地圖）。動(dòng)態(tài)障礙物需重算全局路徑，實(shí)時(shí)性差。

○定位： 常作其他算法（如A*）基礎(chǔ)，或在環(huán)境簡(jiǎn)單時(shí)使用。

↑Dijkstra算法從起點(diǎn)開始，像波紋一樣逐層探索節(jié)點(diǎn)

2.A* 算法：?jiǎn)l(fā)式的智慧導(dǎo)航

A*（A-Star）算法是對(duì)Dijkstra算法的優(yōu)化，它引入了啟發(fā)式信息來(lái)引導(dǎo)搜索方向，從而更快地找到目標(biāo)。

●核心思想： 選擇下一個(gè)訪問(wèn)節(jié)點(diǎn)時(shí)，同時(shí)考慮：

○g(n)： 從起始點(diǎn)到節(jié)點(diǎn)n的實(shí)際路徑成本。

○h(n)： 從節(jié)點(diǎn)n到目標(biāo)的估計(jì)成本（啟發(fā)函數(shù)，如曼哈頓/歐氏距離）。

○評(píng)估函數(shù)：f(n) = g(n) + h(n)

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

●過(guò)程： 類似于Dijkstra，類似Dijkstra，但優(yōu)先隊(duì)列按f(n)排序，優(yōu)先擴(kuò)展f(n)最小的節(jié)點(diǎn)，使搜索更有方向性地朝向目標(biāo)。

●AGV應(yīng)用：

○優(yōu)點(diǎn)：在啟發(fā)函數(shù)滿足條件時(shí)，保證最優(yōu)路徑且通常比Dijkstra效率高得多。廣泛用于AGV全局路徑規(guī)劃。

○缺點(diǎn)： 性能受啟發(fā)函數(shù)選擇影響；內(nèi)存消耗可能大；環(huán)境頻繁變化時(shí)仍需重規(guī)劃。

○動(dòng)態(tài)變種： 為應(yīng)對(duì)動(dòng)態(tài)環(huán)境，有D*, LPA*, D* Lite等算法。它們能在環(huán)境變化時(shí)增量式更新路徑（而非完全重算），顯著提高響應(yīng)速度。D* Lite是AGV動(dòng)態(tài)避障常用算法。

↑A*算法在啟發(fā)函數(shù)引導(dǎo)下，搜索區(qū)域更集中地朝向目標(biāo)點(diǎn)擴(kuò)展，而不是盲目擴(kuò)散

3.RRT* 算法：擁抱隨機(jī)性與優(yōu)化

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

●核心思想：

通過(guò)在狀態(tài)空間隨機(jī)采樣，逐步生長(zhǎng)一棵從起點(diǎn)開始的樹來(lái)探索空間。RRT*是RRT的優(yōu)化版，增加了重連接 (Rewiring) 步驟，使路徑能漸近最優(yōu)（采樣點(diǎn)越多，路徑越接近最優(yōu)）。

●過(guò)程：

○采樣： 在狀態(tài)空間中隨機(jī)生成點(diǎn) x_rand。

○查找最近鄰： 在樹中找到離 x_rand 最近的節(jié)點(diǎn) x_nearest。

○擴(kuò)展（Steer）： 從 x_nearest 向 x_rand 延伸一個(gè)步長(zhǎng)（避開障礙），得到新節(jié)點(diǎn) x_new。

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

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

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

○重復(fù)： 直到樹擴(kuò)展到目標(biāo)區(qū)域附近。

●AGV應(yīng)用：

○優(yōu)點(diǎn)： 處理高維狀態(tài)（姿態(tài)、速度等）和復(fù)雜約束能力強(qiáng)；不需要顯式環(huán)境地圖；概率完備性（存在路徑則最終能找到）；RRT具有漸近最優(yōu)性。

○缺點(diǎn)： 路徑非嚴(yán)格最優(yōu)（除非無(wú)限采樣）；路徑可能不平滑（需后處理）；性能對(duì)參數(shù)敏感；收斂可能較慢。

○動(dòng)態(tài)變種： 如 Dynamic RRT，通過(guò)移除/更新樹中與動(dòng)態(tài)障礙物碰撞的部分并繼續(xù)生長(zhǎng)來(lái)實(shí)現(xiàn)重規(guī)劃。

↑RRT*樹從起點(diǎn)開始隨機(jī)生長(zhǎng)，探索空間

AGV小車中的動(dòng)態(tài)路徑規(guī)劃實(shí)踐

# AGV避障應(yīng)用場(chǎng)景

在實(shí)際的AGV應(yīng)用中，通常不會(huì)只使用單一算法，而是結(jié)合使用：

1.全局路徑規(guī)劃：

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

↑全局路徑（虛線）

2.局部路徑規(guī)劃/動(dòng)態(tài)避障：

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

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

3.路徑跟蹤：

控制算法負(fù)責(zé)精確地沿著規(guī)劃好的路徑（無(wú)論是全局還是局部）驅(qū)動(dòng)AGV行駛。

這種分層規(guī)劃的策略兼顧了全局最優(yōu)性和局部實(shí)時(shí)性。D Lite等算法因其高效的增量式重規(guī)劃能力，在處理局部動(dòng)態(tài)變化時(shí)表現(xiàn)尤為出色。RRT及其變種則在處理復(fù)雜環(huán)境和運(yùn)動(dòng)約束時(shí)更具優(yōu)勢(shì)。

↑更改全局路徑

挑戰(zhàn)與未來(lái)趨勢(shì)

# 挑戰(zhàn)

盡管動(dòng)態(tài)路徑規(guī)劃技術(shù)取得了長(zhǎng)足進(jìn)步，但在AGV行業(yè)應(yīng)用中仍面臨挑戰(zhàn)：

●實(shí)時(shí)性要求： 尤其是在高速運(yùn)行或密集交通場(chǎng)景下，算法需要在毫秒級(jí)完成計(jì)算。

●環(huán)境不確定性： 傳感器噪聲、定位誤差、動(dòng)態(tài)障礙物預(yù)測(cè)的困難。

●多AGV協(xié)調(diào)： 避免沖突、死鎖，實(shí)現(xiàn)高效協(xié)作。

●復(fù)雜運(yùn)動(dòng)學(xué)約束： 考慮AGV的尺寸、轉(zhuǎn)彎半徑、加減速性能。

# 未來(lái)趨勢(shì)

未來(lái)，動(dòng)態(tài)路徑規(guī)劃將朝著更智能、更高效的方向發(fā)展：

●機(jī)器學(xué)習(xí)融合： 利用強(qiáng)化學(xué)習(xí)、模仿學(xué)習(xí)等方法讓AGV自主學(xué)習(xí)更優(yōu)的導(dǎo)航策略。

●預(yù)測(cè)性規(guī)劃： 預(yù)測(cè)其他動(dòng)態(tài)障礙物（如行人、車輛）的意圖和軌跡，提前規(guī)劃。

●語(yǔ)義理解： 讓AGV理解環(huán)境中的語(yǔ)義信息（如“人行道”、“充電區(qū)”），做出更符合場(chǎng)景的決策。

●人機(jī)協(xié)作： 在人機(jī)共存的環(huán)境中，實(shí)現(xiàn)更安全、自然的交互與避讓。

# 結(jié)語(yǔ)

Dijkstra、A、RRT及其動(dòng)態(tài)變種，是AGV小車動(dòng)態(tài)路徑規(guī)劃算法庫(kù)的核心工具。它們?nèi)缤珹GV的“智能之眼”和“動(dòng)態(tài)之舵”，使其能在復(fù)雜環(huán)境中靈活穿梭、高效作業(yè)。理解這些算法的原理和特點(diǎn)，對(duì)推動(dòng)AGV技術(shù)乃至整個(gè)自動(dòng)化領(lǐng)域的發(fā)展至關(guān)重要。隨著算法演進(jìn)和算力提升，未來(lái)的AGV必將更加智能、可靠和高效。

作為智能物流解決方案領(lǐng)域的企業(yè)，AiTEN海豚之星始終聚焦“智慧工廠”場(chǎng)景，深度整合技術(shù)創(chuàng)新與行業(yè)需求，已為全球200余家制造業(yè)客戶提供全方位服務(wù)：依托全系列搬運(yùn)機(jī)器人產(chǎn)品矩陣覆蓋多樣化搬運(yùn)場(chǎng)景，自研行業(yè)級(jí)智能調(diào)度系統(tǒng)實(shí)現(xiàn)多設(shè)備高效協(xié)同，并通過(guò)覆蓋售前規(guī)劃、部署實(shí)施到運(yùn)維優(yōu)化的全生命周期服務(wù)體系，助力企業(yè)實(shí)現(xiàn)物流智能化轉(zhuǎn)型，持續(xù)賦能制造業(yè)數(shù)字化升級(jí)與高質(zhì)量發(fā)展。

審核編輯 黃宇