Eyal Amir Point-Sensitive Circumscription.

c-fcs-98-56   [original] [abstract]

[mail to author]   [mail to moderator] [debate procedure] [copyright]

Q1. Erik Sandewall:

I have questions about your section 6, "Applying Point-Sensitive Circumscription to Theories of Action", which I can not make sense of. You first review the formulation of PCM (Prototypical Chronological Minimization) in pointwise circumscription, and then write (p. 71):

We do not claim that Point-Sensitive Circumscription can formalize the entire K-IA ontological class, but that it can take you farther than Pointwise circumscription can.

Let me briefly review the relevant aspect of Features and fluents, in order to put what follows into context. The K-IA ontological class allows for scenarios with nondeterministic actions, actions with extended duration in time and internal structure, and all combinations of prediction and postdiction. It does not model causality or other forms of ramification, nor concurrency, etc.

For this K-IA class, we have studied a number of entailment methods, each of which can then be reexpressed in e.g. pointwise circumscription. PCM is one of those entailment methods. Each of them is defined in terms of preference criteria or other selection criteria on models, and it is these criteria that may be translated e.g. to circumscription as a way of proceeding towards an implementation. For each entailment method, there is also an assessment of range of applicability. This assessment is model-theoretic, and is independent of the choice of implementation method.

In this framework it is perfectly reasonable, as you do, to evaluate a variant of circumscription with respect to whether or not it is capable of expressing a particular entailment method, or even a collection of them. This makes much more sense than analyzing circumscription variants directly in terms of test examples, since then so much depends on the choice of axiomatization.

Though I agree with your methodology up to that point, I do not understand the concrete case where it is applied. You only discuss how PCM is rendered in variants of circumscription, but Doherty has already shown how to express PCM in pointwise circumscription. If your variant of circumscription is able to handle more examples correctly within the range of K-IA, it could therefore only be because it were an inaccurate rendering of PCM.

Also, although the range of applicability of PCM is only a limited part of K-IA, there are other entailment methods such as PMON which are correct for K-IA, and which can also be expressed in pointwise circumscription following Doherty. This makes it even more strange how point-sensitive circumscription can do something that pointwise circumscription can not, with respect to the K-IA class.

You also discuss a simple case of ramification using the duality between the dead and alive properties. This of course is not within K-IA, as you also observe. However, there are certainly known methods that handle such simple ramifications (as well somewhat less trivial ones) correctly and that have been expressed or re-expressed using pointwise circumscription.

Could you help me understand your contribution in these respects?

A1. Eyal Amir (2.3):

Dear Erik. Thank you much for your insightful comments. You write

... The K-IA ontological class allows for scenarios with nondeterministic actions, actions with extended duration in time and internal structure, and all combinations of prediction and postdiction. It does not model causality or other forms of ramification, nor concurrency, etc. ... For this K-IA class, we have studied a number of entailment methods, each of which can then be reexpressed in e.g. pointwise circumscription. PCM is one of those entailment methods. .... In this framework it is perfectly reasonable, as you do, to evaluate a variant of circumscription with respect to whether or not it is capable of expressing a particular entailment method, or even a collection of them. ... Though I agree with your methodology up to that point, I do not understand the concrete case where it is applied. You only discuss how PCM is rendered in variants of circumscription, but Doherty has already shown how to express PCM in pointwise circumscription. If your variant of circumscription is able to handle more examples correctly within the range of K-IA, it could therefore only be because it were an inaccurate rendering of PCM.

[For the reader: PCM is defined roughly as follows (see [s-Gabbay-94-999] for more details): Interpretations  I «_pcm I'  iff  M = M'  (the objects are the same) and there is  t₀  s.t.

1. for all  t < t₀ ,  R(t) = R'(t)  (the fluents are identical in  I  and  I'  before  t₀ ) and
2.  breakset(I, t₀) c breakset(I', t₀)  (the fluent value changes from  t₀-1  to  t₀  in  I  are a subset of the appropriate changes in  I' ).

Pointwise Circumscription (I shall abbreviate it here Pt-Circ) is a special case of Point-Sensitive Circumscription (abbreviated here Pt-Sens), and so PCM can be expressed in Pt-Sens the same way [c-ictl-94-82] shows with Pt-Circ. However, Doherty and Lukaszewicz showed that Pt-Circ expresses PCM only for the ontological class Kp-IAex, in which no observations later than time  t = 0  are allowed. The example I give in the paper shows that Pt-Sens may be able to express PCM outside Kp-IA (notice that the example I give falls within K-IA, as the "ramification" is accounted for by domain constraints (observations for time later than 0)). I did not prove a higher lower-bound, though. I just showed cases outside Kp-IA where Pt-Circ fails and Pt-Sens succeeds.

You then write

Also, although the range of applicability of PCM is only a limited part of K-IA, there are other entailment methods such as PMON which are correct for K-IA, and which can also be expressed in pointwise circumscription following Doherty. This makes it even more strange how point-sensitive circumscription can do something that pointwise circumscription can not, with respect to the K-IA class.

My claim was that we may be able to avoid filtering (the way [c-ictl-94-82] does) in grasping K-IA. I did not prove that either. Future work?...

You also discuss a simple case of ramification using the duality between the dead and alive properties. This of course is not within K-IA, as you also observe. However, there are certainly known methods that handle such simple ramifications (as well somewhat less trivial ones) correctly and that have been expressed or re-expressed using pointwise circumscription.

Although the simple example I gave is within K-IA, I support the claim that Pt-Sens can treat some forms of ramification (a first hint at that was made in a paper of mine in NRAC'97). I am not aware of previous expressions of ramifications using Pt-Circ and will be happy to get some pointers.

Eyal

References:

C1-1. Patrick Doherty (8.3):

Hi Eyal,

A few comments regarding your paper and then a few regarding your comments to Erik. First, your paper:

First off, I think your notion of Pt-Sens circumscription is an interesting technical result, but wonder about its widespread applicability (see comments below). The "counter-intuitive example" (your description) you provide as a reason for proposing Pt-Sens circumscription would appear to be more counter-intuitive in the way the policy is set up rather than in the result. The reason for introducing pointwise circumscription in the first place is so that one can vary parts of an extension while fixing other parts. To introduce a policy where you vary the whole extension of the predicate you are minimizing strikes me as being a bit extreme. But, I suppose one could find more intuitive "counter-intuitive" examples to prove your case, which do not violate one's sense of proper use of pointwise circumscription (if there is such a thing!)

You also state in section 7 that

pointwise circumscription is sufficient if we restrict ourselves to deterministic actions and to cases in which there are no domain constraints.

Well, the K-IA class deals with non-deterministic actions just fine and in the case of PMON, or its extension PMON(RC) discussed below, where ramification can be dealt with using a combination of domain and dependency constraints, syntactic characterizations for both can be defined using pointwise circumscription. Although it is computationally more feasible to choose a different type of circumscription. You can check my ecai94 paper or the paper by gustafsson and myself in kr96. In fact, I think you attended the ijcai97 workshop where I demonstrated PMON(RC).

In conclusion, I enjoyed the first part of the paper, but I'd think the second part regarding applications to logics of action and change needs some more work (By the way, I have only read your workshop draft, so you may have fixed things since.)

Now some comments about your and Erik's interaction:

Pointwise Circumscription (I shall abbreviate it here Pt-Circ) is a special case of Point-Sensitive Circumscription (abbreviated here Pt-Sens), and so PCM can be expressed in Pt-Sens the same way [c-ictl-94-82] shows with Pt-Circ. However, Doherty and Lukaszewicz showed that Pt-Circ expresses PCM only for the ontological class Kp-IAex, in which no observations later than time  t0  are allowed.

The point is that PCM is limited to the class Kp-IAex, and Pt-Circ was used to provide a syntactic characterization of PCM's minimization policy, not that Pt-Circ is inherently unable to represent classes which subsume Kp-IAex.

My claim was that we may be able to avoid filtering (the way [c-ictl-94-82] does) in grasping K-IA.

I did not prove that either. Future work?...

Why would you want to avoid filtering? And, if there is a legitimate reason, I would imagine you'd want to replace pointwise circumscription with a more computationally efficient policy than a generalization of generalized pointwise circumscription which is what Pt-Sens appears to be.

You also discuss a simple case of ramification using the duality between the dead and alive properties. This of course is not within K-IA, as you also observe. However, there are certainly known methods that handle such simple ramifications (as well somewhat less trivial ones) correctly and that have been expressed or re-expressed using pointwise circumscription.

Although the simple example I gave is within K-IA, I support the claim that Pt-Sens can treat some forms of ramification (a first hint at that was made in a paper of mine in NRAC'97). I am not aware of previous expressions of ramifications using Pt-Circ and will be happy to get some pointers.

In the KR96 paper by Gustafsson and myself, we introduce a straightforward technique to extend PMON, which is assessed correct for the K-IA class, so that it deals with a broad class of problems associated with ramification. This logic PMON(RC) subsumes K-IA. The minimization policy is practically the same as PMON and can trivially be defined using pointwise circumscription, although we use standard predicate circumscription (in fact predicate completion). In fact, we model both the stuffy room example from Winslett and the alive/walking example in the paper. There are many more examples that you can test using the VITAL tool which I demonstrated at IJCAI97.

regards,

Patrick Doherty

References:

This on-line debate page is part of a discussion at recent workshop; similar pages are set up for each of the workshop articles. The discussion is organized by the area Reasoning about Actions and Change within the Electronic Transactions on Artificial Intelligence (ETAI).

To contribute, please click [mail to moderator] above and send your question or comment as an E-mail message.