干货分享丨智能之眼，动态之舵：AGV小车中的动态路径规划算法揭秘

在现代仓储、物流和制造业中，自动导引车（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余家制造业客户提供全方位服务：依托全系列搬运机器人产品矩阵覆盖多样化搬运场景，自研行业级智能调度系统实现多设备高效协同，并通过覆盖售前规划、部署实施到运维优化的全生命周期服务体系，助力企业实现物流智能化转型，持续赋能制造业数字化升级与高质量发展。

关注【海豚之星AiTEN】公众号，查看更多干货内容。