math.OCMar 13, 2026

Hybrid topology control: a dynamic leader-based distributed edge-addition and deletion mechanism

Authors: Kunal Garg, Xi Yu

Organizations: School of Engineering for Matter, Transport and Energy, Arizona State University · School of Manufacturing Systems and Networks, Arizona State University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Coordinated operations of multi-robot systems (MRS) require agents to maintain communication connections to accomplish team objectives. However, maintaining the connections imposes costs in terms of restricted robot mobility, resulting in suboptimal team performance. In this work, we consider a realistic MRS framework in which agents are subject to unknown dynamical disturbances and experience communication delays. Most existing works on connectivity maintenance use consensus-based frameworks for graph reconfiguration, where decision-making time scales with the number of nodes and requires multiple rounds of communication, making them ineffective under communication delays. To address this, we propose a novel leader-based decision-making algorithm that uses a central node for efficient real-time reconfiguration, reducing decision-making time to depend on the graph diameter rather than the number of nodes and requiring only one round of information transfer through the network. We propose a novel method for estimating robot locations within the MRS that actively accounts for unknown disturbances and the communication delays. Using these position estimates, the central node selects a set of edges to delete while allowing the formation of new edges, aiming to keep the diameter of the new graph within a threshold. We provide numerous simulation results to showcase the efficacy of the proposed method.

Figures & tables

Fig. 1 : Hybrid topology control framework: the central node decides the edge to be deleted and the edge to be added to the base graph. Once the new graph is formed, a possibly new central node is chosen. The position uncertainties of each node for the central node are shown through dotted circles.
Fig. 2 : Position estimate, denoted as the shaded region, for 1-hop and 2-hop neighbors in the presence of time delays.
Fig. 3 : Simulation results for A: proposed method , B: centralized method with no delays and no diameter limit , C: centralized method with no diameter limits , and D: distributed method with fixed central node with 20 nodes. In each row, the left figure illustrates the final graph after 3000 iterations, and the right figure plots the number of edges in the graph and the number of stressed edges at each time step.
MethodCostTime
Method A2069.30.4s
Method B1572.90.1s
Method C2105.51.4s
Method D2082.90.4s
TABLE I : Cumulative costs and wall-clock time for the proposed and baseline methods averaged over 1000 runs for graphs with ∣V∣=20|\mathcal{V}|=20 and τD=8\tau_{D}=8 .
TABLE II : Wall-clock time comparison for the proposed Method A and the baseline Method B over 100 runs with 100 decisions in each run for varying ∣V∣|\mathcal{V}| and fixed diameter bound of τD=8\tau_{D}=8 .
 τD=5\tau_{D}=5τD=10\tau_{D}=10τD=15\tau_{D}=15
 TimeCostTimeCostTimeCost
Method A5.2s5922.94.2s4107.73.9s3410.9
Method C32.8s6991.457.6s4814.233.9s4314.1
TABLE III : Wall-clock time and cumulative cost comparison for the proposed Method A and the baseline Method C over 10 runs with 100 decisions in each run for varying diameter bound τD\tau_{D} and fixed number for nodes ∣V∣=50|\mathcal{V}|=50 .
More in this topic

Multi-Robot Systems

Multi-robot systems coordinate teams of robots to plan, perceive, communicate, and act together in shared tasks and environments.

See all 205 papers

Explore similar work

CardsList
Jun 1, 2026

Spatio-Temporal Reconnection for Multi-Robot Networks using Adaptive Prescribed-Time CBFs

In multi-robot systems, maintaining persistent communication graph connectivity is often overly restrictive, especially when robots have limited communication ranges but operate in large environments. Instead, allowing robots to temporarily disconnect and later reconnect is often more desirable for efficient task execution while still ensuring timely information sharing across the team. In this paper, we propose an adaptive prescribed-time control barrier function (adaptive PT-CBF) framework that enables robots to temporarily disconnect and re-enter the communication range within an adjustable and feasible prescribed time. Moreover, we introduce a reconnection triggering mechanism that jointly considers task execution and reconnection urgency, thereby providing a principled way to decide when reconnection should occur. Theoretical analysis justifies convergence to the satisfying reconnection within a prescribed finite time. Experimental results validate the performance of our proposed adaptive PT-CBF with improved task efficiency and satisfying reconnections.

Hao Liu, Yupeng Yang, Yanze Zhang +1

Department of Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA · Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA

Multi-Robot SystemsControl Barrier FunctionsMulti-Robot CoordinationFeedback ControlMulti-Agent Communication
AskPDF
Oct 5, 2026

Towards Decentralized Formation of Minimum-Length Communication Networks Using Robot Swarms

Multi-robot missions in infrastructure-denied environments frequently rely on reliable communication links between spatially separated locations. We propose a fully decentralized framework for constructing and dynamically maintaining communication networks without centralized topology planning or global positioning infrastructure. Driven strictly by local interactions, robots reconfigure local network topologies and adjust their physical positions to minimize overall network length while adhering to communication constraints. Formal analysis shows that our local reconfiguration operations guarantee continuous network connectivity, strictly decrease network length with every branch transfer, and bound worst-case performance to the shortest starlike tree. Embodied simulations and physical multi-robot experiments confirm that our approach forms networks near the length of centrally computed Euclidean Steiner trees. Additionally, the system dynamically adapts to moving targets and optimizes deployment by utilizing only necessary connectors, preserving excess robots for auxiliary tasks. This work enables autonomous swarms to self-organize adaptive ad hoc communication infrastructure in communication-denied environments, which could support applications varying from subterranean exploration to planetary missions.

Genki Miyauchi, Mohamed S. Talamali, Julian Rau +1

Bristol Robotics Laboratory, University of Bristol, Bristol, UK · School of Electrical and Electronic Engineering, University of Sheffield, Sheffield, UK · Department of Computer Science, Technical University of Darmstadt, Darmstadt, Germany

Swarm RoboticsCombinatorial OptimizationMulti-Robot CoordinationDecentralized Optimization
AskPDF
Jul 11, 2026

From Non-Rigid to Rigid: Safe Acquisition of Rigid Communication Graphs under Limited Sensing

Communication graph rigidity is a fundamental requirement in many multi robot formation control approaches. However, ensuring and maintaining a rigid communication topology becomes challenging in practice due to limited sensing ranges and dynamic operating conditions. This paper provides a method for achieving an inter robot collision free, rigid time varying communication graph, where communication links are established or broken according to limited sensing ranges, without assuming an initial rigid graph. In addition, the proposed approach guarantees the realization of a rigid graph for heterogeneous nonlinear multi robot systems. A computationally lean, distributed quadratic optimization-based controller is developed for a leader follower architecture, acquiring rigidity based on hierarchical second-order consensus among robots. Follower agents do not require global absolute positions of any agent, including their own. The proposed method is validated through both simulations and hardware experiments in a motion-capture environment, demonstrating reliable performance under the limited sensing capabilities of individual robots.

Saharsh, Vedhas Talnikar, Pushpak Jagtap

Department of Cyber Physical Systems · Indian Institute of Science · Bengaluru, 560012, India

Multi-Robot Formation ControlMulti-Agent ControlMulti-Robot CoordinationMulti-Agent Communication
AskPDF