Learning to Coordinate Actions in Multi-Agent-Systems

1 Introduction

Multi-Agent Systems. In computer science and arti­ ficial intelligence the concept of multi-agent systems has influenced the initial developments in areas like cognitive modelling [Selfridge, 1959; Minsky, 1979], blacxboard systems [Erman and Lesser, 1975], object-oriented pro­ gramming languages [Hewitt, 1977], and formal models of concurrency [Petri, 1962; Brauer et al., 1987]. Nowa­ days multi-agent systems establish a major research sub­ ject in distributed artificial intelligence; see fBond and Gasser, 1988;· Brauer and Hermindez, 1991; Gasser and Huhns, 1989; Huhns, 1987] . The interest in multi-agent systems is largely founded on the insight that many real­ world problems are best modelled using a set of agents instead of a single agent . Inyarticular, multi-agent mod­ elling makes it possible (i to cope with natural con­ straints like the limitation of the processing power of a single agent or the physical distribution of the data to be processed and {ii) to profit from inherent properties of distributed systems like robustness, fault tolerance, parallelism and scalability.

Generally, a multi-agent system is composed of anum­ ber of agents that are able to interact with each other and the environment and that differ from each other in their skills and their knowledge about the environment. (Usually an individual agent is assumed to consist of sen­ sor component, a motor component, a knowledge base, and a learning component.) There is a great variety in the multi-agent systems studied in distributed arti­ ficial intelligence [Huhns, 1987, foreword]. This raper deals with reactive multi-ae;ent systems, where 'reac­ tive" means that the behaviOr and the environment of the system are strongly coupled (there is a continuous interaction between the system and its environment).

Learning. There is a common agreement that there are two important reasons for studying learning in multi­ agent systems: to be able to endow artificial multi­ agent systems (e.g., systems of interacting autonomous robots) with the ability to automatically improve their behavior; and to get a better understandmg of the learn­ ing processes in natural multi-agent systems (e.g., hu­ man groups or societies) . In a multi-agent system two forms of learning can be distinguished [Shaw and Whin­ ston, 1989]. First, centralized or isolated learning, i.e. learning that is done by a single agent on its own (e.g. by creating new knowledge structures or by practicing motor activities). And second, distributed or collective learning, i.e. learning that is done by the agents as a group (e.g. by exchanging knowledge or by observing other agents). This paper focusses on collective learn­ ing and the central question addressed is: "How can each agent learn which action it shall perform under which circumstances?" In answering this question, two important constraints have to be taken into consider­ ation [Wei6, 1993a, 1993b]. First, the incompatibility constraint, i.e. the fact that different actions may be incompatible in the sense that the execution of one ac­ tion leads to environmental changes that impair or even prevent the execution of the otliers. And second, the local information constraint, i.e. the fact that an agent typically has only local information about the actual en­ vironmental state, and this information max differ from the one another agent has; this situation is illustrated by figure 1.

Two algorithms called the ACE algorithm and the AGE algorithm for reinforcement learning in reactive multi-agent systems are described (ACE and AGE are acronyms for "ACtion Estimation" and "Action Group Estimation", respectively). These algorithms base on the action-oriented version [Wei6, 1992] of the bucket brigade learning model for classifier systems [Holland, 1986]. Accordin~ to both algorithms the agents collec­ tively learn to estimate the goal relevance of their actions and, based on their estimates, to coordinate their actions and to generate appropriate action sequences.

Notational Preliminaries. For a description of the ACE and the AGE algorithm the following elemen­ tary notation is used throughout the rest of this paper. Ag = {At, ... ,An} (n EN) denotes the set of all agents. S (T, U, ... ) refers to an environmental state, and S; refers to the part of S that is known to the agent A; E Ag (S; ~ S); S; is called A; 's knowledge about S. AG 011 = { al, ... , a~'} ( m; E N) denotes the set of all possible actions of the agent A;, and it is called the action potential of A;. AG 0 ,. [S] denotes the set of all ac­ tions that A; could carry out (identifies as "executable") in the environmental stateS (AGou[S] ~ AG 0 ,.).

It is worth emphasizing that S; n Sj may but need not be empty, and that U7=t S; is not necessarily equal to S (i.e. the agents may have incomplete information about an environmental state, see figure 1). Similarly, if S and T are two different environmental states, then S; nT; may but need not be empty; in particular, it may be the case that S; = T; (i.e. an agent may be unable to distinguish between different environmental states).

2 Collective Learning

The ACE Algorithm. According to the ACE al­ gorithm the learning activity of the multi-agent system results from the repeated execution of a basic working cycle which consists of the three activitities action deter­ mination, competition, and credit assignment as follows.

First, each agent A; E Ag determines, in dependence on its knowled§e S; about the actual environmental state S, the set Acf .. [S] of actions that it could carry out.

Then the agents compete for the right to become ac­ tive. This competition encompasses the calculation and announcement of bids and the selection of the actions that are actually carried out:

• (i) Each agent A; makes a bid B{ [S] for each of its possible actions a{ E AG 0 .. [S] and announces it to the other agents. The bid is calculated by

where Q is a small constant called rnk factor' p is a small random number called noise term, e is a constant called estimate minimum, and E{ [S] is A; 's estimate of the goal relevance of a{ in dependence on its knowledge S; about S. The a indicates the fraction of Ef [S] the agent A; is willing to risk for being allowed to perform the action a{; the P intro­ duces noise into the competition in order to avoid getting stuck into local learning minima; and the e helps to prevent executing useless (low-estimated) actions. (Whenever an agent A; can execute an ac­ tion under some knowledge S; for the first time, it initializes the estimated goal relevance of this ac­ tion with a predefined value Einit; afterwards the estimated goal relevance is adjusted during credit assignment as it is described below.)

• (ii) After the agents have announced their bids, they select the actions to be carried out. The agent hav­ ing made the highest bid is allowed to execute its corresponding action, and all agents withdraw the bids for those actions that are incompatible to this selected action; this is repeated until no further ac­ tion being associated with a non-zero bid can be selected. This action selection may be formally de­ scribed as follows:
• AcP 0 .. [SJ = u~=l Acfou[S] and A= 0
• until AcPou [S] = 0 do
• select a{ E AcP 0 ,. [S] with Bf [S] ~ Bi[S) for all a~ E AcP 0 " [S]
• A = A u {a{}
• AcPOU [S] = AcP 0 .. [S] \ (a{ U {a~ E Ac"ou[S): a~ and a{ are incompatible} )

The set A is called the actual activity context, and the actions contained in in this set are called the actual actions (in stateS). (The selection requires a rational or non-egoistic behavior of the agents in the sense that none of the agents insists the execution of a low-bid or an incompatible action.)

. F~nally, the ~gents assign credit to each other by ad­ JUstmg the esttmates of the goal relevance of then ac­ tions. This adjustment is done accordin~ to the action­ oriented bucket brigade mechanism [Wet6, 1992]. Infor­ mally, the agents reduce the estimates of their actual ac­ tions (the actual winners pay for their previlege to carry out their actions), and hand the amount of all reductions back to the agents that won the previous competition (the previous winners are rewarded for appropriately set­ ting up the environment). The previous winners, in turn, add the received amount to the estimates of the actions they performed last. Additionally, if there is an external reward from the environment, then the agents distribute this reward among the actual actions. Formally, this can be described as follows:

• (i) For each actual action a{ E A the agent A; modifies its estimate Ef [S] according to

where B{ [S] is the corresponding action-specific bid and Ru:t is the external reward (if there is any).

• (ii) The agents sum up the bids they made for the actual actions. The resulting sum B..4[S],

is distributed in equal shares among those actions that were carried out during the previous competi­ tion. Suppose that T is the previous environmental state, B is the previous activity context, and a~ E B. Then E~[T] is increased by

This credit assigment mechanism has two major effects [Holland, 1985]: the estimates of actions that are in­ volved in a successful sequence of action sets (i.e. a se­ quence that leads to external reward) increase over time and, by the way, stabilize this sequence; and conversely, the estimates of actions that are involved in an unsuc­ cessful sequence decrease over time and destabilize this sequence.

The AGE Algorithm. The AGE algorithm retains the basic working cycle of the ACE algorithm - re­ peated execution of action determination, competition and credit assignment - but realizes competition in a different way. Now an agent estimates the e;oal relevance of an action not only in dependence on 1ts knowledge about the actual envuonmental state but also in depen­ dence on the possible activity contexts, and the agents do not compete for carrying out individual actions but for carrying out groups ofactions. Generally, an activ­ ity context is a group of mutually compatible actions. Formally, the set of all possible activity contexts in an environmental state S is given by

The competition is organized as follows (let S be the actual environmental state).

• (i) For each A E A[S] the agents calculate a bid B..4[S] for being allowed to carry out all the actions con­ tained in A by

with

where a is a risk factor, {3 is a noise term, and E{ [S, A] is A, 's estimate of the goal relevance of a{ in dependence on S, and A.

• (ii) The activity context A E A[S] being associated with the greatest bid B..4[S] is selected, and all actions contained in this context are carried out.

Credit assignment is done analogously to the ACE al­ gorithm (suppose that the activity context A has been selected):

• (i) For each a{ E A the agent A, modifies its estimate Ef [S, A] according to

• (ii) The total bid B..4[S] is distributed among the ac­ tions that were carried out in the previous competi­ tion. Suppose that Tis the previous environmental state and that B is the previously selected activity context. For each a~ E B the agent A.1: increases EUT,B] by

Like the ACE-type adjustment does, this AGE-type ad­ justment of the estimates induces the stabilization of suc­ cessful sequences of action sets and to the destabilization of unsuccessful ones.

3 Experimental Results

Task Domain. As a task domain the blocks world is chosen. This domain is clearly enough for experimental studies in an unknown field like collective learning, and it is well suited for illustrating the essential features of the ACE algorithm and the AGE algorithm.

The task to be solved by the agents is to transform a start confi~uration of blocks into a goal configuration within a lim1ted time interval. Figure 2 shows· such a task together with the actions that can be carried out by the ae;ents. In this example each agent is assumed to have hmited motor capabilities and to be ·specialized in moving one specific block; for instance, agent A1 is responsible for block A, and is able to J;>Ut this block on block B (put(A, B)) or on the ground (put(A, 1.)). The precondition for the application of an action put(x, y) is that the blocks x and y are empty, i.e. that no other blocks are placed on them. {Note that an agent's action is quite complex and involves a number of activities; for instance, in order to put A on B the agent has to walk to A, to pick up A, to walk to B, and to place A on B.)

Each agent 1s assumed to have limited sensor capa­ bilities (it only "sees" what is directly relevant to its actions) and, as a consequence, to have only local infor­ mation about each environmental state. The part S, of an environmental state S that is known to an agent Ai is specified as follows. For each of its actions a{ = put(x, y) an agent only knows {i) the block on which z E {x, y} is positioned and {ii) whether z E { x, y} is empty. The knowledge specified by (i) and (ii) is called the environ­ mental context of the action put(x, y).

Furthermore, two actions are considered to be in­ compatible if the execution of one of them changes the environmental context of the other. Formally, this can be expressed as follows: two actions, put(x, y) and put(u, v), are incompatible if x E {u, v} or u E {x, y} or 11 = v ~ .l. Examples of sets of incompatible actions are {put(.B, C), put(B, D)} ("a block cannot be put on dif­ ferent blocks at the same time"), {put(D, C),put(E, C)} ("two different blocks cannot be put on the same block at the same time"), and {put( E, B), put( B, C)} ("a block cannot be put on a block which at the same time is put on another b'lock"'). It is assumed that the agents know these incompatibifity constraints.

As it is described in section 2, learning proceeds by the repeated execution of the basic working cycle. A trial is defined as any sequence of at most four cycles that trans­ forms the start into the goal configuration (successful trial), as well as any sequence of exactly four cycles that transforms the start into a non-goal configuration. At the end of each trial the start configuration is restored, and it is again presented to the agents. Additionally, at the end of each successful trial a non-zero external reward Rez:t is provided.

Task Analysis. As a consequence of the local information constraint, an agent may be unable to distinguish between environmental states in which its actions are useful and relevant to goal attainment and environmen­ tal states in which its actions are useless. (This situation is sometimes called the Sussman anomaly.) Consider the environmental states T, U and V shown in figure 3. Based on the usual blocks world notation, these three states are completely described by

• T {on(A, .L), on(B, C), on(C, .L), on(D, E), on(E, .L), empty(A), empty( B), empty( D)} ,
• U ·{on(A, .L), on(B, D), on(D, .L), on(C, .L), on(E, .L), empty(A), empty( B), empty( C), empty( E)} and
• V = {on(A, .L), on(B, C), on(C, D), on(D, .L), on(E, .L), empty(A), empty( B), empty( E)}

As it is easy to see, the action put(A 1 B) of the agent A1 is useful in state T but not usefulm state V. How­ ever, because A1 's local information 7i. and V1 about the states T and V, respectively, are identical, the agent A1 is unable to distinguish between these two states. (Of course, an agent does not always fail to distin­ guish between "useful and useless states"; see e.g. the states T and U. A1 's local information is given by T1 = V1 = {on(A, .L), on(B, C), empty(A), empty(B)} and U1 = {on(A, .L), on(B, D), empty(A), empty( B)}.)

An analysis of the search space of the task depicted in figure 2 shows that there are only 3 successful tri­ als of length 3, and 13 successful trials of length 4. The probability that a randomly generated sequence of applicable sets of compatible act10ns transforms the start into the goal configuration is 2.6 percent, if the sequence has the length 3, and 3.3 percent, if the se­ quence has the length 4. With that, the probabil­ ity that a random trial solves the task to be learnt is less than 6 percent. (An example of a successful trial of length 3 is given by ( {put(C, .L),put(E, .l)}, {put(B C),put(D, E)}, {put( A, B)}). Note that a se­ quential "one-action-per-cycle" approach would require five cycles in order to implement this sequence.)

Experimental Results. A series of experiments was performed to test the ACE and the AGE algorithm. Figure 4 shows the performance profiles of the ACE algo­ rithm, the AGE algorithm, and a random walk algorithm (i.e. an algorithm which randomly chooses an applicable set of compatible actions in each cycle) . The parameter setting underlying these performance profiles was as fol­ lows: Einit = Rez:t = 1000, a= 0.1 , f3 E [-a/5 ... +a/5] (randomly chosen), and e = 0.7 · Einit . (It has to be mentioned that the learning effects reported below can be observed for a broad range of parameters and are not limited to this setting.) Each data point in figure 4 reflects the average external reward per episode ob­ tained during the previous 50 episodes, There are sev­ eral important observations. First, the ACE and the AGE algorithm performed significantly better than the random walk algorithm, and they reached their max­ imum performance level after about 250 trials. After that, the performance levels remained almost constant; this shows that the ACE/ AGE algorithms were able to learn stable sequences of action sets. Second, the performance level of the AGE algorithm is clearly above the performance of the ACE algorithm. This illustrates the Importance of estimating the goal relevance of an action, as it is done by the AGE algorithm, in dependence on other (concurrent) actions. The reason for that is that an action may be useful in one activity context but use­ less in another. However, the improved performance is achieved at the cost of higher space and computation time: whereas the costs of the ACE al~orithm are pro­ portional to the number of possible actiOns that can be carried out by the agents, the costs of the AGE al~o­ rithm are proportional to the number of {>OSSible actiOn sets. And thirdbdespite their learning abilities both algo­ rithms remain elow the possible maximal reward level (which is 1000). The reason for that is the local infor­ mation constraint and, with that, the inability of the agents to distinguish between all different environmen­ tal states; as a consequence, the same estimates are used for different environmental states and necessarily remain inaccurate on some scale.

4 Concluding Remarks

This paper took the first steps towards learning to coor­ dinate actions in multi-agent systems. Two algorithms called the ACE algorithm and the ACE algorithm for the delayed reinforcement learning of sequences of action sets were introduced and experimental results illustrating the learning abilities of these two algorithms were presented. Both algorithms are "elementary" in a twofold sense. On the one side, they make only weak demands on the cog­ nitive abilities of the individual agents. For instance, they do not require that the agents are able to reason about the other agents' knowledge or intentions and they do not require that the agents possess complex decision making strategies. As a consequence, the algorithms are even applicable to systems that are composed of rather simple a~ents. On the other side, both algorithms are very flexible learning schemes that can be extended in a number of ways. For instance, they allow to incor­ porate high- level problem solving and planning mecha­ nisms known from the field of single- agent systems, as well as a number of refinements that have been proposed for the bucket brigade learning model (e.g., tax payment, support and look- ahead mechanisms) .

Our future research will concentrate on these possible extensions of the ACE/ AGE algorithms. A major topic is the development of algorithms that implement multi­ agent learning of sequences of compatible actions like the ACE/ AGE algorithms do, but that better cope with the local informatiOn constraint.

Another goal of future research is the development of learning algorithms for more complex structured (e.g. hi­ erarchically organized) multi-agent systems [Fox, 1981] . Up to now this toP-ic has been not addressed in the field of distributed artificial intelligence. However, there are various related works from other disciplines like psychol­ ogy (e.g., [Guzzo, 1982; Laughlin, 1988]) and economics (e.g., [Argyris and Schon, 1978; Galbraith, 1973; Hed­ berg, 1981; Sikora and Shaw, 1989)) that are likely to be very stimulating and useful for achieving this challanging goal.