As discussed via email, let's revisit this after the ICAPS deadline.

Malte has some very good points. 
I suggest we do a code review via Skype.

I've changed the title of this and assigned to myself (although I'm sure I'll
need input from Erez and Gabi). There may be some structural changes, so before
I mess something up, is there any other work on the search algorithms and
related code currently going on that I should be aware of?

I did a quick test with one Pathways instance that was causing problems, and at
least for that instances the performance problem did disappear.

The behaviour regarding what's added where still looks different to the old best
first search to me, though. The old best first search
(best_first_search.cc@3487) would collect all preferred operators from all
heuristics (including duplicates) into an array, then add all elements of that
(including duplicates) into the preferred open queue and all operators into the
general open queue, the latter in the order in which they come from the
successor generator.

A significant difference between the old and new version of the code is the
behaviour if some heuristic declares a state to be a dead end. The old code
would only remove a state from consideration *for the heuristics that declare it
a dead end*. The new code before Erez's most recent patch would ignore a state
as soon as *one* heuristic declares it a dead end, and the current code ignores
such states if they are non-preferred, but still considers them if they are
preferred.

I don't really understand what the new implementation does with that
"open_list->evaluate(new_g...)" line, but given that it first handles all
preferred operators and then all non-preferred ones, it looks like preferred
operators are always added to the general queue first, before all non-preferred
operators, which wasn't done before.

I tried to dig into this a bit more deeply and browsed around the new code a
bit, and I think the new code needs a code review before we should go further.
Here's a few things that bothered me (no particular order):

* The new header files follow a different convention for the #ifndef/#define
  macro names than the old ones.
* The difference between "general_lazy_best_first_search" and
  "lazy_best_first_search_engine" is that the former is general whereas the
  latter is greedy (if I understand the correctly), but the names of the
  classes don't really show that. (The word "Greedy" should show up somewhere.)
* There are three TODOs in lazy_best_first_search_engine.cc that I think
  shouldn't be there. (Or at least I don't understand what they are about.)
* LazyBestFirstSearchEngine::initialize has a bug if heuristics.size() == 0
  and preferred_operator_heuristics.size() == 1.
* GeneralLazyBestFirstSearch::generate_successors() keeps recomputing the
  same parent state buffer for every successor.

I think the code needs cleaning up, and there's little point in experimenting
before the cleanup, because we'd have to redo the experiments after the cleanup
anyway.

I changed the order successors are inserted into the open list (in lazy general
search) to the way it was in the old best first search. Results on pathways are
now exactly the same as the old search (up to the number of expanded nodes).
It might be worth investigating the effect of the order of preferred operators
sometime.

The preferred operators are not generated in any particular order, so if order
matters, then we were lucky before. One way to test this would be to randomly
permute the preferred operators in both the old (r3487) and new (r3555) code
before insertion and re-run some tests on Pathways.

I took a closer look and saw that there were a few configurations without 
preferred operators, and the difference between them in the total number of 
problems solved is no more than 2.
This seems to indicate that we are doing something different with preferred 
operators. Does anyone have any idea if the order of the preferred operators is 
important?

One thing I can think of is that the order in which preferred operators are 
inserted into the open list is different. From the few tests I ran without 
preferred operators, the results were the same as the old search.
Malte - if you can run a few comparisons without preferred operators (I don't 
think we need all these configurations, just 1 or 2), it might allow us to focus 
our efforts.

I should point out that the extreme difference in the fFlLz configuration (i.e.
LAMA's heuristics) may also have something to do with the synergy (or lack
thereof) between the FF/Landmark heuristics in the versions of the code that we
tested. I know there was some back and forth there, and I don't know offhand
what was actually in these two revisions we tested.

I'm attaching the coverage results for corresponding configurations of the old
lazy search from r3487 and the new lazy search from current trunk (more
precisely, r3555).

Summary: I tested 11 planner configurations. Considering only the most basic
measure, total number of tasks solved, we get

 * 3x improvements: cCz (+4), fz (+2), lLz (+5)
 * 7x worse performance: cCfFz (-4), dDz (-7), dz (-1), fFlLz (-28), fFz (-16),
yYz (-5), yz (-1)
 * 1x same performance: b

So overall performance is worse. In particular, the five best configurations
(cCfFz, dDz, fFlLz, fFz, yYz) all get worse.

Looking at particular result, it is striking that in the Pathways domain, all
five top configurations get *much* worse (and no top configuration gets better).
Indeed, without Pathways, three of these five configurations would actually be
improved. So I guess the next step should be to try to discover what goes wrong
in Pathways.

I don't know the new code, so I'm assigning this back to Erez. If anyone else
wants to look into this or if you need detailed data, do speak up.

Malte - please test the new lazy best first search.

I won't get to do this soon. Feel free to assign to me, but then it'll sit idle
for a while.

I implemented lazy best first search, and also two derived classes: lazy WA* and
lazy greedy best first search.
I would appreciate it if Gabi or Malte could run some tests, since I don't have
any free servers at the moments.
To use lazy greedy best first search, just add z (i.e. fFlLz).
To use lazy WA* just add w with weight (i.e. fFlLw10)

I am going to implement lazy general best first search using the new open lists

Should this remain assigned to Erez?

Our original plan was to integrate the "preferred" branch later, after "lama",
"FDtech" and "everything". Hence preferred operators were only supposed to be
added to the eager search later. (None of these branches supported eager search
with preferred operators. Eager search was only used for optimal planning, for
which we don't need preferred operator support.)

I don't mind changing that plan, but then we should talk about how exactly we
want to implement preferred operators for eager search. (Store them upon
evaluation or recompute them upon expansion.)

Both approaches have pros and cons. One problem with storing them upon
evaluation is that I'm not sure how to do it without using extra space in the
cases where we *don't* use preferred operators (e.g. vanilla A*).

I don't think that eager is done because it does not capture everything that we
have in the good old (lazy greedy) best first search (like preferred operators).

Eager is done, lazy not yet.

Implement lazy & eager general (additive) best first search.
The weights of g and h should be parameters.