Robot Motion Planning: A*, RRT, Trajectories & Replanning

Q: When should I use A* versus RRT?

A works well in low-dimensional, discretized spaces such as 2D maps for mobile robots. Sampling planners such as RRT-Connect suit high-dimensional problems such as robot arms, where grids become impractically large.

Robot Motion Planning

A robot that knows where it is and what it wants still has to answer the hard question: how do I get there? A warehouse robot needs a route through aisles that avoids shelves, people, and other robots. A robot arm needs a joint motion that reaches a part without hitting the bin, the table, or itself. A drone needs a path that respects its acceleration limits and stays inside its approved airspace. Motion planning turns goals into collision-free, physically executable motions.

Planning is usually split into layers. A global planner finds a route through a mostly static map; a local planner or controller follows it while reacting to obstacles the map did not contain; a trajectory generator adds timing that respects velocity, acceleration, and jerk limits. Around them, execution monitoring checks whether the robot is actually following the plan and triggers replanning or a safe stop when it is not. This page covers the main algorithms at each layer and the engineering decisions that make them work outside a demo.

TL;DR

Plan in configuration space (C-space): the set of all robot poses or joint values, where obstacles become forbidden regions.
Collision checking dominates runtime; simplify geometry, inflate obstacles by the robot's size plus a margin, and check edges, not just endpoints.
Graph search (A*, D* Lite, hybrid A*) suits low-dimensional grids such as mobile robot maps; sampling planners (RRT, RRT*, PRM) suit high-dimensional arms.
Trajectory optimization smooths paths and trades off length, clearance, and effort; time parameterization adds speeds within actuator limits.
Vehicles have kinodynamic constraints (turning radius, acceleration); plan with motion primitives or state lattices that respect them.
Replan as the world changes, monitor execution against the plan, and test planners on recorded and adversarial scenarios.

Quick Example

A* on an occupancy grid, with obstacles inflated by the robot's radius so the planner can treat the robot as a point:

The path swings around the inflated end of the wall. A real system would then smooth it, add clearance costs near obstacles, and time-parameterize it before handing it to a controller.

Core Concepts

Configuration Space

A robot's configuration is everything needed to place it: (x, y, θ) for a mobile base, six or seven joint angles for an arm, position plus orientation for a drone. The configuration space contains every configuration; obstacles in the world map to regions of C-space where the robot would collide. Planning becomes finding a continuous path through free C-space.

Kinematic models from Robot Kinematics and Dynamics map configurations to link positions for collision checks.

Collision Checking

Planners spend most of their time asking "is this configuration, or this motion between two configurations, collision-free?"

Represent robots and obstacles with simplified geometry: spheres, capsules, boxes, and convex hulls instead of detailed meshes.
Use a broad phase (bounding volume hierarchies, spatial hashing) to skip distant pairs, then a narrow phase for exact checks.
Inflate obstacles by the robot's radius plus a safety margin that accounts for localization and control error.
Check the motion, not just the endpoints: discretize edges finely enough, or use continuous collision checking, so the robot cannot tunnel through thin obstacles.
Arms also need self-collision checks, with an allowed-collision matrix for links that always touch.

Graph Search Planners

Discretize the space into a grid or lattice and search it:

Grid search is complete and optimal at its resolution, but cost grows rapidly with dimension. See Graph Algorithms.

Sampling-Based Planners

For high-dimensional C-spaces, sample random configurations instead of building a grid:

RRT (rapidly exploring random tree) grows a tree from the start toward random samples; RRT-Connect grows trees from both ends and is fast in practice.
RRT\* and PRM\* rewire connections to converge toward optimal paths as samples increase.
PRM (probabilistic roadmap) builds a reusable roadmap of the free space, useful when many queries share an environment.

Sampling planners are probabilistically complete: given enough time, they find a path if one exists, but they produce jagged paths that need smoothing, and their randomness means results vary between runs — set seeds for tests.

Trajectory Optimization and Time Parameterization

A path is geometry; a trajectory adds time. Optimization-based planners (CHOMP, STOMP, TrajOpt) refine paths to minimize length, effort, and jerk while maximizing clearance. Time parameterization then assigns velocities along the path that respect joint or wheel limits on velocity, acceleration, and sometimes jerk — for example time-optimal parameterization (TOPP) or simpler trapezoidal profiles. Executing a geometric path without parameterization asks the controller for impossible accelerations.

Kinodynamic Planning

Cars cannot move sideways, drones cannot stop instantly, and heavy robots cannot turn on the spot at speed. Kinodynamic planners respect these constraints by searching over feasible motion primitives (hybrid A*, lattices), using steering functions such as Dubins or Reeds-Shepp curves, or optimizing trajectories with dynamics constraints, often in a receding horizon with model predictive control.

Local Planning and Replanning

The global plan assumes a map; the real world has people, open doors, and pallets that moved. Local planners — dynamic window approach, timed elastic bands, model predictive controllers — follow the global path while avoiding nearby obstacles from live sensor data. When the local planner cannot make progress, the system replans globally or runs recovery behaviors (back up, rotate, clear costmaps, ask for help). Frameworks such as Nav2 and MoveIt package these layers.

Execution Monitoring

Monitoring ties planning to Robot Safety and Fleet Operations: plans should never be the only barrier between the robot and a collision.

Best Practices

Separate Global, Local, and Timing Layers

Use a global planner for routes, a local planner for live avoidance, and explicit time parameterization within actuator limits.

Budget for Collision Checking

Simplify geometry, use broad-phase culling, and check motions densely enough to catch thin obstacles.

Include Uncertainty in Margins

Inflate obstacles for localization error, control error, and sensor latency, not just the robot's footprint.

Test on Hard Scenarios

Keep a library of narrow passages, dynamic obstacles, dead ends, and recorded field failures, and run planners against it with fixed seeds in CI.

Common Mistakes

Checking Only Waypoints

Executing an Untimed Path

Zero Safety Margin

FAQ

What is the difference between path planning and motion planning?

Path planning usually means finding a collision-free geometric route. Motion planning also covers the robot's kinematics and dynamics, timing, and execution, producing a trajectory the robot can actually follow.

When should I use A* versus RRT?

A* works well in low-dimensional, discretized spaces such as 2D maps for mobile robots. Sampling planners such as RRT-Connect suit high-dimensional problems such as robot arms, where grids become impractically large.

What is configuration space?

The space of all possible robot configurations — positions and orientations, or joint values. Obstacles map to forbidden regions in this space, and planning becomes finding a path through the free regions.

Why do sampling-based planners produce jerky paths?

They connect random samples with straight segments. Post-processing with shortcutting, smoothing, or trajectory optimization produces smoother, shorter motions.

What is replanning?

Computing a new plan when the environment changes, the robot deviates from its trajectory, or the current plan becomes infeasible — often using incremental algorithms such as D* Lite that reuse previous work.