总结课程《深蓝学院移动机器人路径规划》

深度优先遍历：栈
广度优先遍历：队列

1.Dijkstra

Dijkstra = 广度优先遍历 + 权重

在Dijkstra 算法中，相当于在每条路径上添加了权重。在每次弹出扩展点的时候，需要计算代价函数g(n)最小的节点。如果通过该节点所扩展得到的邻居节点并不在容器中，则需要直接添加进去。如果已经存在在容器中，则需要对比从该节点出发所得到的代价是否比其原有代价更小。

代价函数：f(n)=g(n)

2. A*

A*= Dijkstra + 启发式

Dijkstra算法仅仅考虑了从起始点出发的累计代价g(n)，当考虑从路标点到目标点之间的代价h(n)，即类似贪心算法，则为A*算法。
此时与Dijkstra算法考虑的代价则不同，其他则一样。

代价函数：f(n)=g(n)+h(n)

如何保证A*算法的最优质：
估计的启发式函数cost < 真实cost ，
即对于任何一个节点，h(n)<h*(n)。例如使用欧式距离作为启发式函数！

3.Weighted A*

如果h(n)>=h*(n)，可以理解为A*算法在往贪心算法演变，即尽可能的往目标点移动。

代价函数：f(n)=g(n)+$\epsilon$h(n)
当$\epsilon >1$，则朝着目标点更近的方向规划
当$\epsilon =0$， Dijkstra 算法
当$\epsilon =1$， A*算法
并且存在：当前cost <= $\epsilon$最优cost

4.最佳启发函数

启发式函数代价需要小于真实的代价，那么当其相等的时候，就是最佳的启发式函数。例如在一个二维的栅格地图中：


如果用两者的最小距离，即对角的启发式函数，此时所遍历的节点明显减少，三维同理。
$$dx=abs(node.x-goal.x)$$$$dy=abs(node.y-goal.y)$$$$h=(dx+dy)+(\surd 2-2)\ast min(dx,dy)$$

5.打破平衡 Tie Breaker

在一次规划中，存在很多代价一样但结果不一样的最优路径。因此会沿着多条路径同时进行扩展。

当打破对称性之后(右图)，可以明显看到所便利的节点减少。
打破对称性的方法，对相等的cost进行极小的放大。
$$h=h\times 1.0+p$$$$p<\frac{minimumcostofonestep}{expectedmaximumpathcos}$$
虽然此时启发式函数稍微大于真实的代价，但是并不影响实际的规划效果。

6.Jump Point Search

系统性的消灭对称性问题！

JSP = A* + 消灭对称性问题

Look Ahead Rule

如果从该节点出发，到达其父节点可到达的节点的代价，大于等于从其父节点出发的代价，则该目标节点不需要考虑。
即上图中白色节点，则需要被考虑。红色节点因为存在障碍物需要被强制考虑。

Jumping Rules

直线跳跃优先级大于对角线跳跃