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).