See meta-issue: issue924.

I tested the problems and can confirm that all behave well now when using the blind heuristic or hmax with axioms=approximate_negative. When using hmax with the default (only approximate cycles) then the blowup still happens in citycar und mst, but not in the two exist problems and also not in dom_edge_queue.pddl + prob_triangle_in_square.pddl.

I'm thus closing this issue and will open the two other issues mentioned in msg11683 momentarily.

We need unrolling too for "exact" negated axioms, not because of the combinatorial explosion but because the non-unrolled version is incorrect for derived variables with a definition involving cycles. (Using this incorrect negation was a bug that we fixed by overapproximating the cases involving cycles; adding an exact version would be a new feature.)

I suggest using this issue to check that the specific examples that were reported here now behave better when using a suitable planner configuration. If they do, I suggest we close it because the original "bug" -- an unavoidable exponential behaviour -- is no longer there. But we should test the instances discussed in this issue before closing.

This would leave two wishes for the future:

- exact negated axioms
- negated axioms without the exponential CNF-to-DNF transformation

I suggest making both of these new issues.

Sorry, just realized that we can avoid the explosion with auxiliary variables, not with unrolling. I think unrolling would be relevant for derived variables with cyclic dependencies, where we currently always overapproximate (see issue453).

The default behaviour can still cause a combinatorial explosion, but
 1) only when using a heuristic that needs negated axioms
 2) these heuristics now have an option to avoid it (at the cost of heuristic accuracy).
I thus changed the priority to feature (and removed the translator keyword, since the computation has been moved to the search component). I assume we would still like to provide an alternative way of exactly computing negated axioms that avoids the combinatorial explosion (I think unrolling would be the key here?), but I don't know if we want to just change this issue to be about this instead, or rather open a new issue and close this one instead.

What's the status of this now that issue454 is merged?

Christian Muise reported some new tasks which also run into the exponential blowup. The tasks can be found here:
https://github.com/haz/minor-planning/ (for example revision ee618c0)
The repo contains two domain and two problem files, where the domain files are just variations, and the problem files work with both domains. prob_triangle_in_square.pddl is solvable, prob_C6_planar.pddl is not.

Side note: Once issue454 is merged, dom_edge_queue.pddl + prob_triangle_in_square.pddl should be solved in reasonable time according to Christian's test on the 454 branch.

Original message to the mail list below.  The domain and problem files are 
very simplified, so the "bug" is very easy to reproduce/alter.

Also thanks for all the work in maintaining and improving FD over the years, 
it probably does not get said frequently enough ;-)
____________________
Dear all,

I am working on a domain where agents move in a 3D grid.  I attach 2 very 
simple domain and problem files with only one action and one trivial goal to 
showcase my problem.  The "NoBlowup" version works as I would expect.  The 
"Blowup" version Exists statement memory usage (when processing the axioms) is 
growing by a ratio of 6 per extra agent.  The time cost increases similarly.  
This means that I cannot use more than 8 agents on my 32GB memory machine for 
a 13x13x13 grid when using the "Blowup" version.

The Exist statement which blows-up (memory and time-wise) if using more than 8 
agents below:

(not (exists (?r - agent)
    (and
       (at_agentX ?r ?x1)
       (at_agentY ?r ?y1)
       (at_agentZ ?r ?z1)
     )
    )
)

The Exist statement that does not blow-up (it can deal with 16 agents 
instantaneously, translate memory and time efforts are negligible):

(not (exists (?r - agent)
     (and
         (at_agent ?r ?x1 ?y1 ?z1)
      )
     )
)

The only difference between both versions is whether the "at_agent" predicate 
is split up or not.  I do not understand why the difference in performance, as 
a function of the number of agents, is so large (for grounding).  Am I missing 
something or is there a problem with the way translate handles the first 
Exist?

Thanks a lot for your help,

We treat some performance problems as bugs, and I think this one is severe
enough to qualify. So I'm reclassifying this as "bug".

Lu Xu: I have added you to the "nosy list" of this issue, so that you will
receive email updates when we make progress on this issue. If you prefer not to
receive these updates, please let me know, and I can remove you from the nosy
list again. (You can also remove yourself.)

And now the problem file.

I am attaching another example that highlights this performance issue, or at
least I think it has the same cause. It is a modified version of the citycar
domain that includes some compiled-in control knowledge.

This comes from issue912; I have received the PDDL file from Xu Lu email and
received permission to add it here. First, the domain file.

Spawned from issue335. I'm attaching Patrik's example from that issue. With the
current translator version, we quickly run out of memory on this example unless
we comment out all but two objects. This is probably caused by
axiom_rules.compute_negative_axioms, which does a CNF-to-DNF-style conversion.

There are two separate aspects here. Firstly, we could avoid the exponential
blowup by introducing auxiliary axioms.

Secondly, it's not clear why we need to compute these negated axioms at all. I
think they were originally added for "extended DTGs", and I'm not sure if they
are really used except perhaps by a few optional parts of the planner (CG
heuristic, possibly cea heuristic, possibly some landmark generation methods).
If this is an optional computation, it doesn't belong in the translator.
(However, I did a quick test that simply removed this line of code, and this
didn't work well, claiming Patrik's example is unsolvable. It may be that the
simplification later on in the translator then decides that the variable is
unnecessary or something like that.)