Issue450

Title negated axiom rules cause combinatorial explosion
Priority bug Status chatting
Superseder Nosy List alachun, gabi, haz, malte, patrik
Assigned To Keywords translator
Optional summary

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

Files
File name Uploaded Type Edit Remove
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
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
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