Kinodynamic Planning

动力学约束规划Advanced

Planning that satisfies obstacle avoidance and dynamics limits like velocity, acceleration, and torque together, producing a directly executable trajectory.

Ordinary path planning only handles geometry — finding a route from A to B that avoids obstacles, with speed figured out separately. Kinodynamic planning, a term coined by Donald, Xavier, Canny, and Reif in 1993, requires the result to satisfy both kinematic constraints (obstacle avoidance, joint limits) and dynamics constraints (velocity, acceleration, force, or torque limits) at the same time. It therefore usually searches over a state space that includes both position and velocity, expanding only along motions the system can actually perform — a car, for example, can't move sideways. A representative method is LaValle and Kuffner's 2001 randomized kinodynamic planning: rather than connecting tree nodes with straight lines, it extends the RRT search tree by applying a control input and integrating the dynamics model forward for a short time to get a new state. Another common route plans a purely geometric path first and applies time parameterization afterward — simpler, but it may fail to find a feasible solution for strongly dynamic tasks like running, jumping, or high-speed flight. Trajectory optimization and MPC are also often used to solve this class of problem.

ExampleGetting a quadruped robot to jump onto a step requires more than just a geometrically feasible foothold route: the joint torque available at takeoff must be enough, the center of mass must follow a parabola while airborne, and landing speed must stay within limits — all of which have to be folded into the planning together as dynamics constraints.

Also called: Kinodynamic Motion Planning
Related: Motion Planning · Rapidly-exploring Random Tree · Trajectory Optimization · Time-Optimal Path Parameterization · Nonholonomic Constraint · State Space
Sources: Kinodynamic planning - Wikipedia
Rapidly exploring random tree - Wikipedia（引 LaValle & Kuffner 2001, Randomized Kinodynamic Planning, IJRR） (Chinese)