本文课件来自香港科技大学，我的母校，感谢ELEC

本节介绍A算法中的打破路径对称性的几种方法，在工程实践中有一定的参考意义。

根据上图，我们举一个简单的例子，可以看到，同样的A算法，我们在采用了不用的h启发函数后，搜索的效率是不同的，第二个A*中，我们对h进行了一定的放大，发现搜索区域缩减了很多，搜索效率提高。

值得注意的是，虽然我们的启发函数已经不符合我们之前讲的要求：h<=h*, 但是，工程中，由于障碍物的存在，这个真实的h是远大于h*的，所以对h稍作放大完全不会有太大印象。另一个重点是启发式函数的选择，尽量要和真实的h cost 相近，比如下图：

前一个图我们采用了对角距离，也就是下图的距离计算方法：

来作为启发式函数，而不是用L2 norm来作为启发式函数，显然，对角距离更符合这个情况中的真实距离的表达方式，因此计算效率更高。
另外，还有两个常用的方法，第一，当cost function相同时，我们还可以选择h较小的那个最为优先选项。 第二，我们引入一个cross最为cost function 中的一部分，意思是我们更加倾向于走直线，而不是走折线。

如图所示，这里的cost function 就变成了
h=ℎ+𝑐𝑟𝑜𝑠𝑠×0.001

当然，tie breaker 也是有缺点的，打破了路径对称性后，比如做一个绕障的行为，我们的期望轨迹可能是：

显然，我们的期望轨迹是很难实现的，我们希望它和红色的轨迹尽量相似，做平滑处理的时候才更加方便，所以tie breaker也给我们带来了一些麻烦，这时候有一个高阶的图搜索算法JPS跳点搜索可以解决这个问题。详见全局路径规划：图搜索算法介绍4(JPS)