Integrated perception, mapping, and footstep planning for humanoid navigation among 3D obstacles

In this paper, we present an integrated navigation system that allows humanoid robots to autonomously navigate in unknown, cluttered environments. From the data of an onboard consumer-grade depth camera, our system estimates the robot's pose to compensate for drift of odometry and maintains a heightmap representation of the environment. Based on this model, our system iteratively computes sequences of safe actions including footsteps and whole-body motions, leading the robot to target locations. Hereby, the planner chooses from a set of actions that consists of planar footsteps, step-over actions, as well as parameterized step-onto and step-down actions. To efficiently check for collisions during planning, we developed a new approach that takes into account the shape of the robot and the obstacles. As we demonstrate in experiments with a Nao humanoid, our system leads to robust navigation in cluttered environments and the robot is able to traverse highly challenging passages.