An asynchronous team (A-Team) is a strongly cyclic computational network. Results are circulated through this network by software agents. The number of agents can be arbitrarily large and the agents may be distributed over an arbitrarily wide area. Agents cooperate by working on one another's results. Each agent is completely autonomous (it decides which results it is going to work on and when). Results that are not being worked on accumulate in shared memories to form populations. Randomization (the effects of chance) and destruction (the elimination of weak results) play key roles in determining what happens to the populations.
A-Teams have proved to be extremely effective in solving very difficult problems for which many algorithms are available, but none is entirely satisfactory. Some are reliable but too slow, others are fast but too unreliable. An A-Team combines such algorithms so they can cooperate to produce much better results much faster than they could if working alone. The number of algorithms in an A-Team can be arbitrarily large. All the algorithms can work in parallel all the time. Moreover, the addition of a new algorithm is quick and easy. Indeed, A-teams are so easy to assemble and disassemble that they can be used for task-specific applications: when a difficult computational task is encountered, assemble an A-Team customized for the task from all the available agents (encapsulated algorithms or procedures), perform the task, and then disassemble the A-Team so its agents are released for other tasks.
An A-Team is a strongly cyclic network of shared memories and agents. The theory of such networks, which we are developing, shows that they are scale-effective: for every A-Team there are certain memories and agents that if added, will result in better performance. Thus, if an A-Team is not fast enough or is not producing good enough results, one only needs to find the right agents and memories to add, and the team will work better. How are these agents and memories to be found? At the moment, the process is experimental. Our main research goal is to make it automatic.
If you have a difficult computational problem that cannot be satisfactorily solved, A-Teams might help.
Contact Sarosh Talukdar (412-268-8778, snt+@edrc.cmu.edu) for further information.
R.W. Quadrel, "Asynchronous Design Environments: Architecture and Behavior," Department of Architecture, Carnegie Mellon University, Pittsburgh, PA, 1991
S. Murthy, "Synergy in cooperating agents: designing manipulators from task specifications," Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 1992.
C.L. Chen, "Bayesian Nets and A-Teams for Power System Fault Diagnosis," Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 1992
Pedro S. deSouza, "Asynchronous Organizations for Multi-Algorithm Problems," Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 1993
V. C. Ramesh , "Inertial Search and Asynchronous Decompositions," Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 1996
C. K. Tsen, "Solving Train Scheduling Problems Using A-Teams," Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 1995
Andrew Gove : Theory of A-Teams
S.N. Talukdar, S.S. Pyo and T.Giras, "Asynchronous Procedures for Parallel Processing," IEEE Trans. on PAS, Vol. PAS-102, No. 11, Nov. 1983
P.S. deSouza and S.N. Talukdar, "Genetic Algorithms in Asynchronous Teams," Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, Los Altos, CA, 1991
S.N. Talukdar and V.C. Ramesh, "A parallel global optimization algorithm and its application to the CCOPF problem," Proceedings of the Power Industry Computer Applications Conference, Phoenix, May 1993
S.Y. Chen, S.N. Talukdar and N.M. Sadeh, "Job-Shop-Scheduling by a Team of Asynchronous Agents," IJCAI-93 Workshop on Knowledge-Based Production, Scheduling and Control, Chambery, France, 1993
S.N. Talukdar, Lars Baerentzen, Andrew Gove and Pedro deSouza, "Cooperation Schemes for Autonomous Agents," 1996
Group Leader: Sarosh Talukdar
Graduate Students: Lars Baerentzen, Eduardo Camponogara, Philip Chang, Steven Y. Chen, Sanjay Sachdev
Researchers: John Dolan, Jim Hemmerle, Michael Terk
Undergraduate Students: Rudolph Yeung