Hybrid A*
- 又称: Hybrid A-star, hybrid-state A*
- 类别: Planning & manipulation › Motion planning
- 标签: path-planning, graph-search, autonomous-driving, nonholonomic, parking
A* 搜索的一种变体,面向类车机器人:它在连续状态中模拟可行的转向运动来扩展节点,同时用粗的 (x, y, 航向) 栅格进行剪枝。
定义
Hybrid A 是一种面向具有非完整约束的车辆的基于搜索的路径规划器,由 Dolgov、Thrun、Montemerlo 和 Diebel 为斯坦福大学参加 2007 年 DARPA 城市挑战赛的参赛车辆提出,在比赛中用于处理停车场和其他非结构化区域。与标准 A 一样,它维护一个按代价加启发值排序的开放列表。区别在于状态的表示方式。搜索空间按位置和航向划分为单元格,但每个节点都保存一个精确的连续位姿。扩展一个节点时,会以几个转向角(例如向左打满、直行和向右打满),向前行驶,并在允许时倒车,对车辆进行一小段弧线的模拟,通常使用运动学自行车模型**。只有当新位姿所在的单元格尚未以更低代价到达过时,它才会被保留。
由于每条边都是一段模拟运动,所得路径天然可行驶,而基于单元格中心的普通栅格 A 无法做到这一点。代价是按单元格剪枝会丢弃一些本可能通向解的状态,因此该规划器在严格意义上既不完备也不最优;粗的单元格使它很快,但可能让它错过狭窄空间中的机动。原始方法使用两个可采纳的启发函数并取较大者:不考虑障碍物时汽车的最短路径长度,例如 Reeds–Shepp 路径或 Dubins 车**路径;以及对一个可以原地转向的机器人,在栅格上做 2D 搜索得到的考虑障碍物的最短路径。它还会周期性地尝试用一条 Reeds–Shepp 曲线把当前节点直接连到目标,这称为解析扩展,有助于搜索到达精确的目标位姿。
原始路径沿离散的转向选择行进,因此会略呈锯齿状。原始系统用一个基于梯度的优化器对其进行平滑,在间隙、曲率和平滑度之间取得平衡,然后为跟踪控制器进行插值。Hybrid A 不同于状态格规划(它用预先计算的运动基元**连接固定的格点),也不同于假定存在参考车道的 Frenet 坐标系规划器。
为何重要
Hybrid A* 是在停车场、堆场和其他没有车道的空间中,最广泛用于类车机器人的规划器之一。它展示了一种把栅格搜索的速度与符合车辆转向极限的路径结合起来的实用方法,而且它的结构出现在许多开源驾驶软件栈中。
主要应用
- 自动泊车和代客泊车机动
- 卡车、牵引车和挂车在堆场和场站中的调车
- 仓库、农场和建筑工地中的类车机器人
- 自动驾驶软件栈中非结构化区域的规划
- 越野车辆和矿用车辆的路径规划
实际应用
一台自动牵引车必须倒车进入装卸位。规划器把堆场离散化为位置单元格和航向区间,使用自行车模型以向前和向后的几个转向角扩展节点,并在每个模拟位姿处检查车辆完整轮廓的碰撞。每扩展几次,它就尝试一次直接到装卸位位姿的 Reeds–Shepp 连接。一旦找到路径,就对其按曲率和间隙进行平滑、重新做碰撞检查,并赋予速度曲线,然后由路径跟踪控制器驱动执行。当规划器在狭窄处失败时,团队首先减小单元格尺寸或增加转向角,然后才改动其他任何东西。
常见误解
- Hybrid A 就是栅格上的普通 A — 节点保存由模拟转向运动到达的连续位姿,栅格只用于剪除重复状态
- 由于栅格的存在,它的路径可能在运动学上不可行 — 边是模拟的车辆运动,因此可行性成立;栅格牺牲的是完备性和最优性
- Hybrid A* 给出最短路径 — 单元格剪枝和有限的转向选择意味着结果是近似的,通常随后还要平滑
- 它规划带速度的完整轨迹 — 它规划的是几何路径;速度曲线和动力学是之后处理的
谁需要了解
- 从事泊车和非结构化区域的自动驾驶工程师
- 使用类车或 Ackermann 平台的移动机器人开发者
- 学习基于搜索的规划的运动规划学生
- 农业、采矿和物流领域的野外机器人工程师
相关技术
- A* 搜索
- Reeds–Shepp 曲线
- 状态格规划器(state lattice planner)
- Voronoi 场(Voronoi field)
- 路径平滑(path smoothing)
- 纯追踪(pure pursuit)与 Stanley 控制器
相关术语
- Nonholonomic Constraint
- Dubins Car
- Bicycle model
- Motion Primitive
- Configuration Space
- Frenet Frame Planning
相关项目
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
- Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots
- Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
- Vision Pilot: Autoware Foundation's open-source L2 ADAS stack from a single camera