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

N:o Question Answer(s) Continued discussion
1 11.7  Erik Sandewall
14.7  Paolo Liberatore
 
2 22.7  Michael Thielscher
24.7  Paolo Liberatore
 
3 22.7  Michael Thielscher
24.7  Paolo Liberatore
 
4 28.7  Erik Sandewall
30.7  Paolo Liberatore
 
5 21.11  Anonymous reviewer
24.11  Paolo Liberatore
 
6 24.11  Thomas Drakengren
1.12  Paolo Liberatore
 
 

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:

j-aij-66-125Bernhard Nebel and Christer Bäckström.
On the computational complexity of temporal projection, planning, and plan validation. [abstract] [postscript] [bibtex]
Artificial Intelligence, vol. 66 (1994), pp. 125-160.

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
   x jo <- c jo,   ¬x io  
   x jo <- ¬c jo,   x io  
Furthermore, each effect proposition, for example
   Ak causes F0 if F1F2  
is mapped into a clause
   c j0 <- x i1,   x i2,   ¬x i0  
The last literal is needed because  c j0  expresses that  F0  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 io  notequal  x jo  then  c jo ". 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:

c-ecai-94-401Patrick Doherty.
Reasoning about Action and Change using Occlusion. [postscript]
Proc. European Conference on Artificial Intelligence, 1994, pp. 401-405.
c-ijcai-89-894Erik Sandewall.
Filter Preferential Entailment for the Logic of Action in Almost Continuous Worlds.
Proc. International Joint Conference on Artificial Intelligence, 1989, pp. 894-899.
mb-Sandewall-94Erik Sandewall.
Features and Fluents. The Representation of Knowledge about Dynamical Systems.
Oxford University Press, 1994.

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  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   {HL}   to be a possible initial state. This is because  PsiD(I,  {HL} )  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  PsiD(Isigma 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   {HL}  . 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   (sigmaPhi)   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 
(The choice of the semantics of the paper is the first one, while the discarded one uses the second one.) Statements like " I at 0 " or " I happens at 0 " means that  I  is executed in the time point 0 (and thus the action must be executable in that state).

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   {HL}   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  PsiD  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:

c-ijcai-97-1447Thomas Drakengren and Marcus Bjäreland.
Reasoning about Action in Polynomial Time.
Proc. International Joint Conference on Artificial Intelligence, 1997, pp. 1447-1453.

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  PsiD  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


 

Background: Review Protocol Pages and the ETAI

This Review 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.