Learning to Solve Compositional Geometry Routing Problems¶

会议: NeurIPS 2026
arXiv: 2605.18094
OpenReview: https://openreview.net/forum?id=kvdydED2s3
领域: 优化/理论
关键词: 神经组合优化, 组合几何路径规划, 差分注意力机制, 双层对比学习, 策略强化学习

一句话总结¶

针对涵盖点、线、面多几何混合且动作空间庞大冗余的组合几何路径规划问题（CGRP），提出即插即用求解框架 DiCon，通过差分注意力抑制次优候选动作并结合实例级与任务内双层对比学习，显著提升神经求解器的表征能力与零样本组合泛化性。

研究背景与动机¶

路径规划问题是机器人巡检、灾难搜救、现代物流以及设施维护等实际空间决策任务的理论基石。然而，传统规划模型通常假定单一的服务几何类型：节点路径规划（如旅行商问题 TSP）将任务抽象为离散点；弧段路径规划聚焦于道路、管道或裂缝等线段结构；区域覆盖路径规划则要求机器人在传感器检测范围内完整扫描特定空间多边形。在真实世界的复杂任务中（例如无人机对水域进行覆盖巡视、沿输电线路进行缺陷排查、并在关键输电基塔停靠采样），任务往往表现为点、线、面不同几何形态的任意混合。若将这些场景人为割裂并使用特定几何的独立算法求解，极大地限制了求解器的通用性与协同优化能力。

将这些混合几何形式统一建模为组合几何路径规划问题（Compositional Geometry Routing Problem, CGRP）面临着三大核心困难。首先是非对称性加剧：非点任务（线和面）包含固有的内部服务路径，从前驱任务进入该任务以及从该任务离开前往后继任务的旅行距离往往不相等。其次是内部服务路径与外部跨任务路由的紧耦合：为线或区域任务选定具体的出入口（entry-exit pair）既是局部覆盖决策，又直接改变了与前后任务的连接成本。最关键的是动作空间的组合爆炸与信噪比急剧恶化：每个非点任务都衍生出多个几何可行但策略上弱劣的候选出入口配置，传统神经组合优化（NCO）策略在庞大且嘈杂的动作分布中极易分散注意力并陷入过度探索。

针对表示学习受阻与决策阶段候选动作冗余的双重挑战，本文的核心切入角度是将决策侧的注意力主动去噪与表征侧的双粒度几何对齐解耦并联合优化。核心 idea：提出即插即用框架 DiCon，在解码器中引入差分注意力机制（Differential Attention）通过两路注意力图差分主动抵消次优动作的概率分布，同时在编码端构建旋转反射不变的实例级对比学习与聚类语义等价出入口的任务内对比学习，实现高信噪比决策与跨几何组合泛化。

方法详解¶

整体框架¶

DiCon 是一个与模型骨干（Backbone）解耦的即插即用增强框架，能够无缝嵌入主流自回归神经求解器（如 POMO 和 RELD）。整体流程分为统一几何特征编码、多层编码器全局表征、解码端差分注意力降噪决策，以及训练阶段的双层对比自监督辅助约束。在输入端，模型将点任务、线任务和区域任务提取为统一的 4 维出入口坐标、2 维几何中心锚点以及 1 维离散几何类别指示符；在解码端，采用差分多头注意力替代标准 MHA 以聚焦高价值转移；在损失端，结合策略梯度与双层对比损失端到端协同更新网络。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入实例<br/>点/线/面任务混合坐标集"] --> B["统一特征编码<br/>出入口坐标 + 几何锚点 + 类别指示"]
    B --> C["多层 Transformer 编码器<br/>提取多任务几何感知隐层表征"]
    C --> D["双层对比学习优化<br/>实例级旋转不变 + 任务内语义聚类"]
    C --> E["差分多头注意力解码器<br/>双软最大值注意力图差分去噪"]
    E --> F["输出有效巡回路径<br/>各任务访问顺序与最佳出入口选择"]
    D -.->|联合梯度正则化| C

关键设计¶

1. 统一几何特征编码：抹平多几何形态输入鸿沟 传统节点路径规划器仅接受单点二维坐标输入，无法直接容纳包含自身物理尺寸与多候选形态的线段和区域面任务。为此，DiCon 提取三组基础几何属性：所有候选节点的出入口坐标对 $L_i = \{L_i^+, L_i^-\} \in \mathbb{R}^4$（对于点任务及 Depot，入点与出点重合且服务成本 $c_i=0$；线任务两端为入出点且 $c_i$ 为线段长度；区域任务生成 $\omega$ 组沿长边锯齿状扫描的候选出入口且 $c_i$ 为覆盖路径长度）；几何中心锚点 $G_i \in \mathbb{R}^2$（点坐标或线/面中心）；以及类型指示符 $I_i \in \{0, 1, 2\}$（分别表示面、线、点）。初始节点嵌入向量由可学习映射线性投影后相加融合： $$h_i^0 = W_L L_i + W_G G_i + W_I I_i + b$$ Depot 节点则单独由投影参数映射为 $h_0^0$。该设计使得编码器在统一的连续隐空间内捕捉异构几何实体之间的空间交互与拓扑分布。

2. 差分注意力机制：解码阶段的主动注意力去噪 在 CGRP 中，区域任务的 $\omega$ 组扫描配置及线任务的两种穿越方向带来了海量的候选出入口动作，其中大量候选在几何上合法但在全局全局路由上极度次优（例如背离主路径流动方向的折返配置）。标准多头注意力（MHA）在计算上下文与候选的匹配度时，会向所有合法动作弥散注意力概率质量，造成严重的过度探索。DiCon 将解码器的注意力机制重构为差分多头注意力（MHDA）。对于注意力头 $m \in [1, \dots, M]$，将查询与键划分为两组独立的映射 $Q_m^1, Q_m^2$ 和 $K_m^1, K_m^2$，分别计算两个独立的 Softmax 注意力图： $$A_m^1 = \text{softmax}\left(\frac{Q_m^1 (K_m^1)^T}{\sqrt{d/M}}\right), \quad A_m^2 = \text{softmax}\left(\frac{Q_m^2 (K_m^2)^T}{\sqrt{d/M}}\right)$$ 最终注意力输出由两个图的加权差分与值矩阵相乘得到： $$s_m = (A_m^1 - \lambda_m A_m^2) V$$ 其中 $\lambda_m \ge 0$ 是头部专属的可学习缩放因子（初始化为 0.5）。第二路注意力分支专门用于捕捉普遍存在但优先级较低的背景关联与弱候选特征，通过相减操作主动压制低显著性动作上的概率权重，使得输出熵显著下降，解码器能够高置信度聚焦于关键出入口。

3. 双层对比学习：解耦实例全局不变性与任务内局部一致性 为了解决不同几何混合比例导致的表征泛化困难，DiCon 引入实例级与任务内双层自监督对比约束。在实例级别，利用路径优化对刚体几何变换（旋转与坐标轴镜像翻转）的本质不变性，对同一实例生成 $\mathbb{A}$ 个增广视图，通过带有 Stop-gradient 的 SimSiam 结构预测器最大化不同增广视图全局表征间的余弦相似度： $$\mathcal{L}_{\text{CL}}^{\text{ins}} = -\frac{1}{\mathbb{A}(\mathbb{A}-1)} \sum_{\xi=1}^{\mathbb{A}} \sum_{\tau \neq \xi} \frac{q^\xi}{\|q^\xi\|_2} \cdot \frac{z^\tau}{\|z^\tau\|_2}$$ 在任务内级别，考虑到属于同一区域任务的 $\omega$ 个出入口候选或同一线任务的正反方向虽然坐标完全不同，但服务的是同一个底层语义目标。若任由编码器独立表征这些候选，会割裂同一任务的内在关联。因此设计任务内对比损失：在不同视图之间，以某一候选的预测输出为查询，将同一任务下的其他语义等价候选作为正样本拉近： $$\mathcal{L}_{\text{CL}}^{\text{intra}} = -\frac{1}{2\mathbb{A}(\mathbb{A}-1)} \sum_{\xi=1}^{\mathbb{A}} \sum_{\tau \neq \xi} \left[\mathcal{L}_{\text{area}}(\xi, \tau) + \mathcal{L}_{\text{line}}(\xi, \tau)\right]$$ 该设计使潜在特征空间中同一任务的多个候选紧密聚类，同时保持不同任务间的可分性，大幅提升了对多候选非点几何任务的结构感知力。

损失函数 / 训练策略¶

整个模型的端到端联合训练目标为强化学习策略梯度与双层对比损失的加权三元组： $$\mathcal{L}_{\text{total}} = \mathcal{L}_{\text{RL}}^\theta + \lambda_{\text{ins}} \mathcal{L}_{\text{CL}}^{\text{ins}} + \lambda_{\text{intra}} \mathcal{L}_{\text{CL}}^{\text{intra}}$$ 其中主策略损失 $\mathcal{L}_{\text{RL}}^\theta$ 采用带有共享基线的 REINFORCE 算法优化，以多个增广视图的平均回报作为基线降低方差。超参数配置为 $\lambda_{\text{ins}} = 0.10$ 与 $\lambda_{\text{intra}} = 0.02$。在反向传播中，编码器、投影头和预测头由三项损失共同更新，而解码器仅由 RL 策略损失优化。

实验关键数据¶

主实验¶

在评测中，以主流强启发式求解器 LKH3 作为计算性能差距（Gap）的基线，测试覆盖同分布规模（20、100）、外推大尺度（200、300）以及不同组合几何形态。在两套先进神经骨干 POMO 与 RELD 上的主要对比结果如下：

数据集/规模	指标	DiCon-R-Aug (本文最佳)	DiCon-P (POMO增强)	RELD (原始骨干)	POMO (原始骨干)	Gurobi (商用精确解)	LKH3 (基准)
CGRP-20 (同分布)	Obj / Gap(%) / Time	6.065 / -0.02% / 1.36s	6.075 / 0.14% / 0.07s	6.074 / 0.13% / 0.09s	6.076 / 0.15% / 0.09s	6.065 / -0.02% / 8.49m	6.066 / 0.00% / 7.53m
CGRP-100 (同分布)	Obj / Gap(%) / Time	8.363 / 0.10% / 4.01s	8.406 / 0.63% / 0.16s	8.406 / 0.63% / 0.26s	8.465 / 1.32% / 0.19s	8.423 / 0.82% / 2.86h	8.354 / 0.00% / 50.30m
CGRP-200 (大尺度泛化)	Obj / Gap(%) / Time	13.755 / 0.57% / 20.95s	13.949 / 1.99% / 0.80s	13.922 / 1.79% / 1.17s	14.115 / 3.20% / 0.94s	14.451 / 5.66% / 5.03h	13.677 / 0.00% / 3.32h
CGRP-300 (大尺度泛化)	Obj / Gap(%) / Time	15.595 / 2.84% / 43.44s	16.021 / 5.65% / 2.14s	15.839 / 4.45% / 2.99s	16.344 / 7.78% / 2.58s	16.253 / 7.17% / 10.08h	15.165 / 0.00% / 7.96h

此外，在纯线任务 Line100 以及混合极值场景 Area20+Line80 等未见过的极端几何组合测试中，DiCon 展现出压倒性的泛化性能：在 Line100 上，DiCon-R-Aug 达到 12.319（Gap 为 -2.10%，超越 LKH3 的 12.582 且用时仅 7.71s vs. 29.77m）；在 Area20+Line80 上，DiCon-R-Aug 达到 16.217（Gap 为 -1.78%，超越 LKH3 的 16.510 且用时仅 10.87s vs. 43.63m）。

消融实验¶

通过对 DiCon 关键机制（差分注意力 DA、实例级对比学习 IL-CL、任务内对比学习 IT-CL）在 CGRP-100 和极端混合场景 Area20+Line30 上的逐级剥离验证，各模块的贡献度与参数/效率分析如下：

配置	CGRP-100 Obj (Gap%)	Area20+Line30 Obj (Gap%)	说明
DiCon-P (Full Model)	8.406 (+0.63%)	12.470 (-0.43%)	完整模型：含 DA + IL-CL + IT-CL
w/o IT-CL	8.421 (+0.80%)	12.485 (-0.31%)	去除任务内对比学习，语义聚类缺失
w/o IT-CL & IL-CL	8.431 (+0.92%)	12.493 (-0.25%)	进一步去除实例级对比学习，退化为仅含 DA
POMO (Baseline, w/o All)	8.465 (+1.32%)	12.504 (-0.16%)	原始 POMO 骨干，无任何 DiCon 模块
RELD_DA (仅引入 DA)	8.403 (+0.59%)	12.456 (-0.54%)	RELD 骨干仅增加差分注意力
RELD_double (等参对照组)	8.405 (+0.62%)	12.458 (-0.53%)	增加三层 MLP 适配器对齐参数量，性能不及 DA

关键发现¶

差分注意力的决定性降噪价值：从消融数据可见，单独引入 DA 机制即可带来显著的性能跃升（POMO 从 8.465 提升至 8.431，RELD 从 8.406 提升至 8.403）。解码器输出熵分析（Appendix O）表明，MHDA 在所有解码步上的熵值比传统 MHA 稳定降低 0.001–0.005，证明差分抑制有效排除了劣质动作干扰。
任务内对比学习在复杂非点几何中的放大效应：随着非点任务（线与面）比例从 0% 上升至 100%（Table 8），DiCon 相对基线的提升幅度单调扩大。在包含大量出入口的场景下，任务内对比学习通过强制聚集同一任务的候选嵌入，显著抑制了潜在子空间的表示漂移。
参数开销与结构有效性：DA 机制仅为解码器增加约 4.9 万参数（全模型参数仅增加 3.5%）。而通过 MLP 强行对齐参数量的 RELD_double 变体在所有场景下均逊于 RELD_DA，证明收益来源于注意力的差分抑制机制而非单纯扩充模型容量。

亮点与洞察¶

解码器注意力差分抑制机制：利用两路注意力图的差值 $(A_m^1 - \lambda_m A_m^2)$ 消除底噪注意力，优雅地解决了组合优化中“合法动作繁多但有效转移极少”的决策稀释难题。
双层对称性对比驱动的几何表征：将全局刚体变换不变性与局域语义等效聚类相结合，无需人工设计复杂的几何规则即让模型自发习得点、线、面的拓扑共性与内在约束。
跨问题与真实工业场景的即插即用迁移性：无需重新设计主干结构，DiCon 可直接推广至广义旅行商问题（GTSP）、距离电量约束巡检场景（DCCGRP），并在杭州真实城市水网/路网多任务巡检和嘉兴 500kV 变电站高压线塔巡检中展现出超越传统运筹工具的落地实力。

局限与展望¶

单智能体与无强时空约束假设：当前 CGRP 设定限定于单一机器人且未考虑时间窗（Time Windows）、负载容量上限（Capacities）等强业务约束。
区域任务扫描模式预定：当前区域覆盖成本基于固定的长边锯齿状扫描估算，尚未将区域内连续扫描形态与全局巡回做联合端到端策略生成。
未来改进方向：可将 DiCon 扩展为分层多智能体协同架构（Hierarchical / Decentralized Multi-Agent RL），并结合动态掩码处理电量与时间窗等复杂物理约束。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性提出并形式化多几何混合的 CGRP 规划问题，巧妙将差分注意力与双层对比学习引入神经组合优化。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖同分布、大尺度跨度（至1000规模）、极端混合配比、GTSP迁移、两处真实工业数据以及多维度消融。
写作质量: ⭐⭐⭐⭐⭐ 数学形式化严谨，架构设计动机条理明晰，图表详实且消融实验对齐严格。
价值: ⭐⭐⭐⭐⭐ 为现实中普遍存在但长期被学术界割裂的无人机/机器人异构巡检提供了一站式的统一解决范式。