Hybrid A* for Car-Like Robots

Plain A* on a grid gives paths with sharp turns that a car cannot drive. Hybrid A* keeps the speed of grid search but expands each node with short arcs the car could actually drive, forward and backward, at a few steering angles. Each node stores its exact continuous pose, while the grid only decides what counts as already visited.

Max steering angle Allow reversing Reverse penalty

The search

Each node is a continuous pose $(x, y, \theta)$. Expanding it drives a short arc with each steering choice, forward and, if allowed, backward. A node is skipped if its grid cell and heading bin were already visited. The cost adds arc length, with extra cost for reversing and for switching direction, and the heuristic is the straight-line distance to the goal:

$$f = g + h, \qquad g = \sum \ell_i\,(1 + [\text{reverse}](\rho - 1)) \qquad h = \lVert \mathbf{x} - \mathbf{x}_g\rVert$$

What to notice

The final path is drivable, since it is made only of arcs and straight pieces with the car's turning limit. To get into the slot it backs in, which needs reversing. Turn reversing off and it must find a forward-only way in, which may be much longer or fail. Stanford's car in the 2007 DARPA Urban Challenge used Hybrid A*, and it is still common for parking and for robots in tight spaces.