The changes look fine to me.
I will do a performance evaluation and compare to results I have from the new 
selective-max experiment after we integrate the emil-new changes (since I had 
both changes in that experiment).

Marking as resolved.

OK, I've integrated the single-changeset patch as branch "issue112", which is
now part of the default on master.

The complete diff is at http://hg.fast-downward.org/rev/6bcaab08c16b -- Erez,
it'd be good if you could have a look so that you know what I changed (mostly
cosmetic issues to make names more in line with how things are called in the
rest of the code etc.)

Erez, if you want to do a performance evaluation of this, let me know. Otherwise
we can mark this one as resolved.

No problem

On Oct 31, 2010 9:41 PM, "Malte Helmert" <downward.issues@googlemail.com>
wrote:

Malte Helmert <helmert@informatik.uni-freiburg.de> added the comment:
Hmmm, seems to be working fine, but I'm a bit reluctant to push this to
master
as is, since there are altogether 14 changesets with quite a few
back-and-forth
edits. Any objections to me turning these 14 changesets into one single
changeset that doesn't retain all the intermediate stages?

It's not actually larger than the largest of the individual changes in
there,
and our history would look much nicer when we have to work with this in the
future (for debugging etc.)

_______________________________________________________
Fast Downward issue tracker <downward.issue...

Hmmm, seems to be working fine, but I'm a bit reluctant to push this to master
as is, since there are altogether 14 changesets with quite a few back-and-forth
edits. Any objections to me turning these 14 changesets into one single
changeset that doesn't retain all the intermediate stages?

It's not actually larger than the largest of the individual changes in there,
and our history would look much nicer when we have to work with this in the
future (for debugging etc.)

That's a good point. I'll give this some more thought.

On Sun, Oct 31, 2010 at 8:31 PM, Malte Helmert <
downward.issues@googlemail.com> wrote:

>
> Malte Helmert <helmert@informatik.uni-freiburg.de> added the comment:
>
> I would argue that what is put into the key by
> AlternationOpenList::remove_min
> is wrong. If you look at the paper by Gabi and me, the "key" should be the
> vector of h values, not the scalar h value for the particular heuristic
> that was
> selected for this particular iteration.
>
> Of course this causes further problems when using alternation over
> alternation,
> alternation over tie-breaking or other kinds of nested open queues. The
> underlying reason for this is that it's maybe not a good idea to shoe-horn
> the
> notion of a "vector<int> key" onto all open list implementations, since
> this is
> not really the reality. (For example, some of them really have a single int
> key;
> others might have vectors of vectors, etc.)
>
> Maybe it's hopeless to define a general notion of "open list key" at the
> moment;
> at least I don't know what a good definition would be. In that case, we
> should
> only implement the cases where we do have a reasonable notion and let the
> cases
> that make no sense or are too hard to implement (e.g. alternation) fail.
>
> I'll adapt the current implementation of the LM-A* integration along this
> lines,
> but let me know what you think if you have comments.
>
> _______________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://issues.fast-downward.org/issue112>
> _______________________________________________________
>

-- 

--------------------------------------------------------------
"Adventure is just bad planning."
    Roald Amundsen
    Norwegian Arctic & Antarctic explorer
    (1872 - 1928)
--------------------------------------------------------------

OK, this is tentatively done. I'll run some (very) basic tests, then add this to
master. Erez, it'd be good if you could run some more serious performance tests
on this at some point once it's committed.

I would argue that what is put into the key by AlternationOpenList::remove_min
is wrong. If you look at the paper by Gabi and me, the "key" should be the
vector of h values, not the scalar h value for the particular heuristic that was
selected for this particular iteration.

Of course this causes further problems when using alternation over alternation,
alternation over tie-breaking or other kinds of nested open queues. The
underlying reason for this is that it's maybe not a good idea to shoe-horn the
notion of a "vector<int> key" onto all open list implementations, since this is
not really the reality. (For example, some of them really have a single int key;
others might have vectors of vectors, etc.)

Maybe it's hopeless to define a general notion of "open list key" at the moment;
at least I don't know what a good definition would be. In that case, we should
only implement the cases where we do have a reasonable notion and let the cases
that make no sense or are too hard to implement (e.g. alternation) fail.

I'll adapt the current implementation of the LM-A* integration along this lines,
but let me know what you think if you have comments.

Done.
open_list.remove_min(vector<int> *key) - if the passed vector is non-null, it 
puts the removed key in there. Default value is NULL.

pushed in changeset  bd5e9e3f253c

> The reason I didn't create a min_key() method is that remove_min() actually
> does a bit of work in some cases (alternation, pareto). In fact, with pareto
> open lists, min_key() isn't even well defined, since there's a random choice
> between several minimum keys involved. An alternative would be to pass a
> vector to remove_min, where it would place the key of the removed entry (that
> is, it would be   Entry remove_min(vector<int> &keys)). Let me know if you
> think this is better.

Yes, that would be better. Let me know when an updated version is ready.

Now that the option is only available for A*, the preferredness when inserting
reevaluated states into the open list should be "false", since A* doesn't have
preferred states.

The basic idea behind LM-A* is that a state can have it's h-value increase when 
a new path to it is found. However, we don't want to re-evaluate a state every 
time a new path to it is found so:
1. When a new path to a state is found, we store the information from the path 
(reach_state)
2. When we pop a state from the open list, we check if a new path to it has been 
found since it was placed there.
2.1 If a new path has been found, we evaluate the heuristic again, and if it 
increases, we update the h-value, push the state into the open list (with the 
new h-value), and get another state.
Now, suppose two copies of state s are in the open list (from two different 
paths). When we pop the first copy, we update the h-value of s, and then push it 
again with the new h-value. Then, the second copy of s is popped. Since we can't 
update the h-value inside the open list, this copy was popped prematurely, using 
the old h-value. 
This is why when we pop a state from the open list, we first make sure its h-
value is up to date.


To address the comments:


The reason I didn't create a min_key() method is that remove_min() actually does 
a bit of work in some cases (alternation, pareto). In fact, with pareto open 
lists, min_key() isn't even well defined, since there's a random choice between 
several minimum keys involved. An alternative would be to pass a vector to 
remove_min, where it would place the key of the removed entry (that is, it would 
be   Entry remove_min(vector<int> &keys)). Let me know if you think this is 
better.


I got rid of the mpd option for general eager search. It is now valid only for 
A*. 


I added calls to mark_not_eval() after a node is evaluated (that was an 
oversight before, they were there in the original implementation). 


I didn't want to add a reevaluated_states counter, since it's not clear whether 
a state that is reevaluated 3 times should count as 1 or 3. Instead, I added an 
evaluations counter, which counts the number of calls to evaluate(), so if there 
are 2 heuristics, this should be twice the number of evaluates states (unless 
there are real reevaluations).


I merged the two blocks of mpd in fetch_next_node into 1.


I got rid of the useless comment about mpd.


I changed need_eval to bool:1.


I push everything to my repository, it's changeset d356927d8d60

> need_eval() should not test against 1 but do a "return
> info.need_eval" instead. This is both clearer regarding intent since we don't
> use 0 and 1 but proper boolean values and more efficient, since static-casting
> an int into a bool is guaranteed to be a no-op.

Sorry, that was garbled; the part after "since static-casting" was left over
from an older text.

After reading around a bit, it's actually perfectly legitimate to use

    bool need_eval: 1;

instead of unsigned int, which is even clearer. The caveat is that it's not
guaranteed that a compiler can merge an int field with a bool field to save
space, but

 a) g++ does, and
 b) there is no guarantee that it can merge an int field with an unsigned int
    field either.

I think this would actually be a good place for a compile-time assertion to
verify that the node info struct has the intended size. (But that is a separate
issue.)

Some small comments I forgot:

    bool use_multi_path_dependence; // whether to use multi-path dependence

That's a useless comment as the name is self-explanatory. Should be removed.

In SearchNodeInfo::SearchNodeInfo, need_eval(0) should be "false", not 0, and
similarly true and false should be used instead of 1 and 0 in mark_to_eval and
mark_not_eval. need_eval() should not test against 1 but do a "return
info.need_eval" instead. This is both clearer regarding intent since we don't
use 0 and 1 but proper boolean values and more efficient, since static-casting
an int into a bool is guaranteed to be a no-op.

> I have yet to be convinced that we need the get_last_key_removed interface at
> all.

In fact it looks like the only place where this is called is *right after a
remove_min operation*. Then why not give the open lists a bog-standard "min_key"
method that returns the *current* minimum key instead?

Two issues with the "mark_to_eval" code:

 * Currently, if we use LM-A* with the LM heuristic, it looks like every node
   that ends up being expanded is evaluated at least twice, once in step() as
   it is generated and once in fetch_next_node() as it is expanded. The reason
   for this is that as the node is generated, its h value is computed yet still
   mark_to_eval is called, so the value is marked as dirty even though it is
   up to date. Hence we get two evaluations even when only one path to this
   node is generated, which is unnecessary. To fix this, I think that
   the test
   if (eval_change)
       succ_node.mark_to_eval();
   should additionally check that this is not a new node.

 * The need_eval marker is never cleared, and hence if a path-dependent
   heuristic *once* says that it wants an h value to be reevaluated, then
   the h value of that state will be reevaluated *every time* in the future,
   even if subsequently reach_state returns false. To fix this, need_eval
   should be cleared when the h value is computed. (Actually, this would
   automatically also fix the previous issue if it's done also upon the first
   h value computation.)

A few other issues with the code:

 * pushed_f is declared and computed but never used
 * pushed_h is defined in a more general scope than necessary [SA 18] and
   receives an unnecessary default value that is always overridden
 * We currently use "evaluated" to keep track of the total number of
   states evaluated, which is useful info to keep. So I think the reevaluations
   should use a new counter ("re-evaluations"?) instead.
 * It's not clear to me why re-evaluations always set "preferred=true" in the
   call to open_list->evaluate. I don't think I have something better to
   recommend either, but at the very least this warrants a comment, not just
   in the code but also in the description of the mpd option on the wiki.
 * To keep the mpd code as localized as possible, I think it'd be preferable
   to have the two "if (use_multi_path_depence ...)" blocks in fetch_next_node
   combined into one. I don't see why the currently first one cannot be moved
   into the currently second one -- it does nothing that has to be done if the
   node is already closed, I think.

A final concern is that the search code currently has too much duplication and
quite a few comment corpses that reflect old assumptions that are no longer true
(e.g. there is a comment that states that we don't need to reopen because our
heuristic is consistent -- this is wrong because we *do* have inconsistent
heuristics, and we *do* actually reopen). I can take care of these things later
though; better not to conflate those changes with the LM-A* patch.

Erez, can you make some changes that take the above points into account and push
them to your bitbucket branch?

If you do an
# hg update -r 32fca20e2a62
[work on code]
# hg commit
# hg push
this should end up in the correct place in your repository.

I just looked at the proposed changes (changeset 32fca20e2a62 in Erez's repository).


I have yet to be convinced that we need the get_last_key_removed interface at
all. It seems wrong for the open list to do store information on the search
algorithm's behalf that doesn't logically belong into the open list at all.
(Open lists should *not* need to care about the history of values that have been
stored in them.)

Also, the "mpd" option is exposed as a general option of eager search in
GeneralEagerBestFirstSearch::create, but the code

            assert(open_list->get_last_key_removed().size() == 2);
            pushed_f = open_list->get_last_key_removed()[0];
            pushed_h = open_list->get_last_key_removed()[1];

suggests that it is only valid when combined with a particular kind of open list
(namely, the ones we use for A*). This limitation should either be

 * lifted, or
 * documented in the code and enforced.

If the latter is preferable, note that assertions like the one above should only
be used to check for internal program errors since they are ignored by default
(only "make debug" cares about them). Wrong command-line options are user errors
and should be tested in the command-line parser. (Of course, having relevant
assertions *in addition* to that is fine.)


Indepedently of the comments above, it's not clear to me why the code does what
it does. Erez, can you send a high-level explanation, e.g. pseudo-code,
explaining what was changed in step and fetch_next_node and why?

Assuming you've set up meld,
# hg meld -c 32fca20e2a62
gives you a nice side-by-side diff.

This isn't part of the LM-A* implementstion, just something I did later to
 test it (like Malte suggested(

On Fri, Aug 27, 2010 at 1:28 PM, Gabi Röger <downward.issues@gmail.com> <
downward.issues@googlemail.com> wrote:

>
> Gabi Röger <roeger@informatik.uni-freiburg.de> added the comment:
>
> I reviewed the get_last_key_removed() method in the open lists and it looks
> ok.
>
> Erez, I also saw that you added an id to every search node. For what is
> this used?
>
> ----------
> nosy: +gabi
>
> _______________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://issues.fast-downward.org/issue112>
> _______________________________________________________
>

-- 

--------------------------------------------------------------
"Adventure is just bad planning."
    Roald Amundsen
    Norwegian Arctic & Antarctic explorer
    (1872 - 1928)
--------------------------------------------------------------

I reviewed the get_last_key_removed() method in the open lists and it looks ok.

Erez, I also saw that you added an id to every search node. For what is this used?

I had to modify some core code (add a need_eval member to SearchNodeInfo, and add 
a get_last_key_removed() method to [all] open lists), 
so I did this in a new branch called trunk-integration.