Footstep Planning

Computing where and in what orientation a legged robot should plant each of its next footsteps.

Footstep planning finds a sequence of safe foot placements (positions and orientations) for a biped or quadruped, taking it from its current position to a goal, while satisfying constraints such as keeping consecutive steps within the leg's reach and avoiding obstacles or gaps. It's a simplified version of full contact motion planning: it handles the whole-body dynamics only loosely, deciding just where the feet go and leaving exactly how the body moves to a controller further downstream. Approaches fall into roughly two categories. Discrete search builds a set of candidate steps and searches over them on a tree using something like A*. Continuous optimization is the other route — MIT's Deits and Tedrake, for example, decomposed the reachable footholds into a set of convex regions in 2014 and used mixed-integer convex optimization to find the globally optimal footstep sequence. Reinforcement-learning locomotion controllers, by contrast, usually decide footholds implicitly.

ExampleDeits and Tedrake's planner guided an Atlas humanoid across a row of stepping stones; removing one stone made it automatically switch to a longer detour route. Short sequences of a few steps solved in under 1 second, while sequences of 10–30 steps took tens of seconds to a few minutes on a laptop.

Also called

Foothold Planning

Related

Gait Planning · Swing Foot Trajectory Planning · Raibert Heuristic · Perceptive Locomotion · Elevation Map · Multi-contact Planning

Sources

Footstep Planning on Uneven Terrain with Mixed-Integer Convex Optimization (Deits & Tedrake, 2014)