Doing Time Date: Sun, 12 Dec 1999 From: Esra Erdem and Vladimir Lifschitz To: TAG We formalized Example 3.1 of the paper ``LUPS-A Language for Updating Logic Programs'' by J. J. Alferes, L. M. Pereira, H. Przymusinska, and T. Przymusinski. This paper appears in Proceedings of LPNMR'99. In this paper, Example 3.1 is described as follows: Consider the scenario: once Republicans take over both Congress and the Presidency they establish a law stating that abortions are punishable by jail; once Democrats take over both Congress and the Presidency they abolish such a law; in the meantime, there are no changes in the law because always either the President or the Congress vetoes such changes; performing an abortion is an event, i.e. a non-inertial update. Consider the following update history: (1) a Democratic Congress and a Republican President (Reagan); (2) Mary performs abortion; (3) Republican Congress is elected (Republican President remains in office: Bush); (4) Kate performs abortion; (5) Clinton is elected President; (6) Ann performs abortion; (7) Gore is elected President and Democratic Congress is in place (year 2000?); (8) Susan performs abortion. We formalized this example in the action language C. In our formalization, the fluents are repC, repP, jail(X), prohibited. They are all inertial. The elementary actions are electC(P), electP(P), abn(X). The actions are not executable unless specified. The effects of these actions are described by the following propositions: electC(rep) causes repC. electP(rep) causes repP. electC(dem) causes -repC. electP(dem) causes -repP. abn(X) causes jail(X) if prohibited. In the following propositions, we describe under which conditions an abortion is prohibited, and under which conditions it is not prohibited. caused prohibited if repC & repP. caused -prohibited if -repC & -repP. Then we performed the reasoning automatically (by ccalc) for the update history: 0. -repC, repP, abn(mary), 1. electC(rep), 2. abn(kate), 3. electP(dem), 4. abn(ann), 5. electC(dem), electP(dem), 6. abn(susan) assuming that no one is in jail initially. ccalc finds the following result: run time (seconds) 0.01 0. repP ACTIONS: abn(mary) 1. repP ACTIONS: electC(rep) 2. prohibited repC repP ACTIONS: abn(kate) 3. prohibited repC repP jail(kate) ACTIONS: electP(dem) 4. prohibited repC jail(kate) ACTIONS: abn(ann) 5. prohibited repC jail(ann) jail(kate) ACTIONS: electC(dem) electP(dem) 6. jail(ann) jail(kate) ACTIONS: abn(susan) 7. jail(ann) jail(kate) yes LUPS is similar to action languages but is more complicated in that it operates with logic programs rather than states of a transition system. Our formalization shows that, for at least one of their motivating examples, this additional level of complexity is unnecessary. Please let us know if you have any questions. ========= Date: Sun, 12 Dec 1999 From: Vladimir Lifschitz To: TAG The example that Esra and I wrote to you about in connection with the LUPS paper is funny in that it doesn't allow a person to get out of jail, never ever, no matter what. Let's try to be more realistic. Can you describe, in your favorite action language, the effect of action sentence(x,t) (sentence x to t units of time in jail) on fluent jail(x) (x is in jail)? To jazz it up, you can add a life sentence, parole, and life without the possibilty of parole. ======== Date: Thu, 16 Dec 1999 From: Joohyung Lee and Vladimir Lifschitz To: TAG Attached is an attempt to describe in Action Language C, the effect of the sentence, also with life sentence, parole, and life without the possibilty of parole. Here, The time steps of actions are required to be consistent with the units of time in jail. Please let us know if you have qustions or comments. === :- include 'C.t'. :- macros maxInt -> 9; sum(#1,#2,#3) -> #1 is min((#2)+(#3),maxInt); diff(#1,#2,#3) -> #1 is max((#2)-(#3),0). :- sorts person; number. :- variables P :: person; T,T1 :: number; A,A1 :: action; X,X1 :: computed. :- constants 0..maxInt :: number; joker :: person; timeToServe(person,number) :: fluent; jail(person) :: fluent; notAllowedParole(person) :: inertialFluent; parole(person), lifeSentence(person), lifeSentenceNoParole(person), sentence(person,number) :: action. nonexecutable A && A1 if -(A=A1). % unique remaining units of time in jail for every person. always \/T: timeToServe(P,T). caused -timeToServe(P,T1) if timeToServe(P,T) && -(T=T1). % The fact that the remaining units of time in jail is not 0 % means the person is in jail now. caused jail(P) if timeToServe(P,T) && -(T=0). % otherwise, he is not in jail now. caused -jail(P) if timeToServe(P,0). % sentence a person P to T units of time in jail % if the person is not in jail now, sentence(P,T) causes timeToServe(P,T) if -jail(P). % if the person is already in jail, % another sentence will add up the time to serve in jail. sentence(P,T) causes timeToServe(P,X1) if jail(P) && timeToServe(P,T1) && sum(X,T,T1) && diff(X1,X,1). nonexecutable sentence(P,0). % life sentence(w, w/o parole) will set time to serve to maximum time. lifeSentence(P) causes timeToServe(P,maxInt). lifeSentenceNoParole(P) causes timeToServe(P,maxInt). lifeSentenceNoParole(P) causes notAllowedParole(P). % if life sentenced without parole, the person can't be paroled. nonexecutable parole(P) if notAllowedParole(P). % notAllowedParole flag will be set to default after % the end of serving in jail. caused -notAllowedParole(P) if timeToServe(P,0). % decrease remaining units of time in jail, if not sentenced otherwise. /\T1: -sentence(P,T1) && -lifeSentence(P) && -lifeSentenceNoParole(P) && -parole(P) causes timeToServe(P,X) if timeToServe(P,T) && diff(X,T,1). % parole parole(P) causes timeToServe(P,0) if jail(P). :- plan label :: 0; time :: 9; facts :: 0: timeToServe(joker,0), 2: -o(A), 3: -o(A), 4: o(sentence(joker,2)), 7: o(lifeSentenceNoParole(joker)), 8: -o(A); goals :: 1: -jail(joker), 2: jail(joker), 3: jail(joker), 4: jail(joker), 6: -jail(joker). === | ?- plan 0. calling sato... run time (seconds) 0.10 0. timeToServe(joker,0) 1. timeToServe(joker,0) ACTIONS: sentence(joker,7) 2. jail(joker) timeToServe(joker,7) 3. jail(joker) timeToServe(joker,6) 4. jail(joker) timeToServe(joker,5) ACTIONS: sentence(joker,2) 5. jail(joker) timeToServe(joker,6) ACTIONS: parole(joker) 6. timeToServe(joker,0) 7. timeToServe(joker,0) ACTIONS: lifeSentenceNoParole(joker) 8. jail(joker) notAllowedParole(joker) timeToServe(joker,9) 9. jail(joker) notAllowedParole(joker) timeToServe(joker,8) Verify plan? (y/n) y verifying......... The plan is verified! yes | ?- ========== Date: 16 Dec 1999 From: Vladimir Lifschitz To: TAG Let's look at the key postulate in the formalization that Jo sent you this morning: the remaining time decreases by 1 whenever the person is not sentenced to an additional term. Here it is, in a slightly simplified form: /\T1: -sentence(P,T1) causes timeToServe(P,X) if timeToServe(P,T) && diff(X,T,1). In action language C, this is shorthand for caused timeToServe(P,X) after /\T1: -sentence(P,T1) && timeToServe(P,T) && diff(X,T,1). What's interesting about this postulate is that it sanctions a change in the value of a fluent under the assumption that certain actions are *not* executed. Accordingly, in the output of ccalc we read: 1. timeToServe(joker,0) ACTIONS: sentence(joker,7) 2. jail(joker) timeToServe(joker,7) 3. jail(joker) timeToServe(joker,6) 4. jail(joker) timeToServe(joker,5) I am wondering whether anything like this can be expressed in Action Language B. Any ideas? ========== Date: Thu, 16 Dec 1999 From: Hudson Turner To: Vladimir Lifschitz Perhaps it would be nicer to avoid reference to actions... It seems this could be nicely expressed instead as a form of inertia -- roughly, time to serve normally decreases by 1. caused timeToServe(P,X) if timeToServe(P,X) after timeToServe(P,T) && diff(X,T,1). This approach might prove more convenient if we later add a "pardon" action, for instance. ========== Date: Thu, 16 Dec 1999 From: Vladimir Lifschitz To: Hudson Turner Good point. Your observation suggests that the phenomenon we are talking about may be one of those that Action Language B is not good for.