Perceptive Variable-Timing Footstep Planning for Humanoid Locomotion on Disconnected Footholds

Zhaoyang Xiang; Upama Pant; Ayonga Hereid

cs.ROMar 8, 2026

Perceptive Variable-Timing Footstep Planning for Humanoid Locomotion on Disconnected Footholds

Authors: Zhaoyang Xiang, Upama Pant, Ayonga Hereid

Organizations: Mechanical and Aerospace Engineering, The Ohio State University, Columbus, OH 43210, USA.

Abstract

Walking over disconnected footholds requires selecting landing regions while adapting step timing to the robot's motion. We present a perceptive model predictive planner that combines discrete region selection, foot placement, and current-step duration in a mixed-integer quadratic program using step-to-step Divergent Component of Motion (DCM) dynamics. Onboard depth data are fused into a probabilistic heightmap in the stance foot frame. Convex steppable regions are extracted and shrunk by margins that increase with estimated height uncertainty. Linear constraints impose capturability-based bounds on DCM evolution and limit swing-foot retargeting using the remaining commanded swing time. Within-step replanning updates the initial DCM from measurements to respond to model mismatch and disturbances. We evaluate the framework on Digit in simulation over randomized footholds and on hardware over separated plates, with mean planner solve times of 11.4~~ms and 4.0~~ms, respectively.

Figures & tables

Fig. 1: (Left) Snapshot of one of the random simulation terrains for all ablation tests. The blue rectangles show the planned step position for the previewed steps, and the red bar shows the goal position in the sagittal direction. (Top Right) Local heightmap colored by height. (Bottom Right) Steppable cells (gray), selection window (shaded rectangle), stance foot (red), and convex regions passed to the planner (green polygons).

Fig. 2: Overview of the framework. Perception builds a probabilistic local heightmap from onboard depth cameras and extracts convex steppable regions. Regions with less certain height are shrunk more. The MIQP planner chooses the next footholds and the duration of the current step. The whole-body controller (WBC) tracks a swing-foot trajectory to the planned foothold and computes joint torques. During each swing, the planner is solved again from the measured DCM and swing-foot position.

Fig. 3: From heightmap to steppable regions. Top left: the local heightmap, shaded by height. Top right: candidate steppable cells after thresholding. Bottom right: contours simplified to polygons by RDP. Bottom left: convex hulls represented as linear region constraints.

Panel of Figure 4 — Fig. 4: A successful run of the proposed MIQP planner on one of the 100 randomized test fields. (Left) The robot walks from the left platform to the right platform through the stepping-stone region. The panel shows each landing foot position and how the CoM and DCM evolve. (Middle) Forward CoM velocity stays near 1 m/s over most of the crossing, although the planner does not track the hand-selected nominal velocity. It briefly dropped to about 0.3 m/s near 8 s, when the planner steps almost in-place before a large forward gap. (Right) The MIQP is solved again throughout each swing, and each solve adjusts the current step duration together with the landing position. The planned duration therefore changes throughout the swing, by up to about 0.2 s within one step. The actual duration (diamond) is close to the last planned value. Dotted lines mark step transitions.

Fig. 5: Snapshots in time sequence of the Digit walking through the test field, with the second plate rotated by $+15^{\circ}$ . Key frames 1-3 show the moments when Digit was: starting a step across the first gap, landing the swing foot during the crossing, and walking inside the second plate. Key frames 4-6 and 7-9 show the moments near the second and third gap likewise.

Fig. 6: Hardware heightmaps at selected steps in the current stance foot frame. Lighter gray indicates higher terrain, so the white regions are the detected steppable plates; green polygons mark extracted region constraints; and the dashed blue rectangle is the selection window. The black cross marks the stance foot; blue/orange outlines denote a few left/right feet stance positions before and after the current stance position; and the red star marks the swing target.

	Crossing	Steps	Landing	Infeasible
Configuration	success	to failure	success	solves
	(%)		(%)	(%)
A	83	24.0	99.3	5.8
B	0	3.0	–	79.6
C	74	24.3	99.2	7.3

TABLE I: Ablation of the proposed foot-placement planner in MuJoCo

Humanoid Robot Locomotion

Humanoid robot locomotion studies how bipedal robots walk, run, recover from disturbances, and traverse varied terrain.

See all 145 papers

FootQuery: Future-Touchdown-Guided Retrieval from Depth History for Perceptive Humanoid Locomotion
Sep 18, 2026Tao Dong, Jia Yu, Yuxuan Fan +5Humanoid Robot Locomotion Terrain-Aware Robot Locomotion
Institute for AI Industry Research (AIR), Tsinghua University, Beijing, China. · University of Science and Technology Beijing, Beijing, China. · Nanyang Technological University, Singapore. +1
Mind Your Steps: A General Learning Framework for Accurate Humanoid Foothold Tracking
Jun 6, 2026Alessandro Montenegro, Shihao Li, Puze Liu +2Robot Trajectory Tracking Humanoid Robot Locomotion
Politecnico di Milano · Tongji University · Technische Universität Darmstadt +2
CASSR: Continuous A-Star Search through Reachability for real time footstep planning
Mar 3, 2026Jiayi Wang, Steve TonneauMotion Planning Constrained Motion Planning
State Key Laboratory of General Artificial Intelligence, BIGAI, Beijing 100080, China · University of Edinburgh, IPAB, Edinburgh EH8 9YL, U.K.

Sep 18, 2026J/K move · Enter open · S save

FootQuery: Future-Touchdown-Guided Retrieval from Depth History for Perceptive Humanoid Locomotion

Tao Dong, Jia Yu, Yuxuan Fan, Linna Zhao+4

Institute for AI Industry Research (AIR), Tsinghua University, Beijing, China. · University of Science and Technology Beijing, Beijing, China. · Nanyang Technological University, Singapore.+1

Humanoid Robot Locomotion Terrain-Aware Robot Locomotion Robot Locomotion

Open paper AskPDF arXiv

Humanoid locomotion over complex terrain requires anticipating footholds that may no longer be visible at touchdown. Limited camera coverage and self-occlusion make it necessary to retrieve relevant terrain information from earlier observations. We present FootQuery, a perceptive locomotion framework that queries depth history using each foot's predicted next touchdown. The policy predicts touchdown locations and uncertainty from proprioception and uses these distributions, together with per-foot features, to query sparsely sampled historical depth frames. During training, realized contacts are projected into historical images to supervise retrieval at the regions where those contacts were visible. The retrieved per-foot features are fused with global visual memory to generate control actions. A progressive force-assistance curriculum supports early exploration, while event-consistent tread-midline shaping encourages coordinated stair contacts. Deployment requires only proprioception and onboard depth images. In simulation, the complete framework outperforms its component ablations on the most challenging tested stairs, gaps, and platforms. Real-world experiments on a Unitree G1 demonstrate continuous traversal with a single policy across outdoor stairs and indoor routes combining stair ascent and descent, platforms, and gaps. These results support organizing visual history around anticipated contacts for perceptive humanoid locomotion.

Abstract

Humanoid Robot Locomotion

Explore similar work

FootQuery: Future-Touchdown-Guided Retrieval from Depth History for Perceptive Humanoid Locomotion

Mind Your Steps: A General Learning Framework for Accurate Humanoid Foothold Tracking

CASSR: Continuous A-Star Search through Reachability for real time footstep planning