Fight for a Snack: Discussion

Date: Fri, 24 Dec 2003
From: Michael Gelfond
To: TAG

I am having difficulties understanding the meaning of the time 
variable in the first solution. 
In the standard usage the value of this variable 
changes as a result of an action. Under this interpretation
we should have:

fight(apple ,left ,1).
fight(banana,right,2).

instead of 

fight(apple ,left ,2).
fight(banana,right,3).

But this change leads to an incorrect solution. 

SOME EXPLANATION will be useful here.


It also maybe interesting to compare styles
of solutions 1 and 2. The difference between SMODELS and DLV 
is accidental. According to Greg he used SMODELS since at the time
DLV was not available at his APPLE computer. (It is now. Thanks!).

The real difference is in the use of negation and constraints.
For instance, if I update the Gerald's  program by adding

has(apple,left,1).

it will not be able to detect inconsistency (which I believe is intended). 
Greg's program will. (He misses a constraint though, 
``one can't fight oneself'', correctly stated by Selim.)
Selim's solution also seems to be aimed at solving a particular
problem. In this sense it is similar to 1.
I encourage my students to make sure that, given the story,
their program  should be able to correctly answer, say, queries 

has(me,apple,0) yes

has(left,apple,0) no

has(me, apple, 1) maybe

which seem to be difficult to obtain from Selim's representation.
(But, most likely, this was not his goal). 
What are your attitudes and preference?

========

Date: Mon, 19 Jan 2004
From: Selim Erdogan
To: TAG

   The results to the queries given by Michael above can be obtained by
just cosmetically extending my representation.  What needs to be done is to
add a statically determined fluent has(person,snack) and define it in
terms of the possible_owner fluent.  This can be done by adding the
following lines:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- sorts
   truth.

:- constants
  has(person,snack)		:: sdFluent(truth).

caused has(P,S)=no if -possible_owner(P,S).
caused has(P,S)=yes if possible_owner(P,S)
	                && [/\P1 | -possible_owner(P1,S) ++ P=P1].
caused has(P,S)=maybe if possible_owner(P,S)
			&& possible_owner(P1,S) && P\=P1.

:- objects
  yes, no, maybe            :: truth.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   Getting back to the discussion of the problem in general, the reason I
included the uncertainty inside the program by having a single model with
multiple "possible_owner"s (instead of allowing multiple models with each
having single owners) was that I wanted the system to have access to this
uncertainty.  If we want a system to reason with the uncertainty in this
problem, then in the case with multiple models, we'd need a higher level
system working on top to go through those models and see what the case is
in each of them.

   It seems like the uncertainty in this problem is related to our limited
knowledge of the result of the action, rather than the action's
nondeterminism.  This could be thought of as a form of nondeterminism too,
but it influenced me enough to write a representation where an action
deterministically causes an uncertain result instead of a nondeterministic
action causing different results in different models.

   An interesting extension of this problem is when a new person comes and
wants to take possession of the apple and the banana.  Whom should that
person fight?  If he fights me, it might be for nothing if my neighbors
already took the fruit from me.  On the other hand if he doesn't know who
won the fights, the most guaranteed thing would be to fight all of us.
Representing the different possibilities as different scenarios may lead
to wrong plans for the "new person" since he will plan to fight me if he
bases his plans on the scenario where I won, when in fact my neighbor
might have won.  How might a higher level system working on top of
multiple models deal with this?

   When you consider this extended scenario with my program, it just seems
to spread possible ownership and our knowledge about the owners of the
snacks starts to get really vague.  What happens when there are many
possible owners and a newcomer fights just one but not all?  My solution
makes him a possible owner too but is this a good idea?

========

Date: Thu, 29 Jan 2004
From: Michael Gelfond
To: Selim Erdogan

> The results to the queries given by Michael above can be obtained by
> just cosmetically extending my representation.  What needs to be done is to
> add a statically determined fluent has(person,snack) and define it in
> terms of the possible_owner fluent.  This can be done by adding the
> following lines:
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> :- sorts
>    truth.
>
> :- constants
>   has(person,snack)		:: sdFluent(truth).
>
> caused has(P,S)=no if -possible_owner(P,S).
> caused has(P,S)=yes if possible_owner(P,S)
> 	                && [/\P1 | -possible_owner(P1,S) ++ P=P1].
> caused has(P,S)=maybe if possible_owner(P,S)
> 			&& possible_owner(P1,S) && P\=P1.
>
> :- objects
>   yes, no, maybe            :: truth.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This is certainly possible but it is not exactly what I 
meant.  Let me try to give more details:

In the ASP methodology, I am trying to describe, we have
several players:
 
P - programmer;
A - agent associated with the program which
    contains the agent's knowledge base, KB.
U - user.

The user, U, is given collections of input and output
relations and objects from the language of agent A.
( Output relations correspond to views in the database terminology
or to EXPORT relations (procedures) in the lingo of programming
languages.)

U has a number of ways in which he can communicate with the agent. 
Here is a (very) incomplete list:


1. U can tell A a new input fact;

2. U can query A about truth or falsity of the output relations;

3. U can ask A to perform a certain task, e.g. planning, etc

4. U can give A goals and ask him to accomplish them autonomously, etc.


So I was talking about task (2). If p is an output relation
then answer to p is yes if KB entails p, no if it entails ~p,
unknown otherwise. One can also have possible(p) if p holds
in at least one answer set of KB, etc. 

has(person,fruit,timepoint) (or the corresponding holds in the Greg's
program) is a natural output relation. (It can be used to define
other output relations, e.g.

dangerous(P,T) :- likes(P,F),
                  ~has(P,F,T).

)
So the user can ask queries

   possible(has(P,apple)) which will return the possible owners
   of the apple.

I am not sure what are the output relations in your solution,
and how the query answering is interpreted in it. 
(One surely does not want the user to define queries every time
he wants to ask them.) 

This is not really a criticism of your solution though - just
an attempt to more clearly articulate the approach and see
if there is a real difference. Right now I am not really sure.

> Getting back to the discussion of the problem in general, the  
> reason I included the uncertainty inside the program by having 
> a single model  with multiple "possible_owner"s (instead of 
> allowing multiple models with each having single owners) was 
> that I wanted the system to have access to  this
> uncertainty.  If we want a system to reason with the uncertainty in  
> this problem, then in the case with multiple models, we'd need a higher  
> level system working on top to go through those models and 
> see what the case is in each of them.

You are right. A long time ago I had a formalism of epistemic 
specifications which was invented to deal with this. It had an
operator M and would allow us to say something like:

possible_owner(P,F,T) :- M has(P,F,T).

be_nice_to(P) :- possible_owner(P,F,T)

Here I ``use'' the info about possible ownership.
Assuming that the original program had two answer sets, S1 and S2,
containing has(me,apple,1) and has(left,apple,1) respectively
the new program (epistemic specifications) will have 
two answer sets 

S1 + {possible_owner(me,apple,1),possible_owner(left,apple,1),
      be_nice_to(me),be_nice_to(left)}

S2 + {possible_owner(me,apple,1),possible_owner(left,apple,1),
      be_nice_to(me),be_nice_to(left)}

The formalism was used by several people but didn't really
attracted much attention. It maybe useful here though.

> It seems like the uncertainty in this problem is related to our  
> limited knowledge of the result of the action, rather than the action's
> nondeterminism.  This could be thought of as a form of nondeterminism  
> too, but it influenced me enough to write a representation where an action
> deterministically causes an uncertain result instead of a  
> nondeterministic action causing different results in different models.

I am not sure I understand this. For me the outcome of fighting
in most cases is rather unpredictable and can be viewed as a
true non-deterministic effect (if, of course, such a thing exists at all). 

> An interesting extension of this problem is when a new person comes  
> and wants to take possession of the apple and the banana.  Whom should that
> person fight?  

I am not sure we can answer this question without new imformation
(especally since I do not think X CAN fight Y for P if neither has P).

> If he fights me, it might be for nothing if my neighbors
> already took the fruit from me.  On the other hand if he doesn't know  
> who won the fights, the most guaranteed thing would be to fight all of us.
> Representing the different possibilities as different scenarios may  
> lead to wrong plans for the "new person" since he will plan to fight me if  
> he bases his plans on the scenario where I won, when in fact my neighbor
> might have won.  How might a higher level system working on top of
> multiple models deal with this?

I think we need observations similar to those we have in the ``APL agent
manager''. Marcello plans to say more about it soon.


========

Date: Wed, 24 Mar 2004
From: Gerald Pfeifer
To: Michael Gelfond

> I am having difficulties understanding the meaning of the time
> variable in the first solution.
> In the standard usage the value of this variable
> changes as a result of an action. Under this interpretation
> we should have:
>
> fight(apple ,left ,1).
> fight(banana,right,2).
>
> instead of
>
> fight(apple ,left ,2).
> fight(banana,right,3).
>
> But this change leads to an incorrect solution.
>
> SOME EXPLANATION will be useful here.

When first reading your question, I couldn't remember, but the answer
is surprisingly simple:  I started counting the time at 1 (like Pascal
programmers) instead of 0, so 1 denoted the intial state and 2 was the
first action state.

Note that my solution really was not meant as a good example in knowledge
representation, it was quit ad hoc and just designed to get the answers
to the specific problem (without caring for elaboration tolerance, for
example).