Choosing a Place for Dinner: Solutions Date: Thu, 26 Jun 2003 From: Vladimir Lifschitz To: TAG I have received four solutions from you, and these solutions use four different knowledge representation systems: CCalc, cmodels, dlv and LPOD. The solutions are appended at the end of this message. It is interesting to compare the formalizations of the statement If there is choice, Peter prefers not to go to the place where he had dinner the night before in these solutions. The smodels formalization is the most straightforward. It defines the predicate has_choice by the rule has_choice(D) :- restaurant(R1), restaurant(R2), day(D), neq(R1,R2), available(R1,D), available(R2,D). and then imposes the constraint :- restaurant(R), next(D1,D2), eats(R,D1), eats(R,D2), has_choice(D2). The dlv formalization is similar except that it replaces the symbol ':-' in the constraint with the "weak constraint" symbol ':~' . This interesting feature of dlv makes constraints defeasible, in the sense that they are disregarded if it is impossible to satisfy them. The authors of these solutions explain: To see how the behaviors of the two programs differ, consider what happens if we were to add extra information saying that Peter went to the Chinese on Wednesday and Thursday. The first program would be inconsistent, while the second would still be consistent. In conclusion, it seems that the second solution is more elaboration tolerant. The CCalc formalization is more flexible than the smodels version also, but in a different way. It uses the "unless" construct of CCalc and an abnormality predicate to say that normally Peter doesn't go to the restaurant that he visited the day before: nonexecutable go(R) if visited=R unless ab(R). Separately, it specifies that the case when the other restaurant is closed is an exception: caused ab(R) after closed(R1,today) where R\=R1. This design allows us to weaken the rule about choosing a different restaurant by specifying other exceptions. We can even disable that rule altogether by adding the rule that makes ab identically true. Finally, the LPOD solution is surprisingly concise, in comparison with the others. LPOD ("Logic Programs with Ordered Disjunctions") is a formalism introduced by Gerd Brewka, and its distinctive feature is the use of ordered disjunctions ... x ... x ... in the heads of rules to indicate preferences. For instance, the rule dinnerit(D2) x dinnerch(D2) :- day(D2), day(D1), dinnerch(D1), row(D1,D2). can be understood to mean that if Peter has a Chinese dinner on day D1, and D2 is the next day, then he has either an Italian dinner or a Chinese dinner on day D2, and THE FIRST OPTION IS PREFERRED. That's it! LPOD programs can be executed under a special version of smodels, called psmodels, which is available at http://www.tcs.hut.fi/Software/smodels/priority/ . ======================= 1. Joohyung Lee, Ccalc ======================= % Peter's choice of restaurants :- macros sunday -> 0; monday -> 1; tuesday -> 2; wednesday -> 3; thursday -> 4; friday -> 5; saturday -> 6. :- sorts restaurant; day. :- objects chinese, italian :: restaurant; sunday..saturday :: day. :- variables R,R1 :: restaurant; D :: day. :- constants today :: simpleFluent(day); visited :: inertialFluent(restaurant); closed(restaurant,day) :: boolean; go(restaurant) :: exogenousAction. % days go on caused today=(D+1) mod 7 after today=D. % italian restaurant is closed on monday closed(italian,monday). default -closed(R,D). % if the restaurant is closed today, don't go there nonexecutable go(R) if closed(R,today). go(R) causes visited=R. % prefer not to go to the same restaurant visited yesterday nonexecutable go(R) if visited=R unless ab(R). % but no choice if the other restaurant is closed caused ab(R) after closed(R1,today) where R\=R1. % eat everyday ;-) always [\/R | go(R)]. :- query maxstep :: 40; 0: today=friday. ================================================== 2. Marcello Balducini and Michael Gelfond, smodels ================================================== % Days next(mon,tue). next(tue,wed). next(wed,thu). next(thu,fri). next(fri,sat). next(sat,sun). next(sun,mon). #hide next(X,Y). day(X) :- next(X,Y). #domain day(D). #hide day(D). % Restaurants restaurant(italian). restaurant(chinese). #hide restaurant(R). %%%%%%%%%%%%%%%%%%%%%%%% % RULE 1 % % Peter eats either at the Italian or at the Chinese. % 1{ eats(R,Day) : restaurant(R) }1 :- day(Day). % The Italian is closed on Monday closed(italian,mon). #hide closed(R,D). % RULE 2 % % Peter cannot eat at a closed restaurant. :- eats(R,D), closed(R,D). % RULE 3 % % If there is choice, Peter prefers not to go to the place % where he had dinner the night before. :- restaurant(R), next(D1,D2), eats(R,D1), eats(R,D2), has_choice(D2). % RULE 4 % % has_choice(D): Peter has a choice of restaurant on day D. % has_choice(D) :- restaurant(R1), restaurant(R2), day(D), neq(R1,R2), available(R1,D), available(R2,D). #hide has_choice(D). % RULE 5 % % available(R,D): restaurant R is available on day D % available(R,D) :- restaurant(R), day(D), not closed(R,D). #hide available(R,D). ============================================== 3. Marcello Balducini and Michael Gelfond, dlv ============================================== % Days 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). % Restaurants restaurant(italian). restaurant(chinese). %%%%%%%%%%%%%%%%%%%%%%%% % RULE 1 % % Peter eats either at the Italian or at the Chinese. % 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. % The Italian is closed on Monday closed(italian,mon). % RULE 3 % % Peter cannot eat at a closed restaurant. % :- eats(R,D), closed(R,D). % RULE 4 (WEAK CONSTRAINT) % % If there is choice, Peter prefers not to go to the place % where he had dinner the night before. % :~ eats(E,D1), eats(E,D2), next(D1,D2), has_choice(D2). % RULE 5 % % has_choice(D): there is a choice of a restaurant on day D. % has_choice(D) :- restaurant(R1), restaurant(R2), day(D), R1 != R2, available(R1,D), available(R2,D). % RULE 6 % % available(R,D): restaurant R is available on day D % % We assume COMPLETE INFORMATION on closed(R,D). % available(R,D) :- restaurant(R), day(D), not closed(R,D). ========================================== 4. Ale Provetti and Alessandra Mileo, 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). closedit(2). dinnerch(D) :- closedit(D), day(D). dinnerit(D) :- closedch(D), day(D). %having dinner relation 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). %constraints :- dinnerit(D), dinnerch(D), day(D).