Multi-Agent Planning as a Dynamic Search for Social Consensus

1 Introduction

The field of Distributed Artificial Intelligence (DAI) is concerned with coordinated, efficient activity by groups of autonomous agents. Activity in multi-agent worlds often requires agreement by the agents as to how they will act, and the reaching of consensus is a major con­ cern of DAI. The formation of multi-agent plans has been approached in several different ways: throue;h the use of synchronization techniques [Georgeff, 1984J, such as those used in operating systems, through the distri­ bution of single-agent planners [Corkill, 1979], such as NOAH, and through centralized planners that ensure co­ ordination [Rosenschein, 1982] .

*This research was partially supported by the Israeli Min­ istry of Science and Technology (Grant 032-8284)

In this paper, we present a new approach to deriving multi-agent plans. We consider how agents could reach consensus using a voting procedure, without having to reveal full goals and preferences (unless that is actually necessary for consensus to be reached). Our technique also does away with the need to generate final alterna­ tives ahead of time (instead, candidate states arise at each step as a natural consequence of the emerging plan) . The agents iteratively converge to a plan that brings the group to a state maximizing social welfare.

2 The Scenario

Our scenario involves a group of n agents operating in a world currently in the state s0 . Each agent has its own private goal. Since all agents operate in the same en­ vironment and may share resources, it is desirable that they agree on a joint plan for the group that will trans­ form the world to an agreed-upon final state.

Each agent is assumed to have a value, a worth , that it associates with states that satisfy its goal. This worth can be used to assign a utility to any state, goal or not, that is reached by a particular plan (the techniques for doing this assignment are discussed below) .

Given the existence of such a worth function, we want to give the agents a method for choosing a group plan . The agents will all participate in the choice process, as well as in carrying out the resulting multi-agent plan. The group plan should then result in a compromise state that is in consensus. 1

2.1 An Example

Consider a simple scenario in the slotted blocks world. There are four slots (a, b, c, d) , five blocks (1,2,3,4,5), and the world is described by the relations: On( Ob)l, Obh)- Obj1 is stacked onto Obh; Clear(Obj)-there is no object on Obj; and At(Obj, Slot)- Obj is located at Slot . The function loc(Obj) returns the location (slot) of Obj. Slots them­ selves function as (stationary) objects (e.g., block 1 in slot b could be described by On( 1, b)).

1 The decision procedure, to be presented below, may also serve in a single-agent planning scenario, where an agent is trying to integrate a group of disparate goals.

There are three agents operating in the world. The start state is shown at the far left of Figure 1. As fur­ ther represented in that figure, these agents have (re­ spectively) the following goals: g1 ={At(4, c),At(2, b)}, 92 ={ On(2, 4),0n(5, 2)}, 93 ={ On(3, 2), At(2, c)}, with respectively the the individual worths: 8, 12 and 16.

There is only one available operator: Move( Obi!, Obh)-place Obj1 onto Ob}2. This operator can be char­ acterized by the following STRIPS-like lists: [Prec: Clear(Obj!), Clear(Ob}2), On(Ob}J , ObJx)J, [Del: On(Obj1, Objx), Clear(Ob}2), At(Obj1 ,lac(Ob}J))],

[Add: On(Ob}J, Ob}2), At(Obj1,1ac(Ob}2)))].

Assume that when a single agent performs the M ave operation there is a cost of 4, while if two agents M ave an object together the operation costs a total of 3 ( 1.5 each).

We want the agents to jointly choose a plan that re­ sults in a compromise state.

3 General Overview of the Process

The algorithm enables a group of agents to find the state that maximizes their social welfare function fu. There are many possible global utility functions , such as tak­ ing the product of individual agent utilities , or taking their median, or taking their sum. Our procedure here is not dependent on any particular function , and is equally suitable regardless of the one chosen. Given the set of individual utility functions of the agents in the decision group, we define the Social Welfare/Utility U(E) (of any set of constraints E) to be that function fu of all the individual worth functions , minus the cost of achieving the set from so (that is, U(E) equals fu minus the cost of achieving E).

The underlying idea is the dynamic generation of al­ ternatives that locates the mpst desirable state for the society. At each step , all agents reveal additional in­ formation about their private goals. The current set of candidate states is then expanded and (possibly) pruned to comprise the new set of candidate states. The process continues until all newly formed sets of constraints have lower social utility than their ancestor sets. Note that our primary concern here is not with the complexity of the planning process but rather with the resulting state of the multi-agent plan .

The search procedure needs an accurate value for the social utility of each candidate state in order to proceed correctly (i.e. , the search space of alternatives is dynam­ ically pruned by the social welfare criterion). To provide this value , the agents vote over the set of candidates at each step.

The search method combines aspects of hill-climbing with breadth-first search. For example, parallel searches are carried out in each promising direction (where so­ cial utility is growing or constant within the gap bound \Ju 2 ). When the search encounters a direction where social utility decreases beyond this limit, however, the search is terminated (reminiscent of hill-climbing).

The procedure has the following advantages: (a) al­ ternatives are generated by the entire group dynami­ cally (allowing the procedure to be distributed [Ephrati and Rosenschein, 1993]); (b) utilities will be calculated and submitted only for "feasible" alternatives (utilities of infeasible alternatives need not be revealed, reducing the choice procedure's computational complexity, and also respecting agent privacy when possible lEphrati and Rosenschein, 1992b]); (c) agents are required to sub­ mit only the minimally "conflict-sufficient" information about their goals (described below), further maintaining their privacy.

3.1 Definitions

• e(g;) is the set of absolutely necessary constraints needed for any optimal plan to achieve the goal g; , starting at the initial state so. In accordance with the partial order over these constraints, 3 we divide e(g) into subsets of constraints. Each such subset within e(g) comprises all the constraints that can be satisfied within j (optimal) steps, and are necessary at some subsequent step after j. The total number of operators (the length of the plan) that satisfies the set of constraints e(g) is denoted by l(e(g)) .

We denote e(g)'s components by Ui Et, such that Ei includes all the constraints that can be satisfied within j steps, and are necessary at some step 2: j. For any j 2: l(e(g)) , we define Ei to be the description of the goal g.

Example: In the blocks world scenario from Sec­ tion 2.1, e(gl) for Agent 1 would be: E1 [C(2), C(4)](= Ei) u [C(4) , A(2, b)](= E?) u [A(4, c), At(2, b)](= Ef)

• A constraint I E Ei is said to be temporary if later in the plan there is a copstraint l E Ek (where k > j) that denies it (I 1\ I I= False)· We say that a set of apparently conflicting constraints E is semi­ consistent (E ~tmp False) if the removal of tempo­ rary constraints makes it consistent (see Section 4.1 for an example). Given a semi-consistent E we de­ fine r( E) to be the set of all maximal consistent subsets of the predicates in E.
• P( E) denotes the set of the cheapest "grounded" (or "complete" [Chapman, 1987]) plans that achieve the final subset of E. We denote these states by s(E) ( = { s I ( s I= E 1 (E)) 1\ c( so ~ s) = minki=E'(El c( so ~ k)} ).

2 Given fu and the agents' utility functions, we define the gap bound '\ju to be the maximal gap between any local maximum of fu and any local minimum that follows it.

3 Constraints are temporally (partially) ordered sets of the domain's predicates associated with the appropriate limita­ tions on their codesignation.

• Follow (E) is defined to be the set of constraints that can be satisfied by invoking at most one operator, given the initial set of constraints E (Follow(E) = {I l3op3P[op(P(E)) f: I]}).

4 The Algorithm

This section describes the algorithm in more detail along with a running example. At each step of the pro~edure, agents try to impose more of their private constraints on the group's aggregated set of sets of constraints. Since agents want to maximize their own utility, they will im­ pose as many constraints as they can at each step. The set of all non-pruned aggregated sets of constraints at step k is denoted by Ak (its constituent sets will be de­ noted by Aj, where j is simply an index over those sets). Ak+ denotes the set Ak before it is pruned (similarly, its non-pruned components are denoted by Ak+).

As an example, assume a simple scenario of th~ slotted blocks world (we use the same operators and predicates as described in Section 2.1). There are 3 blocks (1,2,3) and two agents (a1 , a2 ). The initial state is {On(1, b), On(3, 1), On(2, c)}. The agent's goals are (respectively) 91 = {On(1, 2)} and 92 = {On(2, 3)}. 4 The exact procedure is defined as follows:

1. At step 0 each agent i finds e(g;)-the individual temporally ordered set of constraints that achieves the goal g;, starting from the initial state. The vir­ tual set of alternatives is initialized to be the empty set (A 0 = 0).

In our example, we have: 5 e(91 ) = {[C(2)] U [C(2), C(1)] u[0(1, 2)]} (this ordered set induces the plan (M(3, 2), M(1,2))) and e(92) = {[C(3),C(2)]U(0(2,3)]} (inducing the plan (M(2, 3)) ). Note that C(2) and C(3) are tempo­ rary since they are denied later in the plan .

• Ak 2. At step k, each agent may declare E. ; C E 1 +1 only . - . if any k :5 I Ef was already declared and accepted by the group, and the declaration is "feasible," i.e., it can be reached by invoking one operator on some set of constraints that was reached by the proce­ dure during the previous step: 3Aj[(Aj E Ak)t\

(U~=l E! ~ AJ)A (E:~ ~ Follow (Aj))] . i can try to impose elements of his "next" pnvate subset of constraints on the group decision only if they are still relevant and his previous constraints were ac­ cepted by the group.

At the first step, each agent i may declare E~ . In our example, this will be E~, = [C(2)] and E~~ = (C(J), C(2)].

At the second step, a1 declares E:~, which in this example equals E~, = (C(2), C(1)]. Similarly, a2 declares E~~ = (0(2, 3)] . (Both are in Fouow(A 1 ), which contains only one subset.) At the third step, a1 declares (0(1, 2)] and a2 declares (0(2, 3)] (his final goal, which is already in A 2 ) .

4 This is reminiscent of Sussman's Anomaly in the single­ agent planning scenario-where the plan to achieve one sub­ goal obstructs the plan that achieves the other. The exam­ ple assumes that although the final state that satisfies both agents' goals costs 9 to reach, it is the state that meets the social welfare criterion.

5 yYe will use the ·first letter to denote the full operator predicate, and fi to denote any location excluding y's. We also use a typewriter font to denote temporary constraints.

1. For each set of constraints A~ E Ak, we generate all the maximal consistent or s'emi-consistent exten-. (k+l)+ . A(k+l)+ swns {Ai } with elements of U; E; 1 (i .e. , each element in AJk+l)+ is defined as {A~U {I I (IE (k+l)+ J U; E:; )A( (I U AJk+l)+) ~tmp Fal·e)}} ).

At the first step, the aggregated set of constraints is { C(3), C(2)} . At the second step, both declara­ tions may coexist consistently, and there is therefore only one successor to the previous set of constraints: { C(2), C(1 ), 0(2, 3)} . At the third step, the aggregated set is { 0(1, 2}, 0(2, 3)}, and it satisfied both agents' goals.

1. At this stage, all extensions are evaluated so as to enable the pruning of sets that reduce social utility. Each agent declares the utility it associates with each newly-formed set of aggregated constraints.

The first set of aggregated constraints is satisfied by the initial state, and thus induces the null plan (with cost of zero). The value given to that first set is the value that agents assign to the initial state. The second set can be achieved by the plan (M(3, a)) , with cost of 3. In order for the set not to be pruned, it must be the case that the agents value the set by at least 3 + ~u more than the initial set . The third set is the set that satisfies the social welfare criterion (by our assumption above), and therefore (by definition) will have higher value than previous steps (and not be pruned) .

1. The next set of sets of constraints is pruned so that it contains only sets that do not decrease the social utility (with respect to their ancestor set) by more than the gap bound \]u. Formally, Ak+ 1 = { AJ+ 1 I AJ+l E AJk+l)+ !\VI :5 k[U(AJ+ 1 ) ~ U(A})+\]u]} . In this simple example, all the individual extensions are mu­ tually consistent. Therefore, there is only one aggregated extension at each step. Since this set brings the agent closer to the set that satisfies the social welfare criterion, it is not pruned .
2. The process ends when Ak+l = Ak. The values assigned by each agent to each state in A k are then compared to find the consistent sets that maximize social utility (Ak ={A I A E Ak t\ 'VA*[A* E Ak => U(A*) :5 U(A)]}) . Among these equivalent sets, one is randomly chosen.

In the example there is only one such set-the final set which is determined in the fourth step.

Theorem 1 Given any social welfare function fu , and an appropriate gap bound \]u, this mechanism finds all sets that maximize the Social Welfare . Consensus will be reached after at most O(maxAI(P(A)) steps such that P(A) results in a state that maximizes the group 's social welfare.

Proof. The proof of this theorem, and the one below, appear in [Ephrati and Rosenschein, 1992a] with slightly different notations. o

4.1 Constraints

There are several important aspects of, and requirements for, the procedure above to succeed, which we discuss in this section. Figure 2 shows three simple scenarios in the slotted blocks world that will help us explain the issues involved. In these examples, two agents can achieve a consensus state that fully satisfies both agents' goals. There are three slots, and several blocks in each world. Only the Move operator is available, and it costs 2 under all circumstances.

Figure 2: Three scenarios in the slotted blocks world

4.1.1 Specification of Constraints

An important requirement for the success of the pro­ cedure is that each agent identify and declare only the absolutely necessary constraints needed for its in­ dividual plan to succeed. As an example, consider the first scenario in Figure 2. Two agents want to achieve the following goals: 91 = {A(1 , a), C(1)} and 92 = {0(3, 2),A(2,b)}. These two goals can co-exist, as shown in the final goal state. To achieve his goal, a1 need not take any action. a2, on the other hand, has to carry out (M(2 , x),M(3, 2),M(2, b) ,M(3 , b)) . The only way for the second step of this plan to be completed is by stack­ ing either block 3 or block 2 onto block 1. By including either of these into his set of constraints, a2 would en­ counter a1 's opposition, thus (perhaps) preventing his own goal from being achieved .

However , the purpose of the second Move operator is just to achieve A(3, b). If a2 declares his set of constraints to be [C(2)]u[C(2), C(3)]u[C(2), C(3), A(3, b)]U[C(2), C(3),A(2, b)]U[A(2, b), 0(3, 2)], the conflict is avoided.

4.1.2 Aggregation of Temporary Constraints

In the second scenario, a1 's goal is the same, but a2 's goal is now {0(5, 4),0(3,2) ,A(2,b) ,A(4,b)}. As in the previous example, there is no way for him to achieve his goal without trying to temporarily violate a1 's goal. But in contrast to that example, there is no way to specify a2 's constraints in a way that would avoid the conflict. Here, for example, A(2, b), although temporary, is crucial for a2 's plan 's success. Were the process to consider sets of constraints to be relevant only as long as they were consistent, the process might stop after two steps, avoiding the goal state from even being considered.

[t is therefore necessary that the temporary conflicts between the agents' plans not cause deadlocks (that is, if there is a temporal order that can later resolve them). This phenomena is achieved by allowing the existence of semi-consistent sets of constraints, and having agents ex­ press preferences over these sets. For that reason, agents should recognize what their temporary constraints are (terms that will be violated by their own future ac­ tions). Identifying the temporary constraints of his own plan, a2's set of constraints (E2) would then become: [C(2)] U (C(2), A(2, b)] U [A(2, b),C(4), A(3, ~b)] U [A(2, b) , C(4), A(3 , ~b) , C(S) , A(4 , b)] U [A(2, b) ,C(4) , A(3 , ~b) , C(S) , A(S, 4b)] U [A(2, b) , C( 4), A(3, ~b), C(S),A(S, 4b), C(2) ,A( 4, b)]U[A(3, ~b),C(2), A(4, b),0(5, 4),C(3)]U[C(2),A(4, b), 0(5, 4),C(3), A(2, b)]U[A( 4, b),0(5, 4), 0(3, 2),A(2, b)] As can be seen in this specification, all the constraints that contradict a1 's goal are temporary. Therefore, even though a2 's plan actually violates a1 's goal, the mutual goal state is reachable.

4.1.3 Aggregation of Functional Constraints

The generation of consensus sets of constraints is based on the aggregation of the individual sets of con­ straints. As the third example in Figure 2 shows, this is not always trivial. Here, there is a ceiling that makes it impossible for more than two blocks to be stacked . This time a1 's goal is A(l, b) while 92 = A(4, b). We assume that the function h(b) returns the height (in number of blocks) at slot b. As in all our scenarios, s0 satisfies Ef of both agents. 6 Following the second step of his plan, each of the agents has as temporary constraints h(b) :::; 1 and C(x), where xis the block he wants to move onto slot b. These constraints enable each agent to move "his" block to slot b after removing block 2.

The aggregation of these constraints requires careful analysis. First, it must be recognized when the aggre­ gated constraints of two identical terms such as h( x) :::; 1 will be h(x) :::; 2, or h('x) :::; 1, or even h(x) :::; 0. Had block 4 been located on block 1 in the initial state of our example, the third solution would be appropriate. Using it in the given scenario, however, would yield as the aggregated set of constraints in the second step [C(1), C(4), h(b):::; 0] . The induced states of this set cost 10 move operators, while the actual plan that achieves the mutual goal costs only 5. The problem here is that both constraints are temporary (each agent needs a free space for one block only momentarily). Thus, in this case, the aggregated height should stay 1, leading to a state that is only three Move steps distant from the ini­ tial state. Unfortunately, it not clear how in general this subtle analysis is to be done.

4.1.4 Evaluation of Sets of Constraints

Evaluation of sets of constraints plays an important role in the search procedure. One straightforward worth function for an arbitrary set A might be built by tak­ ing the worth of a goal state (assumed to be available) , subtracting the cost of the single-agent plan from A to the goal, then subtracting the agent's share of the cost of the multi-agent plan to get from start state s0 to A.

Note, however, that using the above equation the worth of so for an agent would simply be the worth of his goal, minus the cost of his one-agent plan to reach that goal (in a one-agent scenario this would be true for every set). Thus, since the evaluation function does not capture the notion of progress in the plan, the agent has no motivation to carry out his plan at all.

There are several ways to refine the worth function so as to solve this problem. One way is by making the

6 El = [C(l),C(2),h(c) ~ 1] and E~ =[C(4),C(2) ,h(a) ~ 1]. Note that by its nature, the height constraint is tem­ porary, since it always is a precondition of an action that violates it!

"future-cost" (i.e., w;(g;)- c;(A""" g;)) more sensitive to the progress of the plan. A simple approach is to take into consideration only that fraction of the goal's worth which reflects the amount of work already done to achieve it (~ w;(g;) x [l(P(s0 """ A))/l(P(A """ g;))], which is meaningful only if w;(g;) > c;(so """ g;)). Another way is to give greater weight to the cost of operators that are located further along in the plan (~ w;(g;)- 2:::~ k x C(opk)). Or, assuming that each op­ erator has a probability (pr( opk)) associated with its success, we could use ~ (IJ~ pr( opk) x w;(g;))- c;(A""" g; ). These evaluations may be further refined by having weighted costs and/or probability of success associated with each of the constraints that needs to be achieved in order to transform the given set into the goal set (see [Haddawy and Hanks, 1990] and [Kanazawa and Dean, 1989] for richer probabilistic approaches).

Note that instead of assigning worth to sets of con­ straints, it may sometimes be more natural to evaluate their induced states (s(A) instead of A). In any case, the worth associated with all states induced from a single set of constraints will be equivalent. In addition, note that for many variations of the above worth functions, it will be sufficient to take the gap bound \]u to be zero (what was called a progressive worth function in [Ephrati and Rosenschein, 1992a]) . For example, it would be sufficient to assume above that \t'ic(A1 """ A2 ) :S c;(s1 """s2 )) .

5 Manipulative/Insincere Agents

In choosing a state that maximizes social welfare, it is critical that agents, at each step, express their true worth values. However, if our group consists of autonomous, self-motivated agents, each concerned with its own util­ ity (and not the group's welfare), they might be tempted to express false worth values, in an attempt to manipu­ late the group choice procedure. This is a classic problem in voting theory: the expression of worth values at each step can be seen as an (iterative) cardinal voting proce­ dure, and we are interested in a non-manipulable voting scheme so that the agents will be kept honest. We have investigated other aspects of this problem in previous work [Ephrati and Rosenschein, 1992b] .

Fortunately, there do exist solutions to this problem, such that the above plan choice mechanism can be used even when the agents are not necessarily benevolent and honest . If the social welfare function is taken to be the (weighted) sum !fum (or average) of the individual util­ ities , it is possible to ensure that all agents will vote honestly. This is done by minor changes to the proce­ dure of Section 4, that allow it to use a variant of the Clarke Tax mechanism (CTm).

In [Ephrati and Rosenschein, 1991] we proposed the CTm as a plausible group decision procedure. The basic idea of the mechanism is to make sure that each voter has only one dominant strategy, telling the truth. This phenomenon is established by choosing the alternative that scores the highest sum of bids/votes and then tax­ ing some agents. The tax (if any) equals the portion of the agent's bid for the winning alternative that made a difference to the outcome. Given this scheme, revealing true preferences is the dominant strategy.

In our procedure, the agents are participating in many intermediate votes, and alternatives are generated dy­ namically (as a consequence of the intermediate votes). Therefore, the original version of the CTm cannot be used efficiently. Instead we use an iterative variation of the CTm; at each step, the tax is defined with respect to all previous steps, but is actually levied only at the final step. We use the following definitions for the stepwise Clarke tax mechanism:

• The function v; : A --+ IR, returns the true worth (to a;) of each aggregated set A. Similarly, the function df (j) returns the declared worth of the set Aj by agent a; at step k . d} denotes the vector (df(1), .. . , df(m)), the agent's declared worth over all alternatives and v} denotes the true value.
• The profile of preferences declared by all agents at step k is denoted by D~, where D~; denotes this set excluding i's preferences, such that D~ = (D~;, d}) .
• The choice function f : D~ x A --+ A returns the state that is the maximizer of 2:::7=1 df(A);
• The tax imposed on i at step k is tf (!( D~)) = I:#i dj(f(D~; ))- I: iii dj(f(D~;, d})), if this value is positive. Otherwise, tf will be zero. There­ fore , the utility uf (!( D~)) of agent i with respect to the chosen alternative is w;(f(D~))- tf(f(D~)).

The planning algorithm itself should also be updated in two ways . First , since each intermediate vote is only over a subset of candidates, there is the possibility that an agent will "shift" his vote by a constant , keeping a single round's preferences accurate while undermining inter-vote comparisons. To maintain truth telling as a dominant strategy, it is necessary that artificial shifting does not occur. Therefore, we will require that all votes be relative to some "benchmark": we include A 0 (the empty set) in the set of alternatives at every step . If each agent is motivated to give his true preferences over the other states relative to A 0 ( v; (A J), then the score of each state s in the vote is exactly f.um (A).

Second, the tax is calculated with respect to the final choice. Knowing that a semi-consistent set cannot be chosen, an agent might give it an artificial value in order to change the final outcome. We therefore allow agents to vote only over consistent sets. Step 4 of the algorithm is therefore changed as follows :

• For each A E A(k+l)+ \ Ak find r(A), its maxi­ mal consistent subsets. Each agent gives its vote regarding each state in r( A) U A 0 . The worth of a consistent set is simply the sum of individual worths given to that state (note that for any consistent set A, r(A) = A). The worth of each semi-consistent set in A(k+l)+ is computed as follows: for each agent and semi-consistent set A, there is a consis­ tent set with maximal worth in r(A) . The worth of a semi-consistent set is taken to be the sum of these maximal worth sets in r(A), over all agents (2:::; maXEEr(A) w;(E)).

At the and of the process, each agent is fined the Clarke Tax with respect to the final group choice.

Theorem 2 At any step k of the procedure, i 's best strategy is to vote over the alternatives at that step ( Ak) according to his true preferences vi.

5.1 Using the Procedure on Our Example

We now use the iterative procedure with its CTm to solve the first problem presented in Section 2.1. We assume that the cost of reaching a state is divided equally among the agents (by side-payments if necessary), and that each agent i uses the worth function Wi(A) = wi(Ui)­ c; ( s( A) --... g;) (the goal's worth minus the cost of the work needed to transform a state induced by the set to the goal state) . From the agents' individual goals, we get the following constraints:

E1 [C(2), C(4)](= E 1 ) U [C(4) , A(2, b)](= Ef} U [A( 4, c), At(2, b)](= E~fl E2 = [C(2) , C( 4)] U [c( 4) , C(2) , C(5)]U[C(2), C(5), 0(2, 4)]U[0(2, 4), 0(5, 2)] E3 [C(2)] U [C(2), C(3)] U [C(2) , C(3), A(3, ~)] U [C(2) , C(3), A(2, c)] U [A(2, c), 0(3, 2)] '"' r-~---~�~ l--~- --~i�.'>l -t~----;,�sl r-~-;-.<2.~

At the third step, the new added constraints generate 3 possible maximally consistent extensions: A~ =[A(2, b), A( 4, c), C(2), C(5), C(3), A(3, c)] inducing s2, A~ =[0(2, 4), A(2, b),C(2), C(5), C(3), A(3, c)] induc­ ing s3 , and A~ =[0(2, 4), A( 4, c), C(2), C(5),C(3), A(3, c)] inducing s4 and s5 . These induced states respectively score 11, 3, 12, and 12; A~, which decreases the social utility, is therefore pruned.

At the fourth step, the two remaining extensions are extended further; a1 hands in {A(2,b),A(4, c)} (which is in Follow (A~)), a2 hands in { 0(2, 4), 0(5, 2)} and a3 { C(3), C(2) , A(2, c)} (both in Follow (A~)). These con­ straints yield six different extensions that again induce the states s2 , s 3 , s4 , s5 and the new states S6 and s7 (that score respectively -5 and 5). Therefore, only the sets that induce s4 and s5 can be further extended (by a3 ) to induce s8 . Although s8 fully satisfies a3 's goal, it scores only 5 and the process ends.

All intermediate votes are now gathered for the final vote. Both s4 and s5 maximize the social welfare utility (both are one operation distant from each of the agents' goals). Both a2 and a3 are taxed 2. a2 improves its utility by 2 and a3 by 6 ( a1 's utility is not improved with respect to s0 ) . The group's social utility is therefore improved by 8.

E~~---~2.~ 6

Related Work

_ biJ ~ ~ : There are a number of artificial intelligence researchers · ·~ · -~ whose work relates to the approach we have been discussing above. Some of this work follows in the foot­ steps of Korf [Korf, 1987], who showed that the plan­ ning search space can be reduced if the final goal can be decomposed into several sub-goals, and the plans that achieve these sub-goals can be combined to achieve the original goal. This result suggests that the multi-agent planning algorithm presented in this paper can also serve to reduce the search space in a single-agent planning sce­ nario if a non-optimal solution is acceptable.

' -'-·-L-'-·-~---'--'-'-!... 1

'--'-· ' ·

Figure 3: Induced States of the Five Steps

Figure 3 presents the induced states at each step (in this example, all the generated sets are consistent). At the first step, each agent declares El . A 1 , the set that includes all possible consensus sets of constraints, has only one member : A} = {[C(2), C(4)]}. s(AD also has only one member, s0 . Agents then vote on this state, and it receives a score of 0 (for example, a2 goal's worth is 12, and to achieve it the agent would perform (M(4, c),M(2, 4) ,M(5 , 2)) at a cost of 12; therefore, he values so as 0) .

At the second step, each agent hands in E[ (which is in Follow (A}) for each i) . Since all these constraints coexist consistently, A 2 =[C(2) ,C(4) ,C(5) ,C(3),A(2, b)] . This set induces the single state s1 (= s(Ai)) as de­ scribed in Figure 3. Note that there are many other states that could satisfy this set of constraints, but s1 has the minimal cost. This state can be achieved by (Move(4,a),Move(2, 1)); therefore, the state costs 6. Subtracting this cost from the worth values given by each agent (4 in this case by all three agents), the state scores 6. Since this score is greater than that of the preceding state s0 , the process continues.

7 a1 's plan might be (M ove(2, 1) , Move( 4, 3)) . The first operation is enabled since the constraint C(2) is satisfied. Th C(2) constraint is satisfied by so, which is included in Ef . C(4) is needed for a future operator, but it is also satisfied by so, and therefore it too is included in Ef. A(2, b) can be satisfied within one move, and is necessary at all future times for the plan to succeed, so it is included in any future set of constraints.

A similar approach is taken in [Nau et al., 1990] to find an optimal plan. It is shown there how planning for mul­ tiple goals can be done by first generating several plans for each subgoal and then merging these plans. Finding the solution is guaranteed (under several restrictions) only if a sufficient number of alternative plans is gener­ ated for each sub-goal. Our approach does away with the need for several plans for each subgoal by using con­ straints instead of grounded plans (a level of abstraction that represents all possible grounded plans).

In [Foulser et al. , 1992] it is shown how to merge grounded linear plans (as opposed to aggregating con­ straints) in a dynamic fashion. To achieve an optimal fi­ nal plan it takes that algorithm O(TI7= 1 l(P(gi))), while the approximation algorithm that is presented there takes polynomial time.

Our approach also resembles the GEMPLAN sys­ tem [Lansky, 1990]. There, the search space ofthe global plan is divided into "regions" of activity. Planning in each region is done separately, but an important part of the planning process within a region is the updating of its overlapping regions (in our terms, all individual plans are generated and aggregated simultaneously). This model served as a basis for the DCONSA system [Pope et a/., 1992] where agents were not assumed to have complete information about their local environments. The com­ bination of local plans was done through "interaction constraints" that were pre-specified.

The concept of solution that our algorithm employs (maximization of social welfare) also resembles the ap­ proach taken in CONSENSUS [Clark et a/., 1992] where several expert systems "elect" a plan that scores the highest rating with respect to the individual points of view. There, however, the election refers to different complete global plans that each expert generates.

Another advantage of our proposed process is that it can easily be modified to deal with dynamic priori­ ties. Since the search is guided by the vote taken at each step, it is possible to allow the agents to change their "tastes" or priorities over time (for example, due to environmental changes). As an example, in the Multi­ Fireboss Phoenix system [Moehlman and Lesser, 1990] planning (the actions needed to assess and contain fires) IS performed by several spatially distributed agents. The system addresses, through a sophisticated negotiation protocol, the dynamic allocation of resources. Our al­ gorithm would solve this problem in a direct manner without negotiation . At each time interval , the agent~ would vote over the possible relevant distributions (one step of the algorithm per time interval) . Given the in­ dividual utilities, the accurate distribution of resources would be chosen that maximizes the social utility (mini­ mizes the damage according to the group's perspective) . In addition (as mentioned in Section 5), there is no need to assume that the agents are benevolent .

7 Conclusions

We have introduced a new dynamic, iterative voting pro­ cedure. It enables a group of agents to construct a joint plan that results in a final state that maximizes social welfare for the group. The technique is more direct and formally specified than other consensus procedures that have been proposed, and maint~ins agent privacy more effectively. Techniques such as these provide a natu­ ral method for the coordination of multi-agent activ­ ity. Conflicts among agents are then not "negotiated" away, but are rather incrementally dealt with. Agents iteratively search for a final state that maximizes the entire group's utility, incrementally constructing a plan to achieve that state. The search can be constructed so that any manipulation by an untruthful agent will harm the agent more than it helps him.

References ·

• [Chapman, 1987] D. Chapman. Planning for conjuctive goals. Artificial Intelligence, 32:333-377, 1987.
• [Clark et al. , 1992] R. Clark, C. Grossner, and T. Radhakr­ ishnan. ONSENSUS: a planning protocol for cooperat­ ing expert systems. In Proceedings of the Eleventh Inter­ national Workshop on Distributed Artificial Intelligence, pages 77-94, Glen Arbor, Michigan, February 1992.
• [Corkill, 1979] D. Corkill. Hierarchical planning in a dis­ tributed environment. In Proceedings of the Sixth Inter-
• national Joint Conference on Artificial Intelligence, pages 168- 175, Tokyo, August 1979.
• [Ephrati and Rosenschein, 1991] E. Ephrati and J. S. Rosen­ schein. The Clarke Tax as a consensus mechanism among automated agents. In Proceedings of the Ninth National Conference on Artificial Intelligence, pages 173-178, Ana­ heim, California, July 1991.
• [Ephrati and Rosenschein, 1992a] E. Ephrati and J. S. Rosenschein. Multi-agent planning as search for a consen­ sus that maximizes social welfare. In Pre-Proceedings of the Fourth European Workshop on Modeling Autonomous Agents in a Multi-Agent World, Rome, Italy, July 1992.
• [Ephrati and Rosenschein, 1992b] E. Ephrati and J . S. Rosenschein. Reaching agreement through partial revela­ tion of preferences. In Proceedings of the Tenth European Conference on Artificial Intelligence, pages 229-233, Vi­ enna, Austria, August 1992.
• [Ephrati and Rosenschein, 1993] E. Ephrati and J. S. Rosen­ schein. Distributed consensus mechanisms for self­ interested heterogeneous agents . In First International Conference on Intelligent and Cooperative Information Systems, Rotterdam, May 1993. To appear.
• [Foulser et al., 1992] D. E. Foulser, M. Li, and Q. Yang. The­ ory and algorithms for plan merging. Artificial Intelligence, 57:143-181, 1992.
• [Georgeff, 1984] M. Georgeff. A theory of action for multi­ agent planning. In Proceedings of the National Conference on Artificial Intelligence, pages 121- 125, Austin, Texas , August 1984.
• [Haddawy and Hanks , 1990] P. Haddawy and S. Hanks. Is­ sues in descision-theoretic planning: Symbolic goals and numeric utilities. Technical report, University of Illinois at Urbana-Champaign, IL, 1990.
• [Kanazawa and Dean, 1989] K. Kanazawa and T. Dean. A model for projection and action. In Proceedings of the Eleventh International Joint Conference on Artificial In­ telligence, 1989.
• [Korf, 1987] R. E. Korf. Planning as search: A quantitative approach. Artificial Intelligence, 33:65- 88, 1987.
• [Lansky, 1990] A. L. Lansky. Localized search for controlling automated reasoning. In Proceedings of the Workshop on Innovative Approachess to Planning, Scheduling and Con­ trol, pages 115-125, San Diego, California, November 1990.
• [Moehlman and Lesser, 1990] T. Moehlman and V. Lesser. Cooperative planning and decentralized negotiation in Multi-Fireboss Phoenix. In Proceedings of the Workshop on Innovative Approaches to Planning, Scheduling and Control, pages 144-159, San Diego, November 1990.
• [Nau et al., 1990] D. S. Nau, Q. Yang, and J. Hendler. Op­ timization of multiple-goal plans with limited interaction. In Proceedings of the Workshop on Innovative Approaches to Planning, Scheduling and Control, pages 160-165, San Diego, California, November 1990.
• [Pope et al., 1992] R. P. Pope, S. E. Conry, and R. A. Mayer. Distributing the planning process in a dynamic environ­ ment. In Proceedings of the Eleventh International Work­ shop on Distributed Artificial Intelligence, pages 317-331, Glen Arbor, Michigan, February 1992.
• [Rosenschein, 1982] J. S. Rosenschein. Synchronization of multi-agent plans. In Proceedings of the National Confer­ ence on Artificial Intelligence, pages 115- 119, Pittsburgh, Pennsylvania, August 1982.