On Learning Optimal Corners in Orthogonal Partially Observable Cooperative Guard Art Galleries

Yassin Ben Mansour; Edwin Meriaux

cs.MAOct 5, 2026

On Learning Optimal Corners in Orthogonal Partially Observable Cooperative Guard Art Galleries

Authors: Yassin Ben Mansour, Edwin Meriaux

Abstract

The CADENCE algorithm solves the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) with formal coverage and connectivity guarantees, but leaves unspecified which valid corner each agent should be deployed to, a choice that strongly affects efficiency. We introduce two learned corner-selection heuristics that preserve these guarantees: a CNN scoring candidates on a grid encoding, and a GATv2 network trained with Deep Q-Learning (DQN) on a visibility graph. Across 7,500 runs on random orthogonal environments (50x50 to 250x250), our heuristics outperform baseline CADENCE in both steps to full coverage and peak agent count, with gains growing with scale, and improve on Incremental Self-Deployment (ISDA) baselines in agent utilization while providing guarantees ISDA lacks. Learned corner selection thus improves CADENCE in speed and agent utilization at no cost to its formal properties.

Figures & tables

Fig. 1: Agent Deployment in CADENCE, previous agent (red color), new agent deployed in a valid corner (yellow color)

Fig. 2: CNN-based corner selection, agent (red color), valid corners (orange color), new agent(green color), predicted discovered area(yellow color)

Fig. 3: GATv2-based scoring of a candidate valid corner.

CADENCE
	$50^{2}$						$100^{2}$						$250^{2}$
Method	Final	$\sigma$	Max	$\sigma$	Steps	$\sigma$	Final	$\sigma$	Max	$\sigma$	Steps	$\sigma$	Final	$\sigma$	Max	$\sigma$	Steps	$\sigma$
rand_point	$\mathbf{13.1}$	$3.2$	$22.2$	$3.0$	$1488$	$412$	$\mathbf{25.7}$	$3.6$	$42.3$	$4.3$	$8320$	$1345$	$\mathbf{44.6}$	$6.3$	$74.2$	$6.9$	$51434$	$6576$
CNN	$14.7$	$3.1$	$17.0$	$3.5$	$751$	$317$	$28.2$	$3.5$	$34.7$	$4.4$	$3552$	$1092$	$48.8$	$6.2$	$61.2$	$7.4$	$17191$	$3765$
DQN	$14.2$	$3.1$	$16.6$	$3.2$	$816$	$295$	$27.3$	$3.5$	$\mathbf{31.2}$	$3.5$	$3689$	$937$	$47.2$	$6.1$	$\mathbf{53.2}$	$6.3$	$19000$	$3636$
Baseline

TABLE I: Mean final nb. of agents (Final), maximal nb. of agents (Max), and total nb. of steps (Steps) over random orthogonal worlds (lower is better; bests per column in bold). Dashes indicate less than 80% of the runs finished within the step budget for

100^{2}

, and 0% of the runs finished in under 24 hours for

250^{2}

. [ 8 ]

Explore similar work

Learning to Place Guards by Reinforcement: A Geo-Free Neural Policy for the Vertex-Guard Art Gallery Problem
Jun 19, 2026Domagoj Ševerdija, Jurica Maltar, Nathan Chappel +1Neural Combinatorial Optimization Neural Policies
School of Applied Mathematics and Informatics, University J. J. Strossmayer of Osijek, Croatia
COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space
May 20, 2026Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed +4Vehicle Routing Problem Multi-Agent Path Finding
Huawei Technologies Canada, 4321 Still Creek Dr, Burnaby, BC, Canada V5C 6S7 · Huawei Technologies, China
Coordination Graphs for Constrained Multi-Agent Reinforcement Learning
Jun 1, 2026Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders JonssonMulti-Agent Reinforcement Learning Coordination
Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain

Jun 19, 2026, cs.LGJ/K move · Enter open · S save

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

Domagoj Ševerdija, Jurica Maltar, Nathan Chappel, Domagoj Matijević

School of Applied Mathematics and Informatics, University J. J. Strossmayer of Osijek, Croatia

Neural Combinatorial Optimization Neural Policies Geometry-Aware

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning