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 l1-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.
翻译:在不均匀的地形上,脚踏式的脚踏式脚踏板在脚踏板选择接触表面的不切实际的问题和将每一脚踏脚踏在所选表面的连续问题处理。 因此,脚步规划可以用混合整数程序(MIP)来解决,这是一种优雅的、但需要计算的方法,可以使其不适于在线规划。 我们把MIP重新改造成一个最根本的问题,然后把它作为计算效率低的l1-中度最小化,称为SL1M。 此外,我们通过将SL1M与基于取样的根根轨迹规划器结合到不相关的表面候选人,改进SL1MM的性能和汇合。我们在四个具有代表性的情景中对人造图塔洛斯的测试显示,SL1M总是比MIP更快。对于组合复杂程度小(每步 < 10个表面/每步) 的情况,SL1M至少比MIP快两倍,不需要钻。 此外,在更复杂的案例中,SL1MMM比MIP更快100倍地结合, 并显示多的MAIP的计算框架。