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

📄 arXiv: 2407.12962v2 📥 PDF

作者: Jiayi Wang, Saeid Samadi, Hefan Wang, Pierre Fernbach, Olivier Stasse, Sethu Vijayakumar, Steve Tonneau

分类: cs.RO

发布日期: 2024-07-17 (更新: 2024-10-10)

备注: Accepted in Humanoids 2024

💡 一句话要点

NAS算法：高效计算人形机器人步态规划的所有可行解

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 步态规划 人形机器人 接触规划 全局优化 GPU并行化

📋 核心要点

  1. 现有步态规划方法难以同时兼顾连续性和离散性，无法高效地找到所有可行解，阻碍了机器人运动的全局优化。
  2. NAS算法通过同时考虑连续和离散因素，枚举并优化所有可能的接触方案，从而获得全局最优的步态规划策略。
  3. 实验表明，NAS算法在Talos机器人上实现了高效的步态规划，并通过GPU并行化进一步提升了计算效率。

📝 摘要（中文）

本文提出了一种名为NAS的算法，旨在解决接触规划问题，即在给定步数内，人形机器人有多少种方式可以攀登楼梯。与关注连续性的方法不同，NAS同时考虑问题的连续性和离散性，计算所有可能的解决方案，即机器人哪些执行器将踩在哪个表面以及以什么顺序踩踏。据我们所知，NAS是第一个产生全局最优策略的算法，可以实时高效地查询，用于规划人形机器人的下一步动作。实验结果表明，尽管理论上复杂度呈指数级增长，但优化将NAS的实际复杂度降低到可管理的双线性形式，同时保持完整性保证，并实现高效的GPU并行化。NAS已在Talos机器人上进行了模拟和硬件平台验证。未来的工作将集中于进一步减少计算时间，并将算法的适用性扩展到步态运动之外。

🔬 方法详解

问题定义：论文旨在解决人形机器人步态规划中的接触规划问题。现有方法通常难以同时处理连续的运动参数和离散的接触点选择，导致无法找到所有可行的步态方案，也难以进行全局优化。现有的方法可能陷入局部最优，或者计算复杂度过高，难以实时应用。

核心思路：NAS算法的核心思路是同时考虑步态规划的连续性和离散性。它通过枚举所有可能的接触点序列（离散部分），并在每个序列下优化连续的运动参数，从而找到所有可行的步态方案。这种方法保证了全局最优性，并允许机器人根据环境和任务选择最佳的步态。

技术框架：NAS算法的整体框架可以概括为以下几个步骤：1. 定义机器人的运动学和动力学模型。2. 枚举所有可能的接触点序列。3. 对于每个接触点序列，使用优化算法（例如，非线性规划）求解最优的运动参数。4. 评估每个步态方案的代价函数值。5. 选择代价函数值最小的步态方案作为最终结果。该框架利用GPU进行并行化计算，加速枚举和优化过程。

关键创新：NAS算法的关键创新在于它能够同时处理步态规划的连续性和离散性，从而找到所有可行的步态方案。与传统的基于采样的或基于优化的方法不同，NAS算法保证了全局最优性。此外，NAS算法通过优化减少了实际的计算复杂度，使其能够应用于实时控制。

关键设计：NAS算法的关键设计包括：1. 使用高效的枚举算法来生成所有可能的接触点序列。2. 使用优化的非线性规划求解器来优化每个接触点序列下的运动参数。3. 设计合适的代价函数来评估每个步态方案的质量，例如，考虑步态的稳定性、能量消耗和运动平滑性。4. 利用GPU进行并行化计算，加速枚举和优化过程。具体的参数设置和损失函数选择取决于具体的机器人和任务。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，NAS算法能够在Talos机器人上实现高效的步态规划。尽管理论复杂度呈指数级增长，但通过优化，实际复杂度降低到可管理的双线性形式。在模拟和硬件平台上的实验都验证了NAS算法的有效性。视频演示展示了NAS算法在各种场景下的应用，例如在不平坦地形上的行走。

🎯 应用场景

NAS算法可应用于各种人形机器人步态规划场景，例如复杂地形行走、避障运动、人机协作等。该算法能够为机器人提供全局最优的步态策略，提高其运动的稳定性和效率。此外，NAS算法还可以用于步态生成和步态学习，为机器人提供更多样化的运动能力。未来，该算法有望应用于医疗康复、灾难救援等领域。

📄 摘要（原文）

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, \emph{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 \emph{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 video is available at \url{https://youtu.be/I5yFe0ez0sI}