Lattice Planner

The foundational concept where the continuous, high-dimensional state space (e.g., x, y, heading, curvature, velocity) is discretized into a structured graph. Nodes represent reachable states, and edges represent kinematically feasible motion primitives connecting them. This transforms the continuous planning problem into a discrete graph search, enabling the use of algorithms like A* while respecting the vehicle's physical constraints from the outset.

A pre-computed set of short, feasible trajectory segments that form the edges of the lattice. Each primitive is generated by integrating a control input (e.g., steering angle, acceleration) over a short duration through the vehicle's dynamic model.

• Ensures Dynamical Feasibility: Every path composed of primitives inherently obeys acceleration, curvature, and non-holonomic constraints.
• Enables Smooth Trajectories: Primitives are designed to connect states with continuous derivatives, avoiding jerky, infeasible motions.
• Balances Resolution and Performance: The library's density and duration determine the planner's granularity and computational cost.

Lattice planners often employ hierarchical or multi-resolution search strategies to manage computational complexity. A coarse lattice (longer primitives, sparser states) is used for long-range global planning, while a fine-resolution lattice is used for local, precise maneuvering and obstacle avoidance. This allows the planner to efficiently explore vast state spaces, a critical capability for autonomous vehicles operating at highway speeds where the planning horizon extends hundreds of meters.

Optimal or near-optimal paths through the lattice are found using informed graph search algorithms like A* or its variants. The search is guided by an admissible heuristic (e.g., Euclidean distance to goal, ignoring obstacles and dynamics), which dramatically prunes the search space. The total cost of a path is the sum of the costs of its constituent primitives, which can incorporate factors like:

• Travel time
• Energy consumption
• Comfort (jerk, lateral acceleration)
• Proximity to obstacles

Unlike geometric planners that post-process a path for dynamic feasibility, lattice planners embed dynamics into the search space. Since every motion primitive is generated from the vehicle model, any path found is guaranteed to be executable by the vehicle's controller, provided it respects actuator limits. This is essential for non-holonomic systems like cars and differential-drive robots, which cannot move sideways, and for maintaining stability at high speeds where kinematic approximations break down.

Lattice planners are inherently compatible with real-time replanning engines. They can function as the core planner within a Model Predictive Control (MPC) or Receding Horizon Control loop. When a replanning trigger occurs (e.g., new obstacle detection), the planner can be warm-started from the vehicle's current state in the lattice. Incremental search algorithms like D Lite* can also be adapted to the lattice structure, allowing for efficient path repair in dynamic environments without restarting the search from scratch.

Lattice planners are extensively used for on-road and off-road autonomous vehicle path planning. They excel at generating smooth lane-change maneuvers, highway merges, and complex urban turns by searching over a graph of pre-computed motion primitives that respect vehicle dynamics (e.g., maximum curvature, acceleration). This ensures the resulting path is not just collision-free but also comfortable for passengers and executable by the vehicle's low-level controller.

• Key Feature: Plans kinodynamically feasible trajectories that a car can physically follow.
• Example: An autonomous taxi uses a lattice planner to compute a smooth trajectory for an unprotected left turn, accounting for oncoming traffic and lane boundaries.

In dynamic warehouse environments, Autonomous Mobile Robots (AMRs) and forklifts use lattice planners for precise point-to-point navigation while avoiding static racks, other robots, and human workers. The planner's ability to incorporate non-holonomic constraints is critical for vehicles like forklifts that cannot move sideways.

• Key Feature: Efficiently handles the replanning required when new obstacles (like a fallen pallet) are detected.
• Integration: Often works in tandem with a higher-level Multi-Agent Path Finding (MAPF) scheduler that assigns goals, while the lattice planner handles the local, executable trajectory.

Large, slow-moving agricultural robots performing tasks like planting, weeding, or harvesting use lattice planners to navigate uneven, unstructured terrain. The state lattice can be defined in terms relevant to the task, such as headland turns at the end of a crop row.

• Key Feature: The discretized state space allows for efficient planning over long distances in open fields while respecting the vehicle's slip constraints and implement kinematics.
• Challenge: Must account for significant wheel slip and terrain inclination, often requiring tight integration with state estimation systems.

For drones and other UAVs, lattice planners generate aggressive, yet safe, flight trajectories through cluttered environments like forests or urban canyons. Motion primitives are defined in 3D space, capturing the quadrotor's dynamics (pitch, roll, yaw, thrust).

• Key Feature: Enables high-speed flight by pre-computing primitive maneuvers that are at the limits of the drone's dynamic envelope.
• Use Case: A drone inspecting a wind turbine blade uses a lattice planner to compute a smooth, continuous path around the complex structure, minimizing flight time while maintaining a safe distance.

Unmanned surface vessels (USVs) and autonomous boats employ lattice planners for tasks like harbor navigation, channel keeping, and docking. The motion primitives must model complex hydrodynamic constraints, such as large turning radii and significant drift due to currents.

• Key Feature: The planner's graph can incorporate environmental forces (current, wind) into the state transition, leading to more robust and energy-efficient paths.
• Application: An autonomous research vessel uses a lattice planner to execute a precise lawnmower survey pattern while compensating for cross-currents.

While often associated with mobile platforms, the lattice planning paradigm is also applied to motion planning for robotic arms, especially in cluttered workspaces. The state space includes joint angles and velocities, and motion primitives are short, dynamically feasible joint-space trajectories.

• Key Feature: Provides a guaranteed feasible alternative to purely geometric planners by ensuring the planned joint motions respect torque and acceleration limits.
• Scenario: A robotic arm on an assembly line uses a lattice planner to quickly compute a smooth, jolt-free motion to insert a component while avoiding nearby equipment and human co-workers.

A motion primitive is a short, pre-computed trajectory segment that is guaranteed to be kinematically and dynamically feasible for a specific robot model. Lattice planners construct complex paths by connecting these primitives end-to-end in a graph.

• Role in Lattice Planning: Serves as the fundamental building block of the lattice graph. Each edge corresponds to the execution of a single primitive.
• Characteristics: Primitives are typically generated offline by forward-simulating the robot's control inputs (e.g., steering angles, accelerations) over a fixed time step or distance.
• Example: For an autonomous vehicle, a library might include primitives for 'go straight 5m', 'turn left with a 10m radius', and 'lane-change right'.

Kinodynamic planning is the problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic restrictions like a car's turning radius) and dynamic constraints (e.g., limits on acceleration, torque, or jerk).

• Relation to Lattice Planners: Lattice planners are a primary algorithmic solution to the kinodynamic planning problem. By constructing the state lattice from motion primitives that obey these constraints, any path found through the graph is, by definition, kinodynamically feasible.
• Contrast with Geometric Planners: Pure geometric planners (like standard A* on a grid) find paths that are only collision-free, ignoring the physical limitations of how the robot can move.

A state lattice is the discretized graph structure at the core of a lattice planner. Unlike a standard grid that discretizes only position (x,y), a state lattice discretizes the robot's full state space (e.g., x, y, heading θ, curvature κ, and sometimes velocity).

• Graph Structure: Each node represents a discrete state. Edges represent feasible transitions between these states, corresponding to the execution of motion primitives.
• Dimensionality: The lattice exists in a high-dimensional space (state-space), making search challenging but enabling the planning of smooth, complex maneuvers.
• Search Overlay: Algorithms like A* are used to search this lattice graph for an optimal path from a start state to a goal state region.

Receding Horizon Control, often implemented via Model Predictive Control (MPC), is a control strategy where a finite-horizon optimization problem is solved at each time step, and only the initial control action is executed before the horizon 'recedes' and the process repeats.

• Synergy with Lattice Planners: Lattice planners are frequently used as the trajectory generator within an RHC/MPC framework. The planner generates a candidate trajectory over the planning horizon, and the controller optimizes tracking while satisfying constraints.
• Real-Time Adaptation: This combination allows the system to continuously re-plan based on the latest sensor data, handling dynamic obstacles and environmental changes effectively.

Sampling-based planners like RRT* and Probabilistic Roadmap (PRM) are alternative motion planning paradigms that randomly sample the configuration space to build a graph or tree of feasible paths.

• Comparison with Lattice Planners:
  • Lattice Planners: Use a structured, deterministic discretization (the lattice). This provides strong guarantees on dynamic feasibility and is highly efficient for systems with regular, repetitive motion patterns (like ground vehicles).
  • Sampling-Based Planners: Use random, unstructured sampling. They are more general and can be easier to apply to high-DOF systems (like robot arms) or complex environments, but may produce less smooth paths and require post-processing for dynamic feasibility.

A feasibility checker is a critical software component that validates whether a candidate trajectory or plan satisfies all system constraints before it is passed to the controller for execution.

• Key Constraints Checked:
  • Collision Avoidance: Verifies the path is free of static and dynamic obstacles.
  • Dynamic Feasibility: Ensures the path does not violate velocity, acceleration, or jerk limits.
  • Kinematic Feasibility: Confirms adherence to non-holonomic constraints.
• Role in Planning Pipeline: In a lattice planner, primitives are pre-checked for dynamic feasibility. During the graph search, a collision checker is invoked for each primitive to ensure the final path is both feasible and safe.