## Paolo Liberatore## The Complexity of the Language A |

The article mentioned above has been submitted to the Electronic
Transactions on Artificial Intelligence, and the present page
contains the review discussion. Click for
more explanations and for the webpage of the
author, Paolo Liberatore.
## Overview of interactions
Q1.
Paolo,
What is the relationship (or is there any) between your results and the
results by Nebel and Bäckström would seem to be related to plan validation?
A
A1.
This is an interesting question. In general, entailment in reasoning
about actions languages such iff the goal is true after the execution of the
sequence (regardless of the initial state).
G
As for the specific problems of consistency (or entailment) in
Of course both problems (entailment and plan validation) are coNP complete, so one can be reduced to each other, but I do not think there is a "simple" and intuitive way to do that for entailment in A and plan validation as defined by Bäckström and Nebel. Q2.
Paolo, I have two questions/comments. First,
Your proof of intractability of general A2.
Yes. Indeed, NP completeness is due to the fact that the possible
initial states are exponentially many. If there is only a constant
(small) number of unspecified fluents in the initial state, then the
number of initial states is constant (in complexity theory, if
2 is also a constant). The same holds also
when there is a non-constant number of unspecified fluents in the
initial state, but no effect proposition have them as preconditions.
^{ c} Q3.
My other question is,
Did you have a look at extensions of A3.
I have not studied the complexity of the extensions of , namely
A for consistency
and Sigma_{2} for entailment.
The complete knowledge of the initial state
should reduce the complexity to NP and coNP, respectively. The proposal
by Bornscheuer&Thielscher should be as easy as basic Pi_{2}
(NP and coNP complete). About non-deterministic actions: I had a look to
A
(proposed by Kartha&Lifschitz), and it seems to me that it should be
AR_{0} also. A complete knowledge of the inital state
does not help, since the domain description can always contain propositions
such as Sigma_{2} . There are other formalizations of
non-deterministic actions, but I have not analyzed them yet.
A releases F Q4.
Paolo,
Your construction in section 4 seems to be similar to the entailment
method PMON, but differs from it in an interesting way. In your case,
if the action to node i ,
you introduce for each fluent j the clauses
F_{o}
expresses that
c^{ j}_{0} F_{0} has to change from node to node i ,
whereas the effect proposition merely assigns its new value, regardless
of whether it had it before or not. (I hope I got this right).
j Now, this is similar to how occlusion is used in PMON, except that occlusion only states a "permission" to change. (Occlusion is the same as the "release" operator later adopted by Lifschitz). Therefore, the counterpart of the first two clauses above are the "nochange" axioms, which in your notation would be
notequal x^{ i}_{o} then x^{ j}_{o} ".
For things to come out right, in PMON one has to minimize occlusion
(the c^{ j}_{o} propositions, in your notation) before applying the nochange axioms.
In your case there does not seem to be any corresponding partitioning of
the axioms for the purpose of completion.
c It is clear that the Clark completion can not be directly applied to the PMON formulation, or at least that some preliminary transformation would be necessary. On the other hand, occlusion is instrumental for expressing nondeterminism; it allows one to say that a fluent may or may not change a value. Your formulation does not seem to lend itself to expressing nondeterminism in that way. Therefore, I wonder whether you see any possibility of modifying the construction in your section 4 along the lines of occlusion and PMON? This might be a way of finding some restricted cases of nondeterministic scenarios whose computational properties are not too bad. Also, could you comment on how these two formulations relate in other respects, for example, if you see any difference from a computational point of view?
PMON was introduced in "Features and Fluents"
A4.
I will answer to the last question first. From a computational point
of view, entailment under completion is "only" coNP compete, since the
completion of a set of clauses is a propositional formula of polynomial
size. On the other hand, circumscriptive entailment is
Since PMON requires a minimization of the occlusion predicate, it should
be harder than the completion formulation of
Q5.
Section 6 in the article addresses domain descriptions in which some
states are not reachable from the initial state. I think the modification
of the semantics of H L
Intuitively, the model should be the same. But the reachable states
semantics now considers Psi_{D}(I, {H, L} )
Generally, my feeling is that in order to solve the problem that your
example highlights (and I think it is a problem) you cannot do in the
language of A Also, on page 5 you write:
This reduction seems not to go through for your modified semantics of section 6. The rest (i.e. the main part of the paper) is just perfect as far as I can see. And it was a pleasure to read the paper.
A5.
You wrote:
You are right. In this case, the semantics does not capture the intuitive meaning of the domain description. You also wrote:
The intended semantics for the actions in Psi_{D}(I, sigma) A sigma it is possible
to express propositions like " I I {H, L}
(If there is a proposition " Psi I I Psi
Analyzing the problem of unreachable states, my first idea for solving it was:
an interpreted structure D - each action is executable in any state reachable from
*sigma* - each value proposition is satisfied (as in the old semantics of
)A
However, I discarded this idea, and instead I defined the one that is presented in the paper. Note that this semantics, although correct wrt your example, suffers from some drawbacks. For example, if for any state there is an action not executable there, then the domain description is inconsistent. Consider for example the case
F J F I {F} I
I I0 I0 FI - if
*F**were*executed the result would be a state that implies*F* is executable in the initial state, and the resulting state implies*F**F*
I0 I0 I
I discarded the first semantics (preferring the one of the paper) because
the impossibility of executing an action in the initial state (or any other
state) may influence the set of the possible initial states. The semantics
of the paper first determines the set of possible initial states, and only
then determines which states are reachable from them. However, in the example
of the counter, the initial state because
the action I
Perhaps the discarded solution is better then the chosen one. The problem is
left open. A minimal requirement for a semantics that takes into account
the reachability of states is that if Psi_{D} You also wrote:
Indeed, this property holds only for the classical semantics of
Q6.
Paolo, Here are some questions and suggestions about details in your article:
page 16, line -14: What about the case
¬ AG
page 17, line 8: This case is similar to the IJCAI '97 paper by myself and
Marcus Bjäreland page 19, line 3: An inconsistent domain description could never entail the same propositions as a consistent one. What is the intended meaning in this case?
A6.
Dear Thomas, Thank you for your suggestions. About your observations:
In this case
The original domain description implies (under the semantics of reachable states) the same propositions of the modified one (using Gelfond & Lifshitz's semantics). The point is that I am using two entailment relations for the original domain description and modified one. Paolo
## Background: Review Protocol Pages and the ETAIThisReview Protocol Page (RPP) is a part of the webpage structure
for the Electronic Transactions on Artificial Intelligence, or
ETAI. The ETAI is an electronic journal that uses the Internet
medium not merely for distributing the articles, but also for a
novel, two-stage review procedure. The first review phase is open
and allows the peer community to ask questions to the author and
to create a discussion about the contribution. The second phase -
called refereeing in the ETAI - is like conventional journal
refereeing except that the major part of the required feedback
is supposed to have occurred already in the first, review phase.
The referees make a recommendation whether the article is to be accepted or declined, as usual. The article and the discussion remain on-line regardless of whether the article was accepted or not. Additional questions and discussion after the acceptance decision are welcomed. The Review Protocol Page is used as a working structure for the entire reviewing process. During the first (review) phase it accumulates the successive debate contributions. If the referees make specific comments about the article in the refereeing phase, then those comments are posted on the RPP as well, but without indicating the identity of the referee. (In many cases the referees may return simply an " accept" or " decline" recommendation, namely if sufficient feedback has been obtained already in the review phase).
This debate is moderated by Erik Sandewall. |