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