Footstep planning

Planning discrete contacts#

A path can say where a robot body should travel without saying where either foot can land. A footstep plan adds discrete contact decisions: which foot moves next and the position and orientation of each landing. It can also include timing, partial footholds, or a cost for awkward steps.

Search-based planners commonly expand candidate steps on a lattice. Optimisation-based planners can choose continuous poses while enforcing geometric constraints. Deits and Tedrake formulated uneven-terrain footstep planning as mixed-integer convex optimisation, illustrating that footstep planning is not tied to one search method.

From terrain to executable steps#

A planner needs a terrain representation and a model of feasible relative foot placements. It may reject surfaces that are too small, steep, obstructed, or unreachable. The rough-terrain planner reported by Griffin and colleagues uses planar regions, permits partial footholds, and was demonstrated with Atlas and Valkyrie humanoid robots in virtual and physical environments.

The output remains a plan rather than motor commands. A walking controller must turn the selected contacts into swing trajectories, body motion, and contact forces while maintaining bipedal locomotion. The required margin depends on the controller, state estimate, and foot geometry.

A geometrically valid step can still fail#

Terrain sensing may miss an edge or estimate the surface normal incorrectly. A foot pose can satisfy static reachability while requiring excessive speed, joint torque, friction, or body momentum during execution. Planning with simplified reachability or balance models trades physical detail for speed.

Replanning can respond to updated terrain or tracking error, but it introduces its own latency. A useful evaluation separates planning time and plan quality from execution success, and reports the terrain assumptions and whether tests occurred only in simulation.