Romeo and Juliet: Discussion Date: Mon, 8 Oct 2001 From: Vladimir Lifschitz To: TAG Several solutions to the Romeo and Juliet problem are available now at http://www.cs.utexas.edu/tag/discussions.html . As an example, here is the output produced by one of the Smodels programs: Answer: 1 Stable Model: get_married(juliet,romeo,2) Answer: 2 Stable Model: ask_parent(juliet) get_married(juliet,romeo,1) Answer: 3 Stable Model: ask_parent(juliet) ask_parent(romeo) get_married(juliet,romeo,0) In some formalizations, asking permission is viewed as a separate event that occurs prior to getting married, and then the number of answers may be greater than 3. The heart of the problem is, of course, describing how a person's age changes with time. The summary below shows how this is done in each solution. Please let us know if you have any comments or questions. Regards, Vladimir ============================================================================= Summary of Solutions *** SOLUTION 1, in the language of PAL age(P):=prev(age(P))+1 if wait_a_year; *** SOLUTION 2, in the language of smodels state(AGE1,AGE2,PERM1,PERM2,STAT) :- do(wait,AGE1-1,AGE2-1,PERM1,PERM2,STAT), age(AGE1), age(AGE2), permission(PERM1), permission(PERM2), status(STAT). *** SOLUTION 3, in the language of smodels age(X,A1,T) :- age(X,A,0), assign(A1,A+T),time(T), person(X), number(A), number(A1), T>0. *** SOLUTION 4, in the language of smodels holds(age(P, X + 1), T + 1) :- occurs(waitAYear, T), holds(age(P, X), T), timePoint(T), agePoint(X), person(P). *** SOLUTION 5, in the language of CCalc wait causes age(P)=Ag+1 if age(P)=Ag where Ag<19. *** SOLUTION 6, in the language of Smodels age_of(P,A+1,S+1) :- age_of(P,A,S),person(P),age(A),step(S),S 1, person(P), age(A), age(P,A,Y-1). (b) has_permit(Person,Year) has_perm(P,Y2) :- year(Y1),year(Y2),person(P), o(get_perm(P),Y1), Y1 <= Y2. The first rule corresponds to 'the natural flow of time'. The second is a causal law combined with inertia. Both fluents are subject to the closed world assumption which we could, of course, represent explicitly. Now our task can be formulated as selecting a year for marriage and, if needed, a year for getting the necessary permission, i.e we have 1{o(get_married,Y) : year(Y)}1. {o(get_perm(P),Y) : year(Y)}1 :- person(P). The selected actions should satisfy one legal constraint: :- year(Y), person(P),age(A), o(get_married,Y), age(P,A,Y), A < 18, not has_perm(P,Y). and a few commonsense constraints prohibiting performance of useless actions, e.g. Do not ask for a permission if older than 17. :- age(A),year(Y),person(P), age(P,A,Y), A>17, get_perm(P,Y). No unused permissions allowed. :- year(Y), person(P),age(A), o(get_married,Y), age(P,A,Y), A > 17, has_perm(P,Y). The smodels gives us four models: o(get_married,1) o(get_perm(r),1) o(get_perm(j),1) ::endmodel o(get_married,3) ::endmodel o(get_married,2) o(get_perm(j),2) ::endmodel o(get_married,2) o(get_perm(j),1) ::endmodel Now we can address the second part of scheduling - finding legal ordering of actions within each interval. Since the operation is important for scheduling and probably for some other purposes It may be a good idea to expand A-Prolog and its interpreters by a good efficient mechanism for finding enumerations of sets satisfying certain constraints. I do not believe it is really difficult and may be very useful. WHAT DO YOU THINK? Is it worth doing? Meanwhile me can do it directly by (somewhat clumsy) rules: step(0..2). 1{do(get_married(Y),T) : step(T)}1 :- year(Y), o(get_married,Y). 1{do(get_perm(P,Y),T) : step(T) }1 :- year(Y),person(P), o(get_perm(P),Y). (Notice the use of new relation, DO.) Permission should be obtained before marriage. :- year(Y), person(P), step(T1),step(T2), do(get_married(Y),T2), do(get_perm(P,Y),T1), T1 >= T2. The rules so far are o.k. But we also need to insure enumeration by consecutive numbers starting at 0. To do that I'll use an auxiliary relation action_occ(Y,T) read as 'Some action which occur in year Y is enumerated by number T' action_occ(Y,T) :- do(get_married(Y),T), year(Y), step(T). action_occ(Y,T) :- do(get_perm(P,Y),T), step(T), person(P), year(Y). and a constraint :- not action_occ(Y,T), action_occ(Y,T+1), year(Y), step(T). THESE THREE RULES ARE FAIRLY UGLY and can be replaced by the general mechanism I was referring to before. Can we do better than that? ANY COMMENTS? Now SMODELS produces the following six plans: do(get_married(1),1) do(get_perm(r,1),0) do(get_perm(j,1),0) ::endmodel do(get_married(1),2) do(get_perm(r,1),0) do(get_perm(j,1),1) ::endmodel do(get_married(1),2) do(get_perm(r,1),1) do(get_perm(j,1),0) ::endmodel do(get_married(3),0) ::endmodel do(get_married(2),1) do(get_perm(j,2),0) ::endmodel do(get_married(2),0) do(get_perm(j,1),0) ::endmodel Notice that in plan (1) both people are asking for the permissions simultaneously. I hope this was useful. I'd really like to hear some comments and to see an analysis of other solutions based on the more or less explicit explanation of the goal of the formalization. ======== Date: Tue, 6 Nov 2001 From: Vladimir Lifschitz To: Michael Gelfond > It seems that different people understood Vladimir's > specification differently. You are right! I knew that my specification was not entirely complete and unambiguous, but I didn't quite expect this diversity of interpretations. For instance, I thought of the plan > get_perm(juliet,1). > get_perm(romeo,1). > get_married(1). as valid. But I can understand why you decided to reject it. > But what is the intended use of a toy problem, like > that of Romeo and Juliet? > Normally, such an intended use is to illustrate, clarify, > or simply investigate the ability (or inability) of a formalism > to express some features associated with the problem. Yes, I think of a small KR problem, such as Romeo and Juliet, as a simple way to isolate a class of features to be represented. The goal is to represent the features that are needed to understand and answer the question. In this example, the key element is the dependence of a person's age on the flow of time.