路径规划： PRM 路径规划算法 (Probabilistic Roadmaps 随机路标图)

　　随机路标图-Probabilistic Roadmaps (路径规划算法) 　　路径规划作为机器人完成各种任务的基础，一直是研究的热点。研究人员提出了许多规划方法如： 　　1. A* 　　2. Djstar 　　3. D* 　　4. 随机路标图（PRM）法 　　5. 人工势场法 　　6. 单元分解法 　　7. 快速搜索树（RRT）法等 　　传统的人工势场、单元分解法需要对空间中的障碍物进行精确建模，当环境中的障碍物较为复杂时，将导致规划算法计算量较大。  　　 　　基于 随机采样技术 的 PRM法 可以有效解决 “高维空间” 和 “复杂约束” 中的路径规划问题。 　　 　　如上图所示， 是一种基于图搜索的方法，一共分为两个步骤：，  　　它将连续空间转换成离散空间，再利用A*等搜索算法在路线图上寻找路径，以提高搜索效率。 　　这种方法能用相对少的随机采样点来找到一个解，对多数问题而言，相对少的样本足以覆盖大部分可行的空间，并且找到路径的概率为1（随着采样数增加，P（找到一条路径）指数的趋向于1）。显然，当采样点太少，或者分布不合理时，PRM算法是不完备的，但是随着采用点的增加，也可以达到完备。所以PRM是概率完备且不最优的。  　　用随机路径图（PRM）法寻找给定地图中两点之间的路径，PRM进行路径规划的步骤： 　　（1）学习阶段： 　　在给定图的自由空间里随机撒点（自定义个数），构建一个路径网络图。 　　a）构造步骤 　　b）扩张步骤 　　（2）查询阶段： 　　查询从一个起点到一个终点的路径。 　　a）局部路径规划 　　b）距离计算 　　c）碰撞检查 　　  　　PRM学习阶段包含两部分内容： 　　 　　  　　  　　文字说明 　　步骤 1～2 : 初始化两个集合，其中N：随机点集，E：路径集。 　　步骤 4 : 随机撒点，将撒的点放入N中，随机撒点的过程中： 　　1. 必须是自由空间的随机点 　　2. 每个点都要确保与障碍物无碰撞 　　步骤 5～8 ：对每一个新的节点c，我们从当前N中选择一系列的相邻点n，并且使用local planner进行路径规划 　　步骤 9～10 ：将可行驶的路径的边界（c，n）加入到E集合中，不可行的路径去掉。 　　  　　图片说明 　　  　　 　　  　　  　　  　　  　　  　　  　　  　　  　　  　　  　　  　　  　　参考： 　　Kavraki, L.E., P. Svestka, J.-C. Latombe, and M.H. Overmars. “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics and Automation. Vol. 12, No. 4, Aug 1996 pp. 566—580. 　　http://www.cnblogs.com/21207-iHome/p/6049259.html  　　endl; 　　  　　参考博客： 　　https://blog.csdn.net/DinnerHowe/article/details/80267062?tdsourcetag=s_pctim_aiomsg