The email has been sent, and Jendrik has made the changes to lab. They will
trickle into the public versions eventually. All done here, thanks to everyone! :-)

I checked the search code; redundant mutexes are not harmful. So I suggest going
with B. The preprocessor documentation is already updated.

I'm done updating the documentation on the wiki. Jendrik will look into lab next.

Hmmm, one more thing I noticed while updating the references to the preprocessor
on the wiki. Previously, the preprocessor stripped mutexes that only refer to a
single state variable, and this was documented behaviour, i.e., the search
component was allowed to rely on this.

The new implementation also usually does this, but *not* if both
--keep-unreachable-facts and --skip-variable-reordering is used, because in this
case the new code is skipped altogether. What do you suggest?

A) Change the translator to also filter mutexes of this kind when these two
options are used.

B) Change the documentation to mention that there are certain cases where such
redundant axioms are generated.

C) Something else.

Great! :-) I can think of three more TODOs:

1. Update the wiki to remove references to the preprocessor.
2. Make the necessary changes to lab.
3. Write an email to the Fast Downward list to let people know what changes for
them (mainly: new translator options instead of old preprocessor option;
possibly changes for users of lab).

Jendrik will look into 2. I can volunteer to do 1 and/or 3, unless Gabi prefers
to do these herself. Gabi, what are your preferences?

Merged.

Jendrik, just let me know if you have any questions for the lab update. You
probably don't have to change a lot.

Gabi, do you want to do the merge or should I?

Fine with me.

Gabi has a repository on bitbucket, but I suggest we just merge it, then you can
look at the code in the master repo (branch issue26 as usual).

Well, I don't know how you changed the driver, but I guess all that needs to change 
is that lab doesn't try to compress the "output" file. Probably some of the parsing 
code will also have to be changed. Is the code available somewhere?

Once this is merged, we need to update the parts of the wiki that refer to the
preprocessor. For example, I think there is a page documenting the preprocessor
output format.

Thanks! I pushed a tiny change. From my perspective, the code is ready to merge.
We still have to test if/which further changes to lab are necessary because of
the output files and preprocessor log that no longer exist etc., but if Jendrik
is fine with it, I don't think that has to be part of this issue.

Yes, we use the pre->eff CG variant. I added this as a comment in the class
description. I also added the output that states how many variables etc. were
removed.

Besides that, I also did two refactoring steps (replacing the bool dict with a
set and removing unused counters). Malte, these are only local changes so they
should be easy to review.

It seems that we indeed do not prune irrelevant facts. Should we open a new
issue for this?

+1 for reinstating the output mentioned in 2). This is essential information for 
those keeping an eye on things that should not be pruned because of external 
assumptions (e.g., the PDDL is a determinized version of a non-deterministic 
problem ;)).

Code looks great! I merged from default and made a few (very) cosmetic changes
to some comments, variable names and such.

Two more things before we merge:

1) The variant of the causal graph that is used in translate/variable_order.py
is the pre->eff graph, right? (That is, it does not have eff<->eff edges.) If
that's right, I'd like to document this near the top of the file where we talk
about the causal graph, but I'd like to see this confirmed first.

2) The only thing I miss compared to the old preprocessor is the output which
states how many variables, operators etc. were removed, i.e., these lines:

43 variables of 117 necessary
0 of 5 mutex groups necessary.
1445 of 1784 operators necessary.
0 of 0 axiom rules necessary.

Any objections to putting these back in? Gabi, do you want to add the code for
this or should I?

By the way, is it true that we only prune irrelevant variables, but not
irrelevant facts? This would be quite a lost opportunity, which we should
probably rectify at some point.

I prepared everything for reviewing...

Great!

The time required by the additional functionality in the translator appears
uncritical: http://ai.cs.unibas.ch/_tmp_files/roeger/issue26-time.html

On most tasks it's a fraction of a second. Maximum is 42s on the largest airport
task but this is quite an outlier. From the other tested domains, no task takes
more than 6s (longest is tidybot-sat11-strips-p20.pddl).

I tested the tidybot task on my desktop machine. There the additional time
required by the translator is 2.6s whereas the separate preprocessing step 
takes 16.5s (doing more things which are irrelevant for the search component).

I like merging v1, and I agree that we should then remove the preprocessor.

Before we do this, can you post experimental results for v1? I know the later
stages of the planner aren't affected, but it would be good to see what the
effect on translator runtime is.

If we integrate the latest changes, the preprocessor becomes obsolete. I would
prefer not to maintain it any further as part of Fast Downward and to entirely
remove it from the repository. Any objections?

Here are the results from the experiments:

http://ai.cs.unibas.ch/_tmp_files/roeger/issue26-v3-optimal-issue26-v1-issue26-v2-compare.html
http://ai.cs.unibas.ch/_tmp_files/roeger/issue26-v3-satisficing-issue26-v1-issue26-v2-compare.html
http://ai.cs.unibas.ch/_tmp_files/roeger/issue26-v3-satisficing-issue26-v2-issue26-v3-compare.html

For optimal planning on STRIPS tasks, the change from v1 to v2 overall does not
make much of a difference except for some slightly negative impact with the
merge-and-shrink configuration I tested. The change from v2 to v3 does not
affect STRIPS tasks.

For satisficing planning the change from v1 to v2 negatively affects the causal
graph heuristic, especially on pathways and assembly. For the other heuristics,
the picture is less clear. The change from v2 to v3 seems to be perfectly
neutral with respect to plan quality. Coverage is slightly reduced but there is
not really a reason for this because the only affected tasks are STRIPS tasks
and the input of the search component is equal with both version. The coverage
drop is also not caused by a longer translation time. I have no clear idea why
v2 and v3 should behave equally but it seems that the change does not affect the
greedy variable ordering.

So overall, I would vote for integrating version 1 in the default branch. This
also has the advantage that it does not change the behaviour of any planner
configuration.

Alternatively, we could also try a 4th version that differs from v1 by
explicitly tie-breaking on the order the nodes have been encountered by Tarjan's
algorithm. In version 1, it is only used for an initial ordering but later in
the algorithm ties can be broken differently. However, I would expect that this
might mostly have a positive impact on the causal graph heuristic, so I don't
think that it is worth to change the overall planner behaviour for this.

The only remaining (= actually used) functionality of the preprocessor is the
definition of the variable order from the causal graph (and the pruning of
irrelevant variables). I reimplemented this functionality as part of the
translator in three different versions:

v1: Reproduces exactly the result of the preprocessor.

v2: Variables within a strongly connected component of the causal graph are
ordered by a greedy method that is based on weights for the edges (explained in
my comment for v3). There is a tweak in the code of v1 that ensures that for
equally weighted nodes tie-breaking is done based on the order the nodes have
been encountered by Tarjan's algorithm for identifying the SCCs. The difference
between v1 and v2 is that I removed this tweak.

v3: In the preprocessor you can find the following comment:
 * there is a weighted edge from a variable A to a variable B with weight n+m if
 * there are n operators that have A as prevail condition or postcondition or
 * effect condition for B and that have B as postcondition, and if there are
 * m axioms that have A as condition and B as effect.
This is not really what is implemented for operators in the preprocessor.
Instead of counting each operator at most once for variables A and B (A!=B), the
actual weight from an operator is something like
* 1 if A is a prevail condition and there is an effect on B plus
* #(normalized effects on B) if A is a precondition of the operator plus
* #(normalized conditional effects on B where A is an effect condition)
Version 3 of the code instead implements the weights as described in the
comment. This shouldn't make a difference for STRIPS tasks.

Experiments are running.

Causal graph, DTGs and successor generator from the preprocessor output are now
ignored by the search component. The preprocessor output format can now be
changed to be identical to the translator output format.

We created issues to move the successor generator (issue547) and the DTGs
(issue549) into the search code. The causal graph was already moved there. Once
these two issues are done, successor generator, causal graph and DTGs can be
removed from the preprocessor, and the preprocessor output format can be changed
to be identical to the translator output format.

Things have moved a bit since this last message more than five years ago. :-)

The all.groups and test.groups files are long gone, and the search no longer
needs causal graph information from the preprocessor (though it is still generated).

Getting rid of the dependency on DTGs generated by the preprocessor is issue549.

For now, our migration strategy is to allow the search code to run the
preprocessor internally (if called on a translator output) *OR* to read already
preprocessed input, so that merging branches etc. remains easy enough.

Sounds perfect to me.

  Cheers

The mutex information will definitely stay. Several parts of the planner rely on
it, although I don't exactly know which ones. (Silvia originally added the file
for the landmark heuristic.) The current idea is to integrate all three
translator output files into a single file -- while the test.groups information
is not really necessary for the planner, it would allow more readable dumps and
logs.

About arbitrary external libraries, we can easily add a contrib directory or
some such to the distribution, maybe drawing stuff from branches/ext or some
other place.

- Moving as much of the preprocessing to the translator would be a bonus --
especially the parts that delete variables / operators. One common problem I've
faced was when I wanted to address certain variables / operators and they
changed between output.sas / output formats (along with test.groups for seeing
what variable values correspond to which fluents). If this is locked in as part
of the translate phase, that problem goes away.

- I have a use for test.groups and all.groups. I know there's a suggesting
elsewhere to move the all.groups into output.sas, and I'm all for that -- just
don't do away with recording all the mutex relationships...info there is great
to have / reason with.

- Some of the stuff I'm working on requires a parser almost line-for-line like
the SG parser. If it /is/ removed from the main code base, then I'd suggest
having a place in the code where arbitrary libraries can be kept. ie. Go there
if you want an SG parser, or a PDDL parser, or whatever. That way, if someone
has a whacky approach of restructuring the SG post-translate and pre-search,
they can pull in the library and do it themselves in the frankenstein solver
they're working on.

  Thanks for keeping in the SG / DTG / CG dump -- definitely a key ingredient in
a lot of my ongoing projects.

Yes, there are simplifications going on in the preprocessor. We would move those
either to search or to the translator. External tools that detect irrelevant
operators/variables could work directly on the translator output, I think, so
that should still be possible.

We can easily add some options to skip search and dump SGs, DTGs and CG.

Inserting modified data structures (e.g. SGs) back into the planner would be the
one use case that would be harder to support. If we don't support it, we can get
rid of all the SG parsing code, which would be very nice.

So would you be OK with this?

I do indeed use the preprocessor output. Besides the possibility of having
operators / variables simplified or removed (I think the preprocessing catches
some things here, no?), I use the following:

- Successor Generator: For other planning systems, I use the SG for rapid
operator applicability. It's also good to get a hold of this, modify it, then
insert it back in for LAMA (or whatever) to use. The API I use to deal with it
assumes that we can have access to this prior to planning:
http://tinyurl.com/yksjdt2

- DTGs: Most of my use with these involve either visualizing the problem, or M&S
type operations. If M&S has a better form of representing this (ie. the
characterization of operators on edge transitions), then updating the DTG export
would be great to have.

- CG: Again, this is used for visualization / a number of other things. Merging
heuristics, stratification uses, variable typing, etc.

  All in all the extra stuff the preprocessor gives you is quite important to
have before planning begins. If it's merged into the search step, a flag to
avoid search would be good to have (so the compiled program can be used as a
preprocessor, search only, or both).

The preprocessor should be part of the search code. Integrating it should be
fairly straight-forward, but we should make sure that this does not increase
memory usage of the search component (i.e., after preprocessing, we should
properly delete everything that we don't need to hold on to).

Also, if I recall correctly, there are currently some users of the preprocessor
output other than Fast Downward itself. Christian, if I recall correctly you use
the preprocessed output for something? What do you use, and in what form do you
need it?

Once we've done the integration, we should consider which preprocessor data
structures should be computed unconditionally (such as the successor generators)
and which ones should really be part of particular heuristics. For example, DTGs
are not relevant for all heuristics; in vanilla Fast Downward, only h^CG and
h^cea use them (h^m&s could, but doesn't). I guess that there are some more
users in the FDTech and lama branches, though.