Thanks! I didn't realize that succ_node's g value was uninitialized at this
point. I now checked the code to see that the initialization only happens later
in "open", and this clears it up. (Makes sense in retrospect.)

I find this interplay between the search space and the open lists where both
need the successor node's g value a bit tricky (and hence bug-prone). I don't
have a good solution for the moment, but it would be good if we found a way to
simplify this code (or encapsulate the trickiness) in the future. I'll add a
comment.

Just to make sure, this is the change I am talking about (output from - svn
diff -r 4180:4181)
Index: general_eager_best_first_search.cc
===================================================================
--- general_eager_best_first_search.cc (revision 4180)
+++ general_eager_best_first_search.cc (revision 4181)
@@ -120,8 +120,7 @@
             }
             search_progress.inc_evaluated();

-            open_list->evaluate(succ_node.get_g(), is_preferred);
-
+            open_list->evaluate(node.get_g() + op->get_cost(),
is_preferred);
             bool dead_end = open_list->is_dead_end() &&
open_list->dead_end_is_reliable();
             if (dead_end) {
                 succ_node.mark_as_dead_end();
@@ -132,7 +131,6 @@
             int succ_h = heuristics[0]->get_heuristic();
             succ_node.open(succ_h, node, op);

-
  open_list->insert(succ_node.get_state_buffer());
             search_progress.check_h_progress(succ_node.get_g());

This change is there because the call to open_list->evaluate now come before
succ_node.open, so calling open_list->evaluate(node.get_g()..) would pass -1
instead of g (since it's not initialized yet).

On Sun, Jun 6, 2010 at 7:18 PM, Malte Helmert <
downward.issues@googlemail.com> wrote:

>
> Malte Helmert <helmert@informatik.uni-freiburg.de> added the comment:
>
> I think you're talking about the change in r4180, which as I said is fine.
>
> I'm talking about the change in r4181.
>
> _______________________________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://alfons.informatik.uni-freiburg.de:8088/downward-issues/issue88>
> _______________________________________________________________________
>

-- 

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

I think you're talking about the change in r4180, which as I said is fine.

I'm talking about the change in r4181.

The call to succ_node.open (line 132) comes after the call to open_list->evaluate 
(line 123), which needs the g-value of the state. 
This was a bug before, which is now fixed.

Erez: the fix in r4180 I understand.

About r4181, in which situations does this make a difference? I see that the new
code behaves differently from the old one (the number of expansions in the
example you mention in msg316 changes), but why? Under what circumstances can
succ_node.get_g() be different from node.get_g() + op->get_cost() here?

(I want to make sure there is no data inconsistency somewhere that might also
bite us somewhere else.)

Negative -- my issue is unrelated. Sorry for the confusion.

This may fix an issue I'm currently investigating around the dead-end detection
in LM-CUT and RPG heuristics. I'll try to confirm by week's end.

Note to self: the fixes were committed in r4180 and r4181.

We discovered a bug where A* in the presence of dead-ends does not behave properly. 
This bug is not obvious in release mode, since the assertions are compiled away.
However, in debug mode, A* + LM-CUT on AIRPORT-14 fails with an assertion error
in the call to get_heuristic().
I fixed this issue, and possibly another issue which I discovered when debugging
this, where A* expanded states with a larger f-value than the optimal solution.
This was fixed by changing the order between open-list->evaluate(...) and
succ_node.open(), and computing the g in the call to open-list->evaluate(...).
This might impact experiments that were run before.