Paolo Liberatore: The Complexity of the Language A.

[summary] [full text] [author]

[msg to moderator] [debate procedure] [copyright]

Additional reviewing information: Minor details noticed by reviewers.

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  Sigma₂  for consistency and  Pi₂  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  AR₀  (proposed by Kartha&Lifschitz), and it seems to me that it should be  Sigma₂  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  A_k  goes from node  i  to node  j , you introduce for each fluent  F_o  the clauses

	x jo <- c jo,   ¬x io
	x jo <- ¬c jo,   x io

Furthermore, each effect proposition, for example

Ak causes F0 if F1, F2

is mapped into a clause

c j0 <- x i1,   x i2,   ¬x i0

The last literal is needed because  c ^j₀  expresses that  F₀  has to change from node  i  to node  j , whereas the effect proposition merely assigns its new value, regardless of whether it had it before or not. (I hope I got this right).

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

	c jo <- x io,   ¬x jo
	c jo <- ¬x io,   x jo

which together say "if  x ⁱ_o  notequal  x ^j_o  then  c ^j_o ". For things to come out right, in PMON one has to minimize occlusion (the  c  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.

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  Pi₂  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  A  as proposed in that section does not allow to solve the problem of unreachable states. Consider the situation where you replace the observation that  H  and  L  are initially both false by what you observe after two steps, i.e. replace the two `initially' propositions by

	H after I;I
	¬ L after I;I

Intuitively, the model should be the same. But the reachable states semantics now considers   {H, L}   to be a possible initial state. This is because  Psi_D(I,  {H, L} )  is undefined there, hence both value propositions are weakly true. I.o.w., you get back to the orginal  A  semantics you wanted to avoid.

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 . What you need is a notion such as ``action  A  is executable if ...''.

Also, on page 5 you write:

``to prove that  D  entails  F  after  A1;...;Am  it suffices to prove that  D u ¬ F after A1;...;Am  is inconsistent.''

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:

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  A  as proposed in that section does not allow to solve the problem of unreachable states. Consider ...

You are right. In this case, the semantics does not capture the intuitive meaning of the domain description.

You also wrote:

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 . What you need is a notion such as ``action  A  is executable if ...''.

The intended semantics for the actions in  A  is: all actions are executable in any state. When  Psi_D(I, sigma)  is undefined, the choice of the original semantics of  A  is that the whole domain description is inconsistent. What I meant is instead that  A  is not executable in  sigma . In this sense, in  A  it is possible to express propositions like " I  is executable if", but only in a non-intuitive way: in the example of the counter  I  is not executable in   {H, L}  . We need an appropriate semantics for such propositions.

(If there is a proposition " I  is executable if ..." there is no need to make  Psi  defined on  I  in states in which  I  is not executable. As a result, there is nothing that prevent us from using the indefiniteness of  Psi  to infer the non-executability of actions. The drawback is that this definition is less intuitive.)

Analyzing the problem of unreachable states, my first idea for solving it was: an interpreted structure   (sigma, Phi)   is a model of  D  if and only if

1. each action is executable in any state reachable from  sigma 
2. 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

	I is executable if F
	J is executable if ¬ F

This domain is inconsistent, because in the initial state in which  F  is true the action  J  is not executable, while in the initial state in which  F  is false the action  I  is not executable. In such cases, it seems possible to infer that, if the initial state is   {F}   then the first action executed is  I . For instance, if there is also a proposition

initially F

the first executed action is  I . The semantics of  A  does not infer any statement about the execution of actions (in  E  and similar languages there are propositions like " I at 0 " or " I happens at 0 "). A statement like " F after I " may be interpreted in two ways:

1. if  F  were executed the result would be a state that implies  F 
2.  F  is executable in the initial state, and the resulting state implies  F 

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   {H, L}   must be rejected because the action  I  is not executable from there. This is why the semantics of the paper fails.

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  D  does not have "executable" propositions (or, if  Psi_D  is total) then the new semantics must coincide with G&L's semantics. The semantics of the paper (and the one of the previous paragraph) has this property (clearly, this is not enough.)

You also wrote:

Also, on page 5 you write:

``to prove that  D  entails  F  after  A1;...;Am  it suffices to prove that  D u ¬ F after A1;...;Am  is inconsistent.''

This reduction seems not to go through for your modified semantics of section 6.

Indeed, this property holds only for the classical semantics of  A  (this property is used for proving the complexity of the entailment in the classical semantics of  A ).

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  A causes G ,  A causes ¬ G  ? That would be inconsistent. What is the intended meaning in this 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:

page 16, line -14: What about the case  A causes G ,  A causes ¬ G  ? That would be inconsistent. What do you mean in this case?

In this case  Psi_D  is not total. This can be verified in polynomial time (Lemma 1).

page 19, line 3: An inconsistent domain description could never entail the same propositions as a consistent one! What do you mean 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