Kinodynamic Planning

Unlike pure geometric planners, kinodynamic planning simultaneously enforces two classes of constraints:

• Kinematic Constraints: Govern the robot's admissible configurations, such as a non-holonomic car's turning radius or a robotic arm's joint limits.
• Dynamic Constraints: Govern the robot's motion over time, such as maximum acceleration, torque limits, and wheel slip conditions. This ensures the resulting trajectory is dynamically feasible, meaning the robot can actually follow it given its physical actuators and inertia.

Kinodynamic planning operates in the robot's phase space (or state space), which includes both configuration (e.g., position, orientation) and its derivatives (e.g., velocity, angular rate).

• A point in this space is a full state vector (e.g., [x, y, θ, v, ω]).
• The planner searches for a continuous state-time trajectory through this high-dimensional space.
• This is fundamentally more complex than planning in configuration space alone, as it must reason about how the state evolves under the robot's dynamics model.

At its core, the algorithm integrates a dynamics model—a set of differential equations describing how control inputs (e.g., throttle, steering) change the robot's state.

• Example: For a differential-drive robot: dx/dt = v * cos(θ), dy/dt = v * sin(θ), dθ/dt = ω.
• The planner uses this model to propagate or simulate potential motions forward in time, ensuring every segment of the path is consistent with the robot's physics.
• This allows it to plan maneuvers like acceleration out of a tight turn or controlled braking to a precise stop.

The high-dimensional, continuous state space is typically explored using sampling-based motion planners.

• Kinodynamic Rapidly-exploring Random Trees (RRTs): The most common approach. The tree grows by randomly sampling a control input, applying it via the dynamics model for a short duration, and generating a new feasible state.
• State Lattice Planners: Pre-compute a discrete set of motion primitives—short, feasible trajectory segments generated by applying a discrete set of control inputs. The planner searches over sequences of these primitives.
• These methods are probabilistically complete, meaning they will find a solution if one exists, given enough time.

Beyond search, kinodynamic problems can be framed as a constrained optimization.

• The planner defines a cost function (e.g., minimize time, energy, or jerk).
• It then directly solves for the optimal control inputs and state trajectory that minimize cost while satisfying:
  • Differential constraints (the dynamics model).
  • Path constraints (collision avoidance, staying in bounds).
  • Boundary constraints (start and goal states).
• This is often solved using Model Predictive Control (MPC) or direct transcription methods, yielding smooth, high-performance trajectories.

Kinodynamic planning is essential for applications where dynamics dominate:

• Autonomous Racing: Planning the racing line requires managing tire friction limits and vehicle inertia at the edge of control.
• Legged Locomotion: For robots like quadrupeds or humanoids, planning must account for balance, contact forces, and centroidal dynamics.
• Aerial Acrobatics: Drones performing flips or agile maneuvers must plan trajectories that respect thrust and angular momentum limits.
• Industrial Manipulators: High-speed pick-and-place robots use kinodynamic planning to minimize cycle time while avoiding actuator torque saturation.

The broader field of computing a sequence of valid configurations that moves an agent from a start to a goal. Kinodynamic planning is a specialized subset that enforces dynamic feasibility—ensuring the planned path can be executed given the agent's acceleration and velocity limits—whereas classical motion planning often considers only geometric (kinematic) constraints like obstacle avoidance.

The physical limits on an agent's motion derived from its dynamics model, such as maximum acceleration, deceleration, torque, and velocity. These are the "dynamic" part of kinodynamic planning. Examples include:

• A warehouse AMR's maximum safe turning acceleration.
• A drone's thrust limits for vertical ascent. Ignoring these constraints yields trajectories that are geometrically clear but physically impossible to follow.

The geometric limits on an agent's possible configurations, independent of forces. These define the "kinematic" component. Common constraints include:

• Non-holonomic constraints: Limits on permissible directions of motion (e.g., a car cannot move sideways).
• Holonomic constraints: Pure configuration limits (e.g., a robotic arm's joint limits). Kinodynamic planners must satisfy both kinematic and dynamic constraints simultaneously.

A common algorithmic approach to kinodynamic planning. It discretizes the state space (position, velocity, orientation) into a graph (lattice) where edges correspond to motion primitives—short, feasible trajectories pre-computed using the agent's dynamic model. Search algorithms (e.g., A*) then find a feasible path through this lattice. This method explicitly encodes dynamic constraints into the graph structure.

An alternative to search-based kinodynamic planning. It treats path finding as a continuous optimization problem, minimizing a cost function (e.g., time, energy) subject to constraints (dynamics, obstacles). Methods like Model Predictive Control (MPC) and Sequential Quadratic Programming (SQP) are used. This approach is highly effective for refining rough paths into smooth, optimal trajectories that respect dynamics.

The core output of a kinodynamic planner: a time-parameterized path (x(t), y(t), θ(t), v(t), ...) that is:

• Collision-free with the environment.
• Dynamically feasible: All derivatives (velocity, acceleration) satisfy the agent's physical limits.
• Kinematically feasible: Adheres to steering and turning constraints. A trajectory that is only collision-free is not sufficient for real-world execution; it must be feasible.