wikillm

Concept · 4 papers · updated 2026-10-25

A* search

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.

graph-searchheuristicsmotion-planningtrajectory-generationnavigation

Markdown7 min read

AI-compiled overview, updated 2026-10-25, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

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 1709.05401 §3.2, motion primitives used as guidance for a trajectory optimiser 2408.10618 §4.1, car-like states with steering and arc-length moves 2412.03174 §3.1.1, and an occupancy grid used as a baseline 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 1709.05401 §3.3 1709.05401 §3.4. The paper calls the result optimal within the lattice, not for the continuous problem 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 ρ 1709.05401 §3.1. With a zero heuristic, A* reduces to Dijkstra (uniform-cost) search, which is the baseline in the paper's comparison 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 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 1709.05401 fig. 5. Card: Search-based Motion Planning for Quadrotors.

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 1709.05401 eq. 7. It is consistent, by the triangle inequality on distances 1709.05401 §3.4.1. On the same query it expanded 1282 nodes in 0.064 s 1709.05401 fig. 5. It needs v_max, which the paper does not fix 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 1709.05401 §3.4.2 1709.05401 eq. 10. The paper states this bound is admissible 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) 1709.05401 §3.4.2. On the same query it expanded 376 nodes in 0.016 s 1709.05401 fig. 5. Card: Search-based Motion Planning for Quadrotors.

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 2408.10618 §4.1. The paper gives no heuristic and no values for the search's cost weights 2408.10618 §4.2, and the planner code is not in the linked repository README.md. Card: OMEGA.

Hybrid A* for car-like robots

RTEB runs a hybrid A* only when the Timed Elastic Band trajectory is not kinematically feasible 2412.03174 §3. States are x, y and heading θ. Each move is a steering angle and an arc length, with turning radius L / tan φ 2412.03174 §3.1 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 2412.03174 §3. Card: Resilient Timed Elastic Band Planner.

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 2412.02655 §5.1.1. A* expanded 2254 nodes in 0.1253 s on average over ten runs, with path length 177 2412.02655 tab. 2. Card: LLM-Enhanced Path Planning.

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.

SituationUseWhy
No usable cost-to-go bound, or the bound is not yet trustedDijkstra (h = 0)Always correct on the graph, but the most expansions: 2707 in the paper's query 1709.05401 fig. 5
Speed bound known, no dynamics in the heuristic, and a cheap estimate is wantedh1Consistent and simple. Halves the expansions versus Dijkstra in the paper's query: 1282 1709.05401 fig. 5 1709.05401 eq. 7
Velocity or acceleration control (n = 1 or 2) and closed forms are implementedh2Fewest expansions in the paper's query: 376 1709.05401 fig. 5. Closed forms exist for these two orders 1709.05401 §3.4.2
Jerk or higher-order controlh1, or check the cost firstNo closed form for h2 is given for jerk 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 1709.05401 tab. 1
Car-like robot that needs a drivable path around obstacles, inside a local plannerHybrid A* over steering and arc primitivesRTEB uses it as a recovery step when the local trajectory is infeasible 2412.03174 §3. Its cost is not reported separately from the whole planner 2412.03174 tab. 4
Guidance segments for a trajectory optimiser over flight primitivesKinodynamic A* with an energy termOMEGA uses this pattern 2408.10618 §4.1. The paper does not give the heuristic, so it cannot be reproduced from the card 2408.10618 §4.2

For receding-horizon re-planning, the paper re-plans at 3 Hz in simulation 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 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 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 1709.05401 eq. 7, and the LQMT cost for h2 1709.05401 eq. 10. For h2 the duration T is constrained to be at least the minimum-time bound 1709.05401 eq. 6. The closed forms divide by powers of T, so small durations need a guard 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 2412.03174 §3.1.1. For OMEGA's kinodynamic search, flight primitives add an energy cost 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 1709.05401 §5.1. The released library, a later and more general version of the code, defaults to the minimum-time bound h1 env_base.h. The paper does not state which heuristic its re-planning runs used 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 2412.02655 tab. 2. DCIP's path costs also include zone weights, so they are not comparable with A*'s path cost there 2412.02655 tab. 2. RTEB reports no node counts 2412.03174 tab. 4.

Requirements differ. The 1709 paper requires its heuristic to be admissible and consistent 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

Related

ConceptModel predictive control (MPC)Solve a finite-horizon optimal control problem from the current state, apply only the first input and re-solve. In autonomous racing it is the most common control approach. Variants add nonlinear, sampling, learned or logic-based models, learned or imitation-trained policies and LLM-set parameters. Racing sources give no head-to-head comparison.ConceptLLM tree searchSearch over a language model's own intermediate reasoning steps: the model proposes candidate next steps, scores partial solutions, and breadth-first or depth-first search keeps promising branches and backtracks. No training. Tree of Thoughts reports 74% vs 4% for CoT on Game of 24 (GPT-4), at $0.74 vs $0.47 per problem for best-of-100 CoT. LLM+P instead hands the search to a classical planner.ConceptLLM planningLLM+P writes PDDL for a classical planner. Text2Motion checks LLM skill sequences with learned feasibility models. KnowNo asks a human when calibrated options are ambiguous. Chameleon, LLM-Planner and Hindsight Planner pick steps from examples, the last two replanning. DCIP edits a grid map; DexDiff uses a fine-tuned VLM plan. Each needs a model, data, tools or demonstrations.ConceptKinematic bicycle modelA force-free vehicle model with no lateral slip, where each axle is one wheel at its centre and every block moves along its own heading. Two papers use it: an articulated tractor-trailer tracked by nonlinear MPC, and closed-form arc primitives for a hybrid A* search in a car-like planner. Results are author-reported, from simulation and one real vehicle.ConceptMotion primitivesShort pieces that carry a system from one state to the next. Constant-input pieces with a closed-form cost form graph edges for quadrotor A* planning; learned pieces are conditioned on a partial observation for humanoid teleoperation; parameterised skills are checked inside an LLM planner. Results are author-reported.ConceptTime-optimal controlLinear minimum-time control: pick inputs that reach a goal state at the lowest cost of effort plus a weighted duration. Closed forms exist for velocity and acceleration control. The paper uses them as a heuristic for A* over a lattice of motion primitives, and reports a large node reduction for one start state. Only one source so far; no head-to-head comparison.

Source and license

Compiled from the papers listed on this page, all published under CC BY, CC BY-SA or CC0, with citations. See each paper's page for its authors and license.