This paper extends an existing framework for the coordination of mobile agents in unknown worlds, by considering the possibility of dynamic instability. In the original problem, known as the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) (arXiv:2512.09495), the multi-agent system must establish a communication network which completely covers an initially unknown constrained space. However, the POCGAGP fails to account for the unpredictability often seen in real-world deployment. To address this, the dynamic case (DPOCGAGP) introduces two settings which can influence the mobile network during deployment: Agent Loss and World Change, which represent dynamic changes to the world. Within this study, we present advancements to two state-of-the-art algorithms, the Centralized Agent-Directed Exploration for Network Coverage (CADENCE), and its decentralized analogue, DADENCE, to provide solutions in these cases. We then compare their performance against another state-of-the-art benchmark algorithm, and show that the adapted algorithms outperform across our benchmark test set, which comprises over 4500 test cases of varied size and structure.
Figures & tables
Fig. 1 : Robots attempting to form a MANET in a partially observed indoor environment with collapsed wall sections and a failed agent.
Fig. 2 : Illustration of a polygon W with all invalid reflexive corners in green and valid corners in red.
Fig. 3 : Graph-based representation of a disconnected MANET due to agent attrition.
Fig. 4 : Example 2D dungeon map after 2 successive mutations.
Fig. 5 : Steady State Coverage before (left) and after (middle, right) world mutation event.
Fig. 6 : Graph-based representation of an example of network fragmentation and subnetwork independence.
Fig. 7 : Comparison of agent use and map coverage for an example 30×30 world with a 10% agent loss at step 400: (a) active agents over time; (b) map coverage (%) over time.
Fig. 8 : Example quadtree decomposition and world complexity bin distributions for 100 worlds
Fig. 9 : Performance metrics for 500 world seed tests with 5 stochastic 10% agent loss events against complexity: (a) Max Agent Use; (b) Final Agent Count; (c) Final Step Count.
Fig. 10 : Performance metrics for 500 world seed tests with 5 stochastic world changes against complexity: (a) Max Agent Use; (b) Final Agent Count; (c) Final Step Count.
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.
Edwin Meriaux, Louis-Roy Langevin, Shuo Wen +3
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
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
This paper presents a systematic study of pathfinding algorithms in the context of Dynamic Multi-Agent Pathfinding (D-MAPF), a setting that combines dynamic obstacles, partial observability, and inter-agent conflicts. We evaluate six representative algorithms: Dijkstra, D* Lite, Space-Time A*, WHCA*, M*, and a novel method denoted as A** within a unified simulation framework. The proposed A** algorithm introduces a template-based approach that decouples offline geometric path generation from online temporal adaptation. By precomputing multiple diverse candidate paths and dynamically reconnecting to them using space-time planning, A** improves solution quality in environments with frequent changes and limited sensing
Gabriel Fejziaj, Salama Hassona, Wieslaw Marszalek
Department of Computer Science, Opole University of Technology, Opole, 45-758, Poland.