CASSR: Continuous A-Star Search through Reachability for real time footstep planning

📄 arXiv: 2603.02989v1 📥 PDF

作者: Jiayi Wang, Steve Tonneau

分类: cs.RO

发布日期: 2026-03-03

💡 一句话要点

CASSR：基于可达性分析的连续A*搜索，实现机器人实时步态规划

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

关键词: 步态规划 A*搜索 可达性分析 凸优化 双足机器人

📋 核心要点

  1. 传统步态规划方法如离散化A*和MIP在处理高维连续空间时面临计算效率和精度的挑战。
  2. CASSR通过递归传播凸连续运动学约束，并在A*搜索中集成EPA启发式方法，实现了高效的步态规划。
  3. 实验结果表明，CASSR在速度和性能上显著优于离散化A*和商业MIP求解器，可实现实时步态规划。

📝 摘要（中文）

步态规划涉及具有挑战性的组合搜索。传统的A方法需要离散化可达性约束，而混合整数规划(MIP)支持连续公式，但很快变得难以处理，尤其是在包含旋转时。我们提出CASSR，这是一种新颖的框架，它在A搜索中递归地传播机器人运动学约束的凸连续公式。结合基于EPA算法的新cost-to-go启发式方法，CASSR可以在125毫秒内有效地规划多达30个步点的接触序列。在双足运动任务上的实验表明，CASSR的性能优于传统的离散化A*方法高达100倍，同时也超过了商业MIP求解器。这些结果表明，CASSR能够为双足机器人实现快速、可靠和实时的步态规划。

🔬 方法详解

问题定义：步态规划旨在为双足机器人生成一系列足部落点，使其能够在复杂环境中稳定行走。现有方法，如离散化A*，由于需要对连续空间进行离散化，导致计算量大，精度受限。而混合整数规划(MIP)虽然能处理连续约束，但计算复杂度高，难以满足实时性要求，尤其是在考虑旋转的情况下。

核心思路：CASSR的核心思想是在A*搜索框架内，使用连续的凸优化方法来表示和传播机器人的运动学约束。通过递归地更新和扩展可达区域，CASSR能够有效地探索搜索空间，找到最优的步态序列。关键在于避免了离散化，并利用凸优化的高效性。

技术框架：CASSR的整体框架包括以下几个主要阶段：1) 初始化：定义机器人的初始状态和目标状态。2) A搜索：使用A算法进行搜索，每个节点代表一个可能的足部落点。3) 可达性传播：对于每个节点，使用凸优化方法计算其可达区域，并将其传播到相邻节点。4) 启发式搜索：使用基于EPA算法的cost-to-go启发式函数来指导搜索方向。5) 路径生成：当找到目标节点时，回溯生成完整的步态序列。

关键创新：CASSR的关键创新在于将连续的凸优化方法与A搜索相结合，实现了高效的步态规划。与传统的离散化A相比，CASSR避免了离散化误差，提高了规划精度。与MIP相比，CASSR利用凸优化的高效性，显著降低了计算复杂度。此外，基于EPA算法的启发式函数能够更准确地估计剩余代价，加速搜索过程。

关键设计：CASSR的关键设计包括：1) 使用凸多面体来表示机器人的可达区域。2) 使用EPA算法来计算两个凸多面体之间的距离，作为启发式函数的依据。3) 递归地更新和扩展可达区域，以保证搜索的完整性。4) 优化目标通常包括步长、步高、稳定性裕度等因素，通过加权求和的方式进行优化。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，CASSR在双足运动任务上的性能显著优于传统的离散化A*方法，速度提升高达100倍。同时，CASSR也超过了商业MIP求解器，能够在125毫秒内规划多达30个步点的接触序列。这些结果验证了CASSR的有效性和实时性，使其成为双足机器人步态规划的理想选择。

🎯 应用场景

CASSR在双足机器人、人形机器人等领域具有广泛的应用前景。它可以用于实现机器人在复杂地形上的稳定行走、避障和导航。此外，CASSR还可以应用于虚拟现实、游戏等领域，为虚拟角色提供逼真的运动控制。该研究的突破将推动机器人技术的发展，使其能够更好地适应各种实际应用场景。

📄 摘要（原文）

Footstep planning involves a challenging combinatorial search. Traditional A approaches require discretising reachability constraints, while Mixed-Integer Programming (MIP) supports continuous formulations but quickly becomes intractable, especially when rotations are included. We present CASSR, a novel framework that recursively propagates convex, continuous formulations of a robot's kinematic constraints within an A search. Combined with a new cost-to-go heuristic based on the EPA algorithm, CASSR efficiently plans contact sequences of up to 30 footsteps in under 125 ms. Experiments on biped locomotion tasks demonstrate that CASSR outperforms traditional discretised A* by up to a factor of 100, while also surpassing a commercial MIP solver. These results show that CASSR enables fast, reliable, and real-time footstep planning for biped robots.