Can Learned Corner Selection Improve Guard Art Gallery Deployment Without Losing Guarantees?

The paper changes only which valid corner gets picked

CADENCE solves the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) with formal coverage and connectivity guarantees, but it leaves one decision open: which valid corner each agent should be deployed to. That choice strongly affects efficiency. This paper does not modify the POCGAGP formulation or CADENCE's connectivity machinery; it targets only the unspecified selection inside CADENCE's loop.

The practical consequence is that a mis-scored candidate costs efficiency, not correctness. CADENCE terminates with full coverage regardless of which valid corner is chosen, so learning supplies only the ordering over candidates while the search keeps its correctness conditions. The learned selectors fully retain CADENCE's worst-case agent bound of n/2 + h − 2 and its theoretical coverage guarantees.

A CNN scores grids while a GATv2 scores visibility graphs

The first heuristic is a CNN that scores candidate corners on a grid encoding. An orthogonal environment discretizes onto a grid without distortion, and the quantities determining a corner's value are local spatial patterns: unseen area beyond it, surrounding wall orientation, and frontier position. The paper notes the limitation of this choice: visibility is not spatially local, since a corner can reveal a cell far along a sightline while being blind to its immediate neighbour behind a wall, so convolution must be deep enough to span sightlines and must additionally learn occlusion logic the geometry already provides.

The second heuristic is a GATv2 network trained with Deep Q-Learning on a visibility graph. Here edges encode sightlines rather than spatial adjacency, so a single message-passing step propagates coverage information along line-of-sight paths. The Q-network uses four GATv2Conv layers, each followed by layer normalization and an ELU activation, with a residual connection between the first two layers; node embeddings feed an Advantage head applied per node and a Value head applied to a global mean-pooled graph embedding. Because the advantage stream emits one scalar per node rather than a fixed-width vector, the same weights apply to environments of any size.

Each node carries ten normalized features: a one-hot encoding of node type (unexplored, free seen space, wall adjacent to seen area, frontier, agent, deployment point), x and y coordinates divided by the grid extent, a flag marking valid corners, and travel distance from the deployment point. The CNN is trained on precomputed before/after pairs, whereas the GAT is trained directly on CADENCE rollouts by Deep Q-Learning, using the number of newly discovered nodes in each episode as the reward signal, over 100 worlds trained eight times each.

7,500 runs across three grid sizes

Evaluation compared the CNN- and DQN-based corner selection methods to CADENCE with random corner selection and two ISDA variants (ISDA edge and ISDA any) across random orthogonal worlds of grid sizes 50², 100², and 250². For each algorithm, 300 worlds were tested, each one five times: 1,500 tests per algorithm and 7,500 total.

Three metrics were measured, and they answer different questions: the mean final number of agents, the maximal number of agents during execution, and the total number of steps taken. Lower values indicate better performance on all three. Keeping these separate matters because, as the paper's discussion states, no method dominates and each metric has a different winner.

Step savings over random selection grow with map size

On small maps of 50², CADENCE CNN and CADENCE DQN achieved full coverage in 751 and 816 steps respectively, outperforming CADENCE rand point at 1,488 steps while remaining competitive with ISDA edge at 573 steps. On larger worlds the gap widens: in 250² environments the CNN and DQN took 17,191 and 19,000 steps respectively, compared to 51,434 for CADENCE rand point.

Relative to random corner selection, both methods roughly halve completion time at 50², and the advantage grows with scale, saving up to 67% (CNN) and 63% (DQN) of steps on 250² maps. The paper attributes this to the learned policies being trained to maximize newly revealed area, which concentrates their benefit on the transient cost of deployment rather than on the size of the terminal configuration.

DQN suppresses peak agents while final agent counts rise slightly

CADENCE DQN consistently achieved the lowest peak agent expansion across medium and large environments, recording the lowest maximum agent counts on 100² (31.2) and 250² (53.2), outperforming both rand point (74.2) and ISDA edge (63.1). On 250² maps that is a 28.3% reduction in peak agent count compared to rand point.

The trade-off appears in the final agent count. Rand point maintained slightly lower final agent counts (44.6 versus 47.2 for DQN and 48.8 for CNN on 250²). Both learning-based CADENCE variants pay for their speed and peak-agent gains with a modest increase in final agents of 6–12%, a gap the paper reports as remaining within one within-column standard deviation at every size. Both still outperformed ISDA variants in final agent minimization, and both remained resilient to the state-space explosion that caused ISDA any to time out or exceed the step budget on larger maps.

ISDA edge stays faster but carries no formal safety certificate

ISDA edge remains the fastest method at every size, and its advantage in steps widens from +31% to +49% as worlds grow. However, DQN beats ISDA edge in peak agent count throughout, at 100² (31.2 versus 33.6) and 250² (53.2 versus 63.1). At 250², DQN and CNN also achieve lower final agent counts (47.2 and 48.8 respectively) than ISDA edge (62.9), representing a 22.4% and 24.9% reduction.

The structural difference is the guarantee. The learned selectors merely reorder corner evaluations within CADENCE without modifying its core deployment logic, so they retain CADENCE's worst-case agent bound and theoretical coverage guarantees. ISDA lacks formal safety certificates, which the paper links to catastrophic failure where ISDA any timed out on all 250² runs. The paper frames the learned selectors' contribution as repositioning CADENCE along its speed–resource trade-off curve rather than as a simple leaderboard victory.

The evidence covers random orthogonal worlds up to 250²

All reported results come from random orthogonal environments of 50², 100², and 250², with 300 worlds per algorithm and five repetitions each. The guarantees the learned selectors preserve are CADENCE's coverage and connectivity guarantees, which the paper connects to the requirements of MANETs. The comparison set is CADENCE with random corner selection plus ISDA edge and ISDA any; no other selection policies were tested.

Two reporting boundaries matter for reading the table. Dashes indicate that fewer than 80% of runs finished within the step budget for 100², and that 0% of runs finished in under 24 hours for 250². The paper's own summary is that CNN and DQN are slower than ISDA in steps but match or exceed it in agent utilization while maintaining the formal coverage and connectivity guarantees.

Choose learned selection for peak concurrency, not raw speed

The decision this paper supports is not "learned selection is better" but which cost you are willing to pay. If the binding constraint is total steps to full coverage, ISDA edge wins at every tested size and its margin widens with scale. If the binding constraint is peak concurrent agents while keeping formal coverage and connectivity guarantees, DQN is the strongest option in this evidence, posting the lowest maximum agent counts at 100² (31.2) and 250² (53.2) and beating ISDA edge at both sizes.

The cost of that choice is a 6–12% increase in final agents relative to random selection, a gap the paper reports as within one within-column standard deviation at every size. So the learned selectors are best read as a way to shift CADENCE toward lower transient deployment cost, not as a way to shrink the terminal configuration or to outrun ISDA on time.

Guarantees are preserved, but the learned policies are not certified

The preserved guarantees belong to CADENCE, not to the learned models. Because the selectors only choose among valid corners, CADENCE still terminates with full coverage and still respects its worst-case agent bound; the learned component itself carries no separate correctness certificate, and a mis-scored candidate costs efficiency rather than coverage.

The evidence is also bounded by its test distribution: random orthogonal worlds at three grid sizes, with training on 100 worlds for the GAT. The paper does not report results for non-orthogonal polygons, for grid sizes beyond 250², or for selection policies outside the compared set, so the reported step savings and peak-agent reductions should be read within those conditions.

Sources used in this answer