Footstep planning on uneven terrain with mixed-integer convex optimization
Open Access
- 1 November 2014
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21640572,p. 279-286
- https://doi.org/10.1109/humanoids.2014.7041373
Abstract
We present a new method for planning footstep placements for a robot walking on uneven terrain with obstacles, using a mixed-integer quadratically-constrained quadratic program (MIQCQP). Our approach is unique in that it handles obstacle avoidance, kinematic reachability, and rotation of footstep placements, which typically have required non-convex constraints, in a single mixed-integer optimization that can be efficiently solved to its global optimum. Reachability is enforced through a convex inner approximation of the reachable space for the robot's feet. Rotation of the footsteps is handled by a piecewise linear approximation of sine and cosine, designed to ensure that the approximation never overestimates the robot's reachability. Obstacle avoidance is ensured by decomposing the environment into convex regions of obstacle-free configuration space and assigning each footstep to one such safe region. We demonstrate this technique in simple 2D and 3D environments and with real environments sensed by a humanoid robot. We also discuss computational performance of the algorithm, which is currently capable of planning short sequences of a few steps in under one second or longer sequences of 10-30 footsteps in tens of seconds to minutes on common laptop computer hardware. Our implementation is available within the Drake MATLAB toolbox [1].This publication has 13 references indexed in Scilit:
- Anytime search-based footstep planning with suboptimality boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Real-time replanning using 3D environment for humanoid robotPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Comprehensive summary of the Institute for Human and Machine Cognition’s experience with LittleDogThe International Journal of Robotics Research, 2011
- Bounding on rough terrain with the LittleDog robotThe International Journal of Robotics Research, 2010
- Online Walking Motion Generation with Automatic Footstep PlacementAdvanced Robotics, 2010
- An adaptive action model for legged navigation planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Vision-guided humanoid footstep planning for dynamic environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Multi-Step Motion Planning for Free-Climbing RobotsPublished by Springer Science and Business Media LLC ,2005
- Convex OptimizationPublished by Cambridge University Press (CUP) ,2004
- Footstep planning among obstacles for biped robotsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002