💻 computer science

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

本文提出了 CASSR 框架，通过递归传播凸连续运动学约束并结合基于 EPA 算法的启发式函数，在 A*搜索中实现了比传统离散化方法快 100 倍且优于商业 MIP 求解器的实时双足机器人步态规划。

原作者： Jiayi Wang, Steve Tonneau

发布于 2026-03-05

📖 1 分钟阅读☕ 轻松阅读

原作者： Jiayi Wang, Steve Tonneau

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一种名为 CASSR 的新算法，它的核心任务是帮助双足机器人（比如人形机器人）在复杂的环境中快速、实时地规划“走路”的步法。

为了让你更容易理解，我们可以把机器人走路想象成一个人在玩“跳房子”游戏，或者在布满石头的河面上过河。

1. 核心难题：过河太复杂了

想象一下，你面前有一条河，河里有无数块形状各异的石头。你的目标是走到对岸。

传统方法（离散化 A）：* 就像把河面画成了一张网格地图。你只能踩在网格的交叉点上。如果石头不在格子上，你就得强行把它“对齐”到最近的格子上。这会导致你要么踩空，要么走很多冤枉路，甚至根本找不到路。
另一种方法（MIP 求解器）： 就像请了一位超级严谨的数学家。他会计算每一块石头的每一个角度、每一个可能的落脚点，试图找到“绝对完美”的路线。但这太慢了！如果石头太多，这位数学家算到头发白也算不完，根本来不及让你过河。

2. CASSR 的绝招：把“格子”变成“连续的水域”

CASSR 的发明者（Jiayi Wang 和 Steve Tonneau）想出了一个聪明的办法：不再把落脚点限制在死板的格子上，而是把“能踩到的地方”看作一片连续的、凸起的“安全区域”。

连续的安全区（凸多面体）：
想象你站在当前这块石头上，你的脚能伸到的范围，不是几个离散的点，而是一个连续的、像果冻一样的透明区域。只要落在这个果冻区域内，都是安全的。
CASSR 就像是一个拥有透视眼的向导，它不关心具体的坐标点，而是直接在这个“果冻区域”里寻找下一块石头。
递归传播（像滚雪球）：
当你从第一块石头跳到第二块时，CASSR 不会重新计算，而是把第一块石头的“果冻区域”像滚雪球一样，顺着你的腿长“滚”到第二块石头上，形成一个新的、更大的“果冻区域”。这个过程一直重复，直到覆盖到对岸。

3. 两个阶段的“过河策略”

CASSR 把过河分成了两步走，就像先定大方向，再微调细节：

第一步：定路线（A 搜索）*
它先快速决定：“我们要踩哪几块石头？先踩左边那块，再踩中间那块……"
这里它用了一个很酷的**“橡皮筋”算法（EPA 算法）来估算距离。就像你手里有一根橡皮筋，一头连着现在的脚，一头连着对岸的目标。橡皮筋拉得越直，距离越近。这个算法能非常快地算出还需要跳几步，甚至能处理转身**这种复杂动作（就像你过河时可能需要侧身转个弯）。
第二步：定落点（QP 优化）
一旦确定了要踩哪几块石头，CASSR 就会解一个**“最小化问题”**。这就好比：既然已经决定踩这三块石头了，那具体踩在石头的哪个位置，能让步子迈得最舒服、最稳、离石头边缘最远？它会在刚才确定的“果冻区域”里，精确地算出最佳落脚点。

4. 为什么它这么牛？（实验结果）

论文通过实验对比了三种方法：

传统网格法（离散 A）：* 像走迷宫，容易卡死，或者为了对齐网格走很多弯路。
数学家法（MIP）： 算得太慢，等算出来，你可能已经掉河里了。
CASSR（新方法）：
- 速度快得惊人： 在复杂的“狭窄通道”或需要“转身”的场景中，它比传统方法快100 倍！能在125 毫秒内规划出 30 步的路线（相当于眨眼间就规划好了）。
- 更聪明： 它探索的“可能性”更少，但找到的路更优。因为它不需要在无数个网格点里瞎撞，而是直接在连续的“安全果冻”里找路。
- 实时性： 这意味着机器人可以在走路的同时，实时规划下一步，甚至应对突发情况。

总结

CASSR 就像给机器人装上了一双“直觉眼”和“灵活腿”。
它不再死板地数格子，也不再死磕复杂的数学公式，而是通过连续的区域想象和聪明的估算，让机器人能像人一样，在复杂的石头阵中快速、流畅地找到过河的最佳路线。这对于未来让人形机器人真正走进我们的家庭、工厂或灾难现场，具有非常重要的意义。

CASSR 论文技术总结

论文标题：CASSR: Continuous A-Star Search through Reachability for real time footstep planning (CASSR：基于可达性的连续 A搜索用于实时步态规划)
作者：Jiayi Wang, Steve Tonneau
核心领域：双足机器人步态规划、运动规划、A搜索、混合整数规划 (MIP)

1. 问题背景 (Problem)

双足机器人的步态规划（Footstep Planning）本质上是一个具有指数级复杂度的组合搜索问题，需要在满足几何约束（如碰撞避免、关节限制）和动力学约束（如接触力、可达性）的同时，规划出一系列接触序列。

传统 A 的局限性：传统的 A 方法通常需要对可达性约束进行离散化（Discretisation）。这种离散化虽然简化了搜索，但会减少可行解的数量，加剧组合爆炸问题，并可能因分辨率不足而丢失最优解或可行解。
MIP 方法的局限性：混合整数规划（MIP）支持连续形式的约束建模，理论上更精确，但随着步数增加和旋转自由度的引入，其计算复杂度迅速变得不可处理（Intractable），难以满足实时性要求。
核心挑战：如何在保持 A* 搜索的确定性、最优性和低复杂度的同时，引入连续的可达性约束表示，以避免离散化带来的精度损失和效率瓶颈。

2. 方法论 (Methodology)

作者提出了 CASSR (Continuous A-Star Search through Reachability)，一种将连续可达性约束递归传播到 A* 搜索框架中的新算法。该方法分为两个主要阶段：

A. 连续 A* 搜索 (阶段一：接触面序列规划)

搜索空间重构：不再将搜索节点定义为具体的接触位置（离散点），而是定义为接触表面（Contact Surfaces）。
递归可达性传播：
- 利用递归公式计算 $n$ 步可达集。
- 对于当前节点（代表一个凸接触面及其上的可达多面体），通过计算闵可夫斯基和 (Minkowski Sum) 与旋转矩阵，生成下一步的可达凸多面体（Polytope）。
- 将生成的可达多面体与环境中的凸接触表面进行求交。
- 每个非空的交集生成一个新的子节点（代表新的接触表面和可达区域）。
旋转处理：为了处理脚部偏航角（Yaw）的变化，将可能的旋转角度离散化（如 $10^\circ$ 增量），作为分支因子的一部分，但位置本身保持连续。
启发式函数 (Heuristic)：
- 提出了一种基于 EPA 算法 (Expanding Polytope Algorithm) 的新启发式函数。
- 用于计算当前节点的多面体与目标（点或多面体）之间的最小距离。
- 该启发式函数能更准确地估计旋转距离和步数下界，虽然为了效率牺牲了严格的可采纳性（Admissibility），使其成为加权 A*，但在实验中总能找到最优步数解。

B. 二次规划求解 (阶段二：接触位置优化)

一旦 A* 搜索确定了接触表面的序列和对应的旋转角度，问题转化为一个二次规划 (QP) 问题。
目标：在满足线性约束（前一步可达集与当前接触面的交集）的前提下，优化接触位置。
鲁棒性优化：引入松弛变量，最大化接触点与接触面边界的距离，防止脚部踏在边缘导致的不稳定。
可行性保证：由于 A* 阶段基于凸集传播，该 QP 问题被证明是始终可行的。

3. 主要贡献 (Key Contributions)

首个连续可达性表示的 A 求解器：实现了在长时域（Long-horizon）规划中，将连续可达性约束直接集成到 A 搜索中，无需预先离散化位置。
基于 EPA 算法的新型启发式函数：利用 EPA 算法高效计算多面体与目标之间的距离，有效近似旋转距离，提升了搜索效率。
鲁棒的安全代价函数：提出了一种最大化接触点与表面边界最小距离的代价函数，增强了步态规划的鲁棒性。
两阶段解耦架构：将“接触面序列选择”与“具体接触位置优化”解耦，既保证了搜索的完备性，又通过 QP 保证了最终轨迹的可行性。

4. 实验结果 (Results)

在 Talos 双足机器人的 6 种不同场景（包括楼梯、局部极小值、狭窄通道）中，CASSR 与离散化 A* 和 MIP 求解器进行了对比：

计算速度：
- CASSR 比传统离散化 A* 快 100 倍（在复杂场景如局部极小值中）。
- CASSR 比商业 MIP 求解器（Gurobi）快 6 到 20 倍（即使在 MIP 拥有已知最优步数先验的情况下）。
- 在包含旋转的复杂场景中，CASSR 能在 125ms 内规划出多达 30 步的接触序列，满足实时控制需求（1Hz）。
搜索效率：
- CASSR 探索的节点数量显著少于离散化 A*（在某些场景下减少 2000 倍），因为连续表示有效减少了组合爆炸。
- 在“楼梯”等简单场景中，CASSR 甚至无需分支即可直接找到路径。
最优性：
- 尽管启发式函数不是严格可采纳的，但在所有实验中，CASSR 找到的解在步数上均是最优的（与全局搜索基准一致）。
- 离散化 A* 在允许旋转时，由于离散化误差，往往无法找到可行解或需要更多步数。

5. 意义与影响 (Significance)

实时性突破：CASSR 证明了基于 A* 的框架结合连续可达性建模，能够解决传统上被认为计算量过大的长时域双足机器人步态规划问题，使其能够集成到实时控制回路中。
效率与精度的平衡：该方法成功克服了离散化带来的精度损失和 MIP 带来的计算瓶颈，提供了一种在复杂环境中快速、可靠且高效的规划方案。
未来方向：论文指出，该框架具有扩展性，未来可结合机器学习处理更复杂的非线性约束（如碰撞和动力学），并推广到非循环的 locomotion-manipulation（移动操作）任务中。

总结：CASSR 通过创新的连续可达性传播机制和高效的启发式搜索，显著提升了双足机器人步态规划的性能，为复杂环境下的实时机器人运动规划提供了强有力的解决方案。