A-Teams Project Home Page


Index:


What is an Asynchronous Team of Autonomous Agents?

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.


Where Did the Ideas Come From?

An A-Team is a combination of the best features from a number of natural and synthetic systems, including: insect societies, cellular communities, genetic algorithms, blackboards, simulated annealing and tabu search.

What are A-Teams good for?

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.


Where have A-Teams been applied?

At Carnegie Mellon University, A-Teams have been used to solve a number of difficult and important problems, including: traveling salesman problems, high-rise building design, reconfigurable robot design, diagnosis of faults in electric networks, control of electric networks, job-shop-scheduling, protein structure analysis, robot-path-planning, and train-scheduling. Other groups, to whom the A-team technology has been transferred, have applied it to steel-mill scheduling, paper-mill scheduling and constraint satisfaction.

How do A-Teams Work?

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.


What can You gain from A-Teams?

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.


Current Research Thrusts


References

  1. Ph.D. Dissertations

    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

  2. M.S. Theses

    Andrew Gove : Theory of A-Teams

  3. Publications

    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


Current Research Group At Carnegie Mellon University

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


Author: Sanjay Sachdev sachdev@edrc.cmu.edu