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

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

See meta-issue: issue924.
File name Uploaded Type Edit Remove 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
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)
       (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)
         (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 

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.)
Date User Action Args
2019-12-19 16:44:34francos3setfiles: +
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