Asynchronous teams: Cooperation schemes for autonomous agents

Experiments over a variety of optimization problems indicate that scale-eff ective convergence is an emergent behavior of certain computer-based agents , provided these agents are organized into an asynchronous team (A-Team). A n A-Team is a problem-solving architecture in which the agents are autonomo us and cooperate by modifying one another's trial solutions. These solution s circulate continually. Convergence is said to occur if and when a persist ent solution appears. Convergence is said to be scale-effective if the qual ity of the persistent solution increases with the number of agents, and the speed of its appearance increases with the number of computers. This paper uses a traveling salesman problem to illustrate scale-effective behavior a nd develops Markov models that explain its occurrence in A-Teams, particula rly how autonomous agents, without strategic planning or centralized coordi nation, can converge to solutions of arbitrarily high quality. The models a lso perdict two properties that remain to be experimentally confirmed: construction and destruction are dual processes. In other words, adept dest ruction can compensate for inept construction in an A-Team, and vice-versa. (Construction refers to the process of creating or changing solutions, des truction, to the process of erasing solutions.) solution quality is independent of agent-phylum. In other words, A-Teams pr ovide an organizational framework in which humans and autonomous mechanical agents can cooperate effectively.