CS Paper Radar

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.RO ·submitted 2026-09-19 14:47 UTC · v1

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.

Comment
Paper accept at Algowin2026

Closest papers

Nearest neighbours by meaning across the whole index.

Adaptive Coverage Algorithms for Mobile Ad Hoc Networks in Dynamic Worlds

cs.RO cs.MA ·2026-10-30 ·Hugo Gandhi, Edwin Meriaux, Antonio Loría
publishedbenchmark similarity 0.77
Abstract · 8 pages, 10 figures. Accepted to the 2026 IEEE MIT Undergraduate Research Technology Conference (URTC)

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.

0.28

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

cs.MA cs.LGcs.RO ·2026-10-05 ·Yassin Ben Mansour, Edwin Meriaux
similarity 0.65
Abstract

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.

0.21

Agents in the Scene: An Agentic Framework for Resource-Efficient Site-Specific Base Station Deployment

eess.SY ·2026-09-16 ·Zihao Zhou, Zhaolin Wang, Yuanwei Liu
similarity 0.58
Abstract

An agentic framework is proposed for autonomous site-specific base station (BS) deployment in wireless network planning. In contrast to conventional approaches that rely on manual site surveys or extensive ray-tracing (RT) simulations with significant human intervention, the proposed framework autonomously explores and optimizes BS deployment under a limited RT evaluation budget, enabling resource-efficient network planning. To this end, a continuous, geometry-grounded deployment action space is first constructed from three-dimensional (3D) wireless digital twins. Within this action space, an agent team operates through a stateful perception--reasoning--reflection loop. Specifically, a Placement Agent first generates candidate BS deployments in two complementary modes: an experience-guided mode that refines promising solutions, and an exploration mode that avoids getting stuck in local optima. After the candidate deployments are evaluated through RT, a Reflection Agent interprets the RT results together with the scene geometry, identifies performance-limiting factors such as blockage, overlapping coverage, and uncovered areas, and converts these diagnoses into guidance for subsequent deployment. Through this iterative process, site-specific experience is accumulated and deployment plans are optimized without human intervention. Numerical results in two realistic urban scenarios show that: 1) the proposed approach substantially outperforms heuristic, learning-based, and large language model (LLM)-assisted methods; 2) it achieves highly competitive coverage against the optimal solution while requiring substantially fewer transmitter-level RT evaluations; 3) site-specific reflection effectively turns raw RT feedback into refinement guidance, whereas the dual-mode mechanism preserves diversity and facilitates escape from local optima.

0.47

Universal Rendezvous of Anonymous Agents with Footprints

cs.DC ·2026-08-10 ·Bibhuti Das
similarity 0.54
Abstract

Deterministic rendezvous for two anonymous mobile agents starting simultaneously from two distinct nodes of an anonymous connected graph and navigating synchronously in the graph requires that they meet at some node. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are the initial positions of the agents. Such an instance is said to be feasible if there is a deterministic algorithm guaranteeing rendezvous, possibly valid only for this instance. A rendezvous algorithm is said to be universal for a class of instances if it guarantees rendezvous for all feasible instances from this class. We consider the model with footprints: whenever an agent visits an unmarked node, it leaves a permanent footprint on it, and all footprints are identical. This paper aims at answering the open problem from the paper by Das and Pelc (SPAA 2026), asking whether there exists a universal rendezvous algorithm for the class of all instances in the model with footprints. We propose a universal rendezvous algorithm for the class of all instances where the underlying graph is connected (finite or countably infinite) in the model with footprints. This shows the existence of a universal algorithm for the class of all instances in the model with footprints, which is an affirmative answer to the open problem.

0.04

Beyond the Boundary: Optimal Grid Dispersion by Spread, Reverse, and Collect

cs.DC ·2026-10-12 ·Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, Subhajit Pramanick
theory similarity 0.53
Abstract

\emph{Dispersion} requires a set of mobile agents to occupy distinct nodes of a graph such that each node contains at most one agent. We study deterministic dispersion of $k\le n$ agents on an $n$-node oriented square grid, where each node has globally consistent North, East, South, and West port labels, from arbitrary initial configurations. This includes both \emph{rooted} configurations, where all agents are co-located initially, and \emph{general} configurations, where agents are initially distributed arbitrarily across the nodes. On oriented square grids, Kshemkalyani, Molla, and Sharma~\cite{KMS20} gave an $O(\min(k,\Side))$-round algorithm in the local-communication model, where only agents on the same node can exchange information, and an $O(\sqrt{k})$-round algorithm in the global-communication model, where any two agents can communicate regardless of position, both using $O(\log k)$ bits per agent. The bound in the local communication model is optimal when $k=Θ(n)$, but it remains open whether local communication alone can match the $Ω(\sqrt{k})$ time lower bound when $k=o(n)$. We solve this by presenting \textsc{Spread--Reverse--Collect} (SRC), a deterministic algorithm that disperses any $k\le n$ agents in $O(\sqrt{k})$ synchronous rounds using $O(\log k)$ bits of persistent memory per agent, matching both time and memory lower bounds. SRC is based on a geometric primitive, a \sharpS-shaped parallel sweep, together with a simple priority rule. Unlike earlier grid algorithms that gather agents at the boundary and spread out from there, each SRC sweep starts from the agents' current position, and when it reaches the boundary the group simply reflects its sweep back inside and continues. SRC therefore needs no knowledge of the grid size and runs unchanged on an infinite oriented grid.

0.24

Connectivity Preservation and Graph Stretching in Range-Only Swarm Dispersion

cs.MA ·2026-09-23 ·Ariel Barel
theory similarity 0.52
Abstract

We study connectivity-preserving finite-jump dispersion of anonymous, identical, and oblivious agents under an idealized range-only sensing model. Each agent measures only the distances to its visible neighbors, without bearings, identifiers, communication, memory, or a shared coordinate system. We derive the largest isotropic displacement certifiable as safe from these measurements alone. The resulting rule requires only the distance to the farthest visible neighbor: each agent selects a random direction and moves by half of its remaining visibility margin. The rule preserves every existing visibility edge under synchronous finite motion and therefore preserves connectivity. For two agents, we prove positive conditional drift in squared distance, almost-sure convergence to the visibility boundary, and finite expected time to reach any fixed neighborhood of that boundary. A one-million-run Monte Carlo experiment agrees with the exact first-round moments and estimates approximately 9.5 rounds to reach distance 0.97V from coincident initial positions; an independent Bellman-equation computation gives the same estimate. For general swarms, 1,000 runs across five initial-topology classes reproduce the deterministic safety guarantee at implementation level and reveal a consistent topology-dependent ordering of attainable diameter under the tested protocol. These results provide a theoretical foundation for connectivity-preserving multi-robot dispersion under minimal sensing, while isolating the guarantees achievable from anonymous range measurements alone.

0.24

Scalable Multi-Agent Maze Traversal with Local Communication

cs.RO cs.MA ·2026-08-12 ·Julian Rau, Jahir Argote-Gerald, Grace McFassel, Genki Miyauchi, Paul Trodden +1 more
publishedtheory similarity 0.50
Abstract · This manuscript has been accepted for publication in the proceedings of the World Symposium on the Algorithmic Foundations of Robotics (WAFR…

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.

0.16

Mechanism Design for Facility Location Games Under a Prelocated Facility

cs.GT ·2026-08-31 ·Genjie Qin, Qizhi Fang, Wenjing Liu
publishedtheory similarity 0.50
Abstract

We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of $n$ agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents' private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all the agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with $2$-approximation and provide a lower bound of $1.5-ε\textbf{ }(ε>0)$ for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of $n$ for deterministic strategy-proof mechanisms and lower bounds of $1.5$ and $1.0425$ for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof $5/3$-approximation mechanism for the maximum cost and a deterministic strategy-proof $(n-1)$-approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective.

0.39