Search papers, labs, and topics across Lattice.
The paper introduces CASSR, a continuous A* search algorithm for real-time footstep planning that recursively propagates convex, continuous formulations of kinematic constraints. CASSR leverages a novel cost-to-go heuristic based on the EPA algorithm to efficiently plan contact sequences. Experiments on biped locomotion show CASSR achieves up to 100x speedup over traditional discretized A* and outperforms commercial MIP solvers, enabling real-time performance.
Bipedal robots can now plan 30-step trajectories in under 125ms, thanks to a continuous A* search that smokes discretized methods and MIP solvers.
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.
