|
Paolo LiberatoreThe 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. Erik Sandewall (11.7):
Paolo, 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? References:
A1. Paolo Liberatore (14.7):
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. Q2. Michael Thielscher (22.7):
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? A2. Paolo Liberatore (24.7):
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. Q3. Michael Thielscher (22.7):
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? A3. Paolo Liberatore (24.7):
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. Q4. Erik Sandewall (28.7):
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]). References:
A4. Paolo Liberatore (30.7):
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
language of 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. Paolo Liberatore (24.11):
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
(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
Q6. Thomas Drakengren (24.11):
Paolo, 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? References:
A6. Paolo Liberatore (1.12):
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
|