SAMCON（基于采样的运动控制）
✅ 本章定位：理解 序列蒙特卡洛方法 在轨迹优化中的应用，掌握 SAMCON 的核心思想、算法流程以及与 CMA-ES 的对比。
一、从 CMA-ES 到 SAMCON
CMA-ES 的局限性
CMA-ES 是一种强大的无梯度优化方法，但在角色动画中存在以下问题：
| 问题 | 说明 | 影响 |
|---|---|---|
| 全轨迹仿真 | 每次采样需要从头到尾仿真整条轨迹 | 计算量大，效率低 |
| 长轨迹难收敛 | 轨迹越长，搜索空间越大 | 收敛速度慢，容易陷入局部最优 |
| 无法利用时序结构 | 将轨迹视为整体优化 | 忽略了运动的时序依赖性 |
直观理解：
CMA-ES: 采样整条轨迹 → 仿真 100 帧 → 评估
↓
计算成本：100 帧 × λ 个样本 = 100λ 次仿真步
SAMCON 的核心改进
SAMCON (SAmpling-based Motion CONtrol) [Liu et al. 2010, 2015] 针对 CMA-ES 的缺点进行了两项关键改进：
改进 1：分段优化
- 将轨迹分割成多个小段
- 每次只优化一小段，降低搜索空间维度
改进 2：序列蒙特卡洛
- 使用粒子滤波的思想
- 保留多个假设（粒子），避免局部最优
- 逐帧/逐段推进，利用时序结构
SAMCON: 分段采样 → 逐帧仿真 → 粒子滤波
↓
计算成本：每帧 λ 个样本，但收敛更快
二、SAMCON 算法框架
2.1 问题形式化
输入：
- 参考运动片段（Motion Clip）：\(M_{\text{ref}} = {m_1, m_2, \dots, m_T}\)
- 初始状态：\(x _0\)
- 物理仿真器
输出：
- 开环控制轨迹：\(u_{0:T}\)
- 物理可行的状态轨迹：\(x_{0:T}\)
目标： $$ \min {u{0:T}} \sum _{t=0}^{T} |x_t - x_t^{\text{ref}}|^2 + \lambda |u_t|^2 $$
s.t. 物理约束（动力学、接触、关节限制等）
2.2 算法流程
算法：SAMCON
输入：
- 参考运动 M_ref
- 初始状态 x_0
- 粒子数量 N
- 每段长度 L
输出：
- 控制轨迹 u_{0:T}
- 状态轨迹 x_{0:T}
1. 初始化粒子集合 P_0 = {x_0}
2. For t = 0 to T-1:
(a) 采样阶段
对每个粒子 x_t^(i) ∈ P_t:
采样偏移量 δ ~ N(0, Σ)
生成候选控制 u_t^(i) = u_ref(t) + δ
(b) 仿真阶段
对每个候选控制 u_t^(i):
用物理仿真器仿真一帧
得到新状态 x_{t+1}^(i)
(c) 评估阶段
计算每个新状态的得分：
score^(i) = -||x_{t+1}^(i) - x_{t+1}^ref||²
(d) 选择阶段
根据得分对粒子排序
保留前 N 个最优粒子
P_{t+1} = {top-N particles}
(e) 重采样（可选）
如果粒子多样性过低：
对优质粒子进行重采样
3. 从最终粒子集合中提取最优轨迹
2.3 可视化理解
时刻 t: 粒子集合 P_t
o o o o = 粒子（假设）
o o
o o
↓ 采样 + 仿真
时刻 t+1: 新粒子集合
o o o o = 优质粒子（保留）
o o× ×× × = 劣质粒子（淘汰）
o ×
↓ 选择
时刻 t+1: 筛选后
o o o 保留 N 个最优
o o
三、SAMCON 关键技术
3.1 偏移量采样
核心思想：在参考轨迹上添加随机偏移，跟踪偏移后的轨迹。
$$ u_t^{(i)} = u_{\text{ref}}(t) + \delta^{(i)}, \quad \delta^{(i)} \sim \mathcal{N}(0, \Sigma) $$
采样策略：
| 策略 | 说明 | 适用场景 |
|---|---|---|
| 高斯采样 | \(\delta \sim \mathcal{N}(0, \Sigma)\) | 一般情况 |
| 自适应方差 | 根据上一帧结果调整 \(\Sigma\) | 动态环境 |
| 重要性采样 | 偏向更有希望的区域 | 复杂约束 |
3.2 粒子选择
选择标准： $$ \text{score}^{(i)} = -|x_{t+1}^{(i)} - x_{t+1}^{\text{ref}}|^2 - \lambda |u_t^{(i)}|^2 $$
选择策略：
| 策略 | 说明 | 优点 | 缺点 |
|---|---|---|---|
| Top-N | 保留得分最高的 N 个 | 简单高效 | 可能丢失多样性 |
| 轮盘赌 | 按得分比例概率选择 | 保持多样性 | 收敛稍慢 |
| 精英保留 | 最优粒子直接晋级 + 随机选择 | 兼顾收敛与多样性 | 需要调参 |
3.3 重采样机制
问题：经过多轮选择后，粒子可能趋于一致（粒子退化）
解决：定期重采样，补充多样性
重采样条件：
- 粒子多样性低于阈值
- 连续 k 帧没有改进
- 检测到陷入局部最优
重采样方法：
1. 对优质粒子添加高斯噪声
2. 从历史优质粒子中随机复制
3. 完全重新采样（探索模式）
3.4 分段策略
分段方式：
| 方式 | 说明 | 适用场景 |
|---|---|---|
| 固定长度 | 每 L 帧一段 | 均匀运动 |
| 按关键帧 | 在接触事件处分段 | 步态、跳跃等 |
| 自适应 | 根据误差动态调整 | 复杂运动 |
段间衔接：
- 保证状态连续性（位置、速度）
- 使用重叠窗口平滑过渡
四、SAMCON 与相关方法对比
4.1 与 CMA-ES 对比
| 维度 | CMA-ES | SAMCON |
|---|---|---|
| 优化单位 | 整条轨迹 | 分段/逐帧 |
| 搜索空间 | 高维（T × 控制维度） | 低维（每段控制维度） |
| 仿真成本 | 全轨迹仿真 | 单帧/单段仿真 |
| 收敛速度 | 慢（尤其长轨迹） | 快（分段降低难度） |
| 抗局部最优 | 中（依赖协方差自适应） | 高（粒子多样性） |
| 内存需求 | 低 | 中（需存储粒子集合） |
| 并行性 | 好（样本独立） | 中（帧间依赖） |
4.2 与 MPC 对比
| 维度 | SAMCON | MPC |
|---|---|---|
| 优化方法 | 序列蒙特卡洛（采样） | 数值优化/解析 |
| 梯度需求 | 无需 | 通常需要 |
| 适用问题 | 不可微、接触频繁 | 平滑、可微 |
| 计算成本 | 中（大量仿真） | 高（求解优化问题） |
| 实时性 | 中（可增量计算） | 低（需要完整求解） |
| 鲁棒性 | 高（粒子多样性） | 中（依赖初始猜测） |
4.3 方法选择建议
更多方法对比请参见：方法对比与分类。
应用场景 → 推荐方法
─────────────────────────
离线轨迹优化，平滑问题 → iLQR/DDP
离线轨迹优化，接触频繁 → CMA-ES
在线实时控制，简单场景 → SAMCON
在线实时控制，复杂场景 → MPC
需要泛化能力 → DeepMimic/强化学习
五、SAMCON 的应用实例
5.1 运动跟踪 [Liu et al. 2010]
问题：
- 输入：动捕数据（Motion Capture）
- 目标：生成物理可行的跟踪轨迹
- 挑战：动捕数据可能不满足物理约束（穿地、失衡等）
方法：
- 用动捕数据作为参考轨迹 \(M_{\text{ref}}\)
- SAMCON 逐帧采样偏移量
- 物理仿真验证可行性
- 选择最接近参考的粒子
结果：
- 自动修正穿地问题
- 维持动态平衡
- 保持原始运动风格
5.2 地形自适应行走
问题：
- 在不平坦地形上行走
- 需要调整步态适应地形
SAMCON 方案：
每帧：
1. 采样多种落脚点
2. 仿真验证稳定性
3. 选择最优落脚点
4. 继续推进
优势：
- 无需预先规划接触序列
- 自动适应未知地形
- 实时响应扰动
5.3 跌倒恢复
问题：
- 角色受到外力推击
- 需要快速恢复平衡
SAMCON 方案：
- 增大采样方差（探索模式）
- 增加粒子数量
- 以稳定性为首要评分标准
结果：
- 自动跨步恢复平衡
- 必要时主动倒地
- 倒地后自主爬起
六、工程实践
6.1 参数设置
| 参数 | 推荐值 | 说明 |
|---|---|---|
| 粒子数量 N | 50-200 | 越多效果越好，但计算成本增加 |
| 采样方差 \(\Sigma\) | 根据任务调整 | 大→探索，小→开发 |
| 段长度 L | 5-20 帧 | 根据运动类型调整 |
| 精英比例 | 10-30% | 保留优质粒子 |
6.2 实用技巧
1. 自适应方差
if diversity < threshold:
Σ *= 1.5 # 增加探索
elif convergence_speed > target:
Σ *= 0.8 # 加快收敛
2. 粒子多样性度量 $$ \text{diversity} = \frac{1}{N^2} \sum_{i,j} |x^{(i)} - x^{(j)}| $$
3. 渐进式优化
- 先用少量粒子快速得到可行解
- 再用更多粒子精细化
4. 缓存与重用
- 缓存仿真结果
- 重用历史优质粒子
6.3 性能优化
并行化：
# 粒子仿真可并行
from joblib import Parallel, delayed
def simulate_particle(particle):
# 仿真一帧
return new_state
new_states = Parallel(n_jobs=-1)(
delayed(simulate_particle)(p) for p in particles
)
向量化：
- 将粒子状态组织成数组
- 使用 SIMD/GPU 加速仿真
七、关键要点总结
核心思想
- 分段优化：将长轨迹分割为小段，降低搜索空间维度
- 序列蒙特卡洛：使用粒子滤波思想，保留多个假设
- 逐帧推进：利用时序结构， incremental 构建完整轨迹
算法流程
初始化 → 采样偏移 → 物理仿真 → 评估选择 → 重采样 → 推进到下一帧
优缺点
| 优点 | 缺点 |
|---|---|
| 无需梯度，适用于黑盒问题 | 需要大量仿真 |
| 分段优化，收敛快 | 粒子退化问题 |
| 粒子多样性，抗局部最优 | 需要调参 |
| 可实时应用 | 高维问题效果差 |
适用场景
- ✅ 运动跟踪（动捕数据物理化）
- ✅ 地形自适应行走
- ✅ 跌倒恢复与平衡控制
- ✅ 在线实时控制
- ❌ 离线全局优化（用 CMA-ES 更合适）
- ❌ 高维精细优化（用 iLQR 更合适）
八、深入学习
前置知识
相关方法
参考资料
- Liu et al. 2010 - Sampling-based Motion Control
- Liu et al. 2015 - Terrain Runner
- Al Borno et al. 2013 - Trajectory Optimization for Full-Body Movements
代码资源
- MOCCA - Motion Control and Optimization - UBC 的运动控制库
本文出自 CaterpillarStudyGroup，转载请注明出处。 https://caterpillarstudygroup.github.io/GAMES105_mdbook/