A* 在栅格地图上搜索低代价路径的工程解释

A* 是机器人路径规划里最常见的搜索算法之一。它解决的问题很具体：给定一张栅格地图、一个起点、一个终点和一组障碍物，搜索一条从起点到终点的低代价可行路径。

在室内导航项目里，A* 通常不直接运行在高精度传感器地图上。SLAM 可能维护 2cm 分辨率地图，但规划常用 5cm、10cm 或更粗的栅格。原因很直接：格子越多，搜索空间越大，open set、closed set、父节点数组和代价数组都会占用更多 RAM。

A* 要解决的问题

先把环境离散成网格。每个格子有状态：

可通行
障碍
未知
高代价区域

然后给定起点 S 和终点 G，A* 在网格上扩展节点，直到找到一条通向目标的路径。

下面的 SVG 使用固定 10x10 网格运行 8 连通 A* 后绘制。示例参数如下：

起点：(1, 8)。
目标：(8, 1)。
障碍：(4,1)..(4,6)，(6,4)，(7,4)，(8,4)。
移动代价：正交 10，对角 14。
约束：对角移动禁止穿角。
启发函数：Octile 距离。

这个图里，灰色格子是障碍。红线来自 A* 回溯出的父节点链：

(1,8) -> (2,7) -> (3,7) -> (4,7) -> (5,7) -> (5,6)
      -> (5,5) -> (5,4) -> (5,3) -> (6,2) -> (7,1) -> (8,1)

这条路径没有进入障碍格，也没有通过对角移动穿过障碍角点。

三个代价：g、h、f

A* 的核心公式只有一个：

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

含义如下：

符号	含义	工程解释
`g(n)`	从起点走到当前格子的已知代价	已经花掉的成本
`h(n)`	从当前格子到目标的估计代价	还要花多少成本
`f(n)`	总估计代价	用来决定下一步扩展谁

A* 每次从 open set 里取出 f 最小的格子扩展。g 让搜索不乱跑，h 让搜索朝目标靠近。

h(n) 叫启发函数。它不能随便写。常见选择：

4 连通网格：曼哈顿距离。
8 连通网格：Octile 距离。
任意方向连续空间：欧氏距离。

在 8 连通栅格里，正交移动代价常设为 10，对角移动代价常设为 14，因为 14 近似 10 * sqrt(2)。这样可以用整数代价避免浮点。

open set 和 closed set

A* 维护两类集合。

open set：已经发现，但还没有扩展的格子。
closed set：已经扩展过，不需要重复处理的格子。

每一轮循环：

从 open set 取出 f 最小的格子。
把它放入 closed set。
检查它的相邻格子。
如果相邻格子可通行，计算新的 g、h、f。
如果这条路更便宜，更新该格子的父节点。
到达目标后，从目标格沿父节点回溯出路径。

open set 通常用最小堆实现。每次取 f 最小节点的复杂度是 O(log N)，比每轮扫描整个数组更适合大地图。

4 连通和 8 连通

4 连通只能上下左右移动。8 连通允许对角移动。

连通方式	可移动方向	适合场景
4 连通	上、下、左、右	机器人不能斜穿格子，路径更保守
8 连通	上、下、左、右、四个对角	路径更短，更接近真实移动

8 连通要处理一个额外问题：对角线穿角。如果两个正交相邻格子都是障碍，机器人不能从它们之间斜穿过去。工程实现通常会禁止这种对角移动。

障碍  可走
可走  当前

从“当前”斜走到左上角时，左侧和上侧至少要有足够通道，否则会擦过障碍角。

障碍膨胀和代价地图

真实机器人有尺寸。即使某个格子没有障碍，贴着障碍边走也可能碰撞。因此规划前通常会做障碍膨胀。

障碍膨胀的做法是：把障碍周围若干格标成高代价区域。离障碍越近，代价越高。

代价地图会进入 g(n)。路径如果靠近障碍，虽然几何距离短，但总代价可能更高。这样 A* 会倾向于选择更安全的路线。

A* 的基本伪代码

open_set.push(start);
g[start] = 0;
parent[start] = none;

while (!open_set.empty()) {
    current = open_set.pop_min_f();

    if (current == goal) {
        return rebuild_path(parent, goal);
    }

    closed[current] = true;

    for each neighbor of current {
        if (neighbor is obstacle || closed[neighbor]) {
            continue;
        }

        tentative_g = g[current] + move_cost(current, neighbor) + cell_cost(neighbor);

        if (neighbor not in open_set || tentative_g < g[neighbor]) {
            parent[neighbor] = current;
            g[neighbor] = tentative_g;
            h[neighbor] = heuristic(neighbor, goal);
            f[neighbor] = g[neighbor] + h[neighbor];
            open_set.push_or_update(neighbor, f[neighbor]);
        }
    }
}

return no_path;

工程实现里还会额外处理：

起点或终点落在障碍上。
目标附近容差，不要求精确到某个格子。
open set 容量上限。
路径数组长度上限。
旧路径亲和度，减少重规划抖动。
未知区是否允许通行。

在嵌入式导航里的取舍

嵌入式项目里，A* 的关键约束是内存和时间预算。

以 40 x 40 规划图为例，只有 1600 个格子。可以为每个格子准备：

g_cost
parent
state
heap_index
cell_cost

这些数组可以静态分配，避免动态内存。

如果直接在 200 x 200 地图上搜索，节点数量变成 40000。RAM、open set 和最坏搜索时间都会明显上升。NoeticMaze 这类 MCU 项目通常会保留一张高精度 SLAM 图，再降采样出低分辨率规划图。

A* 的边界

A* 只负责在当前代价地图上搜索路径。

它不负责：

感知障碍。
估计机器人位置。
控制电机。
修正地图漂移。
预测动态障碍物。

它依赖上游模块提供正确地图，依赖下游控制器跟踪路径。地图错了，A* 会在错误地图上认真搜索；控制器跟踪不好，路径再合理也无法稳定执行。

总结

A* 的核心可以压缩成一句话：每次扩展 f(n)=g(n)+h(n) 最小的候选格子，并用父节点记录最便宜的来路。

在机器人导航里，真正需要工程化处理的是栅格分辨率、代价地图、障碍膨胀、open set 数据结构、路径平滑和重规划稳定性。算法本身不复杂，复杂的是把它放进有限 RAM、有限 CPU 和真实底盘误差里运行。

本文由 AI 辅助生成，可能存在错误或遗漏，请以实际资料和官方文档为准。