Rigidity-Preserving Team Partitions in Multiagent Networks

Daniela Carboni, Ryan K. Williams, Andrea Gasparri, Giovanni Ulivi, Gaurav S. SukhatmeIEEE Trans. Cybernetics 2015 · DOI · OpenReview

Abstract

Motivated by the strong influence network rigidity has on collaborative systems, in this paper, we consider the problem of partitioning a multiagent network into two sub-teams, a bipartition, such that the resulting sub-teams are topologically rigid. In this direction, we determine the existence conditions for rigidity-preserving bipartitions, and provide an iterative algorithm that identifies such partitions in polynomial time. In particular, the relationship between rigid graph partitions and the previously identified Z-link edge structure is given, yielding a feasible direction for graph search. Adapting a supergraph search mechanism, we then detail a methodology for discerning graphs cuts that represent valid rigid bipartitions. Next, we extend our methods to a decentralized context by exploiting leader election and an improved graph search to evaluate feasible cuts using only local agent-to-agent communication. Finally, full algorithm details and pseudocode are provided, together with simulation results that verify correctness and demonstrate complexity.
BibTeX
@article{carboni2015rigidity,
  author = {Daniela Carboni and Ryan K. Williams and Andrea Gasparri and Giovanni Ulivi and Gaurav S. Sukhatme},
  title = {{Rigidity-Preserving Team Partitions in Multiagent Networks}},
  journal = {IEEE Trans. Cybernetics},
  year = {2015},
  doi = {10.1109/tcyb.2014.2378552},
}

Loading related content...

Figure