Issue396

Title possibility to compile away conditional effects
Priority feature Status in-progress
Superseder Nosy List florian, gabi, haz, jendrik, malte, mkatz
Assigned To gabi Keywords translator
Optional summary

Created on 2013-11-11.15:38:24 by gabi, last changed by malte.

Files
File name Uploaded Type Edit Remove
issue396-fixed-redundant-effects.patch florian, 2014-01-13.14:25:48 text/x-patch
issue396.patch gabi, 2013-12-20.15:49:49 text/x-patch
Messages
msg3207 (view) Author: florian Date: 2014-07-14.15:08:06
Michael noted that there is another issue in the patch. An example shows up in
the cave diver domain of IPC14:

The problematic operator looks like this:

PRE:  [<Atom available(d0)>, <NegatedAtom in-water()>]
ADD:  [([], <Atom at-surface(d0)>), ([], <Atom in-water()>)]
DEL:  [([], <Atom available(d0)>), ([], <Atom available(d3)>)]

The problematic thing here is the delete effect of <Atom available(d3)>.
There is no corresponding add effect for the same mutex group (FDR
variable), so the translation adds a guarding conditional effect:

IF var3=<Atom available(d3)> THEN var3=<none of those>

Quoting from Gabi's email:

> The trivial solution would be adding a separate action for each value of
> the FDR variable and to include it as a precondition. For the one with
> var3=<Atom available(d3)>, we would include the effect on var3, for all
> others not. However, this is again an expensive thing to do because in
> the case of several such guards (on different variables) this leads to
> another combinatorial blow-up.
>
> We probably need to think more about this.
msg2912 (view) Author: florian Date: 2014-01-13.14:47:26
> A warning: with conditional effects, having the same atom in condition and
> effect isn't always redundant.

I see, but this occurred after the compilation in the compiled operators without
conditional effects. I guess this can happen when combining two conditional effects:

A => B
B => C

is compiled to

<{not A, not B}, {}>
<{A, not B}, {B}>
<{not A, B}, {C}>
<{A, B}, {B, C}>

The first one is a no-op (should be ignored) and the last one should be <{A, B},
{C}> instead.
msg2911 (view) Author: florian Date: 2014-01-13.14:41:14
I also noticed that miconic-simpleadl tasks with conditional effects compiled
away can have a lower initial h value than the same tasks with conditional
effects in LMcut (the version with basic conditional effect support). This could
be also be a problem with the conditional effect support in LMcut but this did
not show up in issue403.

Example: miconic-simpleadl/s30-0.pddl
Translated with conditional effects compiled away, both the original LMcut and
the one from issue403 start with an initial h value of 56.

Without compiling away conditional effects, the LMcut heuristic from issue403
starts with the perfect heuristic value of 71.
msg2910 (view) Author: malte Date: 2014-01-13.14:40:29
A warning: with conditional effects, having the same atom in condition and
effect isn't always redundant. I know Gabi is well aware of this, but the others
working on this might not. For example, consider an operator with the following
effects ("=>" for conditional effects):

a and c => a
b => not a

The net effect of this is that it is equivalent to

b and not c => not a

(BTW, something like this might make for a nice test case if we had a proper
collection of tests, which we should maybe start at some point.)
msg2909 (view) Author: florian Date: 2014-01-13.14:25:48
The task coins_p-01.pddl in domain t0-coins triggered an assertion with this
patch (stack trace at the end of this message). The problem seems to be that
operators are created that have an atom appear in condition and effect (making
the effect redundant). I attached a proposed fix for this. Since I don't know
the code in simplify.py at all, I didn't want to replace the existing patch.

Traceback (most recent call last):
  File "app_main.py", line 51, in run_toplevel
  File "./translate/translate.py", line 769, in <module>
    main()
  File "./translate/translate.py", line 759, in main
    sas_task = pddl_to_sas(task)
  File "./translate/translate.py", line 624, in pddl_to_sas
    simplify.filter_unreachable_propositions(sas_task)
  File "/home/pommerening/projects/downward/metis/src/translate/simplify.py",
line 325, in filter_unreachable_propositions
    renaming.apply_to_task(sas_task)
  File "/home/pommerening/projects/downward/metis/src/translate/simplify.py",
line 140, in apply_to_task
    self.apply_to_operators(task.operators)
  File "/home/pommerening/projects/downward/metis/src/translate/simplify.py",
line 204, in apply_to_operators
    self.apply_to_operator(op)
  File "/home/pommerening/projects/downward/metis/src/translate/simplify.py",
line 232, in apply_to_operator
    new_pre_post.append(self.translate_pre_post(entry))
  File "/home/pommerening/projects/downward/metis/src/translate/simplify.py",
line 268, in translate_pre_post
    assert new_post is not always_false
AssertionError
msg2844 (view) Author: gabi Date: 2013-12-20.15:49:49
Unfortunately, I found a bug in the patch (actions could be discarded), so I
attach an updated version.
msg2841 (view) Author: gabi Date: 2013-12-19.14:53:55
Sorry, I attached an outdated (and buggy) patch. Here is the correct one.
msg2840 (view) Author: gabi Date: 2013-12-19.14:52:16
Since I will not be able to finish this properly before the IPC, I now attach a
(dangerously untested) patch that should do the trick (set the flag
COMPILE_AWAY_CONDITIONAL_EFFECTS in src/translate/translate.py to True). 

I do not think that we should integrate this in the planner. First, because it
is not yet the best possible implementation (we could avoid some copying and
negating by distinguishing add and del effects in the init method of
PropositionalAction and we should filter for duplicate actions afterwards).
Second, I think we should keep the pressure to really support conditional
effects in the planner.
msg2703 (view) Author: haz Date: 2013-11-20.05:40:09
It would be a very helpful feature. But I would say the same of having the 
sequential operator compilation as well -- it is a nice fall back when 
conditional effects must be compiled away and the exponential blow-up is too big 
to handle.
msg2680 (view) Author: gabi Date: 2013-11-11.15:38:24
Since the IPC 2014 requires support of conditional effects, we should implement 
a possibility to compile them away. We plan to multiply out conditional effects,
which can lead to an exponential blow-up of the task. On the positive side,
compared to other ways of removing conditional effects, it does not add axioms
or split up an operator application into a sequence of operator applications.

This should also serve as a baseline for a direct support of conditional effects
in various heuristics. It also could help to verify that the problems reported
in issue146 are really due to conditional effects.
History
Date User Action Args
2014-10-04 19:35:33maltesetkeyword: + translator
2014-07-14 15:15:46mkatzsetnosy: + mkatz
2014-07-14 15:08:06floriansetmessages: + msg3207
2014-01-13 14:47:26floriansetmessages: + msg2912
2014-01-13 14:41:14floriansetmessages: + msg2911
2014-01-13 14:40:29maltesetmessages: + msg2910
2014-01-13 14:25:48floriansetfiles: + issue396-fixed-redundant-effects.patch
nosy: + florian
messages: + msg2909
2013-12-20 15:49:49gabisetfiles: + issue396.patch
messages: + msg2844
2013-12-20 15:49:38gabisetfiles: - issue396.patch
2013-12-19 14:54:07gabisetfiles: - issue396.patch
2013-12-19 14:53:55gabisetfiles: + issue396.patch
messages: + msg2841
2013-12-19 14:52:16gabisetfiles: + issue396.patch
messages: + msg2840
2013-11-20 05:40:09hazsetnosy: + haz
messages: + msg2703
2013-11-16 19:37:02jendriksetnosy: + malte, jendrik
2013-11-11 15:38:24gabicreate