Fast Footstep Planning with Aborting A*

Footstep planning is the dominating approach when it comes to controlling the walk of a humanoid robot, even though a footstep plan is expensive to compute. The most prominent proposals typically spend up to a few seconds of computation time and output a sequence of up to 30 steps all the way to the goal. This way, footstep planning is applicable only in static environments where nothing changes after a plan has been computed. Since uncontrolled environments present challenges such as unforeseen motion of other objects and unexpected disturbances to balance, fast replanning of a footstep plan while the robot is in motion is highly desirable. We present a new way of fast footstep planning - Aborting A* - which is able to guarantee a replanning rate of 50 Hz by aborting an A* search before completion. We make aborting possible by using a novel, obstacle-aware heuristic function that lays out rotate-translate-rotate motions along the shortest path to the goal, enabling us to stop the planning progress prematurely with a target-oriented solution at any time during the search, even after only a few nodes have been expanded. We show in our experiments that despite the bounded computation time, our planner computes good results and does not get stuck in local minima.