路径规划问题就是把机器人的工作环境量化的描述出来，让机器人知道哪里可以走，哪里不可以走，从而规划出一条可行的轨迹，并且对于轨迹本身进行优化
环境的描述
对于环境的描述，我们一般使用两种方法——Grid map 和 Feature Map
这两种map的方法实际上是互补的
，
一般来讲：我们会维护两种地图
，用grip map和feature map来相互映射
Grid Map
有地方也叫configuration space
grid map就是比较直观，把所有障碍物表示成黑色的pixel，可通行区域就是白色
但在比赛中是会有一些加成区域和惩罚区域 (灰色)
优势：
- 能够直接进行规划,生成路径。
- 可以很好的表示地图上各个区域空间附加信息；如代价，概率分布等信息
缺点：
- 真正有用的信息十分稀疏。
- 内存占用随着地图精度的增加而大幅上升
- 无法理解地图中的语义信息
无法理解地图中的语义信息指的是我们在grip map中，不知道障碍块是什么材质的，木头的、铁的、可不可以移动，这个障碍物是静止的还是敌方的机器人
要合理利用grid map的精细度
可能是粗糙的全局地图+精细的局部地图
Feature Map
其实说它是map是不太准确的，它就是一个字典，存储各个物体的位置与几何描述
优点
- 对于每一个物体的几何形状的描述和位置的描述都是无限精细的。
- 没有额外的空间占用
- 保留各个障碍物的语义信息。能够区分障碍块和对方机器人。
缺点
- 无法直接进行路径规划
- 无法表示空间分布。
全局路径规划
最优路径规划
直接用grid map
①Dijkstra
②A*
关键点是我们知道一些额外的信息，类似有上帝视角，而不是只是作为一个图的探索者
f(n) = g(n) + h(n)
g(n)可以看做从start到current所花费的cost，h(n)从current到end的花费。
A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。
由于其简便性，A* 算法在移动机器人平台上被广泛的运用，ICRA 比赛的官方代码就是使用这种思路；
但是A* 算法的稳定性非常差。而且无法适用于比较精细的地图
概率路径规划
即基于采样的规划算法
概率性的算法，并不能保证求到最优解
PRM算法
Probabilistic Roadmaps 随机路标图
概率完全、渐进最优
PRM算法及其变种就是在原始地图上进行撒点，抽取roadmap在这样一个拓扑地图上进行规划
优点
- 1. PRM可以被重复使用
- 2. 相较于A* on grid map 更快
缺点
- 1. 每次地图发生动态变化，图都需要重构。
- 2. 渐进最优；概率完全
RRT算法
Rapidly-exploring Random Tree 快速探索随机树
概率完全
实质上只是一种连通算法，不算是优化算法，但是比起PRM构图更快，更灵活，非常适合在复杂，动态地图上进行规划
RRT以及其优秀的变种RRT-connect则是在地图上每步随机撒一个点，迭代生长树的方式，连接起止点为目的，最后在连接的图上进行规划
比较玄学
上个世纪被提出，但是近些年才被接收并使用
