Hybrid A*：算法概念详解
在之前，我们一起学习了A*算法，A* 是一种用于在图或网格中寻找最短路径的启发式搜索算法。然而A*算法得到的最优路径为折线，在实际机器人的运动中，我们更希望追踪的路径为平滑的曲线。
Hybrid A*（混合 A*）是一种用于连续空间、具有非完整约束的运动规划算法，尤其适用于自动驾驶车辆或移动机器人。
1 核心思想
Hybrid A* 将 A* 的启发式搜索思想与连续状态空间的运动模型结合起来。
与普通 A* 不同，Hybrid A* 的搜索节点不仅包括位置坐标 (x,y) ，还包括车辆朝向 θ 。因此每个节点是一个三维状态：n=(x,y,θ)
这使得搜索考虑了车辆的运动学约束，即在寻找下一个搜索节点时不能单纯以相邻节点为搜索目标，要根据预先设定的采样步长，考虑转弯半径限制、不能原地旋转等因素，采样运动轨迹，并判断轨迹是否会与障碍物发生碰撞，选择满足车辆运动条件的轨迹为待选的搜索节点。
2 主要特点
2.1 实际代价函数 g
混合A*的实际代价函数g，例如Apollo中实际代价函数是一个由多目标代价线性组成的满足车辆运动学约束的值（由运动代价（包括路径弧长、转向惩罚和换挡惩罚组成）、行为代价、约束惩罚、加权合成。）
2.2 预估代价函数 h
混合A*的预估代价函数h，一般有以下几种计算方式：
1.无障碍物的非完整性约束（考虑运动学约束不考虑障碍物）：使用Reed-Sheep（RS）或 Dubins曲线连接目标点，即可得到一条考虑运动学约束但不考虑障碍物的最短路径。
2.有障碍物的完整性启发（考虑障碍物但不考虑约束）：曼哈顿距离或者迪杰斯特拉（Dijkstra）（Apollo中即采用该方法）
Dubins 距离：对于一辆只能前进、最小转弯半径为 R 的车辆，从初始状态(xs,ys,θs)到目标状态(xg,yg,θg)满足转向约束的最短路径。
Reeds–Shepp 路径：允许前后倒车、具有最小转弯半径的车辆的最短可行路径。
3 搜索流程
3.1初始化起点与目标点状态
设定 (xstart,ystart,θstart) 和 (xgoal,ygoal,θgoal) 。
3.2 定义可行控制集
一般包括一组离散转向角（如 -δmax,0,+δmax ）与运动方向（前进/后退）。
3.3 扩展节点
对每个当前节点，使用运动学模型（如简化自行车模型）计算下一个状态。：
3.4 代价计算与启发式估计、
使用与 A* 类似的 f=g+h ，其中 g 由控制输入长度累积，h 通常为到目标点的 Dubins/Reeds-Shepp 距离。
3.5 终止条件与路径回溯
当节点足够接近目标点（在一定容差范围内）时，停止搜索并回溯路径。
4 Hybrid A* 与 A* 的区别对比
注意：
混合A*算法不一定能找到到达终点的路径，这是因为经典A*算法的搜索空间可以是全空间，但是混合A*算法的搜索空间需要满足车辆动力学，无法保证遍历所有节点。
5 参考资料
[1] 03 车辆运动规划控制常用算法---混合A* - 知乎
都看到这里了，如果有所帮助，点个赞再走吧~~
不断学习，持续成长，欢迎大家一起交流学习！
