Skip to the content ForoHackers
Log inJoin

Motion planning: start here

Motion planning
#365 · Ophuscado · · Report

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

  1. Graph search and the A* algorithm on a grid, implemented by hand.
  2. Configuration space for a two-link arm, drawn and then computed.
  3. Implement RRT in two dimensions and watch it explore.
  4. Smooth a path into a trajectory with velocity and acceleration limits.
  5. Use a planning library with a simulated robot and compare planners on the same problem.

Related tags

#robotics #algorithms #graph-theory #autonomous-systems

Log in or join to reply.