Learning Situation-Specific Rules for Coordination in Multiagent Systems

Revised on Nov. 16, 2001


                Achieving globally coherent§ activity in a cooperative, distributed multi-agent system is a difficult problem for a number of reasons. One difficulty is that an agent's control decisions, based only on its local view of problem-solving task structures, may lead to inappropriate decisions about which activity it should do next, what results it should transmit to other agents and what results it should ask other agents to produce. If an agent has a view of the activities (task structures) of other agents, it can make more informed choices[1,2,3,4]. Another difficulty is that even with this type of meta-level information, there is still residual uncertainty about the outcomes of tasks and which future tasks will be coming into the system that may result in agents still exhibiting non-coherent behavior. These difficulties with achieving effective coordination are further exacerbated by the fact that an agent, in acquiring and exploiting a non-local view of other agents' activities, may expend significant computational resources. This expense is in terms of communication delays, as well as the computational cost of both providing this information in a suitable form to other agents and processing this information to make local decisions. Thus, for specific problem-solving situations, due to the inherent uncertainty in agents' activities and the cost of meta-level processing, it may not be worthwhile to acquire a complete view of other agents' activities, and thus a coordination strategy that does not eliminate all non-coherent activity may be optimal [4].

                For example, coordination to avoid redundant activities may be unnecessary if processing resources are not overloaded and if communication channels are neither expensive nor overloaded. In this case, local problem solving is done more efficiently where there is no additional overhead for coordination. If a coordination strategy can be developed whose costs can be varied depending upon the amount and type of non-local information used to make coordination decisions, then it seems that only a selected, possibly situation-specific, view of other agents' activities is necessary. The obvious next question is how to determine what the appropriate situation-specific view is and what type of coordination rules should be used in the situation. It is our hypothesis that for many multi-agent applications, especially those operating in complex, open and possibly evolving environments, it is very difficult or impossible for the designer of a system to a priori anticipate all the problem-solving contexts and exactly which information and what coordination strategy for each context will be most cost-effective. Thus, in this research, we propose integrating into each agent a distributed learning component that agents can use to acquire through experience which information is necessary for effective coordination in a specific situation and how to exploit this information locally to select and schedule its activities to achieve the desired coordination.

                Another way of understanding our approach to learning coordination rules can be seen by relating it to the GPGP/TAEMS coordination model [1,5,6]. From the perspective of this model, each of the agents makes scheduling decisions based on a subjective view of its own and other agents' activities and its view of available resources. This subjective view is specified by relationships among these activities such as enable-, facilitate-, overlap- and support-relations and resource usage patterns such as use-relation. These relationships describe how an activity affects the duration and importance rating of other activities, as well as the quality of the outcomes. All coordination activities are based on the existence and quantitative characteristics of these relationships. In certain situations this subjective view will lead to an agent taking ineffective or inappropriate actions because the relationships among certain non-local activities or the non-local resources have not been specified as part of the subjective view, and thus have not been appropriately taken into account in making coordination decisions. This lack of effective coordination can also occur because the subjective view was based on default assumptions or out-of-date information. In our case, we start out with agents who, prior to learning, have subjective views used for coordination that are based solely on their local activities. The use of this totally local subjective view implicitly makes the assumption that there are sufficient computational and other resources so that the details of the activities and the states of other agents are not necessary for effective operation. Thus, the goal of the learning system can be thought of as adding non-local control information (and associated control rules) to minimally augment the subjective view of an agent so that it has sufficient information about other agents' activities for it to make a more effective control decision in a specific situation.

               We developed this distributed learning component based on explanation based learning (EBL) techniques [7,8] using a domain model and inductive techniques such as comparative analysis. We implemented these ideas and applied it to a real distributed problem-solving system, LODES, which performs diagnosis of a computer communications network.

§ The behavior of cooperative agents is not coherent when agents transmit information that is not relevant or not timely, derive information that had already been generated by another agent, or cause the overloading of scarce or expensive shared resources.
Support-relation is a new relationship that was not in the original formulation discussed and relates to how a task in one agent can affect the subjective view of its own and another agent's task structure by changing the importance rating of its tasks. This rating change can, in turn, cause the agent to choose one task over another for execution.

References

[1] Decker, K.S. and Lesser, V.R. ``Designing a Family of Coordination Algorithms,'' Proceedings of the First International Conference on Multiagent Systems, San Francisco, June 1995. AAAI Press
[2] Durfee, E. H., Lesser, V. R. and Corkill, D. D., ``Coherent Cooperation Among Communicating Problem Solvers,'' IEEE Transactions on Computers, Vol. 36, Issue 11, November 1987, pp. 1275-1291. (Also published in Readings in Distributed Artificial Intelligence, A. Bond and L. Gasser (eds.), Morgan Kaufmann Publishers, California, 1988, pp. 268-284.)
[3] Durfee, E. H. and Lesser, V. R., ``Partial Global Planning: A Coordination Framework for Distributed Hypothesis Formation,'' IEEE Transactions on Systems, Man, and Cybernetics, 21(5):1167-1183, September/October 1991.
[4] Lesser, V. R., ``A Retrospective View of FA/C Distributed Problem Solving,'' IEEE Transactions on Systems, Man, and Cybernetics, 21(6):1347-1362, Nov./Dec. 1991.
[5] Decker, K. and Lesser, V. R. ``Quantitative Modeling of Complex Environments,'' International Journal of Intelligent Systems in Accounting, Finance and Management, special issue on Mathematical and Computational Models of Organizations: Models and Characteristics of Agent Behavior, 1993.
[6] Lesser, V.R., Decker, K., Carver, N., Garvey, A., Neiman, D., Nagendra Prasad, M., and Wagner, T., ``Evolution of the GPGP Domain-Independent Coordination Framework,'' University of Massachusetts/Amherst, Computer Science Technical Report 98--05, 1998.
[7] DeJong, G. ``Generalizations Based on Explanations,'' Proceedings. of 7th International Joint Conference on Artificial Intelligence, pp. 67-69, 1981.
[8] Mitchell, T. M., Keller, R. M. and Kedar-Cabelli, S. T. ``Explanation-Based Generalizations: A Unifying View,'' Machine Learning, Vol. 1, pp. 47-80, 1986.


Related papers

  • T. Sugawara and V. Lesser,``Learning to Improve Coordinated Actions in Cooperative Distributed Problem-Solving Environment,'' in Machine Learning Vol. 33, No.2/3, pp. 129 - 153, Kluwer Academic Publishers, 1998.

  • T. Sugawara and S. Kurihara,``Learning Message-Related Coordination Control in Multiagent Systems,'' Multi-Agent Systems -- Theories, Languages, and Applications, LNAI 1544, pp. 29 - 44, Springer-Verlag, 1998 (This papar is alsp avaiable from Proc. of the 4th Australian workshop on Distributed Artificial Intelligence , 1998).

  • T. Sugawara and V. Lesser, ``On-Line Learning of Coordination Plans,'' Proc. of the 12th Int. AAAI Workshop on Distributed Artificial Intelligence, 1993.

  • Sugawara, T. and Lesser, V. R. ``On-Line Learning of Coordination Plans,'' COINS Technical Report, 93-27, Univ. of Massachusetts, 1993.


© Toshiharu Sugawara