路径规划

Path Planning常用

在不碰撞的前提下，找出从起点到终点要经过的一串位置或姿态。

路径规划是给定环境、起点和终点，算出一条无碰撞几何路线的问题，常与「运动规划」混用，也被称为「钢琴搬运工问题」。严格说，路径只描述依次经过哪些位形（位置和姿态的组合），不含时间；给路径配上每一时刻的速度和加速度才是轨迹，这一步叫轨迹规划或时间参数化。常见算法分三类：栅格搜索（A*、Dijkstra），适合二维地图导航；基于采样的方法（PRM、RRT），适合机械臂这类高维构型空间；人工势场法，简单但容易困在局部极小值。移动机器人通常先做全局路径规划，再让局部规划器边走边避障。