Excellent! I'll close this one. Looking at the diff, I noticed a problem with
the code that sets the bound, though, but I'll make that a separate issue since
this is an unrelated bug.

I changed the bound default to numeric_limits<int>::max(), and got rid of
the -1.

On Thu, Mar 18, 2010 at 9:35 AM, Malte Helmert <
downward.issues@googlemail.com> wrote:

>
> Malte Helmert <helmert@informatik.uni-freiburg.de> added the comment:
>
> Here's my thoughts: if the last plan found had a cost of 100, then from
> then we
> only need to keep states with g < 100, or equivalently, g <= 99. Once we
> reach g
> = 100, there is no way we can find a better solution than before, even
> through
> zero-cost operators. Am I missing something?
>
> BTW, I'm not too concerned about whether we use <= or <, although I have a
> slight preference for <= since this is what IDA* does, which is kind-of
> similar.
> But no matter what we choose, it should be documented somewhere in the *.h
> file.
>
> I have a slightly stronger preference for -1 vs. numeric_limits<int>::max,
> where
> I prefer the latter (because it is harder to have bugs with that -- it's
> easy to
> forget to test against -1 in some place, and I had bugs like that before in
> other, similar parts of the code).
>
> _______________________________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://alfons.informatik.uni-freiburg.de:8088/downward-issues/issue82>
> _______________________________________________________________________
>

-- 

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

Here's my thoughts: if the last plan found had a cost of 100, then from then we
only need to keep states with g < 100, or equivalently, g <= 99. Once we reach g
= 100, there is no way we can find a better solution than before, even through
zero-cost operators. Am I missing something?

BTW, I'm not too concerned about whether we use <= or <, although I have a
slight preference for <= since this is what IDA* does, which is kind-of similar.
But no matter what we choose, it should be documented somewhere in the *.h file.

I have a slightly stronger preference for -1 vs. numeric_limits<int>::max, where
I prefer the latter (because it is harder to have bugs with that -- it's easy to
forget to test against -1 in some place, and I had bugs like that before in
other, similar parts of the code).

I made all of the suggested changes (except for bound == -1) and commited.
Actually, Malte's comment about <= for the bound made me realize that we have a
problem with the bound with 0-cost actions, when we're doing iterated searches
(like in LAMA with w=1 at the end).
If we prune when g > bound, we might keep ending up with the same solution over
and over.
If we prune when g >= bound, we might prune some solutions, since there might be
a 0-cost path to a goal.

Any idea?

Looks good in general! Feel free to commit, although in the near future, 
please everyone don't add new features before we've reduced our bug 
count and/or have come up with some kind of automated performance test 
to evaluate the changes.

Some suggested minor changes:

 * If there's no particular reason why a method should return something,
   it should be void. IOW, get_successors should be void.
 * The name "get_successors" isn't great, since really it gets the
   operators for the successors, not the successors themselves. I was a bit
   confused about having both "get_successors" and "generate_successors".
   Suggest changing "get_successors" to "get_successor_operators".
 * ops.insert() should be ops.assign() here. (That's clearer, I'd say.)
   Actually, no -- if could just be "ops = all_operators". Actually, no
   again -- no need to be O(n) when you can be O(1): It should be
   ops.swap(all_operators);
 * operators[i]->unmark() should only be called for marked operators
   (although I know it doesn't matter with the current implementation),
   so I suggest changing the loop in generate_successors to:
    for(int i = 0; i < operators.size(); i++) {
        int new_g = current_g + operators[i]->get_cost();
        bool is_preferred = operators[i]->is_marked();
        if (is_preferred)
            operators[i]->unmark();
        if (bound == -1 || new_g < bound) {
            open_list->evaluate(new_g, is_preferred);
            open_list->insert(make_pair(current_state_buffer, operators[i]));
        }
    }
    (BTW: Wouldn't it be good to use numeric_limits<int>::max() for the -1
    bound to avoid the case distinction? Also, I'd prefer a "<=" test for
    the bound.)


Formatting etc. -- please pay attention to these! I find inconsistently
formatted code very distracting.
  * Long lines should be split. The absolute limit should be 80 characters;
    I prefer splitting already at 72 or so.
  * Space after commas (see changed line in the constructor).
  * It should be "} else {".
  * "state_var_t* current_state_buffer" should be "state_var_t *
    current_state_buffer"
  * There should be no extra parentheses in
    "if((bound == -1) || (new_g < bound))" (I know they were there before,
    but certainly not by me. :-)

Hi Guys,
I implemented different types of successor orderings for lazy GBFS.
In addition to being useful, it also cleans up the code for generate_successors
a bit. 
The svn diff is attached, please take a look and let me know if you have
objections to checking this in. BTW, pref_first is the option we use now, and is
the default.