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

Jiayi Wang; Steve Tonneau

cs.ROMar 3, 2026

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

Authors: Jiayi Wang, Steve Tonneau

Organizations: State Key Laboratory of General Artificial Intelligence, BIGAI, Beijing 100080, China · University of Edinburgh, IPAB, Edinburgh EH8 9YL, U.K.

Abstract

Footstep planning involves a challenging combinatorial search. Traditional A* approaches require discretising reachability constraints, while Mixed-Integer Programming (MIP) supports continuous formulations but quickly becomes intractable, especially when rotations are included. We present CASSR, a novel framework that recursively propagates convex, continuous formulations of a robot's kinematic constraints within an A* search. Combined with a new cost-to-go heuristic based on the EPA algorithm, CASSR efficiently plans contact sequences of up to 30 footsteps in under 125 ms. Experiments on biped locomotion tasks demonstrate that CASSR outperforms traditional discretised A* by up to a factor of 100, while also surpassing a commercial MIP solver. These results show that CASSR enables fast, reliable, and real-time footstep planning for biped robots.

Figures & tables

Panel of Figure 1 — Fig. 1 : The pictures are taken from the back of the robot (the forward direction is towards the stepping stones). Given the position of a foot (grey rectangle) and assuming no rotation, we can compute the reachability constraints for the other foot as a convex polytope (red for constraints on the right foot, green for the left foot). The set of positions reachable from the red polygon (b) is obtained by computing the Minkowski sum of all reachability polytopes for all positions in the polygon (c, d, e). This is computed efficiently as the convex hull of the reachability polytopes of the extreme points (d). Not all extreme points are shown in (d) for readability. The union of the 3 green polygons in (f) is the 2 step-reachable set and corresponds to 3 nodes added to the $A^{*}$ graph.

Fig. 2 : Reachable set (red polytope) for the right foot with respect to the left foot (rectangle), seen from the back of the robot. To avoid leg crossing the right foot is constrained to be “on the right” of the left foot by construction of the set.

Method		Stairs					Local Minima					Narrow Passage
		Computation time (ms)			# of Nodes	# of Steps	Computation time (ms)			# of Nodes	# of Steps	Computation time (ms)			# of Nodes	# of Steps
		A*	QP	Total			A*	QP	Total			A*	QP	Total
CASSR (ours)	without rotation	4.67 $\pm$ 0.17	8.51 $\pm$ 0.88	13.18 $\pm$ 0.91	16	15	8.08 $\pm$ 0.26	33.18 $\pm$ 3.03	41.27 $\pm$ 2.85	42	25	Fail	-	-	-	-
CASSR (ours)	with rotation	10.00 $\pm$ 0.15	4.74 $\pm$ 0.60	14.75 $\pm$ 0.53	33	11	33.66 $\pm$ 0.9	14.61 $\pm$ 0.92	48.27 $\pm$ 0.70	92	19	60.41 $\pm$ 0.46	64.72 $\pm$ 1.22	125.13 $\pm$ 1.43	88	29
Discretized A*	without rotation	4.32 $\pm$ 0.07	-	4.32 $\pm$ 0.07	102	15	61.81 $\pm$ 0.29	-	61.81 $\pm$ 0.29	728	25	Fail	-	-	-	-
Discretized A*	with rotation	38.50 $\pm$ 0.95	-	38.50 $\pm$ 0.95	253	15	6626.53 $\pm$ 45.61	-	6626.53 $\pm$ 45.61	23233	23	1456.19 $\pm$ 15.15	-	1456.19 $\pm$ 15.15	1851	41

TABLE I : Computation times and number of nodes expanded on all scenarios different instances of planners

Panel of Figure 4 — Fig. 3 : Scenarios and contact plans found by CASSR with (line 2) or without (line 1) rotation. Target is the yellow sphere and Talos is always at the start position. The blue (resp. red) rectangles indicate a contact placement for the left (resp. right).

Motion Planning

Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.

See all 405 papers

Perceptive Variable-Timing Footstep Planning for Humanoid Locomotion on Disconnected Footholds
Mar 8, 2026Zhaoyang Xiang, Upama Pant, Ayonga HereidHumanoid Robot Locomotion Terrain-Aware Robot Locomotion
Mechanical and Aerospace Engineering, The Ohio State University, Columbus, OH 43210, USA.
EXACT-MPPI: Exact Signed-Distance Navigation for Arbitrary-Footprint Robots from Point Clouds via Path Integral Control
May 28, 2026Chen Peng, Zhikang Ge, Wenwu Lu +3Robot Navigation Robot Motion Planning
ZJU-Hangzhou Global Scientific and Technological Innovation Center, Zhejiang University, Hangzhou, China · College of Biosystems Engineering and Food Science, Zhejiang University, Hangzhou, China · Department of Biological and Agricultural Engineering, University of California, Davis, Davis, California, USA
KCFRC: Kinematic Collision-Aware Foothold Reachability Criteria for Legged Locomotion
Feb 24, 2026Lei Ye, Haibo Gao, Huaiguang Yang +6Legged Robotics Reachability Analysis
State Key Laboratory of Robotics and Systems, Harbin Institute of Technology, Harbin 150001, China.

Mar 8, 2026J/K move · Enter open · S save

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

Zhaoyang Xiang, Upama Pant, Ayonga Hereid

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

Humanoid Robot Locomotion Terrain-Aware Robot Locomotion Motion Planning Model Predictive Control

Open paper AskPDF arXiv

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.

Abstract

Motion Planning

Explore similar work

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

EXACT-MPPI: Exact Signed-Distance Navigation for Arbitrary-Footprint Robots from Point Clouds via Path Integral Control

KCFRC: Kinematic Collision-Aware Foothold Reachability Criteria for Legged Locomotion