A Formalization of Equilibria for Multiagent Planning

1 Introduction

Traditionally, planning involves a single agent for which a planner needs to find a sequence of actions that can transform some initial state into some state where a given goal state­ ment is satisfied. But in general, "planning" can be viewed as being concerned with a general action selection problem. The planning framework has been extended from the classi­ cal deterministic plan generation problem along many other dimensions, in particular nondeterministic actions. With the introduction of nondeterministic actions, the presence of an environment and other agents can become a consideration. In fact, actions may have nondeterministic effects not only be­ cause of the uncertainty of their own execution, but also due to the uncertainty of the actions of other agents. The pos­ sible presence of other agents as executors is the challenge of "multiagent planning." The interest in this area has been steadily increasing and many issues remain open.

Despite the existence of planning languages with explicit models of uncontrallable agents [Jensen and Veloso, 2000], we believe that there has not been a formal discussion of the space of multiagent plans or solutions. In this work, we do not focus on the problem of plan generation for multiagent planning. Instead, we focus on the interesting question of analyzing and comparing solutions for multiagent planning. Our motivation comes from making an analogy with game theory and the notion of equilibria [Owen, 1995].

Inspired by game theory and extending previous formal definitions of single-agent planning [Cimatti eta/., 2000], in this paper, we introduce a formal definition of equilibria for multiagent planning.

2 Planning Equilibria

In this section, we formalize the concept of a multiagent plan­ ning equilibrium. In order to help make these concepts clear we will first describe an example, which is small enough to easily enumerate all of the states.

2.1 A Simple Example- The Narrow Doorway

Consider a two agent robot domain where both agents are in a hallway and want to move into the same room through a single doorway. The agents have an operator to go through the door (G) that only succeeds if the other agent is not also trying to go through the door. They also have the choice of waiting (W). Each agent's goal is simply to be in the room.

A Formalization of Equilibria for Multiagent Planning

Michael Bowling, Rune Jensen, and Manuela Veloso

Computer Science Department Carnegie Mellon University Pittsburgh PA, 15213-3891

2.2 The Formalization

We first begin by formalizing some planning related concepts. The definitions parallel closely with Cimatti and colleagues' single-agent formalization [2000]. We extend their defini­ tions of planning domains, problems, and solutions to encom­ pass multiple agents. We then follow this formal framework with a definition of multi agent planning equilibrium. Notice that the definitions and concepts presented are not bound to any particular planning algorithm or language.

We start by defining a multiagent planning domain.

Definition 1 (Multiagent Planning Domain)

A multiagent planning domain D is a tuple (P,S,n,Ai=l.. .n, R) where,

• P is the finite set of propositions,
• S <:;;; 2P is the set of valid states,
• n is the number of agents,
• A; is agent i 's finite set of actions, and
• R <:;;; S x A x S is a nondeterministic transition relation where A= A1 x .. . X An and must satisfy the following condition. If (s, a, s') E Rand (s, b, s") E R then, 1::/i there exists s'" E S,

I.e., each agent's set of actions that can be executed from a state are independent.

In addition, let ACT; ( s) <:;;; A; be the set of applicable or executable actions in states. Formally,

The additional condition in the planning domain definition on R requires that each agent be capable of selecting actions independently. Formally this amounts to the following. For all states s and executable actions for the agents a; E Act; ( s) there exists some transition (s, (ai=l ... n), s') that is in R.

In the doorway domain, P contains two propositions, A­ in-room and B-in-room. The set of states S corresponds to all four possible subsets ofP, since all combinations of proposi­ tions are valid in this domain. n is two and AA B is the set of actions { G, W}. The transition relation R is defined by the rules described above. The complete enumeration of states and transitions is shown in Figure I. The figure also num­ bers the states so they can be referred to in an abbreviated form. Note that this domain satisfies the independent action condition on n.

Definition 2 (Multiagent Planning Problem)

Let V = (P, S, n, Ai=l...n, R) be a multiagent planning do­ main. A multiagent planning problem P for V is a tuple (V,I, Yi=l. .. n), where I ~ Sis the set of possible initial states and Q; ~ Sis the set of goal states for agent i.

In the doorway example, the goal states for agent A are {1 , 3} and for agent Bare {2, 3}. The initial state set is the singular set { 0}. With this definition of domain and problem, we can now formalize a notion of a plan.

Definition 3 (State-Action Table)

A state-action table 7r;for agent i in domain Vis a set of pairs {(s,a;)ls E S,a; E ACT;(s)}. Ajointstate-actiontable1r constructed from state-action tables for each agent 1ri=l. .. n is the set of pairs

A Ooint) state-action table is complete if and only if for any s E S there exists some pair (s, ·) in the state-action table.

For the doorway domain, a state-action table (or plan) for each agent might be,

These are also complete state-action tables since they specify at least one action for each state. We can combine these ta­ bles into a complete joint state-action table. In general, a joint state-action table together with a multiagent planning domain determines the entire execution of the system. In order to de­ fine what it means for a plan to be a solution to a planning problem we need to formalize the notion of reachability and paths of execution. We will do this by first defining the exe­ cution structure of the multiagent system.

Definition 4 (Induced Execution Structure)

Let 1r be a joint state-action table of a multiagent planning domain V = (P, S, n, A;, R). The execution structure in­ duced by 1r from the set of initial states I ~ S is a tuple K = ( Q, T) with Q ~ S and T ~ S x S inductively defined as follows:

• if s E I, then s E Q, and
• if s E Q and there exists a state-action pair (s, a) E 1r and transition (s, a, s') E R, then s' E Q and (s, s') E T.

A state s E Q is a terminal state of K if and only if there is nos' E Q such that (s, s') E T .

Intuitively, Q is the set of states that the system could reach during execution of the plan 1r, and Tis the set of transitions that the system could cross during execution. For our door­ way domain the execution structure induced by our example joint state-action table is,

We can now formalize an execution path.

Definition 5 (Execution Path)

Let K = ( Q, T) be the execution structure induced by a state­ action table 1r from I . An execution path of K from so E I is a possibly infinite sequence s0 , s1 , s 2 , ... of states in Q such that, for all states s; in the sequence:

• either s; is the last state of the sequence, in which case s; is a terminal state of K, or
• (s; , Si+I) E T.

A state s' is reachable from a state s if and only if there is an execution path with s0 =sands; = s'.

For our doorway domain and example joint state-action ta­ ble one execution path from the initial state is,

We are now in a position to define what it means for our plan to solve a planning problem. We actually define multiple con­ cepts increasing in strength. These concepts formalize some of the intuitive discussion from the previous section about whether a plan has one or more of the following properties:

• the possibility of reaching the goal,
• a guarantee of reaching the goal, and
• a guarantee of reaching the goal in a finite number of steps.

These concepts and their formalization are inspired and highly related to Cimatti and colleagues' single-agent solu­ tion concepts [Cimatti eta/., 2000].

Definition 6 (Multiagent Planning Solutions)

Let V be a multiagent planning domain and P (V, I, Yi=l...n) be a multiagent planning problem. Let 7r be a complete joint state-action table for V. Let K = ( Q, T) be the execution structure induced by 7r from I . The following is an ordered list of solution concepts increasing in strength.

1. 1r is a weak solution for agent i if and only if for any state in I some state in Q; is reachable.
2. 1r is a strong cyclic solution for agent i if and only if from any state in Q some state in Q; is reachable.
3. 1r is a strong solution for agent i if and only if all execu­ tion paths, including infinite length paths, from a state in Q contain a state in Q;.

1. 1r is a perfect solution for agent i if and only if for all ex­ ecution paths so , s 1, s2 . . . from a state in Q there exists some n 2: 0 such that Vi 2: n, Si E ~h

A state-action table's strength STRENGTH(V, P,i,1r) is the largest number whose condition above applies for agent i. If no conditions apply then STRENGTH(V, P, i, 1r) = 0.

For our doorway domain, the joint state-action table is a strong cyclic solution for both agents but not strong (i.e., it has a strength of 2 for both agents). This means that there is a path to the goal from any reachable state. But there are also paths that do not include either agents' goal states, and so it is not a strong solution for either agent.

These solutions define what it means for one agent to be successful given a joint state-action table. The goal of plan­ ning from one agent's perspective is to find a plan that has the highest strength given the plans of the other agents. But the other agents' selection of a plan is equally contingent upon the first agent's plan. This recursive dependency leads to our main contribution of the paper: planning equilibria.

Definition 7 (Multiagent Planning Equilibria)

Let V be a multiagent planning domain and P (V, I, Yi=l...n) be a multiagent planning problem. Let 1r be a complete joint state-action table for V. Let K = ( Q, T) be the execution structure induced by 1r from I. 1r is an equilib­ rium solution to P if and only if for all agents i and for any complete joint state-action table 1r 1 such that 1fJti = 1fj.

I.e., each agent's state-action table attains the strongest solu­ tion concept possible given the state-action tables of the other agents.

Note that our example joint state-action table for the door­ way domain is not an equilibrium. Both agents A and B cur­ rently have strength 2, but B can achieve a strength of 4 by choosing a different state-action table. Specifically, B should select the wait (W) action from the initial state and the go (G) action in state 1.

To make the concept of planning equilibria clearer, we il­ lustrate it in the doorway domain. We gave above an example joint state-action table that is not a multiagent planning equi­ libria for this domain. An equilibria is the following state­ action tables:

In this case agent A goes through the door while agent B waits and then follows through the door. This is a perfect plan for both agents and so obviously no agent can achieve a higher strength with a different state-action table. Similarly, the symmetric tables where agent B goes through the door while agent A waits is also an equilibrium. There is an addi­ tional equilibrium,

Here both agents nondeterministically decide between going through the door and waiting. This results in a strong cyclic solution for both agents, but given this state-action table for the other agent no strong or perfect plan exists for either agent. So this is also an equilibrium although obviously in­ ferior to the other equilibria where both agents have higher strength plans. In game theory, such a joint strategy is called Pareto dominated.

Collision variation. Consider a variation on this domain where collisions (when both agents choose G) result in the robots becoming damaged and unable to move. In this case, the first two state-action tables above remain equilibria, but the third inferior table no longer is an equilibrium. This joint plan is now only a weak solution for both agents since there is a possibility of never achieving the goal. Each agent can also change to a different plan where it waits for the other agent to get through the door thus achieving a strong cyclic plan and a higher strength.

Door closing variation. Finally, consider that one agent en­ tering the room sometimes causes the door to close behind it. Once the door is closed it cannot be opened and the door­ way cannot be used. In this case, the same two joint plans are again an equilibrium but now they have different strengths for the different agents. The first joint state-action table is a strong plan for agent A, but only a weak plan for agent 8, though it can do no better. The second is just a symmetry of this.

3 Conclusion

We presented a formalization of multiagent planning and in­ troduced the concept of a multiagent planning equilibrium. This is the first known solution concept that explicitly ac­ counts for the goals of all the agents. This work provides a unifying framework for considering planning in multiagent domains with identical, competing, or overlapping goals. It also opens up many exciting questions related to practical al­ gorithms for finding equilibria, the existence of equilibria, and the coordination of equilibria selection.

Acknowledgments

This research was sponsored by grant No. F30602-00-2-0549. The content of this publication does not necessarily reflect the position of the funding agencies and no official endorsement should be in­ ferred.