Footstep planning for humanoid robots

Abstract

Humanoid robot locomotion involves trajectories that are much harder to generate and control than the ones for other robots locomotion. Therefore, motion planning problems for humanoid robots are of particular interest. We consider the footstep planning problem for humanoid robots. In particular, we consider a special case of the reachability problem in a free unbounded environment, the reachability with arbitrary steps problem. We show NP-completeness of the problem.