Connectivity Lifting for Multi-Agent Systems

Author(s):

Moshe Hamaoui

Abstract:

Enhancing network connectivity in multi-agent systems, particularly for airborne platforms with limited communication ranges, is a crucial challenge in designing resilient teams of autonomous collaborating agents. This report formulates and addresses the Multi-Agent System Connectivity Augmentation problem that seeks to efficiently increase network connectivity subject to the agents’ motion and reachability constraints. A two-phased approach is proposed. First, we identify feasible edge sets that meet a specified vertex-connectivity threshold, employing cardinality bounds and pruning techniques to reduce computational complexity. Second, we optimize the spatial arrangement of agents by embedding these edge sets into 3D space, minimizing displacement using second-order cone programming. Numerical experiments demonstrate that the proposed method significantly improves network resilience with minimal agent movement. Furthermore, the application of practical heuristics, such as maintaining initial communication links, achieves substantial reductions in computational time with little or no loss of solution quality. This framework offers a scalable approach to improving the robustness of multi-agent systems with potential for further extensions in decentralized and real-time applications.