In this paper, we consider the problem of decentralized evaluation of redundant rigidity of a multi-agent network topology. Redundancy is an important restriction of a graph's rigidity property as it is a necessary condition for the global rigidity of a graph, a combinatorial notion that is vital for graph realizability with consequences for example in localization. Furthermore, redundant rigidity enforces additional structure which allows for link loss or failure while maintaining an underlying rigid topology. First, we map the combinatorial conditions for determining redundant rigidity to the context of a centralized pebble game. By exploiting intuition from a bipartite matching characterization, we demonstrate decentralized conditions based in graph search and agent agreement. Then we provide a complete description of a decentralized algorithm for evaluating redundant rigidity, exploiting auctions and boolean consensus. To illustrate our methods, we provide a brief simulation study of redundant rigidity evaluation and nonholonomic control that closes the paper.

Williams, R.K., Gasparri, A., Soffietti, M., & Sukhatme, G.S. (2015). Redundantly rigid topologies in decentralized multi-agent networks. In Proceedings of the IEEE Conference on Decision and Control (pp.6101-6108). Institute of Electrical and Electronics Engineers Inc. [10.1109/CDC.2015.7403179].

Redundantly rigid topologies in decentralized multi-agent networks

GASPARRI, ANDREA;
2015

Abstract

In this paper, we consider the problem of decentralized evaluation of redundant rigidity of a multi-agent network topology. Redundancy is an important restriction of a graph's rigidity property as it is a necessary condition for the global rigidity of a graph, a combinatorial notion that is vital for graph realizability with consequences for example in localization. Furthermore, redundant rigidity enforces additional structure which allows for link loss or failure while maintaining an underlying rigid topology. First, we map the combinatorial conditions for determining redundant rigidity to the context of a centralized pebble game. By exploiting intuition from a bipartite matching characterization, we demonstrate decentralized conditions based in graph search and agent agreement. Then we provide a complete description of a decentralized algorithm for evaluating redundant rigidity, exploiting auctions and boolean consensus. To illustrate our methods, we provide a brief simulation study of redundant rigidity evaluation and nonholonomic control that closes the paper.
9781479978861
Williams, R.K., Gasparri, A., Soffietti, M., & Sukhatme, G.S. (2015). Redundantly rigid topologies in decentralized multi-agent networks. In Proceedings of the IEEE Conference on Decision and Control (pp.6101-6108). Institute of Electrical and Electronics Engineers Inc. [10.1109/CDC.2015.7403179].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/315679
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact