Advanced Petri Nets and the Fluent Calculus

Abstract

In this paper we discuss conjunctive planning problems in the context of the fluent calculus and Petri nets. We show that both formalisms are equivalent in solving these problems. Thereafter, we extend actions to contain preconditions as well as obstacles. This requires to extend the fluent calculus as well as Petri nets. Again, we show that both extended formalisms are equivalent.

-

Introduction It is widely believed that humans generate models and reason with respect to these models [ 14 ]. It is less widely believed that logics can be used to adequately model human reasoning [ 3 ]. Based on ideas first presented in [ 18 ], H¨olldobler and Kencana Ramli [ 10 ] have developed a logic based on weakly completed logic programs and interpreted under the three-valued Lukasiewicz semantics; this logic was shown to adequately model human reasoning scenarios like the suppression and the selection task by generating a least model of an appropriate logic program and reasoning with respect to this least model [ 6,7 ]. Moreover, it was shown that there is a connectionist realization of this approach based on the core method [ 11,1 ].

However, human reasoning is much more complex than the above mentioned scenarios and involves – among others – reasoning about actions and causality including compositionality, concurrency, quick reactions, and resilience in the face of unexpected events. An architecture for such actions was developed in [ 2 ] based on extended Petri nets. Unfortunately, there is a huge gap between Petri nets and the logic developed by H¨olldobler and Kencana Ramli and it is not at all obvious how the two approaches can be combined. Moreover, a close inspection of [ 2 ] revealed that some concepts are only specified procedurally.

A central notion in Petri nets are tokens which are consumed and produced when executing an action. Likewise, in the equational logic programming approach to actions and causality presented in [ 12 ] resources are used. The approach was later called fluent calculus in [ 19 ]. The logic programs in the fluent calculus admit least models and reasoning is performed with respect to these models. Hence, the fluent calculus seems to be a promising candidate to add reasoning about actions and causality to the human reasoning approach of H¨olldobler and Kencana Ramli.

The goal of the research presented in this paper is to understand the relation

between the fluent calculus and the extended Petri networks used in [ 2 ]. To this end, we will rigorously define various classes of planning problems, we will map these problems into Petri nets and into the fluent calculus, and we formally prove that there is a one-to-one correspondence between the two approaches in solving such problems.

The paper is structured as follows: Following the introduction in Section 1 we

will present main notions and notations in Section 2. Conjunctive and advanced planning problems are discussed in Sections 3 and 4. In the final Section 5 we will discuss our results and point to future work. Due to lack of space we cannot include proofs; they are worked out in detail in [ 15 ] if not stated otherwise. 2

Preliminaries

Multisets Multisets are generalizations of sets, where members may occur more

than once. In this paper, multisets are depicted with the help of the parenthesis {˙ and }˙. ∅˙ denotes the empty multiset and ∪˙, ∩˙, ⊆˙, \˙, =. , and 6=˙ denote the usual operations and relations on multisets, viz. multiset-union, -intersection, -subset, -difference, -equality, -inequality, respectively. Moreover, x ∈k M holds if and if x occurs exactly k times in the multiset M, where k ∈ N.

Petri Nets A Petri net is a tuple (P, T , F ), where P and T are finite sets called

places and transitions, respectively, P ∩ T = ∅, and F ⊆˙ (P × T ) ∪˙ (T × P). A marking is a finite multiset M over P; its elements are called tokens. The pre-set •t of t ∈ T is a finite multiset with p ∈k •t iff p ∈ P ∧ (p, t) ∈k F . The post-set t• of t ∈ T is a finite multiset with p ∈k t• iff p ∈ P ∧ (t, p) ∈k F .

Let N = (P, T , F ) be a Petri net and M, M0, and M00 be markings. t ∈ T is enabled at M in N iff •t ⊆˙ M; an enabled transition t can fire leading to M0, denoted by M −→ M0, where M0 =. (M \ • t) ∪˙ t•. Firing sequences are [t] ˙ inductively defined as follows: M −→[] M; if M −[→t] M0 and M0 −→w M00 then M −[−t|−w→] M00, where w is a list of transitions. A firing sequence from M to M0 of N is a firing sequence which starts from M and yields M0.

Equational Logic Programming We assume the reader to be familiar with first-order predicate logic with equality and, in particular, with equational logic programming as, for example, presented in [9,17,13].

Fluents and Fluent Terms In planning, the notion of a fluent is often used to

describe an item which may be present in one state but not in the next state.

In the fluent calculus, fluents are non-variable terms built over some alphabet

like a, f (a), or f (X), where a is a constant, f a function symbol, and X a variable; this alphabet must not contain the binary function symbol ◦ and the constant 1 as these symbols are used to represent multisets of fluents; ground fluents are fluents which do not contain an occurrence of a variable (e.g., a and f (a)); simple fluents are fluents which are constants (e.g., a). The set of fluent terms is the smallest set satisfying the following conditions: 1 is a fluent term; each fluent is a fluent term; if s and t are fluent terms, then so is s ◦ t. As the sequences of fluents occurring in a fluent term is not important, we consider ◦ to be associative and commutative, and 1 to be a unit element with respect to ◦; let KAC1 be the corresponding equational axioms plus the axioms of equality.

There is a one-to-one correspondence between equivalence classes of fluent terms with respect to KAC1 and multisets of fluents as follows: Let t be a fluent term and M a multiset of fluents in: and

M−I =

s ◦ M0−I iiff MM ==.. {∅˙˙,s }˙ ∪˙ M0. ( 1 3

Conjunctive Planning Problems

Conjunctive planning problems were considered in [8] to relate the fluent calculus to the linear connection method and to linear logic. Here, we consider a slightly simplified version in that we restrict fluents to simple fluents.

A conjunctive planning problem (CPP) is a tuple (I, G, A), where I and G

are finite multisets of simple fluents called initial and goal state, respectively, and A is a finite set of actions; an action is an expression of the form a : C ⇒ E , where a is the name of the action and C and E are finite multisets of simple fluents called conditions and (immediate) effects, respectively.

Let S be a finite multiset of simple fluents; such multisets are called states in

the sequel. An action a : C ⇒ E is applicable to S iff C ⊆˙ S; its application leads to the state (S \˙ C) ∪˙ E . A plan is a sequence or list of actions; it transforms state S into S0 if and only if S0 is the result of successively applying the actions occurring in the plan to S. A plan is a solution to a CPP (I, G, A) if and only if it transforms I into G.

To illustrate CPPs, consider a situation where a man living in an apartment becomes severely ill and calls the ambulance. The ambulance men decide that he needs to undergo treatment in a hospital and carry him on a stretcher to the ambulance. Finally, the ambulance car is driven to the hospital. This problem is considered as a CPP with fluent ill (denoting the ill man), apt (denoting that he is in his apartment), amb (denoting that the patient is in the ambulance car), and hos (denoting that the patient is in the hospital). The action names are c (the ambulance men are carrying the patient to the ambulance car) and d (driving to the hospital). Alltogether we obtain a CPP (I, G, A), where I =. {˙ill , apt }˙, G =. {˙ill , hos }˙, and

.

A = {c : {˙ill , apt }˙ ⇒ {˙ill , amb }˙, d : {˙ill , amb }˙ ⇒ {˙ill , hos }˙}.

The goal state G is reached from the initial state I by applying first c yielding

the intermediate state {˙ill , amb }˙ and, thereafter, applying d. 3.1

Conjunctive Planning Problems in the Fluent Calculus

This subsection is based on [12], where an equational logic programming solution

to CPPs was presented. For each action a : C ⇒ E in a given CPP a fact action(C−I , a, E −I ) is specified; let KA be the set of all facts of this form for a given CPP. For the running example we obtain

KA = {action(ill ◦ apt , c, ill ◦ amb), action(ill ◦ amb, d, ill ◦ hos)} The applicability of an action is specified by

applicable(C ◦ Z, A, E ◦ Z) ← action(C, A, E), where Z is a variable which will be used to collect all fluents of a state which are not affected by the application of an action. Causality is specified with the help of a ternary predicate symbol causes. Intuitively, causes(X, P, Y ) is used to represent that the execution of plan P in state X transforms X into state Y . causes is specified inductively on the structure of plans, i.e., lists of actions: causes(X, [ ], X) causes(X, [A|P ], Y ) ← applicable(X, A, U ) ∧ causes(U, P, Y )

Let KC be the set containing the clauses for applicable and causes. A CPP

(I, G, A) can now be represented in the fluent calculus by the question of whether

KA ∪ KC ∪ KAC1 |= (∃P ) causes(I−I , P, G−I ), and SLDE-resolution can be applied to compute an answer substitution for P encoding a solution for the CPP if it is solvable.

Let F CQ denote the fluent calculus representation of a CPP Q. The following

theorem is proven in [ 8 ]: Theorem 1. Let Q be a CPP. The following statements are equivalent for a plan p: 1. p is a solution for Q.

2. p is generated by SLDE-resolution for F CQ.

3.2

Conjunctive Planning Problems in Petri Nets Let Q = (I, G, A) be a CPP. The Petri net NQ = (P, T , F ) together with the markings I and G is the Petri net representation of Q, where P is the set of all simple fluents occurring in Q, T is the set of all action names occurring in Q, (p, t) ∈k F if and only if t : C ⇒ E ∈ A such that p ∈k C, and (t, p) ∈k F if and only if t : C ⇒ E ∈ A such that p ∈k E . apt • c d

hos amb • ill a ∈OTnewsihthou•lad =o.bCseravnedtah•at=.foEr.eCacohnvaecrtsieolny,aw:hCen⇒evEerina tArawnseitfiionnd ta itsraennsaibtiloend in NQ given a marking M, then there exists an action with name t in A which is applicable in M.

The question of whether there exists a plan p solving a CPP (I, G, A) is the

question of whether there exists a firing sequence from I to G in NQ. The Petri net for the running example is depicted in Figure 1. One should observe that [c, d] is a firing sequence leading from the {˙apt , ill }˙ to {˙ill , hos }˙.

As a first result we extend Theorem 1. Throughout this subsection, let Q be the

CPP (I, G, A) and F CQ and NQ be its representations in the fluent calculus and

in Petri nets, respectively.

Theorem 2. The following statements are equivalent for a plan p: 1. p is a solution for Q.

2. p is generated by SLDE-resolution for F CQ.

3. p is a firing sequence from I to G in NQ.

Proof. Because of Theorem 1 it suffices to show that the 2. and 3. are equivalent.

By induction on the number of transitions occurring in p in can be shown that

3. implies 2.. The converse can be shown to hold by induction on the number of actions occurring in p.

4

Advanced Planning Problems

In conjunctive planning problems, all conditions of an action are consumed when

the action is executed. In this section we extend planning problems to allow preconditions which are only tested when an action is executed but are not consumed and to allow obstacles which prevent an action from being executed even if its conditions are satisfied.

An advanced conjunctive planning problem (ACPP) is a tuple (I, G, A), where

I and G are finite multisets of simple fluents called initial and goal state, respectively, and A is a finite set of advanced actions; an advanced action is an

expression of the form a : C =R=,⇒O E , where a is the name of the action, C, R, O and E are multisets of simple fluents called conditions, preconditions, obstacles, and effects, respectively, and C ∩˙ E =. ∅˙.

Let S be a state. An extended action a : C =R=,⇒O E is applicable to S if and only if C ⊆˙ S, R ⊆˙ S, and ∀e ∈k O(e ∈j S → j < k). Its application yields the state (S \˙ C) ∪˙ E . If the last condition in the definition of applicability to

S is violated, i.e., if there is an extended action with name a, obstacles O and

e ∈k O, and e ∈j S such that j ≥ k, then a is hindered in S. Plans and solutions are defined as before.

To illustrate ACPPs we modify the running example by assuming that the patient was so fat that he did not fit through the appartment door. Hence, the ambulance men cannot carry him to the ambulance car. We introduce an ad. ditional fluent fat and obtain the ACPP (I, G, A), where I = {˙ill , fat , apt }˙, G =. {˙ill , fat , hos }˙, and

A = {c : {˙apt }˙ ={˙=il=l}˙=, {=˙f=a⇒t}˙ {˙amb }˙, d : {˙amb }˙ ={=˙i=ll =}˙⇒∅˙ {˙hos }˙}.

. , Obviously, this ACPP cannot be solved as the obstacle fat hinders the application of the action c. By the way, the ill man was later rescued with a help of a mobile cran, which carried him out of his apartment through a window. 4.1

Advanced Planning Problems in Petri Nets

Petri nets were extended by so-called inhibitory arcs, which may by weighted

and which increase the modeling power of Petri nets to the level of Turing machines [ 16,5,4 ]. We combine inhibitor arcs with so-called test arcs, which were introduced in [ 2 ] to allow for places, which may contain real-valued or discrete tokens in order to enable an action, but which are not consumed.

An advanced Petri net is a tuple (P, T , F , H, L), where (P, T , F ) is a Petri

net, H ⊆˙ P × T , and L ⊆˙ P × T ; H and L are the multiset of inhibitory and test arcs, respectively. The multiset Ht of inhibitory places of transition t ∈ T is defined by p ∈k Ht if and only if p ∈ P ∧ (p, t) ∈k H. Likewise, the multiset Nt of test places of transition t is defined as p ∈k Nt if and only if p ∈ P ∧ (p, t) ∈k L.

Let N = (P, T , F , H, L) be an advanced Petri net and M a marking. t ∈ T is enabled at M in N if and only if •t ⊆˙ M, ∀p ∈ P((p, t) ∈k L∧p ∈j M → k ≤ j), and ∀p ∈ P((p, t) ∈m H ∧ p ∈n M → m > n). The notions fire and firing sequence are defined as before.

Let Q = (I, G, A) be an ACPP. The Petri net NQA = (P, T , F , H, L) together with the markings I and G is the Petri net representation of Q, where P, T , and F are defined as in Subsection 3.2, (p, t) ∈k H if and only if ∃(t : C =R=,⇒O E ) ∈ A such that p ∈k O, and (p, t) ∈k L if and only if ∃(t : C =R=,⇒O E ) ∈ A such that p ∈k R. The Petri net for the modified running example is shown in Figure 2.

From this definition we learn that for every action t : C =R=,⇒O E in A we find a . . . . transition t ∈ NQA with Ht = O, Nt = R, •t = C, and t• = E . One should observe apt • • fat amb • ill c d hos that the requirements for enabling a transition in NQA are the requirements for the applicability of an action in Q. Hence, a transition t is enabled at marking M in NQA if and only if there exists an action t in Q with t being applicable in M. each advanced action a : C =R=,⇒O E and each obstacle o ∈k O the fact k times inhib(zo ◦ .}.|. ◦ o{, a)

precon(R−I , A) is added to KA. In addition, for each advanced action a : C =R=,⇒O E the fact is added to KA; it is used in the (modified) definition of applicable to test whether all preconditions are met. For our modified running example we obtain KA = { action(apt , c, amb), action(amb, d, hos),

inhib(fat , c), precon(ill , c), precon(ill , d) }.

The rule

hinder (X ◦ Z, A) ← inhib(X, A) is added to KC to prohibit the application of action A whenever sufficiently many obstacles X are present in a state X ◦ Z. The definition of applicable in

KC is modified to

applicable(C ◦ Z, A, E ◦ Z) ← action(C, A, E) ∧ precon(R, A) ∧ R ◦ Y ≈ C ◦ Z ∧ ¬hinder (C ◦ Z, A) where the subgoal R ◦ Y ≈ C ◦ Z is used to check whether the preconditions R of action A are satisfied in state C ◦ Z. As the equality predicate ≈ is now used explicitly as a subgoal, the axiom of reflexivity

X ≈ X must be added to KC , effectively forcing the AC1-unification of the left-hand and the right-hand side of the subgoal R ◦ Y ≈ C ◦ Z.

Let KAA and KCA be the modified sets of clauses for a given ACPP (I, G, A).

The ACPP can now be presented in the fluent calculus by the question of whether

KAA ∪ KCA ∪ KAC1 |= (∃P ) causes(I−I , P, G−I ), and SLDENF-resolution can be applied to compute an answer substitution for P , if existing [ 13 ]. SLDENF-resolution is sound [ 17 ], but it is only shown to be complete if the completion of KAA ∪ KCA ∪ KAC1 is satisfiable and SLDENFderivations neither flounder nor are infinite [ 13 ].

Lemma 3. The completion of KAA ∪ KCA ∪ KAC1 is satisfiable.

Proof. By construction of a model for the completion KAA ∪ KCA ∪ KAC1.

Regarding the question of whether SLDENF-derivations flounder or are infi

nite we observe that the definition of causes is recursive in the second argument, which is a list. If the length of this list is known in advance and the first argument of causes is a ground fluent term (which holds by the definition of a planning problem), then SLDENF-derivations neither flounder nor are infinite. Proposition 4. Let s be a ground fluent term and a the name of an action.

Then, each SLDENF-derivation of ← hinder (s, a) is finite.

Proof. Follows immediately from the definition of hinder and inhib.

Proposition 5. No SLDENF-derivation of ← causes(I−I , [A1, . . . , An], G−I ) flounders or is infinite.

Proof. By induction on n.

Based on this result we must refine the fluent calculus representation of an

ACPP to the question of whether

KAA ∪ KCA ∪ KAC1 |= (∃A1, . . . , An) causes(I−I , [A1, . . . , An], G−I ). and iteratively increase n in the search for a solution of the planning problem.

Finally, we show that hinder prevents actions from being applicable:

Proposition 6. There are enough obstacles in a state S to hinder an advanced

action a if and only if there is an SLDENF-resolution proof of ← hinder (S−I , a).

Proof. Follows from the definitions of hinder and inhib.

Petri Nets versus Fluent Calculus Representations

Throughout this subsection, let Q be the ACPP (I, G, A), F CQA and NQA be

its representations in the advanced fluent calculus and the advanced Petri nets, respectively, and p be the plan [a1, . . . , an].

Theorem 7. The following statements are equivalent for a plan p: 1. p is a solution for Q.

2. p is generated by SLDENF-resolution for F CQA.

3. p is a firing sequence from I to G in NQA.

Proof. The theorem is obtained if we can prove that 1. implies 2., 2. implies 3., and 3. implies 1. These implications can be shown by inductions on the length of the plan p, on the length of the SLDENF-resolution refutation, and on the length of the firing sequence, respectively.

5

Discussion In this paper we have shown that there is a close correspondence between Petri nets and the fluent calculus for conjunctive planning problems. This correspondence is preserved if we extended Petri nets and the fluent calculus by test and inhibitory arcs. The correspondence can be even further extended to planning problems with fluents containing real values as investigated in [ 15 ]. In [ 2 ], it was shown that Petri nets can be combined with Bayes nets via real-valued fluents, and, hence, it should now be possible to combine the fluent calculus and Bayes nets. However, this needs to be rigourously investigated in the near future.

Whereas in this paper we were computing answer substitutions by SLDE

and SLDENF-resolution in the fluent calculus, we also like to invesigate the corresponding fixpoint characterization of the fluent calculus. This is the obvious next step in order to combine the human reasoning approach mentioned in the introduction with reasoning about actions and causality in the fluent calculus.

Finally, the ultimate goal is a connectionist realization of the combined approach within the core method [11,1].

Acknowledgements We would like to thank Bertram Fronh¨ofer and Christoph

Wernhard for many fruitful discussions and the anonymous referees for there comments.

References

1. S. Bader and S. Ho¨lldobler. The core method: Connectionist model generation . In S. Kollias et. al., editor, Proceedings of the 16th International Conference on Artificial Neural Networks (ICANN) , volume 4132 of Lecture Notes in Computer Science, pages 1 - 13 . Springer, 2006 .

2. L. Barrett . An Architecture for Structured, Concurrent, Real-time Action . PhD thesis , Computer Science Division, University of California at Berkeley, 2010 .

3. R. M. J. Byrne . Suppressing valid inferences with conditionals . Cognition , 31 : 61 - 83 , 1989 .

4. R. David and H. Alla . On hybrid Petri nets . Discrete Event Dynamic Systems , 11 ( 1-2 ): 9 - 40 , 2001 .

5. J. Desel and W. Reisig . Lectures on Petri Nets I: Basic Models , volume 1491 of LNCS , chapter Place/Transition Petri Nets, pages 122 - 173 . Springer, 1998 .

6. E.-A. Dietz , S. Ho¨lldobler, and M. Ragni . A computational logic approach to the suppression task . In N. Miyake, D. Peebles , and R. P . Cooper, editors, Proceedings of the 34th Annual Conference of the Cognitive Science Society , pages 1500 - 1505 . Cognitive Science Society , 2012 .

7. E.-A. Dietz , S. Ho¨lldobler, and M. Ragni . A computational logic approach to the abstract and the social case of the selection task . In Proceedings Eleventh International Symposium on Logical Formalizations of Commonsense Reasoning , 2013 .

8. G. Große , S. Ho¨lldobler, and J. Schneeberger . Linear deductive planning . Journal of Logic and Computation , 6 ( 2 ): 233 - 262 , 1996 .

9. S. Ho¨lldobler. Foundations of Equational Logic Programming , volume 353 of Lecture Notes in Artificial Intelligence . Springer, Berlin, 1989 .

10. S. Ho¨lldobler and C. D. P. Kencana Ramli . Logic programs under three-valued Lukasiewicz's semantics . In P. M. Hill and D. S. Warren, editors, Logic Programming , volume 5649 of Lecture Notes in Computer Science, pages 464 - 478 . Springer Berlin Heidelberg, 2009 .

11. S. Ho¨lldobler and C. D. P. Kencana Ramli . Logics and networks for human reasoning . In C. Alippi, Marios M. Polycarpou , Christos G. Panayiotou, and Georgios Ellinasetal, editors, Artificial Neural Networks - ICANN , volume 5769 of Lecture Notes in Computer Science, pages 85 - 94 . Springer Berlin Heidelberg, 2009 .

12. S. Ho¨lldobler and J. Schneeberger . A new deductive approach to planning . New Generation Computing , 8 : 225 - 244 , 1990 .

13. S. Ho¨lldobler and M. Thielscher . Computing change and specificity with equational logic programs . Annals of Mathematics and Artificial Intelligence , 14 : 99 - 133 , 1995 .

14. P.N. Johnson-Laird . Mental Models: Towards a Cognitive Science of Language, Inference, and Consciousness . Cambridge University Press, Cambridge, 1983 .

15. F. Jovan . Planning problems in Petri nets and fluent calculus . Master's thesis , TU Dresden, Faculty of Computer Science, 2014 .

16. T. Murata . Petri nets: Properties, analysis and applications . In Proceedings of the IEEE , volume 77 , pages 541 - 580 , 1989 .

17. J. C. Shepherdson . SLDNF-resolution with equality . Journal of Automated Reasoning , 8 : 297 - 306 , 1992 .

18. K. Stenning and M. van Lambalgen . Human Reasoning and Cognitive Science . MIT Press, 2008 .

19. M. Thielscher . Introduction to the fluent calculus . Electronic Transactions on Artificial Intelligence , 2 : 179 - 192 , 1998 .