Evaluating Network Rigidity in Realistic Systems: Decentralization, Asynchronicity, and Parallelization

In this paper, we consider the problem of evaluating the rigidity of a planar network, while satisfying common objectives of real-world systems: decentralization, asynchronicity, and parallelization. The implications that rigidity has in fundamental multirobot problems, e. g., guaranteed formation stability and relative localizability, motivates this study. We propose the decentralization of the pebble game algorithm of Jacobs et al., which is an O(n(2)) method that determines the generic rigidity of a planar network. Our decentralization is based on asynchronous messaging and distributed memory, coupled with auctions for electing leaders to arbitrate rigidity evaluation. Further, we provide a parallelization that takes inspiration from gossip algorithms to yield significantly reduced execution time and messaging. An analysis of the correctness, finite termination, and complexity is given, along with a simulated application in decentralized rigidity control. Finally, we provide Monte Carlo analysis in a Contiki networking environment, illustrating the real-world applicability of our methods, and yielding a bridge between rigidity theory and realistic interacting systems.