Refining and Extending the Procedural Net

1. Paper Overview

In the next section we give Sacerdoti 's definition of the Procedural Net. A simple method for deriving Procedural Net behaviours is also presented, and it is argued that lhe Procedural Net cannot describe ileration. Section 3 defines and discusses the Plan Net. Two sample Plan Nets are given. An operational semanlies is suggested for lhe Plan Nel, and it is argued that Plan Nets can describe ileration. The Procedural Nel and lhe Plan Nel are compared in Seclion 4. Section 5 concludes.

2. The Procedural Net

A Procedural Nel has been defined as "a nelwork of actions at varying Ievels of detail , slruclured inlo a hierarchy of partially ordered time sequences" (Sacerdoti , 1975, p . 10) . The basic objecls in a Procedural Nel are actions, and some ordering relations on lhe aclions . Because of lhi s, we refer lo lhe Procedural Nel as an "event space" repres enlation. A nel can be drawn as an aclion- on- node graph, wilh directed arcs between nodes . An arc running from one node a lo another node ß means that the action denoted by a must occur "before" the action denoted by ß .

We can derive the possible behaviours of a given Procedural Net by analyzing the state space which it describes . A net's state space can be produced by playing a version of the "pebbling game" (Pippenger. 1980). Whil e pebbling was not developed with this application in mind, it does capture our

REFINING AND EXTENDING THE PROCEDURAL NET

Mark E. Drummond

Department of Artificial Inte lligence University of Edinburgh Hope Park Square Edinburgh, Scotland, U.K.

intuition of what "before" means in a Procedural Net . In our version of this game, we place "pebbles" on the nodes of a Procedural Net as they are executed . The net starts out pebble- free, and finishes up pebble-laden - each node must be pebbled ; that is, each aclion must be executed. Pebble placement is carried out according to the rule: A node may be pebbled if all of its immediate predecessors are pebbled.

The Procedural Net has been criticized recently (McDermott, 1983; Rosenschein, 1984) . This paper addresses the Procedural Net's inabilily to des cribe "iterative" behaviour . Such behaviour is difficult to model in a natural way using a Procedural Net. Since the arcs of a nel are taken to mean "before", one cannot simply direct an arc from an action "back inlo" lhe net.

It is obvious that all Procedural Net state-spaces will be loop- free, since lhe number of pebbles on a net must increase monotonically. There will never be an action which removes a pebble; thus never an action which can produce an earlier sta te . This is due to the slrict "before" interprelation of

the Procedural Net's arcs .

While Sacerdoti did inc!ude a mechanism for dealing with iteration, it hides the notion of "process" inside a special replicate node. Hi s treatment of iteration poses problems . Below, we suggest that by defining an alternative "event space" representation for plans , we can describe iterative behaviour . This new definition follows the belief that iteration must be expressed in terms of the structure of a plan, so that a planner can r eason

about the iteration.

3 . The Plan Net

In this section, we define Plan Nets. using some basic concepls from Nel Theory (Brauer , 1979).

Definition 1. A Plan Net is a 6-luple <P.T,Ra,Rb,Rc,Re>, where P lpt,p2, ... ,pN!. a finite set of places ; T = !t1.l2, .. ,tw!. a finite set of transilions ; N ~ 0, M ~ 0 ; and T n P = rf>, the emply set. R. = !(tl.tk) I 3pjEP [(ti,pJ)ERc & (pJ ,tk)ERe]!. lhe Allow relation . Re ~ (P·T) , the Enable relalion; Re ~ (T·P), the Cause relation. Rb ~ (T·T) , the Before relalion; Rb must be a strict partial order on T.

Definition 2. Place p; is an input place of transition lj if and only if (pl,lJ) E Re. Place p1 is an outpul place of transition lj if and only if (lJ,pl) E Re.

Definition 3. A marking of a Plan Net is a mapping J.L: P -+ !O. 1!.

Definition 4 . A transition lj is enabled if for each input place, p1, J.L(PI) = 1. A transition lJ may fire when enabled. Firing lj in a marking J.L produces a new marking J.L' such that

1. If PI is an input place of lj then J.L'(pl) = 0;
2. If p1 is an outpul place of lj then J.L'(pl) = 1;
3. If p; is not an input place and not an outGut place of lJ then J.L'(pl) = J.L p1) .

A place is thought of as a "condition", a static thing which does or does not hold. If a place p1 is marked (J.L(PI) = 1) it is considered to be believed [by the planning system], and if it is unmarked (J.L(pl) = 0), it is considered to be not believed [by the planning system].

Transitions are events, the Plan Net counterparts of a Procedural Net's actions . Events are dynamic entilies ; conditions are static . Events are things which "happen" .

The Allow relation (Ro) is an abstraction of two simpler relations : Cause (Re) , and Enable (Re) . Events cause conditions, and conditions enable events. The input places of a transition describe those conditions which must be believed to hold in the world for the event the transition denotes to be enabled. The firing of a transition models the activation of its event . After firing , the outpul places of the transition describe the new conditio:t;ls that are believed to hold .

Sampie plans in this formalism are given in Figures 1 and 2. The plan of Figure 1 is designed to solve a canonical Blocks World problem. An initial marking is included . The plan of Figure 2 is one for (endlessly) hammering a nail . The plans Iook !arge, but this is due to redundant information being included in the formalism. When a plan is drawn as a graph it shrinks to more modest proportians (see Drummond, forthcoming).

4 . Comparing the Nets

In this section we argue that the Plan Net representation is more powerful than the Procedural Net because of an explicit epistemological commitment to conditions and events . The Procedural Net makes no clear distinction between them. Using the Allow and Before relations as defined above , we can produce state spaces which contain cycles; that is , ones which correspond to iterative

behaviour .

c p T Re <P.T,Ra,Rb,Re,Re> ! (on c a) , (on c t3) , (on a tl) , (on b t2), (on b c), (on a b), (clear t3), (clear a) , (clear tl), (clear b) , (clear t2) , (clear c)l ! (move c a t3), (move a t1 b) , (move b t2 c) l ! ((move c a t3) , (clear a)), ((move c a t3) , (on c t3)), ((move c a t3) , (clear c)) , ((move b t2 c), (clear b)) , ((move b t2 c), (on b c)) , ((move b t2 c), (clear t2)). ((move a t1 b), (clear a)), ((move a t1 b), (clear t1)) , ((move a t1 b) , (on a b)) l Re ! ((on c a), (move c a t3)), ((clear t3) , (move c a t3)). ((clear c), (move c a t3)) , ((clear a), (move a t1 b)), ((clear b) , (move a tl b)) , ((on a tl), (move a t1 b)) , ((clear c), (move b t2 c)) , ((clear b) , (move b t2 c)) , ((on b t2), (move b t2 c)) l Ra ! ((move c a t3), (move b t2 c)), ((move b t2 c) , (move a t1 b)), ((move c a t3) , (move a t1 b)) , ((move b t2 c) , (move b t2 c)), ((move a t1 b), (move a t1 b)), ((move c a t3), (move c a t3)) l Rb ! ((move c a t3) , (move b t2 c)) , ((move b t2 c) , (move a t1 b)) l J.L(p) = 1 if p E !(on c a) , (clear t3) , (clear c) , (clear b), (on b t2) , (on a tl)l J.L(p) 0 otherwise .

NOAH (Sacerdoti , 1975 ) , and its descendents , such as NONLIN (Tate, 1976), DEVISER (Vere , 1981 ), and SIPE (Wilkins , 1983) all use plans based on Sacerdoti's original Procedural Net . The following comments are expressed principally in t erms of NOAH, but apply equally to these newer planners .

The Allow relation takes the form of a "before" link in a Procedural Net which has been introduced by pattern-directed operator invocation. Such a link might appear, for instance , between an action whi ch must make block A clear , and an action which mus t stack A on B.

c p T Re Re <P.T,Ro,Rb,Rc,Re> !Hammer-Up, Hammer-Downj ! Lift- Hammer- Up, Pound-Hammer-Down l !(Pound-Hammer-Down, Lift-Hammer- Up), (Lift-Hammer-Up, Pound-Hammer-Down) l ! (Hammer-Up, Pound-Hammer-Down). (Hammer-Down, Lift-Hammer- Up) l ! (Pound-Hammer-Down, Hammer-Down). (Lift-Hammer- Up, Hammer-Up)j !l

The Before relation appears in a Procedural Net as a "before" link introduced by the Resolve Conflicts critic . This critic analyzes operator preconditions and effecls, and inlroduces "before" erderings because of unfavourable interactions.

In Section 2, it was shown that one can take a Procedural Net, and through repeated application of the pebbling rule , determine possible net behaviours . The situation is slightly more complex when we consider deriving a Plan Net's possible behaviours. To do this, we require an initial marking of the net , the net itself, and the firing rule as provided in Definition 4. Using the initial net marking, we repeatedly fire transitions until either no enabled transitions remain, or a marking is reached that has been seen previously. A tre e or graph s tructure can be built in this manner, in which the nodes contain states {markings) of the Plan Net, and the arc s are transitions for moving from one state to another . In net Theory, this structure is often called a reachability tree {or graph), and is precisely the sort of behavioural account we generated for the Procedural Net by using the Pebbling rule. (See Pete rson, 1980, for more on net reachability. ) The important thing is that the state space constructed from a Plan Net need not be loop free . Using these nets. it is possib!e to model iterative behaviour in a natural way.

A planning system called Selah has been implemented which uses the Plan Net representation. Selah is currently able to solve "Blocks World" problems. and work is underway to extend its construction algorithms to allow it to create iterative plans .

5. Summary

This paper has defined the Plan Net using Sacerdoti's Procedural Net as a starting point. Through the introduction of a simple operational semantics, the Procedural Net was shown to be incapab!e of describing iterative behaviour. It was argued that the Plan Net can describe such behaviour . The implementation of a planner able to construct iterative plans is underway, and results from it will be reported.

Acknow!edgements

Thanks are given to the Edinburgh University AI Planning Group, and to Dave Wilkins for providing useful comment on an earlier version of this paper . I am indebted to Kar! Kempf and Barry Fox of the University of Missouri for introducing me to Pebbling . The supervision of Austin Tate has been invaluable.

Heferences

Brauer, W. (ed.). 1979 . Springer-Verlag LNCS series . Net theory and applications . Proceedings of the Advanced Course on General Net Theory of Processes and Systems, Hamburg.

Drummond , M. 1985 . Ph.D. dissertation. University of Edinburgh. (To appear .)

McDermott , D. 1983 . a logical analysis . 302- 308. Generalizing problern reduction : Proceedings of IJCAI- 83 . pp .

Peterson, J .L. 1980. modeling of systems . Prentice-Hall.

Pippenger , N. 1980. Pebbling . RC 8258 (#35937), IBM TJ Watson Research Center , Yorktown Heights , NY.

Rosenschein, S . 1984. Invited lecture at AAAI- 84 , In Austin, TX: "A perspective on planning" .

Sacerdoti, E .D. 1975. A structure for plans and behaviour. SR! Technical Note # 109.

Tate, A. 1976 . Project non-linear planner . Department of Artificial #25 . planning using a hierarchic University of Edinburgh, Intelligence Research Report

Vere, S.A. 1981. Planning in time : windows and durations for activities and goals . Jet Propulsion Laboratory, Information Systems Research section, research report.

Wilkins, D.E . 1983. independent planner . 733-740 . Representation in a domain Proceedings of IJCAI- 83 . pp .