  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.be/Shkf8PyDg4g
