Dynamic Adaptation of Communication Topology in Robotic Swarms Based on Local Graph k-Connectivity

Ensuring the stability of the communication structure in robotic swarms with limited communication range requires the development of effective mechanisms for adapting the interaction topology between agents. In dynamically changing environments, conventional fixed-topology approaches prove inadequate, necessitating adaptive solutions that function without comprehensive network knowledge. This study investigates a dynamic connectivity graph management method grounded in local node k-connectivity metrics, which quantify the minimum number of agents whose removal would isolate a given node from the network. We propose an algorithm for selecting control agents based on degree centrality criteria while accounting for the structure of connected graph components, implemented within a modular software environment for reproducible testing on double integrator and quadcopter models. Computations proceed in a decentralized manner using local measurements, minimizing communication channel load and enabling scalability as group size increases. Experimental evaluation on systems ranging from 10 to 100 agents demonstrates that the adaptive approach improves connectivity preservation probability from 64 % to 88 % under conditions with 20 % malicious agents in sparse topologies, while the average local k-connectivity increases from 2.3 to 3.8 for k-nearest neighbor scenarios with k = 3. Computational complexity analysis confirms the method’s scalability, with graph update times of 15—45 ms for systems up to 100 agents at a 20 Hz sampling frequency. The low latency of topology calculations enables integration into real-time control loops for micro-UAV and ground platform onboard controllers. Future work may incorporate data transmission delay models and kinematic constraints of physical robots to facilitate field testing. These findings advance decentralized control theory for distributed systems and provide a foundation for designing fault-tolerant robotic swarm architectures.

1. Tang R., Tang J., Talip M. S. А., Halid F., Jusoh J. A., Ferdaus M. M., Ismail А. R. Enhanced multi agent coordination algorithm for drone swarm patrolling in durian orchards, Scientific Reports, 2025, vol. 15, no. 1, pp. 9139, DOI: 10.1038/s41598-025-88145-7.

2. Romanov А. M. Ensuring scalability and specified fault tolerance level of robot control systems, Vestnik of Bauman Moscow State Technical University. Series: Instrument Engineering, 2023, no. 2, pp. 12—25 (in Russian).

3. Belkin U. V., Prihodskiy A. A., Serikov S. A. Development and evaluation of decentralized control algorithms for robot swarms in emergency response scenarios, Izvestiya of Volgograd State Technical University, 2025, no. 4 (299), pp. 12—15, DOI: 10.35211/1990-5297-2025-4-299-12-15 (in Russian).

4. Belkin U. V., Prihodskiy A. A., Serikov S. A. Improvement of decentralized swarm robot control methods for emergency response: dispersion algorithm, Quality and Life, 2025, no. 2 (46), pp. 63—70 (in Russian).

5. Sabattini L., Chopra N., Secchi C. Decentralized connectivity maintenance for cooperative control of mobile robotic systems, The International Journal of Robotics Research, 2013, vol. 32, no. 12, pp. 1411—1423, DOI: 10.1177/0278364913499085.

6. Reynolds C. W. Flocks, herds, and schools: А distributed behavioral model, Computer Graphics (SIGGRAPH ‘87 Conference Proceedings), 1987, vol. 21, no. 4, pp. 25—34, DOI: 10.1145/37402.37406.

7. Olfati-Saber R. Flocking for multi-agent dynamic systems: Algorithms and theory, IEEE Transactions on Automatic Control, 2006, vol. 51, no. 3, pp. 401—420, DOI: 10.1109/TAC.2005.864190.

8. Chen G., Duan Z. Network synchronizability analysis: А graph-theoretic approach, Chaos: An Interdisciplinary Journal of Nonlinear Science, 2008, vol. 18, no. 3, pp. 037102, DOI: 10.1063/1.2965530.

9. Li Y., Huang Y., Feng J., Chen Z. Multiagent reinforcement learning based on structural coordination, Tsinghua Science and Technology, 2025, vol. 30, no. 3, pp. 278—291, DOI: 10.26599/TST.2025.9010043.

10. Baltes J., Akbar I., Saeedvand S. Cooperative dual-actor proximal policy optimization algorithm for multi-robot complex control task, Advanced Engineering Informatics, 2025, vol. 63, pp. 102960, DOI: 10.1016/j.aei.2024.102960.

11. Kargar E., Kyrki V. MACRPO: Multi-agent cooperative recurrent policy optimization, Frontiers in Robotics and AI, 2024, vol. 11, pp. 1394209, DOI: 10.3389/frobt.2024.1394209.

12. Yang Sh., Filimonov N. B. Consensus problems in multiagent systems: State of the art and perspectives, High-Performance Computing Systems and Technologies, 2025, vol. 9, no. 1, pp. 197—207 (in Russian).

13. He C., Feng Z., Ren Z. А flocking algorithm for multi-agent systems with connectivity preservation under hybrid metric-topological interactions, PLOS ONE, 2018, vol. 13, no. 2, pp. e0192987, DOI: 10.1371/journal.pone.0192987.

14. Tarjan R. E. Depth-first search and linear graph algorithms, SIAM Journal on Computing. 1972, vol. 1, no. 2, pp. 146—160. DOI: 10.1137/0201010.

15. Freeman L. C. Centrality in social networks: Conceptual clarification, Social Networks, 1978, vol. 1, no. 3, pp. 215—239, DOI: 10.1016/0378-8733(78)90021-7.

16. Ji M., Egerstedt M. Distributed coordination control of multiagent systems while preserving connectedness, IEEE Transactions on Robotics, 2007, vol. 23, no. 4, pp. 693—703, DOI: 10.1109/TRO.2007.900638.

17. Dimarogonas D. V., Johansson K. H. Decentralized connectivity maintenance in mobile networks with bounded inputs, IEEE International Conference on Robotics and Automation, 2008, pp. 1507—1512, DOI: 10.1109/ROBOT.2008.4543418.

18. Albert R., Jeong H., Barabási А. L. Error and attack tolerance of complex networks, Nature, 2000, vol. 406, pp. 378—382, DOI: 10.1038/35019019.

19. Beineke L. W., Oellermann O. R., Pippert R. E. The average connectivity of a graph, Discrete Mathematics, 2002, vol. 252, no. 1—3, pp. 31—45, DOI: 10.1016/S0012-365X(01)00180-7.

20. Cao Y., Ren W. Distributed coordinated tracking with reduced interaction via a variable structure approach, IEEE Transactions on Automatic Control, 2012, vol. 57, no. 1, pp. 33—48, DOI: 10.1109/TAC.2011.2146830.

21. Gerdpratoom N., Yamamoto K. Decentralized nonlinear model predictive control-based flock navigation with real-time obstacle avoidance in unknown obstructed environments, Frontiers in Robotics and AI, 2025, vol. 12, pp. 1540808, DOI: 10.3389/frobt.2025.1540808.

22. Wang L., Ames A. D., Egerstedt M. Safety barrier certificates for collision-free multirobot systems, IEEE Transactions on Robotics, 2017, vol. 33, no. 3, pp. 661—674, DOI: 10.1109/TRO.2017.2659727.

23. Hildenbrandt H., Carere C., Hemelrijk C. K. Self-organized aerial displays of thousands of starlings: А model, Behavioral Ecology, 2010, vol. 21, no. 6, pp. 1349—1359, DOI: 10.1093/beheco/arq149.

24. Dey S., Xu Н. Distributed adaptive flocking control for large-scale multiagent systems, IEEE Transactions on Neural Networks and Learning Systems, 2025, vol. 36, pp. 3126—3135, DOI: 10.1109/TNNLS.2024.3456789.