路径规划与避障调参开发与调试 - 第3节

一、启发式权重：A*的灵魂调节旋钮

A*算法的核心，说白了就是两个代价的博弈：g(n)（已经走过的路）和h(n)（预估还要走的路）。启发式权重就是给这个博弈加个砝码。

1.1 权重w的数学本质

标准A*的代价函数是：f(n) = g(n) + h(n)。加了权重后变成：f(n) = g(n) + w * h(n)。

w=1时，就是标准A*，保证最优解。w>1时，算法会更「激进」——更相信启发式估计，直奔目标。w<1时，算法更「保守」，倾向于多探索。

我个人习惯把w叫做「贪婪系数」。w越大，路径越直，但可能绕远路。w越小，路径越优，但搜索范围爆炸。

1.2 动态权重策略

固定权重太死板了。我在项目中用过一种动态调整策略：

// 动态权重示例
float dynamicWeight(Node* current, Node* start, Node* goal) {
    float progress = distance(current, start) / distance(start, goal);
    // 前期探索，后期收敛
    return 1.0 + 0.5 * (1.0 - progress);
}

嗯，这里要注意：动态权重的变化曲线要平滑。我曾经试过阶跃式的切换，结果路径出现诡异的抖动。

1.3 权重对路径形态的影响

权重w	路径特点	搜索节点数	适用场景
0.5 - 0.8	最优路径，但弯曲	非常多	高精度需求
1.0	标准A*路径	中等	通用场景
1.2 - 1.5	路径较直，略绕	较少	实时性要求高
2.0+	非常直，可能穿障碍	很少	紧急避障

二、搜索邻域：决定路径的「视野」

邻域选择说白了就是：每次扩展节点时，看周围哪些邻居。这直接影响路径的平滑度和搜索效率。

2.1 4邻域 vs 8邻域 vs 16邻域

4邻域只能上下左右走，路径全是直角转弯。8邻域加了对角线，路径更自然。16邻域再加了「跳马步」，路径更灵活。

你想想看，8邻域是最常用的。为什么？因为4邻域路径太僵硬，16邻域又太费计算。8邻域是个不错的平衡点。

// 8邻域偏移量
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

2.2 邻域选择的实际影响

我在做仓储机器人时发现一个有趣的现象：8邻域在空旷区域表现很好，但在狭窄通道里，路径会「蹭墙」。后来我改用了自适应邻域——在开阔处用8邻域，在狭窄处自动切换到16邻域。

三、路径平滑与剪枝：让机器人走得更优雅

A*出来的原始路径，说白了就是一堆离散点。直接让机器人沿着走，你会看到一顿一顿的抖动。必须做平滑处理。

3.1 冗余点剪枝

最简单的剪枝：如果三个点共线，去掉中间那个。更高级的：用射线法检查两点之间是否无障碍，如果有，就跳过中间所有点。

// 简单剪枝算法
vector<Point> prunePath(vector<Point>& path) {
    vector<Point> result;
    result.push_back(path[0]);
    for (int i = 1; i < path.size() - 1; i++) {
        if (!isCollinear(path[i-1], path[i], path[i+1])) {
            result.push_back(path[i]);
        }
    }
    result.push_back(path.back());
    return result;
}

3.2 曲线平滑

剪枝后路径还是折线，需要用曲线拟合。我常用的是三次样条插值或者贝塞尔曲线。注意控制点不能太多，否则计算量太大。

四、内存与效率：鱼和熊掌的博弈

A*的内存消耗主要在open list和closed list上。地图越大，内存越吃紧。我见过有人用1000x1000的栅格地图，open list里塞了几十万个节点，直接内存溢出。

4.1 数据结构的选择

数据结构	插入	取出最小	更新	内存占用
二叉堆	O(log n)	O(log n)	O(log n)	低
斐波那契堆	O(1)	O(log n)	O(1)	高
配对堆	O(1)	O(log n)	O(log n)	中

我个人习惯用二叉堆。虽然理论上不是最快的，但实现简单，稳定性好。斐波那契堆虽然快，但常数太大，小地图反而更慢。

4.2 内存优化技巧

• 位图存储：用bit来标记节点状态，而不是用bool数组。能省7/8的内存。
• 延迟扩展：不要一次性把所有邻居都加入open list，按需扩展。
• 分层搜索：先粗粒度搜索，再细粒度优化。我在地铁站导航项目中用过，内存占用降低了60%。

五、知识体系总览

下面这张图总结了A*深度调参的核心脉络：

调参这件事，没有银弹。每个项目都有自己的脾气。我做了这么多年机器人，最大的体会就是：多试、多测、多记录。把每次调参的结果记下来，慢慢就能找到感觉。

可可精品资料库