MATLAB算法实战应用案例精讲-【采样路径规划算法】PRM算法（附MATLAB、C++和Python等源码）
前言
路径规划作为机器人完成各种任务的基础，一直是研究的热点。研究人员提出了许多规划方法：如人工势场法、单元分解法、随机路标图（PRM）法、快速搜索树（RRT）法等。传统的人工势场、单元分解法需要对空间中的障碍物进行精确建模，当环境中的障碍物较为复杂时，将导致规划算法计算量较大。基于随机采样技术的PRM法可以有效解决高维空间和复杂约束中的路径规划问题。
1.算法原理
机器人运动规划的基本任务可以描述为：从开始位置到目标位置的运动。这一任务通常涉及到两项基本问题：
- 如何躲避构型空间中出现的障碍物（几何路径规划）
- 如何满足机器人本身在机械、传感方面的速度、加速度等限制（不确定性、反馈、微分约束等）
其中，基于抽样的运动规划算法是用于解决第 1 个问题的重要方法，其核心思想为：先对机器人的单个构型进行碰撞检测，建立无碰撞构型的数据库，再对不同的构型进行采样以生成无碰撞路径。该算法的优点在于具有通用性，只需要针对不同的机器人运动规划问题进行合理的参数调整。该算法的缺点在于完备性较弱，即当参数设置不合理时，即使存在可行的路径，也不一定能够找到。
典型的抽样规划方法有综合查询方法和单一查询方法两类。前者首先构建路线图，先通过采样和碰撞检测建立完整的无向图，以得到构型空间的完整连接属性。再通过图