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.
Carboni, D., Williams, R.K., Gasparri, A., Ulivi, G., & Sukhatme, G.S. (2015). Rigidity-Preserving Team Partitions in Multiagent Networks. IEEE TRANSACTIONS ON CYBERNETICS, 45(12), 2640-53-2653.
|Titolo:||Rigidity-Preserving Team Partitions in Multiagent Networks|
|Data di pubblicazione:||2015|
|Citazione:||Carboni, D., Williams, R.K., Gasparri, A., Ulivi, G., & Sukhatme, G.S. (2015). Rigidity-Preserving Team Partitions in Multiagent Networks. IEEE TRANSACTIONS ON CYBERNETICS, 45(12), 2640-53-2653.|
|Appare nelle tipologie:||1.1 Articolo in rivista|