Learning to Solve Compositional Geometry Routing Problems

📄 arXiv: 2605.18094v1 📥 PDF

作者: Mingfeng Fan, Jianan Zhou, Jiaqi Cheng, Yifeng Zhang, Jie Zhang, Guillaume Adrien Sartoretti

分类: cs.AI

发布日期: 2026-05-18

备注: 27 pages, 10 figures

💡 一句话要点

提出DiCon，解决组合几何路由问题中的复杂表征与决策挑战。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 组合几何路由 差分注意力 对比学习 表征学习 路由算法

📋 核心要点

  1. 传统路由方法难以处理CGRP中非点任务带来的不对称性、耦合路径和庞大动作空间。
  2. DiCon通过差分注意力抑制非优选项，并利用双层对比学习增强表征的鲁棒性和几何感知能力。
  3. 实验表明，DiCon在不同CGRP实例中表现出强大的性能、通用性和泛化能力。

📝 摘要（中文）

本文研究了组合几何路由问题（CGRP），它是传统路由问题的一个统一超类，涵盖了点、线、面以及任意混合任务几何形状，为实际路由场景提供了广泛的抽象。与标准基于点的路由不同，具有非点任务的CGRP本质上可能是不对称的，旅行路线与内在路径紧密耦合，并因大量可行但通常不相关的选项而扩大了行动空间，从而对表征学习和决策提出了重大挑战。为了应对这些挑战，我们提出DiCon，一种具有对比学习的差分注意力辅助求解器，作为一个即插即用框架，从两个互补的角度解决问题。首先，我们引入了一种差分注意力机制，主动抑制不太有竞争力的候选动作的概率质量。其次，我们设计了一个双层对比学习目标，以促进鲁棒的全局实例表示并规范几何感知的任务表示。大量实验表明，DiCon在具有不同组成的各种CGRP实例中实现了强大的性能、广泛的通用性和卓越的泛化能力。

🔬 方法详解

问题定义：论文旨在解决组合几何路由问题（CGRP），该问题涵盖了点、线、面等多种几何形状的任务，是对传统点路由问题的扩展。现有方法在处理CGRP时，面临着任务几何形状带来的不对称性、路径耦合以及巨大的动作空间等挑战，导致表征学习和决策困难。

核心思路：论文的核心思路是通过差分注意力机制和双层对比学习，提升模型在复杂CGRP场景下的表征能力和决策能力。差分注意力机制用于抑制不相关的候选动作，从而减少搜索空间；双层对比学习则用于学习鲁棒的全局实例表示和几何感知的任务表示，从而提升模型的泛化能力。

技术框架：DiCon框架主要包含两个核心模块：差分注意力模块和双层对比学习模块。差分注意力模块通过计算每个候选动作的注意力权重，并抑制权重较低的动作，从而减少搜索空间。双层对比学习模块则通过对比学习的方式，学习全局实例表示和几何感知的任务表示。整个框架可以作为一个即插即用的模块，嵌入到现有的路由算法中。

关键创新：论文的关键创新在于提出了差分注意力机制和双层对比学习方法，用于解决CGRP中的复杂表征和决策问题。差分注意力机制能够有效地减少搜索空间，提高决策效率；双层对比学习则能够学习到更鲁棒和具有几何感知能力的表征，从而提升模型的泛化能力。与现有方法相比，DiCon能够更好地处理CGRP中的不对称性、路径耦合以及巨大的动作空间等挑战。

关键设计：差分注意力机制通过一个神经网络来计算每个候选动作的注意力权重，该网络的输入包括当前状态、任务几何形状以及候选动作。双层对比学习模块包含实例级别的对比学习和任务级别的对比学习。实例级别的对比学习旨在学习鲁棒的全局实例表示，任务级别的对比学习旨在学习几何感知的任务表示。损失函数由两部分组成：差分注意力损失和对比学习损失。差分注意力损失用于鼓励模型抑制不相关的候选动作，对比学习损失用于鼓励模型学习鲁棒和具有几何感知能力的表征。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，DiCon在各种CGRP实例中实现了强大的性能、广泛的通用性和卓越的泛化能力。与现有基线方法相比，DiCon在不同组成的CGRP实例上均取得了显著的性能提升，证明了其在处理复杂几何路由问题方面的有效性。具体性能数据未知，但摘要强调了“strong performance, broad versatility, and superior generalization”。

🎯 应用场景

该研究成果可应用于各种实际路由场景，例如物流配送、机器人导航、交通规划等。特别是在涉及复杂几何形状任务的场景中，例如无人机巡检、城市管网维护等，DiCon能够提供更高效、更可靠的路由解决方案。未来，该方法有望进一步扩展到其他组合优化问题，例如车辆路径问题、旅行商问题等。

📄 摘要（原文）

We study the Compositional Geometry Routing Problem (CGRP), a unified superclass of traditional routing problems that covers point-only, line-only, area-only, and arbitrary hybrid task geometries, providing a broad abstraction for real-world routing scenarios. Beyond standard point-based routing, CGRP with non-point tasks can be inherently asymmetric, tightly coupled travel routes with the intrinsic path, and enlarges the action space with numerous feasible yet often irrelevant options, thereby posing significant challenges for both representation learning and decision-making. To address these challenges, we propose DiCon, a differential attention-assisted solver with contrastive learning, as a plug-and-play framework that tackles the problem from two complementary angles. First, we introduce a differential attention mechanism that actively suppresses the probability mass on less competitive candidate actions. Second, we design a double-level contrastive learning objective to promote robust global instance representations and regularize geometry-aware task representations. Extensive experiments demonstrate that DiCon achieves strong performance, broad versatility, and superior generalization across diverse CGRP instances with different compositions.