After reading through the issue discussion again, I think we're done here. The
original suggestion was incorporated. We found out that it can be detrimental to
performance, mainly due to its effect on relevance analysis, so we made it
optional. In the current code, it is disabled by default, but can be enabled
with the translator option --add-implied-preconditions, which carries a warning
in the documentation that refers to this issue. I think that's good enough to
consider the original concern addressed.

We also discussed the possible improvement of adding a section to the translator
output that lists known implications between facts, but I would see this as a
separate request. If someone wants to pursue this further, please open a new
issue with priority "wish".

> Say we use the default partial encoding and compute mutex groups
> {a, b, c}, {d, e, f}, {a, d, g} before selecting the FDR variables.
>  Then we might select:
>
> dom(v_1) = {a, b, c}
> dom(v_2) = {d, e, f}
> dom(v_3) = {g, "none of those"}
> 
> and would have the currently unused implications
> (v_1=a) => (v_3="none of those")
> (v_2=d) => (v_3="none of those")

If I recall, the translator patch captures that case.  If there is a binary
variable (e.g. v_3) and we have a precondition that is mutex with "v3=g", then
it implies the precondition "v3='none of those'"; and substitutes this into the
operator in place of 'v3=-1'.

Not sure if there are other inferences in the translator that need ((A&B) => C)
- I haven't looked at it much since 2009.

> fact => fact is a subset of what can be inferred; a useful subset, of course,
> but it depends how general you want it to be.  If I recall, there are some
> analyses for eliminating '-1' preconditions that amount to:
>
> (factA & factB) => factC
>
> ...which would then be relevant to operators with both factA and factB in
> their preconditions.

Certainly true in general, but is the translator in the current form capable of
performing such an analysis?

A reasonable minimum requirement for me is that we can express the information
that we currently infer. I wouldn't much mind being unable to express
information that the current code cannot derive anyway.

We certainly have unexploited information of the form "factA => factB" at the
moment. Say we use the default partial encoding and compute mutex groups {a, b,
c}, {d, e, f}, {a, d, g} before selecting the FDR variables. Then we might select:

dom(v_1) = {a, b, c}
dom(v_2) = {d, e, f}
dom(v_3) = {g, "none of those"}

and would have the currently unused implications
(v_1=a) => (v_3="none of those")
(v_2=d) => (v_3="none of those")

Do we currently find and drop information of the form f1 & f2 => f3?

fact => fact is a subset of what can be inferred; a useful subset, of course,
but it depends how general you want it to be.  If I recall, there are some
analyses for eliminating '-1' preconditions that amount to:

(factA & factB) => factC

...which would then be relevant to operators with both factA and factB in their
preconditions.

(In domains with dead-ends, one can infer extra preconditions on operators too,
based on their preconditions and effects; and the fact that the goal must be
reachable after the operator is applied.  These have nothing to do with -1
transitions, rather they imply dead-end avoidance, but are implied preconditions
all the same.)

My initial thought would be that if we're replacing a -1 value with something
implied, prefix it with a +.  E.g. '6 -1 2' becomes '6 +3 2' if '6 3' is
implied; '7 +8' means 'we didn't have any condition on 7 before, but we've
implied 7 8'; etc.

Advantages: is backwards compatible
Disavantages: re. Malte's comments, it makes using the implied preconditions the
default.  (I suppose one could hack the code in operator.cc to segregate implied
preconditions?)

Fine with me. If we do not change the representation of conditions but add
another section, I would not want to include this change in the current revision
(mostly because I am short of time).

Sounds like a good idea to me.

I've been thinking. In general, adding all implied conditions can be a
performance issue. In the worst case, we could blow up the problem
representation quadratically. I don't expect this to happen in the current suite
of domains, but I'm not sure if this is good enough reason to ignore the point.

Right now, if I'm not missing something, the only implied conditions we could
add stem from knowledge of the form "fact1 implies fact2". Maybe we would be
better served by leaving the representation of conditions alone, but adding
implication information of this kind to the output in a separate section?

Then all the potential users of the representation could add the implied
conditions or not, at their discretion, and they could also use them in places
other than preconditions, effect conditions or goals (e.g. for landmarks, or for
SAT representations).

Please make a suggestion. The main thing is that we should use the same
mechanism for all kinds of conditions (preconditions; effect conditions of
conditional effects; goal conditions).

"but probably only after we've done the long overdue output file overhaul"

I am currently working on this revision of the output file. How should we mark
implied preconditions?

OK, I think the new data is fairly conclusive, so I think we can leave this the
way it currently is, with the implied preconditions controlled by a translator
flag which is off by default.

In a perfect world (=> with much more time available), it might be nice to have
the preconditions present in the output, but marked as "implied" so that every
part of the planner can decide for itself whether it wants to use them or not.
If anyone wants to implement such functionality, they are welcome. :-) (I can't
guarantee it will be merged, though -- possibly yes, but probably only after
we've done the long overdue output file overhaul.)

Here you go ;)

Yes, please do!

I ran a new experiment comparing the revisions from Malte's experiment with the 
current hg tip revision as of today and found that at least the coverage is 
bigger (or at least equal) in the latest revision than the maximum coverage of 
the revisions in Malte's experiment for each search configuration. So I would 
propose to close this bug. If you want to, I can provide the reports as well.

Experiment done, but I'm not sure what to make of it. I compared four revisions
of the translator: r3827, r3829 and r3840 of the translate-andrew branch (as
previously), and the trunk code after the most recent modification (r4283). All
tested with the search code, using some of our "standard configurations" on some
standard domain suites.

Here's the total number of tasks solved by configuration and revision:

issue7-r3827/results/search/version-fF 1450
issue7-r3827/results/search/version-oa10000 310
issue7-r3827/results/search/version-ou 437
issue7-r3827/results/search/version-yY 1445

issue7-r3829/results/search/version-fF 1447
issue7-r3829/results/search/version-oa10000 307
issue7-r3829/results/search/version-ou 434
issue7-r3829/results/search/version-yY 1445

issue7-r3840/results/search/version-fF 1451
issue7-r3840/results/search/version-oa10000 308
issue7-r3840/results/search/version-ou 434
issue7-r3840/results/search/version-yY 1453

issue7-r4283/results/search/version-fF 1447
issue7-r4283/results/search/version-oa10000 311
issue7-r4283/results/search/version-ou 437
issue7-r4283/results/search/version-yY 1445

With respect to these summary numbers, the latest revision looks good for the
optimal configurations, not quite as good for the suboptimal ones. I'm attaching
a file with per-domain results (only on those configurations/domains where the
different revisions had a different coverage) for closer inspection. Still not
sure if there's something systematic going on here that we should look at, or if
this is just random noise and we should close this one.

Any insights?

If anyone feels like looking at the data in a more detailed way (e.g. look at
expansion numbers), I'd be happy to provide a tar file with all the raw data.

OK, I looked at the preprocessor code.

What the code calls the "causal graph" is actually not the causal graph as
defined in most papers, as it does not include effect <-> effects arcs, only
condition --> effect arcs. For many things, such as relevance analysis, this is
actually preferable. Still, it's a source of confusion and we should check if
any of the code that uses the causal graph requires the currently missing effect
<-> effect arcs. I opened issue89 for this. Everybody interested in following
this, please add yourself to the nosy list there.

So what is happening is that the implied preconditions add more arcs to the
"causal graph", preventing certain irrelevant variables to be detected as
irrelevant. In Trucks-Strips at least, this can have disastrous effects.
Therefore, I've disabled ADD_IMPLIED_PRECONDITIONS in r4283.

If we're lucky, this should fix the performance issues I mentioned in msg206.

I'll now run some detailed tests with this modification.

It looks like the "add implied preconditions" feature has an adverse effect on
relevance analysis (i.e., things that should be irrelevant and were previously
detected as irrelevant are no longer detected after the change). I'm looking
into this.

I've made the feature optional in r4275 (variable ADD_IMPLIED_PRECONDITIONS in
translate.py), but it is still enabled by default.

I've generated a test case by taking Trucks-STRIPS #1 and making it a lot
smaller. (Added to translator/regression-tests.) The translator generates 9
variables for this instance. Without the implied preconditions, only 4 of these
survive the relevance analysis in the preprocessor. *With* the implied
preconditions, all 9 survive. It looks like the preprocessor is correct, but
I'll look into that before making a final call on what to do here.

The experiment has completed, and the results are a bit troubling. In all four
configurations, coverage gets worse (not by much, but still).

I'll look into this a bit more and try to understand it. With LM-cut and
merge-and-shrink, the culprit seems to be the trucks-strips domain.

The experiment also uncovered a bug with merge-and-shrink, apparently unrelated
to this issue. I opened a new issue for that: issue68.

I'll look into the FF and h^cea configurations in detail later, after the
picture with the optimal settings is clearer.

Just checked - the code does the same thing as my original patch.  Thanks for
your work on this.

I've moved the points mentioned in my previous comment to a separate issue: issue66.

Regarding the impact of the translator change on search, I started a proper
experiment with the four mentioned search configurations. I expect we'll have to
do similar experiments in other contexts in the future, so I made an effort to
encapsulate it all in a self-contained script that might be used as a basis for
future similar experiments. The code currently (r3846) lives at
trunk/scripts/stuff/issue7.

One more thing: once we're using the new translator code everywhere, we should
get rid of the special-casing of "stupid conditional effects" in some heuristic
implementations (LM-cut, merge-and-shrink, possibly others) since it should no
longer be needed.

Looking at the number of domains affected by the change, I guess we should check
somewhat more thoroughly what the performance impact is on the search code. As
with most changes in the translator, it's not really clear how it affects search
performance. I would intuitively expect that it should rather help than harm
with all heuristics I can think of, but you never know...

If anyone with access to the gkigrid has the time and inclination to do a quick
before/after test, that would of course be truly great. Personally, I'd be most
interested in what the change does to configurations oa10000, ou, fF, and yY.
(The first and last of these are most dependent on the FDR encoding.) Otherwise
I'll do it myself as soon as I get to it.

OK, I'm more or less happy with the code now and merged it to trunk in r3841.
Andrew, can you verify that it still does what you expect it to do?

Here's the impact of the change on the domains from suite ALL (i.e. IPC 1-5).

 * Domains where some unnecessary effect conditions are removed:
   miconic-fulladl, miconic-simpleadl, movie, psr-large, psr-middle, satellite,
   schedule
 * Domains where some implied preconditions are added:
   airport, blocks, depot, driverlog, freecell, grid, psr-small, storage
 * Domains where both happens: none
 * Domains where neither happens:
   assembly, gripper, logistics00, logistics98, miconic, mprime, mystery,
   optical-telegraphs, pathways, philosophers, pipesworld-notankage,
   pipesworld-tankage, rovers, tpp, trucks, zenotravel

OK, for those interested in following this, I've created a branch of the
translator under branches/translate-andrew in which I'll try to integrate the
functionality of Andrew's patch. (The "vartwo != var" change is already in there.)

If possible, I'd like to simplify the code a bit, so it's a bit more work than
just applying the patch, but I hope we'll have the functionality included in the
trunk pretty soon.

Good catch - should be:

if vartwo != var:

I'm looking into this right now. I'm a bit stumped by the line "if vartwo !=
valtwo" in "build_surrogate_key" in the patch. Looks like you're comparing a
variable number to a value number here -- is that a mistake?

Looking great, thanks!

I've set myself a reminder to deal with this after the ICAPS deadline.

Okay, I've ported the changes to downward-trunk/downward/translate/translate.py
and ran svn diff - patch is attached.

In terms of performance impact:

* Satellite pfile33:

Original: 1526MB RAM, 1227s CPU
Patched:  1526MB RAM, 1219s CPU

* PSR pfile40 (I didn't have enough RAM for pfile50 with either the modified or
unmodified translate.py):

Original: 760MB RAM, 402s CPU
After:  767MB RAM, 418s CPU.

In PSR, there are a lot of binary variables, so the 7MB of RAM and 11.190s of
the extra CPU time is accounted for by building the surrogates lookup table to
eliminate the first sort of (-1 > v) transitions mentioned in this thread.

Thanks a lot, Andrew!

Since it's a pretty large patch and translate.py is already quite a mess, it may
take us a while to incorporate it. (We should really start taking some measures
to keep that file somewhat manageable...)

If anyone wants to speed up adoption of this feature, two things that would help
would be

 * to convert the patch to unified diff format (use "svn diff" or "diff -u") and
 * to provide some before/after info on runtime and memory usage for the large
benchmark tasks (most importantly Satellite #33, PSR-Large #50)

The attached diff now improves the translator in two ways:

i) Fixes the transitions explained earlier in this thread

ii) Eliminates the pointless prevail conditions attached to pre_post conditions
affecting binary variables (that Malte mentioned).  So, for instance, in
Satellite, rather than switch_on actions defining a pre_post where:

condition: <26 = 0>
effect: <26 goes from xx to 1>

that now becomes just:

effect: <26 goes from -1 to 1>

Okay, sub 1Kb example attached.  Two switches, only one can be on at once (the
fact 'available' encodes that neither is on).  The translator encodes the
problem in three variables:

var0 = {(available), (on a), (on b)}
var1 = {(off a), none}
var2 = {(off b), none}

(SwitchOn a) is fine: var0 from 0 to 1, var1 from 0 to 1

(SwitchOff a) exhibits the behaviour discussed: var0 from 1 to 0, but var1 from
-1 to 0.

With the patch applied to the translator, this becomes (1 to 0), as (var0 = 1)
implies (var1 = 1).

In terms of domains affected, off the top of my head:
- Driverlog (board, disembark)
- Depots (hoists are lifting or empty)
- Sokoban (moving into a square does 0->1 on it being free; leaving does -1->0)
- etc.

by "very probably to", I meant "very probably related to".

Thanks for the note! So this is separate from (but very probably to) the
conditional effects issue Erez and I had in mind.

I guess this affects (among other things) all Driverlog tasks? It would be great
if you could attach/upload a concrete domain.pddl/problem.pddl pair that
highlight the problem. (Small ones preferred.)

Okay, quick example of the cases where it helps.  The Driverlog disembark
action, in PDDL, looks something like:

:preconditions
  (and...
     (driving ?driver ?truck)
  ...)
:effects
  (and ...
     (empty ?truck)
  ...)

The translator currently produces a binary variable for (empty ?truck), with the
relevant disembarks changing the value of it from -1 to 0 (i.e. anything to
true).  The patch picks up the obvious cases where another precondition (here,
driving...) implies that the truck isn't empty, and hence the Pre value can be
changed to 1.

Addendum: there are several kinds of stupid transitions in the translator
output; not sure which one Andrew's patch addresses.

One important stupidity we should fix is unnecessary conditional effects of the
kind "if x is 0, set it to 1" where x is a binary state variable. Such
transitions occur in at least Satellite (I think), and we have to work around
them in heuristics that don't support conditional effects.

And I implemented the same thing for at least one particular heuristic within
the heuristic (merge-and-shrink if I remember correctly, but maybe LM-cut or both).

The translator is probably the best place for this because it's the earliest
place, and hence also people who just use the translator can benefit. There's a
bunch of such external users.

So we should put this in the translator, and once we've done that, remove the
equivalent special purpose code in the heuristic initializers.

Michael Katz implemented the same thing (I think) as a method of the Operator class

[[original email by Christian Muise]]

Hey Malte,

  Great to hear the overhaul is underway. I just wanted to forward a
modification that Andrew Coles (cc'd in case there are any questions)
made this summer to the translate.py -- it detects sufficient
conditions for changing the -1 -> val transitions into val -> val
transitions. The patch should be applied to the LAMA version of
translate.py (since the trunk version doesn't have the operator cost
info in it). Hopefully the modification will be useful.

  Cheers,
   Christian

On Mon, Oct 5, 2009 at 1:26 PM, Malte Helmert
<helmert@informatik.uni-freiburg.de> wrote:
> Dear Fast Downward repository users,
>
> we (= Gabi, Erez and me) are currently heavily modifying the Fast
> Downward codebase, merging branches, moving them around, deleting stuff,
> etc. The goal is to get rid of the jungle of branches and have one
> definitive version of the planner ("1.0?").
> <snip>