Solving Footstep Planning as a Feasibility Problem Using L1-Norm Minimization
- 14 June 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 6 (3) , 5961-5968
Abstract
One challenge of legged locomotion on uneven terrains is to deal with both the discrete problem of selecting a contact surface for each footstep and the continuous problem of placing each footstep on the selected surface. Consequently, footstep planning can be addressed with a Mixed Integer Program (MIP), an elegant but computationally demanding method, which can make it unsuitable for online planning. We reformulate the MIP into a cardinality problem, then approximate it as a computationally efficient l 1-norm minimisation, called SL1M. Moreover, we improve the performance and convergence of SL1M by combining it with a sampling-based root trajectory planner to prune irrelevant surface candidates. Our tests on the humanoid Talos in four representative scenarios show that SL1M always converges faster than MIP. For scenarios when the combinatorial complexity is small ($<; 10$ surfaces per step), SL1M converges at least two times faster than MIP with no need for pruning. In more complex cases, SL1M converges up to 100 times faster than MIP with the help of pruning. Moreover, pruning can also improve the MIP computation time. The versatility of the framework is shown with additional tests on the quadruped robot ANYmal.Keywords
All Related Versions
Funding Information
- ITRC/IITP program (IITP-2021-0-01460)
- NRF (2017R1A2B3012701)
- Pierre Fernbach, Thomas Flayols, Andrea Del Prete
- Nicolas Mansard and Steve Tonneau
- H2020 project Memmo (ICT-780l684)
This publication has 28 references indexed in Scilit:
- A robust linear MPC approach to online generation of 3D biped walking motion2015
- An Architecture for Online Affordance‐based Perception and Whole‐body PlanningJournal of Field Robotics, 2014
- A direct method for trajectory optimization of rigid bodies through contactThe International Journal of Robotics Research, 2013
- Planning contact points for humanoid robotsRobotics and Autonomous Systems, 2013
- Discovery of complex behaviors through contact-invariant optimizationACM Transactions on Graphics, 2012
- Motion Planning for Legged Robots on Varied TerrainThe International Journal of Robotics Research, 2008
- Enhancing Sparsity by Reweighted ℓ 1 MinimizationJournal of Fourier Analysis and Applications, 2008
- Trajectory optimization of mechanical hybrid systems using SUMT2006
- Motion Planning of Multi-Limbed Robots Subject to Equilibrium Constraints: The Free-Climbing Robot ProblemThe International Journal of Robotics Research, 2006
- Semidefinite ProgrammingSIAM Review, 1996