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
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
Figure 1: Sample agent placements (red) under CADENCE in orthogonal worlds.
Figure 2: A maximal rectangle R containing z and its boundary regions.
Figure 3: Impossible configurations for S⊆R4 with endpoints m , m′ in Lemma 2 .
Figure 4: (a) Case 3 showing why a valid 270∘ corner y on ∂R must exist. (b) Theorem 2: splitting W along ℓ .
502
1002
Method
Final
σ
Max
σ
Steps
σ
Final
σ
Max
σ
Steps
σ
CADENCE
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
13.0
3.1
21.1
3.3
1558
467
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 1002 , and 0% of the runs finished in under 24 hours for 2502 .
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.
Yassin Ben Mansour, Edwin Meriaux
UFR Sciences Universit´e Paris-Saclay Orsay, France · L2S, Centralesup´elec Universit´e Paris-Saclay Gif-sur-Yvette, France
Coordinating agents through hazardous environments, such as aid-delivering drones navigating conflict zones or field robots traversing deployment areas filled with obstacles, poses fundamental planning challenges. We introduce and analyze the computational complexity of a new multi-agent path planning problem that captures this setting. A group of identical agents begins at a common start location and must navigate a graph-based environment to reach a common target. The graph contains hazards that eliminate agents upon contact but then enter a known cooldown period before reactivating. In this discrete-time, fully-observable, deterministic setting, the planning task is to compute a movement schedule that maximizes the number of agents reaching the target. We first prove that, despite the exponentially large space of feasible plans, optimal plans require only polynomially-many steps, establishing membership in NP. We then show that the problem is NP-hard even when the environment graph is a tree. On the positive side, we present a polynomial-time algorithm for graphs consisting of vertex-disjoint paths from start to target. Our results establish a rich computational landscape for this problem, identifying both intractable and tractable fragments.
Andrzej Kaczmarczyk, Šimon Schierreich, Nicholas Axel Tanujaya +1
Czech Technical University in Prague · AGH University of Krakow · Bina Nusantara University +1
Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to 625 agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a naïve baseline in which all agents independently execute the single-agent solver.
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