Title create "eager_wastar" analog of "lazy_wastar"
Priority feature Status resolved
Superseder Nosy List augusto, gabi, jendrik, malte, manuel, salome
Assigned To augusto Keywords
Optional summary

Created on 2011-12-21.14:11:35 by malte, last changed by jendrik.

msg8294 (view) Author: jendrik Date: 2018-12-13.16:29:09
Augusto and I polished the documentation and merged this.
msg8255 (view) Author: augusto Date: 2018-12-12.12:06:53
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 :)
msg8254 (view) Author: malte Date: 2018-12-12.11:39:10
It isn't really different implementations. astar, eager_greedy and eager_wastar
are all syntactic sugar for different parameter settings of the "eager" search
msg8253 (view) Author: jendrik Date: 2018-12-12.11:38:52
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.
msg8252 (view) Author: gabi Date: 2018-12-12.11:34:28
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).
msg8251 (view) Author: malte Date: 2018-12-12.11:30:47
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?
msg8249 (view) Author: gabi Date: 2018-12-12.11:18:34
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?
msg7917 (view) Author: manuel Date: 2018-10-08.09:42:59
The results look reasonable to me as well.

We should not forget to document that wastar with w=1 does not behave like astar.
msg7911 (view) Author: jendrik Date: 2018-10-07.20:31:50
I left some comments on Bitbucket. The experimental results look reasonable to 
msg7814 (view) Author: malte Date: 2018-09-30.17:21:56
Thanks, Augusto! Who can take a look at the code and experiments?
msg7807 (view) Author: augusto Date: 2018-09-27.17:00:52
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

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.

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.
msg7806 (view) Author: augusto Date: 2018-09-27.16:49:28
I created a pull request for the issue. You can find it in the following link:

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.
msg7758 (view) Author: augusto Date: 2018-09-21.18:15:10
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".
msg2512 (view) Author: malte Date: 2013-06-25.15:08:20
Commenting on the implementation strategy: looking at all the parsing code in and, 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
msg2005 (view) Author: malte Date: 2011-12-21.14:11:35
We currently have nice syntactic sugar to created lazy weighted A* searches, but
not to create eager weighted A* searches. This should be added.
Date User Action Args
2018-12-13 16:29:09jendriksetstatus: reviewing -> resolved
messages: + msg8294
2018-12-12 12:06:53augustosetmessages: + msg8255
2018-12-12 11:39:10maltesetmessages: + msg8254
2018-12-12 11:38:52jendriksetmessages: + msg8253
2018-12-12 11:34:28gabisetmessages: + msg8252
2018-12-12 11:30:47maltesetmessages: + msg8251
2018-12-12 11:18:34gabisetnosy: + gabi
messages: + msg8249
2018-10-08 09:42:59manuelsetmessages: + msg7917
2018-10-07 20:31:50jendriksetmessages: + msg7911
2018-09-30 17:21:56maltesetmessages: + msg7814
2018-09-27 17:00:52augustosetmessages: + msg7807
2018-09-27 16:49:28augustosetstatus: chatting -> reviewing
assignedto: salome -> augusto
messages: + msg7806
2018-09-21 18:15:10augustosetmessages: + msg7758
2018-09-21 16:29:12augustosetnosy: + augusto
2016-09-07 12:42:52manuelsetnosy: + manuel
2014-12-17 21:06:39jendriksetnosy: + jendrik
2013-06-25 15:08:20maltesetmessages: + msg2512
2013-06-25 15:02:58gabisetassignedto: malte -> salome
nosy: + salome
2011-12-21 14:11:35maltecreate