Issue311

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

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

Messages
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 
me.
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
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
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:
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.
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
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.
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.
History
Date User Action Args
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