koorio.com

海量文库 文档专家

海量文库 文档专家

- 厦门大学《应用多元统计分析》第08章 相应分析
- 厦门大学《应用多元统计分析》第04章 判别分析
- 厦门大学《应用多元统计分析》第07章 因子分析
- 厦门大学《应用多元统计分析》第05章 聚类分析
- 厦门大学《应用多元统计分析》第09章 典型相关分析
- An Event-Condition-Action Language for XML
- Jocaml a language for concurrent distributed and mobile programming
- scoop simple concurrent object-oriented programming
- Concurrent Semantics for the Web Services Specification Language Daml-S
- An extended query language for action languages (and its application to aggregates and pref
- Speaking and acting – interacting language and action for an expressive character
- Human actions and errors in risk handling—an empirically grounded discussion of cognitive action-re
- A NETWORK PROGRAMMING LANGUAGE BASED ON CONCURRENT PROCESSES AND REGULAR EXPRESSIONS
- Speaking and Acting - Interacting Language and Action for an Expressive Character. Intellig
- Representing Concurrent Actions and Solving Conflicts

Language HSimple (R): An Action Language for Representing Concurrent Actions and Continuous Changes

Department of Computer Science Queen Mary and West eld College Mile End Road, London E1 4NS, U.K. email: hisashi@dcs.qmw.ac.uk In this paper, a new higher-level action language called HSimple (R) is introduced. Language HSimple(R) is based on (locally) strati ed logic program Apt et al., 1988] and can treat concurrent actions and continuous changes. Also, it can handle implication rules (rami cation) under the implication restriction. This work is the extension of Language H Hayashi, 1996] which can handle only a discrete time line. At the end, it is shown that any action can be expressed as a uent by comparing them in the logic program level. Evans and Sergot Evans and Sergot, 1995] presented a general and rather abstract framework for treating persistence in temporal reasoning. For simplicity, they concentrated only on one uent or time-varying proposition. Then Hayashi Hayashi, 1996] extended the strati ed persistence rule, one of the two persistence rules Evans and Sergot presented, included the idea of actions, showed that any extended program can be (locally) strati ed Apt et al., 1988], and thereby developed a new action language, Language H which is similar to Language A Gelfond and Lifschitz, 1993]. Although Language H can treat concurrent actions, implications (rami cations), a dis-

Hisashi Hayashi

Abstract

1 Introduction

crete time line (non-negative integers), triggered events, predicates such as `append', and so on, it cannot treat continuous changes using a continuous time line (non-negative real number), released uents, and non-continuous uents. The aim of this paper is to extend Language H to include these features, thereby to construct a new action language named HSimple(R) and to show the corresponding logic programs can still be strati ed. To include continuous changes, continuous actions which are similar to continuous uents will be introduced. While these actions are happening, they can a ect uents. For example, while the action ll is happening, the height of the water increases (see example 2.16). This method will be proved later to be the same as the idea of a trajectory predicate in the continuous version of event calculus Shanahan, 1990]. Also this approach is di erent from that of Herrmann and Thielscher, 1996] in which actions are regarded as points between two processes. To include released uents and non-continuous uents, the strati ed persistence rule will be extended slightly. Released uents will be included using the idea of Kartha and Lifschitz, 1994]. It also uses the idea of a cancel predicate Gelfond et al., 1991] Lin and Shoham, 1992] to modify the concurrent actions of Language H, although Language H can treat concurrent actions using actions with negations as failure to some extent.

In this paper, rstly, the syntax is de ned incrementally showing intuitive meanings and examples. Secondly, a translation method from Language HSimple (R) into logic programs is shown. Thirdly, the semantics is de ned based on the translated logic programs. Fourthly, it is shown that all the translated logic programs can be strati ed. Fifthly, actions, uents, and canceling sentences are compared and it is shown that we can express the changing world using only uents and without using actions. Finally conclusion and future work are discussed.

2 Syntax

In this section, the formal syntax of Language HSimple (R) is de ned. First, a domain language will be de ned. Second, some terminologies will be de ned such as uents. Third, fundamental sentences used in Language HSimple(R) will be introduced. Finally, programs and queries are de ned. De nition 2.1 A domain language is a tuple hF A T P V Ei where F is a non-empty set of uent constants, A is a non-empty set of actions, T is a non empty set of time points which are non-negative real numbers. P is a non-empty set of predicates, V is a non-empty set of mathematical variables, E is a nonempty set of mathematical expression. Intuitively, actions (or events) in A happen instantaneously and if a uent starts holding, then an action (an event) must have happened and immediately after the action, the uent starts holding. Built-in predicates in P such as `append' and ` ' can be used in Language HSimple (R). Also user-de ned predicates can be used which are de ned by the sentences which will be introduced later. However, it is the responsibility of the user and the maker of the compiler (or the interpreter) that all the predicates can be judged to be true or false within limited time and have their own unique models.

; ; ; ; ; <

Mathematical variables in V will be used in a special (atomic) uent called value uent which will be de ned soon. Mathematical expression in E is like 1 + 2 3 or (4) which can be de ned precisely in the lower level. Each of them should correspond to one of a real number. De nition 2.2 A value uent is of the form value(name, v) where name is a mathematical variable and v is a real number. Note that value(name, v) means the value of name is v. If 1 6= 2 , both of value(name, 1) and value(name, 2) do not hold at the same time. This will be included in the semantics or the persistence rules (p-axioms) which will be introduced later. De nition 2.3 An atomic uent is either a uent constant or a value uent. De nition 2.4 A uent is either an atomic uent or an atomic uent preceded by a classical negation ` '. De nition 2.5 A f-literal is either a uent or a uent preceded by a negation as failure `not'. Clearly, f-literals are higher level notion than uents. Fluents are higher level notion than atomic uents. Similarly p-literals and literals are de ned. De nition 2.6 A p-literal is either a predicate or a predicate preceded by a negation as failure `not'. De nition 2.7 A literal is either a f-literal or a p-literal. Literals are used in the conditions of some sentences which will be introduced soon. Example 2.8 Let `loaded' and `alive' be atomic uents, let `wind' be a mathematical variable, and let ` ' be a predicate, we can express such a condition as \if the gun is loaded, if we are not sure if the turkey is not alive, and if the wind is weaker than 10 units" in the following way: if loaded, not alive, value(wind, V), V 10

square v v v v < <

Now sentences can be de ned. De nition 2.9 Each of the followings is a sentence, where ` ' is an action, ` ' is a time point, ` ' is a uent, ` 1',..., ` n' are p-literals, ` ' is a predicate, and ` 1',..., ` m ' are literals; :- 1 ,..., n. p1] . p2] given+( , ). f1] given0( , ). f2] ] cause+ if 1,..., m at . f3] released+( , ). r1] ] release+ if 1,..., m at . r2] action( , ). a1] In f3] and r2], it is allowed to omit `if 1,..., m ' and/or `at '. Also ` ]' can be omitted. In this case, we can use ` ]' instead. This means `even if nothing happens...'. The meaning of `released+' in r1] and release+ in r2] is similar to that of release propositions in Kartha and Lifschitz, 1994] Intuitive meaning is as follows; p1] and p2] are used to de ne predicates exactly in the same way as the logic program. f1] means that continues to hold immediately after until it is stopped. f2] means that holds at . f3] means that if 1,..., m hold at and if happens at , then continues to hold immediately after . r1] means that the truth value of becomes unknown immediately after . r2] means that if 1 ,..., m hold at and if happens at , then the truth value of becomes unknown immediately after . a1] means that happens at . If we regard Language A as a kind of situation calculus McCarthy and Hayes, 1969], these sentences are similar to event calculus Kowalski and Sergot, 1986] Sadri and Kowalski, 1995]. In this sense, Language E Kakas and Miller, 1997] is similar to event calculus. Example 2.10 If the gun is loaded, the turkey is dead after shooting it. If we do not know if the gun is loaded, we also do not know if the turkey is alive after shooting it. After spinning the chamber, it becomes unknown if the gun is loaded

a t F P P p L L p P P p F t F t a F L L t F t a F L L t a t L L t a F t F t L L t a t F t F t L L t a t F t a t

or not. After loading the gun, the gun is loaded. The turkey is alive and the gun is loaded immediately after time point 0. At time point 10, the agent spins the chamber. At time point 20, the agent shoots the turkey. At time point 30, the agent loads the gun. At time point 40, the agent shoots the turkey. This example which was originally introduced in Sandewall, 1992] can be expressed by the following sentences, where `alive' and `loaded' are uents and where `shoot',`spin', and `load' are actions; given+(alive, 0). given+(loaded, 0). action(spin, 10). action(shoot, 20). action(load, 30). action(shoot, 40). shoot cause+ alive if loaded. shoot release+ alive if not loaded. spin release+ loaded. load cause+ loaded. We can see how we can use predicates in the following example. Example 2.11 Let us suppose that there are two queues. If a person arrives, the person queues in the shorter line. In this example, if the length of the two lines are the same, a new person queues in `line1' because it is closer. At rst, `hisashi', `fred', and `jane' are in `line 1' in this order and `tom' and `bob' are in `line2' in this order. At time point 5, `eva' arrives and queues. The predicate `longer(X, Y)' means that the length of list `X' is longer than the length of list `Y'. Let us assume that lists are built in in the logic program and also the predicates `length' and `>' are built in. `line(..., ...)' is a uent. `queue(...)' is an action. This example which was originally used in Hayashi, 1996] can be expressed as follows; given+( jane, fred, hisashi], 0). given+( bob, tom], 0). action(queue(eva), 5). longer(X, Y) :- length(X, A), length(Y, B), A>B.

queue(X)] cause+ line(line1, XjQ1]) if line(line1, Q1), line(line2, Q2), not longer(Q2, Q1). queue(X)] release+ line(line1, Q1) if line(line1, Q1), line(line2, Q2), not longer(Q2, Q1). queue(X)] cause+ line(line2, XjQ2]) if line(line1, Q1), line(line2, Q2), longer(Q2, Q1). queue(X)] release+ line(line2, Q2) if line(line1, Q1), line(line2, Q2), longer(Q2, Q1). `at t' is useful to restrict the time point for the application of f3] and r2]. Example 2.12 If the person arrives at the station before time point 10, the person can get on the train. `arrive' is an action which means that the person arrives at the station. `aboard' is a uent which means that the person is in the train. `<' is a built-in predicate. This example is expressed as follows; arrive] cause+ aboard if T<10 at T. A uent might continue to hold. Another uent might hold only at one time point and might not continue to hold afterwards. However, any action never continues to hold in any literature although we can nd actions with duration. In Language HSimple(R), actions are allowed to continue. De nition 2.13 Each of the followings is a sentence, where `a1', `a2', and `a' are actions, `t' is a time point, `F ' is a uent, and `L1 ',..., `Lm' are literals; start+(a, t). a2] end+(a, t). a3] a1 ] start+ a2 if L1 ,..., Lm at t. a4] a1 ] end+ a2 if L1 ,..., Lm at t. a5] Intuitive meaning is as follows; a2] means that a continues to happen immediately after t until it is stopped. a3] means that a ends to happen immediately after t. a4] means that if L1 ,..., Lm hold at t and if a1 happens at t, then

2 continues to happen immediately after . a5] means that if 1,..., m hold at and if 1 happens at , then 2 ends to happen immediately after . Like in f3] and r2], in a4] and a5], it is allowed to omit `if 1,..., m', `at ' and/or ]. We can also use ` ]' instead of omitting `at ' Note that a2], a3], a4], a5] are similar to f1], r1], f3], r2] respectively. Example 2.14 A man is running at rst and he is not tired (after time point 0). He stops running if he is tired and if he tumbles. Anyway, he stops running immediately after time point 10. This example is expressed by the following sentences, where `tired' is a uent and where `run' and `tumble' are actions. given+( tired, 0). start+(run, 0). tumble] end+ run if tired. end+(run, 10). In the example above, `run' is an action rather than a uent because, by running, you move out of the place where you were. Now we can express continuous changes by the following sentences. De nition 2.15 Each of the followings is a sentence, where ` ' is an action, ` 1 ' and ` 2' ( 1 2 ) are time points, ` 1',..., ` n' and ` ' are mathematical variables, ` ' is a mathematical expression, and ` 1',..., ` n ' are real numbers; value+( , ) at 2 if value( 1 , 1),..., value( n , n) at 1 while . v1] value0( , ) at 2 if value( 1, 1),..., value( n , n) at 1 while . v2] Note that `if value( 1, 1),..., value( n , n) ' can be omitted in both v1] and v2]. Intuitively, v1] means that if action is started at time point 1 by a sentence of the form a2], a4], if the value of mathematical variables 1,..., n is 1,..., n respectively at 1 and if is not stopped between time points 1 and 2 by a sentence of the form a3], a5], then the value of mathematical variable is at 2. If is

a t L L t a t a t L L t a t a t t t < t x x y v v v y v t x v x v t a y v t x v x v t a x v x v a t x x v v t a t t y v t a

stopped at 2 by a sentence of the form a3], a5] at 2, the value of continues to be also after 2 until it is stopped. v2] is almost the same as v1]. The only difference is that even if is stopped by a sentence of the form a3], a5] at 2, the value of does not continue to be after 2 by this sentence. Example 2.16 At time point 0, the height of the water in the kitchen sink is 0cm. At time point 10, the agent starts lling the kitchen sink with water at 2cm per 1 time unit. However, we cannot ll the water any more after the water reaches the top of the kitchen sink. The height of the kitchen sink is 30cm. We can express this example which was introduced in Shanahan, 1990] by the following sentences, where ` ll' is an action and `height' is a mathematical variable; given+(value(height, 0), 0). start+( ll, 10). value+(height, H0+2*(T1-T0)) at T1 if value(height, H0) at T0 while ll. ] end+ ll if value(height, 30). Note that in the last sentence, there is no action in ]. No action is needed to end ` ll'. In order to describe an example of chemical reaction, we need to be able to handle triggered events which always happen as soon as some conditions are satis ed. Also it is nicer if we can use implication rules. De nition 2.17 Each of the followings is a sentence, where ` ' is a time point, ` ' is a uent, ` ' is an action, and ` 1 ',..., ` m ' are literals; happen0 if 1,..., m at . a6] 1,..., m imply0 at . f4] Intuitively, a6] means that if 1,..., m hold at , then happens at . Similarly, f4] means that if 1,..., m hold at , then holds at . For the use of f4], we need to be careful. f4] is allowed to be used if and only if the implication restriction which will be introduced shortly is not violated. The example of f4] will be shown after introducing the idea of concurrent actions.

t t y v t a t y v t t F a L L a L L t L L F t L L t a t L L t F t

Example 2.18 There are two chemicals, A and

B. Normally A and B are very stable, however, mixing A and B causes explosion. The uent `a' means that the chemical A is in the bowl. The uent `b' means that the chemical B is in the bowl. The action `explode' means that the explosion happens. We can express this example as follows; explode happen0 if a, b. In the following de nition, a program will be de ned later. De nition 2.19 The atomic uent `x' depend on the atomic uent `y' if and only if; there exists an atomic uent `z' such that `x' depends on `z' and `z' depends on `y' or; there exists a following sentence in the program, where `X' is one of the f-literals of the form: `x', ` x', `not x' or `not x' and where `Y' is one of the uents of the form: `y', ` y'; ..., X ,... imply0 Y ... The following restriction serves to the strati cation of the corresponding logic program of the program using implication rules; De nition 2.20 The implication restriction is that there must not exist two atomic uents, `x', `y' such that `x' depends on `y' and `y' depends on `x'. Note that this restriction also prevents the case where `x' depends on `x'. Finally, f3], r2], a4], and a5] are extended to f'3], r'2], a'4], and a'5] respectively so that they can cope with concurrent actions. De nition 2.21 Sentences f3], r2], a4], and a5] are extended to f'3], r'2], a'4], and a'5] respectively as follows, where `a1',... ,`an', and `a' are actions, `L1 ',... ,`Ln ' are literals, F is a uent, and t is a time point; a1 , ..., an ] cause+ F if L1 ,..., Lm at t. f'3] a1 , ..., an ] release+ F if L1 ,..., Lm at t. r'2]

a

..., n] start+ 2 if 1,..., m at . a'4] 1, ..., n ] end+ 2 if 1,..., m at . a'5] Intuitively, ` 1, ..., n]' means that if 1, ..., n happen at the same time. If we admit concurrent actions, we also have to think about actions which cancel the e ect of actions. De nition 2.22 Each of the followings is a sentence, where ` 1',..., ` n', ` n+1 ',...,` k ', and ` ' are actions, ` ' is a uent, and ` 1',..., ` m ' are literals; 1,..., n ] cancel caused by n+1 ,..., k ] if 1 ,..., m at . c1] released by 1,..., n ] continue n+1 ,..., k ] if 1 ,..., m at . c2] ,..., n] cancel started by n+1,..., 1 k ] if 1 ,..., m at . c3] ,..., n] continue ended by n+1,..., 1 k ] if 1 ,..., m at . c4] Intuitive meaning is that 1,..., n cancel the e ect of actions n+1,..., k at concerning or in f'3], r'2], a'4], and a'5] if 1,..., m hold at . This idea is based on Gelfond et al., 1991] and Lin and Shoham, 1992]. The following example is using both concurrent actions and implication rules. Example 2.23 Lifting only the left side (or the right side) of the soup bowl results in the soup being spilt. However, Lifting both sides does not result in the same consequence. Instead, the soup bowl is lifted. When the bowl is lifted, the soup is also lifted if it is not spilt. At rst, soup is not spilt and the soup bowl is not lifted. This example was originally used in Lin and Shoham, 1992] and is slightly modi ed here. The uent `spilt' means that the soup is spilt. The uents `lifted(soup)' and `lifted(bowl)' mean that the soup and the bowl are lifted respectively. The actions `lift(left)' and `lift(right)' mean lifting the left side and lifting the right side respectively. We can express this example as follows;

a a a L L t a a a L L t a a a a a a a a F L L a a F a a L L t a a F a a L L t a a a a a L L t a a a a a L L t a a a a t F a L L t

1,

given+( lifted(bowl), 0). given+( spilt, 0). lift(left)] cause+ spilt. lift(right)] cause+ spilt. lift(left), lift(right)] cause+ lifted(bowl). lift(left), lift(right)] cancel spilt caused by lift(left)]. lift(left), lift(right)] cancel spilt caused by lift(right)]. lifted(bowl), spilt imply0 lifted(soup). We can de ne more sentences, however, in order to concentrate on essential sentences, no more sentences are de ned. This section is nished by de ning programs and queries. De nition 2.24 A program is a sequence of a nite number of sentences. For example, `s1:::sn' is a program where `s1; :::; sn' are sentences. De nition 2.25 An Atomic Query is one of the followings: hold(F , t), not hold(F , t), happen(a, t), not happen(a, t) where F is a uent, a is an action, and t is a time point. De nition 2.26 A query is ? h1; :::; hn. where h1 ,..., hn are atomic queries. Because the formal semantics of Language HSimple(R) is de ned on the basis of its corresponding logic program, its semantics is de ned after the translation method into logic programs is shown.

In this section, the translation method from Language HSimple (R) into logic programs is introduced. First, basic axioms concerning persistence rules and value uents will be de ned. Second, the translation method from sentences

3 Translation into Logic Programs

in the program of Language HSimple(R) into clauses of the logic program is shown. Each translation is based on the intuitive meaning of the sentence of Language HSimple(R). 3.1 Axioms Two axioms are assumed: 1 p-axioms, 2 vaxioms. First of all, we use the following persistence rules written in the logic program as axioms (paxioms). These axioms are added to all the translated logic programs;

hold(F, T) :- given0(F, T), not contradict0(F, T). hold(F, T2) :- T1<T2, given+(F, T1), not contradict+(F, T1), not broken(F, T1, T2). contradict0(F, T) :contrary(F, Fc), given0(Fc, T). contradict+(F, T) :contrary(F, Fc), given+(Fc, T). broken(F, T1, T2) :- T1<T, T<T2, released+(F, T). broken(F, T1, T2) :- T1<T, T<=T2, released0(F, T). broken(F, T1, T2) :- T1<T, T<T2, contrary(F, Fc), given+(Fc, T). broken(F, T1, T2) :- T1<T, T<=T2, contrary(F, Fc), given0(Fc, T). contrary( F, F). contrary(F, F) :- not F= Fc.

pa1]

pa2]

pa3]

3)' are given, the contradict0 and contradict+ will detect these contradictions respectively and these information is simply ignored. This persistence rule is similar to that of Evans and Sergot, 1995] in the sense that the given assumptions and the beliefs calculated by the persistence rule are divided, however, it is di erent in the sense that assumptions given by `given0' do not continue and that continuing uents are stopped by `released0' and `released1'. Because given contradictions are detected and ignored, there is no contradiction such as `hold(f, 10)' and `hold( f, 10)' as shown in Evans and Sergot, 1995]. As explained in the de nition of uent, value(name, v) is an atomic uent which means the value of name is v. We need to restrict the use of this atomic uent so that both of value(name, 1) and value(name, 2) do not hold at the same time if 1 6= 2. The following v-axioms are added to all the translated logic programs;

v v v v

pa4]

released0(value(Name, V1), T):given0(value(Name, V2), T). released+(value(Name, V1), T):given+(value(Name, V2), T).

pa5]

va1]

pa6]

pa7]

pa8] pa9]

Intuitively, given+(F, T) means that F continues to hold immediately after time point T until it is stopped. given0(F, T) means that F holds at time point T. released+(F, T) means that the truth value of F is unknown immediately after T. released0(F, T) means that the truth value of F is unknown at T. If, for example, `given0(f, 5)' and `given0( f, 5)' are given and `given+(f, 3)' and `given+( f,

pa10]

f L; t

va2] 3.2 Translation of Sentences In addition to p-axioms and v-axioms, sentences p1], p2], f1], f2], f'3], f4], r1], r'2], a1], a2], a3], a'4], a'5], a6], c1], c2], c3], c4], v2] of Language HSimple(R) are translated automatically into , lp1], lp2], lf1], lf2], lf3], lf4], lr1], lr2], la1], la2], la3], la4], la5], la6], lc1], lc2], lc3], lc4], lv2] and also v1] is translated into lv1.1] and lv1.2], where perm( 1, 2) is a predicate which means that the elements of lists 1 and 2 are the same and where; 8 (if is a p-literal) > > hold( ) < (if is a uent) ( ) = not hold( ) (if is > : where is a uent) :- 1 ,..., n . lp1]

L L L L L L L;t L L;t L not F F p P P

p. given+(F , t) :- 0<=t. given0(F , t) :- 0<=t. given+(F , t2) :- 0<= t1, t1 <=t2, hold(a1, t1 ),..., hold(an, t1 ), f L1 ; t1 ,..., f Lm ; t1 , not canceled( a1,...,an], F , t1 ). given0(F , t) :- 0<=t, f L1 ; t ,..., f Lm ; t . released+(F , t) :- 0<=t. released+(F , t2 ) :- 0<=t1, t1 <=t2 , hold(a1, t1 ),..., hold(an, t1 ), f L1 ; t1 ,..., f Lm ; t1 , not canceled( a1,...,an], F , t1).

lp2]

lf1] lf2]

(

)

(

)

lf3]

(

)

(

)

lf4] lr1]

canceled(L, a, T) :perm(L, an+1,..., ak ]), hold(a1, T),..., hold(an, T), f L1 ; T ,..., f Lm ; T . given0(value(y , V), t2) :0<=t1, t1<t2, given+(a, t1), hold(value(x1, v1), t1),..., hold(value(xn, vn ), t1), not broken(a, t1, t2), V is v .

(

)

(

)

lc4]

(

)

(

)

given0(a, t) :- 0<=t. given+(a, t) :- 0<=t. released+(a, t) :- 0<=t. given+(a, t2) :- 0<=t1, t1<=t2, hold(a1, t1 ),..., hold(an, t1 ), f L1 ; t1 ,..., f Lm ; t1 , not canceled( a1,...,an], a, t1 ). released+(a, t2) :- 0<=t1, t1<=t2, hold(a1, t1 ),..., hold(an, t1 ), f L1 ; t1 ,..., f Lm ; t1 not canceled( a1,...,an], a, t1 ).

lr2]

given+(value(y , V), t2) :0<=t1, t1<t2, given+(a, t1), released+(a, t2 ), hold(value(x1, v1), t1),..., hold(value(xn, vn ), t1), not broken(a, t1, t2), V is v . given0(value(y , V), t2) :0<=t1, t1<t2, given+(a, t1), hold(value(x1, v1), t1),..., hold(value(xn, vn ), t1), not broken(a, t1, t2), V is v .

p

lv1.1]

la1] la2]

lv1.2]

la3] )

(

)

(

la4]

(

)

(

)

given+(a, t) :- 0<=t, f L1 ; t ,..., f Lm ; t . canceled(L, F , T) :perm(L, an+1,..., ak ]), hold(a1, T),..., hold(an, T), f L1 ; T ,..., f Lm ; T . canceled(L, F , T) :perm(L, an+1,..., ak ]), hold(a1, T),..., hold(an, T), f L1 ; T ,..., f Lm ; T . canceled(L, a, T) :perm(L, an+1,..., ak ]), hold(a1, T),..., hold(an, T), f L1 ; T ,..., f Lm ; T .

la5] (

)

(

)

la6]

lv2] Note that the user-de ned predicate ` ' might need to be evaluated separately using lp1] and lp2] because all the predicates of Language HSimple(R) are assumed to have their own unique models and this assumption is based on the users and makers of the compiler (or the interpreter). Normally the user-de ned predicates should be evaluated by topdown reasoning because most of the users de ning predicates are familiar with SLDNF.

(

)

(

)

lc1]

4 Semantics

(

)

(

)

lc2]

(

)

(

)

lc3]

The semantics of Language HSimple (R) is based on its corresponding logic program. It is also possible to de ne an independent semantics for Language HSimple (R), which facilitates the comparison of di erent formalisms via their translations from Language HSimple (R). De nition 4.1 The answer to a query to a program is; yes if and only if;

hold(F , t) in the query where F is a uent and t is a time point, hold(F , t) is true in the translated logic program and; { for all the atomic queries of the form: not hold(F , t) in the query where F is a uent and t is a time point, hold(F , t) is false in the translated logic program and; { for all the atomic queries of the form: happen(a, t) in the query where a is an action and t is a time point, hold(a, t) is true in the translated logic program and; { for all the atomic queries of the form: not happen(a, t) in the query where a is an action and t is a time point, hold(a, t) is false in the translated logic program. no otherwise. Example 4.2 The queries and answers to example 2.10 is as follows; ? not hold(alive, 25), not hold( alive, 25). yes. ? hold(alive, 45). no. ? hold( alive, 45). yes. Example 4.3 The queries and answers to example 2.11 is as follows; ? hold( bob, tom], 10). no. ? hold( eva, bob, tom], 10). yes. Example 4.4 The queries and answers to example 2.16 is as follows; ? hold(value(height, 0), 10). yes. ? hold(value(height, 20), 20). yes.

{ for all the atomic queries of the form:

p p

All the translated programs including p-axioms and v-axioms can be strati ed in the following way, where means any term of the logic program, 1 2 means that 1 is de ned in a higher stratum than 2 is, 1 2 means that 1 is de ned in the same stratum as 2 is, where 1 and 2 are predicates of the logic program; For any atomic uent and for any time point ,

p p p p p p p p f t

5 Strati cation of the Translated Logic Program

? hold(value(height, 40), 30). no. ? hold(value(height, 30), 30). yes.

For any two uents 1 and 2 which do not depend on any uent and for any time point ,

f f t

contradict+(f , t) contradict+( f , t), given+(f ,t) given+( f ,t), released+(f , t) released+( f , t), canceled( , f , t) canceled( , f , t), hold(f , t) hold( f , t), contradict0(f , t) contradict0( f , t), given0(f ,t) given0( f ,t), released0(f , t) released0( f , t), broken(f , , t) broken( f , , t)

contradict+(f1, t) contradict+(f2, t), given+(f1,t) given+(f2,t), released+(f1, t) released+(f2, t), canceled( , f1 , t) canceled( , f2 , t), hold(f1, t) hold(f2, t), contradict0(f1, t) contradict0(f2, t),

For any two actions time point ,

t

given0(f1,t) released0(f1, released0(f2, broken(f1, , broken(f2, ,

t) t) t) a

given0(f2,t),

t),

1

and

a

2

and for any

For any uent or action and for any time point ,

x t

contradict+(a1, t) contradict+(a2, t), given+(a1,t) given+(a2,t), released+(a1, t) released+(a2, t), canceled( , a1, t) canceled( , a2, t), hold(a1, t) hold(a2, t), contradict0(a1, t) contradict0(a2, t), given0(a1,t) given0(a2,t), released0(a1, t) released0(a2, t), broken(a1, , t) broken(a2, , t)

Note that this strati cation is possible if implication restriction is not violated. This strati cation method was already introduced in the original version of Language H Hayashi, 1996] as the implication theorem. For any atomic uent which does not depend on any other atomic uent, for any action , and for two time points 1 and 2 such that 1 2,

f a t t t < t

broken(f1, , t) contradict+(f2, t)

Intuitively, if 1 2 , then predicates regarding 1 is de ned in a lower stratum than predicates regarding 2. For any predicate of the logic program other than: contradict+( , ), given+( , ), released+( , ), canceled( , , ), hold( , ), contradict0( , ), given0( , ), released0( , ), and broken( , , ),

t < t t t P

broken(f , , t2 ) contradict+(a, t1)

contradict+(x, t) given+(x, t) released+(x, t) canceled( , hold(x, t) contradict0(x, t) given0(x, t) released0(x, t) broken(x, , t)

x, t)

For any action , for any uent , and for any time point ,

a f t

broken(a, , t) contradict+(f , t)

(cf. a6].) For any atomic uent 1 which depends on another atomic uent 2 and for any time point ,

f f t

(i.e. is either unde ned or de ned in the lowest stratum. Note that any has its own unique model.) Intuitively, we can stratify the program as follows; Suppose that 1 does not depend on any other uent, 2 depends on 1, 3 depends on 2,..., n depends on n?1 , and n is not depended on by any uent. Suppose that is any predicate of the logic program other than contradict+( , ), given+( , ), released+( , ), canceled( , , ), hold( , ), contradict0( , ), given0( , ), released0( , ), and broken( , , ). We can stratify the translated logic program as follows;

P P f f f f f f f f P

broken( ,

, 0)

P

. . .

broken(f1, , ) contradict+(a, ) given+(a, ) released+(a, ) canceled( , a, ) hold(a, ) contradict0(a, ) given0(a, ) released0(a, ) broken(a, , ) contradict+(fn, ) given+(fn, ) released+(fn, ) canceled( , fn , ) hold(fn, ) contradict0(fn, ) given0(fn, ) released0(fn, ) broken(fn, , ) . . .

1

1

2

1

1

1

1

1

given0(fn, ) released0(fn, ) broken(fn, , ) . . . contradict+(f1,

canceled( , fn , ) hold(fn, ) contradict0(fn, )

0

0

0

0

0 0

1 1

1

1

1

1

1

1

1

hold(f1, ) contradict0(f1, ) given0(f1, ) released0(f1, ) broken(f1, , )

given+(f1, ) released+(f1, ) canceled( , f1 , )

0

0)

0

0

0

0

0

0 0

P

1 1

6 Discussion

contradict+(f1, ) given+(f1, ) released+(f1, ) canceled( , f1, ) hold(f1, ) contradict0(f1, ) given0(f1, ) released0(f1, ) broken(f1, , ) contradict+(a, ) given+(a, ) released+(a, ) canceled( , a, ) ` hold(a, ) contradict0(a, ) given0(a, ) released0(a, ) broken(a, , ) contradict+(fn, ) given+(fn, ) released+(fn, )

1

1

1

1

1

1

1

1 1

0

0

0

0

0

0

0

0 0

0

0

0

In the translation method shown, in order to express actions and uents, the common predicates are used such as 'hold', 'given+', 'given0', 'released0', 'released+', 'broken' and so on. This enables us to compare the meaning of actions and uents easily. 6.1 Comparison of Canceling sentences We can nd that all of lc1],..., lc4] are of the same form. So, we can replace any sentence of the form c1],..., c4] with a sentence of the same form: 1,..., n ] cancel a ected by n+1 ,..., k ] if 1 ,..., m at . c] where 1,..., k are actions, 1,..., m are literals, and is either an action or a uent. 6.2 Comparison of Actions and Fluents If we compare the translated programs, we can nd the same translation as follows; la1] is the same as lf2]. la2] is the same as lf1]. la3] is the same as lr1]. la4] is the same as lf3]. la5] is the same as lr2]. la6] is the same as lf4]. What does this mean? In the end, we can conclude that all actions can be expressed by

a a X a a L L t a a L L X

uents. Actions can be regarded as kinds of uents. The only di erence is their roles. Actions happen instantaneously to change the truth value of uents. Actually, if we regard actions as uents, we can do without a1], a2], a3], a'4], a'5], and a6]. 6.3 Sentences of the Form v1] and v2] vs. Shanahan's Trajectory Predicates In Shanahan's continuous version of event calculus Shanahan, 1990], he used trajectory predicates to describe the changing world. A trajectory predicate means that a uent hold at time point 2 if an action happen at time point 1 ( 2) and if a uent is always true between the two time points. We can easily understand that this idea is the same as the role of sentences v1] , v2] if we regard actions as uents. In Language HSimple (R), the protected uent is just regarded as an action in order to emphasize that not uents but actions are changing the world.

t t < t

we can introduce sentences such as \When some uents hold, if some actions happen, another action will happen after some time although we do not know what is happening before the new action happens." Also, we can introduce a predicate `given(x, t)' in the logic program level which means that `x' holds at `t' and it continues to hold afterwards until it is stopped. There are three future directions for this project: 1 computation by forward reasoning, 2 computation by backward reasoning, 3 application to robotics. In forward reasoning computation, we can calculate the unique (locally) strati ed (stable) model by calculating the model of each stratum from the bottom stratum. However, although it was shown that all the translated logic programs can be strati ed, it was not shown how to stratify them into the smallest possible number of strata. Because we are not interested in all the time points, we do not have to calculate what will hold at such time points. Remember that we can stratify the program into uncountably many strata. The key time points are the time points we are interested in and any time point where `given+( , )' or `given0( , )' is true. In backward reasoning, we can use SLDNF. Furthermore, the strati ed model of any strati ed logic program is consistent with its completion. The task for backward reasoning is to develop e cient algorithm and to conquer arithmetic problems which arise when you use normal Prolog. Simple queries and answers are suitable for this method. In the application of robotics, the future work is to calculate the current belief from given past and present facts by forward reasoning, to react if it needs to, and to calculate a future partial plan within limited time by abduction.

t t t

8 Future Work

7 Conclusion

In de ning the syntax, its intuitive meaning was explained using some examples which showed that Language HSimple (R) is powerful enough to express the changing world including continuous changes on a continuous time line, concurrent actions, implication, and continuous (and non-continuous) uents (and actions). By de ning the formal semantics based on its corresponding logic program, it was shown that programs in Language HSimple (R) have the unique semantics corresponding to the strati ed model Apt et al., 1988] of the translated logic program. Because the common predicates such as `given0', `given+', `hold', `released0', `released+', and so on were used in translating a program in Language HSimple (R) into a logic program, it is easy to compare uents and actions and we nd that actions can be expressed as uents. Although not so many sentences were de ned, we can extend this language easily. For example,

References

Apt et al., 1988] K.

Apt,

H.

Blair,

and A. Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89{148. Morgan Kaufman, 1988. Evans and Sergot, 1995] D. Evans and M. Sergot. An abstract framework for the representation of persistence. Department of Computing, Imperial College of Science, Technology and Medicine, 1995. Gelfond and Lifschitz, 1993] M. Gelfond and V. Lifschitz. Representing action and change by logic program. Journal of Logic Programming, 17:301{322, 1993. Gelfond et al., 1991] M. Gelfond, V. Lifschitz, and A. Rabinov. What are the limitations of the situation calculus? In R. Boyer, editor, Essays in Honor of Woody Bledsoe, pages 167{179. Kluwer Academic, 1991. Hayashi, 1996] H. Hayashi. The language H: A language for representing actions. Master's thesis, Department of Computing, Imperial College of Science, Technology and Medicine, University of London, 1996. Herrmann and Thielscher, 1996] C. S. Herrmann and M. Thielscher. Reasoning about continuous processes. In B. Clancey and D. Weld, editors, Proceedings of the Thirteenth National Conference on Arti cial Intelligence (AAAI), pages 639{644. MIT Press, 1996. Kakas and Miller, 1997] A. Kakas and R. Miller. A simple declarative language for describing narratives with actions. Journal of Logic Programming Special Issue on Reasoning about Actions, 1997. Kartha and Lifschitz, 1994] G. N. Kartha and V. Lifschitz. Actions with indirect e ects (preliminary report. In Fourth International Conference on Principles of Knowledge Representation and Reasoning, pages 341{350, 1994. Kowalski and Sergot, 1986] R. Kowalski and M. Sergot. A logic-based calculus of events. New Generation Computing, 4:23{37, 1986.

Lin and Shoham, 1992] F. Lin and Y. Shoham. Concurrent actions in the situation calculus. In AAAI 92, pages 590{595, 1992. McCarthy and Hayes, 1969] J. McCarthy and P. J. Hayes. Some philosophical problems from the standpoint of arti cial intelligence. In D. Michie and B. Meltzer, editors, Machine Intelligence, volume 4, pages 469{502. Edinburgh University Press, 1969. Sadri and Kowalski, 1995] F. Sadri and R. Kowalski. Variants of the event calculus. In International Conference on Logic Programming, pages 67{82. MIT Press, 1995. Sandewall, 1992] Erik Sandewall. Features and uents: A systematic approach to the representation of knowledge about dynamic systems. Technical Report LiTH-IDA-R-92-30, Linkoping University, 1992. Shanahan, 1990] M. Shanahan. Representing continuous change in the event calculus. In ECAI 90, pages 598{603, 1990.

赞助商链接