A* 算法
在讲A*算法之前，需要先了解一下机器人最终的路径规划是如何产生的。
还记得求最短路的dijkstra算法吗，dijkstra算法同样可以使用在AI挑战赛中，但是dijkstra算法是一个广度优先的算法，为了求到最短路，运算量很大，是为了求解最短路而设计的，往往我们在实际使用中，并不需要求最短路，多开一点也无妨，假如能多开一点换来巨量的运算量减少，那将血赚，于是深度优先的A-Star全局路径规划算法就被选中了。
上图是ros自带的move_base功能包，里面提供了路径规划与导航的功能，它的路径规划思路是先由全局规划器使用A*或dijkstra算法求解出全局路径（定下大方向，大计划），然后再由局部规划器读取全局路径，规划几步（一步一步实现大计划）并优化这几步，保证这几步当中，不磕磕碰碰，不飞车飘移，走得稳稳重重，安全到达目标。
dijkstra算法中，每一个被更新点的选取，是依照当前点到源点的实际距离，选取最小值，不断更新，直到汇点作为最小点被选中，这保证了路径的最短性。
A*算法与dijkstra很相似，不过选取点的时候，是依照当前点到汇点的估算距离，选最小值，不断更新，直到汇点作为最小点被选中，这保证了每一次选取的时候都从离汇点最近的点开始走，是一种贪心算法，减少了大量不必要的运算，但不能保证得到的路径是最短的。
由上图可见，A*算法确实减少了很多的运算量。
于是我们需要定义一个估算距离，它由当前的实际距离和启发函数得出。
估算距离F = 当前点距离源点的距离G + 使用启发函数计算得的当前点到汇点的估算距离H启发函数可以使用欧几里得距离、曼哈顿距离、对角距离等。
- 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离（Manhattan distance）。
- 如果图形中允许朝八个方向移动，则可以使用对角距离。
- 如果图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）。
由于曼哈顿距离是计算最快的，我们继续以曼哈顿距离做启发函数为例，当然，实际使用哪一个做启发函数，可以多次调试。
曼哈顿距离
曼哈顿距离就是两点x，y坐标差的绝对值之和。如(1, 3) 到 (2, 2)的曼哈顿距离为 2。
只需要计算两次减法一次加法，曼哈顿距离运算相当简便。
在实际比赛中，虽然车辆可以多个方向移动，但也可以使用曼哈顿距离作为启发函数。
A*模拟如上。
有了以上的分析，可以发现代码与dijkstra是很相似的，只需要将按实际距离排序部分更改为按估算距离排序取点即可。
