← 返回论文列表

AAC:基于架构可采纳的ALT可微分地标压缩
AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT

作者: An T. Le, Vien Ngo
arXiv: 2604.20744v1
分类: cs.AI, cs.LG, cs.RO
📝 论文摘要
我们提出**AAC**(架构可容许压缩器),这是一种用于ALT(A*、地标与三角不等式)最短路径启发式的可微分地标选择模块,其输出在构造上具有可容许性:每次前向传播都是三角不等式下界的行随机混合,因此该启发式在**任何**参数设置下均保持可容许性,无需收敛、校准或投影步骤。在部署时,该模块可简化为经典ALT在习得子集上的应用,与神经编码器实现端到端组合,同时保留经典工具链。这一构造是经典启发式搜索中“压缩同时保持可容许性”传统的首个可微分实例。 在匹配的逐顶点内存协议下,我们证明采用最远点采样地标的ALT(FPS-ALT)在度量图上具有可证明的近最优覆盖度,为**任意**选择器留下的提升空间最多仅为几个百分点。AAC的运行效果接近此上限:在9个道路网络上的差距为0.9–3.9个百分点,在合成图上的差距≤1.3个百分点,且在1500多次查询及所有记录运行中均保持零可容许性违反。在匹配内存条件下,AAC在DIMACS道路网络的中位数查询中比FPS-ALT快1.2–1.5倍,其离线成本在170–1924次查询内即可摊销。通过受控消融实验,我们分离出关键约束条件:默认初始化下的训练目标漂移(而非架构容量限制);采用前m个恒等初始化可完全消除扩展次数差距。我们开源了该模块、包含配对双单侧检验等效性与预注册的可复用匹配内存基准测试协议,以及一个参考的压缩差分启发式基线。

📊 核心分析

🎯 研究动机
该论文旨在解决在最短路径启发式搜索中,如何将神经网络与经典算法(如ALT)结合时保持启发式的可采纳性(admissibility)这一关键问题。研究背景是:传统ALT算法依赖人工选择地标(landmarks),而神经网络虽能学习选择地标,但难以保证其输出的启发式始终满足可采纳性约束,这限制了端到端学习的应用。
🔧 核心方法
论文提出了一个名为AAC(Architecturally Admissible Compressor)的可微分(differentiable)地标选择模块。其核心方法是: - 设计一个架构,使其前向传播的输出是三角不等式(triangle inequality)下界的行随机(row-stochastic)混合。 - 这种构造确保了对于任何参数设置,生成的启发式函数天生就是可采纳的(admissible by construction),无需额外的收敛、校准或投影步骤。 - 在部署时,该模块可简化为在学得的地标子集上运行的经典ALT算法,从而与神经编码器(neural encoders)进行端到端组合,同时保留经典工具链。
💡 核心创新
论文的核心创新点在于: - **首个可微分的、保持可采纳性的压缩架构**:这是经典启发式搜索中“压缩同时保持可采纳性”传统的第一个可微分实例。 - **架构保证的可采纳性**:通过巧妙的架构设计,确保所有参数设置下输出的启发式都自动满足可采纳性,从根本上解决了学习与理论保证之间的矛盾。 - **识别并解决了关键训练瓶颈**:通过对照实验(controlled ablation)发现,性能瓶颈并非架构容量,而是默认初始化下的训练目标漂移(objective drift),并提出“前m个恒等初始化(identity-on-first-m initialization)”来完全消除扩展计数(expansion-count)的差距。
🏆 总体贡献
论文对该领域的整体贡献包括: - **理论贡献**:在匹配的每顶点内存协议(matched per-vertex memory protocol)下,证明了采用最远点采样地标(FPS-ALT)的ALT在度量图(metric graphs)上具有接近最优的覆盖率(coverage),为任何选择器设定了性能上限。 - **实践贡献**:AAC模块在实践中性能接近该理论上限,在多个真实和合成图数据集上验证了其有效性和零可采纳性违规。在匹配内存下,其查询速度也优于FPS-ALT。 - **资源贡献**:开源了AAC模块、一个可复用的匹配内存基准测试协议(包含配对双单侧检验(TOST)等价性和预注册(pre-registration)),以及一个参考的压缩差分启发式基线(baseline),为后续研究提供了工具和标准。