Robot motion planning

The problem, stated properly

Motion planning finds a path from where the robot is to where it needs to be, without hitting anything, while respecting the machine's limits. Stated that way it sounds geometric. The reason it is hard is dimensionality: a seven-joint arm has a seven-dimensional space of configurations, a humanoid has dozens, and the obstacles do not appear as obstacles in that space.

Configuration space

The central idea, and the one worth internalising. Rather than reasoning about the robot's shape moving through the world, planning reasons about a single point moving through configuration space — the space whose axes are the joint values. Every pose of the robot is one point in it.

This makes the problem tractable and destroys intuition. An obstacle that is a simple box in the world becomes a complicated, curved, high-dimensional region in configuration space, and nobody can picture it. Which is why planning is done by algorithms rather than by eye, and why planner behaviour sometimes looks strange from outside.

The algorithm families

Sampling-based planners dominate in practice. Rather than mapping the forbidden regions, they sample random configurations, keep the valid ones, and connect them into a graph or tree until a path emerges. Tree-based variants grow from the start toward the goal and are fast at finding a path; roadmap variants build a reusable graph of a static environment, which pays off when planning repeatedly in the same space. Their strength is that high dimensions do not break them; their weakness is that the path is not optimal and is often visibly inelegant, and they struggle with narrow passages, since random sampling rarely lands in a tight gap.

Optimisation-based planners start from an initial guess and refine it against a cost function covering smoothness, clearance, effort and time. They produce much better-looking motion and can get stuck in local minima, so they are frequently seeded by a sampling planner — rough path first, then polish.

Search-based planners discretise the space and run graph search. Predictable and complete at the chosen resolution, and limited by how badly discretisation scales with dimension.

Learned planners predict promising configurations or whole trajectories from experience, usually to accelerate one of the above rather than to replace it.

Constraints that make it harder

• Kinematic limits. Joint ranges, and the singularities where the arm loses a direction of control — points a planner must route around.
• Dynamics. Velocity, acceleration and torque limits turn a geometric path into a timed trajectory, and a path that is geometrically fine can be dynamically infeasible.
• Task constraints. Carrying an open container means keeping it level throughout, which removes most of the configuration space.
• Balance. For legged and humanoid platforms, the support polygon and centre-of-mass trajectory are planning constraints, not afterthoughts.
• Dynamic obstacles. People move. A plan computed against a snapshot is wrong as soon as it executes.

Replanning, and why it dominates real systems

Any environment with people or moving equipment invalidates plans continuously, so real systems replan constantly rather than planning once. That turns a one-off computation into a latency budget: the planner must return something good enough, quickly enough, repeatedly.

The architecture that results is layered. A slower global planner produces a route; a fast local planner adjusts it against immediate obstacles; a reactive layer below both can stop. Most apparent planning failures are actually failures of this hierarchy — the local layer avoiding into a position the global layer cannot recover from.

Why planning is rarely what fails

Motion planning is one of the most mature areas in robotics. Mature, well-tested libraries exist, and for a well-posed problem in a known environment they work.

What fails around it:

• Perception. A planner given a wrong or incomplete obstacle map plans a correct path through a world that does not exist. Unobserved space treated as free is the classic version.
• Goal specification. Reaching a pose is easy; knowing which pose accomplishes the task is the hard part, and that is a grasp or task problem.
• Replanning latency. A correct plan delivered after the situation changed is not a correct plan.
• Dynamic feasibility. Paths that the controller cannot actually track.
• Uncertainty. Planning against point estimates with no margin for pose error.

Which is the general pattern in this field: the famous hard problem has largely been solved, and the difficulty moved to the interfaces around it.

Motion planning is not grasp planning

These are separate problems that are frequently conflated in conversation and in bug reports, and separating them clarifies a great deal.

Grasp planning asks where to put the gripper: which approach, which contact points, which orientation will hold the object. It is a perception and contact problem, it depends on object geometry and material, and it is where most manipulation difficulty actually lives.

Motion planning asks how to get the gripper there. It is a geometry and kinematics problem, and it is comparatively mature.

The dependency runs one way and tightly: a grasp that is geometrically unreachable is not a grasp, so good systems generate several candidate grasps ranked by quality and let the motion planner reject the ones it cannot reach. A system that commits to a single best grasp and then discovers the arm cannot get there has coupled the two problems in the expensive direction, and the symptom — frequent planning failures — points at the wrong layer.

Practical notes

• Seed optimisation planners with a sampled path rather than hoping they escape local minima.
• Inflate obstacles by the actual uncertainty of your perception, not by a guessed margin.
• Treat unobserved space as occupied until proven otherwise.
• Measure replanning latency under load, not on an idle machine.
• Separate "can the robot reach it" from "is this the right thing to reach for". They fail differently and are usually conflated in bug reports.

Planning for a humanoid specifically

Everything above applies to an arm bolted to a bench. A legged, balancing machine adds constraints that change the problem rather than merely enlarging it.

• The base is not fixed. An arm's reachable workspace is a known volume. A humanoid can step, so reachability becomes a planning decision rather than a lookup, and the planner must decide whether to reach or to reposition.
• Balance is a hard constraint throughout. The centre of mass must stay within the support polygon for the whole trajectory, not just at the endpoints. A path that is valid at every sampled configuration can still topple the machine between samples.
• Whole-body coordination. Reaching with one arm moves the centre of mass, which the legs must compensate for. The degrees of freedom are coupled, so planning them independently produces motion that is individually valid and jointly unstable.
• Failure is not a stop. An arm that fails to plan stands still. A biped that fails mid-motion falls, and falling is an outcome with hardware and safety consequences.
• Contact is part of the plan. Where to place a foot, whether to brace against a surface, when to use a handrail — these are planning decisions in a way they never are for a fixed arm.

This is the practical reason humanoid platforms keep whole-body control and balance inside the manufacturer's own stack rather than exposing them. It is not commercial protectionism; it is that the layer cannot be safely owned by a third party who cannot see the full state of the machine.

Where planning meets uncertainty

A planner given exact geometry produces an exact path. Real geometry is an estimate, and the gap between those two facts is where a surprising number of collisions come from.

The common response is to inflate obstacles by a safety margin, which works and has a cost: inflate too little and you clip things, inflate too much and narrow passages close entirely, making the planner report failure in a space the robot could physically traverse. The margin should come from the measured uncertainty of the perception system rather than from a round number someone chose, and it should differ by sensor and by distance — depth error typically grows with range, so a fixed margin is simultaneously too tight far away and too loose up close.