Kinodynamic Planning

• Also called: kinodynamic motion planning
• Category: Planning & manipulation › Motion planning
• Tags: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

Motion planning that respects both geometric constraints such as collisions and the system's dynamics, finding control inputs over time rather than just a collision-free path.

Definition

Kinodynamic planning is motion planning in which the solution must satisfy kinematic constraints, such as avoiding obstacles and joint limits, and dynamic constraints, such as bounded accelerations, forces or torques, at the same time. The term was introduced by Donald, Xavier, Canny and Reif in 1993. Instead of searching for a geometric path in configuration space and timing it later, a kinodynamic planner searches for a duration and a control function whose resulting trajectory, obtained by integrating the system dynamics, starts at the initial state, stays in the free space and ends in a goal region.

The search therefore happens in the state space, which includes velocities as well as positions, and often has twice the dimension of the configuration space. The main difficulty is that two nearby states cannot in general be joined by a straight line: connecting them requires solving a two-point boundary value problem under the dynamics, which is easy for simple systems such as double integrators or Dubins cars but hard in general. Sampling-based planners such as kinodynamic RRT, introduced by LaValle and Kuffner, avoid this by growing a tree forward: they pick a node, apply sampled or chosen controls for a short time and keep the resulting states. Later methods such as SST add asymptotic near-optimality without needing a steering function.

Other families tackle the same problem differently. Search-based planners use a lattice of precomputed motion primitives, each of which is dynamically feasible. Trajectory optimization methods, including direct collocation and shooting, treat the controls and states as decision variables and solve a constrained nonlinear program, which converges quickly locally but can get trapped in local minima. Practical systems often combine the two: a sampling or search stage finds a feasible trajectory, and optimization then refines it. When the dynamics are uncertain, as in pushing objects, planners may use learned or residual models of the system and plan with open-loop controls that are then corrected by feedback.

Why it matters

Fast or heavy robots, cars, drones and pushed objects cannot follow arbitrary geometric paths: a path that ignores momentum or actuator limits may be impossible to execute. Kinodynamic planning produces trajectories the system can actually follow, which matters most when the robot moves quickly or has limited control authority.

Key applications

• Trajectory planning for cars and other nonholonomic vehicles
• Aggressive flight planning for drones and fixed-wing aircraft
• Nonprehensile manipulation such as planning sequences of pushes
• Fast arm motions near torque and velocity limits
• Legged and humanoid motion planning with contact dynamics
• Spacecraft and underwater vehicle maneuvering

In practice

A robot arm must push a box across a table to a goal region, avoiding an obstacle, without grasping it. The team models the box motion as a function of push parameters such as contact point, direction and duration, using an analytic pushing model corrected by a learned residual. A kinodynamic RRT samples push actions from the current box state, propagates each through the model and adds the resulting box poses to the tree, discarding pushes that would collide with the obstacle. Once a branch reaches the goal region, the sequence of pushes is executed, and the box pose is re-observed after each push so the planner can replan from the true state if the model was wrong.

Common misconceptions

• Kinodynamic planning is geometric planning followed by time parameterization — decoupled pipelines can produce paths that no dynamically feasible trajectory can follow, while kinodynamic planners consider dynamics during the search
• Any sampling-based planner can be made kinodynamic by swapping the distance metric — connecting two states generally requires solving a boundary value problem or propagating controls forward, not drawing a straight line
• A kinodynamic plan can be executed open loop — model errors and disturbances accumulate, so the plan is normally tracked with a feedback controller or replanned

Who should know this

• Motion planning engineers for vehicles, drones and arms
• Manipulation researchers working on pushing and other dynamic tasks
• Autonomous driving planning engineers
• Robotics students studying planning beyond configuration space

Related technologies

• Kinodynamic RRT
• Stable Sparse RRT (SST)
• State Lattice Planners
• Open Motion Planning Library (OMPL)
• Trajectory Optimization

Related terms

• Motion Planning
• Rapidly-exploring random tree
• Configuration Space
• Direct Collocation
• Double Integrator
• Nonprehensile Manipulation

Related projects

• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
• Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines

Videos

• 6.8210 Spring 2024 Lecture 18: Sampling-based (kinodynamic) motion planning: underactuated