We consider the problem of autonomous collaboration in groups of robots or vehicles or agents in general. We describe methods for deriving local coordination rules using techniques from time-varying Markov random fields, which result in distributed asynchronous coordination algorithms using parallel Gibbs samplers. The algorithms circumvent the well known problem of traditional potential methods that get stuck in locally optimal paths. We show that under reasonable and mild assumptions globally optimal coordination paths emerge from these local strategies. We then consider the tradeoffs between performance and execution time. We develop and analyze two additional distributed coordination algorithms to speed up convergence, a hybrid one which is a mixture between deterministic gradient coordination and randomized Gibbs samplers, and another one which adds memory to this second hybrid algorithm. We demonstrate that these algorithms converge much faster while still resulting in nearly optimal paths. We then investigate the role of the communication topology among the collaborating agents in improving performance of distributed algorithms on graphs, such as convergence speed. We rigorously demonstrate that Small World graphs emerge as a good tradeoff between performance and efficiency in consensus problems, where the latter serves as a prototypical coordination problem. We discuss extensions to expander graphs and the significance of separating the collaboration topology from the communication topology in collaborating swarms. Next we introduce constrained coalitional games and we show that they capture in a fundamental way the basic tradeoff of benefits vs. cost of collaboration, in networked collaborating systems. We demonstrate that various simple models of constrained coalitional games can explain network formation and the emergence or not of collaboration. We close with conclusions on autonomic networked swarms and examples from biology, engineering, social and economic networks, and provide a brief list of interesting future research directions.
Download talk slides and videos in zip [~27MB]http://www.iit.demokritos.gr/docs/seminars/iptseminars-2010-06-25-Baras.zip