Connectivity Preservation and Graph Stretching in Range-Only Swarm Dispersion

Ariel Barel

cs.MASep 23, 2026

Connectivity Preservation and Graph Stretching in Range-Only Swarm Dispersion

Authors: Ariel Barel

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.

Explore similar work

Jun 28, 2026cs.RO

SPACE: Swarm Pheromone Fields for Adaptive Collision-Aware Exploration

Massive robot swarms can explore unknown environments quickly, but adding robots eventually stops helping. Doorways and dense traffic create congestion, increasing inter-robot contacts and reducing the value of each additional robot. We study this safety-efficiency tradeoff for ground swarms of tens to hundreds of robots. We present SPACE, Swarm Pheromone Fields for Adaptive Collision-Aware Exploration. Inspired by ant foraging, SPACE maintains a shared environmental field with an attractive frontier pheromone, a repellent explore pheromone, and a fast robot-density field. Coordination is decentralized and mediated through this field. We evaluate SPACE on real building floorplans, namely sixteen home layouts from the HouseExpo dataset and eight campus floors from the KTH dataset, with swarms of up to two hundred and fifty-six robots. SPACE lies on the empirical Pareto frontier. It attains the lowest inter-robot contact rate at every congested swarm size, four to seventeen times fewer than a greedy nearest-frontier planner, while keeping coverage time within about two percent of that near time-optimal planner. The results indicate that, at this scale, coordination mainly improves safety rather than coverage time.

Haohua Que, Haojia Gao, Mingkai Liu +3

Swarms Collision-Free Trajectories Rotational Repulsion Mechanism

Ask PDF

Jul 5, 2026math.OC

Anytime Plug-and-Play Control with Contract-Based Distributed MPC

A central challenge in many mobile multi-robot applications is that communication topologies are inherently time-varying. Agents may enter or exit the network and such changes cannot generally be restricted a priori. This work introduces a distributed multi-agent control algorithm based on local communication that supports anytime agent joining and leaving the communication network without centralized coordination. The method scales efficiently with the number of agents by relying on a distance-based neighbor definition and on contracts derived from predicted trajectories. The resulting contract constraints guarantee collision avoidance and constraint satisfaction. We validate the proposed method in an autonomous multi-agent driving scenario, demonstrating effective collision avoidance in high-speed, dynamic environments with agents moving in opposite directions, in both simulated and real-world experiments.

Sabrina Bodmer, Danilo Saccani, Melanie N. Zeilinger +1

Multi-Robot Systems Collision Avoidance Model Predictive Control

Ask PDF

Sep 1, 2026cs.RO

Connectivity-Aware Graph Extension for Decentralized Multi-Robot Exploration

Exploring unknown environments with multiple UAVs requires coordination under intermittent communication, making decentralized operation a baseline assumption. We propose, within a decentralized framework, a novel exploration graph extension strategy based on frontier connectivity to extend exploration plans and maintain area partitioning among agents stable and robust to disconnections and changes in spatial layout. The proposed extension method is applied to two state-of-the-art area partitioning methods and evaluated in simulation. Experiments show improved performance over existing graph extension approaches with higher exploration efficiency under low communication rate.

Béatrice Garcia Cegarra, Elena Vanneaux, Quentin Picard +1

Multi-Uav Systems Multi-Robot Systems Uncrewed Aerial Vehicles Decentralization Unknown Environments Complex Networks

Ask PDF