An Implementation of a Multi-Agent Plan Synchronizer

1. Introduetlon

All planning systems operate by combining actions or sub-pians in some way so that the total plan satisfies some constraint - usually to achieve a goal state. Knowledge of how actions interact with each other and the world is used to determine the appropriate combinations. In NOAH[S[, for example, consideration of interactions between sub-pians is explicit in the planning process. A plan is a partial order of sub-plans. The planning technique is to expand sub-pians into partial orderings of lower Ievel sub-plans, and then Iook for and resolve ensuing conOicts. The resolution may impose fixed orderings. This can be unnecessarily restrictive, as in the case where two sub-pians may execute in any order but not at the same time.

This paper considers the use of synchronizing primitives to resolve conOicts and produce a p)an which is as unrestrictive as possible. The models of plan and action used are appropriate for simple agents or robots engaged in parallel and or repetitive tasks which may be described at a Ievel not using sensory input to tbe agents. Use could be made of this tecbnique, for example, in automated assembly lines. Georgeff[2[ has also done related work on planning for multiple agents.

2. Underlylng theory.

Here we give an informal summary of a fully formalized theory of action and tbe world , wbich is described in [6[.

2.1. Aetloria

An agent changes the world by executing actions. When multiple agents are operating in parallel , it may be possible for two actions to be executing simultaneously , and so actions must have a beginning and an end . We consider an action to be decomposed into disc rete transformations of tbe world , wbicb are called euents. An event also bas an associated correctness condition, which must be true at tbe moment it is executed. An action will be a set of possible finite sequences of events.

2.2. The envlronment

Tbe state of the enuironment in which actions are executcd consists of a world state, and a set of actions currently being

AN IMPLEMENTATION OF A MULTI-AGENT PLAN SYNCHRONIZER

Christopher Stuart

Department of Computer Science Monash University Clayton 3168 Australia

executed. If an agent executes an action , one of the possible sequences of events for that action is selected non-deterministically and added to tbe environment state. Tbe environment may at any time take a currently executing action, pop tbe next event from the event sequence, check for event failure, and change the world state according to tbat event .

Tbe environment defines a set of symbols called operators, and gives eacb operator an interpretation as a set of event sequences ( action ). These operators are the means of interact ion between an agent and tbe environment, and are excbanged as messages.

2.3. Agent.

Tbe execution of a plan corresponds to some sequence of messages between tbe environment and an agent. Let A be the set of operators. Tben a scquence of messages will be denoted by a st ring over the alphabet { begin, end} X A. For any CLEA, ( begin CL) corresponds to the agent sending Cl to tbe environment to cause tbe -associated action to be executed, and (end CL) corresponds to the environment sending Cl to tbe agent to indicate that the associated action has completed. We refer simply to strings and assume them to be over tbis alphabet.

An agent is an acceptor for s.trings. The formal model for an agent is similar to a non-deterministic finite automaton. It has a set of nodes (agent states), and a set of arcs defining allowed state transitions witb associated messages. An agent deadlocks if it is in a state from wbicb tbcre are no possible state transitions involving a ( begin a) message, and tbe environment bas finisbed executing all the operators sent by the agent.

An agent defines a set of possible strings, and for any string, an environment defines some set of possible world state sequences. The planning problern is to take information about the environment , and find an agent whicb has some dcsi rcd cffect on tbe world , such as the ultimate acbieving of a goal world state, no matter what choices t he environment makes . We say two agents are equiualent if in any environment they induce the same set of possible sequences of world states.

An agent is bounded if tbere is a finite upper bound on the number of actions wbicb the environment can be executing at a time. Tbus a bounded agent will suffice to represent the concurrent activity of a finite number of multiple real world agents .

2.4. Plans

Given three symbol sets A, M and S being operators, memory states aod signa/s respectively, p/ans are defined recursively .

• For any aEA : a is a plan for executing an single action.
• For any mEM, 8ES: (set m ), (send 8) and (guard m 8) are synchronizing primitives.
• If p 1 and p 2 are two plans, tben p 1 ;p 2 is tbe plan to execute them in sequence, p 1 jjp 2 is to execute them in parallel, p 1 jp 2 is to execute one or tbe other by non-deterministic selection, and p: executes p 1 an arbitrary number of times.

The semanlies for plans is given as a mapping from plans to agents, which is desc ribed in [6[ . Intuitively , the agent for the simple plan Q is an automaton accepting only the string ((b egin Q) ,(end Q)} . The plan operators build automata in the conventional manner. The synchronizing primitives correspond to arcs in the automaton which have a side effect on plan execution without exchanging any messages with the environment . Set changes the memory stat e of the plan, and guard and send can only be executed simultaneously, and then only when the memory is in the specified state and the signals match. This particular form of primitive is an adaptation of synchronization in the parallel programmins langnage CSP[3[, which uses guards which may be a combination of an inputfoutput operation and a normal conditional.

The following two results, given without proof, assert that there is a one to one correspondence between plans and bounded agents.

• Any agcnt which is given as the semantics of a plan is bounded.
• For any arbitrary boundcd agent, there is a plan which has an interpretation equivalent to that agent.

3. The Interaction problern

The problern addressed here is that of ensuring that a plan does not deadlock , or allow any event to fail. Correctness conditions on events or actions can be used to represent many types of plan correctness. lf a plan should achieve some goal state given some initial condit ion, this is ensured by beginning the plan with an action that asserts the initial condition, and terminating it with an action that will always fail in the absence of the goal condition. A condition which must be maintained during a plan can be enforced with an action in parallel that will fail in the absence of the maintained condition.

A program has been developed wbich takes a plan and ·a desc ription of an environment , and generates a revised plan which allows all and only the sequences of communication acts of the first plan that cannot cause failure, and also that will never deadlock.

3.1. Preventlng event tallure

For this program we use a very simple form of event, corresponding to the operators of the STRIPS planner[ 1]. The world is modeled as a set of propositions. Events are constrained to add or delete propositions without reference to the current world state. Also, the correctness condition is a conjunction of propositions or negated propositions. Thus an event is four sets of propositions: a require tru e sct , a require false set , an add set and a delete set.

lt turns out in this case that to prevent event failure an action is completely defined by five sets of atomic formulae (possibly negated propositions). The live properties are defined by considering the execution of the action in isolation from other actions. An atomic formula is

• assert ed if it is inevitably true after the execution.
• retract ed if it could possibly become false after the execution .
• conflict ed if it could become false at some stage during the execut ion.
• a precondition if it must be true immediately before the action begins to ensure that no event will fail.
• a during condition if it must be true for some event in the action.

The necessary and sufficient rules for ensuring no event failure are:

• An action which has a during condition may not run in parallel with an action that conHicts that during condition .
• An action QP which has a precondition may not begin until some action Q 0 which asserts that condition has completed, and also no action Q, which retracts that condition may be running from when Q 0 begins until QP ends.

3.2. Synehronl&lng Plan·

We synchronize a plan by inserting send operations, and running it in parallel with a synchronization skeleton consisting only of guard and set operations. The set of possible strings for the resulting plan is a subset of those for the original plan. Manna and Wolper describe an algorithm for generating such a skeleton froril propositional temporal logic (PTL) formulae used to express constraints on execution sequences of a plan.[4]

PTL is a logic for reasoning about sequences of states. The interpretation of a PTL formula is the set of sequences for which it is true. States give truth values to propositions and hence to non modal formulae, and the temporal connectives of PTL ( always, euentually, until and next) have truth values depending on the successors of a state. We also use a regular expression operator equivalent in expressiveness to the grammar operators of Wolper.[7] A regular expression with the basic elements being non modal formulae translates into a set of sequences of non modal formulae, and tben to a Set of sequences of states.

3.3. The algorlthm

The plan synchronizer has three phases. First, PTL formulae are generated. Correctness constraints, being the two rules defined above, are expressed in Standard PTL, using proposi·ions to represent relevant stages in plan execution . A regular expression formula corresponding to a simplification of the plan is used to express the constraints imposed by the plan syntax on the order of the relevant stages. The formulae are simplified or ignored depending on orderings already enforced by the plan syntax. This reduces the time spent in the second phase without altering the interpretation of the conjunction of all the PTL formulae generated.

Second, a tableau method of theorem proving is applied. Formulae are decomposed into non modal constraints on the first state of a sequence, and generat constraints on the remainder. A graph is constructed, with arcs corresponding to st a.; es in plan execution , and nodes Iabeted with PTL formulae. This graph is pruned to enforce eventuality constraints. Every interpretation for the original PTL formula is a path through the final graph , and every finite path is the prefix of an interpretation.

Finally , the graph is converted directly into a synchronization skeleton , and send operations are inserted into the plan for every proposition used . The set of memory states used corresponds to the set of nodes in the graph , and each arc is represented as a guarded command to alter the memory. The resulting plan allows all possible execution sequences of the original which do not permit an event to fail , and which always allow for plan termination.

The current version of the program only bandies restricted classes of plans and actions (no loops, no selection, and actions consisting of a single event sequence), but is being extended at the moment to include these.

4. An example

Consider the problern of three robots all trying to pickup a block and move it clockwise to a location which another robot will clear as it moves, represented by the following unsynchronized plan:

((START (Rl R2 R3) ((A X) (B Y) (C Z))) (PARALLEL ( (PJCKUP Rl A X) (PUTDOWN Rl A Y)) ( (PICKUP R2 B Y) (PUTDOWN R2 B Z)) ( (PICKUP R3 C Z) (PUTDOWN R3 C X))))

The start action sets up the ioitial conditioos, and theo each robot in parallel executes a pickup aod putdowo. Clearly collisioos might result. The problern is represented pictorially in the followiog diagram:

The synchronized plan produced by the program is ((PARALLEL

( (SEND (BEGIN 1)) (START (RI R2 R3) ((A X) (B Y) (C Z))) (PARALLEL ( (PICKUP Rl A X) (SEND (END 2 I 1)) (SEND (BEGIN 2 I 2)) (PUTDOWN Rl A Y)) ( (PICKUP R2 B Y) (SEND (END 2 2 1)) (SEND (BEGIN 2 2 2)) (PUTDOWN R2 B Z)) ( (PICKUP R3 C Z) (SEND (END 2 3 1)) (SEND (BEGIN 2 3 2)) (PUTDOWN R3 C X)))) ( (RECV (BEG IN I)) (SETQ N2) (WIULE (NOT (EQ N 13)) (SELECT-ONE-OF (IF (AND (EQ N 2) (RECV (END 2 3 1))) THEN (SETQ N 5)) (IF (AND (EQ N 2) (RECV (END 2 2 1))) THEN (SETQ N 4)) (IF (AND (EQ N 5) (RECV (END 2 I 1)))

THEN (SETQ N 6)))))))

The syntax is close to CSP, and can be translated directly into plans as we have defined them. A !arge section of the synchronization skeleton has been removed in the example, since it contains 42 guarded commands - poe for each arc in the model for the PTL formulae. The final plan has the desired result of holding any potdown until the appropriate pickup has completed. Each pickup is followed by a send which indicates a block is clear, and each puldown is preceded hy a send which is delayed until the appropriate destination block is clear.

5. Concluslon and Future Work

There are some optimizations possible in the general method by pruoing the graph, which in the above example would have reduced the size of the synchrooization skeletoo, aod removed redundant refereoces to (BEGIN 1) . lt is also worthy of iovestigation to coosider how synchronization primitives could be inserted in the main plan without adding a new parallel brauch with the syochrooizatioo skeleton, or how the syochrooization skeleton could be made more modular , with distinct compooeots to handle particular coostraiots.

The definition of actions aod envirooments given here enables very stroog properties to be given to the syochronized plaos: in particular that alt and on/y the correct executions of the initial plan are permitted. This is in contrast to previous means of syochrooiziog plaos which prohibit some executioo sequeoces that would succeed.

By extending the definition of actions to include general state traosformatioos in events, a similar algorithm could generate a plan which is still less restrictive than that produced by previous plan modifyiog techoiques, but might still disallow certaio correct executions. There is oo simple actioo descriptioo capturiog all the essential properties in the same way as cao be done in the simple case with live sets of atomic formulae. Also, the PTL formulae might need to reference propositioos reßectiog world state as weil as the stages of plan execution. This problern could be considered in more detail.

There is also the problern of types of oon-determioism. The curreot selection operator correspoods to the case where a plan may proceed in ooe of two directions, and the synchrooizer is permitted to chose ooe over the other. This is ange/ic noo-determinism. However, it may be the case for some plans that the choice is critical, but made at execution time, in which case the synchronizer must allow both cases or oone at all. This is demonie noo-determinism, and implies some additional structure to a plan which restricts the ways in which it may be synchronized. For added complexity, the decision may be based on the state of the world model , and so the synchronizer cao determine the choices it must leave opeo, depending on the possible world models it derives for the momeot of choice.

Loops often have a termination cooditioo which is a fuoction of all the activity in the loop, and yet may not easily be derived from the given ioformatioo. Such a termioation conditioo could be specified if a plan segmeot were treated as a siogle hierarchical actioo, aod giveo properties similar to those for individual actioos. Coosider a loop of an action that removes a single item from a box uotil none are left . To represeot this in the formalism giveo here, the eotire loop would be giveo an assert cooditioo that the box become empty. To guarantee termination, the eotire loop could be giveo a during condition that oo one places aoythiog in the box.

A versioo of the program is beiog desigoed which will take as input an arbitrary plan as defined above, aod will also handle both types of ooo-determioism, aod cooditioos attached to sub-piaus as · bierarcbical actioos. Tbe theoretical justificatioo is being pursued concurreotly.

ACKNOWLEDGEMENTS

Much of this investigatioo was cooducted at the Al ceoter at SR! International. Thaoks are due to the ceoter aod especially to Michael Georgeff for helpful discussion; aod to Mooash Uoiversity for fioaocial assistaoce, aod where the work is proceediog.

HEFERENCES

• IIJ Fikes, R.E., Nilsson, N.J. "STRIPS: A oew approach to the application of theorem proviog in problern solviog." Artificial Int elligence 2 (1971), pp189-208.
• 121 Georgeff, M.P. "Commuoicatioo aod Interaction in Multi-Agent Planning." In Proc. AAA/-83, (1983) ppl25-129.
• I3J Hoare, C.A.R. "Commuoicatiog Sequeotial Processes. " In Communications of the ACM 21:8 (1978), pp 666-677.
• 141 Manna, Z.; Wolper, P. "Syothesis of Commuoicating Processes from Temporal Logic Specificatioos." Report STAN-CS-81-872, Stanford University Computer Scieoce Dept, September 1981.
• ISJ Sacerdoti, E.D. "A Structure for Plans and Behaviour." Tech Note 109, SRI Al Center, Meolo Park , CA 1975.
• 161 Stuart, C.J. "An lmplemeotatioo of a Multi-Agent Plan Synchrooizer Using a Temporal Logic Theorem Prover." Report uoder developmeot, SRI Al Center, Meolo Park, CA, 1985.
• I7J Wolper, P. "Temporal Logic Cao Be More Expressive." In Proc. of the 22nd Symposium on Foundations of Computer Science. Nashville, TN, (1981)