Footstep planning is one of the most essential components when planning the navigation of humanoid robots. In the future, it may also be a core component for soccer playing humanoids, e.g. in duels or for exact positioning. This presentation will first introduce the basic principles of footstep planning using the A* search. Often, obstacles create local minima in the search space, forcing heuristic planners such as A* to expand large areas. Furthermore, planning longer footstep paths often takes a long time to compute. We will introduce and discuss several solutions to these problems. For navigation, finding the optimal path initially is often not needed as it can be improved while walking. Thus, anytime search-based planning based on the anytime repairing A* or randomized A* search provides promising functionality. It allows to obtain efficient paths with provable suboptimality within short planning times. By adding new stepping capabilities and accounting for the whole body of the robot in the collision check, we extend the footstep planning approach to 3D. This enables a humanoid to step over clutter and climb onto obstacles.
Universität Bonn, Institute for Computer Science, Autonomous Intelligent Systems