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
What is the relationship (or is there any) between your results and the results by Nebel and Bäckström [j-aij-66-125] on the complexity of plan validation and temporal projection? Since basic A characterizes updates to the current state, it is at least related to the STRIPS-based framework of classical planning, and deciding the consistency of a set of statements in A would seem to be related to plan validation?
This is an interesting question. In general, entailment in reasoning about actions languages such A is strictly related to (deductive) plan validation. Indeed, a plan is a sequence of actions, and it achieves a goal G iff the goal is true after the execution of the sequence (regardless of the initial state).
As for the specific problems of consistency (or entailment) in A and plan validation as defined by Bäckström and Nebel, I think there are substantial differences. Let me explain in short what is the source of intractability of these problems. In A the NP-hardness is due to the incomplete specification of the initial state: one has in general to consider an exponential number of possible initial states. The problems of temporal projection and plan validation analyzed by Bäckström and Nebel are intractable because the possible sequences of actions can be exponentially many. The initial state is fixed (and fully specified), but, in order to verify if a fact is true after an event (or to verify whether a goal is achieved), one has to consider all the possible sequences of actions that respect a given ordering.
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.
Paolo, I have two questions/comments. First, Your proof of intractability of general A relies on the construction of effect propositions all of whose conditions are unspecified in the initial state. It therefore seems that even if the initial state is incomplete, if only the number of (relevant) unspecified fluents is small then both consistency checking and entailment is still polynomial, am I right?
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 c is a constant, then 2 c 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.
My other question is, Did you have a look at extensions of A which support nondeterministic actions? Does tractablity in case of complete initial states still hold?
I have not studied the complexity of the extensions of A in details. At a first look, it seems easy to prove that the dialects that include concurrent actions (the proposals by Baral&Gelfond and Li&Pereira) are more complex than basic A , namely Sigma2 for consistency and Pi2 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 A (NP and coNP complete). About non-deterministic actions: I had a look to AR0 (proposed by Kartha&Lifschitz), and it seems to me that it should be Sigma2 also. A complete knowledge of the inital state does not help, since the domain description can always contain propositions such as A releases F . There are other formalizations of non-deterministic actions, but I have not analyzed them yet.
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 Ak goes from node i to node j , you introduce for each fluent Fo the clauses
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
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" [mb-Sandewall-94]; the definition is in section 11.4.3 and the assessment in section 11.6.3. Doherty described its reduction to circumscription in [c-ecai-94-401]. (Occlusion was introduced in 1989, [c-ijcai-89-894]).
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 Pi2 complete, thus harder.
Since PMON requires a minimization of the occlusion predicate, it should be harder than the completion formulation of A . On the other hand, PMON allows a correct formulation of non-deterministic actions, while completion does not. Right now, I do not see an easy way of extending the translation of section 4 without introducing an explicit minimization, thus increasing the complexity. Of course, this increase of complexity should not be considered bad, since languages with non-deterministic actions are surely harder (in the general case) than simple languages. I agree with you that extending the translation in the sense you pointed out should allow the identification of subclasses of the problem for which the computational complexity is only coNP, since it should be easier to find classes for which the minimazation policy can be replaced by a simpler completion.
Q5. Anonymous reviewer (21.11):
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
Intuitively, the model should be the same. But the reachable states
semantics now considers
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
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.
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
(If there is a proposition "
Analyzing the problem of unreachable states, my first idea for solving it was:
an interpreted structure
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
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
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
You also wrote:
Indeed, this property holds only for the classical semantics of
Here are some questions and suggestions about details in your article:
page 16, line -14: What about the case
page 17, line 8: This case is similar to the IJCAI '97 paper by myself and Marcus Bjäreland [c-ijcai-97-1447], where we require one negative precondition and one negative postcondition (which is of course equivalent, replacing true and false). You can probably add some nondeterminism here, retaining tractability, if you do not allow a precondition, the same way as we're doing it (you can then have a Horn postcondition).
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?
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.
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
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.
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.