Asynchronous teams: Cooperation schemes for autonomous agents

Experiments over a variety of optimization problems indicate that scale-effective convergence is an emergent behaviour of certain computer-based agents, provided these agents are organized into an asychronous team (A-Team). An A-Team is a problem-solving architecture in which the agents are autonomous and cooperate by modifying one another's trial solutions. These solutions circulate continually. Convergence is said to occur if and when a persistent solution appears. Convergence is said to be scale-effective if the quality 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 behaviour and develops Markov models that explain its occurrence in A-Teams, particularly how autonomous agents, without strategic planning or centralized coordination, can converge to solutions of arbitrarily high quality. The models also predict two properties that remain to be experimentally confirmed: construction and destruction are dual processes. In other words, adept destruction can compensate for inept construction in an A-Team, and vice versa. (Construction refers to the process of creating or changing solutions, destruction, to the process of erasing solutions.) Solution quality is independent of agent-phylum. In other words, A-Teams provide an organizational framework in which humans and autonomous mechanical agents can cooperate effectively.