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<maxStep,
                       wait_for_a_year(S).

*** SOLUTION 7, in the language of Smodels

  age(j,Y,A) :- year(Y), A = 15+Y. 
  age(r,Y,A) :- year(Y), A = 16+Y. 

*** SOLUTION 8, in the language of Smodels

  age(X,A+1,T+1) :- person(X), time(T),
		    age(X,A,T), age(A).

*** SOLUTION 9, in the language of Smodels

  human_age(H,A,S):-human_age(H,A-1,S-1),one_year_pass(S-1),
                    step(S),age(A),human(H).

*** SOLUTION 10, in the language of CCalc

  waitAYear causes age(P) eq A+1 if age(P) eq A && A < maxAge.

==========

Date: Sun, 28 Oct 2001
From: Michael Gelfond
To: TAG

Some time ago I looked at the solutions of the Romeo and Juliet
problem proposed by Vladimir and had a discussion of some of them
with my students. 
Below are parts of the discussion which, I hope,
can be of interest to other members of TAG.
As usual these comments are long so please have patience.
The intent is to stimulate some broader discussion. 

1. The first set of comments is about the way we specify
our problems.

Vladimir says: 
    'Describe this domain in an implemented, 
     declarative language, and use  your 
     representation to compute all possible 
     plans of action that Romeo and Juliet can come up with.'

It seems that different people understood Vladimir's
specification differently. Here are three examples:

(a) Some have plans similar to the one below:

  get_perm(juliet,1).
  get_perm(romeo,1).
  get_married(1).

The plan says that both should get permissions and marry
during the first year.

According to other people this set of actions is not yet a plan,
since the order of actions to be performed is not specified.

(b) Some view a plan 

  get_perm(romeo,1).
  get_perm(juliet,2).
  get_married(3).

as valid.
Others seem to believe that this plan is irrational
and therefore shall not be produced by the program.
if you plan to marry during the third year asking
for the permissions is wasteful. Of course, due to
some unforeseen circumstances this may happen in reality
but we are asked to produce plans, not possible futures.

(c) Some prohibit a plan in which permission is obtained
simultaneously by both people and some allow it. 

After the discussion we seem to agree that (a) is not a plan,
(b) is not a plan assuming the rationality assumption, and (c)
must be allowed - Romeo and Juliet can invite their parents
to some nice place and break the news to both of their families.

ANY COMMENTS? 

2. The second part of our discussion dealt with the methodology
of problem solving and programming in A-Prolog and other declarative
languages. Assuming that two programs are correct how do we judge
their comparative merits? What is a good programming style
in the context of declarative programming?
What are the 'thought processes' involved in writing a program?

Below is my attempt to providing some partial answers to 
these questions. As an illustration I am using a slightly modified
version of my solution of Vladimir's problem. (The modifications were
necessary since my program was not really meant for posting.
I wrote it quickly to illustrate a point to one of my 
students but never actually read it before the Vladimir's message.
So some elements of bad style, like the absence of comments, etc
are obvious.)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

First some general statement:
In my experience the art of declarative programming consists
in balancing the following characteristics of the resulting system:

1. High degree of elaboration tolerance (simple changes
   in the domain knowledge and the queries should be reflected
   by simple changes in the formal representation). 

2. Simplicity (Simple problem should have a simple solution).

3. Efficiency.

The balancing is usually  non-trivial since the desirable characteristics
often contradict each other. I believe that the comparative
importance of each of them is determined by the intended
use of the system. 
The intended use (together with the correctness concerns) should
guide the process of program development. It
will, to a large extend, determine quality of the solution.

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.

It is not easy however to clearly specify these features.
When I looked at the Romeo and Juliet problem 
I was not at all sure why Vladimir wanted it solved.
Efficiency does not seem to be a problem.
The story seems too narrow to make it a platform for 
investigating elaboration tolerance. We can of course
attempt to construct a comprehensive theory of marriage
and use it to address this problem but is that what is 
intended?  Other possibilities include the investigation
of representing  'the natural flow of time', or simply using 
the language to find all the reasonable plans for getting 
married available to the couple, etc.

It may be that, for a 'toy' problem, its desired characteristics
should be mentioned explicitly, either by a specifier or by 
an implementor.
This will make solutions more interesting and understandable to a reader.

Here is my attempt to explain my thinking in this way:

Since the goal of getting all the plans is mentioned
explicitly I took this to be the real purpose of the program.
Its intended use is to produce these plans.
This interpretation determined most of my further steps.

The remaining problem was to find out what point is supposed
to be illustrated by the problem, i.e. why is it interesting?

The wording of the problem suggests that the couple
is planning to marry during the first, second, of third year
starting from the current moment of time. This implies
a timeline
...1...2...3...
The time before 1, the past, is of no interest to us.
The interval between 1 and 2 represents the first 
year, etc. 

The plan should tell the couple what actions to perform during
which year and how to order the actions performed during the same year.

The problem can therefore be modeled not only as a 'typical' planning
problem we discussed in TAG before but also as a scheduling problem.
(As far as I understand combining planners and schedulers under
the umbrella of a single, efficiently implemented logical formalism is 
(one of ?) the most important problems in the planning community.)

So I decided to view the problem as a simple example of scheduling.
I never used A-Prolog for this purpose before so it can make it 
interesting.

Now the solution:

First I concentrate on assigning actions to proper intervals. 

I need types

year(1..3).
person(r;j).
age(16..19).

and actions get_perm(Person) and get_married.

There are some possible alternatives: get_married may
have parameters for a bride and a groom. If I use them 
then my program will be able to simultaneously schedule 
weddings for multiple pairs. I do not immediately
see this as an advantage. On another hand introducing
parameters would probably require stating the symmetry
of the operation. (I do not want to learn that P1 get married
to P2 but not visa versa.) 
Hence no parameters for get_married. 

Now I need to decide on the fluents relevant to the problem.
To make the marriage plans for a year Y our program needs 
to know the age of participants and either or not they have
permissions to marry.

I select two fluents:

(a) age(Person,Age,Year):
  
age(j,16,1).
age(r,17,1).
age(P,A+1,Y) :- 
          year(Y), 
          Y > 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.