Also consider issue497.

I'm adding some issues here that also discuss possible changes in the translator output format:
 - issue454 wants to "simplify the translator output format by only allowing binary derived variables whose default value is always false, and only allowing axioms setting a derived variable to true". This is also related to issue54 (enforce that derived variables must be binary).
 - issue978 wants to move the axiom layer computation to the search code.

As discussed in issue509 (msg6992 to msg6995), we would like to remove the
metric section altogether. We already planned to set costs to 1 if the metric is
unused, so it wouldn't serve any purpose anymore.

Since the last sprint, the translator's sas_task module now contains some
information on what we consider "valid" output tasks. Note that so far, this
*only* applies to the translator, not to the preprocessor output.

This is closely related to point 5., and as of today there is now a
TODO/discussion that is closely related to point 4., so I want to point this out
here, as I think only Gabi knows about these comments yet. (She reviewed the
issue that added most of these comments.)

Regarding point 5., we must eventually also decide what to do about our
"canonical order" in abstract tasks in the search component. Having a canonical
order defined for the global task (only) won't be very useful there if nobody
works with the global task directly.

We currently store the variable assignment of the initial state as a vector<int>
g_initial_state_data. We then have a global function g_initial_state() that
registers the initial state data in the global registry and returns the actual
state object. This is somewhat complicated compared to just storing the state
object. It can also be confusing because g_initial_state_data does not have
axioms evaluated yet, so it cannot be used instead of the initial state.

As far as I know, the only reason for this setup is that the axioms are not
known when the initial state is read in. On the other hand, it looks like the
axioms depend on the initial state as well (g_default_axiom_values).

Florian, regarding the new order of sections (variables < mutexes < axioms <
operators < initial state < goal): Is this still beneficial? I do not see how to
exploit it in read_everything (globals.cc). 

(I already asked this about a year ago but your answer from msg2717 is no longer
conclusive, given other changes in the planner.)

I was reminded of the following by the email to the public Fast Downward list
that arrived today: it would be nice if the file format included some additional
metadata about the instance. Something like ("#" marks comments that are not
part of the file format)

begin_header
/home/user/.../blocks/domain.pddl    # domain file name used (or a relative path?)
/home/user/.../blocks/prob04.pddl    # problem file name used (or a relative path?)
blocksworld                          # domain name from the PDDL file header
probBlocks-foobar-04-xxx             # problem name from the PDDL file header
end_header

right after the version block. This is not really needed for lab, which knows
this info itself, but maybe not everybody uses lab, and I can imagine
interesting uses. For example, one could write a script such that

$ ./validate_plans.py output sas_plan

validates the plan for the given preprocessor output file. (For this the header
is needed because the validator needs access to the domain and problem filename.)

I don't have a strong preference about the details you discussed (but I agree
with Gabi that it would be suboptimal to bump the version number many times, but
also to keep many things that are essentially done as "open"; I also agree with
Florian that they perhaps shouldn't be marked as "resolved" while they're not
yet merged).

A general mechanism to minimize the damage of disruptive changes like file
format changes is to keep them as small as possible by first making all required
changes that can be done non-disruptively. Then the time period over which the
disruptive code needs to be developed, reviewed and merged is small.

In this case, there are at least three preparatory changes we can do without
changing the file format:

>  3. action costs 1 if not :metric declaration

Here, we can already change the translator and preprocessor to have the output
in the form we want to have (which, as I understand, is to mark the action cost
as "1" rather than "0" if there is no :metric declaration). I don't think this
violates our current file format. It might break some unnecessary assertions,
which we could then remove.

>  5. canonicalize the order of things

IIRC, this was about the order in which we list effects and parts of individual
conditions. We can already change this now without changing the file format, and
add disabled tests that verify upon reading the input that it is in canonical
order. When we change the file format, we then only need to enable the tests.

>  6. remove causal graph

We can already make all changes to the code that need to be made for the causal
graph to be removable, i.e., make sure it's not used any more. The change to
throw it out will then be trivial.

>  7. add implied preconditions and mark them

Semantically, there's nothing wrong with adding these as proper preconditions to
the translator, which of course we can do in our current output format (without
marking them). I don't think we want to do this unconditionally since we know it
negatively affects relevance analysis and might negatively affect certain
heuristics, but we can already add this as a translator *option* and see what
impact it has when enabled.


Another thing we can do to smoothen the transition period is to make some of the
incompatible changes optional and disabled by default for a while. For example,
the translator only emits version-4 files if run with new option
"--experimental-new-output-format". The preprocessor can read version-3 and
version-4 and writes whatever format it has read. The search code uses version-4
internally, so e.g. it can handle implied preconditions, but will simply not
generate any implied preconditions when given a version-3 input file. The code
to make use of implied preconditions can then be developed (e.g. we can make
sure that the preprocessor's relevance analysis ignores them) without anyone
being inconvenienced by an incompatibility until everything is done. (Adding
some scaffolding like this while transitioning from one thing to another is not
at all unusual, e.g. when refactoring.)

Not sure if I'm sufficiently clear. TL;DR: let's start doing things now that we
can do to ease the change to the new file format without breaking things.

Like I said, I would leave issues open that are not merged into default (because
there is still something to do for them), but I'm ok with another solution as well.

After reading msg3309: Yes sub-issues sound good too.

Actually, the issue would be resolved if we consider it as a subissue of
issue371. Maybe we can mark them as such in the title, e.g. "Sub-issue of 371:
get rid of distinction between pre and prevail".

So what is your proposal? Just adding a comment leaves everything open. For me
the purpose of the issue tracker is to quickly see what needs to be done.

This depends on the definition of "resolved". For me this includes that the code
is merged into default but I'm not insisting on that definition. I would prefer
not to make this type of branching a typical use case by introducing a new
status. If we do this too often, the history might get messy.

The we would have the tracker cluttered with issues that are actually already
resolved. Maybe it would be better to introduce a new status for cases like this
that lets the issue disappear from the TODO list?

> The main down side of this procedure would be that there were resolved issues
> in the tracker that have not actually been integrated into the default branch.

We would not have to close the issues once they are merged into the new branch.
We could just add comments with references to the issues here and a comment
"resolved in branch for issue371" to the new issues.

Many of the changes of this issue have already been implemented but I think the
set of changes just became too large. I also don't think that splitting up the
issue into large chunks and bumping the version number several times is not the
optimal way to go.

So I suggest that we create a branch for this issue of which we again branch off
separate issues for each of the changes. We then can review, discuss and merge
them separately. If we do not proceed fast enough, we can still merge an
intermediate state with a new version number into the default branch. 

The main down side of this procedure would be that there were resolved issues in
the tracker that have not actually been integrated into the default branch.

Malte, Florian, what do you think?

Florian, I think you wanted to add new issues for version 5 and 6 (msg3252)? If
you do, for version 6 please add a cross-reference to issue7, which is closely
related.

Fine with me. I must have misinterpreted the comments on change 4.

I would separate the new semantics of conditional effects. Most of these other
things are already implemented but nothing has been merged, yet. Maybe its
better if I separate the issues in a way that does not make it necessary to
re-implement everything?

> So my suggestion would be to rename this one to "translator output format
> version 4" (or something more descriptive), close it, and move the deferred
> items to a new issue. (Once the work is done.)

From the comments it sounds like we plan 3 new translator output format versions:

Version 4 with changes
  1. variables < mutexes < axioms < operators < initial state < goal
  2. get rid of distinction between pre and prevail
  3. action costs 1 if not :metric declaration
  4. new semantics of conditional effects

Version 5 with change
  5. canonicalize the order of things

Version 6 with changes
  6. remove causal graph
  7. add implied preconditions and mark them


If there are not objections, I'll create the new issues for versions 5 and 6.

Are the changes for 1.-4. already merged?

PS: I think it's generally a good idea if we can close an issue once we've done
all the work we're willing to do at that time. This gives us a clear
relationship of "one issue = one branch = one set of experiments" that helps
with finding the relevant code for an issue later etc.

So my suggestion would be to rename this one to "translator output format
version 4" (or something more descriptive), close it, and move the deferred
items to a new issue. (Once the work is done.)

If it's not useful, it can go. No point in putting it back in after you've
already done the work of removing it.

I'll have a look at the patch for the heuristics where the pre/prevail
distinction "should" be useful (h^cea, CG, M&S, PDB) to see if we're currently
duplicating some work there. The CEGAR abstractions and Patrik's regression code
also exploit the pre vs. prevail distinction somewhere, I think, but I don't
think this is a good reason to stall the change.

What about the support of the old operator interface?

> So we could already specify the new semantics in version 4 but it would
> actually not yet be fully supported (or exploited).

This seems to be less work to me than bumping the version number twice (and
hence preferable).

Currently several effects on a variable may only trigger if they set the same
value. This is guaranteed by the translator: assuming that the invariance
analysis is correct there cannot trigger more than one add effect. For delete
effects, we add the condition that no add effect triggers (issue146).

So the old files would also be correct under the new semantics but with the new
semantics the output files could be much more compact. So we could already
specify the new semantics in version 4 but it would actually not yet be fully
supported (or exploited).

Deferring 6.+7. sounds good to me; I like change 5., but I'm not in a hurry, so
your choice. *If* we canonicalize, we should also sort operator effects by
variable. This will help with make certain kinds of compuations (e.g. for POR)
more efficient. (Obviously we can't sort by variable *and value* because of
change 4.)

Does change 4 require a change in the output format at all? Isn't it just a
change in semantics? A change in semantics might also warrant a version number
bump if it can potentially break anything, but I wonder if in this case this is
actually the case. I think that what 4. does is give proper semantics to a case
where currently the semantics is not properly defined (= what happens if
multiple effects setting the same variable to different values trigger).

How should we proceed here? I would like to defer changes 6 and 7 (removing the
causal graph and adding implied preconditions) for the moment. 

From my perspective, we could define changes 1-3 as output file version 4. We
also could include change 5 (canonicalising the order of everything) in this
version (I would still need to do this).

Change 4 (sequential evaluation of operator effects) is maybe more critical than
the other ones so I wonder whether we should split it of here and give this
change its own output format version (which would be 5). What do you think?

The last point is what we should do with the old operator interface in the
search. At the moment, I removed it entirely, so there is no method
get_pre_post. I also changed one field name of the preconditions so that
everyone notices that a certain piece of code should be checked. Should I revert
this and try to conform to the old interface as much as possible (transforming
to old prepost effects on the fly)?

Here are the results for satisficing planning (6.3 MB). Please ignore the errors
with the causal graph heuristics, I had a typo in the experiment script (new
experiments for cg are running).

We gain one more solved instance with most heuristics. Quality and number of
evaluations appears not to be affected, but we need slightly more memory. I do
not really know where. The only thing I am aware of is that every operator now
stores an extra entry in the precondition vector for non-prevail conditions
(previously they have been stored as one field in the effect). However, I do not
think this is critical.

I append first results for optimal planning (2.6MB) for the changes 1-3.

The old revision is 3e3cd7c3f552, the new one 133fa577fe9c. There are not many
changes in the results but there is one more solved instance:
p30-airport4halfMUC-p8.pddl with LM-Cut was now solved withing 1058 seconds and
a memory consumption of 1.5GB. I have no idea why. On the other airport
instances, there is not much difference between the two versions.

To keep track of the changes, I made a copy of the output format specification at
http://www.fast-downward.org/TranslatorOutputFormat4 (currently contains changes
1-3).

Apart from the causal graph heuristic, the variable order is very important for
the merge-and-shrink heuristic. The PDB heuristic also depends on it, where our
default (= stupid) pattern selection strategy uses the variable orders from
merge-and-shrink. Unless I forgot something, the other heuristics don't care
about the order except for tie-breaking (which may be important too, of course,
so changing the order requires an experiment for them).

The order may also be helpful for efficient successor generation, but we haven't
done extensive experiments on this. Christian Muise has done some related
experiments that show that good ordering for successor generators is very
useful, but we don't know how good our ordering is.

There are also third-party planners who use "the Fast Downward variable
ordering" for things such as BDD variable ordering or merge strategies in
symbolic merge-and-shrink.

As an intermediate step, if we want to get rid of the mixing of regular
variables and derived variables in the translator output, one option would be to
add an additional "begin variable_order/end variable_order" block in the
preprocessor that contains the current ordering information.

If the causal graph heuristic depends on a certain ordering of the variables, it
should probably handle this itself. What other heuristics have such a dependency?

> Regarding 1: Florian, what do you mean with "In particular, it (the initial
> state) could then be handled more like other states.". Do you mean that it can
> be read within a read_init function in globals.cc or are there additional
> simplifications in the State class possible?

I hope I'm not confusing the different implementations here, but if I remember
correctly, axioms were evaluated for the initial state after creating it. For
all other states, axioms were evaluated during their creation. This meant that
the State class could not be made immutable.

This changed somewhat in issue344 and issue385, where currently only the buffer
of the initial state (state_var_t*) is stored and axioms are evaluated by the
state registry when the buffer is registered (this is still one of the open
discussions on issue385).

> I would propose to separate normal variables from derived variables and to
> introduce a special section for default values What do you think?

This would have several nice aspects. In particular, it would be easier to store
states without wastefully reserving space for the derived variables.

The two drawbacks that I see are:

1. In operators and goals, it would no longer be clear what "variable #i" is.
Let's say we have 10 regular and 10 derived variables. Is variable #14 the 5th
derived one or the 5th regular one? (This can of course be easily solved with a
simple convention, but it would be .)

2. We cannot interleave normal and derived variables in the variable order any
more. Is this a problem for heuristics like the causal graph heuristic that
depend on ordering the variables in a suitable way?

Regarding 1: Simply having the axioms before the initial state does not resolve 
the dependency because the default values of the axioms are specified in the 
initial state specification. They are required when creating the AxiomEvaluator 
in read_axioms. What should we do about this? I would propose to separate 
normal variables from derived variables and to introduce a special section for 
default values What do you think?

Regarding 1: Florian, what do you mean with "In particular, it (the initial
state) could then be handled more like other states.". Do you mean that it can
be read within a read_init function in globals.cc or are there additional
simplifications in the State class possible?

7. We could add implied preconditions to the operators and mark them as such.
(cf. issue7).

6. The causal graph should disappear from the input file format. See issue372.

5. While we're at it, we might want to canonicalize the order of things, e.g.
require that all preconditions, effect conditions, mutexes etc. are sorted. I
think it currently *is* canonicalized already, and some of the code requires it
for correctness, but since this isn't prescribed anywhere, we have lots of
assertions that check the canonicity all over again in all kinds of places.

4. The fix of issue86 and issue146 will probably require a change of the
semantics of conditional effects in the output.

I'll start numbering things in case someone wants to comment on individual
suggestions.

Repeating Florian's suggestion:

1. Since the axioms affect the initial state, they should occur before it in the
files. This would make parsing the initial state easier. In particular, it could
then be handled more like other states.

Addendum to this: I think it makes logical sense to keep operators and axioms
together, so I would suggest an order like

variables < mutexes < axioms < operators < initial state < goal

2. We should get rid of the distinction between preconditions and prevail
conditions in the encoding.

3. In problems without a :metric declaration, we should use 1 for the action
costs rather than 0. (We can keep the info in the begin_metric/end_metric block,
so this wouldn't use any information, just make things clearer for people who
don't look into this block.)

This issue should be used to collect changes in the output format, so all of
them can be done at the same time.
I'll start with a change that would be nice for parsing the initial state:
Since the axioms affect the initial state, they should occur before it in the
files. This would make parsing the initial state easier. In particular, it could
then be handled more like other states.