Why include velocity in the state?

Motion feasibility and control effort depend on momentum and other dynamics, not just position.

Does LQR solve the entire nonlinear planning problem?

No. It provides local control and cost information used within a broader search.

Does the star have a meaning?

Yes. RRT* includes cost-improving connection choices and rewiring; claims about it should not automatically be assigned to ordinary RRT.

AI Glossary / Graphs and symbolic AI / Advanced

Linear-quadratic regulator rapidly exploring random tree

Definition

Linear-quadratic regulator rapidly exploring random tree refers to motion-planning approaches that combine sampling-based tree search with linear-quadratic control ideas. The closely associated LQR-RRT* algorithm uses locally derived control costs and policies to guide tree growth when a robot's dynamics make simple geometric closeness misleading.

What it means

A robot's state includes more than its location. Velocity, orientation, and other quantities affect which motions it can execute. A vehicle near a target but moving rapidly away may be harder to bring to that target than a more distant vehicle moving appropriately.
RRT-style planners explore possible motion through a growing tree. LQR contributes a local approximation to control effort and a way to steer toward a state. The star in RRT* matters: it denotes a variant that also revises connections to improve path cost. The glossary's long title should not erase that distinction between related algorithms.

How it works

The planner samples a state and uses a local linear approximation of the dynamics together with quadratic cost choices to help evaluate nearby tree nodes. A local controller then extends a candidate trajectory. Validity checks remain necessary before the connection is accepted.
In the cited LQR-RRT* method, LQR-derived information also supports choosing and revising connections. The local extension can end somewhere other than the originally sampled state. This combines broad exploration with local control guidance, but local approximations are not exact descriptions of arbitrary nonlinear dynamics. Model choice, cost weights, constraints, and numerical implementation still affect the result.

Three practical examples

A robotics researcher can explore feasible motions for a torque-limited pendulum, where simply drawing a line between angles ignores velocity and actuation.
A simulation study can compare geometric and dynamics-aware choices of which existing state should extend toward a sample.
A robot-planning prototype can examine the tradeoff between reaching a target and the modeled control effort used along a trajectory.

Think of it this way

Think of choosing where to begin a bicycle maneuver. The rider physically nearest the destination may face the wrong direction or carry unsuitable momentum, while another rider can approach more naturally. The analogy is limited because an LQR-guided planner uses explicit dynamics and cost approximations rather than a human's intuitive judgment.

Worked example

Consider an invented two-coordinate state error relative to a sampled target. The coordinates are scaled position error and scaled velocity error, so the numerical comparison is meaningful within this toy representation. Candidate A has error (0.1, 0.8), and candidate B has error (0.9, 0.1).
Squared Euclidean distance gives A a value of 0.1 squared plus 0.8 squared, or 0.65. B has 0.9 squared plus 0.1 squared, or 0.82. Ordinary Euclidean closeness therefore favors A.
For illustration, suppose a local quadratic cost estimate is V(e) = e1 squared + 9 times e2 squared. A's estimate is 0.01 + 9 times 0.64 = 5.77. B's estimate is 0.81 + 9 times 0.01 = 0.90. This estimate favors B because velocity mismatch is expensive under the assumed local model.
The matrix behind that expression is diagonal with entries 1 and 9. It is supplied for teaching purposes, not derived here from a particular robot's Riccati equation. Real LQR guidance derives the value function from the chosen dynamics and cost problem.
Even if B looks preferable by this estimate, the planner must attempt a feasible extension and check its trajectory. An obstacle or an actuator limit could reject it. Furthermore, parent selection in a cost-improving tree may consider accumulated cost from the root as well as a connection cost. The local comparison alone does not identify the best complete path or prove that the robot reaches the target.

Illustrative case study

In a fictional simulation project, Fern Robotics initially chooses tree nodes using position alone. Some selected states are close to a sample but have velocities that make the attempted extension poor. The team adds a dynamics-aware local estimate and records both the predicted cost and the actual simulated extension.
When predictions differ from simulation far from the linearization point, the team treats that as a model-limit signal. This invented case illustrates how local guidance should be evaluated. It does not claim a measured speedup, successful physical deployment, or universal superiority over other planners.

Common misconceptions and mistakes

LQR-RRT* is not simply a straight-line path followed by an LQR controller. Control-related information guides the search itself. Nor does the word optimal mean that every finite run returns a globally optimal trajectory.
Do not assume local linearization removes all nonlinear difficulties or that a quadratic cost automatically enforces hard constraints. Collision checks, state limits, and actuator limits need appropriate handling. A low estimated connection cost is not proof of feasibility. Also, LQR-RRT and LQR-RRT* should not be treated as interchangeable names when discussing rewiring or theoretical properties.

Business use

This is mainly relevant to teams developing motion-planning systems or evaluating robotics research. Begin with a clear dynamics model, a defined state representation, and a cost that reflects the intended task. Examine whether local control approximations remain useful over attempted extensions.
Evaluate solution quality and feasibility across representative scenarios and multiple random seeds. Include failed extensions, computation budgets, and model mismatch in the assessment. Keep simulation evidence separate from physical-system validation. If a report makes an optimality claim, state the algorithm variant, assumptions, and whether the claim is asymptotic theory or an observed finite-run result.

Check your understanding

Why does the worked example's quadratic estimate prefer B even though Euclidean distance prefers A?

Answer: The assumed quadratic estimate penalizes velocity error nine times as strongly as position error. B's much smaller velocity mismatch outweighs its larger position mismatch under that estimate.

Related terms

Rapidly exploring random tree
RRT*
linear-quadratic regulator
kinodynamic planning
local linearization
control cost
steering
collision checking
rewiring

Learn next

Recalculate the toy costs using equal weights, then increase the velocity weight gradually. Observe when the preference changes. Next, study how an LQR value function is derived and how a sampling-based planner validates an attempted trajectory rather than trusting its estimated cost alone.

Sources

Alejandro Perez and colleagues, LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically Derived Extension Heuristics, original author manuscript: https://lis.csail.mit.edu/pubs/perez-icra12.pdf

Previous: Linear programming Next: Linear regression