Adaptive level-of-detail planning for efficient humanoid navigation

In this paper, we consider the problem of efficient path planning for humanoid robots by combining grid-based 2D planning with footstep planning. In this way, we exploit the advantages of both frameworks, namely fast planning on grids and the ability to find solutions in situations where grid-based planning fails. Our method computes a global solution by adaptively switching between fast grid-based planning in open spaces and footstep planning in the vicinity of obstacles. To decide which planning framework to use, our approach classifies the environment into regions of different complexity with respect to the traversability. Experiments carried out in a simulated office environment and with a Nao humanoid show that (i) our approach significantly reduces the planning time compared to pure footstep planning and (ii) the resulting plans are almost as good as globally computed optimal footstep paths.