Real-time footstep planning using a geometric approach

To this date, many footstep planning systems rely on external sensors for mapping and traversability analysis or on computationally expensive algorithms that do not allow for real-time calculations. In this paper, we present an approach that analyzes the environment in the vicinity of the robot with an onboard RGBD camera while computing local footstep plans in real time. We achieve this by combining the advantages of grid-based height maps, fast planar region segmentation, and a systematic local footstep search to a local goal point. Using a single CPU core, a full mapping and planning cycle only takes 18 ms on average and thus presents an important step to autonomous humanoid robots in dynamic environments that only rely on their onboard hardware.