Motion Primitive

A motion primitive is kinematically and dynamically feasible by definition. This means each primitive is a valid solution to the robot's equations of motion, respecting hard constraints such as:

• Maximum velocity and acceleration
• Non-holonomic constraints (e.g., a car cannot move sideways)
• Actuator torque limits Primitives are generated offline by solving boundary value problems, ensuring they can be executed by the physical system without violation.

Complex paths are built by sequentially composing primitives end-to-end. This composition forms a state lattice—a discrete graph embedded in the continuous state space where:

• Nodes represent discretized robot states (x, y, heading, velocity).
• Edges are the motion primitives connecting these states. Planners like Lattice Planners or A* search this graph to find a feasible sequence from start to goal. The use of pre-computed primitives transforms a continuous planning problem into a discrete graph search, enabling real-time performance.

Motion primitives enable planning by defining a manageable discretization of the robot's high-dimensional state space. Instead of planning in continuous space, the planner selects from a finite library of primitives originating from discrete states. Key discretization parameters include:

• Position (x, y) resolution (e.g., 0.1m grid)
• Heading (θ) resolution (e.g., 5° increments)
• Velocity (v) bins (e.g., 0 m/s, 0.5 m/s, 1.0 m/s) The granularity of this discretization creates a trade-off between planning resolution, computational cost, and memory usage for the primitive library.

In real-time replanning engines, motion primitives are the fundamental output of the local planner. When a replanning trigger (e.g., a new obstacle) occurs, the engine:

1. Takes the robot's current state as the new start node.
2. Searches the lattice of primitives for a new feasible sequence over the replanning horizon.
3. Executes the first primitive(s) before replanning again (Receding Horizon Control). This allows for dynamic obstacle avoidance and adaptation while guaranteeing every issued command is dynamically executable.

Motion primitives differ fundamentally from sampling-based planners like RRT or PRM. Key distinctions:

• Pre-computation vs. Online Generation: Primitives are computed offline; RRT samples and connects states online.
• Feasibility Guarantee: Each primitive is dynamically feasible by construction. RRT connections may require post-processing smoothing.
• Deterministic Search vs. Probabilistic Completeness: Lattice search with primitives is deterministic; RRT offers probabilistic completeness. Primitive-based planners are often preferred for high-speed navigation of vehicles with complex dynamics where feasibility is paramount.

Common examples of motion primitives include:

• Dubins Paths: Shortest paths for cars moving forward with a bounded turning radius (e.g., Left-Straight-Left, Right-Straight-Right sequences).
• Reeds-Shepp Paths: Similar to Dubins but allow reverse gear.
• Clothoids: Curves with linearly changing curvature, used for comfortable passenger vehicle paths.
• Polynomial Spirals: Parametric curves used for smooth lane changes.

Primary Applications:

• Autonomous Vehicle lane-keeping and obstacle avoidance.
• Autonomous Mobile Robot (AMR) navigation in warehouses.
• Aerial Drone trajectory planning in cluttered environments.

In lattice-based planners, a finite set of motion primitives is precomputed to form a state lattice—a graph where nodes represent vehicle states (position, heading, velocity) and edges are the primitives connecting them. Planners like Hybrid A* search this lattice for optimal, kinematically feasible paths. This is essential for non-holonomic vehicles like cars or forklifts, where simple straight-line connections are not dynamically possible.

• Key Benefit: Guarantees that all candidate paths respect the vehicle's turning radius and acceleration limits.
• Example: An autonomous mobile robot (AMR) in a warehouse uses a lattice of dubins curves or reeds-shepp curves to plan smooth turns within narrow aisles.

Search-based algorithms like A* and D* use motion primitives to expand the search tree during planning. Instead of arbitrary movements, each expansion applies a primitive from the current state, ensuring every explored path segment is executable. This is a core technique in real-time replanning engines where the environment is dynamic.

• Process: From a node representing the robot's current state, the planner 'sprays' a set of primitives to generate candidate successor states, evaluating each for cost and collision.
• Advantage: Combines the optimality guarantees of graph search with the feasibility guarantees of pre-vetted motion segments.

Motion primitives serve as an excellent initial guess or parameterization for local optimization methods. In the Timed Elastic Band (TEB) approach, a sequence of primitives forms the initial 'band' that is then optimized for smoothness, safety, and speed. Similarly, Model Predictive Control (MPC) solvers can use a library of primitives to warm-start the non-linear optimization, drastically reducing computation time.

• Use Case: A delivery robot uses MPC to navigate a crowded sidewalk. A set of lane-change and deceleration primitives provides the solver with a physically realistic starting point, enabling faster convergence to a safe, compliant trajectory.

In Multi-Agent Path Finding (MAPF), motion primitives standardize the action space for each agent. Algorithms like Conflict-Based Search (CBS) can reason over conflicts at the level of primitives (e.g., two agents attempting to use the same 'forward-left' primitive in the same space-time cell). This abstraction simplifies conflict resolution and deadlock detection.

• Application: Coordinating a heterogeneous fleet of AMRs and manual forklifts. Each vehicle type has its own primitive library, but the orchestrator understands the spacetime footprint of each primitive, enabling safe, synchronized movement in shared zones.

The specific primitives in a library are tailored to a vehicle's kinodynamic constraints. This is a key enabler of heterogeneous fleet orchestration.

• Differential-Drive Robot (AMR): Primitives include in-place rotations, straight-line segments, and arcs of varying curvature.
• Ackermann-Steering Vehicle (Forklift/Car): Primitives are dubins paths (combinations of arcs and straight lines) respecting a minimum turning radius. Reeds-Shepp curves add reverse motions.
• Quadrotor (UAV): Primitives are 3D minimum-snap trajectories or polynomial segments that satisfy dynamics and actuator limits.

Motion primitives are not arbitrary; they are generated offline by solving two-point boundary value problems that respect the vehicle's dynamics model. A feasibility checker validates each primitive against:

• Kinematic Constraints: Adherence to non-holonomic rules (e.g., no sideways movement for a car).
• Dynamic Constraints: Acceleration, jerk, and torque limits.
• Physical Limits: Adherence to maximum velocity and steering angle.
• Collision Geometry: The swept volume of the vehicle along the primitive must be collision-free in a nominal environment.

This offline validation is what makes online planning with primitives so computationally efficient.

A search-based motion planning algorithm that discretizes a vehicle's state space into a graph composed of motion primitives. This lattice structure enables the efficient generation of smooth, dynamically feasible trajectories by connecting pre-computed primitive segments. It is a primary consumer of motion primitive libraries, stitching them together to form complete paths from start to goal states.

The problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic steering limits) and dynamic constraints (e.g., acceleration, torque limits). Motion primitives are explicitly designed to be kinodynamically feasible, making them the ideal atomic units for planners solving this complex problem. This ensures the resulting plans are not just collision-free but also executable by the physical robot.

A software component that validates whether a candidate plan or trajectory satisfies all system constraints before execution. For plans built from motion primitives, the checker verifies:

• Dynamic admissibility of transitions between primitives.
• Collision-free status along the entire composed path.
• Adherence to velocity and acceleration limits. It acts as a critical safety layer, ensuring the output of a lattice or search-based planner is truly executable.

A local trajectory optimization method that deforms an initial path (often from a lattice planner) by optimizing the positions and timings of a sequence of robot states. While not built from fixed primitives, TEB performs continuous optimization of a similar trajectory representation. It optimizes for smoothness, safety, and speed, making it a complementary approach for refining or reactively adjusting a primitive-based plan.

An advanced control methodology where a dynamic model predicts future system behavior. At each control step, it solves a finite-horizon optimization to determine optimal control actions. MPC can use a sequence of motion primitives as the decision variables within its optimization window, selecting the best primitive at each step to minimize a cost function while satisfying constraints, blending planning and control.

The discretized graph structure itself, formed by applying motion primitives from a set of representative states. Each node represents a reachable state (x, y, heading, curvature, velocity), and each edge is a feasible motion primitive connecting two states. This lattice provides the search space for planners like A*, enabling efficient exploration of complex, constrained state spaces.