路径规划之PRM算法

系列文章目录

路径规划之Dijkstra算法
路径规划之Best-First Search算法
路径规划之A *算法
路径规划之D *算法
路径规划之PRM算法

---

---

前言

之前提到的几种路径规划算法都建立在栅格地图上，在目前A*算法比较盛行的情况下，暂时难以提出更好更稳定的静态地图搜索方法。
那如何换一种方向思考呢？在使用A *算法的前提下，我们要想提高路径规划的速度，就需要从地图方向入手，不去搜索原有的栅格地图而是去搜索基于采样点构建PRM路线图来提高路径规划效率。

一、前期准备

1.栅格地图

栅格地图是一种基于网格的地图表示方法，其中地图区域被划分为均匀的网格单元，并为每个网格单元分配特定的属性信息。

2.采样

在机器学习和统计学中，采样是从一个数据集中选取一部分样本用于模型训练或推断。采样可以是随机的也可以是确定性的，并且可以根据各种不同的采样策略进行操作。

3.路标

地图中随机选取的采样点，这些点被用作潜在路径的节点，也被称为路标。

二、PRM算法

1.起源

PRM（Probabilistic Roadmap）算法是由Steven M. LaValle和James J. Kuffner于1999年共同提出的。这是一种用于解决机器人路径规划问题的算法，特别是在复杂和动态环境中。

2.流程

1. 随机采样，在已经建立好得地图上随机选取一定数量的采样点；
2. 移除无效采样点，删除落在障碍物上的点；
3. 连接，根据最近邻规则（可以是其他规则，不同情况使用不同的规则）将采样点和周围相邻点链接；
4. 移除无效连接，将横穿障碍物的连接删除，构建出PRM路线图；
5. 使用A*算法在PRM路线图上寻找最优路径。

3. 优缺点

优点：

1. 适用于高维空间和复杂约束的路径规划问题；
2. 搜索效率高，搜索速度快。

缺点：

   概率完备但不是最优。

4. 实际效果