On the Control of Mobile Ad-Hoc Agent Deployments in Partially Observed Space

Edwin Meriaux; Louis-Roy Langevin; Shuo Wen; Ndiamé Ndiaye; Gregory Dudek; Antonio Loría

cs.ROSep 19, 2026

On the Control of Mobile Ad-Hoc Agent Deployments in Partially Observed Space

Authors: Edwin Meriaux, Louis-Roy Langevin, Shuo Wen, Ndiamé Ndiaye, Gregory Dudek, Antonio Loría

Organizations: Computer Science Department and Mila, McGill University, Montreal, Canada · L2S, CNRS–CentraleSupélec, Université Paris-Saclay, Gif-sur-Yvette, France · Department of Mathematics and Statistics, McGill University, Montreal, Canada

Abstract

We study the online deployment of mobile ad hoc networks in unknown orthogonal environments, formalized as the Partially Observable Cooperative Guard Art Gallery Problem. We give a full proof that CADENCE algorithms achieve full coverage while maintaining a connected visibility graph using at most $n/2 + h - 2$ agents in orthogonal worlds with $n$ corners and $h$ holes. We further evaluate deployment-order heuristics that reduce agent count and deployment time in practice.

Figures & tables

Panel of Figure 1 — Figure 1: Sample agent placements (red) under CADENCE in orthogonal worlds.

Panel of Figure 2 — Figure 2: A maximal rectangle $R$ containing $z$ and its boundary regions.

Panel of Figure 3 — Figure 3: Impossible configurations for $S\subseteq R_{4}$ with endpoints $m$ , $m^{\prime}$ in Lemma 2 .

Panel of Figure 4 — Figure 4: (a) Case 3 showing why a valid $270^{\circ}$ corner $y$ on $\partial R$ must exist. (b) Theorem 2: splitting $W$ along $\ell$ .

CADENCE
	$50^{2}$						$100^{2}$
Method	Final	$\sigma$	Max	$\sigma$	Steps	$\sigma$	Final	$\sigma$	Max	$\sigma$	Steps	$\sigma$
least_edge	$13.4$	$3.1$	$20.0$	$3.1$	$1218$	$337$	$26.5$	$3.5$	$38.9$	$4.1$	$6168$	$1037$
rand_point	$13.1$	$3.2$	$22.2$	$3.0$	$1488$	$412$	$25.7$	$3.6$	$42.3$	$4.3$	$8320$	$1345$
max_dist	$13.0$	$3.1$	$21.9$	$3.9$	$1202$	$411$	$25.6$	$3.5$	$41.1$	$5.0$	$6133$	$1658$
most_edge	$\mathbf{13.0}$	$3.1$	$21.1$	$3.3$	$1558$	$467$	$\mathbf{25.3}$	$3.5$	$40.3$	$3.9$	$8609$	$1582$

Table 1: Mean final nb. of agents (Final), maximal nb. of agents (Max), and total nb. of steps (Steps) over random orthogonal worlds (lower is better; best per column in bold). N/A indicating 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}

Multi-Agent Coordination

Multi-agent coordination studies how autonomous agents align actions, share information, and divide work to achieve individual or collective goals.

See all 520 papers

On Learning Optimal Corners in Orthogonal Partially Observable Cooperative Guard Art Galleries
Oct 5, 2026Yassin Ben Mansour, Edwin MeriauxCoverage Path Planning Multi-Agent Planning
UFR Sciences Universit´e Paris-Saclay Orsay, France · L2S, Centralesup´elec Universit´e Paris-Saclay Gif-sur-Yvette, France
Optimal Path Planning in Hostile Environments
Mar 19, 2026Andrzej Kaczmarczyk, Šimon Schierreich, Nicholas Axel Tanujaya +1Multi-Agent Path Finding Graph-Based Planning
Czech Technical University in Prague · AGH University of Krakow · Bina Nusantara University +1
Scalable Multi-Agent Maze Traversal with Local Communication
Aug 12, 2026Julian Rau, Jahir Argote-Gerald, Grace McFassel +3Multi-Agent Coordination Multi-Robot Exploration
Department of Computer Science, Technical University of Darmstadt, Germany · School of Electrical and Electronic Engineering, The University of Sheffield, UK · Bristol Robotics Laboratory, University of Bristol, Bristol, UK

Oct 5, 2026J/K move · Enter open · S save

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

Yassin Ben Mansour, Edwin Meriaux

UFR Sciences Universit´e Paris-Saclay Orsay, France · L2S, Centralesup´elec Universit´e Paris-Saclay Gif-sur-Yvette, France

Coverage Path Planning Multi-Agent Planning

Open paper AskPDF arXiv

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.

Abstract

Multi-Agent Coordination

Explore similar work

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

Optimal Path Planning in Hostile Environments

Scalable Multi-Agent Maze Traversal with Local Communication