07-路径规划与导航-全局规划

作者：姚博文 · 2026-09-15

全局规划 — 栅格地图、搜索式与采样式规划算法

定位：从栅格地图与代价地图（Costmap）出发，讲透 Dijkstra / A\* / D\* Lite / RRT / RRT\* / PRM 全局规划算法的原理、对比与 Nav2 集成，附可直接运行的 Python 代价地图 A\* 实验 | 适用：智能小车/移动机器人开发

1\. 概述

1.1 这篇解决什么问题

"全局规划"（Global Planning）要回答的问题是：**在已知地图上，从当前位置到目标点，找出一条代价最小的路径**。它和"局部规划"（Local Planning，见 `局部规划.md`）的分工是：

| | 全局规划 | 局部规划 |

| --- | --- | --- |

| 输入 | 地图（栅格/代价地图）+ 起点 + 终点 | 实时传感器 + 当前路径 + 目标 |

| 处理对象 | 静态障碍（建出来的墙、柱子） | 动态障碍（人、移动的小车）+ 运动学/动力学约束 |

| 频率 | 目标点变化、地图更新时才重新规划（低频，1~10Hz 按需） | 每 10~50ms 滚动规划 |

| 输出 | 一条完整的路径点序列（/plan） | 下一个控制周期的速度指令（v, ω） |

| 典型算法 | A*、Dijkstra、D* Lite、RRT*、PRM | DWA、TEB、MPPI |

全局规划器不关心"下一毫秒怎么动"，它只关心"整体往哪走"。一条好的全局路径，让局部规划器的工作量大幅下降——局部规划器只需要"沿这条路径开，别撞人"。

💡 一个常见误区：期望"人从中间走过来时，全局路径立刻绕开他"。这是局部规划器的职责。全局规划器只在**地图变化**（新的静态障碍入库、重新建图）或**目标点改变**时重算。如果你的全局路径经常"追"动态障碍，说明架构用错了地方。

1.2 在自主导航链路中的位置

对应 `00-路线图/学习路线图.md` 的全链路图（阶段 D 的 D1 任务）：

全局规划器需要三样输入，每样都有一个"上游责任人"：

1. **地图**（`/map`，OccupancyGrid）—— 来自 SLAM 或预建地图（见 `06-定位与SLAM/激光SLAM.md`）；

2. **机器人位姿**（`map→base_link`，TF）—— 来自定位（见 `06-定位与SLAM/定位与状态估计.md`）；

3. **代价地图（Costmap）** —— 由全局规划器内部（Nav2 Costmap2D）把"地图 + 实时激光 + 机器人尺寸"烘成一张"每格走起来多贵"的图，这是本篇 §2.2 的重点。

1.3 本文覆盖

1. **栅格地图（Grid Map）**：OccupancyGrid 数据结构、分辨率/原点、格子↔世界坐标换算、激光如何更新占用概率（log-odds）；

2. **代价地图（Costmap）**：Nav2 三层结构（static/obstacle/inflation）、代价取值（0~255）、膨胀（inflation）公式与参数含义；

3. **搜索式规划**：Dijkstra → A\*（启发函数、可采纳/一致性、切角、加权 A\*）→ D\* / D\* Lite（增量重规划）；

4. **采样式规划**：RRT、RRT\*（渐近最优）、PRM（概率路图），以及为什么 2D 小车上它们通常"出场率"不高；

5. **选型对比表** + Nav2 内置规划器对照（NavFn / Smac 家族 / dplanner）；

6. **可运行的纯 Python 代价地图 A**\*（标准库）+ Nav2 配置 YAML + 调参速查 + 踩坑清单。

前置阅读：`01-基础概念/移动机器人与自主导航总览.md`（链路总览）、`06-定位