一、算法概述：什么是基于采样的路径规划？为什么需要它？

大家好，欢迎来到这门课。今天咱们聊聊基于采样的路径规划。

说实话，我第一次接触这个概念时，心里也犯嘀咕：路径规划不就是找条路吗？图搜索算法不是挺好的？后来在实际项目中碰了壁，才明白为什么这个领域会诞生出这么一套全新的方法论。

1.1 传统图搜索算法的困境

先说说我们熟悉的图搜索算法，比如 Dijkstra、A*。这些算法的核心思路是：把空间离散化成网格或节点，然后在图上搜索最优路径。

听起来很合理对吧？但问题出在哪儿呢？

维度灾难。你想想看，一个二维的 1000×1000 网格，就有 100 万个节点。如果扩展到三维空间，或者加入机器人的姿态（比如 6 自由度机械臂），状态空间会爆炸式增长。我曾经做过一个 6 自由度机械臂的路径规划项目，如果用 A* 去搜，状态空间大到连存储都成问题，更别说实时计算了。

另一个问题是：很多真实场景中，我们并不需要精确的最优解。比如让机器人从 A 点走到 B 点，只要不撞墙、路径合理就行，没必要非得是数学意义上的最短路径。图搜索算法为了找到最优解，往往要遍历大量节点，这在复杂环境中非常耗时。

1.2 基于采样的路径规划：换个思路

基于采样的方法，说白了就是：我不去精确建模整个空间，而是随机撒点，看看能不能连出一条路。

这听起来有点粗糙，但效果出奇的好。为什么呢？

• 不需要显式构建障碍物边界：只需要一个碰撞检测函数，判断某个点或某条边是否在障碍物内。这在复杂环境中非常实用。
• 计算复杂度与维度关系不大：采样点的数量主要取决于空间的「复杂度」，而不是维度。所以高维空间下，基于采样的方法往往比图搜索快几个数量级。
• 概率完备性：只要采样点足够多，最终一定能找到路径（如果存在的话）。虽然不保证最优，但工程上够用了。

我记得有一次做无人机航迹规划，环境中有大量不规则障碍物。如果用 A*，得先把空间网格化，然后标记每个格子是否被障碍物占据——光这一步就够头疼的。而用基于采样的方法，我只需要写一个碰撞检测函数，然后让算法自己去探索。嗯，那种感觉就像从「手绘地图」升级到了「盲人摸象，但摸得足够快」。

1.3 与图搜索算法的对比

咱们来做个直观的对比，这样你心里更有数：

对比维度	图搜索算法（A*等）	基于采样的算法（PRM、RRT等）
空间表示	需要离散化（网格、路图）	不需要显式离散化
最优性	保证找到最优解	通常不保证最优，但可渐进优化
高维空间	维度灾难，计算量爆炸	受维度影响小，适合高维
障碍物处理	需要精确建模障碍物	只需要碰撞检测接口
实时性	离线预处理后较快	在线采样，可随时中断
适用场景	低维、静态、需要精确路径	高维、动态、复杂障碍物

看到这个表格，你可能会问：那是不是基于采样的方法就全面优于图搜索？

当然不是。我个人的经验是：没有银弹。如果你的问题空间是二维的、障碍物规则、对最优性要求高，那 A* 依然是很好的选择。但如果你面对的是高维空间、复杂障碍物、或者需要实时响应，那基于采样的方法会让你少掉很多头发。

1.4 一个简单的例子帮你理解

想象一下，你在一片漆黑的房间里找出口。

图搜索的思路：先把房间画成网格，每个格子标记是空地还是障碍物，然后用算法算出最短路径。但画网格本身就很费时，而且如果房间里有家具，网格的精度很难把握。

基于采样的思路：你闭上眼睛，随机朝一个方向走几步，如果撞墙了就换个方向。重复这个过程，直到摸到门。虽然路径可能不是最短的，但你很快就能找到出口。

说白了，图搜索是「先看清再走路」，基于采样是「边摸边走」。在复杂环境中，后者往往更实用。

1.5 避坑指南

最后分享一个我踩过的坑。

我曾经在一个项目中，直接用 RRT 算法做机械臂的路径规划。结果发现算法经常在狭窄通道里卡住，采样点总是落在障碍物上。后来才意识到，均匀随机采样在狭窄通道中效率极低——因为狭窄通道占整个空间的比例太小了。

解决方案是引入启发式采样，比如在目标点附近增加采样密度，或者使用桥测试（bridge test）来识别狭窄通道。这些技巧我们后面会详细讲。

好了，这一章我们聊了基于采样路径规划的基本概念、为什么需要它，以及它和图搜索的区别。下一章，我会带大家深入 PRM（概率路图）算法的细节，看看它到底是怎么工作的。

记住：理解思想比记住代码更重要。这些算法的核心逻辑其实很简单，别被复杂的数学公式吓到。