Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions
Arjun Narayanan, Per-Olof Persson
cs.LG
2026-09-26
半边卷积策略从空边界长出四边形剖分,96未见域全成网、95.7可用、90.2达par;同规模Gmsh完成51且无一最优。
四边形块剖分要把平面区域切成尽量规则的粗四边形网格。单元形状差可以平滑或再分,顶点价错了就是奇点,加密也消不掉。结构网格、张量积基、细分曲面都靠规则连通性;工业网格器事后修价,推进前沿又会多造奇点。这类剖分至今大量靠手和启发式,通常不奔着最优去。
最优有下界。离散 Gauss-Bonnet 恒等式只凭角点和拓扑,就能算出任意全四边形网格的顶点不规则度下限,论文叫 par。网格还没长出来就能算,打到它的连通性就是可证最优。奖励极稀疏,但成功自带证书。均匀随机在五、六边形上大约 3% 打到 par,超过八边的一个都打不到。前作在已有全四边形上改价;这里从空边界起步。
状态是半边网格:每条边两条反向半边,连通性全靠 next、prev、twin。回合从单面边界开始,四个局部动作是向面环前方第 2、3、4 个顶点拉弦,或在当前边上插点。非法动作被 mask,删除关掉,避免走一步再撤销。
策略卷积沿着网格自己的连通性走,每个半边读自己和三个邻居的特征,约 37 万参数,不按位置或规模索引,没见过的大区域可以直接用。观察是 64 个半边的窗口,外加七维全局量(含离 par 的距离),按面数归一化。
奖励用势函数惩罚面缺陷、超出 par 的不规则度、已完成四边形里最差的形状质量,再除以初始缺陷,让不同大小区域的回报落在同一尺度。终止要全四边形、不规则度等于 par,并且解缠平滑后最低质量 q ≥ 0.1。
稀疏奖励靠行为克隆跨过去。多连骨牌、圆环、极坐标轮毂本身就是最优网格,合法往回拆即示范。9000 个认证实例、约 18.7 万对,克隆六轮 top-1 对齐 93.7%,再 PPO 四百万步,35% 回合仍走认证实例;价值头先冻结暖四十轮。整套在 Apple M2 上约四小时。
评测用 GEO2D:带倒角、孔的机械零件轮廓,评测域训练未见。每域五次尝试(一次贪心、四次采样),预算加倍,必要时最多三轮拆分修复。所有方法过同一套解缠平滑再计分。
| 方法 | 全四边形 | 可用(q≥0.3) | 达par | 超par中位数 | 单元数 |
| 智能体(8-24角,96域) | 96.0 | 95.7 | 90.2 | 0 | 16 |
| Gmsh blossom 同单元数 | 51 | 38 | 0 | 9 | 19 |
| Gmsh quasi-structured | 96 | 96 | 2 | 7.5 | 51(3.2×) |
| Gmsh blossom-full | 96 | 96 | 0 | 26 | 220(14×) |
| 智能体(25-50角,64域) | 64.0 | 62.0 | 31.0 | 0.75 | 78 |
| Gmsh blossom 同单元数 | 26 | 18 | 0 | 39 | 97 |
规则性上,对所有能比的域、所有 Gmsh 配置、任意单元数,智能体全胜。七种 Gmsh 在 96 域共 672 次尝试,打到可证最优只有三次。
从零训 PPO 一百万步,96 域达 par 仅 7.2;只克隆 22.3;克隆再 PPO 到 76.2。同等参数、不吃邻接的 Transformer,在更早一版配方、两百万步下达 par 约一半(94.5 vs 51.5)。从未训练的曲线边界加测试时搜索,96 域超 par 中位数 2、37 个达 par;Gmsh 超 par 10-32、最多 2 个达 par。
给网格生成一个可证的终止条件,比「看起来规整」硬得多。智能体从空边界长网格,不依赖已有全四边形初值;卷积跟着半边走,尺寸外推是设计进去的。
场景很窄:二维平面块剖分,给结构网格、多块离散、细分当粗骨架。Gmsh 毫秒出网,这个未优化实现分布内不到一秒、大域数秒、最大带孔域要分钟,曲线修复搜索单域可到十分钟。要可证规则的粗四边形块,这个更接近答案;要快、密、任意 CAD,仍是工业网格器。
论文自己列了三条:解缠平滑在回路里,策略对着这个测试训;速度比 Gmsh 慢一到两个数量级;曲线边界要靠测试时搜索才能过质量线。
评测域全部 par 为零,非零下界只在子问题和 48 个 hold-out 上测过(47/48 达 par)。GEO2D 是格子零件,不是任意 CAD。大域上评测流程贡献很大:默认预算可用 41.0/64,加倍 54.5,修复才到 62.0。分布外训练种子波动约五个域,大边界数字应按区间读。25-50 角曲线域规则性仍领先,过质量线的次数少于用更多单元的 Gmsh。没有三维六面体实验。