混合 A*

在栅格上搜索、但记录车辆连续位置和朝向，保证路径车能开出来的 A* 变体。

混合 A* 由 Dolgov、Thrun 等人为斯坦福无人车 Junior 参加 2007 年 DARPA 城市挑战赛设计。普通 A* 只在栅格中心间跳，折线路径汽车开不出来，因为车不能原地转向（非完整约束）。混合 A* 在位置 x、y 和朝向 θ 上搜索：格子仍用来给节点去重，但节点记着车真实的连续位姿；扩展时按几种固定方向盘转角（含倒车）模拟开一小段，每段都满足车辆运动学。启发值取两者较大者：忽略障碍、按车辆转弯能力算的最短距离，和考虑障碍、忽略朝向的网格最短距离；最后用数值优化把路径磨平。常用于泊车、掉头等场景。

例子Junior 在比赛中用它在停车场里倒车入位、在堵路上掉头，论文报告整轮重规划耗时约 50–300 毫秒。ROS 2 导航框架 Nav2 的 Smac Planner 也提供 Hybrid-A* 实现，面向阿克曼转向的车式底盘。

也叫

Hybrid A星、Hybrid-A*、混合A星

相关

A* 算法、非完整约束、路径规划、动力学约束规划、路径平滑、自动驾驶

来源

Dolgov, Thrun, Montemerlo, Diebel: Practical Search Techniques in Path Planning for Autonomous Driving (2008)
Open Robotics Discourse: [Nav2] SmacPlanner (Hybrid-A*, 2D A*) Now Available (2020-10)