Keep negated static preconditions in logic program for grounding

[abcorrea]

In the logic program used for grounding, Tarski either (i) removes all negated preconditions, or (ii) keeps all negated preconditions. An intermediate approach would be to simply keep negated preconditions involving static predicates. This could have a positive effect because static predicates do not appear in the head of any rule and thus there is no way they could form a cyclic dependency via negated atoms, in the same time that it reduces the size of the final model by pruning trivially inapplicable actions. This would be still polynomial to compute (I think).

[miquelramirez]

Thanks for the feedback @abcorrea ,

one possible way to do this would be to have the static predicates to have associate "empty rules" of the form

:- not pred(X,Y,...).

where pred is the static predicate (detected via simple syntactic analysis of the input pddl) and X, Y would be the schema arguments.

Would that have the intended meaning, @gfrances ? Or you need to use - instead of not? I am reading clingo docs and I am confused :confused:

[abcorrea]

I think this does not work as we intend. This rule would mean "pred(X, Y, ...) has to be part of the model", but since pred is static, if pred(X, Y, ...) is true in the initial state, it will be in every model; and if pred(X, Y, ...) is not true, then it cannot ever be possibly true because no action produces any ground atom with predicate symbol pred (because it is static).

I guess the easiest way is to simply add these preconditions to the rules corresponding to actions and let gringo deal with them. When grounding, gringo will do a dependency analysis and will notice that these static preconditions do not appear in any head, so it will perform some optimizations over that.

Let me know if I got something wrong (which is very likely!)

[gfrances]

I think you're right about the semantics of the problem, augusto, but I am not sure about the polynomiality claims... why would it be polynomial? Looks like you can reduce a CSP to the problem of grounding a single action schema, even if all predicates are static and there is no negation at all?

[abcorrea]

I think we might be talking about different complexities (program vs data complexity). Could you have a look at Theorem 5.1 in "Complexity and Expressive Power of Logic Programming" (Dantsin et al. 2001)? As I understand it, the theorem says that Datalog with stratified negation (our case in this context) is P-complete considering data complexity and EXPTIME for program complexity.

[miquelramirez]

@gfrances if all the predicates (constraints) are binary, and there's no cycles in the causal graph, applying arc-consistency once over every pair of variables results in a globally consistent CSP. So that would be an example of a schema grounding CSP that is tractable. Datalog probably can be compiled into one of the tractable cases, perhaps?

@abcorrea seems to be pointing at a more general special case, but I am not sure what @abcorrea means by "program" vs "data" complexity? "time" and "space"?

[gfrances]

No, I meant that you can reduce any CSP to the problem of checking whether there is any reachable grounding of an (effect-free) action schema from an initial state given by the extensional relations of the CSP. But as augusto points out, this is irrelevant for a fixed domain. BTW Augusto, I assume the results in that paper are for ground logic programs? Program / data complexity here are analogous distinctions to query / data complexity in database theory (first defined in some paper by Vardi) - they refer to the complexity when either the knowledge base or the query / logic program rules are considered as fixed. I'm not sure how the "knowledge base" is defined for logic programs though.

[abcorrea]

I suggest the lecture by Gottlob as a reference, instead of the full paper, if one of you want to have a look: http://www.cs.ox.ac.uk/files/1018/gglecture7.pdf

About the complexities, I think Guillem confused them. From the lecture:

• Data complexity: assume that the logical program is fixed, and the database (in our case, initial state) is the variable input
• Program complexity: assume that the database (respec., initial state) is fixed, and the logical program is the variable input

Guillem, the theorem that I mentioned explains both cases. It reads as follows:

THEOREM 5.1. (Implicit in Apt et al.[1988]). Stratified propositional logic programming with negation is P-complete. Stratified datalog with negation is data complete for P and program complete for EXPTIME

and, as usual, Datalog contains and EDB (grounded) and an IDB (lifted). Did I misunderstand it?

[miquelramirez]

Thanks very much for the pointer @abcorrea - those slides explain beautifully what you meant. I have very little background on logic programming, other than doing some incidental programming on Prolog like 20 years ago and more recently misusing(?) Gringo , so I appreciate very much the resource.

[miquelramirez]

No, I meant that you can reduce any CSP to the problem of checking whether there is any reachable grounding of an (effect-free) action schema from an initial state given by the extensional relations of the CSP. But as augusto points out, this is irrelevant for a fixed domain.

I don't understand what was the intent for this statement, or how it relates to the existence of tractable CSP classes. It is fact that DATALOG is P-complete, it is not a general language to specify arbitrary CSPs.

On the other hand @abcorrea I wonder how that Theorem relates to these results on the expressiveness and complexity of DATALOG, and the complexity of determining entailments from logic programs with negation:

On Datalog vs Polynomial Time
Foto Afrati, Stavros Cosmadakis, Mihalis Yannanakis
Journal of Computer and System Sciences, 51, 177-196 (1995)

and

The Stable Models of a Predicate Logic Program
V. Wiktor Marek, Anil Nerode, Jeffrey Remel
Journal of Logic Programming, 21, 129-153, (1994)

Both of these papers discuss a problem (i.e. finding if a ground atom is entailed by all stable models of a logic program P) that seems to align very well with the complexity reported for "combined complexity" using Gottlob's terminology.

Could somebody explain to me what do we mean exacty by "fixing" the logic program rules or the facts? Does this relate to the possibility to compile the program rules into some form (such as prime implicants or an approximation thereof)?

My current impression is that the concept of data-complexity does not applies to the problem of grounding as we usually deal with it (i.e. every call to the planner is independent, so the entailment check for ground atoms is a "one shot problem") but rather the one that applies is "combined" complexity.

Of course, the setting we rely on for the competitions and validating planning algorithms is not necessarily the one that makes more sense for applications where you can expect many calls to the planner in sequence over the same domain. In that case I can totally see the relevance of the notion of "data"-complexity.

[abcorrea]

@miquelramirez I agree with your comments that this is not really our setting. Unfortunately, even in the community itself, it does not seem to have a common sense about when to use each complexity.

The introduction from the paper "On the Complexity of Database Queries" by Papadimitriou and Yannakakis (1999) explains the difference and problems arising from each definition of complexity. They talk in particular about query languages and focus on conjunctive queries later on, but they also mention Datalog as a query language in the introduction. You probably have free access to the paper in this link: https://www.sciencedirect.com/science/article/pii/S0022000099916264 . The first three paragraphs of the introduction are the important ones to our discussion.

(Spoiler alert: they conclude that none of these complexities -- data, combined, or program complexities -- is really useful to all cases and they present complexity results using the fixed-parameter tractability idea.)

But let me bring the discussion to another perspective: The logical program that I proposed (with negated static preconditions) is no harder than the current logical program that we use. These negated static preconditions would transform our Datalog into a Semipositive Datalog (i.e., a Datalog program allowing negated atoms in the body if these atoms do not appear in the head of any rule). The textbook "Foundations of databases" (Abiteboul et al. 1995) presents some nice properties of Semipositive Datalog programs. The main idea is that we can transform any Semipositive Datalog program into a Positive Datalog program in polynomial time, similar as we do in planning to transform tasks into positive normal form.