全局路径规划（Global Path Planning）是在全局已知环境地图（如栅格地图、矢量图或点云地图）与已知静态障碍物的条件下，寻找一条从起始点到目标点的无碰撞、满足特定约束（如最短距离、最低代价）的几何路径。

在机器人和自动驾驶系统（如 ROS / Nav2 架构）中，全局规划器负责生成宏观拓扑轨迹，而局部规划器（Local Planner，如 DWA、TEB）则在此轨迹指导下实时避开动态障碍物并满足加速度等动力学限制。

核心算法分类与原理

全局路径规划算法主要分为基于图搜索、基于随机采样以及基于曲线与智能优化三大类。

1. 基于图搜索的算法（Graph Search-Based）

这类算法将空间离散化（如网格、栅格图、拓扑图），并在图节点上遍历寻找可行路径。

Dijkstra 算法

• 原理：基于广度优先搜索（BFS）思想，计算起点到图中所有其他节点的最短路径。

• 代价函数：$f(n) = g(n)$，其中 $g(n)$ 是起点到当前节点 $n$ 的实际代价。

• 特点：能保证找到全局最优解，但盲目向所有方向扩展，盲目性大，搜索效率低。

A* 算法

• 原理：在 Dijkstra 的基础上引入启发式（Heuristic）信息，引导搜索向终点方向推进。

• 估价函数：

   

  $$f(n) = g(n) + h(n)$$

  • $g(n)$：起点到当前节点 $n$ 的实际代价。

  • $h(n)$：当前节点 $n$ 到终点的估计代价（如欧氏距离、曼哈顿距离）。

• 特点：只要启发函数 $h(n)$ 是可采纳的（Admissible，即 $h(n) \le h^*(n)$，不过高估计实际距离），A* 就能确保找到最优解，且效率远高于 Dijkstra。

Dynamic A* (D* / D* Lite)

• 原理：增量式搜索算法。在机器人沿规划路径行驶遇到未知障碍物时，仅局部更新被阻挡节点的影响，无需重新搜索全局。

• 应用场景：未知或半未知环境中的自主探索与重规划。

Hybrid A*（混合 A*）

• 原理：将离散图搜索与连续车辆运动学结合。节点扩展时考虑车辆的最小转弯半径、前进/后退状态，生成的每个节点都对应连续状态下的可行轨迹。

• 应用场景：阿克曼转向模型（如自动驾驶汽车、泊车系统）的全局路径规划。

2. 基于随机采样的算法（Sampling-Based）

在不构建显式地图的情况下，通过在构型空间（Configuration Space, C-space）中随机采样节点并连接成树或图。适合高维空间与复杂多自由度机器人。

PRM（概率路图法，Probabilistic Roadmaps）

• 原理：分为学习阶段与查询阶段。

   

  1. 在 C-space 中随机均匀采样点，剔除碰撞点。

  2. 将邻近点连线并进行碰撞检测，构建无碰撞路图（Roadmap）。

  3. 给定起点和终点，连接到路图上并用标准图搜索（如 A*）求解路径。

• 特点：适合多查询（Multi-query）场景，即地图不变、多次规划不同起终点。

RRT（快速扩展随机树，Rapidly-exploring Random Trees）

• 原理：从起点开始建立一棵树，每次在 C-space 随机采点 $q_{\text{rand}}$，找到树上最近节点 $q_{\text{near}}$，向采样点方向生长步长 $\varepsilon$ 得到新节点 $q_{\text{new}}$，经碰撞检测后加入树中，直到连接到终点。

• 特点：单次查询效率极高，对高维空间和非完整性约束（Non-holonomic Constraints）适应性强，但生成的路径往往是折线、非最优。

RRT* 算法

• 原理：在 RRT 基础上增加了邻域重寻优（Rewire）机制。新节点加入后，检查并重新连接邻域节点，使树的路径代价不断降低。

• 特点：具有渐进最优性（Asymptotic Optimality），即随着采样点增加，路径无限接近全局最优解。

3. 基于曲线与智能优化的算法

• 人工势场法（APF）：将终点设为引力源，障碍物设为斥力源，机器人顺着合力梯度方向移动。计算快，但易陷入局部极小值（Local Minima）。

• Bezier / B-Spline 样条曲线：通常作为后处理步骤，将图搜索（如 A*）生成的折线拐角打磨平滑，使其符合动力学平滑度要求。

关键算法对比

算法类别	代表算法	核心优势	主要局限	经典应用场景
栅格图搜索	A*	保证最优性，算法结构简单，工程实现成熟	节点方向受离散化限制（如8方向），路径有折角	扫地机器人、2D网格导航
连续图搜索	Hybrid A*	显式满足车辆运动学约束，生成的路径可直接驾驶	搜索维度高（$x, y, \theta$），内存与计算开销大	自动驾驶极窄空间泊车、阿克曼车辆导航
随机采样	RRT*	擅长高维空间，无需显式地图，渐进最优	随机性强，每次生成的路径不一致，需要平滑	机械臂运动规划、无人机三维避障
增量搜索	D* Lite	动态更新快，无需重新全局搜索	维护 Complex Priority Queue 开销较大	未知环境探险、边建图边导航

工业级全局规划流程

在现代机器人导航框架（如 ROS2 Nav2）中，一个完整的全局规划流水线包含以下步骤：

1. 代价地图建立（Costmap Generation）：将原始地图转化为代价值地图，通过碰撞膨胀层（Inflation Layer）将障碍物向外拓展机器人半径加安全边距。

2. 拓扑路径搜索：运行 A* 或 Hybrid A* 算法，在代价地图上搜索出一条代价最低且无碰撞的节点序列。

3. 路径平滑（Path Smoothing）：使用梯度下降法（Gradient-based Smoothing）或 B 样条曲线，在保持无碰撞的前提下消除折弯、降低曲率变化率。

4. 下发至局部规划器：将平滑后的 Waypoints 序列作为参考轨迹，交由局部规划器（DWA/TEB/MPC）进行实时轨迹跟踪与动态避障。