文摘
In this paper, we consider the problem of identifying a bipartition of a planar multi-robot network, such that the resulting two sub-teams are rigid networks. As opposed to approaching the network splitting problem constructively, we instead 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 direction towards which a graph search is applied. Adapting a supergraph search mechanism from the set generation literature, we then provide a methodology for discerning graphs cuts that represent valid rigid bipartitions. Finally, full algorithm details and pseudocode are provided, together with simulation results that verify correctness and demonstrate complexity.