Ouimet, M.; Cortés, J. Hedonic coalition formation for optimal deployment. (English) Zbl 1358.93015 Automatica 49, No. 11, 3234-3245 (2013). Summary: This paper presents a distributed algorithmic solution, termed coalition formation and deployment algorithm, to achieve network configurations where agents cluster into coincident groups that are distributed optimally over the environment. The motivation for this problem comes from spatial estimation tasks executed with unreliable sensors. We propose a probabilistic strategy that combines a repeated game governing the formation of coalitions with a spatial motion component governing their location. For a class of probabilistic coalition switching laws, we establish the convergence of the agents to coincident groups of a desired size in finite time and the asymptotic convergence of the overall network to the optimal deployment, both with probability 1. We also investigate the algorithm’s time and communication complexity. Specifically, we upper bound the expected completion time of executions that use the proportional-to-number-of-unmatched-agents coalition switching law under arbitrary and complete communication topologies. We also upper bound the number of messages required per timestep to execute our strategy. The proposed algorithm is robust to agent addition and subtraction. From a coalitional game perspective, the algorithm is novel in that the players’ information is limited to the neighboring clusters. From a motion coordination perspective, the algorithm is novel because it brings together the basic tasks of rendezvous (individual agents into clusters) and deployment (clusters in the environment). Simulations illustrate the correctness, robustness, and complexity results. Cited in 1 Document MSC: 93A14 Decentralized systems 93E20 Optimal stochastic control 90C15 Stochastic programming Keywords:sensor networks; hedonic games; coalition formation; optimal deployment; spatial estimation; coalition formation PDFBibTeX XMLCite \textit{M. Ouimet} and \textit{J. Cortés}, Automatica 49, No. 11, 3234--3245 (2013; Zbl 1358.93015) Full Text: DOI