arXiv:2606.21604cs.LGcs.CG2026-06

用强化学习训练神经模型,不用几何计算就能高效安排守卫。

Learning to Place Guards by Reinforcement: A Geo-Free Neural Policy for the Vertex-Guard Art Gallery Problem

  • 用强化学习直接从顶点坐标生成守卫位置策略。
  • 测试时无需几何计算,仍能覆盖90%以上区域,超出训练范围5倍。
  • 通过探针分析发现模型已内化几何知识,失败源于解码器偏差。

神经组合优化(NCO)表明,通过强化学习训练的策略可直接从原始实例构建难解问题的优质解。然而,该策略实际学到的内容与其解码器表达之间存在差异,尚不明确。本文研究顶点守卫艺术馆问题——在多边形中选择顶点放置守卫以覆盖整个区域,这是NP难问题。采用指针网络策略,在仅依赖顶点坐标、无可见性计算和几何预言机的‘无几何推理’约束下,通过覆盖率感知奖励进行训练。模型虽经济地部署守卫,但测试时仍留下尾部未覆盖多边形,且超出训练范围后恶化。为定位原因,冻结训练好的编码器,用小规模单次分类器读取其嵌入表示,仍保持无几何推理。该分类器显著缩小可行性差距,在分布内及分布外均有效,最多扩展至训练范围的五倍,使未覆盖多边形数量降低约一个数量级,代价为少量额外守卫数。结果表明,强化学习获得的表征已包含可行性所需几何信息,残余失败源于解码器校准而非知识缺失。对冻结编码器的探针分析为评估神经组合求解器内部认知提供了实用方法。

原文摘要 · Abstract (English)

Neural combinatorial optimization (NCO) has shown that policies trained by reinforcement can construct strong solutions to NP-hard problems directly from raw instances. What such a policy actually learns, as opposed to what its decoder expresses, remains much less clear. We study this distinction on the vertex-guard Art Gallery Problem, the NP-hard task of choosing polygon vertices from which to observe an entire region. A pointer-network policy is trained from a coverage-aware reward over its own rollouts under the constraint we call geo-free inference: at test time it sees only vertex coordinates, with no visibility computation and no geometric oracle. The policy places guards economically but leaves a tail of under-covered polygons that widens far beyond the training range. To locate the cause, we freeze the trained encoder and read its embeddings with a small single-shot classifier, still geo-free at inference. The classifier closes most of the feasibility gap, in and out of distribution and at up to roughly five times the training range, cutting under-covered polygons by about an order of magnitude at an explicitly reported cost in guard count. We read this as evidence that the reinforcement-trained representation already encodes the geometry required for feasibility, and that residual failures reflect decoder calibration rather than missing knowledge. Probing a frozen encoder thus offers a practical way to ask what a neural combinatorial solver has internalized.

神经组合优化强化学习艺术馆问题可解释性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。