Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces two learned heuristics, a CNN and a GATv2 network trained with DQN, to optimize agent deployment corners within the CADENCE algorithm for the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP). These heuristics aim to improve efficiency by selecting optimal deployment locations while preserving CADENCE's formal coverage and connectivity guarantees. Empirical results across 7,500 runs demonstrate significant improvements in coverage speed and agent utilization compared to baseline CADENCE and ISDA, particularly in larger environments.
Learned corner selection for cooperative guards dramatically boosts deployment efficiency and agent utilization in partially observable environments, outperforming established methods without sacrificing formal guarantees.
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.