Open Source Robotics

A curated collection of high-quality open source robotics projects, tools, and software to propel the robotics community forward.

Hybrid A*

  • Also called: Hybrid A-star, hybrid-state A*
  • Category: Planning & manipulation › Motion planning
  • Tags: path-planning, graph-search, autonomous-driving, nonholonomic, parking

A variant of A* search for car-like robots that expands nodes by simulating feasible steering motions in continuous state while pruning with a coarse (x, y, heading) grid.

Definition

Hybrid A is a search-based path planner for vehicles with nonholonomic constraints, introduced by Dolgov, Thrun, Montemerlo and Diebel for Stanford's entry in the 2007 DARPA Urban Challenge, where it handled parking lots and other unstructured areas. Like standard A, it keeps an open list ordered by cost plus heuristic. The difference is how states are represented. The search space is divided into cells over position and heading, but each node keeps an exact continuous pose. A node is expanded by simulating the vehicle, usually with a kinematic bicycle model**, for a short arc at a few steering angles, such as full left, straight and full right, driving forward and, if allowed, in reverse. A new pose is kept only if its cell has not already been reached at lower cost.

Because every edge is a simulated motion, the resulting path is drivable by construction, which a plain grid A on cell centers cannot provide. The price is that pruning by cell discards states that might have led to a solution, so the planner is neither complete nor optimal in the strict sense; coarse cells make it fast but can make it miss tight maneuvers. The original method used two admissible heuristics and took the larger: the length of the shortest path for a car without obstacles, such as a Reeds–Shepp or Dubins car** path, and the shortest obstacle-aware path for a robot that can turn in place, from a 2D search on the grid. It also periodically tried to connect the current node directly to the goal with a Reeds–Shepp curve, called an analytic expansion, which helps the search reach an exact goal pose.

The raw path follows the discrete steering choices, so it zig-zags slightly. The original system smoothed it with a gradient-based optimizer that balanced clearance, curvature and smoothness, and then interpolated it for the tracking controller. Hybrid A differs from state lattice planning, which connects fixed lattice points with precomputed motion primitives**, and from Frenet-frame planners, which assume a reference lane.

Why it matters

Hybrid A* is one of the most widely used planners for car-like robots in parking, yards and other spaces without lanes. It shows a practical way to combine the speed of grid search with paths that respect a vehicle's turning limits, and its structure appears in many open-source driving stacks.

Key applications

  • Automated parking and valet maneuvers
  • Truck, tug and trailer maneuvering in yards and depots
  • Car-like robots in warehouses, farms and construction sites
  • Planning in unstructured areas of autonomous driving stacks
  • Off-road and mining vehicle path planning

In practice

An autonomous tug must reverse into a loading bay. The planner discretizes the yard into position cells and heading bins, expands nodes with a few steering angles forward and backward using the bicycle model, and checks the vehicle's full footprint for collisions at each simulated pose. Every few expansions it tries a direct Reeds–Shepp connection to the bay pose. Once a path is found, it is smoothed for curvature and clearance, rechecked for collisions, and given a speed profile before a path-tracking controller drives it. When the planner fails in tight spots, the team first reduces cell size or adds more steering angles before changing anything else.

Common misconceptions

  • Hybrid A is ordinary A on a grid — nodes store continuous poses reached by simulated steering motions, and the grid only prunes duplicates
  • Its paths can be kinematically infeasible because of the grid — edges are simulated vehicle motions, so feasibility holds; what the grid costs is completeness and optimality
  • Hybrid A* gives the shortest path — cell pruning and limited steering choices mean the result is approximate, usually followed by smoothing
  • It plans the full trajectory with speeds — it plans a geometric path; speed profiles and dynamics are handled afterward

Who should know this

  • Autonomous driving engineers working on parking and unstructured areas
  • Mobile robot developers with car-like or Ackermann platforms
  • Motion planning students studying search-based planning
  • Field robotics engineers in agriculture, mining and logistics

Related technologies

  • A* search
  • Reeds–Shepp curves
  • State lattice planner
  • Voronoi field
  • Path smoothing
  • Pure pursuit and Stanley controllers

Related terms

  • Nonholonomic Constraint
  • Dubins Car
  • Bicycle model
  • Motion Primitive
  • Configuration Space
  • Frenet Frame Planning

Related projects

  • 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

This website requires JavaScript to function properly. Please enable JavaScript to explore our collection of open source robotics projects.