Hybrid A*

An A* variant that searches over a grid but tracks a vehicle's continuous position and heading, so the resulting path is actually drivable.

Hybrid A* was designed by Dolgov, Thrun, and colleagues for Stanford's self-driving car Junior, for the 2007 DARPA Urban Challenge. Plain A* just hops between grid-cell centers, giving a jagged path a car can't actually follow, since a car can't turn in place (a nonholonomic constraint). Hybrid A* instead searches over position x, y, and heading θ: grid cells are still used to deduplicate nodes, but each node keeps the vehicle's true continuous pose; expansion simulates a short arc using a handful of fixed steering angles (including reverse), each consistent with the vehicle's kinematics. The heuristic takes the larger of two estimates: the shortest distance ignoring obstacles but accounting for turning ability, and the shortest grid distance accounting for obstacles but ignoring heading; the final path is smoothed with numerical optimization. It's commonly used for parking and three-point turns.

ExampleJunior used it in the competition to back into parking spots and make U-turns on blocked roads, with the paper reporting a full replan taking roughly 50–300 milliseconds. ROS 2's Nav2 navigation framework also provides a Hybrid-A* implementation in its Smac Planner, aimed at Ackermann-steered, car-like bases.

Also called

Hybrid-A*

Related

A* Search · Nonholonomic Constraint · Path Planning · Kinodynamic Planning · Path Smoothing (Shortcutting) · Autonomous Driving

Sources

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)