Issue450

Title negated axiom rules cause combinatorial explosion
Priority bug Status chatting
Superseder Nosy List alachun, francos3, gabi, haz, malte, patrik, salome
Assigned To Keywords translator
Optional summary
See meta-issue: issue924.

Created on 2014-08-08.11:55:08 by malte, last changed by malte.

Summary
See meta-issue: issue924.
Files
File name Uploaded Type Edit Remove
ExistBlowupFiles.zip francos3, 2019-12-19.16:44:34 application/zip
citycar-domain.pddl malte, 2019-03-26.11:26:31 application/octet-stream
citycar-p3-2-2-0-1.pddl malte, 2019-03-26.11:26:53 application/octet-stream
mst.pddl malte, 2014-08-08.11:55:08 application/octet-stream
mst2.pddl malte, 2014-08-08.11:55:19 application/octet-stream
Messages
msg11657 (view) Author: malte Date: 2024-07-19.14:13:31
What's the status of this now that issue454 is merged?
msg11601 (view) Author: salome Date: 2024-06-27.12:28:04
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.
msg9125 (view) Author: francos3 Date: 2019-12-19.16:44:34
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,
msg8749 (view) Author: malte Date: 2019-03-26.11:30:48
We treat some performance problems as bugs, and I think this one is severe
enough to qualify. So I'm reclassifying this as "bug".
msg8748 (view) Author: malte Date: 2019-03-26.11:29:42
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.)
msg8746 (view) Author: malte Date: 2019-03-26.11:26:53
And now the problem file.
msg8745 (view) Author: malte Date: 2019-03-26.11:26:31
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.
msg3283 (view) Author: malte Date: 2014-08-08.11:55:08
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.)
History
Date User Action Args
2024-07-19 14:13:31maltesetmessages: + msg11657
2024-06-27 12:28:04salomesetnosy: + salome
messages: + msg11601
2019-12-19 16:44:34francos3setfiles: + ExistBlowupFiles.zip
nosy: + francos3
messages: + msg9125
2019-06-14 14:29:27maltesetsummary: See meta-issue: issue924.
2019-03-26 11:30:48maltesetpriority: feature -> bug
messages: + msg8749
2019-03-26 11:29:42maltesetnosy: + alachun
messages: + msg8748
2019-03-26 11:26:53maltesetfiles: + citycar-p3-2-2-0-1.pddl
messages: + msg8746
2019-03-26 11:26:31maltesetfiles: + citycar-domain.pddl
messages: + msg8745
2015-11-19 23:43:02hazsetnosy: + haz
2014-10-04 19:35:11maltesetkeyword: + translator
2014-08-08 11:55:19maltesetfiles: + mst2.pddl
2014-08-08 11:55:08maltecreate