Choosing a Place for Dinner: Discussion Date: Fri, 27 Jun 2003 From: Axel Polleres To: TAG I just had a quick look at the dlv encoding by Marcello Balducini and Michael Gelfond and would like to add some improvements: > [...] > eats(italian,D) v eats(chinese,D) :- day(D). > [...] > % RULE 2 > % Peter can only have 1 dinner per day. > % > :- eats(R1,D), eats(R2,D), restaurant(R1), restaurant(R2), R1 != R2. 1) RULE 2 is superfluous in this encoding, as disjunction in RULE 1 is always minimal (the program is head-cycle free), i.e. either italian or chinese are chosen in an answer set but not both. head-cycle freeness also holds if we add extra information extra info as proposed by the authors saying that Peter went to the Chinese on Wednesday and Thursday as facts: eats(chinese,wed). eats(chinese,thu). Sidemark: RULE 2 could be usefull if we allow for an arbitrary number of restaurants, then RULES 1-3 could more generally be encoded by the following rules: eats(R,D) v -eats(R,D) :- restaurant(R), day(D), not closed(R,D). :- day(D), not #count{R:eats(R,D)}=1. instead of one big disjunction for all possible restaurants. Note that this uses the new dlv-aggregates to ensure that exactly one restaurant is chosen per day. 2) To my understanding a single weak constraint: :~ eats(R,D), eats(R,D1), next(D,D1). is sufficient as replacement for RULE 4-6. This results in a more concise dlv encoding as follows: ------------------------------------------------ next(mon,tue). next(tue,wed). next(wed,thu). next(thu,fri). next(fri,sat). next(sat,sun). next(sun,mon). day(X) :- next(X,Y). closed(italian,mon). eats(italian,D) v eats(chinese,D) :- day(D). :- eats(R,D), closed(R,D). :~ eats(R,D), eats(R,D1), next(D,D1). ------------------------------------------------ having answer sets exactly corresponding to the answer sets of the other encodings proposed. It is IMO also quite intuitive. What do you think? ======== Date: Thu, 3 Jul 2003 From: Marcello Balduccini To: TAG let me reply to Axel's suggestions in reverse order. > 2) To my understanding a single weak constraint: > :~ eats(R,D), eats(R,D1), next(D,D1). > > is sufficient as replacement for RULE 4-6. > > This results in a more concise dlv encoding as follows: > ------------------------------------------------ > next(mon,tue). next(tue,wed). next(wed,thu). > next(thu,fri). next(fri,sat). next(sat,sun). > next(sun,mon). > > day(X) :- next(X,Y). > closed(italian,mon). > > eats(italian,D) v eats(chinese,D) :- day(D). > :- eats(R,D), closed(R,D). > :~ eats(R,D), eats(R,D1), next(D,D1). > ------------------------------------------------ > > having answer sets exactly corresponding to the answer sets of the > other encodings proposed. It is IMO also quite intuitive. What do you > think? The two versions are *not* equivalent. The program that Michael and I proposed has one answer set: {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), eats(italian,thu), eats(chinese,fri), eats(italian,sat), eats(chinese,sun)} while the modification proposed by Axel has 7: {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), eats(italian,thu), eats(chinese,fri), eats(italian,sat), eats(chinese,sun)} {eats(chinese,mon), eats(chinese,tue), eats(italian,wed), eats(chinese,thu), eats(italian,fri), eats(chinese,sat), eats(italian,sun)} {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), eats(italian,thu), eats(chinese,fri), eats(chinese,sat), eats(italian,sun)} {eats(chinese,mon), eats(italian,tue), eats(italian,wed), eats(chinese,thu), eats(italian,fri), eats(chinese,sat), eats(italian,sun)} {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), eats(chinese,thu), eats(italian,fri), eats(chinese,sat), eats(italian,sun)} {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), eats(italian,thu), eats(italian,fri), eats(chinese,sat), eats(italian,sun)} {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), eats(italian,thu), eats(chinese,fri), eats(italian,sat), eats(italian,sun)} The difference lies indeed in the formalization of the condition that "IF THERE IS A CHOICE, Peter prefers not to go to the place where he had dinner the night before". Our understanding of Vladimir's statement was that, for any two consecutive days D1, D2: 1) if both restaurants are open on D2, then Peter will avoid to go to the same restaurant where he went on D1; 2) if only the Chinese is open on D2, Peter has no choice. Therefore IT IS OK for him to go to the Chinese on D2, even if he has been to the Chinese on D1 as well. In Axel's formalization, Peter prefers not to go the same restaurant on D1 and D2, INDEPENDENTLY of whether he has a choice on D2. So here is what happens in practice. Since there are two restaurants and an odd number of days, any legal selection of restaurants for the week will always contain at least a repetition (i.e., Peter cannot avoid to go to the same restaurant at least once a week). Let us restrict our attention to those candidate solutions containing only one repetition (the others being clearly less acceptable). Under our understanding, the canditate solution where he goes to the Chinese both on Sunday and on Monday does not violate Peter's preference, since he has no choice on Monday. All the other candidate solutions violate the preference. Hence, the first is the only solution to the problem. Under Axel's formalization, all candidate solutions containing only one repetition are equally acceptable, since all of them violate once the preference that he should not go to the same restaurant twice in a row. Hence, his formalization returns seven solutions (the eigth possible selection is not legal because it would force Peter to go to the Italian on Monday). > 1) RULE 2 is superfluous in this encoding, as disjunction in RULE 1 > is always minimal (the program is head-cycle free), i.e. either > italian or chinese are chosen in an answer set but not both. > > head-cycle freeness also holds if we add extra information > extra info as proposed by the authors saying that Peter went to > the Chinese on Wednesday and Thursday as facts: > eats(chinese,wed). > eats(chinese,thu). The fact is that RULE 2 encodes an important piece of commonsense knowledge, which is derivable from RULE 1 ONLY BECAUSE OF THE PARTICULAR WAY THE PROGRAM IS WRITTEN. When we encoded the domain, we tried to be as general as possible, in order to make the encoding elaboration tolerant. Axel gives a good example showing when elaborations can make RULE 2 important when he says: > Sidemark: RULE 2 could be usefull if we allow for an arbitrary number of > restaurants, [...] There is also another interesting example that I want to point out. Suppose we allow the user to specify partial solutions, i.e. information on where Peter should eat on some days. If the user gives an inconsistent specification, such as: eats(chinese,wed). eats(italian,wed). our original encoding returns no model. On the other hand, after we remove RULE 2, the program has two models: {eats(italian,wed), eats(chinese,wed), eats(chinese,mon), eats(italian,tue), eats(chinese,thu), eats(italian,fri), eats(chinese,sat), eats(italian,sun)} {eats(italian,wed), eats(chinese,wed), eats(chinese,mon), eats(italian,tue), eats(italian,thu), eats(chinese,fri), eats(italian,sat), eats(chinese,sun)} This shows that the reasoner failed to detect inconsistency in the input. Verification of the input is in my opinion one important feature of the behavior of rational agents. ======== Date: Thu, 3 Jul 2003 From: Axel Polleres To: Marcello Balducini many thanks for your explanations! On Thu, 3 Jul 2003, Marcello Balduccini wrote: > > having answer sets exactly corresponding to the answer sets of the > > other encodings proposed. It is IMO also quite intuitive. What do you > > think? > The two versions are *not* equivalent. The program that Michael and I > proposed has one answer set: > > {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), > eats(italian,thu), eats(chinese,fri), eats(italian,sat), > eats(chinese,sun)} > > while the modification proposed by Axel has 7: indeed, I was not very precise here, I was referring to the models of the LPOD encoding, which are the same seven. > The difference lies indeed in the formalization of the condition that > "IF THERE IS A CHOICE, Peter prefers not to go to the place where he > had dinner the night before". > [...] > Under our understanding, the canditate solution where he goes to the > Chinese both on Sunday and on Monday does not violate Peter's preference, > since he has no choice on Monday. All the other candidate solutions > violate the preference. Hence, the first is the only solution to the > problem. This is indeed a nice feature of your encoding, which I didn't think of! At least you can save Rule 6 by directly writing non-availability into Rule 5, yes? (but this is only a detail): has_choice(D) :- restaurant(R1), restaurant(R2), day(D), R1 != R2, not closed(R1,D), not closed(R2,D). a final remark: The whole program is probably, though you might need some extra rules, also expressible in smodels in a way such that violations are defeasible (As in the example you suggested where peter eats Chinese on Wednesday and Thursday in a row): One could use their "minimize" statement instead of our weak constraints. Still, I think the idea of weak constraints is more intuitive, especially in this example. ======== Date: Thu, 3 Jul 2003 From: Vladimir Lifschitz To: TAG > > The two versions are *not* equivalent. The program that Michael and I > > proposed has one answer set: > > > > {eats(chinese,mon), eats(italian,tue), eats(chinese,wed), > > eats(italian,thu), eats(chinese,fri), eats(italian,sat), > > eats(chinese,sun)} > > > > while the modification proposed by Axel has 7: > > indeed, I was not very precise here, I was referring to the models of the > LPOD encoding, which are the same seven. This seems to mean that the LPOD formalization is not completely satisfactory, in view of Marcello's criticisms. ======== Date: Thu, 3 Jul 2003 From: Michael Gelfond To: TAG >a final remark: The whole program is probably, though you might need some >extra rules, also expressible in smodels in a way such that violations are >defeasible (As in the example you suggested where peter eats Chinese on >Wednesday and Thursday in a row): One could use their "minimize" >statement instead of our weak constraints. Still, I think the idea of weak >constraints is more intuitive, especially in this example. > It will be interesting to actually do that and compare the representations. I expect some real differences, e.g. minimize will return only one model while weak constraints allow more than that. Another thing which will be nice to do is to modify the program to allow multiple 'weak constraints' with preferences, e.g. add something like 'I prefer to accommodate my guests and, if possible, go to the restaurant of their choice'. If my wife likes the guest then this constraint takes precedence over the desire to change. Otherwise it does not. ======== Date: Mon, 4 Aug 2003 From: Ale Provetti To: TAG at last, also Alessandra and I have something to say about the '1-model' interpretation of the dinner example proposed by Marcello and Michael. Such interpretation of the example too has a rather direct encoding in LPOD: --------------------- day(1..7). row(1,2). row(2,3). row(3,4). row(4,5). row(5,6). row(6,7). row(7,1). closeit(2). %having choice choice(D) :- day(D), not closeit(D), not closech(D). %having no choice dinnerch(D) :- closeit(D), day(D). dinnerit(D) :- closech(D), day(D). %having dinner relation dinnerit(D2) x dinnerch(D2) :- day(D2), day(D1), dinnerch(D1), row(D1,D2), choice(D2). dinnerch(D2) x dinnerit(D2) :- day(D2), day(D1), dinnerit(D1), row(D1,D2), choice(D2). %constraints :- dinnerit(D), dinnerch(D), day(D). ------------------------------------ Since now preferencial reasoning is carried out only for the days true of 'choice', we obtain only one answer set: ------------------------------------ mag[~]>lparse -d none --priorities dinner-choice.sm > dinner-choice.ground mag[~]> mag[~]>psmodels dinner-choice.ground 0 Answer: 1 Stable Model: dinnerch(2) dinnerch(1) dinnerit(3) dinnerch(4) dinnerit(5) dinnerch(6) dinnerit(7) *sat(1,1) *sat(2,1) *sat(3,1) *sat(4,1) *sat(5,1) *sat(6,1) *sat(7,1) *sat(8,1) *sat(9,1) *sat(10,1) *sat(11,1) *sat(12,1) Tester calls: 64 mag[~]> ------------------------------------ The '*sat' atoms are introduced by lparse --priorities to compile preferences, so you may disregard them. However, they can be seen as 'measures' of the degree of satisfaction of a rule. Of course, 'choice' may be given a more elegant implementation, but here we are restricting to two alternatives only.. To conclude the experiment, we have added, following Marcello's consideration on inconsistency detection: dinnerch(4). dinnerit(4). ======== Date: Tue 26 Aug 2003 From: Vladimir Lifschitz To: Alessanra Milleo and Ale Provetti As I understand, the main difference between the new formalization of this example and your original formalization is that you have now added the condition choice(D2) to the bodies of the rules dinnerit(D2) x dinnerch(D2) :- day(D2), day(D1), dinnerch(D1), row(D1,D2). dinnerch(D2) x dinnerit(D2) :- day(D2), day(D1), dinnerit(D1), row(D1,D2). This surely makes your formalization of the assertion "If there is choice, Peter prefers not to go to the place where he had dinner the night before" more adequate: choice(D2) stands for "there is choice." I like it!