Humanoid footstep planning converts a navigation objective into an ordered sequence of left and right foot poses. Each step must be reachable from the current stance, place enough of the sole on supportable terrain and leave a transition that the whole body can execute without collision or loss of balance.
The planner does not finish when it finds geometric footprints. Swing clearance, contact timing, center-of-mass motion, perception uncertainty and controller tracking decide whether the sequence works on hardware. Online replanning must also respect the step already in flight.
Use this guide with the humanoid balance guide and whole-body control guide. Validate planned and executed footprints on the same timeline.
Represent a footstep as pose, support and timing
A useful footstep contains foot identity, position, yaw or full orientation, contact patch, swing timing and expected support transition. A point location is insufficient on narrow, tilted or discontinuous terrain because sole geometry determines actual support.
Define the world, map, stance and sole frames explicitly. Record whether the pose describes the ankle, sole center or another reference, and transform terrain measurements into the same convention.
Bound reachable step generation
Generate candidate steps inside measured limits for forward length, lateral width, yaw, height and crossover. The bounds depend on stance, pelvis motion, joint limits, collision and dynamic speed; a rectangular reach box is only a rough first filter.
Include backward and recovery steps if the controller supports them. Reject candidates that require leg crossing, extreme hip yaw or near-singular posture even when an endpoint inverse-kinematics solution exists.
| Candidate test | Question | Useful margin | Failure symptom |
|---|---|---|---|
| Reach | Can the swing foot arrive? | Joint and posture margin | IK failure |
| Support | Does the sole fit terrain? | Edge and slope margin | Rocking contact |
| Swing | Can the foot clear obstacles? | Swept-volume clearance | Toe collision |
| Balance | Can momentum transfer? | ZMP or capture margin | Unrecoverable step |
| Sequence | Is the next stance useful? | Successor count | Dead end |
Score supportable terrain under the full sole
Use height, slope, roughness, normal, semantic class and uncertainty across the complete foot polygon. A center point on a stair tread can hide heel overhang or a raised edge under the sole. Partial footholds need a controller and contact model qualified for them.
Inflate obstacles and shrink support regions according to perception and localization error. Keep unknown space distinct from known free space so the planner cannot convert missing measurements into confident support.
Search sequences rather than isolated good steps
A low-cost first step may lead to a dead end, awkward stance or unreachable next foothold. Graph search, lattice methods or sampling should include future feasibility, step count, direction change and recovery options in the cost.
The CMU biped navigation work frames footsteps as navigation decisions in complex terrain. Search design should still match the current robot, map resolution and execution horizon.
Use heuristic guidance without hiding alternatives
A navigation path or homotopy class can guide the footstep search around large obstacles and reduce exploration. Overly strong guidance may miss a feasible sequence that temporarily moves away from the nominal path or uses a different passage.
The homotopy-guided footstep planning paper illustrates this strategy. Preserve fallback search and log which heuristic pruned a candidate when diagnosing failures.
Verify swing-foot swept volume
Collision checks must include toe, heel, sole and lower leg over the complete swing trajectory. Linear interpolation between two valid foot poses can strike a step edge or obstacle, especially when terrain height changes.
Generate clearance profiles that fit obstacle geometry and the controller’s velocity and acceleration limits. Test early contact and missed touchdown behavior rather than assuming the nominal swing duration always completes.
Check whole-body and self-collision feasibility
Feet do not move independently of pelvis, knees, torso and arms. A footprint sequence can satisfy local reach limits yet force a knee collision, torso contact or angular-momentum demand outside the controller envelope.
Use a kinematic or trajectory feasibility layer before execution, then preserve margin for state-estimation and terrain error. The motion-planning comparison helps distinguish discrete route search from continuous whole-body refinement.
Connect footsteps to balance dynamics
The walking controller must move center of mass and angular momentum so contact forces remain feasible through each support phase. Step location, duration and orientation change the capture region; a geometrically reachable pose may arrive too late to recover balance.
Expose timing tolerance and capture margin to the planner where possible. For nominal walking, preserve a stop-capable stance. For disturbance recovery, prioritize a timely stabilizing foothold over path elegance.
Respect committed and uncommitted steps
Once the swing foot has accelerated or the support transfer has started, replacing the target abruptly can violate kinematic and dynamic limits. Divide the plan into committed execution and a replannable suffix with a declared update deadline.
When perception changes, validate whether the active step can be adjusted, must land early or requires a protective stop. Do not publish a fresh global path as though every footprint were equally editable.
Reuse plans only after state and map checks
Plan reuse can reduce computation when nearby stance and terrain states share a valid suffix. It can also reproduce an obsolete foothold after localization drift, terrain motion or a different support foot. Revalidate transforms, support and collision before reuse.
The online footstep planning study provides historical evidence for online planning and reuse. Modern deployment still needs bounded latency and current sensor checks.
Evaluate terrain, timing and execution together
Measure planning success and time, expanded states, path cost, minimum support and collision margin, executed foot-pose error, contact timing, slip, replans and falls. Segment results by stairs, gaps, slopes, clutter and perception quality.
Record the requested and measured footprint plus state-estimator covariance. A plan should not receive full credit when the controller lands elsewhere but happens to remain upright.
| Test factor | Variation | Planner metric | Execution metric |
|---|---|---|---|
| Terrain | Step, gap, slope, debris | Search success | Foot support |
| Perception | Noise, holes, latency | Robust path rate | Unexpected contact |
| Dynamics | Speed and disturbance | Capture margin | Recovery success |
| Replan | Obstacle or state change | Update latency | Committed-step safety |
| Model | Joint and sole uncertainty | Feasible margin | Pose and force error |
Release with a footstep-planning contract
Document foot reference frame, reach limits, support criteria, collision geometry, dynamic interface, committed horizon, map uncertainty and recovery behavior. Store terrain, robot model, planner parameters and controller version with benchmarks.
Close validation with the following checklist.
- Check the complete sole and swing volume.
- Search sequences with successor and stop feasibility.
- Verify whole-body and balance constraints.
- Protect committed steps during online replanning.
- Compare planned and measured footprints under uncertainty.
Frequently asked questions
Is a reachable foot pose automatically a safe step?
No. Support area, swing clearance, whole-body feasibility, balance timing and the next stance must also be valid.
Why check the full sole instead of its center?
A center point can lie on support while the heel, toe or side overhangs an edge or contacts a raised obstacle.
Can every step be replanned immediately?
No. A step already in swing or support transfer has a committed execution horizon and only bounded adjustment is safe.
Should the planner always minimize step count?
No. Fewer steps can reduce margin, create long reaches or remove recovery options; cost must reflect execution risk.
What proves footstep-planning performance?
Report search and execution metrics together across terrain, perception error, disturbances, replanning and recovery.
Committed-Step and Recoverable-Stance Boundary
A footprint sequence is an executable contract only after support, swing, whole-body, balance and committed-step constraints agree on the same state and time.