Coordination and Cooperation in Networked Multi-Agent Systems

Sponsor: National Science Foundation under Award 1320304

Networked wireless systems have significantly affected society, as cellular and WiFi networks are now ubiquitous in our daily life. An important class of networks is that of decentralized networks, which are characterized by a lack of fixed infrastructure, a multi-hop nature, and node mobility; such features provide significant flexibility, but also introduce a variety of design issues. A fundamental problem in decentralized networked systems is the coordination of activities of different nodes, where the availability of sufficient communication resources is critical in order for agents to cooperate and coordinate. This project takes a distinctive approach to develop a fundamental understanding of the interplay between communication and cooperation to achieve coordination and addresses the communication and coordination of probabilistic actions in networked multi-agent systems. This can be seen as an instance of network-based stochastic open loop control where a single communication message is sent to the agents to control their behavior in the absence of feedback. The project investigates two interrelated research tasks. First, the PIs wish to understand both the fundamental information-theoretic limits of coordination in small multi-terminal networks and the dependency of these limits on the communication network topology. The second research goal addresses the design of explicit coordination codes from error correction codes and to assess their performance under stringent delay and complexity constraints.

Scientific activities

Fundamental limits of coordination

Code design for coordination

  • Polar codes for coordination [3]
  • Invertible extractors for coordination [4]

Outreach activities


References

  1. Strong Coordination over a Three-Terminal Relay Network,
    Bloch, Matthieu R., and Kliewer Jörg
    , Proc. of IEEE Information Theory Workshop, November, Hobart, Tasmania, p.646–650, (2014)
  2. Strong Coordination over Multi-hop Line Networks,
    Vellambi, Badri N., Kliewer Jörg, and Bloch Matthieu R.
    , IEEE Information Theory Workshop, October, Jeju, South Korea, p.192--196, (2015)
  3. Polar Coding for Empirical and Strong Coordination via Distribution Approximation,
    Chou, Rémi A., Bloch Matthieu R., and Kliewer Jörg
    , Proc. IEEE International Symposium on Information Theory, June, p.1512 - 1516, (2015)
  4. Low-Complexity Channel Resolvability Codes for the Symmetric Multiple-Access Channel,
    Chou, Rémi A., Bloch Matthieu R., and Kliewer Jörg
    , Proc. of IEEE Information Theory Workshop, November, Hobart, Tasmania, p.466–470, (2014)