NAS: N-step computation of All Solutions to the footstep planning problem - Équipe Mouvement des Systèmes Anthropomorphes
Conference Papers Year : 2024

NAS: N-step computation of All Solutions to the footstep planning problem

Abstract

How many ways are there to climb a staircase in a given number of steps? Infinitely many, if we focus on the continuous aspect of the problem. A finite, possibly large number if we consider the discrete aspect, i.e. on which surface which effectors are going to step and in what order. We introduce NAS, an algorithm that considers both aspects simultaneously and computes all the possible solutions to such a contact planning problem, under standard assumptions. To our knowledge NAS is the first algorithm to produce a globally optimal policy, efficiently queried in real time for planning the next footsteps of a humanoid robot.

Our empirical results (in simulation and on the Talos platform) demonstrate that, despite the theoretical exponential complexity, optimisations reduce the practical complexity of NAS to a manageable bilinear form, maintaining completeness guarantees and enabling efficient GPU parallelisation. NAS is demonstrated in a variety of scenarios for the Talos robot, both in simulation and on the hardware platform. Future work will focus on further reducing computation times and extending the algorithm's applicability beyond gaited locomotion. Our companion video is available at https://youtu.

Fichier principal
Vignette du fichier
2407.12962v1.pdf (21.58 Mo) Télécharger le fichier
Origin Files produced by the author(s)
licence
Public Domain

Dates and versions

hal-04730135 , version 1 (10-10-2024)

Licence

Public Domain

Identifiers

Cite

Jiayi Wang, Saeid Samadi, Hefan Wang, Pierre Fernbach, Olivier Stasse, et al.. NAS: N-step computation of All Solutions to the footstep planning problem. International Conference on Humanoid Robotics 2024, Nov 2024, Nancy, France. ⟨hal-04730135⟩
31 View
5 Download

Altmetric

Share

More