算法 | 路径规划之概率路线图（PRM）算法

概率路线图（Probabilistic Roadmaps）

简介

概率路线图（PRM）是基于可用空间和占用空间的给定地图内可能路径的网络图。概率路线图法(PRM)将规划分为两个阶段：学习阶段和查询阶段。在学习阶段，建立一个路线图(Q_{free})；在查询阶段，利用搜索算法在路线图上寻找路径。

一个质点机器人在二维欧氏空间的路线图示例。

（来源：《Principles of Robot Motion: Theory, Algorithms and Implementations》Fig. 7.3）

PRM这种基于图搜索的方法，它将连续空间转换成离散空间，再利用A*等搜索算法在路线图上寻找路径，以提高搜索效率。这种方法能用相对少的随机采样点来找到一个解，对多数问题而言，相对少的样本足以覆盖大部分可行的空间，并且找到路径的概率为1（随着采样数增加，P（找到一条路径）指数的趋向于1）。显然，当采样点太少，或者分布不合理时，PRM算法是不完备的，但是随着采用点的增加，也可以达到完备。所以PRM是概率完备且不最优的。

其建立路线图的步骤如下：

（来源：《Principles of Robot Motion: Theory, Algorithms and Implementations》）

一开始，图(G=(V,E))是空的。然后，在配置空间重复采样。这时假定采样是遵守均匀分布。把不碰到障碍的配置加入到路线图中。一共采样(ｎ)次。PRM路径规划器通过使用空闲空间中的随机采样节点并将它们彼此连接，在指定地图的空闲空间中构建路线图。路线图建立后，用户可以在路线图上查询从指定起点到指定终点的路径。

改进算法

• PRM*

参考

1. 《Principles of Robot Motion: Theory, Algorithms and Implementations》7.1.
2. 《Planning Algorithms》， 5.6 Roadmap Methods for Multiple Queries.
3. https://ww2.mathworks.cn/help/robotics/ug/probabilistic-roadmaps-prm.html
4. https://www.cnblogs.com/21207-iHome/p/7209954.html
5. https://blog.csdn.net/DinnerHowe/article/details/80267062
6. Code for Robot Path Planning using Probabilistic Roadmap