motionplanning

Motion planning is the process of computing a feasible motion for a system to move from a start state to a goal state while avoiding collisions and adhering to kinematic and dynamic constraints. It encompasses both geometric path planning, which seeks a collision-free path in the configuration space, and trajectory planning, which yields a time-parameterized motion that respects dynamics and timing requirements.

In robotics and automation, the environment is transformed into a configuration space (C-space) where obstacles map to forbidden regions. A plan is a continuous curve in C-space (or a trajectory in state space) connecting the start to the goal and staying within free space. Planning can be done offline, online, single-query, or multi-query, and may incorporate uncertainty and nonholonomic constraints.

Approaches to motion planning include sampling-based methods such as Probabilistic Roadmaps (PRM) and Rapidly-exploring Random Trees (RRT) and their variants like RRT* which is asymptotically optimal. Other methods use grid- or lattice-based representations, while optimization-based approaches (CHOMP, TrajOpt, STOMP) formulate planning as a trajectory optimization problem. Kinodynamic planning extends geometric planning to respect system dynamics. In practice, many systems combine decoupled path planning with subsequent trajectory optimization and employ online re-planning in dynamic environments.

Key properties of motion-planning algorithms include completeness (guarantee of finding a solution if one exists under certain conditions), probabilistic completeness for sampling-based methods, and sometimes asymptotic optimality (convergence to the best possible plan over time). Computational bottlenecks often lie in collision checking and searching high-dimensional spaces.

Applications span autonomous vehicles, mobile and legged robots, robotic manipulation, drone flight, computer animation, and industrial automation.