Multiagent Planning with Partially Ordered Temporal Plans

Multiagent Planning with Partially Ordered Temporal Plans

Michael Brenner

Institut fiir Informatik, UniversiHit Freiburg, 79110 Freiburg, Germany brenner@informatik. uni-freiburg.de

Abstract

This paper· discusses the specifics of planning in mul­ tiagent environments. It presents the formal framework MAPL ("maple") for describing multiagent planning do­ mains. MAPL allows to describe both qualitative and quan­ titative temporal relations among events, thus subsuming the temporal models of both PDDL 2.1 and POP. Other fea­ tures are different levels of control over actions, modeling of agents' ignorance of facts, and plan synchronization with communicative actions. For single-agent planning in multi­ agent domains, we present a novel forward-search algorithm synthesizing MAPL's partially ordered temporal plans. Fi­ nally, we present a general distributed algorithm scheme for solving MAPL problems with several coordinating plan­ ners. These different contributions are intended as as step towards a simple, yet expressive standard for the descrip­ tion of multiagent planning domains and algorithms. Such a standard could in the future allow cross-evaluation of Multi­ agent Planning algorithms on standardized benchmarks.

In this paper, we discuss the specific properties of plan­ ning in Multiagent Systems (MAS). With the term Multiagent Planning (MAP), we denote any kind of planning being per­ formed in multiagent environments, meaning on the one hand that the planning process itself may be distributed among sev­ eral planning agents, but also that individual plans can (and possibly must) take into account concurrent actions by several executing agents.

As a motivating example, Fig. 1 shows a simple MAP problem as appearing in the RoboCupRescue challenge [7]. Two autonomous agents, police force P and fire brigade F, are working in a city devastated by an earthquake. While F's goal is to extinguish all burning houses, it is P's capability and goal to clear the blocked roads. P's position being LocO we will assume him being unaware of R12 and R13 being blocked. The agents' actions have specific durations that may be exactly known only at execution time, sometimes because of specific execution parameters of the agents, sometimes be­ cause of intrinsic unpredictability of the environment: while, for example, moving through the town may take between 2

· Definitions of the formal semantics of our Multi agent Planning Language as well as the algorithms for single and multi-agent plan­ ning are given in the long version of this paper [2].

and 4 minutes and depend only on the map distance and speed of the agent, extinguishing a fire may take 1 to 4 hours de­ pending on conditions unknown to the agents.

This trivial example shows several general features of MAP problems and plans: ( 1) Agents may be unaware of parts of the world state (P does not know whether Rl3 is blocked). (2) Concurrent acting is central to MAP (P can move to Loci and start clearing Rl3 while F is extinguish­ ing H 1, although both agents using the same road at the same time may be prohibited to avoid collisions). Modeling con­ currency necessitates (2a) a description of which events may occur concurrently and which not, (2b) metric time for real­ istic descriptions of action durations and their relations, but (2c) synchronizing on actions of unknown (at least to some agent) duration demands qualitative use of time (e.g. "after P has cleared R13"). A specific usage of qualitative time is (3) synchronization on communicative acts, as in "F moves to Loc3 after P has informed him that R13 is clear".

In their plans, agents must take other agents actions into account: F may "exploit" P's clearing ofR13 in his own plan but must also assure that he does not try to use a road that is also used by Pat the same time. Especially, ( 4) cannot control occurence or duration of other agents' actions.

To address the representation problems (1 )-( 4) we intro­ duce the Multiagent Planning Language MAPL ("maple"). Instead of propositional state representations MAPL allows non-boolean state variables (cf. also [5]). To model feature (!)each state variable may have the special value unknown, thereby avoiding representation of belief states as sets of pos­ sible states. A number of other advantages comes with the introduction of state variables; especially, for feature (2a), an intuitive definition of mutual exclusivity (i.e. the impossibil­ ity to execute some actions concurrently, cf. [1]) can be given that describes mutexes as read-write locks on state variables. According to this perspective, distributed planning can then be seen as detection or, even better, prevention of possible read-write locks before execution.

MAPL's temporal model allows to combine (2b) quantita­ tive and (2c) qualitative temporal information in plans, thus subsuming both the purely metric temporal model of PDDL 2.1 [4] and the purely qualitative model of Partial Order Plan­ ning [8]. At its core MAPL represents a multiagent plan as a Simple Temporal Network [3] in which each durative ac­ tion is modeled by start and end events, possibly extended by invariant conditions. In the STN, both action durations and qualitative ordering relations are treated as constraints repre­ sented by closed, semi-open or open intervals. In so doing, not only can imprecisely known action durations be repre­ sented as intervals of the form [(h , 82), but qualitative con­ straints like "after" can be described by (semi-)open intervals like (0, oo ). Fig. 2 shows F's plan for the problem of Fig. I, the interval (0, oo) being represented as <.

Another new concept shown in Fig. 2 is (3) the use of speech acts as reference events for plan synchronization. On the one hand, this allows agents to refer to facts (especially those achieved by others) the change of which they do not influence or witness themselves. On the other hand, as ex­ plained later, speech acts allow agents to reveal only the min­ imum of information about their plans needed for coordina­ tion.

A plan is only fully specified with (4) a contra/function describing which of the agents (or the environment) controls the occurence of each event. With this function we can de­ scribe, e.g., that a specific agent is allowed to add and remove an action from his plan (control of the start event), but has no influence on it its duration (end event controlled by the environment). During planning, having control of an event or not fundamentally changes its possible use and evaluation. For example, being able or unable to control the duration of an action will lead the planner to a fundamentally different heuristic evaluation of its use.

For a plan to be executable, it must be both temporally and logically consistent. The former criterion is reducible to consistency of the underlying STN. The latter, logical consis­ tency, can be defined similarly to POP as the plan having no open conditions and no unsafe links, with the additional crite­ rion that the plan must ensure that no mutex events may occur concurrently. For a plan to solve a certain agent's problem it must achieve his goals and also be consistent with the control function, i.e. only constraints involving events controlled by the respective agent must have been tightened by the planner.

How is planning in MAS carried out? It is obvious that the easiest way is to find a plan alone: assumed that F knows about P's capabilities, F can find a plan that solves his prob­ lems. Even if F does not know about P's concrete actions, this plan will provide clues about where help is needed and thus triggers cooperation. We see that (5) the capability for single-agent synthesis of multiagent plans is a basic require­ ment for MAP. We have developed a plan-space forward­ search algorithm that can be used with any standard forward branching scheme and arbitrary plan metrics. We present two such metrics, the well-known makespan and the new min­ MaxMakespan, the latter of which extends the former by as­ signing maximal possible duration to uncontrolled durative actions. We also describe how heuristic forward planning in the style of FF [6] can be extended to find MAPL plans. The current simple algorithm is sound, but not complete, i.e. there is a set of clearly distinguished MAPL problems it can­ not solve yet. We are working on a sound, yet more complex version of the algorithm.

When several agents are planning and acting individually in a common environment, they will probably run into one of the following problems: (6) They won't be able to find in­ dividual plans solving their problems or (7) the plans found will conflict at execution time. MAP Literature has mostly treated only problem (7), implicitly assuming that plans can be found and that therefore separating planning from coor­ dination is possible. In our opinion, coordination during the planning phase is indispensable in the case of problem (6) and advantageous for problem (7). We have therefore developed a general distributed planning algorithm that uses single-agent planning to synthesize partial plans and to trigger cooperation and coordination efforts as early as possible.

A key concept is the use of a responsibility function that assigns to each state variable an agent managing and control­ ling its changes over time. This agent will detect read-write conflicts in the agents' plans. i.e. possible execution conflicts, but will also provide information when another agent cannot achieve a (sub)goal involving that variable. In the basic form of the algorithm, the responsibility is static, but similar to ap­ proaches in Distributed CSP research [9] we will relax this assumption in future work. The idea of the algorithm is sim­ ple: in a reachability analysis the planning agent detects goals involving state variables he does not know about, cannot ma­ nipulate or could if only some earlier condition were satisfied. He contacts the responsible agents to receive more informa­ tion or delegate a subgoal concerning the variable. The re­ sponsible agent answers the question or adopts a temporary goal to help the asking agent.

All contributions of this paper aim at clarifyfing the spe­ cific representational and algorithmic needs of MAP research. We hope that our representation will allow to conveniently de­ scribe diverse MAP domains for which researchers can pro­ pose and cross-evaluate algorithmic approaches just as di­ verse, thus promoting the field of Multiagent Planning.