Motion Planning

Motion planning is the problem of finding a collision-free path for a robot or autonomous agent from a start configuration to a goal configuration in an environment with obstacles. It is one of the foundational problems in robotics and autonomous systems, bridging computational geometry, control theory, and artificial intelligence.

The problem is harder than it appears. A robot's configuration space — the space of all possible poses — may have six or more dimensions (three for position, three for orientation). Obstacles in physical space become forbidden regions in configuration space, and the planner must find a continuous path through the free space that respects the robot's kinematic and dynamic constraints. The curse of dimensionality makes exhaustive search impossible; practical planners rely on sampling, heuristics, and the exploitation of problem structure.

The dominant algorithms include Rapidly-Exploring Random Trees (RRT), which grow a tree from the start by randomly sampling the configuration space and connecting nearby points; PRM (Probabilistic Roadmap), which pre-samples the free space and connects nearby samples to form a graph; and optimization-based methods like CHOMP and TrajOpt, which formulate planning as trajectory optimization. Each makes a different trade-off between completeness guarantees and computational efficiency.

Motion planning is the physical-world counterpart to informed search and A* search. The heuristic that guides A* — an estimate of remaining cost — is replaced in motion planning by a distance metric in configuration space, and the graph search is replaced by sampling and local connection. The structural identity is deep: both are searching vast spaces using partial knowledge to avoid exhaustive exploration.