Anytime search-based footstep planning with suboptimality bounds
- 1 November 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Efficient footstep planning for humanoid navigation through cluttered environments is still a challenging problem. Many obstacles create local minima in the search space, forcing heuristic planners such as A* to expand large areas. The goal of this work is to efficiently compute long, feasible footstep paths. For navigation, finding the optimal path initially is often not needed as it can be improved while walking. Thus, we propose anytime search-based planning using the anytime repairing A* (ARA*) and randomized A* (R*) planners. This allows to obtain efficient paths with provable suboptimality within short planning times. Opposed to completely randomized methods such as rapidly-exploring random trees (RRTs), these planners create paths that are goal-directed and guaranteed to be no more than a certain factor longer than the optimal solution. We thoroughly evaluated the planners in various scenarios using different heuristics. ARA* with the 2D Dijkstra heuristic yields fast and efficient solutions but its potential inadmissibility results in non-optimal paths for some scenarios. R*, on the other hand borrows ideas from RRTs, yields fast solutions, and is less dependent on a well-designed heuristic function. This allows it to avoid local minima and reduces the number of expanded states.Keywords
This publication has 12 references indexed in Scilit:
- Adaptive level-of-detail planning for efficient humanoid navigationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Anytime Motion Planning using the RRT*Published by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Humanoid navigation with dynamic footstep plansPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Planning Long Dynamically Feasible Maneuvers for Autonomous VehiclesThe International Journal of Robotics Research, 2009
- Search-based planning for a legged robot over rough terrainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- An improved hierarchical motion planner for humanoid robotsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- A modular architecture for humanoid robot navigationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Non-gaited humanoid locomotion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Autonomous 3D walking system for a humanoid robot based on visual step recognition and 3D foot step plannerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Generating near minimal spanning control sets for constrained motion planning in discrete state spacesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005