InterJournal Complex Systems, 1138
Status: Accepted
Manuscript Number: [1138]
Submission Date: 2004
Coordination in Large Collectives
Author(s): Kagan Tumer

Subject(s): CX.6



Finding the subset of a set of imperfect devices (e.g., nano or micro devices) that results in the best aggregate device is a challenging problem (Challet and Johnson, Phys. Rev. Let., vol 89, 028701, 2002). It is an abstraction of what will likely be a major difficulty in designing and controlling systems of nano or micro-scale components, particularly when a large fraction of those components may be unreliable. Imbuing each device with simple decision making ability, we transform this problem into one of coordination in a complex system. As such, in addition to determining what each component should do, we face problems of scaling (number of components in the thousands to tens of thousands), observability (components have limited sensing capabilities), and reliability (the components are faulty). We present an approach based on devising component goals that are both aligned with the overall system goal (e.g.,forming best aggregate device), and rely on information readily (e.g., locally) available to the components. Each component in such a collective, then uses a simple reinforcement learning algorithm to selfishly pursue its own goals. Because those goals have been derived in a principled manner, there is no need to use external devices to force collaboration or coordination among the components for the system to reach a globally desirable state. The results show that not only this approach provides improvements of over an order of magnitude over both traditional search methods and traditional multi-agent methods, but that the gains increase with the size of the system. This latter result makes this method ideal for domains where the number of components is currently in the thousands and will reach millions in the near future.

Retrieve Manuscript
Submit referee report/comment

Public Comments: