机器人的导航规划主要分为三部分：

• 路径规划：根据给定的地图和目标位置，规划一条使机器人到达目标位置的路径(只考虑工作空间的几何约束，不考虑机器人的运动学模型和约束)

• 避障规划：根据传感器的实时测量信息，调整路径/轨迹以避免发生碰撞

• 轨迹规划：根据机器人运动学模型和约束，确定机器人的控制指令，将可行路径转换为可行轨迹

他们之间的关系示意如下：

路径规划

不考虑机器人运动学模型和约束，将机器人抽象为空间中的点

基本概念

• 工作空间：机器人采用位姿描述，并考虑体积，机器人能达到的空间位置集合
• 位形空间（Configuration Space）：不考虑姿态、体积和非完整运动学约束，机器人成为一个可移动点
• 障碍物按照机器人半径进行膨胀，可将工作空间转为位形空间
• 常转换为拓扑连通图和最优路径搜索问题

拓扑连通图的构建

• 基本思路：对空间作离散化
• 分辨率完备resolution completeness:解析性离散化，确保获得可行解
  • 行车图法：基于障碍物集合形状分解姿态空间
  • 单元分解法：区分空闲单元和被占单元
  • 势场法：根据障碍物和目标对空间各点施加虚拟力
• 概率完备Probabilistic completeness：

基于概率进行随机采样离散化，使获得解的概率趋近于1

• PRM(Probabilistic RoadMaps)
• RRT(Rapid-Exploring Radom Trees)

最优路径搜索

• 精确最优搜索：深度优先法、宽度优先法 耗时较大
• 近似最优搜索：
  • 启发式搜索：$A$，$D$
  • 准启发式搜索：退火、进化、蚁群优化等