Flexible Social Laws

1 Introduction

As automation of intelligent tasks increases, the need will arise for heterogeneous agents working in a common environment. As a result, agents will need to plan and coordinate plans in real time.

[Cook, 1994] has described three methods of handling multiple agents: central control, distributed control, and local control (no communication). She notes that central control is effective when communication is reli­ able, and local control is effective if no communication is needed; otherwise, distributed control is necessary. This is the protocol generally used with multiagent sys­ tems [Durfee and Montgomery, 1991; von Martial, 1992; Gmytrasiewicz and Durfee, 1994].

Unfortunately, planning is intractable, especially if plans must be coordinated: the amount of communi­ cation (worst-case) grows as the square of the search space, which is itself exponential for deliberative plan­ ning ([Briggs and Cook, 1995a]). Multiagent planning work so far has mostly provided mechanisms for inter­ action [Georgeff, 1986; von Martial, 1992] without at­ tention to this problem, although [Gmytrasiewicz and Durfee, 1994) shows a model in which agents use deci­ sion theory to decide when to communicate, and [Dur­ fee and Montgomery, 1991] reduces the cost of com­ munication by sendin~ abstract messages. Previous work on social laws [Moses and Tennenholtz, 1990; 1991), that is, constraints on what actions an agent may take, has shown a method for reducing communication and planning time by reducing the options an agent has at any point. (In this paper, we relax the definition of social law to allow each agent to have a distinct set of constraints.)

*This research was supported in part by the National Sci­ ence Foundation, under grant IRI-9308308.

Our work extends the social law paradigm, providing a specific analysis of the costs, and a way of controlling these costs without reducing the applicability of plan­ ning.

1.1 Social laws

Social laws provide a way to constrain the actions of agents in multiagent systems, so as to reduce both the branching factor within an agent's search space and the chance of interaction with another agent's plan.

For example, consider a domain in which mobile robots must share a three-lane highway (Figure 1). One possible social law is a common traffic regulation: "Drive on the right." This law will prune a portion of the search space, since agents will not need to consider moving into other lanes. It will also reduce possible contention, since agents moving in one direction will never share a lane with those moving the opposite direction.

Reducing possible contention over states of resources is crucial, since the detection and resolution of such in­ teractions is the dominant communication cost in mul­ tiagent planning [Briggs and Cook, 1995a]. Specifically, agents need to communicate about the states of resources that their operators require (in a precondition list) or can provide (in a postcondition list). In Figure 1, for exam­ ple, each mobile robot needs to know that a section of the highway is clear before it can safely enter.

Unfortunately, social laws can prevent us from finding a solution. Figure 1 shows a roadblock in the topmost lane. If robot C is required to drive on the right, it cannot move into columns 1-3.

Social laws, therefore, can limit soundness. Determin­ ing if this is a possibility for any particular social law is in general NP-complete [Shoham and Tennenholtz, 1992].

1.2 Flexible social laws

Previous work by the authors [Briggs and Cook, 1995b] has analyzed what may be viewed as a special case of social laws, that is, restrictions on access to resources. This work extends the analysis to a more general concept of flexible social laws.

In this framework, agents prefer to obey the "laws" but are able to relax them. Assume a ranking of sets of social laws, from strictest to most lenient, where a more lenient set is one that allows a greater choice of operators. Also assume a limit on the depth of search. Each agent will try to generate a plan within the strictest set of laws. If this fails, the agent will try again, using the next set in the ranking. This continues until the agent has a successful plan or has failed with the most lenient set of laws.

Flexible social laws can reduce both planning time and communication. Soundness is not sacrificed, because if no solution is found within limits set, the agent plans with more flexible laws.

Of course, when an agent finds a solution while us­ ing a social law, the solution may not be optimal. But (especially if the plan is to be used only once) the cost of plan generation may be high enough that a solution quickly found is better than an optimal one.

If an agent has to try two or more sets of social laws before finding a solution, some redundant planning is performed. We will find that this extra cost is not great, and (for deliberative planning at least) makes the total cost greater than the cost of planning without social laws only in the extreme worst case.

This model should apply to groups of homogeneous or heterogeneous agents, which share subgoals or work on their own goals exclusively. The model should also apply with varying degrees of reactivity, and to anytime planning.

2 An example

Mobile robots A, B, and C are to share a highway (see Figure 1, previous page). A and B want to go right; C is to go left. There is a roadblock in the top lane.

Within one timeslice, a robot can move forward or back, straight ahead or diagonally; or it can wait. Each lane is 5 units long, and only one car can safely occupy the same unit in any timeslice.

Here are some possible planning scenarios, using dif­ ferent social law schemes. In the first scenario, we will have no social laws. For the second, we attempt to re­ duce communication and planning costs with a strict so­ cial law. Since this will not allow all agents to complete their plans, the third uses a more lenient social law, which shows no advantage over no social law at all. Finally, we use a ranking of social laws to reduce cost while still allowing all agents to find a solution. The plans shown are fully coordinated.

We have found an optimal plan, but with some com­ munication cost. In each timeslice, A and B have a pos­ sibility of contention, since each could swerve into the other's lane; in fact, in timeslice 4, A has to, to avoid the roadblock. C has possible contention with both A and B at timeslice 3.

Now we will try planning with a strict social law:

In this non-optimal plan, we have communication only between A and B, which must share a lane; but C cannot complete its task.

A more lenient social law might help:

We have a solution for each agent again; but we have not reduced the need for communication from the first scenario, which had no social laws.

A flexible application of social laws could get us the benefit of reduced communication without sacrificing soundness. Here, agents try planning with social law 1, and on failure, try again with social law 2.

In this case, as in the case with the strictest social law, we sacrificed optimality, and reduced interactions to the possible contention of A and B for the bottom lane; however, by relaxing the law, C was able to find a solution.

3 The model

This section contains definitions and assumptions.

For our analysis, we will assume cooperative agents, that is, agents which are honest and are willing to change their plans to resolve harmful interactions. We also as­ sume that agents plan correctly, that is, that they com­ municate whenever there exists a possibility of interac­ tions between plans.

3.1 Communication needs

During plan generation, these two types of communi­ cation occur between agents: interaction resolution, 1 which is the most costly (demonstrated in [Briggs and Cook, 1995a]), and fact sharing, in which one agent gives another information about the state of some resource, possibly from sensor data. If agents plan for each other, they must also send operator sets so they will know each other's capabilities, as well as information about goals to achieve and returned information about completed plans, which can be collectively called load balancing in­ formation. Since interaction resolution tends to domi­ nate the other types of communication, we will consider it only.

3.2 Definitions

The leniency of a set of social laws is defined as L;e 3 tate.[ioperators allowed in state il/ioperatorsi] /istatesi; this is the average proportion of operators al­ lowed in any state. For convenience, we define strictness as the opposite of leniency, or strictness = 1- leniency.

Let there be IAI agents. Define for each agent A; a ranking of sets of social laws, LawSets;, monoton­ ically increasing in leniency, ranging from LawSetsi ,l (the least lenient) to LawSetsl,ILawSet··l = {} (by defi­ nition, the most lenient). We can ensure that for j < k, LawSets;,j is no more lenient than LawSetsi,k by re­ quiring that LawSets; ,k ~ LawSets; ,j. Each agent may have its own set of laws; this could be helpful in heterogeneous environments. For this reason we define max(ILawSetsi) to be the maximum number of sets of laws for any agent.

At each point in the agent's search space, adhering to a social law means restricting the search to a subset of all possible operator instances. Using flexible social laws requires the establishment of a ranking of such sets. Call this ranking OpSets; . Note that if j ~ k, OpSetsi ,j ~ OpSetsi ,k·

Let P;,j be the set of all predicates that appear as pre- or post-conditions of the operators in OpSetsi ,j ; if there are any derived effects, they are included as well . Pi ,j is therefore the set of all predicates which agent A; may reference or affect while using operators from OpSets; ,j. There is therefore for each ranking OpSets; a corresponding ranking P; . Note that if j ::=:; k, P;,j ~ Pi ,k·

Define 0; to be a number in the range l..iLawSets;l, such that LawSets;,e is the set of social laws agent A; is currently using. (The subscript will be omitted when it is clear from context.)

1 Interactions may be harmful (conflicts) or helpful (favors) .

With each new value of(}, an agent may need to tell all the others what predicates it may be referencing (that is, the predicates in P; ,9 ) , so as to know who to negotiate with. For deliberative planning, the cost will prove to be insignificant. For reactive planning; we will assume that each agent has the same LawSets, such that there is no need to inform each other of what predicates one may be referencing. (Further work is needed to examine the effects of relaxing this assumption.) In either case, we may omit the cost of this information sharing in our analyses.

Here is the algorithm for multiagent planning with flexible social laws.

Algorithm Plan-with-flexible-social-laws mark all agents "active" for 8 = 1 to max(ILawSetsl) do for each "active" agent A; do, in parallel tell all other agents what predicates A; may access plan, using only operators in OpSets; ,o if a solution is found mark agent A; "successful" if 8 = ILawSetsd mark agent A; "failed"

endfor endfor

We define b( 0) to be the branching factor within the search space of any agent, given 0. For simplicity we assume that VO, b( 0) is the same for all agents, and is constant for all choice points in an agent's search space. Further, we assume that b(O) = (}b0 for some constant b0 ; that is, every increase in b, as we increment any(} to (} + 1, is close to the average increase.

We assume a lookahead limit L; we will not try to gen­ erate plans longer than L. We also assume worst-case search space size Size( A;, 0) = b(O)L = boLOL for all 0. (Search space is measured in terms of operator instances considered.) We define Size( 0) = L:!~l1 Size( A;, 0), where IAI is the number of agents. We also assume that we lack sufficient memory to store these exponential search spaces.

We also define cost function C osteomm (A;, 0) to be the number of messages sent for interaction resolution during the ()th iteration of the algorithm. Costeomm(O) = L:!~ 1 1 Costeomm(A;, 0). We assume worst-case cost 2 for any 0.

4 Theoretical analysis

This section contains an analysis of optimality; savings in communication and planning costs, accounting for the penalty from redundant planning work; and best- and worst-case analyses.

2 This means that each node in one agent's search space has a possible conflict with each node in any other agent's. This simplifying assumption will increase our results for com­ munication cost, both with and without social laws; further work is needed to determine how this affects our savings.

4.1 Optimality

Branching factor b( B) is necessarily monotonically in­ creasing with B, but the length (or cost, if we use op­ erator cost) of each agent's final plan (if any is found) is necessarily monotonically decreasing with B, since a more lenient social law can't possibly make a plan longer. 3 (This is true for any domain.)

Therefore a solution for some B < max(ILawSetsi) may not be optimal.

4.2 Communication

Here we calculate Cost comm (A;, B), the maximum num­ ber of messages used for interaction resolution between any two agents, at any iteration in the algorithm. This is proportional to the number of interacting pairs of op­ erators belonging to separate agent's search spaces.

The maximum number of interacting pairs for any B is the number of nodes in one agent's search space times the number of nodes in the other's search space. If both agents are still searching (that is, neither found a solu­ tion at a previous level), then this is (b(B)£) 2 · For all pairs of all IAI agents, there are IAI(IAI- l)b(B) 2 L in­ teracting pairs. If at most C messages are required to resolve interactions between such a pair, there will be C(IAI- l)b(B) 2 L such messages per agent.

By our assumptions, if we are performing deliberative planning, at each iteration of the algorithm an agent will need to tell all the others what predicates it may be referencing (that is, the predicates in P; ,6), so as to know who to negotiate with. The cost per agent A; is (IAI- 1)IP;,61· This is insignificant compared to the ex­ ponential cost C(IAI-l)b(B) 2 L and can thus be ignored.

If planning with b( B) fails, planning with b( B + 1) must either search the same space again, or store the space generated for B. It is not enough to store the leaves of the search tree; a final solution may interleave operators in OpSets;,6 with operators in OpSetsi,6+1 - OpSets;,6.

We have assumed that there was insufficient memory to store these search spaces; instead we will search again each time afresh, forgetting what we generated for pre­ vious values of B. With this assumption, we will need to communicate old information for each new B, increasing Costcomm(A;,B) to C(IAI-1)l::~=l b(t/J) 2 L. The total savings for communication per agent, that is, the cost without any social law minus the cost using flexible sociallaws, is

3 1£ we use breadth-first search. If we use some variation of depth-first search, reducing our options may lead us straight

to the solution; or it may make finding a solution impossible.

This is positive when B 2 L+l < ILawSetsl 2 L(2L + 1). For large L, this is when B < ILawSetsl; that is, when we are able to use social laws at all.

If, when planning is done, all agents have the same B - that is, if they all find their solutions in the same it­ eration - and if Vi, ILawSets; I = lLawSetsl, then total savings for all IAI agents is:

Savingscomm (B)

In general, savings is polynomial in B, but with a very large exponent (2£) if planning is deliberative.

4.3 Planning time

The savings for planning time is also degraded by the redundant planning, so that

Savingsplanning (A;, B) 6 =Size(A;, ILawSets;l)- L Size(A;,t/J) 1/J=l 6 =b(ILawSets;i)L- L b(t/J)L 1/J=l BL+l :=::!boL[ILawSets;jL- L + 1 )

This is positive, for large L, when Savingscomm is positive - in all cases when a solution can be found using any social laws.

If all agents have the same B, and Vi, ILawSets; I ILawSetsl, then: 4

'If we also consider the savings in terms of constraints imposed by the agent upon its own operators, we will find . I I 2L [I 12L en ] . Savmgscon·trainto(B) :::::! CAbo LawSets - 2 L+l ; thts is proportional to Savingscomm ( 8).

4.4 Best- and worst-case bounds

In the best case, each agent finds a solution with its strictest set of laws. For large L, Savingscomm = C(IAI - 1)bo 2 L[ILawSets; 1 2 £ - 1] :::::: C(IAI - 1)bo 2 LILawSets;I 2 L, which is just the cost of communication without social laws. Similarly, Savingsplanning is approximately the cost of planning without social laws. Optimality of the resulting plan may be degraded.

In the worst case, for all A;, B; = ILawSets;i. The communication penalty for trying flexible social laws (per agent) is C(IAI - 1)bo2L ILaw;i~tL+t; that is, ILawSet. ·I · h · h · 11 h 2 £+1 ' times t e cost w1t out soc1a aws; so we ave an increase in communication linear with the number of law sets, but inversely proportional to plan length. If L ~ ILawSets; I, this penalty is not significant. By sim­ ilar reasoning, we find a linear increase in planning time. Optimality is not degraded.

5 Reactive and anytime planning

As agents become more reactive, we are more likely to be planning real time, so optimality may be less impor­ tant . Also, although the exponent L (which represents the lookahead limit) is reduced, we will see that flexible social laws can still reduce cost. Since anytime planning has a smaller depth limit than deliberative planning, this discussion also applies to anytime planners.

Let N = the length of the total plan for any agent. (It may be greater for a reactive planner than for deliber­ ative planning, of course.) N / L is the number of plans an agent must generate and execute to accomplish the task. For a totally reactive planner, L = 1.

The savings for both communication and planning are N / L times the values given in the previous section; but the exponent L is now smaller, so the savings will be less. We note that deliberative planning gets a greater savings from the use of social laws than does reactive planning­ but reactive planning, being closer to tractability to start with, will become tractable more quickly with decreasing B.

For completely reactive planning (L = 1), we find that Savingscomm (B) is positive when B < 1.4ILawSetsi 2 1 3 (approximately). Savingsplanning(B) is positive when B < 1.4JILawSetsi (approximately).

For large numbers of agents and law sets, then, if agents are completely reactive, problems must work out to fit our social law ranking very well (that is, to have solutions when agent use only the first 1.4ILawSetsi 2 1 3 of the social law sets) . But for even moderately re­ active agents (say, L = 5) the range is much wider ( B < 1.2ILawSetsl 10 1 11 ).

6 Conclusions

Flexible social laws are useful in multiagent planning for limiting both communication and planning time without affecting soundness. Despite redundant planning and communication, communication and planning-time sav­ ings are polynomial in the number of social law sets not considered by an agent, but with a large exponent if planning is deliberative. The tradeoff for this is a loss of optimality, and increase in communication and plan­ ning time in the worst case proportional to the number of social law sets in an agent's ranking, but inversely proportional to plan length. (For deliberative planning, this increase is only in the extreme worst case) . We have shown best- and worst- case bounds, and have shown that the model is helpful for reactive and anytime plan­ ning as well as deliberative planning.

Our current work involves finding tighter theoretical limits, and testing the performance of this model. We are also developing a more restricted model which deals only with allocation of resources [Briggs and Cook, 1995b], in real domains. Another interesting area will be develop­ ing criteria for good rankings for the relaxation of social laws, like the downward refinement property [Bacchus and Yang, 1991] in hierarchical planning.

7 Acknowledgements

We would like to thank Qiang Yang and Edmund Durfee for their advice and encouragement.