# Temporal Reasoning with Abductive Logic Programming

发布时间:2021-11-29 06:10:00

With respect to the action language and its extensions, there are four major approaches to the translation of -like action languages into logic programs . In what follows we will brie?y compare our work with [11, 7, 8, 3]. In [11] Gelfond and Lifschitz proposed the action language , presented a translation GL from to extended logic programs with answer sets as semantics, and showed that their translation GL is sound for domain descriptions without similar effect propositions, but not complete. The main differences between [11] and ours lie in the following facts: (1) Concurrent actions are not directly supported in ; (2) Fluents are three-valued in , while they are two-valued in . As a consequence, there may not be any state transition satisfying e-propositions of some domain descriptions of ; (3) GL and use different logic programming paradigms and semantics: GL uses extended logic programs and answer set semantics, while uses abductive normal logic programs and predicate completion semantics. Since D is acyclic, its predicate completion semantics coincides with generalized stable model semantics and well-founded model semantics; (4) Since our translation is both sound and complete for all domain descriptions, we can immediately combine our work with Kartha’s work [15] and relate the abductive normal logic program D to three other formalisms of reasoning about actions, proposed by Pednault [20], Reiter [22] and Baker [2]. In [7] Denecker and Schreye elaborated on Gelfond and Lifschitz’ original work, and proposed a translation DS from domain descriptions in to abductive normal logic programs. The main differences between [7] and our work are: (1) Concurrent actions are not directly , while they are supported in ; (2) Fluents are three-valued in two-valued in . (3) Our translation is complete for any domain description, but DS is complete only for e-consistent domain descriptions. We should point out that our logic programming paradigm is the same as that of [7]. Another approach, similar to [7], was proposed by Dung [8], who proposed a translation from to logic programs with a special semantics similar to the completion semantics. Dung treats the ?uent symbol and its negation symmetrically. In particular, Dung considered its application in database integrity constraints in the presence of updates. Concurrent actions are not considered in Dung [8]. In [3] Baral and Gelfond made a ?rst step to extend with concurrent actions. The semantical difference between and BG has been discussed in Section 2. Another difference lies in the translation of domain descriptions into logic programs: BG inherits the incompleteness of GL , but our translation is complete for any domain description.

A

A

ACKNOWLEDGEMENTS

This work was supported by a post-doctoral fellowship from JNICT under PRAXIS XXI/BPD/4165/94 to the ?rst author, and JNICT PROLOPPE project under PRAXIS/3/31/TIT/24/94.

A

A

REFERENCES

[1] Apt, K.R. and Bezem, M., Acyclic programs, Proc. of ICLP 90, MIT Press, 1990, 579–597 [2] Baker, A.B., Nonmonotonic reasoning in the framework of situation calculus, Arti?cial Intelligence, 49, 1991, 5–23 [3] Baral, C. and Gelfond, M., Representing concurrent actions in extended logic programming, Proc. of IJCAI’93, 1993, pp. 866–871 [4] Console, L., Dupre, D.T., and Torasso, P., On the relationship between abduction and deduction, J. of Logic and Computation, 1:5, 1991, 661– 690 [5] Dam? sio, C. V., Pereira, L.M., and Wolfgang, N. , REVISE: An Exa tended Logic Programming System for Revising Knowledge Bases, Proc. of KR’94, 1994 [6] Denecker, M., De Schreye, D., SLDNFA: an abductive procedure for normal abductive programs, Logic Programming: Proc. of 1992 Int’l Joint Conference and Symposium, . Apt, ed., MIT Press, 1992, 686-700 [7] Denecker, M. and de Schreye, D., Representing incomplete knowledge in abductive logic programming, Logic Programming:Proc. of the 1993 Int’l Symposium, MIT Press, 1993, 147–163 [8] Dung, P.M., Representing actions in logic programming and its application in database updates, Proc. of ICLP 93, MIT Press, 1993, 222–238 [9] Gelfond, M., and Lifschitz, V., The stable model semantics for logic programming, In. Proc. of ILPS’88, MIT Press, 1988, 1070-1080 [10] Gelfond, M. and V. Lifschitz, Logic programs with classical negation, Proc. of ICLP’90, MIT Press, 1990, pp. 579-597 [11] Gelfond, M. and Lifschitz, V., Representing action and change by logic programs, Journal of Logic Programming, Vol.17, 1993, 301–322 [12] Gelfond, M., Lifschitz, V., and Rabinov, A., What are the limitations of the situation calculus?, Automated Reasoning: Essays in Honor of Woody Bledsoe, R. Moore (ed.), 1991, 167-179 [13] Hanks, S, and McDermott, D., Nonmonotonic logics and temporal projection, Arti?cial Intelligence, 35, 1988, 165–195 [14] Kakas, A.C., Mancarella, P., Generalized stable models: A semantics for abduction, Proc. of ECAI’90, 1990 [15] Kartha, G.N., Soundness and completeness theorems for three formalizations of action, Proc. IJCAI93, 1993, 712–718 [16] Kartha, G.N. and Lifschitz, V., Actions with indirect effects: preliminary report, Proc. of KR94, 1994, 341–350 [17] Lifschitz, V., Nested Abnormal Theories, Uni. of Texas at Austin, manuscript, 1994 [18] F. Lin and Y. Shoham, Provably correct theories of actions: preliminary report, Proc. of AAAI-91, 1991 [19] F. Lin and Y. Shoham, Concurrent actions in the situation calculus, Proc. of AAAI-92, 1992, pp.590-595 [20] Pednault, E. P. D., ADL: Exploring the middle ground between STRIPS and the situation calculus, Proc. of KR’89, R. J. Brachman, H. Levesque, R. Reiter (eds.), Morgan Kaufmann Publishers, Inc., 324–332 [21] Pereira, L. M., Alferes, J. J., and Apar?cio, J. N., Nonmonotonic Rea? soning with Well Founded Semantics, In: K. Furukawa (ed.), Proc. of ICLP’91 , MIT Press, 1991, 475-489 [22] Reiter, R., The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression, Arti?cial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, V. Lifschitz (ed.), Academic Press, San Diego, CA, 1991, 359–380 [23] Satoh, K., Iwayama, N., A query evaluation method for abductive logic programming Logic Programming:Proc. of 1992 Int’l Joint Conference and Symposium, 1992, 671-685

A A

AC

A

A

A A

AC

A

AC

A

A

6

CONCLUSIONS

We have analyzed two proposals for semantics of concurrent actions [19, 3], and given a new semantics to common-sense concurrent actions. We have also extended with concurrent actions, and presented a translation from domain descriptions in the resulting new action description language to abductive logic programs, given the soundness and completeness theorems of the translation. We have also compared ours with related work. Our method is applicable to the temporal projection problem with incomplete information, as well as to reasoning about the past. Many benchmark examples in the framework of this paper have been experimented with the latest version [5] of the REVISE system. The future work will focus on extensions of (by allowing, e.g, constraints, durative actions, etc.) and its use in practice.

A

AC

Abduction, Temporal and Causal Reasoning

17

R. Li and L. M. Pereira

initiates(A; F; S ) imm initiates(A; F;S ) initiates(A; F; S ) subacteq(B; A); imm initiates(B; F; S ); not clip initiates(F; B; A; S ): terminates(A; F;S ) imm terminates(A; F; S ): terminates(A; F;S ) subacteq(B; A); imm terminates(B; F;S ); not clip terminates(F; B; A; S ): causes(F;S; A; B ) subacteq(B; A); imm initiates(B; F; S ); not clip initiates(F; B; A; S ); not clip cause1(F;B; A; S ): causes(F;S; A; B ) subacteq(B; A); imm terminates(B; F;S ); not clip terminates(F; B; A; S ) not clip cause2(F;B; A; S ): delta(A;S; F ) initiates(A; G; S ); terminates(A; G; S ); causes(G; S; A; B ); initiates(B; F;S ): delta(A;S; F ) initiates(A; G; S ); terminates(A; G; S ); causes(G; S; A; B ); terminates(B; F; S ): clip initiates(F; B; A; S ) subact(B; C ); subacteq(C; A); imm terminates(C; F; S ): clip terminates(F; B; A; S ) subact(B; C ); subacteq(C; A); imm initiates(C; F; S ): clip cause1(F;B; A; S ) subact(B; C ); subacteq(C; A); imm initiates(C; F; S ); not clip initiates(F; C; A; S ): clip cause2(F;B; A; S ) subact(B; C ); subacteq(C; A); imm terminates(C; F; S ); not clip terminates(F; C; A; S ):

4. Main Predicates: The following predicates are used to determine whether a ?uent is true or false in a situation.

The integrity constraints, denoted by ICD , are de?ned as follows: For each value proposition F after A1 ; : : : ; Am , we have:

Holds(F;result(A1; : : : ; Am ; s0 )) false

not Holds(F;result(A1 ; : : : ; Am ; s0 )):

(5)

As we will use the predicate completion semantics, the above integrity constraint can be equivalently transformed into

Note that we cannot abduce a ?uent to be both true and false. For this purpose we add the following domain-independent constraint:

false is true(F; S0 ); is false(F; S0 ): (6) The literal false is always interpreted as logical falsity, and all rules with false as heads function as integrity constraints. The predicates initially true(F ) and initially false(F ) are taken as abducible predicates used to capture the incomplete knowledge about the initial situation. The semantics of D is de?ned to be the union of the integrity constraints, the Clark Equality Theory, and the ?rstorder theory obtained by completing all the non-abducible predicates [4]. The de?nition for abducible predicates initially true(F ) and initially false(F ) are left open. We will write COMP ( D) to denote the semantics of of D. The following two results justify the above semantics de?nition. Proposition 4.1 D is an acyclic program with ?rst-order constraints in the sense of [1]. Corollary 4.2 For the abductive logic program D, COMP ( D) coincides with its generalized stable model semantics [14] and generalized well-founded model semantics [21]. The following two technical results are proved in the long version of this paper. Theorem 4.3 (Soundness) Let D be any domain description. For any value proposition Q, if COMP ( D) = Q, then D entails Q.

is true(F;result(A; S )) is true(F; S ); not terminates(A; F; S ); not delta(A; S; F ): is true(F;result(A; S )) initiates(A; F; S ); not terminates(A; F; S ); not delta(A; S; F ): is false(F;result(A; S )) is false(F; S ); not initiates(A; F; S ); not delta(A; S; F ): is false(F;result(A; S )) terminates(A; F;S ); not initiates(A; F; S ); not delta(A; S; F ):

5. Domain-Speci?c Predicates The syntax and semantics of the following predicates depend on domain descriptions. Let F be a ?uent name, i.e., F Σf . Then, we write Holds(F;S ) to stand for is true(F; S ) and write Holds( F;S ) for is false(F;S ).

j

Theorem 4.4 (Completeness) Let D be a domain description. For any value proposition Q, if D entails Q, then COMP ( D) = Q.

j

2

For each effect proposition a causes f if p1 ; : : : ; pn in where f is positive, we have a logic programming rule:

:

D,

imm initiates(a; f;S ) Holds(p1; S ); : : : ; Holds(pn; S ): For each effect proposition a causes :f if p1 ; : : : ; pn , where f is positive, we have a logic programming rule: imm terminates(a; f; S ) Holds(p1; S ); : : : ; Holds(pn; S ):

Abduction, Temporal and Causal Reasoning 16

Since our translation is both sound and complete, we can reduce temporal reasoning in to abductive query evaluaiton in logic program D. The work reported in this paper has been experimented with the latest version of the REVISE system [5]. The use of the REVISE system is not essential, and other abductive query evaluaiton procedures for normal logic programs such as SLDNFA [6] and that in [23] should also work. If for every ?uent name F , one and only one of initially F and initially F appears in a domain description, then PROLOG can be used for temporal projection after (3), (4), and (6) are removed and the integrity constraitns are represented only in the form of (5). For example, temporal reasoning in the Yale Shooting domain DY SP can be done in PROLOG. Furthermore, if we introduce more propositions, say observation propositions, we can abductively diagnose action domains when there is a discrepancy between predicted propositions and observed propositions. For the sake of space limitation, we will not go into deeper discussions.

AC

:

5

RELATED WORK

There have been many reports on temporal reasoning. It is extremely dif?cult, if not impossible, to compare our work with all of them. R. Li and L. M. Pereira

each 1 i m, Pi holds in . Moreover, we say that the execution of A in initiates a ?uent expression F if A immediately initiates F , or there is a B A such that execution of B in immediately initiates F and there is no C such that B C A, where execution of C in immediately initiates F . Let F be positive. When A initiates F , we will say that A terminates F . We de?ne two set-ranged functions as follows:

3.3

An alternative semantics

:

:

In this subsection we brie?y introduce an alternative semantics, which is more skeptical than that in the last subsection. For the sake of simplicity, let F and P be two positive ?uents. Consider

A causes F if P F will be regarded as unchanged by A when A is performed in state , if P 62 + . When P 62 + , there are two possibilities: P 2 ? ? , the truth value of P is not known. or P 62 ? . If P 62 + However, P may be actually true or false. If P were actually true, then F would be actually true after A is done in . The problem will arise when F 2 ? . Based on this analysis, we have developed

Initiate(A; Terminate(A;

) )

= =

fF : F 2 Σf and A initiates F in g fF : F 2 Σf and A initiates :F in g

Note that Initiate(A; ) and Terminate(A; ) are not necessarily disjoint. We also need a set-ranged function Cause(F; ; A), (for ?uent name F , state , and action expression A), which is de?ned to contain and only contain all the set-inclusion minimal subactions B of A satisfying: B immediately initiates F (or F , resp.) in and there is no C such that B C A, where C immediately initiates F (or F , resp.) in . If B Cause(F; ; A), we will say that B is a cause for the change in truth values of the ?uent name F in when A is done. The truth value of the ?uent name F may change in two ways: from true to false and from false to true. Note that the subaction B is set-inclusion minimal among all subactions which satisfy one of the two conditions above. For later purpose we also need one more auxiliary functions:

:

:

2

?(A; ) where

=

B2W

(

Initiate(B;

)

Terminate(B;

))

an alternative but more skeptical semantics which is a slight reduct from the semantics in the last subsection in the following way: When F ? and P + ? , F will be regarded as unknown after A is done in instead of unchanged by disabling the inertia law on F in state . It seems to us that this alternative semantics is more skeptical and closer to reality. This alternative semantics is almost the same as the semantics in the previous section, and their difference is best illustrated by the following two examples. Let D1 = initially F . A causes F if P , and D2 = initially F . A causes F if P . According to the new alternative semantics, F should remain to be true if A is done in the initial state in the domain D1 , while F should be unknown if A is done in the initial state in the domain D2 . The detailed technical de?nition of this alternative semantics will be left out. In the following section, we will only use the semantics in the previous subsection.

2

62

g

f

:

f

g

W=

F 2Initiate(A; )\Terminate(A;

Cause(F; ; A)

)

4

FROM AC TO ABDUCTIVE LOGIC PROGRAMS

Intuitively speaking, ?(A; ) denotes those ?uents in?uenced by subactions of A which have con?icting effects. All of the ?uents in?uenced by these subactions will be made unde?ned in the new situation resulting from doing A. De?nition 3.1 (Model) A structure ( description D iff

0

; Φ) is a model of a domain

Every v-proposition of D is satis?ed in ( 0 ; Φ). For every action expression A and every state , Φ(A; ) = where

In order to automate temporal reasoning in , now we present a sound and complete translation from domain descriptions in to abductive logic programs. The familiarity with abductive logic programming is assumed. We write imm to abbreviate “immediately” in imm initiates(A; F;S ) and imm terminates(A; F;S ). In the translation, all the predicates are either self-explanatory or mirror the de?nitions of Subsection 3.2. The symbol not in logic programs denotes the negation-as-failure operator. Let D be a domain description in . The translation D consists of a normal logic program and a set of constraints, de?ned as follows:

A

AC

AC

hS ; S ? i

+

S + = ( + Initiate(A; )) n Terminate(A; ) n ?(A; S ? = ( ? Terminate(A; )) n Initiate(A; ) n ?(A;

) )

1. Auxiliary predicates about subactions: Assume that we are given standard rules for set-theoretical predicates member(A; S ), subseteq(S1 ; S2 ). Sets can be represented by lists. Using these predicates we can de?ne subacteq(S1 ; S2 ) and subact(S1 ; S2 ) about subactions in logic programming rules. 2. Initialization:

A domain description is consistent if it has a model. A domain description is complete if it has exactly one model. We will use Mod(D) to denote the set of all models of D. De?nition 3.2 (Entailment) A v-proposition is entailed by a domain description D if it is satis?ed in every model of D. All of DY SP , Ddoor , and Dsoup de?ned before are complete since they have only one model, respectively. Abduction, Temporal and Causal Reasoning 15

is true(F;s0 ) is false(F;s0 )

where

initially true(F ): initially false(F ):

(3) (4)

3. Auxiliary Predicates: These auxiliary predicates will be used to de?ne two main predicates is true(F;S ) and is false(F;S ), which indicate whether ?uent F is true or false in situation S . R. Li and L. M. Pereira

s0 is a new symbol to denote the initial situation. The initially true(F ) and initially false(F ) are taken to be abducible predicates. If a ?uent name F is abduced to be true (false, resp.) initially, then it is true (false, resp.) in the initial situation s0 .

In Lin and Shoham’s solution, it is required to be able to derive whether or not the door is closed in the next situation in order to guarantee the epistemological completeness. The epistemological completeness implies that in any situation one can always decide whether a ?uent is true or not. Thus, if the door is initially closed, then the door will still be closed after Open; Close is done; if the door is initially open, then the door will still be open after Open; Close is done. This is true when both actions exert exactly the same force according to mechanics. But it is not the case in common sense, and it does not seem to be well justi?ed that we could predict a complete description of the resulting situation after the concurrent action Open; Close is done. In Baral and Gelfond’s solution, after Open; Close is done, the resulting situation does not exist and Open; Close is not executable. Baral and Gelfond de?ne the state (situation) transition by doing actions as a partial mapping. For those concurrent actions with con?icting effects such as Open; Close , the state transition is not de?ned. By [3], any successive actions are not executable after Open; Close is done. Now assume we have an additional action, Switch, which denotes switching a light. According to [3] the action sequence Open; Close ; Switch is unexecutable. In common sense, the status of the light should change, although the status of the door is not known. Now consider another concurrent action Open; Close; Switch . According to [3] the concurrent action Open; Close; Switch is not executable, and the resulting situation is not de?ned. Although Open and Close have con?citing effects, we can at least infer that the status of the light will be changed after Open; Close; Switch is done. In this paper we will give a new semantics to concurrent actions. When subactions of a concurrent action do not have con?icting effects, it can be proved that our semantics coincides with Lin-Shoham’s and Baral-Gelfond’s. When two subactions of a concurrent action have con?icting effects, the truth value of all ?uents affected by the two subactions will be left unde?ned. For example, the ?uent denoting the status of the door will be left unde?ned after Open; Close is done. In our new semantics, we can infer, for example, the door will be closed after the sequence of actions Open; Close ; Close is done, the status of the light will be changed after Open; Close; Switch or Open; Close ; Switch is done. We think that our new semantics is closer to our common-sense reality than the semantics of [19] and [3]. The details of the semantics will be given in Subsection 3.2. Reasonign about effects of (concurrent) actions is automated with abductive logic programming, and temporal reasoning is thus reduced to abductive query evaluation.

f

g

f

g

f

g

f f

g g

An action expression is de?ned to be a non-empty ?nite set of atomic action names. We say that an action expression A is a subaction expression (proper subaction expression) of B iff A B (A B ). If A is a subaction expression of B , we often say that B contains A. We will simply write A for A if A is atomic. An action expression denotes a concurrent action composed of atomic actions which happen at the same time. Fluent expressions and action expressions will simply be called ?uents and actions, respectively, if no confusion arises. In there are two kinds of propositions: value propositions and effect propositions, simply called v-propositions and e-propositions. A v-proposition is a statement of the form

f g

AC

f

g

F after A1; : : : ; Am (1) where F is a ?uent expression and A1 ; : : : ; Am (m 0) are action expressions. If m = 0, then we will write it as initially F: An

e-proposition is a statement of the form

f

g

f

g

f f

f

g g

g

f

g

f

f

g

f

g

g

propositions and e-propositions. For example, a door-light domain is described as follows: Ddoor = initially Closed. initially On. Open causes Closed. Close causes Closed. Switch causes On if On. Switch causes On if On . The Yale Shooting domain [13] is as follows: DY SP = initially Loaded. initially Alive. Shoot causes Alive if Loaded. Shoot causes Loaded: Load causes Loaded . The Murder Mystery domain is obtained from DY SP by substituting Alive after Shoot; Wait for initially Loaded. Mary’s Soup [12] domain is de?ned as follows. Whenever Mary lifts the bowl with only one hand, she will spill the soup. But when she lifts the bowl with two hands, she will not spill the soup. Let LL and LR to denote lifting the bowl with the left hand and the right hand, respectively. Then, the domain can be described as follows: Dsoup = initially Spilled. LL causes Spilled. LR causes Spilled. LL; LR causes Spilled .

A causes F if P1 ; : : : ; Pn (2) where A is an action expression, and each of F; P1 ; : : : ; Pn (n 0) is a ?uent expression. If n = 0, then we will write it as A causes F: Given the alphabet of a domain, its description D is a set of v-

f : f :

: g :

:

:

:

:

g

:

f

f

g

:

:

g

3.2

Semantics of AC

3

AN ACTION DESCRIPTION LANGUAGE AND ITS SEMANTICS

A

In this section we extend Gelfond and Lifschitz’ action language with concurrent actions, and give a new semantics to concurrent actions. The resulting language is denoted by .

AC

3.1

Syntax of AC

We begin with the alphabet Σ of a domain, which consists of two disjoint non-empty sets of symbols Σf and Σa, called ?uent names and atomic action names, respectively. We will often use self-explanatory ?uent names and atomic action names when no confusion arises. A ?uent expressionis de?ned to be a ?uent name possibly preceded by . A ?uent expression is also called a positive ?uent if it only consists of a ?uent name; otherwise it is called a negative ?uent.

:

The semantics of is de?ned by using states and transitions. A state is a pair of sets of ?uent names + ; ? such that + ? = . Given a ?uent name F and a and ? are disjoint, i.e., + + state , we say that F holds in if F , F does not hold in if F ? , and it is not known whether F holds in otherwise. Given a ?uent name F , we also say that F holds in if F does not hold + in . Sometimes we also say that F is true in if F , F is false ? , and F is unde?ned in otherwise. in if F A transition function Φ is a mapping from the set of pairs (A; ), where A is an action expression and is a state, into the set of states. A structure is a pair ( 0 ; Φ), where 0 is a state, called the initial state of the structure, and Φ is a transition function. For any structure M = ( 0; Φ) and any sequence of action expressions A1 ; : : : ; Am in M , by Φ(A1 ; : : : ; Am ; 0 ) we denote the state Φ(Am , Φ(Am?1 , : : :, Φ(A1; 0) : : :)): A v-proposition of the form (1) is satis?ed in a structure M = ( 0 ; Φ) iff F holds in the state Φ(A1 ; : : : ; Am ; 0 ). We say that the execution of an action A in a state immediately initiates a ?uent expression F if there is an e-proposition A causes F if P1; : : : ; Pm in the domain description such that for

AC

\

2

; 2

h

i

:

2

2

Abduction, Temporal and Causal Reasoning

14

R. Li and L. M. Pereira

Temporal Reasoning with Abductive Logic Programming

Renwei Li and Lu?s Moniz Pereira1 ? Abstract

In this paper we extend Gelfond and Lifschitz’ action description language with concurrent actions and give a new semantics to concurrent actions. In order to automate temporal reasoing we present a translation from domain descriptions in the resulting new action description language to abductive logic programs. The translation has been shown to be both sound and complete. Our method is applicable to the temporal projection problem with incomplete information, as well as to reasoning about the past.

A

2

CONCURRENT ACTIONS

1

INTRODUCTION

malisms of reasoning about actions proposed by Baker [2], Pednault [20], and Reiter [22], respectively. Kartha and Lifschitz [16] also considered how to deal with rami?cations based on by using nested abnormality theory [17]. Dung presented a translation of domain descriptions in into abductive logic programs with database updates as applications [8]. Denecker and de Schreye proposed another much simpler translation of into abductive normal logic programs with constraints [7] and showed that their translation is both sound and complete with respect to the predicate completion semantics [4] of abductive normal logic programs. Baral and Gelfond [3] extended the action language with concurrent actions. All these results impress us that the action description language is a good basis for systematical development of theories of actions. This paper is in line with the work related to the action description language . We will extend with concurrent actions in a way different from [3], and present a translation from domain descriptions in the new action description language to abductive normal logic programs. The translation has been shown to be both sound and complete for any domain descriptions. Then temporal reasoning is reduced to abductive query evaluation in abductive logic programs. Our method is applicable to the temporal projection problem with incomplete information, and can also be applied to temporal explanation of inferring actions from ?uent changes. The rest of this paper is organized as follows. In Section 2 we informally discuss concurrent actions and their semantics. In Section 3 we extend with concurrent actions. In Section 4 we present a sound and complete translation from domain descriptions in the new action language to abductive logic programs. In Section 5 we compare our work with others. Finally, in Section 6, we draw some conclusions.

A and presented a translation from A to extended logic programs with answer sets as semantics [10], and proved its soundness. Kartha proposed three sound and complete translations of A into three forA A

In [11] Gelfond and Lifschitz proposed an action description language

A

A

A

A

A

A

1

Department of Computer Science, Universidade Nova de Lisboa, 2825 Monte da Caparica, Portugal. renwei lmp @di.fct.unl.pt

f

j g

In reality, occurrences of many actions overlap in time, which complicates temporal prediction and explanation in AI. For de?nite goals some actions may be planned to be carried out at the same time in order to save time, or to decrease production cost, or for other context-dependent purposes. A concurrent action is understood as a ?nite nonempty set of atomic actions, which happen at the same time. A nonempty subset of a concurrent action is called a subaction of the concurrent action. For example, opening a door and switching on a light at the same time is a concurrent action consisting of two atomic actions: opening a door and switching on a light. In common sense, the effect of a concurrent action is the aggregation of those of its subactions. For example, after one opens a door and switches on a light at the same time, the door is open and the light is on, which is the aggregation of the effects of opening the door and switching on the light. The effect relationship between an action and its subactions was ?rst discussed by Gelfond, Lifschitz and Robinov in the framework of the situation calculus [12], and further explored by Lin and Shoham [19], and Baral and Gelfond [3]. In [19], Lin and Shoham identi?ed a problem called the actionoriented frame problem and called the traditional frame problem the ?uent-oriented frame problem. Their work was motivated by their observation on the similarity and symmetrical roles played by actions and situations. Moreover, Lin and Shoham provided a solution to the action-oriented frame problem and proved its correctness with respect to a formal adequacy criterion called epistemological completeness, proposed in [18] by themselves. Intuitively, a theory of an action is epistemologically complete if, given a complete description of the initial situation, the theory enables us to predict a complete description of the resulting situation when the action is performed. In [3], Baral and Gelfond extended with concurrent actions and obtained an action language, denoted by BG in this paper. When a domain is described in BG the following postulate is adopted and employed: A concurrent action usually inherits effects of its subactions.This is essentially the same as that of [19] . But their techniques are different. Baral and Gelfond used the negation-asfailure operator to formalize the inheritance postulate in extended logic programming with answer-set semantics [10], while Lin and Shoham used circumscription policy to deal with the action-oriented frame problem. Another difference, more important, between [19] and [3] is in their treatment of con?icting effects, as analyzed as follows: Let Open and Close to denote two atomic actions: to make sure to open and close the door, respectively. In common sense, Open and Close have con?icting effects. Now consider a concurrent action Open; Close . How should we evaluate and deal with concurrent actions with con?icting effects? Lin-Shoham and Baral-Gelfond give two different methods.

A

A

A

f

g

c 1996 R. Li and L. M. Pereira ECAI 96. 12th European Conference on Arti?cial Intelligence Edited by W. Wahlster Published in 1996 by John Wiley & Sons, Ltd.