UCSD

Mechanical and Aerospace Engineering

• Home
• Publications
• Group
• Teaching
• Software
• Lab

---

Hedonic coalition formation for optimal deployment
M. Ouimet, J. Cortés
Automatica 49 (11) (2013), 3234-3245

Abstract

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 upper bound the expected completion time of algorithm executions that use the "proportional-to-number-of-unmatched-agents" switching law, that depends on the number of unmatched agents, under arbitrary and complete communication topologies. 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 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). Several simulations illustrate the correctness, robustness, and time complexity results.

pdf   |   ps.gz

Mechanical and Aerospace Engineering, University of California, San Diego
9500 Gilman Dr, La Jolla, California, 92093-0411

Ph: 1-858-822-7930
Fax: 1-858-822-3107

cortes at ucsd.edu
Skype id: jorgilliyo