robotics//motion planning

Motion planning is the problem of finding a collision-free, low-cost path or sequence of motions that takes a robot from a start to a goal, either by searching a graph built from the environment or by sampling a continuous space; it runs between the map and the controller in every warehouse robot, autonomous car, inspection drone and robot arm. What goes in is a map of obstacles, the robot's shape and limits, a start and a goal; what comes out is a path (or a trajectory with timing) that a controller then tracks.

Motion planning is the problem of finding a collision-free, low-cost path or sequence of motions that takes a robot from a start to a goal, either by searching a graph built from the environment or by sampling a continuous space; it runs between the map and the controller in every warehouse robot, autonomous car, inspection drone and robot arm. What goes in is a map of obstacles, the robot's shape and limits, a start and a goal; what comes out is a path (or a trajectory with timing) that a controller then tracks.

The members of the family split the job. A floor is first turned into a graph: an occupancy grid divides it into cells, and every free cell becomes a node. Graph search then finds the cheapest route through it, Dijkstra's algorithm spreading from the start like an oil stain, A* search steering toward the goal with a heuristic estimate of the distance left. What the planner really searches is the robot's configuration space, one point per possible pose; for a wheeled robot it has three dimensions and a grid copes, for a seven-joint arm it has seven and grids drown, which is where RRT samples the space at random instead.

A* with an admissible heuristic is optimal, RRT opens spaces of many dimensions, and an anytime planner always has something to offer when the clock rings.

The shortest path is not the path a robot drives. It grazes corners and ignores how the vehicle turns and brakes, so planning is layered: a global geometric planner at about 1 Hz finds the route, a local planner with the robot's dynamics at 10 to 20 Hz follows it around people and pallets, and the controller underneath runs much faster. If a planner misses its deadline, the layer below keeps the last valid plan or performs a safe manoeuvre, and designing that default is as important as the algorithm.

Both families are industry. Robot arms planning with MoveIt use the OMPL library, full of RRT variants; the navigation stack of ROS 2 (Nav2) ships A*-family planners, including Hybrid A*, which searches over continuous headings for vehicles that cannot turn in place. In sampling planners the dominant cost is collision checking, testing each candidate motion against the obstacles, far more than growing the tree.

Sometimes no online planner is needed. In a warehouse with fixed aisles, routes precomputed on a small graph plus priority rules at crossings are enough; online planning pays when the environment changes or the space is large and continuous.