Motion Planning

A robot that knows where it is (via SLAM or GPS) and what it wants to do must still determine how to move to accomplish its goals without colliding with obstacles or violating its own physical constraints. Motion planning is the field that computes these collision-free trajectories, covering problems from 2D robot navigation to high-dimensional robot arm manipulation in cluttered environments.

The configuration space (C-space) concept is central to motion planning. Instead of reasoning about the robot in 3D space, we reason about all possible configurations of the robot (joint angles for an arm, position and heading for a mobile robot). Obstacles in 3D space correspond to forbidden regions in C-space (configurations where the robot would collide). Motion planning becomes finding a path through the free C-space from start configuration to goal configuration.

Grid-based planners discretise the environment and use graph search algorithms (Dijkstra's, A*) to find shortest paths. A* with an admissible heuristic (like Euclidean distance to goal) efficiently finds optimal paths in grid environments. Probabilistic grid representations and multi-resolution grids handle large environments efficiently. Grid methods work well for 2D navigation but scale poorly to high-dimensional C-spaces (a 6-DOF robot arm has 6-dimensional C-space).

Sampling-based planners address high-dimensional spaces. Rapidly-exploring Random Trees (RRT) builds a tree by randomly sampling configurations and connecting them to the nearest existing node (if the connecting path is collision-free). RRT* is the asymptotically optimal variant that rewires the tree to maintain shortest paths. Probabilistic Roadmap Method (PRM) pre-builds a graph by randomly sampling configurations and connecting nearby pairs, then queries the graph for start-to-goal paths. These methods scale to many dimensions and handle complex geometry.

Optimisation-based planners formulate motion planning as an optimisation problem with collision constraints, smoothness objectives, and dynamic feasibility constraints. Trajectory optimisation methods like TrajOpt or CHOMP iteratively refine an initial path to be smooth, collision-free, and dynamically feasible. These produce smooth, high-quality trajectories but require a collision-free initialisation.

Learning-based approaches use neural networks to predict motion plans: learning a policy that maps state to control directly, using learned value functions to guide tree search, or training diffusion models over trajectory distributions that can be conditioned on goal states. These can incorporate complex learned priors but may require extensive robot interaction data.