Motion planning answers a plain question: how does a robot get from here to there without hitting anything? The answer must respect geometry, the robot's own limits and often time. It is search in a space that is large and continuous, so clever representations matter more than brute force.
Key concepts
- Configuration space: each robot pose is a point, and obstacles become forbidden regions.
- Graph search: Dijkstra's algorithm and A* find shortest paths on grids and roadmaps.
- Sampling-based planning: RRT and PRM explore high-dimensional spaces by random sampling.
- Trajectory optimisation: smooth, feasible motion that respects velocity, acceleration and dynamics.
- Replanning: reacting to moving obstacles and changing maps while moving.
Vocabulary
- Holonomic: a robot that can move in any direction instantly, unlike a car.
- Collision checking: testing whether a pose or a path touches an obstacle.
- Completeness: a planner that finds a path whenever one exists.
- Cost map: a grid where each cell has a price for passing through it.
What to study, in order
- Graph search and the A* algorithm on a grid, implemented by hand.
- Configuration space for a two-link arm, drawn and then computed.
- Implement RRT in two dimensions and watch it explore.
- Smooth a path into a trajectory with velocity and acceleration limits.
- Use a planning library with a simulated robot and compare planners on the same problem.