CASSR: Continuous A-Star Search through Reachability for Real Time Footstep Planning
Jiayi Wang, Steve Tonneau
AI summary
Problem
Traditional A* requires discretizing reachability constraints, limiting solution space and efficiency, while Mixed-Integer Programming (MIP) handles continuous constraints but becomes computationally intractable for real-time planning, especially with rotations.
Approach
CASSR reformulates A* to search over continuous contact surfaces using recursively propagated convex reachability polytopes, paired with a novel EPA-based cost-to-go heuristic and a robust safety cost, followed by a Quadratic Program to compute exact footstep positions.
Key results
- Plans up to 30 footsteps in under 125 ms
- Outperforms discretized A* by up to 100x in computational speed
- Surpasses commercial MIP solvers on complex locomotion tasks
- Guarantees feasible foot placements via post-search Quadratic Program
Why it matters
Enables real-time, robust footstep planning for bipedal robots in complex environments, advancing practical deployment of legged locomotion systems.
Abstract
Footstep planning involves a challenging combi- natorial 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. Video: http://youtu.be/reDGK-VXg9k