本章目录

约束求解器与时间积分

前面的章节已经把接触转换成凸优化问题。求解器在当前状态下计算接触力与加速度;积分器利用这些结果推进位置和速度。一个完整仿真步由这两部分接续完成。

本章从两个叠放方块的受力出发,逐步计算接触力与加速度,再通过弹簧振子比较时间离散方法。最后将碰撞距离、软接触参数、摩擦锥和积分器接成一个可以运行的球面接触模型。

数学约定

当前配置与速度记作 q,v,加速度记作 a,步长为 h。约束力记作 f。优化部分在一次求解中固定 M,J,R;振子采用质量为 1\,\mathrm{kg} 的普通标量坐标。矩阵 H 表示当前二次目标的 Hessian。

01

叠放方块的接触方程

两个方块上下叠放在水平地面上。地面要托住两个方块的总重量,两方块之间的接触只需托住上方块。静止时,这两股支撑力很容易由受力平衡求出;将它们作为已知的检验结果,便能逐步观察求解器怎样从零力走到正确的接触力。

设下方块为物体 1,上方块为物体 2。两者质量都是 1\,\mathrm{kg}、高度都是 1\,\mathrm m,只允许竖直平移。竖直向上为正,重力加速度大小取 10\,\mathrm{m/s^2}。当前两个接触都刚好闭合,速度为零。用 f_1 表示地面对下方块的向上支撑力,用 f_2 表示下方块对上方块的向上支撑力。由作用与反作用,下方块还受到大小为 f_2 的向下作用力。

思考两块物体各重十牛顿,静止时地面要承受多少支撑力?

先看上方块:平衡要求 f_2=10\,\mathrm N。下方块同时承受自身重力和上方块的反作用力,因此 f_1=10\,\mathrm N+f_2=20\,\mathrm N。地面支撑整组物体的重量。下图选取静止支撑状态,可核对两处接触力。

实验 01叠放方块的接触力与加速度

分别改变两处接触力,观察每个方块的合力与加速度。选取静止支撑预设时,两物体的合力都为零。拖动图形可旋转视角。

对每个物体单独列牛顿第二定律,得到下面两行。质量都是一千克,数值上合力与加速度相等,但两者的单位仍分别为牛顿和米每二次方秒。

\begin{aligned}a_1&=-10+f_1-f_2,\\a_2&=-10+f_2.\end{aligned}
(15.1)

先看静止支撑:上方块的 a_2=0 要求 f_2=10\,\mathrm N;代入下方块的 a_1=0,便得 f_1=20\,\mathrm N。地面的反力比层间反力大,是因为它还承担了下方块自身的重量。下面所有迭代都应趋近这组结果。

从物体加速度到接触加速度

求解器处理的是接触处能否分离或继续挤入。记两物体的质心高度为 z_1,z_2。地面间隙为 e_1=z_1-1/2,层间间隙为 e_2=z_2-z_1-1。它们在当前时刻都为零。对时间求两次导数,接触处的相对加速度便是

\ddot e_1=a_1,\qquad \ddot e_2=a_2-a_1,\qquad J=\begin{bmatrix}1&0\\-1&1\end{bmatrix},\qquad \ddot e=Ja.
(15.2)

第一行只看下方块相对地面的运动;第二行比较上、下两物体的运动。若二者一起自由下落,a_1=a_2=-10,层间间隙的二阶导数仍为零,地面间隙却有继续减小的趋势。因此,两行的物理意义各不相同。

把式(15.1)代入式(15.2),接触加速度成为接触力的线性函数:

Ja=Af+b,\qquad A=\begin{bmatrix}1&-1\\-1&2\end{bmatrix},\qquad b=\begin{bmatrix}-10\\0\end{bmatrix}.
(15.3)
推导两行接触响应的来源式(15.3)

逐行代入两物体的加速度:

\begin{aligned}\ddot e_1&=-10+f_1-f_2,\\\ddot e_2&=(-10+f_2)-(-10+f_1-f_2)=-f_1+2f_2.\end{aligned}

层间力 f_2 向上推上方块、向下推下方块,两边都增加分离加速度,所以它在第二行的系数为 2。地面力 f_1 向上推下方块,使层间间隙趋于减小,所以两个交叉系数都是 -1。

用式(11.6)的质量加权接触响应核对同一结果。这里 M=I,故

A=JM^{-1}J^{\mathsf T}=\begin{bmatrix}1&0\\-1&1\end{bmatrix}\begin{bmatrix}1&-1\\0&1\end{bmatrix}=\begin{bmatrix}1&-1\\-1&2\end{bmatrix}.

允许的接触状态与优化目标

对于当前闭合、零相对速度的硬接触,支撑力只能推开物体,因此 f_i\geq0;间隙加速度应满足 \ddot e_i\geq0。若接触开始分离,支撑力应为零;若支撑力为正,接触保持闭合。把这两种情况写在一起,得到第十三章互补条件在本例中的形式:

f\geq0,\qquad w=Af+b\geq0,\qquad f_iw_i=0.
(15.4)

这里用 w 简记两行接触残差。硬接触且参考加速度为零时,它正好等于 \ddot e。式(13.3)的最优性条件与式(13.6)的接触二次目标给出同一关系。本例具体为

\min_{f_1,f_2\geq0}\phi(f),\qquad \phi(f)=\frac12 f_1^2-f_1f_2+f_2^2-10f_1,\qquad \nabla\phi=Af+b.
(15.5)
推导二次目标与互补条件式(15.4)与式(15.5)的对应

展开 \tfrac12 f^{\mathsf T}Af+b^{\mathsf T}f:交叉项由对称位置各贡献一半,合成 -f_1f_2。对两个变量分别求导,得到

\frac{\partial\phi}{\partial f_1}=f_1-f_2-10=w_1,\qquad \frac{\partial\phi}{\partial f_2}=-f_1+2f_2=w_2.

若 f_i>0,允许向正、负两个方向作小变化,最小值要求 w_i=0;若 f_i=0,只能向正方向变化,最小值要求 w_i\geq0。这恰好给出互补条件。任意非零增量 u 满足

u^{\mathsf T}Au=(u_1-u_2)^2+u_2^2>0,

所以目标严格凸,满足上述条件的力就是唯一极小点。

软接触与时间推进

加入第十二章的软约束时,以 a_{\rm ref} 表示接触参考加速度,以正对角矩阵 R 表示柔顺程度。式(13.6)的对偶目标仍是二次式,只需把矩阵和一次项改成

H=JM^{-1}J^{\mathsf T}+R,\qquad b=Ja_u-a_{\rm ref},\qquad \phi(f)=\frac12f^{\mathsf T}Hf+b^{\mathsf T}f.
(15.6)

a_u 是尚未施加约束力时的物体加速度;本例为 (-10,-10)^{\mathsf T}。软模型的残差变为 w=Ja-a_{\rm ref}+Rf。正力行要求这一残差为零,因而允许实际接触加速度偏离参考值。下一节先计算 R=0 的静止支撑,再计算 R=0.1I 的软响应,区分模型差异与迭代误差。

求解期间固定当前位置和速度,反复修改候选力,直到满足最优条件。此后才用 a=a_u+M^{-1}J^{\mathsf T}f 得到加速度并积分。迭代轮数控制当前受力问题的求解精度,时间步长控制状态推进的离散误差。

(q_k,v_k)\longrightarrow(M,J,a_u,a_{\rm ref},R)\longrightarrow(f_k,a_k)\longrightarrow(q_{k+1},v_{k+1}).

例如固定同一个步起点,求解器迭代不足会留下非零的接触最优性残差;把力求得更精确可以减小这类误差。即使本步的力已精确,仍需要用有限步长近似随后一段连续运动。下面先保持步起点不变研究求解,再推进时间研究积分。

02

PGS 的逐行接触求解

投影 Gauss–Seidel 方法(Projected Gauss–Seidel,PGS)每次只改变一个接触力,暂时固定其余力。对叠放方块来说,第一行调整地面支撑力,第二行调整层间支撑力;后一行立即使用前一行刚算出的结果。

第一轮:两处接触的相互影响

从 f=(0,0)^{\mathsf T} 开始。两个物体都自由下落。先固定 f_2=0,调整地面反力,使下方块的 a_1=-10+f_1 为零,得到 f_1=10\,\mathrm N。此时下方块停止加速下落,上方块仍以 -10\,\mathrm{m/s^2} 加速,层间接触便出现挤入趋势。

接着固定新的 f_1=10\,\mathrm N,调整层间力。由式(15.3),层间加速度为 -10+2f_2,令它为零得到 f_2=5\,\mathrm N。这股力向上推上方块,同时向下推下方块,因此两物体的加速度都变成 -5\,\mathrm{m/s^2}。层间条件暂时满足,地面条件又出现了误差。

\begin{array}{c|c|c|c}\text{当前步骤}&(f_1,f_2)\;[\mathrm N]&(a_1,a_2)\;[\mathrm{m/s^2}]&(w_1,w_2)\;[\mathrm{m/s^2}]\\\hline\text{初值}&(0,0)&(-10,-10)&(-10,0)\\\text{更新地面力}&(10,0)&(0,-10)&(0,-10)\\\text{更新层间力}&(10,5)&(-5,-5)&(-5,0)\\\text{再次更新地面力}&(15,5)&(0,-5)&(0,-5)\\\text{再次更新层间力}&(15,7.5)&(-2.5,-2.5)&(-2.5,0)\end{array}

第二轮地面反力补到 15\,\mathrm N,层间反力随后补到 7.5\,\mathrm N。两物体向下的加速度减半。接触之间的耦合使一次逐行扫描只能消除一部分误差,后续扫描继续传递其余影响。表内各行都属于同一时刻的候选解,物体尚未推进到下一帧。

力平面、坐标更新与一维截面

把地面力作为横坐标、层间力作为纵坐标,每一组候选力就在力平面上对应一个点。两种接触都只能推开物体,因此允许区域是包含坐标轴的第一象限。默认模型的目标由式(15.5)展开为

\phi(f_1,f_2)=\frac12f_1^2-f_1f_2+f_2^2-10f_1.

它的等值线是一组以 (20,10) 为中心的椭圆。固定层间力时,候选点只能水平移动;固定地面力时,只能竖直移动。把同一个目标沿这条水平线或竖直线截开,就得到当前行的一元二次函数。

第一步固定 f_2=0,截面为 s^2/2-10s,极小点在 s=10。第二步固定新值 f_1=10,去掉与本行变量无关的常数后,截面为 s^2-10s,极小点在 s=5。于是前两段路径依次水平到达 (10,0)、竖直到达 (10,5)。

实验 02PGS 的等值线、逐行路径与非负投影

默认显示力平面的等值线、非负可行域和已完成的更新路径,下方同步显示当前行的抛物线。初值处预示下一次试算;点击下一步后加入实际路径。上拉 15 牛顿的预设展示负值试算投影到零,其他视图可查看同一步的受力与残差。

在默认参数下,第二次行更新沿竖直方向到达 (10,5)。这一点已使竖直截面达到极小值,仍未到达完整二维目标的中心。下一次水平更新继续降低目标,于是路径逐段接近 (20,10)。切换到受力图,同一步对应两物体均向下的 5\,\mathrm{m/s^2} 加速度,恰好与前表一致。

一般更新式与非负投影

上述两次计算来自同一条规则。把当前要更新的第 i 个分量暂记为 s,其余分量视为已知,目标函数就只剩一个一元二次式。先求其极小点,再把负的试算力截到零:

\widehat f_i=-\frac{b_i+\sum_{j\ne i}H_{ij}f_j}{H_{ii}},\qquad f_i\leftarrow\max(0,\widehat f_i).
(15.7)
推导一行更新的代数推导式(15.7)

目标的对角项贡献 H_{ii}s^2/2,两组对称交叉项合成 s\sum_{j\ne i}H_{ij}f_j,一次项贡献 b_i s。于是

\begin{aligned}\phi_i(s)&=\tfrac12H_{ii}s^2+\left(b_i+\sum_{j\ne i}H_{ij}f_j\right)s+C,\\\phi_i^{\prime}(s)&=H_{ii}s+b_i+\sum_{j\ne i}H_{ij}f_j.\end{aligned}

C 收集与 s 无关的项。由 H_{ii}>0,抛物线开口向上;令导数为零得到 \widehat f_i。若 \widehat f_i<0,允许区间 s\geq0 的最小点为端点零。

用当前残差 w_i=(Hf+b)_i 改写同一试算值:

f_i-\frac{w_i}{H_{ii}}=f_i-\frac{H_{ii}f_i+b_i+\sum_{j\ne i}H_{ij}f_j}{H_{ii}}=-\frac{b_i+\sum_{j\ne i}H_{ij}f_j}{H_{ii}}.

每次更新都精确极小化当前一维子问题,因此整个目标值不会上升。

代入本例的 H=A 和 b,更新式成为 f_1\leftarrow10+f_2、f_2\leftarrow f_1/2。从零开始,两式的试算结果一直非负,所以暂时看不到截断的作用。完成第 k 轮后,结果可以写成

f_1^{(k)}=20(1-2^{-k}),\qquad f_2^{(k)}=10(1-2^{-k}),\qquad a_1^{(k)}=a_2^{(k)}=-10\,2^{-k}.
(15.8)
推导每轮误差减半式(15.8)

第二行使用本轮的新地面力,故

f_2^{(k)}=\frac{10+f_2^{(k-1)}}2=5+\frac12f_2^{(k-1)}.

从两侧减去极限值 10,得到 f_2^{(k)}-10=\tfrac12(f_2^{(k-1)}-10)。初值为零,反复代入便得 f_2^{(k)}-10=-10\,2^{-k}。再将它前一轮的值代入第一行:

f_1^{(k)}=10+10(1-2^{-(k-1)})=20(1-2^{-k}).

最后代回式(15.1),两物体加速度都等于 -10\,2^{-k}。

分离接触与软约束

现在给上方块施加向上的外力 P。它的自由加速度变为 -10+P,所以 b=(-10,P)^{\mathsf T}。取 P=15\,\mathrm N,第一行仍算出 f_1=10\,\mathrm N;第二行的试算值变成

\widehat f_2=\frac{f_1-P}{2}=\frac{10-15}{2}=-2.5\,\mathrm N,\qquad f_2=0.

负试算值要求两物体互相吸引。普通接触只能推,投影便把层间力置零。此时下方块保持 a_1=0,上方块有 a_2=5\,\mathrm{m/s^2},层间开始分离。残差为 w=(0,5)^{\mathsf T},仍完全满足式(15.4);用“所有残差分量都必须为零”作为停止条件会误判这一正确解。

再回到 P=0,取软正则化 R=0.1I\,\mathrm{kg^{-1}}、参考加速度为零。此时 H_{11}=1.1、H_{22}=2.1,两股正力满足 Hf+b=0。解得

f=\begin{bmatrix}2100/131\\1000/131\end{bmatrix}\!\mathrm N\approx\begin{bmatrix}16.031\\7.634\end{bmatrix}\!\mathrm N,\qquad a=\begin{bmatrix}-210/131\\-310/131\end{bmatrix}\!\mathrm{m/s^2}.
(15.9)
计算软模型的力与加速度式(15.9)
\begin{aligned}1.1f_1-f_2&=10,\\-f_1+2.1f_2&=0.\end{aligned}

由第二行 f_1=2.1f_2,代入第一行得到 1.31f_2=10。因此 f_2=1000/131、f_1=2100/131。再代入式(15.1):

a_1=-10+\frac{1100}{131}=-\frac{210}{131},\qquad a_2=-10+\frac{1000}{131}=-\frac{310}{131}.

接触加速度为 Ja=(-210/131,-100/131)^{\mathsf T},正则化项为 Rf=(210/131,100/131)^{\mathsf T},二者相加为零。

软解中的向下加速度来自所选参考值与正则化。继续增加迭代轮数,只会更准确地趋近这组软解。要描述软接触的静止支撑,还需像第十二章那样由位置误差产生非零恢复参考值;静止时应满足 a_{\rm ref}=Rf。

停止量、初值与其他约束行

检查一行是否还需要修正,可以用同一条 PGS 更新式计算“当前值减去重新更新后的值”。将各行绝对值取最大,得到具有力单位的停止量:

\delta_i=f_i-\max\!\left(0,f_i-\frac{w_i}{H_{ii}}\right),\qquad E=\max_i|\delta_i|.
(15.10)
推导零停止量与互补条件式(15.10)

对于非负候选力,分两种情况。若 f_i>0 且 \delta_i=0,投影结果必须等于这个正值,因此截断未发生,w_i/H_{ii}=0。若 f_i=0 且 \delta_i=0,则 -w_i/H_{ii}\leq0,故 w_i\geq0。反过来,将这两类互补状态代入更新式,都保持原力。

H_{ii} 的单位是每千克,w_i 是加速度,所以 w_i/H_{ii} 是力。选取例如 E<10^{-4}\,\mathrm N 的容许误差便有明确尺度。

热启动使用前一时间步的信息构造本步初值。图中可以把初值改成接近支撑解的 (18,9)^{\mathsf T}\,\mathrm N,对比达到同一误差所需的行更新次数。接触状态突变时,旧近似也可能离当前解较远,仍须按本步的约束重新检查。MuJoCo 如何从保存的加速度建立初值,将在源码一节具体对应。

式(15.7)的截断范围由约束类型决定。等式约束的力可取任意实数,直接接受试算值;有限干摩擦损失使用给定上下限;无摩擦法向接触使用 [0,\infty)。椭圆摩擦锥把同一接触的多个分量联系起来,需要作为一个块处理。

记当前接触块的变量为 u,对应主对角块为 H_{BB};其他块的固定值并入一次项系数 c_B。无约束块解为 u_*=-H_{BB}^{-1}c_B。配方后,允许锥内的最优点就是离 u_* 最近的点,距离由 H_{BB} 加权。这个式子给出理想的精确块更新目标。

推导接触块的矩阵度量\min_{u\in\mathcal K}\tfrac12\|u-u_*\|_{H_{BB}}^2

将待更新的块记为 u,收集其他块的已知贡献为 c。该块目标可配方为

\frac12u^{\mathsf T}H_{BB}u+c^{\mathsf T}u=\frac12(u-u_*)^{\mathsf T}H_{BB}(u-u_*)+\text{常数},\quad u_*=-H_{BB}^{-1}c.

在允许的摩擦锥内精确极小化右侧,就得到理想的精确块更新。只有当 H_{BB} 为单位阵的正倍数时,它才等于普通欧氏距离投影。

本地 MuJoCo 的椭圆锥 PGS 先沿当前射线调整,再固定法向处理切向二次约束子问题。上面的矩阵度量说明完整局部问题的目标,具体实现的两个子步骤在第十四章已有展开。

可运行的逐行计算

下面的教学实现与受力图采用同一模型。输入是向上外力、正则化和迭代轮数,输出保留每次行更新后的力、加速度及停止量。P=0,R=0 时趋向静止支撑;P=15,R=0 时得到层间分离。

from stack_contact import pgs_stack

for row in pgs_stack(pull=0, regularization=0, sweeps=2):
    print(row["row"], row["force"], row["acceleration"], row["error"])

# 第二次完整扫描:力为 (15, 7.5),加速度为 (-2.5, -2.5)
separating = list(pgs_stack(pull=15, sweeps=1))[-1]
assert separating["force"] == (10, 0)
assert separating["acceleration"] == (0, 5)

在 examples 目录运行;完整代码逐行保留了试算值和非负投影。

03

梯度方向与共轭方向

逐变量更新一次只处理一个坐标方向。另一种选择是同时改变全部变量:先用梯度找到当前下降方向,再利用二次曲面的形状避免反复修正已经处理过的方向。下面从一条搜索直线上的精确最小值建立这两种方法。

式(13.2)给出了二次目标的梯度与曲率。PGS 沿坐标方向逐项极小化,本节从一般搜索方向出发,计算沿一条直线应该前进多远。

仍取叠放方块的硬接触模型,从 f=0 出发。其内部极小点恰好满足非负性,可以先沿整个力平面研究搜索方向。下面用 x 代表一般优化变量;在这组具体计算中,x=f。到 Newton 一节,变量将改成物体加速度,受力结果仍与前面的软模型核对。

以下优化运算采用物理量在国际单位制下的数值坐标,求得的力按牛顿解释。梯度决定数值坐标中的搜索方向,步长决定沿该方向的更新幅度。

本例梯度为 g=Af+b。起点的负梯度方向是 (10,0)^{\mathsf T},先增加地面力;到达 (10,0)^{\mathsf T} 后,下一共轭方向为 (10,10)^{\mathsf T},把两股力同时增加到静止支撑解。

先考虑没有不等式边界的固定二次目标。梯度为 g=Hx+b,沿方向 p 前进时,可以精确计算使目标最小的步长:

\alpha=-\frac{g^{\mathsf T}p}{p^{\mathsf T}Hp},\qquad x^{\rm new}=x+\alpha p.
(15.12)
推导一维搜索的展开\alpha=-g^{\mathsf T}p/(p^{\mathsf T}Hp)
\begin{aligned}\phi(x+\alpha p)&=\phi(x)+\alpha g^{\mathsf T}p+\frac12\alpha^2p^{\mathsf T}Hp,\\\frac{\mathrm d\phi}{\mathrm d\alpha}&=g^{\mathsf T}p+\alpha p^{\mathsf T}Hp.\end{aligned}

令导数为零即可求出步长。更新后的梯度满足 g_{\rm new}^{\mathsf T}p=0,即本轮方向上的一阶变化已经消除。

最速下降每次使用 p=-g。狭长椭圆的两侧梯度方向变化较大,连续步长往往形成折返路径。共轭梯度法(Conjugate Gradient,CG)用 Hessian 定义方向间的正交性,让新的搜索保留已有方向上的极小化结果。

p_i^{\mathsf T}Hp_j=0\quad(i\ne j),\qquad p_{k+1}=-g_{k+1}+\beta_kp_k.

对于固定正定 Hessian 和精确线搜索,方向系数可取 \beta_k=\|g_{k+1}\|^2/\|g_k\|^2。它使新方向与已有方向关于 H 共轭,从而保留此前完成的极小化。

推导从共轭条件求方向系数\beta_k=\|g_{k+1}\|^2/\|g_k\|^2

要求下一方向与当前方向共轭,代入两项的线性组合:

0=(-g_{k+1}+\beta_kp_k)^{\mathsf T}Hp_k\quad\Longrightarrow\quad\beta_k=\frac{g_{k+1}^{\mathsf T}Hp_k}{p_k^{\mathsf T}Hp_k}.

固定 Hessian 给出 g_{k+1}-g_k=\alpha_kHp_k。精确线搜索和已经建立的共轭关系使新梯度与此前梯度正交;这一关系可逐轮归纳:新梯度对本轮方向正交,对旧方向的内积保持为零,而旧梯度是旧方向的线性组合。于是

\begin{aligned}g_{k+1}^{\mathsf T}Hp_k&=\frac{g_{k+1}^{\mathsf T}(g_{k+1}-g_k)}{\alpha_k}=\frac{\|g_{k+1}\|^2}{\alpha_k},\\\alpha_kp_k^{\mathsf T}Hp_k&=-g_k^{\mathsf T}p_k=\|g_k\|^2,\\\beta_k&=\frac{\|g_{k+1}\|^2}{\|g_k\|^2}.\end{aligned}

还需核对新方向与更早方向的共轭性。对 j<k,用梯度更新式和已经得到的梯度正交关系,逐项计算:

\begin{aligned}g_{k+1}^{\mathsf T}Hp_j&=\frac{g_{k+1}^{\mathsf T}(g_{j+1}-g_j)}{\alpha_j}=0,\\p_{k+1}^{\mathsf T}Hp_j&=-g_{k+1}^{\mathsf T}Hp_j+\beta_kp_k^{\mathsf T}Hp_j=0.\end{aligned}

与当前方向的共轭条件由 \beta_k 保证,与更早方向的共轭条件由上式保留,从而完成归纳。

正定性保证非零共轭方向线性无关。在精确算术中,至多经过变量维数那么多个方向,就能表示完整误差并到达极小点。浮点误差和变化的活动集合会改变这个有限步结论的适用条件。

计算叠放方块的两次 CG 更新f_0=(0,0)^{\mathsf T}\ \longrightarrow\ f_2=(20,10)^{\mathsf T}

初值 g_0=(-10,0)^{\mathsf T},方向 p_0=-g_0=(10,0)^{\mathsf T}。按式(15.12)的精确线搜索公式,

\alpha_0=\frac{100}{(10,0)A(10,0)^{\mathsf T}}=1,\qquad f^{(1)}=(10,0)^{\mathsf T},\qquad g_1=(0,-10)^{\mathsf T}.

新旧梯度平方长度相等,所以 \beta_0=1,下一方向为

p_1=-g_1+p_0=(10,10)^{\mathsf T},\qquad Ap_1=(0,10)^{\mathsf T}.

于是 p_0^{\mathsf T}Ap_1=0,两个方向关于 A 共轭。第二次步长为

\alpha_1=-\frac{(0,-10)(10,10)^{\mathsf T}}{(10,10)(0,10)^{\mathsf T}}=1,\qquad f^{(2)}=(20,10)^{\mathsf T}.

代入式(15.1),两物体加速度均为零。若施加 15\,\mathrm N 的上拉力,无约束极小点会变成 (5,-5)^{\mathsf T},需要接触可行域处理。因此,下文固定二次 CG 的有限步性质适用于这里选定的内部解;MuJoCo 用加速度原始目标处理完整的接触分段。

再用二维对角例核对两个方向。取 H=\operatorname{diag}(1,4)、b=0、x_0=(2,1)^{\mathsf T},第一步的精确线搜索后,梯度转为与旧梯度正交。第二个共轭方向再消除剩余误差,恰好在两步到达原点。

计算二维共轭梯度的两步计算x_2=(0,0)^{\mathsf T}

初始梯度与方向为 g_0=(2,4)^{\mathsf T}、p_0=(-2,-4)^{\mathsf T}。第一步:

\alpha_0=\frac{2^2+4^2}{(-2)^2+4(-4)^2}=\frac5{17},\qquad x_1=\begin{bmatrix}24/17\\-3/17\end{bmatrix},\qquad g_1=\begin{bmatrix}24/17\\-12/17\end{bmatrix}.

有 g_0^{\mathsf T}g_1=48/17-48/17=0。由梯度长度比得到

\beta_0=\frac{(24/17)^2+(-12/17)^2}{20}=\frac{36}{289},\qquad p_1=-g_1+\beta_0p_0=\frac1{289}\begin{bmatrix}-480\\60\end{bmatrix}.

共轭关系可直接算成 p_1^{\mathsf T}Hp_0=(960-960)/289=0。第二次线搜索给出 \alpha_1=17/20,代回 x_2=x_1+\alpha_1p_1,两个分量都为零。

对同一个固定二次目标,可以直接比较不同搜索方向的作用。图中最速下降沿当前梯度法线,共轭梯度保留此前已消除的方向误差,Newton 则利用完整曲率求解;增大条件数会拉长等值椭圆。

实验 03梯度、共轭梯度与 Newton 路径

改变椭圆的条件数,比较三种方法的更新路径。动画同时显示各自已完成的迭代;到达极小点的方法保持在终点。

图的初始条件数为 8,初值为 (1,1)^{\mathsf T}。最速下降与 CG 的第一方向同为 (-1,-8)^{\mathsf T},精确步长为 65/513,所以两条路径的第一个点重合在 (448/513,-7/513)^{\mathsf T}。下一步 CG 改用共轭方向,最速下降继续取新的负梯度,两条路径由此分开。Newton 则解 Hp=-g,在这个固定二次例中一步到达原点。

路径差异来自方向选择与曲率处理。图中的固定二次模型使这些关系清楚可见;实际接触改变活动集合时,目标的局部曲率也随之变化,方向与步长需要重新计算。

图中的条件数等于最大曲率与最小曲率之比。某一方向的曲率远大于另一方向时,同一个长度单位会让梯度在各轴上尺度失衡。预条件通过一组较便宜的线性求解重新缩放变量,使后续方向在更均衡的坐标中形成。

预条件用一个容易求解的正定矩阵 P 改善方向尺度。首先解 Pz_k=g_k,得到预条件梯度 z_k;初始方向取 p_0=-z_0。每一轮先沿当前方向做线搜索,再更新位置与梯度:

\begin{aligned}\alpha_k&=-\frac{g_k^{\mathsf T}p_k}{p_k^{\mathsf T}Hp_k},\\x_{k+1}&=x_k+\alpha_kp_k,\\g_{k+1}&=Hx_{k+1}+b.\end{aligned}

随后再次求解预条件方程,比较新、旧梯度在这一尺度下的长度,并组合下一方向:

\begin{aligned}Pz_{k+1}&=g_{k+1},\\\beta_k&=\frac{g_{k+1}^{\mathsf T}z_{k+1}}{g_k^{\mathsf T}z_k},\\p_{k+1}&=-z_{k+1}+\beta_kp_k.\end{aligned}

位置更新负责降低当前目标;预条件求解负责调整尺度;方向组合负责保留共轭关系。这些公式采用固定的正定 H,P 与精确线搜索。梯度已经为零时即可终止。

推导预条件与变量变换-\widetilde g\ \mapsto\ -P^{-1}g

将 P 分解成 CC^{\mathsf T},用 x=C^{-\mathsf T}y 表示原变量。变换后的二次项和梯度为

\widetilde H=C^{-1}HC^{-\mathsf T},\qquad\widetilde g=C^{-1}g.

在新坐标中采用负梯度方向,映回原坐标得到 -C^{-\mathsf T}C^{-1}g=-P^{-1}g。内积 \widetilde g^{\mathsf T}\widetilde g=g^{\mathsf T}P^{-1}g,因此普通共轭梯度的方向系数恰好变成上式。

接触边界使目标分段后,固定二次曲面的线搜索公式需要重新评价。加速度形式把动力学平衡写入梯度,并在每个分段内提供 Hessian;Newton 法便用这份局部曲率决定方向,再通过新点的目标值决定实际步长。

04

原始目标与阻尼 Newton 法

PGS 直接修改接触力。原始方法则先提出一组候选物体加速度,由软接触规律计算对应的力,再检查这组力能否产生所提出的加速度。两种变量组织方式在最优点满足同一条动力学关系。继续采用式(15.9)的模型:两物体质量为一千克,R=0.1I\,\mathrm{kg^{-1}},自由加速度为 (-10,-10)^{\mathsf T},参考加速度为零。

式(13.7)给出了独立法向接触的加速度目标及其与力空间问题的对应。这里把它逐项代入方块模型,再对同一目标求导、解方向和选步长。

地面行的接触加速度是 a_1,层间行是 a_2-a_1。各行若低于参考值,按软关系产生正力;高于参考值时,接触力为零:

f_1=\max(0,-10a_1),\qquad f_2=\max(0,-10(a_2-a_1)).

第十三章的原始目标在这个模型中完整展开为

F(a)=\frac12\big[(a_1+10)^2+(a_2+10)^2\big]+5\min(0,a_1)^2+5\min(0,a_2-a_1)^2.
(15.11)

前两项衡量物体加速度离自由下落有多远;后两项分别衡量地面和层间的压入趋势。图中两条分界线因此为 a_1=0 与 a_2=a_1。在每个分区中,参与求导的接触项固定,目标就是一个普通二次函数。

在加速度变量中,独立法向软约束对应分段二次目标。记 z_i=J_i a-a_{{\rm ref},i},并用 R_i>0 表示各行正则化:

F(a)=\frac12(a-a_u)^{\mathsf T}M(a-a_u)+\sum_i\frac{\min(0,z_i)^2}{2R_i}.

第一项衡量加速度偏离自由值的惯性代价;每个接触项只在伪加速度低于参考值时产生代价。一次求解中 M,J,R 都固定,改变候选加速度只会改变各行的残差 z_i 及其所在分段。

每一行在 z_i<0 时产生力 f_i=-z_i/R_i,在 z_i\geq0 时力为零。在活动集合保持不变的区域内,梯度与 Hessian 为

g=M(a-a_u)-J^{\mathsf T}f,\qquad H_a=M+\sum_{z_i<0}\frac{J_i^{\mathsf T}J_i}{R_i}.
(15.13)
推导分段二次项的两次求导H_a=M+\sum_{z_i<0}J_i^{\mathsf T}J_i/R_i

活动行的代价为 z_i^2/(2R_i)。因为 \partial z_i/\partial a=J_i,一次和二次导数分别为

\nabla_a\frac{z_i^2}{2R_i}=J_i^{\mathsf T}\frac{z_i}{R_i}=-J_i^{\mathsf T}f_i,\qquad\nabla_a^2\frac{z_i^2}{2R_i}=\frac{J_i^{\mathsf T}J_i}{R_i}.

非活动行的两项贡献都为零。边界 z_i=0 上,两侧的一阶导数接续为零,二阶导数发生跳变。实现需要为边界选择一侧的活动状态,并在后续试探点重新判断。

Newton 方向求解 H_a p=-g。若整条步长都留在同一个二次区域,取单位步长便能到达该区域的极小点;跨越活动边界时,重新评价目标,并缩短步长保证下降。

F(a+\alpha p)\leq F(a)+c\alpha g^{\mathsf T}p,\qquad c\in(0,1).
(15.14)

当梯度非零、当前 Hessian 正定时,Newton 方向一定是下降方向。即使完整一步跨越了接触分区,足够短的正步长仍能满足回溯下降条件。

推导Newton 方向的下降性与回溯g^{\mathsf T}p=-g^{\mathsf T}H_a^{-1}g<0

H_a 为正定矩阵,代入 p=-H_a^{-1}g 得到

g^{\mathsf T}p=-g^{\mathsf T}H_a^{-1}g<0\quad(g\ne0).

在当前点附近,目标的变化为 \alpha g^{\mathsf T}p+o(\alpha)。右侧保留它的 c 倍,因此足够小的正步长能满足下降判据。教学代码从 \alpha=1 开始,每次减半,取 c=10^{-4}。

一次完整的方向计算与回溯

从候选加速度 a=(2,2)^{\mathsf T}\,\mathrm{m/s^2} 开始。它使地面分离、层间相对加速度为零,所以接触力暂为零。式(15.11)给出 F=144,梯度为 (12,12)^{\mathsf T}。边界行取非活动侧曲率,当前 Hessian 是单位阵,因此 Newton 方向为 p=(-12,-12)^{\mathsf T}。

若直接走完整一步,候选点变成 (-10,-10)^{\mathsf T}。此时地面项变为 500,总目标从 144 升到 500。缩短为半步后,到达 (-4,-4)^{\mathsf T}:惯性项为 36,地面项为 80,层间项为零,总目标降为 116,满足回溯判据。

\begin{array}{c|c|c|c}\alpha&a+\alpha p&F(a+\alpha p)&\text{结果}\\\hline1&(-10,-10)^{\mathsf T}&500&\text{拒绝}\\1/2&(-4,-4)^{\mathsf T}&116&\text{接受}\end{array}
计算活动集合变化后的下一方向H_a p=-g

在 a=(-4,-4)^{\mathsf T},地面接触力为 40\,\mathrm N,层间力为零。故

g=\begin{bmatrix}6\\6\end{bmatrix}-J^{\mathsf T}\begin{bmatrix}40\\0\end{bmatrix}=\begin{bmatrix}-34\\6\end{bmatrix},\qquad H_a=I+10\begin{bmatrix}1\\0\end{bmatrix}\begin{bmatrix}1&0\end{bmatrix}=\begin{bmatrix}11&0\\0&1\end{bmatrix}.

逐行解方向方程,得到 p=(34/11,-6)^{\mathsf T}。这个方向向右下方穿过层间活动边界;完整步长与半步仍使目标上升,四分之一步到达 (-71/22,-11/2)^{\mathsf T},目标约为 110.9628,被接受。此时两行都活动,下一 Hessian 为

H_a=I+10\left(\begin{bmatrix}1&0\\0&0\end{bmatrix}+\begin{bmatrix}1&-1\\-1&1\end{bmatrix}\right)=\begin{bmatrix}21&-10\\-10&11\end{bmatrix}.

两行活动区域内,令梯度为零就得到

\begin{bmatrix}21&-10\\-10&11\end{bmatrix}\begin{bmatrix}a_1\\a_2\end{bmatrix}=\begin{bmatrix}-10\\-10\end{bmatrix}.

行列式为 131,解为 a=(-210/131,-310/131)^{\mathsf T}。这个点满足 a_1<0、a_2-a_1<0,确实位于所用分区内,下一次完整 Newton 步便到达它。

实验 04叠放方块的 Newton 试探与回溯

坐标表示两物体的加速度。逐步查看梯度、曲率矩阵、搜索方向及各个被接受或拒绝的试探点。虚线分别标出地面和层间接触的活动边界。

最终接触力由软关系恢复为 f=(2100/131,1000/131)^{\mathsf T}\,\mathrm N,与式(15.9)的 PGS 极限一致。途中某个候选加速度和它产生的接触力可能尚不满足物体动力学,梯度 g=M(a-a_u)-J^{\mathsf T}f 正是两边的差;到达零梯度后,两种计算相互吻合。

MuJoCo 的 CG 与 Newton 在原始加速度目标上共用目标更新和线搜索框架。摩擦会使约束代价具有更丰富的分段结构。接触状态切换时,梯度和曲率都需要用当前状态重新计算。

求解结束后,接触力与加速度属于当前状态。时间积分还需要决定它们在一个有限时间段内如何使用。振子把这个选择简化为一个位置和一个速度:相同的加速度公式,放在步起点、步终点或若干中间试探点,会产生不同的离散轨迹。

05

振子状态与 Euler 方法

用质量为 1\,\mathrm{kg} 的弹簧阻尼振子考察时间推进。自然角频率为 \omega,阻尼系数除以质量后记作 \gamma:

\ddot q=-\omega^2q-\gamma\dot q,\qquad y=\begin{bmatrix}q\\v\end{bmatrix},\qquad\dot y=Ay,\quad A=\begin{bmatrix}0&1\\-\omega^2&-\gamma\end{bmatrix}.

相平面以位置为横轴、速度为纵轴。无阻尼时,轨迹沿能量椭圆运动;有阻尼时,机械能逐渐减少。

E=\frac m2(v^2+\omega^2q^2),\qquad\dot E=mv(-\omega^2q-\gamma v)+m\omega^2qv=-m\gamma v^2.

显式 Euler 用步起点的导数更新全部状态。半隐式 Euler 先更新速度,再用新速度更新位置:

\begin{array}{ll}\text{显式:}&v_{k+1}=v_k-h(\omega^2q_k+\gamma v_k),\quad q_{k+1}=q_k+hv_k,\\\text{半隐式:}&v_{k+1}=v_k-h(\omega^2q_k+\gamma v_k),\quad q_{k+1}=q_k+hv_{k+1}.\end{array}
(15.15)

对无阻尼振子,显式 Euler 在任意正步长下都会放大振幅;半隐式 Euler 在 0<h\omega<2 时保持有界。这个差别由更新矩阵的特征值决定,端点的重根还需单独检查。

推导无阻尼振子的更新矩阵0<h\omega<2\quad\text{(半隐式有界区间)}

将第二种方法的新速度代回位置式。两种矩阵分别为

G_e=\begin{bmatrix}1&h\\-h\omega^2&1\end{bmatrix},\qquad G_s=\begin{bmatrix}1-h^2\omega^2&h\\-h\omega^2&1\end{bmatrix}.

第一种方法的特征值是 1\pm ih\omega,模长大于一。第二种方法满足

\det G_s=1,\quad\operatorname{tr}G_s=2-h^2\omega^2,\quad\lambda^2-(2-h^2\omega^2)\lambda+1=0.

当 0<h\omega<2 时,两根是共轭复数,乘积为一,所以模长均为一。端点 h\omega=2 出现重根和一般性的 Jordan 线性增长;步长再增大时,有一个实根的模长超过一。

显式 Euler 每一步把真实能量乘以 1+h^2\omega^2。半隐式方法在稳定区间内则保持一个含交叉项的修正能量,真实能量围绕它振荡;因此有界轨迹仍会带有相位与能量误差。

推导显式能量增长与半隐式修正能量\widetilde E=\tfrac m2(v^2+\omega^2q^2-h\omega^2qv)

把显式更新代入能量,交叉项相消:

\begin{aligned}\frac{2E_{k+1}}m&=(v_k-h\omega^2q_k)^2+\omega^2(q_k+hv_k)^2\\&=(1+h^2\omega^2)(v_k^2+\omega^2q_k^2),\\E_{k+1}&=(1+h^2\omega^2)E_k.\end{aligned}

半隐式方法保留另一个二次量。令

K=\begin{bmatrix}\omega^2&-h\omega^2/2\\-h\omega^2/2&1\end{bmatrix},\qquad G_s^{\mathsf T}KG_s=K.

令 u=h^2\omega^2,先乘右侧矩阵,再乘左侧转置:

KG_s=\begin{bmatrix}\omega^2(1-u/2)&h\omega^2/2\\-h\omega^2(3-u)/2&1-u/2\end{bmatrix}.
\begin{aligned}(G_s^{\mathsf T}KG_s)_{11}&=\omega^2[(1-u)(1-u/2)+u(3-u)/2]=\omega^2,\\(G_s^{\mathsf T}KG_s)_{12}&=h\omega^2[(1-u)/2-(1-u/2)]=-h\omega^2/2,\\(G_s^{\mathsf T}KG_s)_{22}&=u/2+1-u/2=1.\end{aligned}

左下项由对称性确定。因此

\widetilde E=\frac m2(v^2+\omega^2q^2-h\omega^2qv)

沿离散轨迹保持不变。其矩阵行列式为 \omega^2(1-h^2\omega^2/4),在 h\omega<2 时正定,因而轨迹有界。真实能量围绕初值振荡,误差随步长减小而缩小。

同一连续振子可以在位置、相平面和能量三个视图中检查。位移曲线显示周期与相位,相平面显示轨迹是否收缩或发散,能量曲线则量化每一步带来的增益或耗散。下面所有曲线使用同一初值和时间步。

实验 05相轨迹、位移与能量

选择图示并切换比较曲线,观察相位偏移、能量增长和数值耗散。图中展示真实计算值;超出当前坐标范围的轨迹被图框裁切,当前读数仍保留完整数值。

有界性只说明离散轨迹没有无限增大,准确性还体现在相位和能量偏差随步长减小而收敛。比较积分器时,应同时看这三个视图,而不能仅由短时位移接近判断长期行为。

以 m=1、\omega=1、q_0=1、v_0=0、h=0.1 为例,初始能量为 0.5。显式一步得到 (q_1,v_1)=(1,-0.1),能量为 0.505;半隐式一步得到 (0.99,-0.1),能量为 0.49505。长期走势由更新矩阵的重复作用决定,单步能量的增减则能先显示两种方法不同的取值次序。

06

稳定域与全隐式 Euler

全隐式 Euler 使用步终点的导数。对线性振子,可以直接解出新速度与新位置:

v_{k+1}=v_k-h(\omega^2q_{k+1}+\gamma v_{k+1}),\qquad q_{k+1}=q_k+hv_{k+1}.

将新位置代入新速度方程,可直接解出两者。无阻尼时,全隐式 Euler 每步把能量除以 1+h^2\omega^2,因而即使连续运动守恒,离散轨迹也会收缩。

推导隐式方程的消元v_{k+1}=(v_k-h\omega^2q_k)/(1+h\gamma+h^2\omega^2)
\begin{aligned}(1+h\gamma)v_{k+1}+h\omega^2q_{k+1}&=v_k,\\(1+h\gamma+h^2\omega^2)v_{k+1}&=v_k-h\omega^2q_k,\\v_{k+1}&=\frac{v_k-h\omega^2q_k}{1+h\gamma+h^2\omega^2}.\end{aligned}

无阻尼时,更新矩阵为

G_i=\frac1{1+h^2\omega^2}\begin{bmatrix}1&h\\-h\omega^2&1\end{bmatrix},\qquad E_{k+1}=\frac{E_k}{1+h^2\omega^2}.

即使真实系统守恒,离散能量也逐步衰减。这种数值耗散解释了图中逐渐收缩的相轨迹。

标量测试方程 \dot y=\lambda y 把稳定性归结成复平面上的放大因子。设 z=h\lambda,一步更新写成 y_{k+1}=R(z)y_k。稳定域由 |R(z)|\leq1 给出。

R_e(z)=1+z,\qquad R_i(z)=\frac1{1-z},\qquad R_4(z)=1+z+\frac{z^2}{2}+\frac{z^3}{6}+\frac{z^4}{24}.

显式 Euler 的稳定域是以 (-1,0) 为圆心的单位圆盘,全隐式 Euler 的稳定域包含整个左半平面。RK4 与虚轴相交于 |h\lambda|\leq\sqrt8 的区间,给出了无阻尼振子的线性稳定步长界。

推导稳定域的边界|R(is)|\leq1\iff|s|\leq\sqrt8\quad\text{(RK4)}

令 z=x+iy。显式与隐式方法的条件可分别平方为

(1+x)^2+y^2\leq1,\qquad(1-x)^2+y^2\geq1.

前者是以 (-1,0) 为圆心的单位圆盘;后者包含整个左半平面。对无阻尼振子,特征值位于虚轴。将 z=is 代入四阶多项式:

\begin{aligned}R_4(is)&=1-\frac{s^2}{2}+\frac{s^4}{24}+i\left(s-\frac{s^3}{6}\right),\\|R_4(is)|^2&=\left(1-\frac{s^2}{2}+\frac{s^4}{24}\right)^2+\left(s-\frac{s^3}{6}\right)^2\\&=1-\frac{s^6}{72}+\frac{s^8}{576}.\end{aligned}

于是虚轴稳定区间为 |s|\leq\sqrt8。稳定条件保证误差没有因这个线性放大机制增长;准确重建相位仍需更细的步长。

放大因子把一个时间步对线性模式的作用浓缩成复数。下面把 z=h\lambda 作为平面上的点:落在某方法的稳定域内,表示该模式的模长每步都不会被放大。

实验 06复平面上的稳定域

阴影表示放大因子模长不超过一的区域。改变测试点的实部、虚部,比较三个方法在该点的放大倍数。灰色圆圈表示测试点,三个彩色开关只控制各自的稳定域。

无阻尼振子的特征值在虚轴上,减小步长会把测试点沿虚轴推向原点;阻尼使特征值移入左半平面。步长与连续系统的频率、衰减率因此共同决定它在稳定图中的位置。

提高时间精度的一种途径是在同一步内重新求几次导数。中间状态提供了加速度随状态变化的信息,RK4 再用固定权重组合这些信息。每次导数求值都对应一次当前状态上的动力学计算,所以时间精度与计算成本会一起改变。

07

四阶 Runge–Kutta 的中间状态

一个时间步内,物体位置和受力都会变化。只在步起点求一次导数,难以反映整段运动的变化。RK4 在步内构造几个试探状态,每到一个状态就重新求导,再把这些斜率加权成一次更新。

一般一阶系统写作 \dot y=F(t,y)。四阶 Runge–Kutta 方法(RK4)在一步内使用四个试探状态,每次都重新求导:

\begin{aligned}k_1&=F(t,y),\\k_2&=F(t+h/2,y+hk_1/2),\\k_3&=F(t+h/2,y+hk_2/2),\\k_4&=F(t+h,y+hk_3),\\y_{\rm new}&=y+\frac h6(k_1+2k_2+2k_3+k_4).\end{aligned}
(15.16)

第二、第三次求值的时间相同,试探状态各自来自不同的斜率,因此它们一般产生不同结果。在仿真中,每次求值都可能改变几何、质量矩阵、驱动力和接触状态。

线性系统的四次试探求值可依次展开成矩阵幂。加权结果与精确矩阵指数的前五项一致,所以一步误差从 h^5 开始,光滑固定时段内的累积误差为四阶。

推导线性振子中的四阶展开G_4=\sum_{j=0}^{4}(hA)^j/j!

当 F(y)=Ay 时,把各级试探值递次代入:

\begin{aligned}k_1&=Ay,\\k_2&=Ay+\frac h2A^2y,\\k_3&=Ay+\frac h2A^2y+\frac{h^2}4A^3y,\\k_4&=Ay+hA^2y+\frac{h^2}2A^3y+\frac{h^3}4A^4y.\end{aligned}

按权重相加并乘以步长,得到

y_{\rm new}=\left(I+hA+\frac{h^2A^2}{2}+\frac{h^3A^3}{6}+\frac{h^4A^4}{24}\right)y.

精确解为 \exp(hA)y;两者前五项相同,一步差值从 h^5 开始。在固定有限时段、解和导数有界时,累积误差为四阶。

对光滑非线性系统,函数在各试探点的多元展开还会出现二阶、三阶导数之间的组合。逐项匹配连续解的 Taylor 展开,可得到八个四阶条件;经典 RK4 的系数同时满足这些条件。

推导非线性系统的四阶条件y(t+h)-y_{\rm new}=O(h^5)

对自治系统,记导数算子为 F^{\prime},F^{\prime\prime},F^{\prime\prime\prime},在当前状态取值。连续解的导数逐次为

\begin{aligned}y^{\prime}&=F,\quad y^{\prime\prime}=F^{\prime}F,\\y^{\prime\prime\prime}&=F^{\prime\prime}(F,F)+F^{\prime}F^{\prime}F,\\y^{(4)}&=F^{\prime\prime\prime}(F,F,F)+3F^{\prime\prime}(F,F^{\prime}F)+F^{\prime}F^{\prime\prime}(F,F)+F^{\prime}F^{\prime}F^{\prime}F.\end{aligned}

最后一行由上一行逐项求导:双线性项对自身和两个输入求导得到一个三阶项、两个混合项;嵌套的一阶项再提供一个混合项及两个嵌套项。把这些导数代入 Taylor 式后,系数依次除以阶乘。

将四级公式写为 k_i=F(y+h\sum_j a_{ij}k_j),令 c_i=\sum_j a_{ij}、权重为 b_i。每一级使用同一个多元 Taylor 展开:

F(y+\Delta)=F+F^{\prime}\Delta+\frac12F^{\prime\prime}(\Delta,\Delta)+\frac16F^{\prime\prime\prime}(\Delta,\Delta,\Delta)+O(\|\Delta\|^4).

先用 k_j=F+O(h) 得到 \Delta_i=hc_iF+O(h^2);再把这一步结果代回各级,可依次取得二阶、三阶项。加权后的展开为

\begin{aligned}y_{\rm new}=y&+h\Bigl(\sum_i b_i\Bigr)F+h^2\Bigl(\sum_i b_ic_i\Bigr)F^{\prime}F\\&+h^3\left[\Bigl(\sum_{ij}b_i a_{ij}c_j\Bigr)F^{\prime}F^{\prime}F+\frac12\Bigl(\sum_i b_ic_i^2\Bigr)F^{\prime\prime}(F,F)\right]\\&+h^4\left[\Bigl(\sum_{ijk}b_i a_{ij}a_{jk}c_k\Bigr)F^{\prime}F^{\prime}F^{\prime}F\right.\\&\qquad+\frac12\Bigl(\sum_{ij}b_i a_{ij}c_j^2\Bigr)F^{\prime}F^{\prime\prime}(F,F)\\&\qquad+\Bigl(\sum_{ij}b_ic_i a_{ij}c_j\Bigr)F^{\prime\prime}(F,F^{\prime}F)\\&\qquad\left.+\frac16\Bigl(\sum_i b_ic_i^3\Bigr)F^{\prime\prime\prime}(F,F,F)\right]+O(h^5).\end{aligned}

与连续解的 Taylor 系数逐项比较:三阶两项的系数均为 1/6,四阶混合双线性项为 3/24,其余四阶项为 1/24。于是得到八个条件:

\begin{gathered}\sum_i b_i=1,\quad\sum_i b_ic_i=\frac12,\\\sum_i b_ic_i^2=\frac13,\quad\sum_{ij}b_i a_{ij}c_j=\frac16,\\\sum_i b_ic_i^3=\frac14,\quad\sum_{ij}b_ic_i a_{ij}c_j=\frac18,\\\sum_{ij}b_i a_{ij}c_j^2=\frac1{12},\quad\sum_{ijk}b_i a_{ij}a_{jk}c_k=\frac1{24}.\end{gathered}

四阶公式的非零系数为 a_{21}=a_{32}=1/2、a_{43}=1,并有 c=(0,1/2,1/2,1)、b=(1,2,2,1)/6。例如最后一个和只有路径 4\to3\to2 有贡献,等于 (1/6)\cdot1\cdot(1/2)\cdot(1/2)=1/24。其余和直接代入分别得到上面的七个分数。含时间的系统可把时间作为额外状态并令其导数为一。

RK4 的四个斜率分别来自四个试探状态。下面逐级画出试探点及其斜率,并与真实轨迹比较;两个中点求值发生在同一时间,却使用由不同斜率构造的状态。

实验 07RK4 的四个试探状态

在位置—速度平面逐级显示试探点和当前斜率;逐步按钮同时列出试探状态的公式、数值代入与最后的加权和。灰线为精确轨迹,铜色点为加权后的步终点,可逐项核对每级输入怎样产生下一级状态。

最后一步使用四个斜率的加权和。试探点本身可以偏离真实轨迹,权重通过抵消低阶误差形成更准确的步终点;接触切换降低光滑性时,这种高阶误差抵消的条件也会改变。

高阶精度要求一步内的导数足够光滑。碰撞激活、摩擦状态切换和不连续控制都会削弱这一条件。因此选择积分器还要考虑模型的接触频率、阻尼和每步计算成本。

阻尼很强时,当前速度的微小变化会显著改变下一时刻的力。速度隐式方法直接把这项反馈线性化,并将未知速度增量移到方程左侧。这样可以用一次修改后的质量矩阵求解处理强阻尼,当前位置引起的力则按本节约定保留。

08

速度隐式方法

速度隐式方法固定当前配置,在速度方向近似步终点的力。把当前净广义力记为 \tau(q,v),并定义 D=\partial\tau/\partial v。质量矩阵在这一步线性化中固定为当前值。

前面的积分公式已经决定怎样使用新速度。这里进一步处理速度变化引起的力变化,使阻尼等速度相关作用进入步终点的近似方程。

M(v_{\rm new}-v)=h\tau(q,v_{\rm new}),\qquad\tau(q,v_{\rm new})\approx\tau(q,v)+D(v_{\rm new}-v).

令 \Delta v=v_{\rm new}-v。把步终点的力展开到一阶,并收集所有含未知增量的项,可将这一步写成一个线性求解:

(M-hD)\Delta v=h\tau(q,v),\qquad v_{\rm new}=v+\Delta v.
(15.17)
推导修改质量矩阵的来源(M-hD)\Delta v=h\tau

令速度增量为 \Delta v。把一阶力近似代入隐式方程,再把未知量移到左边:

\begin{aligned}M\Delta v&=h\tau+hD\Delta v,\\(M-hD)\Delta v&=h\tau,\\v_{\rm new}&=v+h(M-hD)^{-1}\tau.\end{aligned}

计算实现先分解修改后的矩阵,再求解增量。若阻尼力为 -Cv 且 C 正定,则 D=-C,修改矩阵为 M+hC,阻尼方向上的响应被稳定地缩小。

对于振子,保持弹簧位置项为 q_k、对速度阻尼项取新值,得到

v_{k+1}=\frac{v_k-h\omega^2q_k}{1+h\gamma},\qquad q_{k+1}=q_k+hv_{k+1}.

在零阻尼情况下,上式回到半隐式 Euler;全隐式 Euler 的分母还含位置弹簧引入的 h^2\omega^2。振子图中的两条曲线可用来比较这两种取值方式。

只保留线性阻尼时,速度隐式方法对任意正步长都保持速度符号并衰减;显式更新要求 0<h\gamma<2 才有幅值衰减。两者的衰减倍率可以直接由一步方程求出。

推导阻尼测试方程与步长v_{k+1}=v_k/(1+h\gamma)

令弹簧项为零,速度满足 \dot v=-\gamma v。显式与速度隐式的放大因子分别为

v_{k+1}=(1-h\gamma)v_k,\qquad v_{k+1}=\frac{v_k}{1+h\gamma}.

当 0<h\gamma<2 时显式方法幅值衰减,其中 h\gamma>1 会造成交替变号。速度隐式对任意正步长都保持相同符号并衰减;增大步长仍会改变实际衰减时间的精度。

09

MuJoCo 的求解与积分实现

以下对照仓库内 MuJoCo 3.10.0。约束求解的主要实现位于 engine_solver.c;状态推进位于 engine_forward.c。局部模型和启用的功能会影响实际分支。

本地 PGS 在约束力变量上逐块更新,每轮用固定种子的伪随机序列打乱块的访问次序。椭圆摩擦块先沿法向或当前力的射线更新,再固定新的法向力,求解切向 QCQP。这两个子步骤降低块目标;第二节的精确锥块极小化给出了该块问题的整体目标。本地 PGS 每轮累加目标改进,按惯性与模型规模归一化后与 tolerance 比较,也受最大迭代次数限制。第十四章给出了固定法向 QCQP 的推导。

CG 与 Newton 在加速度变量上调用共同的原始求解框架:线搜索、更新约束状态、更新梯度,再产生下一方向。Newton 还更新约束 Hessian 及其分解。

本地 CG 默认采用 Hager–Zhang 类型的非线性共轭方向,并带重启与截断。编译分支 mjCG_PRP 选用另一种方向系数。第三节的固定二次 CG 为理解共轭性提供了可手算模型;阅读引擎时还要跟踪变化的活动状态和预条件梯度。

说明默认共轭方向中的变量p_{k+1}=-z_{k+1}+\beta p_k

记新旧梯度之差为 y=g_{k+1}-g_k,预条件梯度为 z=P^{-1}g,其差为 w=z_{k+1}-z_k,旧搜索方向为 p。本地默认分支先计算

\beta_{\rm HZ}=\frac{y^{\mathsf T}z_{k+1}-2\dfrac{y^{\mathsf T}w}{p^{\mathsf T}y}\,p^{\mathsf T}g_{k+1}}{p^{\mathsf T}y}.

分母过小时重启为预条件负梯度;正常分支对系数施加随方向和梯度范数变化的下界,再令 p_{k+1}=-z_{k+1}+\beta p_k。源码中 Mgrad 表示预条件梯度,需与动力学质量矩阵的变量区分。

Euler 路径在 mj_EulerSkip 中处理关节阻尼。启用相应阻尼项时,它使用修改质量矩阵求加速度;随后 mj_advance 先更新速度,再更新配置。RK4 对一步内的试探状态重复调用动力学计算。

本地积分路径的右端包含已经求得的约束力。修改矩阵中的 D 由选定的平滑力项构造:驱动力、被动力,以及相应分支中的速度偏置力。约束力在这次速度线性化中按当前值保留,因此 qDeriv 中保存的是这些平滑力项的速度导数。

implicit 路径调用 mjd_smooth_vel 并包含速度偏置力的导数,将 M-hD 装配到一般稀疏矩阵后进行 LU 分解。implicitfast 路径跳过该偏置导数,使用下三角存储与对称分解。柔性插值刚度还有额外的校正分支。

本地 implicitfast 对符合条件的自由刚体还采用中点速度推进部分自由度。该分支要求自由体构成独立六自由度树、保持唤醒且未参与约束,并在外层检查流体参数和离散逆动力学选项。质心是否与关节原点重合,决定中点更新涉及三个还是六个速度分量;相关判定位于 midpoint_eligible 与 midpoint_aligned。普通关节的速度隐式公式与这个自由体专用分支分别对应不同代码路径。

转动配置按流形更新。自由关节位置有平移和单位四元数,速度中则含线速度和三维角速度,因此两者数组长度可能不同。局部角速度的四元数更新沿用第三章:

Q_{k+1}=Q_k\otimes\begin{bmatrix}\cos(\|\omega_b\|h/2)\\\dfrac{\sin(\|\omega_b\|h/2)}{\|\omega_b\|}\omega_b\end{bmatrix}.

小角分支用对应的平滑极限。实现可从 mj_integratePos 跟踪到四元数积分函数,核对角速度坐标系及乘法次序。RK4 的配置组合同样要通过这种配置更新映射。

# 教学内核:在当前状态求加速度,再作半隐式一步。
def advance(q, v, h, acceleration):
    a = acceleration(q, v)
    v_next = [vi + h*ai for vi, ai in zip(v, a)]
    q_next = [qi + h*vi for qi, vi in zip(q, v_next)]
    return q_next, v_next

这个函数的配置采用普通标量分量。加入球关节或自由关节时,将最后一行配置更新替换为相应的流形映射。

本地求解器的初值与停止条件

在 engine_forward.c 的 warmstart 中,MuJoCo 将保存的 qacc_warmstart 代入当前雅可比与参考量,再由约束代价计算候选力。PGS 比较这组力的对偶目标与零力目标;原始方法比较热启动加速度与自由加速度的原始目标。接触集合已变化时,当前几何和约束参数仍参与这次重算。

本地 solPGS 每轮按块遍历约束,并对块序作伪随机置换;本节教学例固定先地面、后层间,以便逐行手算。源码用按问题惯性与规模归一化的目标改进量及最大迭代次数终止,式(15.10)则提供一个可以直接解释为力修正量的独立检验。

最后沿一条真实时间序列连接各章关系。每一步先由当前位置重算接触距离,处于激活区时构造参考量与锥问题,得到力后返回世界加速度,再更新速度和位置。下一步重新从几何查询开始;各数组由同一个当前状态生成。

10

球面接触的完整时间推进

沿用第十一至十四章的平面与球体模型,球的姿态固定,只允许质心平移。质量为 2\,\mathrm{kg},半径为 \rho=0.2\,\mathrm m,法线向上,切向沿世界横轴。下面的轨迹让球从指定高度下落,同时带有水平初速度。

质心高度为 z,几何间距为 \delta=z-\rho。本地碰撞候选距离采用 margin 与 gap 的和,力约束在 \delta<\texttt{margin} 时激活。恢复误差为 e=\delta-\texttt{margin}。

Ja_u=\begin{bmatrix}-g\\0\end{bmatrix},\qquad J M^{-1}J^{\mathsf T}=\frac1mI\quad\text{(按法向、切向排列)}.

第十二章的函数用误差和速度生成参考加速度、阻抗与正则化。取相同的法向、切向正则化,组装两个接触变量的目标:

H=\left(\frac1m+R\right)I,\quad b=\begin{bmatrix}-g-a_{{\rm ref},n}\\-a_{{\rm ref},t}\end{bmatrix},\quad a_{{\rm ref},t}=-Bv_x,\quad f_n\geq0,\quad |f_t|\leq\mu f_n.

本例的二维允许力域由内部、顶点和两条边组成。先检查无约束解,再沿每条边求一元极小点,最后比较可行候选的目标值,就能得到法向与切向的联合最优解。

推导二维摩擦锥上的精确极小化\min_{f\in\mathcal K}\phi(f)

凸锥的候选极小点包括内部、顶点和两条边。内部点为 -H^{-1}b,满足锥约束时保留;顶点为零。令边的符号为 s\in\{-1,1\},边上力表示为 f=t(1,s\mu)^{\mathsf T},其中 t\geq0。

\phi(t)=\frac12(H_{nn}+\mu^2H_{tt})t^2+(b_n+s\mu b_t)t,\quad t_* =\max\!\left(0,-\frac{b_n+s\mu b_t}{H_{nn}+\mu^2H_{tt}}\right).

比较所有可行候选的目标值,取最小者。二维锥的边界完整地由这两条射线与顶点组成,因而候选已经覆盖极小点的全部位置。

恢复世界方向的加速度后,使用半隐式 Euler 进行时间推进:

a_x=f_t/m,\quad a_z=-g+f_n/m,\qquad v^{\rm new}=v+ha,\quad x^{\rm new}=x+hv^{\rm new}.

现在把几何距离、软参考值、摩擦锥极小化和半隐式积分接成一条时间过程。下图分别显示球心位置与同一状态下重算的接触力;改变步长可比较接触瞬间的峰值与随后支撑状态。

实验 08软接触与摩擦的时间过程

播放下落、接触和水平减速过程;切换位置与接触力曲线,比较不同摩擦系数和步长。虚线标出球心达到接触激活距离时的高度。

接触力峰值受进入接触时的速度和位置误差影响,静止段则应满足法向力等于重力。摩擦使水平速度逐渐衰减;零摩擦时水平速度保持不变。这几条关系可以逐项检验整条仿真流程。

软接触允许一定的位置偏差,margin 也会使力在几何表面相交前出现。正间隙表示两表面尚未接触,负间隙的绝对值则是穿透深度;恢复误差还需减去激活距离。静止时支撑力趋近重力,水平力在零滑速附近衰减。

静止支撑时速度和加速度同时为零,所以法向力必须等于 mg。软约束方程随后把支撑力转成平衡位置误差:-Kd(e)e=R(e)mg。将该误差加回接触边界即可得到球心的支撑高度。

推导静止支撑高度的检验-Kd(e)e=R(e)mg

设切向速度为零,竖直加速度也为零。动力学给出 f_n=mg,对偶最优条件给出

\left(\frac1m+R\right)mg-g-a_{{\rm ref},n}=0\quad\Longrightarrow\quad a_{{\rm ref},n}=Rmg.

静止时参考加速度是 -Kd(e)e,因此平衡误差满足 -Kd(e)e=R(e)mg。当误差幅值位于阻抗的饱和段,代入常量即可直接求解;其余情况可以在这一标量方程上求根。

from solvers_integrators import contact_trace

trajectory = contact_trace(height=0.6, speed=0.8, step=0.005,
                           duration=2.0, friction=0.6)
last = trajectory[-1]
print("state:", last["state"])        # x, z, vx, vz
print("force:", last["force"])        # normal, tangent
print("surface gap:", last["distance"])

在 examples 目录运行这段代码即可得到与图示相同的数据。几何间距、参数映射、锥求解和积分分别保存在独立函数中;每个时刻的力读数都由同一时刻的状态重新计算。

11

习题

习题 1 · 接触耦合与分离

两方块模型取 P=0,R=0,从零力完成两轮 PGS,并写出每轮末的物体加速度。再取 P=15\,\mathrm N,计算第一轮,并解释零力行为何允许正残差。

解答逐行力、加速度与互补条件f=(10,0)^{\mathsf T}\,\mathrm N(分离状态)
f:(0,0)\to(10,0)\to(10,5)\to(15,5)\to(15,7.5).

两轮末的加速度依次为 (-5,-5)^{\mathsf T} 与 (-2.5,-2.5)^{\mathsf T}\,\mathrm{m/s^2}。上拉力为 15\,\mathrm N 时,第二行试算力为 -2.5\,\mathrm N,投影后为零;解为 f=(10,0)^{\mathsf T}\,\mathrm N、a=(0,5)^{\mathsf T}\,\mathrm{m/s^2}。第二行间隙加速增大,零支撑力与正分离加速度同时成立,符合互补条件。

习题 2 · 共轭方向

取 H=\operatorname{diag}(1,4)、b=0,从 x=(1,1)^{\mathsf T} 出发,计算共轭梯度第一步,并检验下一方向与第一方向的共轭性。

解答计算过程与结果
g_0=(1,4)^{\mathsf T},\quad p_0=(-1,-4)^{\mathsf T},\quad\alpha_0=17/65,\quad x_1=(48/65,-3/65)^{\mathsf T}.
g_1=(48/65,-12/65)^{\mathsf T},\qquad\beta_0=144/4225,\qquad p_1=(-3264/4225,204/4225)^{\mathsf T}.
p_0^{\mathsf T}Hp_1=(3264-3264)/4225=0.

第二次精确线搜索得到零点,可用二维线性求解直接核对。

习题 3 · 软法向 Newton 更新

取一维质量 m=2、自由加速度 a_u=-9.81、参考加速度为零、正则化 R=0.1。写出原始目标,在活动区求 Newton 极小点,并核对接触力。

解答计算过程与结果
F(a)=(a+9.81)^2+5\min(0,a)^2.
a<0:\quad g=2(a+9.81)+10a=12a+19.62,\quad H_a=12.
a_*=-1.635,\quad f=-a_*/R=16.35,\quad ma_*=-19.62+16.35=-3.27.

从活动区任一点进行单位 Newton 步都会到达该极小点。软约束留下了与正则化相关的负加速度。

习题 4 · 能量与步长

令无阻尼振子的 m=1\,\mathrm{kg}、\omega=2\,\mathrm{s^{-1}},h=0.1\,\mathrm s,初态为 (q,v)=(1,0)。分别作一步显式、半隐式和全隐式 Euler,比较真实能量和修正能量。

解答计算过程与结果
\begin{array}{c|c|c}\text{方法}&(q_1,v_1)&E_1\\\hline\text{显式}&(1,-0.4)&2.08\\\text{半隐式}&(0.96,-0.4)&1.9232\\\text{全隐式}&(25/26,-5/13)&25/13\end{array}

初始能量为 2\,\mathrm J。半隐式的修正能量为 1.9232-0.5\cdot0.1\cdot4\cdot0.96\cdot(-0.4)=2,与初值相同。

习题 5 · 阻尼衰减

对 \dot v=-20v,分别取 h=0.02,0.08,0.12\,\mathrm s。求显式和速度隐式的放大因子,解释变号和发散。

解答计算过程与结果
R_e=0.6,-0.6,-1.4;\qquad R_v=5/7,5/13,5/17.

第二个显式步长交替变号并衰减,第三个幅值增大。速度隐式的三个因子均在零到一之间;与精确因子 \exp(-20h) 比较仍能看到时间离散误差。

习题 6 · RK4 的逐级求值

对第四题的振子,逐级计算一次 RK4。再把步长减半,并在相同终止时间比较误差。

解答计算过程与结果
\begin{aligned}k_1&=(0,-4),\\y_2&=(1,-0.2),&k_2&=(-0.2,-4),\\y_3&=(0.99,-0.2),&k_3&=(-0.2,-3.96),\\y_4&=(0.98,-0.396),&k_4&=(-0.396,-3.92).\end{aligned}
y_1=(0.9800666667,-0.3973333333),\qquad y(h)=(\cos0.2,-2\sin0.2).

固定终止时间且步长足够小时,步长减半使全局误差约缩小十六倍。可以调用 oscillator_trace 并用 oscillator_exact 比较;两组结果必须使用同一个终止时间。

习题 7 · 摩擦锥的边界极小点

取 H=I、b=(-1,2)^{\mathsf T}、\mu=0.5。求非负法向摩擦锥内的最优力,并与先求法向再裁剪切向的结果比较目标值。

解答计算过程与结果

无约束点为 (1,-2),在锥外。负切向边使用 s=-1:

f_n=\frac{1+0.5\cdot2}{1+0.5^2}=1.6,\quad f_t=-0.8,\quad\phi=-1.6.

先固定法向为一再裁剪切向得到 (1,-0.5),目标为 -1.375。联合极小化允许法向与切向同时调整,得到更低的目标。

习题 8 · 完整接触轨迹

运行第十节的球面接触模型。将摩擦系数设为零,检查水平速度;再恢复摩擦,把步长从 0.005\,\mathrm s 减到一半,比较两秒后的高度和速度。

解答计算过程与结果

零摩擦时两条边重合到法向轴,因此 f_t=0,水平速度保持初始值。存在摩擦时,水平速度随接触减小。

比较步长时,初态、接触参数和终止时间保持一致。用共享默认参数,支撑力逐渐接近 19.62\,\mathrm N;几何间距通常为正,因为激活距离取 0.02\,\mathrm m。

for h in (0.005, 0.0025):
    end = contact_trace(step=h)[-1]
    print(h, end["state"], end["force"])
zero_friction = contact_trace(friction=0)
assert max(abs(s["state"][2] - 0.8) for s in zero_friction) < 1e-12

若两个步长的结果差异仍大,可继续减小步长,检查接触激活附近的瞬态。对比时同时保留位移、速度和力曲线,避免只看一个终点数值。