机器人抓取问题求解的块子梯度贪心Kaczmarz方法(Block Subgradient Greedy Kaczmarz Methods for Robotic Grasping Problems)

《Axioms》：Block Subgradient Greedy Kaczmarz Methods for Robotic Grasping Problems

　　

摘要：机器人抓取问题首先被建模为线性互补问题(Linear Complementarity Problem, LCP)，并重新表述为非光滑方程组(Nonsmooth Equations)。研究人员提出两种块Kaczmarz方法来求解该方程组。利用K-means聚类算法对非光滑方程进行划分，基于所得块信息构建了子梯度贪心随机化Kaczmarz方法(Subgradient Greedy Randomized Kaczmarz Method)与子梯度多步贪心Kaczmarz方法(Subgradient Multi-Step Greedy Kaczmarz Method)。给出了所提块子梯度Kaczmarz方法的渐近收敛性证明。数值结果证实了新方法在计算精度上的优越性。

论文解读：机器人抓取问题中线性互补问题的块子梯度贪心Kaczmarz方法求解

一、研究背景与意义

多指机器人抓取(Multi-fingered Robotic Grasping)是机器人操作的核心环节，涉及感知、位姿生成、轨迹规划及接触力求解。抓取过程中位移与接触力满足互补关系，结合平衡方程、摩擦定律及最大耗散原理可建立线性互补问题(LCP, Linear Complementarity Problem)。LCP的系数矩阵通常为鞍点结构(Saddle-point Matrix)，不具备投影法或模矩阵分裂迭代法所需的收敛条件。现有将LCP转化为非光滑方程并结合Newton-Kaczmarz类方法（如NSNGRK与NSNMGK）虽可行，但单行选取策略在处理大规模或病态系统时效率受限。块Kaczmarz(Block Kaczmarz)方法通过对方程行分块投影可改善条件数，但鲜见于非光滑LCP求解。因此，研究人员将K-means聚类引入广义Jacobian矩阵行划分，结合贪心随机选取策略与子梯度Newton框架，提出Block Newton-Subgradient Nonsmooth Greedy Randomized Kaczmarz (BNSNGRK_k)与Block Newton-Subgradient Nonsmooth Multi-Step Greedy Kaczmarz (BNSNMGK_k)两种方法，并证明其渐近收敛性。该文发表于《Axioms》。

二、关键技术方法概述

研究人员采用Fisher–Burmeister函数将LCP重构为Φ(z)=0形式的非光滑向量方程；利用对偶数自动微分(Dual-number Automatic Differentiation)或中心差分计算Clarke广义Jacobian矩阵?Φ(z)；每轮外迭代对广义Jacobian各行做K-means聚类得到p个行索引块Ω_i，取各块质心最近行作为代表行构建代表Jacobian矩阵J?与代表残差r?；定义阈值ξ=max_i|r?_i|·‖J?_i‖₂/‖J?_i‖_F筛选候选块集S={i:|r?_i|·‖J?_i‖₂/‖J?_i‖_F≥θ·ξ}，按概率P(i∈S)∝|r?_i|²选块(BNSNGRK_k)或依次更新所有候选块(BNSNMGK_k)；选块后用完整子矩阵J_Ωi与残差r_Ωi做Moore–Penrose伪逆更新x_k+1=x_k-J_Ωi⁺r_Ωi，迭代至‖Φ(x_k)‖≤tol。数值实验以L形平面块、三棱柱及立方体为抓取对象，摩擦锥分别用四面体(4边)与八面体(8边)金字塔近似，Lemke法作基准对照。

三、研究结果

2. Problem Description and Preliminaries（问题描述与预备知识）

给出LCP标准形式w=Mz+q, w≥0, z≥0, w^Tz=0及抓取问题系数矩阵的鞍点分块结构。引入Fisher–Burmeister函数?(a,b)=a+b-√(a²+b²)将LCP等价于Φ(z)=0。定义次梯度(Subgradient)、Clarke广义Jacobian ?Φ(z)=conv{lim JΦ(z_k)|z_k→z, Φ可微于z_k}，并列出局部切锥条件(Local Tangential Cone Condition)及相关引理(Lemma 1–3)。

3. Block Subgradient Greedy Kaczmarz Method Based on K-Means Clustering and Convergence Analysis（基于K-means聚类的块子梯度贪心Kaczmarz方法及收敛性分析）

详述广义Jacobian数值构造、K-means行聚类流程、代表行选取、候选块筛选概率及块Newton–Kaczmarz更新公式。给出Algorithm 1 (BNSNGRK_k)与Algorithm 2 (BNSNMGK_k)。证明Lemma 4（局部切锥条件下残差与误差界关系）与Lemma 5（选定块更新下的误差收缩引理，要求κ₂(J_Ωi)²·L·η<2）。在此基础上证明Theorem 1：BNSNGRK_k生成的序列依期望满足E[‖x_k-z‖²]≤(1-ρ)^k‖x₀-z‖²，其中收缩因子含块Jacobian谱条件数κ₂(J_Ωi)之平方，较单行方法更小故收敛更快。Theorem 2：BNSNMGK_k的多步更新具类似误差衰减估计，且因每轮处理多个候选块进一步减少外迭代次数。

4. Experimental Results（实验结果）

4.1. Planar Grasping Problem（平面抓取问题）

平面LCP经正则化后Lemke法得精确解。BNSNGRK_k与BNSNMGK_k在容差10^-8下残差下降速度快于NSNGRK，达到相同精度所需外迭代更少；经验统计显示沿迭代轨迹Lemma 5中收缩条件实际成立（η中位约0.08?2/κ²L）。

4.2. Three-Finger Grasping of an Isosceles Prism（三指抓取等腰棱柱）

四面体摩擦锥近似下Lemke可解，NSNGRK算得抓力与精确解偏差明显，而块方法抓力与位移均高精度吻合；八面体近似下Lemke失效，块两方法结果互洽且均值绝对误差小，表明块方法对高阶病态LCP仍具鲁棒高精度。

4.3. Three-Finger Grasping of a Cube（三指抓取立方体）

收紧容差至10^-10，NSNGRK不收敛；块两方法均收敛，BNSNMGK_k外迭代数少于BNSNGRK_k，抓力计算结果一致，验证了多步块更新的效率优势。

四、讨论与结论

研究人员指出：所提BNSNGRK_k与BNSNMGK_k方法借助K-means对广义Jacobian行聚类形成块结构，结合残差引导的贪心随机块选取与子梯度Newton更新，显著提升了机器人抓取LCP模型非光滑方程求解的数值精度与收敛速度（外迭代次数减少）。收敛性分析表明块Jacobian条件数进入收缩因子使理论收敛率优于单行贪心Kaczmarz。数值实验在典型平面及三维三指抓取场景下验证了其相较NSNGRK方法在求解抓力与相对位移上的精度优势，且多步块版本(BNSNMGK_k)进一步降低迭代步数。由于每轮外迭代执行K-means带来额外开销，少迭代不必然等价于短总耗时，未来可通过热启动质心、增量聚类或周期重聚类降低聚类成本。论文结论为：将基于K-means的块划分融入子梯度贪心Kaczmarz框架可有效解决多指机器人抓取中的线性互补问题求解精度不足问题，为机器人抓取规划中的在线数值计算提供了高精度迭代算法。