Action Languages and Elaboration Tolerance, Part 3

Date: Wed, 09 Jan 2002
From: Pedro Cabalar
To: Michael Gelfond and Vladimir Lifschitz

----- About fluent above -----

To understand the motivation of my doubt, let me put a simpler example
with another fluent. Consider the typical lamp circuit where `light' is
true iff 2 switches are closed. The "usual/traditional" formulation of
this is with 3 regular fluents (light, sw1, sw2) and rules like:

sw1 ^ sw2 causes light	(1)
-sw1 causes -light	(2)
-sw2 causes -light	(3)

Treating light as a defined fluent is also possible: after all, the
truth of light is completely "defined" by sw1 ^ sw2. Then, we can
"remove" (2) and (3), and declare light as noninertial and false by
default.

Now, extrapolating your comments about above to this use of light:

Vladimir:
> Assuming inertia for a defined
> fluent is sometimes harmful, sometimes not, but it is never useful!

Michael:
> You seem to be more interested in modeling 'physical' causality
> and 'physical' inertia while I am mainly concerned with finding
> convenient ways of representing knowledge. The latter representation of
> the 'above' maybe more suitable from your perspective, while from mine
> it is redundant and hence less elegant. (Judging by his
> last message Vladimir shares this perspective.)
> Is this a reasonable analysis?

Q1: why is this 2nd formulation of light "more useful" or "more
elegant"?

Now the programmer would have 2 possibilities to encode the same
scenario. In fact, there is a 3rd possibility since we could assume
light true by default and handle causal rules (2) and (3), removing (1)
instead.

Q2: which should be the criterion to decide when a fluent must be
defined instead of inertial?
Q3: which is the criterion to decide the default value of a defined
fluent?

I understand that defined fluents are interesting, but for me, it would
be simpler if they were only used when the fluent is noninertial "by
nature". A better example could be the one in the new paper about C+,
where something is said about positions of pieces on a moving belt.

Now, coming back to above, if I were an actions-programmer I would first
wonder whether above is inertial by nature or not. I think you've both
agreed in that above "can be" inertial. In other words, it is not
clearly noninertial. Then, at a first sight, I would not see any reason
to remove inertia for above:

Q4: which is the difference of above (w.r.t. light) that points out that
it should be treated as a defined fluent?

My guess is that the difference is due to a "technical" problem and not
to the nature of fluent above in the blocks domain.
 
Michael:
> I am not sure I follow that. Can you elaborate?

The informal definition of above is something like:

  "above(B,L) is true iff either B is on L or it is on another block C
such that, in its turn, above(C,L)"

This definition involves using an existential quantifier. In classical
logic, we'd have that above(B,L) should be equivalent to:

  on(B,L) v exists C (block(C) ^ C!=B ^ above(C,L))	(4)

but, when moving to a dynamic scenario, the equivalence should be
replaced by causal rules where above becomes the effect:

  (4) causes above(B,L)		(5)
  -(4) causes -above(B,L)	(6)

However, using a logic programming style, quantification is not needed:

  above(B,L) :- on(B,L).
  above(B,L) :- block(C), C!=B, on(C,L), above(C,L).

provided that above is false by default

  -above(B,L) :- not above(B,L).

Now, when moving to a dynamic scenario, this last rule enters into a
conflict with inertia:

  h(above(B,L),T+1) :- not -h(above(B,L),T).
  -h(above(B,L),T+1) :- not h(above(B,L),T).

So, the actions-programmer must be aware of this problem, and declare
above as noninertial to avoid it. This is what I mean by saying that the
reason for removing inertia is "technical".

My attempt was to work in the other direction, i.e., with causal rules
(5) and (6) involving quantifiers. 

Q5: As far as I know, C+ allows quantifiers: does the encoding (5),(6)
obtain the expected behavior in C+ (provided that above remains
inertial)?

I first thought that I just needed to add quantifiers to PAL and that's
all. In PAL, (5) and (6) becomes the single expression:

above(B,L):=
    loc(B)=L or 
    (exists C:block. C!=B and C!=L and loc(B)=C and above(C,L));

I tried this, but it didn't work.

Michael:
> What do you mean when you say this didn't work?

PAL is translated into logic programs interpreted either under stable
models or WFS. As it is well known, cycles may lead to a well-founded
model with undefined atoms which usually (not always) means that we get
several stable models or no stable model at all. When this happens, I
understand that the causal description is ill-defined: either we have
constructed some kind of causal paradox or the real world system is
ill-designed.

Using the above formulation, if we just move block 1 on block 2, we get
no stable model, whereas WFS leaves all the above atoms undefined. So,
we got some problem with a "vicious" cycle.

> Is it a problem with the semantics of PAL or with the translation into
> logic programs? 

The problem in PAL is that, informally speaking, causal rules for
above(B,L) depend on some above(C,L), but in its turn, the causal rules
for above(C,L) also depend on above(B,L). The problem is that this cycle
interacts with inertia. I don't know whether this problem arises in
other formulations, although I guess that the answer to Q5 will be
negative.

Michael:
> In your terminology, is the problem 'real' or 'technical'?

I think it is a technical problem. Quantifiers have replaced the use of
defaults, but still we have the conflict with inertia. So, we could
think again about removing inertia for above. But, as I have explained,
I find difficult to find a natural justification to define above as
noninertial.

Michael:
> For me to really answer your question though I need to know
> what is the goal you are trying to achieve.

I want to find a more-or-less natural way of defining above without
having to remove inertia or include new defaults.

Unfortunately, my second attempt to do this (which solved the problem)
is totally dependent on PAL semantics, so I ignore whether it is
applicable to other implementations. PAL uses an "abnormality" predicate
to point out whether inertia is applied or not to a given fluent. The
solution consisted in replacing all conjunctions and disjunctions
(including those derived from the quantifiers) by their "shortcircuit"
versions. For instance, shortcircuit disjunction || in a causal rule
like:

(A || B) causes C

is interpreted so that whenever any of the disjuncts (A, B) persists
true, the rule is not applicable. In the example with `above', this
behavior was crucial. Assume that on(1,5) persists true. Then, the rule 

  on(1,5) || exists C (....) causes above(1,5)

is not applicable and so, above(1,5) persists. Since the rule is not
applicable, above(1,5) does not depend now on above(2,5), above(3,5),
etc, and the cycles are removed.

----- About Michael's solution for inertial above -----

Michael:
> Here I believe is the root of the problem. For you inertia 
> seems to be something which really (physically) affects the fluent.

Yes, this is my particular goal. I'm interested in representing whether
a fluent has persisted or, instead, has been "recomputed". If you look
at PAL output, you'll see that only recomputed facts are displayed in
the narratives.

Still, I think that even when you don't care about that, a programmer
should be able to deal with above as inertial. I prefer, for instance,
your "redundant" solution. I would prefer that the translator
action-language -> logic-program decided whether to remove such a
redundance, rather than forcing the programmer to add an explicit clause
saying that above is noninertial. 

The difference of your solution w.r.t. PAL is that you use a default
instead of quantifiers. Your default, when applied, disables inertia for
the effect fluent. I think that the need of defaults like this (which
are not available in PAL) are perhaps more clear when we want to solve
the qualification problem, for instance. But this is related to the next
part of the mail.

----- About the relation to [Baral&Lobo97] -----

>From your examples, it seems that one of the reasons for using "defined
fluents" is to apply them as abnormality predicates, i.e., exceptions to
a particular default (is this right?). This can be used, for instance,
to solve the qualification problem (which studied in [Baral&Lobo97]).

Example:

  normally switch_on causes light

We can add the defined, noninertial fluent "abnormal_lamp", encoding the
default as:

  h(light,T+1) :- o(switch_on,T), not h(abnormal_lamp,T).

Q6: should we consider abnormal_lamp as a "first-class" fluent, i.e.,
should this fluent be taken into account in the states of our transition
diagram?

A different solution is using B* labelled defaults

  d1: normally switch_on causes light

plus an "implicit" abnormality predicate ab(d1,T) hidden w.r.t. the
"high-level" programmer

  h(light,T+1) :- o(switch_on,T), not ab(d1,T).

This is practically the same as before, but it seems to suggest that
ab(d1,T) should not be part of our transition system. Besides, under my
point of view, it is a better solution, because the actions-programmer
does not have to define an abnormality predicate each time he/she wants
to build a defeasible rule.

In [Baral&Lobo97], 2 abnormality predicates were used. If L is a fluent
literal, we have (adapting the notation):

 ab1(L,T): meaning that some "defeasible" causal rule has fixed -L as
effect at time T. It is just used as exception to inertia of
h(L,T).

 ab0(L,T): meaning that some "strong" causal rule has fixed -L as
effect at time T. It is used as exception both to inertia and to
any defeasible rule whose effect is L. 

Example:
  
  "switch_on normally causes light" =
  h(light,T+1) :- o(switch_on,T), not ab0(light,T).

  "-power causes -light"=
  -h(light,T+1)  :- -h(power,T).
  ab0(light,T+1) :- -h(power,T).

I think this solution is even more transparent for the
actions-programmer, since it does not require explicit labels for the
defaults. It seems that labels should provide more expressivity but:

Q7: is there any example where B* explicit labels are more interesting? 

Michael:
> One of the problems is that their translation to logic programs 
> looks somewhat strange to me now. 
> (Chitta may remember a rational for using two ab's and for having
> the same ab's in the bodies of different defaults, etc).

The answer is in footnote 8 at [Baral&Lobo97]: in fact, you had
suggested them a variation where one of the abnormals "ab0(F,T)" could
be actually replaced by "not -holds(F,T)". After doing that, the result
is exactly the formulation you did for "inertial above"!

> h(F,T+1) :- h(F,T),
>             not ab(d1(F),T),
>             not ~h(F,T+1). 
> 
> ~h(F,T+1) :- h(F,T),
>              not ab(d2(F),T),
>              not h(F,T+1). 
> 


======

Date: Fri, 11 Jan 2002
From: Michael Gelfond
To: Pedro Cabalar

thanks for the message. Below is a  reply to its first part.
I promise to give a more 'complete' response
after Jan 15th (the closest submission deadline). 


Pedro: 
To understand the motivation of my doubt, let me put a simpler example
with another fluent. Consider the typical lamp circuit where `light' is
true iff 2 switches are closed. The "usual/traditional" formulation of
this is with 3 regular fluents (light, sw1, sw2) and rules like:

sw1 ^ sw2 causes light	(1)
-sw1 causes -light	(2)
-sw2 causes -light	(3)

Treating light as a defined fluent is also possible: after all, the
truth of light is completely "defined" by sw1 ^ sw2. Then, we can
"remove" (2) and (3), and declare light as non-inertial and false by
default.

Now, extrapolating your comments about above to this use of light:

Q1: why is this 2nd formulation of light "more useful" or "more
elegant"?

MICHAEL.
I don't think it is. 
But I of course would not view 'light' as a 
defined fluent. (You apparently feel that it is not - otherwise
I cannot explain your use of `` `` over defined.)

Normally I decide which fluents are 'defined' and which are not
in the very beginning of the process of formalization - before
I seriously think about representing effects of actions.

The first question I ask myself when I need to formalize some domain
typically is 
``What are the objects of my domain and what is a minimal set 
of relations between these objects (i.e. minimal set of fluents) 
which completely characterize the state of this domain?" 

In the case of blocks world this can be either ON or ABOVE but not
both - due to my minimality requirement.

In the case of electrical circuits the objects will be switches, bulbs,
etc and fluent will be switch positions (sw1, sw2), bulbs states (lit(b1)), 
etc. 

Notice that at this stage I do not really look at the details
of the circuit  - my representation should work for
any circuit constructed from the corresponding elements. (As a result
I would not even know about the dependency between the two switches and the
light you use in you example.)  In general the state of a bulb is 
determined by a variety of factors and I'll try to make my representation 
sufficiently general to  reflect this fact and to allow addition of new 
info on the subject. 

As a result at this stage I do not have defined fluents.

I hope that this explains why I will not define 'light' as defined
by the switches. 

After the notion of state is defined I start
working on constructing the corresponding action description.
Now I have my transition diagram. 
(Usually at this stage I still have no defined fluents but there
are exception - see (*) below). 

The defined fluents appear if I want the agent to reason about
properties of my objects which do not belong to a minimal set
selected for describing states of the domain. That is when
I define ABOVE. Recall that at this point my transition diagram is 
already defined! I do not need to worry about the inertia axiom anymore.

Going back to your example: Replace your fluent 'light' by a new
fluent TWO - two switches are on. If you do that the first representation
will be very strange while the second will be perfectly clear and
elegant. But I'll think about adding this rule only after
the notion of state is fully defined. 
So what is elegant and what is not depends (at least in part) on the
meaning of the fluents ans laws, and not necessarily on formal
properties of representation.

(*)
Now I can explain why I may sometimes use defined fluents
in a process of constructing the transition diagram even 
though they are not parts of a state: assume that I have several 
causal laws of the form 'If two switches are ON and some Fi is true 
then Gi must be true' (Nothing real comes to mind but I hope it is o.k.)
Now I can introduce a defined fluent TWO just to facilitate
encoding of these laws. But it really has nothing to do with
the notion of state and with inertia - I am just introducing an
abbreviation. 


Pedro:

Now the programmer would have 2 possibilities to encode the same
scenario. In fact, there is a 3rd possibility since we could assume
light true by default and handle causal rules (2) and (3), removing (1)
instead.

Michael:

But you see - I am talking about real circuits! Assuming that
light is normally lit is as strange as assuming that birds
are normally eagles. In some areas such assumptions maybe o.k.
and if your formalization is restricted to such cases using
the default maybe fine. But not in general!

Pedro:

Q2: which should be the criterion to decide when a fluent must be
defined instead of inertial?

See above

Q3: which is the criterion to decide the default value of a defined
fluent?

Michael: 

I'd normally use the default value your fluent has in the domain.
Consider for instance a fluent 

'just_moved(B)' which is true at T if block B was moved at T-1.

The corresponding causal law will be

put(B,C) causes just_moved(B)

The fluent is of course non-inertial with the default value false.

Is it of any help or I am just misunderstanding your questions?

PEDRO:

I understand that defined fluents are interesting, but for me, it would
be simpler if they were only used when the fluent is non-inertial "by
nature". A better example could be the one in the new paper about C+,
where something is said about positions of pieces on a moving belt.

MICHAEL:

Guilty. I didn't read it yet. 

PEDRO.

Now, coming back to above, if I were an actions-programmer I would first
wonder whether above is inertial by nature or not. I think you've both
agreed in that above "can be" inertial. In other words, it is not
clearly non-inertial. Then, at a first sight, I would not see any reason
to remove inertia for above:

MICHAEL. When I decide to make ABOVE a defined fluent 
(when I even start thinking about ABOVE at all) I am already done
with constructing my transition diagram and therefore I do not think
about it being inertial or otherwise.


PEDRO.
Q4: which is the difference of above (w.r.t. light) that points out that
it should be treated as a defined fluent?

Michael:
SEE ABOVE.

PEDRO:
My guess is that the difference is due to a "technical" problem and not
to the nature of fluent above in the blocks domain.

The informal definition of above is something like:

  "above(B,L) is true iff either B is on L or it is on another block C
such that, in its turn, above(C,L)"

This definition involves using an existential quantifier. In classical
logic, we'd have that above(B,L) should be equivalent to:

  on(B,L) v exists C (block(C) ^ C!=B ^ above(C,L))	(4)

but, when moving to a dynamic scenario, the equivalence should be
replaced by causal rules where above becomes the effect:

  (4) causes above(B,L)		(5)
  -(4) causes -above(B,L)	(6)

However, using a logic programming style, quantification is not needed:

  above(B,L) :- on(B,L).
  above(B,L) :- block(C), C!=B, on(C,L), above(C,L).

provided that above is false by default

  -above(B,L) :- not above(B,L).

Now, when moving to a dynamic scenario, this last rule enters into a
conflict with inertia:

  h(above(B,L),T+1) :- not -h(above(B,L),T).
  -h(above(B,L),T+1) :- not h(above(B,L),T).

So, the actions-programmer must be aware of this problem, and declare
above as non-inertial to avoid it. This is what I mean by saying that the
reason for removing inertia is "technical".

MICHAEL. 
All you are saying so far is correct and all I can say in response is -
I was not at all thinking in this way. I hope the arguments above
convince you of that. If not please keep pressing me for better answers.

I'll answer to the rest of your message a little later.

======

Date: Wed, 13 Feb 2002
From: Vladimir Lifschitz
To: Pedro Cabalar

This is a brief comment on your last message to TAG.  You asked, "Which
should be the criterion to decide when a fluent must be defined instead
of inertial?"  This question seems to presuppose that, for any fluent
that we introduce in a formalization of an action domain, we have two
choices: either define it in terms of other fluents or postulate inertia
for it.

It seems to me that there can be cases when we don't treat a fluent as
"defined" (or "statically determined," in the terminology of C+), but
don't introduce the inertia assumption for it either.  In your example
of a lamp controlled by two switches, you describe the system by the
causal laws

sw1 ^ sw2 causes light	(1)
-sw1 causes -light	(2)
-sw2 causes -light	(3)

We do need the inertia assumption for sw1 and sw2, but assuming inertia
for light would be redundant.

I think of inertia as the simplest among possible assumptions about the
default behavior of a fluent.  There are many systems in which other
assumptions of this kind are needed (pendulum, buzzer, conveyor belt,
savings account).  Your rules (1)-(3) are so strong that adding any
default assumption about light to these rules wouldn't change anything.
The most economical approach is to add nothing!

What are your thoughts about this?

======

Date: Thu, 14 Feb 2002
From: Pedro Cabalar
To: Michael Gelfond and Vladimir Lifschitz

First of all, I'm afraid that I mostly have doubts and questions, rather
than answers. As I said before, I agree in the need for declaring default
values and noninertial fluents, something I would like to include in PAL.

After your mails, I think I understand better your positions.
Unfortunately, they seem to be different. In fact, it seems that each of
us has in mind a different degree of relevance for inertia (correct me
if I'm wrong in these observations):

----------
1- For Vladimir, inertia is just one more default and its application is
purely practical, and domain dependent. This means that inertia is used
when there is no other way of establishing the fluent value for the
current scenario. Thus, LIGHT and ABOVE are not considered inertial for
the scenarios we deal with.

Language C+ seems to be thought for adding inertia explicitly each time
we consider it is needed. For instance, C+ paper includes the example of
a circular moving belt:

(1) caused Loc(x)=(l mod 10+1) if Loc(x)=(l mod 10+1) & OnBelt after
Loc(x)=l
(2) caused Loc(x)=l if Loc(x)=l & ~OnBelt(x) after Loc(x)=l

Note that rule (2) is inertia, but only under condition ~OnBelt. 

In C+ a fluent can be inertial or not. If not, it can be "statically
determined" (defined). This usually means defining a default value. All
fluents are taken into account when representing transition diagrams.
For instance, fluent FRUSTRATED is statically determined, true by
default, and is represented in transition diagrams (Fig. 6). Another
example is fluent NATIONALITY with default value UK.

----------
2- Michael's point of view is to include inertia in some cases, even
when its application could be redundant. For instance, Michael considers
that LIGHT should be inertial, though ABOVE not. The decision criterion
is: choose the "primary" fluents for your transition system, avoiding
redundant relations (ABOVE is redundant w.r.t. ON) but only when they
don't talk about a different physical object. Fluent LIGHT is redundant
w.r.t. SW1 and SW2, but talks about a different object (the bulb) w.r.t.
the switches. In Michael's words, the intuition behind this criterion
is:

> my representation should work for
> any circuit constructed from the corresponding elements.

After that, you may decide to include "auxiliary" or "secondary"
fluents, in order to obtain a more compact representation. These defined
fluents should just be seen as abbreviations (or macros). Some examples
could be:
TWO_UP =def= SW1 & SW2
AUX(B) =def= CLEAR(B) & ON(TABLE,B)

Defined fluents do not appear in transition diagrams. Besides, their
implementation may deal with default values or not, but clearly, inertia
does not have anything to do with them. In a very strict sense, we
should not even consider them as fluents (they are not system
properties).

----------
3- Finally, this is how I see things. When I have to include a new
fluent I would like to think whether it is naturally (or physically, if
you prefer so) inertial or not. In other words, given fluent F, I would
ask:

  does the sentence "F has persisted (with value V)" make sense or not?

For instance, "LIGHT has persisted" makes sense. I can decide whether
the light persisted or was affected by the actions. So, for me, there is
no doubt that LIGHT should be inertial without regarding the particular
circuit we deal with.

"ABOVE has persisted" also makes sense. I can also say when a block
remains unaltered above another one, or instead, when it has been forced
to be so. To emphasize this idea, assume we want to avoid that block A
remains above block B for more than N situations. At a first attempt,
wouldn't you declare ABOVE as inertial in this case? In fact, in the
problem description, we are talking now about its persistence.
Furthermore, I would probably like to consider ABOVE as part of my
automaton. Ok, it is not a minimal relation among blocks, but it seems
that it is relevant to explain the transitions.

I agree in that things may become less efficient in this way, but this
is not my concern, yet. In other words, I would add inertia, unless it
can be completely disregarded. I think that this is easier for a
hypothetical programmer. Noninertial fluents could be things like
EXPLOSION or BANG (i.e., momentary "events"). In fact, actions can be
seen as special noninertial fluents (their only particularity is that
they are externally provided).

My initial questions were in this direction: if ABOVE had to be
inertial, how should we implement this? Michael's answer is something
like
	(3): default ~ABOVE(A,B) if true
        ABOVE(A,B) if ON(A,B)
       	ABOVE(A,C) if ON(A,B), ABOVE(B,C)
As default (3) overrides inertia, this is almost identical to define
ABOVE as noninertial: but it is not the same. Generally, we could change
the antecedent of (3) to decide when this default overrides inertia or
not. In other words, when a default is not applicable, now fluent
remains being inertial. Note that a simple translator from B* to LP
could detect that inertia is not needed after all, but the programmer
still sees ABOVE as inertial.

I provided a different solution relying on quantifiers and on the fact
that PAL may decide which ground atoms ABOVE(a,b) have been caused or
have persisted instead. To put an example, if you move a block ontop a
stack, the facts for ABOVE for the rest of blocks in the stack are not
shown among the relevant facts of the successor state (they remain
unaltered).

Finally, consider now the example of locations in a moving belt.
"LOC(x)=L has persisted" has a meaning: objects may persist in a
position. So, for me, location is inertial. It seems that adding the
rule:
	LOC(x):=previous(LOC(x)) mod 10 + 1 if ONBELT
should suffice, while (implicit) inertia would do the rest (when
~ONBELT). Thanks to this discussion, I have now some ideas on how to
build something like this in PAL. 

This solution seems better than "qualified inertia", i.e., rule (2).
What would happen to (2) if we allow now multiple motion laws (PENDULUS,
LINEAR_MOVING, etc) for the object? shouldn't we have to rewrite (2) by
adding more explicit qualifications for inertia?