Identifying Rigidity-Preserving Bipartitions in Planar Multi-Robot Networks

详细信息    查看全文

• 作者：Daniela Carboni^* ; ^{carboni@dia.uniroma3.i" class="auth_mail" title="E-mail the corresponding author} ; Ryan K. Williams^** ; ^{rkwillia@usc.ed" class="auth_mail" title="E-mail the corresponding author} ; Andrea Gasparri^* ; ^{gasparri@dia.uniroma3.i" class="auth_mail" title="E-mail the corresponding author} ; Giovanni Ulivi^* ; ^{ulivi@dia.uniroma3.i" class="auth_mail" title="E-mail the corresponding author} ; Gaurav S. Sukhatme^** ; ^{gaurav@usc.ed" class="auth_mail" title="E-mail the corresponding author}
• 刊名：IFAC-PapersOnLine
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：47
• 期：3
• 页码：8085-8090
• 全文大小：358 K

文摘

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.