Humanoid robots possess the capability of stepping over or onto objects. When planning paths for humanoids, one therefore should consider an intelligent placement of footsteps instead of choosing detours around obstacles. We propose to combine grid-based 2D planning with footstep planning in an efficient manner. 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.
Recently, We released an update of our footstep planner in the ROS humanoid_navigation stack. The planner is now much faster and builds on SBPL. In addition to the previous D* Lite implementation, this now enables anytime (re-)planning with suboptimality bounds, e.g., with ARA* or AD*.
- Search-Based Footstep Planning.
A. Hornung, D. Maier, and M. Bennewitz.
In: Proceedings of the ICRA Workshop on Progress and Open Problems in Motion Planning and Navigation for Humanoids, 2013.
- Adaptive Level-of-Detail Planning for Efficient Humanoid Navigation.
A. Hornung and M. Bennewitz.
In: Proceedings of the IEEE International Conference on Robotics & Automation (ICRA), 2012.
- Humanoid Navigation with Dynamic Footstep Plans.
J. Garimort, A. Hornung, and M. Bennewitz.
In: Proceedings of the IEEE International Conference on Robotics & Automation (ICRA), 2011.
- Anytime Search-Based Footstep Planning with Suboptimality
A. Hornung, A. Dornbush, M. Likhachev, and M. Bennewitz.
In: Proceedings of the IEEE-RAS International Conference on Humanoid Robots (HUMANOIDS), 2012.
This first part of the video below shows our Nao humanoid robot executing a footstep plan, carefully avoiding obstacles. Note that in this scenario, a conventional 2D path using the robot's circumcircle would lead to suboptimal results or even collisions because there is no direct control of the footstep locations.
In the second part of the video, the robot is traversing its initial path when the location of an obstacle changes after a few steps. Reusing previous information, a new footstep path is efficiently planned.