---
kind: concept
slug: a-star-search
title: A* search
summary: >-
  Best-first graph search that orders states by cost-so-far plus a heuristic. Quadrotor motion-primitive planning with admissible bounds: one author-reported query expanded 376 nodes with the LQMT bound vs 2707 for Dijkstra. Other papers use A* for car-like hybrid search and kinodynamic guidance, with no optimality claim.
tags: [graph-search, heuristics, motion-planning, trajectory-generation, navigation]
papers: ["1709.05401", "2408.10618", "2412.02655", "2412.03174"]
related: [model-predictive-control, llm-tree-search, llm-planning, kinematic-bicycle-model, motion-primitives, time-optimal-control]
status: draft
updated_at: 2026-10-25
---

## Overview

A* finds a cheapest path through a graph by always expanding the frontier state
with the lowest cost-so-far plus a heuristic estimate of the cost still to go.
Four cards use it for robot motion, over three kinds of graph: a lattice of
constant-input motion primitives [arxiv:1709.05401 §3.2], motion primitives used
as guidance for a trajectory optimiser [arxiv:2408.10618 §4.1], car-like states
with steering and arc-length moves [arxiv:2412.03174 §3.1.1], and an occupancy
grid used as a baseline [arxiv:2412.02655 tab. 2].

When the heuristic is a lower bound on the cost-to-go and the graph is finite,
the search returns the cheapest path on that graph [arxiv:1709.05401 §3.3]
[arxiv:1709.05401 §3.4]. The paper calls the result optimal within the lattice,
not for the continuous problem [arxiv:1709.05401 §3.3]. The other three cards do
not state an optimality result for their search, so do not assume one for them.

Each edge cost is (‖u‖² + ρ)·τ for a constant control u, duration τ and time
weight ρ [arxiv:1709.05401 §3.1]. With a zero heuristic, A* reduces to Dijkstra
(uniform-cost) search, which is the baseline in the paper's comparison
[arxiv:1709.05401 fig. 5].

## Variants

### Heuristics on a motion-primitive lattice

The paper compares three heuristics for the same search over one lattice of
primitives. Both bounds below are required to be admissible and consistent
[arxiv:1709.05401 §3.4].

#### Dijkstra baseline (heuristic = 0)

No cost-to-go estimate. The search is always correct for the discrete graph, but
it expands the most states. On one start state at 3 m/s it expanded 2707 nodes
in 0.16 s [arxiv:1709.05401 fig. 5]. Card: [Search-based Motion Planning for Quadrotors](/papers/1709.05401).

#### Minimum-time heuristic h1

Relax the dynamics and state constraints, and keep only a lower bound on the
time to reach the goal. With the largest per-axis distance d and speed bound
v_max, the estimate is h1 = ρ·d / v_max [arxiv:1709.05401 eq. 7]. It is
consistent, by the triangle inequality on distances [arxiv:1709.05401 §3.4.1].
On the same query it expanded 1282 nodes in 0.064 s [arxiv:1709.05401 fig. 5].
It needs v_max, which the paper does not fix [arxiv:1709.05401 §3.4.1].

#### LQMT heuristic h2

Keep the dynamics and drop the state and input constraints. The result is the
classical Linear Quadratic Minimum-Time problem, whose optimal cost has a closed
form [arxiv:1709.05401 §3.4.2] [arxiv:1709.05401 eq. 10]. The paper states this
bound is admissible [arxiv:1709.05401 §3.4.2]; the text does not give a
consistency result for it. The closed forms are given only for velocity control
(n = 1) and acceleration control (n = 2) [arxiv:1709.05401 §3.4.2]. On the same
query it expanded 376 nodes in 0.016 s [arxiv:1709.05401 fig. 5]. Card: [Search-based Motion Planning for Quadrotors](/papers/1709.05401).

### Kinodynamic A* as guidance

OMEGA's planner runs a kinodynamic A* over motion primitives on each segment of
an initial trajectory that collides. Flight primitives carry an extra energy
cost. The result is a guidance segment that a spline optimiser then refines
[arxiv:2408.10618 §4.1]. The paper gives no heuristic and no values for the
search's cost weights [arxiv:2408.10618 §4.2], and the planner code is not in
the linked repository [code: README.md#L47]. Card: [OMEGA](/papers/2408.10618).

### Hybrid A* for car-like robots

RTEB runs a hybrid A* only when the Timed Elastic Band trajectory is not
kinematically feasible [arxiv:2412.03174 §3]. States are x, y and heading θ.
Each move is a steering angle and an arc length, with turning radius L / tan φ
[arxiv:2412.03174 §3.1] [arxiv:2412.03174 §3.1.1]. The priority adds a
Euclidean distance to the goal, weighted by λ_heu = 5.0 [arxiv:2412.03174
§3.1.1]. A weight of 5.0 means the priority is no longer the plain lower bound
of the Overview, and the paper does not discuss optimality. The path is then
smoothed and the TEB planner restarts from it [arxiv:2412.03174 §3]. Card:
[Resilient Timed Elastic Band Planner](/papers/2412.03174).

### A* as a grid baseline

A* appears in DCIP only as the baseline on the same occupancy grid. The paper
never names the search that DCIP itself uses [arxiv:2412.02655 §5.1.1].
A* expanded 2254 nodes in 0.1253 s on average over ten runs, with path length
177 [arxiv:2412.02655 tab. 2]. Card: [LLM-Enhanced Path Planning](/papers/2412.02655).

## When to use which

The numbers below are from one start state and one query, and the authors
report them. They show the direction of the effect, not a general speed-up.

| Situation | Use | Why |
|---|---|---|
| No usable cost-to-go bound, or the bound is not yet trusted | Dijkstra (h = 0) | Always correct on the graph, but the most expansions: 2707 in the paper's query [arxiv:1709.05401 fig. 5] |
| Speed bound known, no dynamics in the heuristic, and a cheap estimate is wanted | h1 | Consistent and simple. Halves the expansions versus Dijkstra in the paper's query: 1282 [arxiv:1709.05401 fig. 5] [arxiv:1709.05401 eq. 7] |
| Velocity or acceleration control (n = 1 or 2) and closed forms are implemented | h2 | Fewest expansions in the paper's query: 376 [arxiv:1709.05401 fig. 5]. Closed forms exist for these two orders [arxiv:1709.05401 §3.4.2] |
| Jerk or higher-order control | h1, or check the cost first | No closed form for h2 is given for jerk [arxiv:1709.05401 §3.4.2]. Planning in 3-D jerk control averaged 2.98 s, with a maximum of 9.50 s. Which heuristic that table uses is not stated [arxiv:1709.05401 tab. 1] |
| Car-like robot that needs a drivable path around obstacles, inside a local planner | Hybrid A* over steering and arc primitives | RTEB uses it as a recovery step when the local trajectory is infeasible [arxiv:2412.03174 §3]. Its cost is not reported separately from the whole planner [arxiv:2412.03174 tab. 4] |
| Guidance segments for a trajectory optimiser over flight primitives | Kinodynamic A* with an energy term | OMEGA uses this pattern [arxiv:2408.10618 §4.1]. The paper does not give the heuristic, so it cannot be reproduced from the card [arxiv:2408.10618 §4.2] |

For receding-horizon re-planning, the paper re-plans at 3 Hz in simulation
[arxiv:1709.05401 §5.3]. Its real-time claim depends on the control order: 2-D
acceleration control averages 0.016 s per query, while 3-D jerk control
averages 2.98 s [arxiv:1709.05401 tab. 1].

For dense obstacles, RTEB's whole planner had lower traverse time than TEB at
30% to 50% density in its own sweep [arxiv:2412.03174 tab. 4]. That result
includes the recovery step and the smoother, so it does not show the value of
the hybrid A* alone.

## Implementation sketch

A generic A* over a successor function. The heuristic and the successor set are
the parts that differ between the variants. Each step cites the paper.

```pseudocode
# A* over a graph of states; the heuristic is the variant-specific part
# Input:  start state; goal test; successors(state) -> (next, edge cost)
#         heuristic(state) -> lower bound on cost-to-go  [arxiv:1709.05401 §3.3]
# Output: states from start to goal, or None

def a_star(start, is_goal, successors, heuristic):
    # Queue ordered by cost-so-far plus heuristic  [arxiv:1709.05401 §3.3]
    open_queue = [(heuristic(start), start)]
    best_cost = {start: 0.0}
    parent = {}
    while open_queue:
        _, state = pop_min(open_queue)
        if is_goal(state):
            return path_to(state, parent)
        # Edges are motion primitives with cost (||u||^2 + rho) * tau
        # [arxiv:1709.05401 §3.1]
        for nxt, cost in successors(state):
            new_cost = best_cost[state] + cost
            if new_cost < best_cost.get(nxt, inf):
                best_cost[nxt] = new_cost
                parent[nxt] = state
                push(open_queue, new_cost + heuristic(nxt), nxt)
    return None
```

Where the variants differ: `heuristic` returns 0 for Dijkstra, ρ·d / v_max for
h1 [arxiv:1709.05401 eq. 7], and the LQMT cost for h2 [arxiv:1709.05401 eq. 10].
For h2 the duration T is constrained to be at least the minimum-time bound
[arxiv:1709.05401 eq. 6]. The closed forms divide by powers of T, so small
durations need a guard [arxiv:1709.05401 §3.4.2].

For hybrid A* on car-like states, `successors` applies a steering-and-arc move,
and the step cost adds penalties on arc length, on steering scaled by arc length
and on change of steering [arxiv:2412.03174 §3.1.1]. For OMEGA's kinodynamic
search, flight primitives add an energy cost [arxiv:2408.10618 §4.1]. The loop
itself is unchanged in each case.

## Contradictions

Paper and code differ on the default heuristic. The paper presents h2 as the
tighter bound that speeds up the search [arxiv:1709.05401 §5.1]. The released
library, a later and more general version of the code, defaults to the
minimum-time bound h1 [code: include/mpl_planner/common/env_base.h#L368]. The
paper does not state which heuristic its re-planning runs used
[arxiv:1709.05401 §5.3]. This page does not resolve the difference.

Node counts are not comparable across cards. The 2707 nodes for Dijkstra,
1282 for h1 and 376 for h2 come from one query on one lattice [arxiv:1709.05401
fig. 5]. DCIP's A* count of 2254 is on a different grid, against a DCIP search
whose algorithm is not named [arxiv:2412.02655 tab. 2]. DCIP's path costs also
include zone weights, so they are not comparable with A*'s path cost there
[arxiv:2412.02655 tab. 2]. RTEB reports no node counts [arxiv:2412.03174 tab. 4].

Requirements differ. The 1709 paper requires its heuristic to be admissible
and consistent [arxiv:1709.05401 §3.4]. RTEB weights its goal-distance term by
5.0 and does not say whether the result is a lower bound [arxiv:2412.03174
§3.1.1]. The two papers are not in conflict on results, but only the first
gives the optimality argument.

## Papers

- [Search-based Motion Planning for Quadrotors](/papers/1709.05401): A* over a lattice of constant-input motion primitives, with the h1 and h2 heuristics and their comparison on one query.
- [OMEGA](/papers/2408.10618): kinodynamic A* over motion primitives gives guidance segments for a trajectory optimiser, with an energy cost on flight primitives.
- [LLM-Enhanced Path Planning](/papers/2412.02655): A* as the grid-map baseline for an LLM-driven planner; the LLM's search is not named.
- [Resilient Timed Elastic Band Planner](/papers/2412.03174): hybrid A* over steering and arc primitives as a recovery step for a local planner.