Coordinating simple and unreliable agents

ABSTRACT

Coordinating a large number of simple and unreliable agents to achieve a global objective poses a unique design challenge: How to achieve robust system level behavior in spite of the computational/reliability limitations of the agents. We investigate agent coordination in the difficult optimization problem of selecting the subset of sensing devices with distortions that provides the smallest average distortion [1]. We approach problem by assigning an agent to each device and having that agent use a simple reinforcement learning algorithm to determine whether to be part of the aggregate device. Our results show that the right agent reward structure provides significant improvements over both traditional search methods and traditional multi-agent methods. Furthermore, even in extreme cases of agent failures (i.e., half the agents fail during the simulation) this approach still outperforms a failure-free and centralized search algorithm.

REFERENCES

• 1: D. Challet and N. F. Johnson. Optimal combinations of imperfect objects. Phys. Rev. Let., 89:028701, 2002.
• 2: T. Hogg and B. A. Huberman. Controlling smart matter. Smart Materials and Structures, 7:R1--R14, 1998.
• 3: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 4: M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research, 7:83--124, 1997.
• 5: K. Tumer and D. Wolpert. A survey of collectives. In Collectives and the Design of Complex Systems, pages 1, 42. Springer, 2004.
• 6: D. H. Wolpert and K. Tumer. Optimal payoff functions for members of collectives. Advances in Complex Systems, 4(2/3):265--279, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms, Design, Performance, Reliability