OK, code and documentation ripped out and General{Eager,Lazy}BestFirstSearch
classes renamed.

I've created a separate issue for parsing the dead-end statistics (issue221), so
this one is resolved.

I added dead-end statistics to all search algorithms.

@Jendrik: Can you add these to the evaluation scripts?
The relevant line is of the form:
Dead ends: 26 state(s).

It indeed looks like the difference in reported number of expansions is due to
the old search counting dead ends and the goal state as expanded, which the new
search (correctly) does not. 

The formula "expansions in new code = expansions in old code minus goal state
minus dead-end states" worked perfectly in the examples I tested in Airport and
FreeCell.

So this is ready to be closed. I'll rip out the old greedy search code and
remove it from the documentation. While I'm at it, I'll also rename the
eager/lazy search classes to something saner.

> Can the scripts be adapted to replace this with the memory limit (converted
> to the appropriate unit, e.g. multiplied by 1024 is the mem limit is in MB and
> this number is in KB) when the output is -1?

This is implemented now.

Does this difference only occur in domains that have dead-ends?

> Wouldn't it be easier to let the search code do that itself? Of course, 
> I have no idea how this is implemented at the moment...

If you mean the memory limit: I guess we might. It'd be nice to avoid it, since
all bets are off in signal handlers, and especially in out of memory conditions
which are frequently accompanied by some kind of memory corruption.

For example it's not clear at all to me that getrlimit would work properly in an
out-of-memory situation. I guess we could call getrlimit at the start of program
execution and stow away the info somewhere, but generally I would say that this
is the kind of code that is infinitely easier to do in Python than in C++.

Wouldn't it be easier to let the search code do that itself? Of course, 
I have no idea how this is implemented at the moment...

> I also checked the run.logs of an old and a new configuration 
> (heuristics don't match), but I can't say if this is expected.

This looks good, I think:
    Conducting best first search.
vs.
    Conducting lazy best first search, bound = 2147483647


> The run.log for assembly:prob01.pddl contains for config WORK-blind_lg:
> Simplifying transitions... done!
> Conducting lazy best first search, bound = 2147483647
> Initializing blind search heuristic...
> Best heuristic value: 1 [g=0, 1 evaluated, 0 expanded, t=0s]
> Peak memory: -1 KB
> caught signal 6 -- exiting

OK, this seems to be an out of memory condition which is reported in a strange
way. Can the scripts be adapted to replace this with the memory limit (converted
to the appropriate unit, e.g. multiplied by 1024 is the mem limit is in MB and
this number is in KB) when the output is -1?

OK, so I'd like to double-check what Erez wrote about the differences in
expansion count just to be 100% sure, and then I think the old search algorithm
can go. :-)

I checked the experiment's directory and found that the run scripts have 
the correct config options set. I you grep for old_greedy you won't find 
anything for a while since those runs come after the lazy_greedy runs.

I also checked the run.logs of an old and a new configuration 
(heuristics don't match), but I can't say if this is expected.

This is an example for old greedy:

Simplifying transitions... done!
Conducting best first search.
Initializing FF heuristic...
Simplifying 702 unary operators... done! [546 unary operators]
Initializing context-enhanced additive heuristic...
Best heuristic value: 40/139 [expanded 1 state(s)]

And an example for lazy greedy (different heuristic):

Simplifying transitions... done!
Conducting lazy best first search, bound = 2147483647
Initializing blind search heuristic...
Best heuristic value: 1 [g=0, 1 evaluated, 0 expanded, t=0s]
> 2) What is going on in the Assembly domain where the "memory" entry for one
> config is -30?
The run.log for assembly:prob01.pddl contains for config WORK-blind_lg:

Simplifying transitions... done!
Conducting lazy best first search, bound = 2147483647
Initializing blind search heuristic...
Best heuristic value: 1 [g=0, 1 evaluated, 0 expanded, t=0s]
Peak memory: -1 KB
caught signal 6 -- exiting

I looked into (3).
I think it's just a matter of different accounting.
In the old search, the number reported as expanded states is simply the size of 
the closed list.
In the new search, expansions actually counts the number of expansions 
performed. Since dead-end states are not expanded, they are not counted. I think 
this is the source of the variation in the numbers.

[Adding Gabi and Erez since this may be of more general interest.]

Thanks, looking encouraging!

There are three things I'd like to investigate:

1) Did we indeed run different search algorithms for lazy and old? (With results
so similar to each other, I'd better check. There's always the possibility of a
bug in command-line parsing etc.)

2) What is going on in the Assembly domain where the "memory" entry for one
config is -30?

3) There are a number of cases where the new search has slightly fewer
expansions; that is not fully consistent, but consistent enough for it to look
systematic. It would be good to check what the cause of this is; it's always
possible that thing likes this are due to wrong pruning.

Who can look into these? (Doesn't have to be the same person for everything.)

Once these three questions are resolved, I think we can get rid of the old
implementation.

I have created two reports for this issue. In the concatenated properties file I 
changed the config names from lg_blind to blind_lg etc. with sed to have the old 
and new implementations side by side. Here is the sed expression in case you need 
it: sed "s/\(config = .*\)\([ol]g\)_\([a-z_]*\)/\1\3_\2/"

the first part of the experiment has finished.

Works for me. Are you sure you're not using an outdated version of the code?
The names for the LM methods were changed (slightly) not too long ago.

The original string doesn't work either.

Downward/master/src/search$ ./downward --heuristic 
"hlm,hff=lm_ff_syn(lm_rhw())" --search "lazy_greedy(hlm, hff, 
preferred=(hlm, hff))" < output
Simplifying transitions... done!
ParseError: hlm,hff=lm_ff_syn(lm_rhw())
                               ^
Peak memory: 2172 KB
$

Have you tried the original string as given? The lm_ff_syn syntax returns two
heuristics; see http://www.fast-downward.org/ReusingHeuristics (last section)
for a bit of an explanation.

If that doesn't work, the most likely explanation is a bug in the emil-new
integration where the separate landmark generation method options were introduced.

Well, actually, that's the second most likely explanation. The most likely one
is that I messed up the option string. :-) But I think I copied this one
straight from the wiki.

Can it be the case that you have made a mistake here? Shouldn't that be

--heuristic "hlm=lm_ff_syn(lm_rhw())" --heuristic "hff=ff()" --search 
"lazy_greedy(hlm, hff, preferred=(hlm, hff))"   ?

That results in:

$PLANNER_WORK --heuristic "hlm=lm_ff_syn(lm_rhw())" --heuristic 
"hff=ff()" --search "old_greedy(hlm, hff, preferred=(hlm, hff))" < output

That string however causes a ParseError. What am I missing?

PS: to speed this up, one possibility would be running part of the
configurations on athlon_core.q and part of the configurations on xeon_core.q,
so that 64 and not just 32 cores can be used.

The only important constraint is that for each task and each of the new configs,
the same task with the matching old config is solved on the same kind of machine.

An easy split would be running configs 1.-4. on one queue and 5.-8. on another.

New configurations:

1. --search lazy_greedy(blind())
2. --search lazy_greedy(ff())
3. --search lazy_greedy(cea())
4. --search lazy_greedy(ff(), cea())
5. --heuristic hff=ff()
   --search lazy_greedy(hff, preferred=(hff))
6. --heuristic hcea=cea()
   --search lazy_greedy(hcea, preferred=(hcea))
7. --heuristic hff=ff()
   --heuristic hcea=cea()
   --search lazy_greedy(hff, hcea, preferred=(hff, hcea))
8. --heuristic hlm,hff=lm_ff_syn(lm_rhw())
   --search lazy_greedy(hlm, hff, preferred=(hlm, hff))

Each of these should be compared to the corresponding old configuration where
lazy_greedy is replaced by old_greedy. Note that the log parsing might need to
be adapted for the old code and that I'm not sure if numbers like "generated
states" have matching meanings in all cases, but we can worry about that once we
have the data.

(If you use shell=True, all options including parentheses must be protected by
quotes.)

All option strings above are untested -- I'd strongly suggest testing on a very
small suite first (e.g. only one or two tasks).

The final suite to test this on should be ALL (all heuristics above support
conditional effects and derived predicates).

Which configurations should be compared exactly? Ideally, can you give 
me the command line strings?

We should get rid of the old_greedy search algorithm:
http://www.fast-downward.org/SearchEngine#Old_lazy_greedy_best_first_search

But before doing this, we should make sure that the equivalent new search
algorithms doesn't have serious performance issues (runtime or memory). This is
mostly a matter of comparing matching pairs of algorithm configurations.

Jendrik, do you think you have time for this?