一、前言

       建议在阅读该文章之前阅读文章《入门导航规划概念》。以驾驶汽车时使用手机地图进行导航为例，路径规划指的是：当我们输入目标地点，手机APP软件会基于已经建模的地图给我们规划出最优路线（最短距离或者最小时间）。

二、路径规划概念

（一）路径规划基本概念

定义：根据所给定的地图和目标位置，规划一条使机器人到达目标位置的路径。

因此路径规划考虑的是全局的战略问题。考虑到机器人的各种形态和各种各样运动学模型，因此只考虑工作空间的几何约束，不考虑机器人的运动学模型和约束，即将机器人抽象为一个点，工作空间转化为位形空间。

（二）工作空间与位形空间

1、工作空间：移动机器人上的参考点能到达的空间几何，机器人采用位置和姿态描述，并考虑体积。工作空间包括障碍物空间和自由空间

（1）障碍物空间：不可行的位形集合。在该空间中，机器人会与障碍物发生碰撞

（2）自由空间：可行的位形集合。在该空间中，机器人将无碰的安全移动。

2、位形空间：机器人称为一个可移动点，不考虑姿态、体积和非完整运动学约束。

3、二者转化：

因此，路径规划就是在自由位形空间中为机器人寻找一条路径，使其从初始位置运行到目标位置。

（三）路径规划方法

       路径规划首先将连续环境模型转换成适合于所选路径规划算法的离散拓扑连通图，然后在离散拓扑连通图上生成最优路径。为什么构建离散拓扑连通图呢？原因如下：

       （1）路径规划生成一条机器人到达目标点的路径，因此要对路径存在性进行判断（路径是否经过障碍物），而连通性是拓扑空间的基本属性。

       （2）原始环境地图模型尺寸过大，导致耗费时间长，计算复杂度高，因此将空间离散化，缩小搜索空间。

因此路径规划可以总结为两个基本问题：拓扑连通图构建+最优路径搜索。