基于采样的规划算法之概率路图（PRM）法

概率路图（Probabilistic Road Map, PRM）法严格意义上只是一种构建规划问题图(graph)的方法，在目的上与前面介绍的可视图、Voronoi图一样。在构建完规划问题图(graph)后，还得需要图搜索算法搜索规划问题图的最短路径解。但是，从方法层面，概率路图法采用随机采样的方式来构建规划问题图，也可归为基于采样的规划算法一类。鉴于PRM方法兼具图搜索与采样方法的特性，我将之作为采样方法的第一篇，有承上启下之意。

一、背景

环境感知结果一般由连续空间中的（凸）多边形表示（当然也存在直接利用点云数据构建栅格地图的，不过应用场景大多为野外驾驶场景），下面两张图分别为基于可视图与Voronoi图法得到的规划问题图（graph）。

可视图法以各代表障碍物形状与大小的多边形的顶点为节点；Voronoi图法以代表障碍物的多边形顶点构建维诺图，并以该维诺图的多边形顶点作为节点。它们步骤中都包含了检查特定两节点之间的连线是否穿过障碍物，保证规划的路径是无碰撞的。可视图法与Voronoi图法的共同步骤都包含：找到节点，并检测特定两节点之间是否直线可达，若可达则在这两个节点间添加一条边。

可视图法还好，直接以障碍物多边形的顶点作为节点。Voron