Methodological Issues for Designing Multi-Agent Systems with Machine Learning Techniques: Capitalizing Experiences from the RoboCup Challenge
A. Drogoul & J.-D. Zucker LIP6 - U
niversité Paris 6 Bo?te 169 - 4 Place Jussieu 75252 PARIS CEDEX 05
This paper deals with one of the probably most challenging and, in our opinion, little addressed question that can be found in Distributed Artificial Intelligence today, that of the methodological design of a learning multi-agent system (MAS). In previous work, in order to solve the current software engineering problem of having the ingredients (MAS techniques) but not the recipes (the methodology) we have defined Cassiopeia, an agent-oriented, rolebased method for the design of MAS. It relies on three important notions: (1) independence from the implementation techniques; (2) definition of an agent as a set of three different levels of roles; (3) specification of a methodological process that reconciles both the bottom-up and the top-down approaches to the problem of organization. In this paper we show how this method enables Machine Learning (ML) techniques to be clearly classified and integrated at first hand in the design process of an MAS, by carefully considering the different levels of behaviors to which they can be applied and the techniques which appear to be best suited in these cases. This presentation allows us to take a broad perspective on the use of all the various techniques developed in ML and their potential use within an MAS design methodology. These techniques are illustrated by examples taken from the RoboCup challenge. We then show that a large part of the design activity is nevertheless left to be done as a result of heuristic choices or experimental work. This allows us to propose the Andromeda framework, which consists in a tighter integration of ML techniques within Cassiopeia itself, in order to assist the designer along the different steps of the method and to develop self-improving MAS.
Keywords: agent-oriented design, distributed machine learning, RoboCup Challenge, collective robotics.
Multi-Agent Systems (MAS) have never been technically so simple to implement and conceptually so difficult to design. A number of frameworks are available, theoretical studies are increasing continuously, and it is now even possible to find commercial products that propose to solve almost any of the problems a software engineer usually faces when building an MAS: agents' architectures, cooperation and coordination algorithms, communication languages, etc. The attractiveness of MAS has also increased since its birth: these systems, which used to be restricted to specific areas of application in the late eighties (Bond and Gasser, 1988), can now be found almost everywhere, from natural language processing to planning or problem solving. The potential to apply a promising "divide and conquer" approach to problems that were once thought to be solvable only by centralized techniques (Decker, 1987; Drogoul and Dubreuil, 1991); the ability to use sociological or even biological rather than the traditional psychological metaphors when designing an intelligent system (Drogoul and Ferber, 1993; Korf, 1992); the continuous success of internet-related systems and applications which "naturally" require a decentralized scheme (Moukas, 1996); the appeal of building open systems (Hewitt and Inman, 1991) rather than closed ones, everything, from marketing to research, contributes to make Distributed AI one of the most promising trends in the present and future - of AI. However, ten years after the first use of the term "DAI" for describing this broad domain of research that extends from distributed systems to Artificial Life (Demazeau and Muller, 1991; Werner and Demazeau, 1992), we claim (and intend to demonstrate in this paper) that little has been done on the most delicate part of this novel approach. Although MAS are now used in very large software engineering projects (Wooldridge, 1997), there is no methodology available so far, for allowing software engineers to use the MAS technology in routine operations. And this claim is even more true when one tries to build adaptive MAS - i.e. MAS that can learn how to improve themselves using Machine Learning techniques. 1.1. What is a methodology?
Providing a platform, even splendidly programmed, for designing a system is like providing ingredients without a recipe: depending on the skills of the cook, there is always a chance that something good will be cooked, but maybe not. However, the cook certainly prevents himself from reproducing this experiment, changing it a little bit to accommodate different tastes or teaching it to somebody else. It is and remains a one-shot, stand-alone, success! Methodologies in computer science are what recipes are for cooking: they replace neither the intuition nor the coding, but provide a framework for unifying these two activities. Basically, the main role of a methodology is to identify the steps that are necessary to proceed from the definition of the requirements of a project to their fulfillment (i.e. the project life cycle). More concretely, a methodology supplies the tools for transforming an always intuitive and subjective vision of a system to be built (the client's requirements, for instance) into a formalized and objective (i.e. which can be shared and reused) definition of the same system once it has been implemented. It thus provides a project with "something" that will stand and remain somewhere between the original blueprint and the final code: 1. A structured set of guidelines, which includes the steps mentioned above, advice for each of these steps, and how to proceed from one step to another.
2. A unified way to document the design process. This is used for sharing the experience gained during this process among designers and/or across time whenever, for instance, the design has to be undertaken by other software engineers. 3. The use of a homogeneous terminology, which has a meaning at each step of the cycle and supports the transitions from step to step (it usually also includes a graphical terminology based on diagrams and flowcharts). 4. The use of operational conceptual abstractions; that is, conceptual structures abstract enough to allow a sufficient choice of techniques when it comes to implementing the system, but operational enough to prevent the designer from using unrelated or outdated techniques. 5. A comprehensive and incremental history of the project, which gives the possibility to backtrack from any step to previous ones without losing what has been done before. 1.2. Why a methodology?
In the case of Distributed Artificial Intelligence, the project requirements intuitively consist in having a number of agents achieving a collective task. To fulfill these requirements, one must design the agents with specific attention to both their skills (or functional faculties) and their abilities to organize themselves. This implies managing at least three different levels of abstraction at the same time: 1. The level of the individual agents (What architecture to implement them? What is their knowledge and how do they manage it? What are their skills and how are they distributed among the agents?). 2. The level of the interactions between the agents (How and what do they communicate? Can they act on each other and in which way?). 3. The level of their organization (how do they cooperate? Is there a shared goal and how can they plan to collectively reach it? What is the structure of the organization and how does it evolve?) The RoboCup challenge (Kitano et al., 1997a; Kitano et al., 1995) is a good example of this necessity: designing a team of soccer-playing robots requires the designer to pay attention simultaneously to these three levels. The programming of the individual skills is as important as the design of the inter-individual coordination mechanisms or that of the collective cooperation schemes. Moreover, there is an important interplay between these three levels: for example, knowing how to dribble can enable the players to form powerful collective combinations; on the contrary, being provided with a team strategy may require the players to undertake new individual responsibilities (i.e. special tactics not specifically required when playing alone). The existing methodologies, especially the object-oriented methodologies (Graham, 1994) that can be considered because of some similarities such as distribution or locality1, provide an interesting basis of analysis (Abbott, 1983; Coad and Yourdon, 1991) since they enable the distribution of the initial requirements along the structural and behavioral axes. However, they do not offer any methodological framework for taking the various organizational issues into
And also because most agent-based systems are programmed using object-oriented languages.
account, because the organization is not considered as an object of analysis by itself (Booch, 1994). A number of very interesting studies on building agent-oriented methodologies as extensions of object-oriented ones have nevertheless been undertaken (see for example (Pont and Moreale, 1996)), but what they can really provide so far is still unclear: agents and objects differ in a number of important respects, the most noticeable being the ability of agents to dynamically and autonomously change their organization, something that objects are not supposed to be allowed to do. We believe that although object-oriented languages are the prime target for implementing MAS, it would be an error to consider agents as only "superobjects" (see for instance Wooldridge's arguments about the importance of the intentional stance for building MAS (Wooldridge, 1997) even if, in his case, he still relies on a specific technique, the BDI architecture, for designing an MAS). On the other hand, the little DAI work (e.g. (Moulin and Cloutier, 1994; Wooldridge, 1992)) that deals with methodological aspects either indirectly addresses the organizational issues through the use of specific negotiation or coordination techniques, or imposes certain agents' architectures - which in fact are only particular methods of implementation. The Cassiopeia method, presented in (Collinot and Drogoul, 1998; Drogoul and Collinot, 1998), is an attempt to overcome this problem of reliance on the implementation by providing a rolebased abstract view of the agents within which the different techniques can easily be classified. Like object-oriented methods, it does not solve the problem of design but provides a framework for explicitly and methodically expressing the hypotheses and choices that are being made during the design process. 1.3. Learning Multi-Agent Systems (LMAS)
The design requirements expressed above are even stronger when the goal is to make adaptive MAS, by introducing Machine Learning (ML) techniques that allow the agents to learn how to behave, how to interact or how to organize themselves (Weiss and Sen, 1995). Indeed, it requires the agents to learn different abilities at different levels of abstraction. And it is important not to confuse these levels: individually learning a given skill is not at the same level as collectively learning how to counteract a strategy, for example. Moreover, from a technical point of view, the hypotheses, the protocols and the ML techniques to be used in these two cases are not likely to be the same. In this respect, the introduction of ML techniques in MAS needs to be undertaken methodologically, carefully identifying which techniques to use at which level and which levels to consider. Although this introduction has received a great deal of attention in recent years (Sen, 1997; Weiss, 1996), few people have really considered the specificity of MAS compared to traditional ML systems. The majority of the studies deal with very narrow subjects such as the suitability of given ML techniques to such and such task, but none of them really handles all the following questions, which are central to the design of LMAS: 1. Beneficiary: When an agent learns something, who is the beneficiary? The agent itself? The group of agents? The overall organization? All of them? 2. Learning process: How does it learn? By itself? In interaction with other agents? In a group? 3. Learning tasks: What does it learn? How to behave? How to interact? How to organize itself with the others? 4. Learning techniques: Which technique to use for a given task and a given process? How to compare their suitability? 5. Learning protocols: What is the context that would allow for a correct evaluation of the learning task?
We claim that these questions, among others, cannot be answered without being asked within an MAS design methodological process, which allows the designer to deal with these multiple levels of abstraction while providing a framework for possibly revising the choices. Conversely, we strongly believe that the introduction of ML techniques within the methodological tool itself is the only way to solve the usual problems one faces when designing an MAS (be it adaptive or not). The most crucial of these problems are pointed out at the end of Section 2, after the presentation of the Cassiopeia methodology and with the help of a short presentation of the team we have designed for the RoboCup simulation league. We then propose a classification of different machine learning techniques and concepts in Section 3. The Andromeda2 methodology, which is a result of a tight integration of learning methods with the Cassiopeia concepts, is introduced in Section 4. We conclude by providing some hints about the future of our attempt to build a