Augusto and I polished the documentation and merged this.

The comment from Malte on msg8251 is basically what we discussed before. In
particular, we also mentioned that in the future we could allow different open
lists for both lazy and eager weighted A*. But for now, the point was simply to
replicate as an "eager version" the search engines used in LAMA. (This is the
experiment V3 on the third link in my last comment.)

To be honest, I believe it is my fault that this branch hasn't been merged yet.
I was not sure if I could merge it and I ended up forgetting to ask Jendrik and
Manuel if I could do so. (And I also did not have writing access to the main
branch at that time, which made it even easier to forget :)

It isn't really different implementations. astar, eager_greedy and eager_wastar
are all syntactic sugar for different parameter settings of the "eager" search
engine.

For older comments, you might have to look into the "Activity" tab on Bitbucket.

Once you guys are happy with the documentation, this can be merged, from my
point of view.

Ah, from different implementations, I would not expect the same tie-breaking
behavior anyways. It might still be good to add this to the documentation.

I don't see Jendrik's comments on bitbucket (?!?), so it is unclear to me
whether this is ready to get merged (apart from additional documentation).

Augusto mentioned this in msg7758, maybe he can elaborate.

The story as I recall it is that Weighted A* is supposed to interpolate between
greedy search and A*, but our greedy search and A* use different tie-breaking
rules, so Weighted A* cannot perfectly match both at the same time.

If I recall correctly, we thought that because they are both satisficing
algorithms, it may be better for Weighted A* to be closer to greedy search than
to A* in behaviour if we have to make a choice. Also, this is how the exising
lazy_wastar behaves.

Is this right, Augusto, or did I forget or wrongly remember something?

This seems to be an open branch in the main repository. What is missing to
integrate it into the default branch?

In what respect does wastar with w=1 not behave like astar?

The results look reasonable to me as well.

We should not forget to document that wastar with w=1 does not behave like astar.

I left some comments on Bitbucket. The experimental results look reasonable to 
me.

Thanks, Augusto! Who can take a look at the code and experiments?

About the experiments:

The first experiment compared "eager_wastar" with "eager(single([sum([g(),
weight(..." using LM-cut in a 5 minute time limit. The results seem equivalent,
the difference on coverage (that I noticed) happened on instances that are
finished almost at the time limit (i.e., instances that need ~299 seconds to be
solved)
Link: http://inf.ufrgs.br/~abcorrea/_issues/issue311/issue311-v1.html

The second experiment compare both versions of eager search -- "eager_wastar"
and "eager" with single open list -- with w=1 (which is equivalent to A*) to
"astar". As expected, "astar" performs much better because of the tiebreaking
open list.
Link: http://inf.ufrgs.br/~abcorrea/_issues/issue311/issue311-v2.html

In the third and last experiment, I just ran LAMA, but replacing all calls to
"lazy_wastar" to the new "eager_wastar". This leads to more out-of-time failures
and reduces drastically the number of out-of-memory instances.
Link: http://inf.ufrgs.br/~abcorrea/_issues/issue311/issue311-v3.html

I created a pull request for the issue. You can find it in the following link:
https://bitbucket.org/gutoblaas/downward/pull-requests/2/issue311/diff

I would appreciate if someone could find the time to check it. (I was also
wondering what should we add to the document synopsis of the new class)


I will send the reports of the experiments soon.

Discussing the implementation with Malte, we decided to first create
"eager_wastar" following the same idea of "lazy_wastar": using an alternation
open list with the possibility of preferred operators.

In this way, it is possible to try out an "eager" version of LAMA, which might
be the main use "lazy_wastar". However, in the case where "eager_wastar" has
weight=1, the performance/results won't be the same as "astar", due to the
different tie-breaking methods. Later on, we could create a new issue to extend
"eager_wastar" and "lazy_wastar" to also allow tiebreaking open lists, which
would allow us to treat "astar" as a specific case of "eager_wastar".

Commenting on the implementation strategy: looking at all the parsing code in
eager_search.cc and lazy_search.cc, there has to be a better way to handle this
than the way we did it before.

Maybe a generic way to rewrite the parse tree would be a better solution? I
don't know, but the search code parsers are already quite hard to maintain and
extend.

We currently have nice syntactic sugar to created lazy weighted A* searches, but
not to create eager weighted A* searches. This should be added.