Sorry for the many emails. I've uploaded the reports for this issue in bzipped
form for posterity since the _tmp_files links in the messages below are not
permanent.

All done. Thanks, everyone!

After merge, I think it could be a good idea to try that with state symmetry 
pruning.

> ...and we still need to test this on non-optimal configurations (oops!).
>
> This changes all search algorithms, and our tests so far only test eager
> search. I'll start an additional test.

Done and looking good (few changes, but on average: more problems solved,
faster, less memory):

http://ai.cs.unibas.ch/_tmp_files/helmert/report-compare-issue344-exp14.html

Florian, if you also think this is read to merge, please let me know. (I still
have to add the experiment scripts; am planning to do so today.)

> Sure, I can do the review. Is the code available in the master repository?

I just pushed it.

>> 1. Make the new code prettier.
> Is there anything specific that should be prettier? If not, I don't think we
> should add an issue for this.

Yes, there are some specific pointers in the changed code. You're right: if we
open an issue, it should be specific about what should be cleaned up.

>> 2. Further improvements to space efficiency. From memory:
> Should I add an issue for this?

Yes, this might be useful.

> I guess 3. and 4. have the same underlying issue: we should think about how to
> handle temporary states. That is, should they be registered, should there be a
> way to unregister them, or should we use temporary registries. Me suggestion
> would be to add one issue for both of them.

Agreed.

> I suggest that someone (Florian?) conducts a review of the new code,
> and once they're happy, we can merge.
Sure, I can do the review. Is the code available in the master repository?

> For future reference, here's the ones I can think of:
> 
> 1. Make the new code prettier.
Is there anything specific that should be prettier? If not, I don't think we
should add an issue for this.

> 2. Further improvements to space efficiency. From memory:
> - could make the vector<bool> for landmarks more compact
> - could reduce stored handles to just integers
> - could remove the data pointer from state representation
> There may be more opportunities described in the code.
Should I add an issue for this?

> 3. Look into the interaction of iPDB and state registries, in particular getting
> rid of the memory penalty.
>
> 4. Look into the interaction of selmax and state registries, making the
> heuristic work again.
I guess 3. and 4. have the same underlying issue: we should think about how to
handle temporary states. That is, should they be registered, should there be a
way to unregister them, or should we use temporary registries. Me suggestion
would be to add one issue for both of them.

...and we still need to test this on non-optimal configurations (oops!).

This changes all search algorithms, and our tests so far only test eager search.
I'll start an additional test.

Regarding how to proceed: I suggest that someone (Florian?) conducts a review of
the new code, and once they're happy, we can merge. The remaining TODOs can be
left for other issues, I think.

For future reference, here's the ones I can think of:

1. Make the new code prettier.

2. Further improvements to space efficiency. From memory:
- could make the vector<bool> for landmarks more compact
- could reduce stored handles to just integers
- could remove the data pointer from state representation
There may be more opportunities described in the code.

3. Look into the interaction of iPDB and state registries, in particular getting
rid of the memory penalty.

4. Look into the interaction of selmax and state registries, making the
heuristic work again.

Results are here (warning, 40 MB):
http://ai.cs.unibas.ch/_tmp_files/helmert/report-compare-issue344-exp13.html

Interpretation:

1. Generally speaking, very good. We no longer lose coverage except for one h^2
task where we seem to be unlucky with the timeout (possibly due to the typical
runtime fluctuations on the grid).

2. Coverage increases by 4 for blind search because this latest version is a bit
more memory-efficient than our old code. We tend to be faster and use less
memory across the board.

3. Most configurations (e.g. LM-Cut, iPDB) either have the same or +1 coverage.

4. BJOLP's coverage increases by 5, and it is quite a bit faster, presumably due
to the more compact storage and faster access for the landmark information.

5. I had to disable the learning code because I removed Heuristic::reset, which
I was never very happy with and whose interaction with the state registry is
unclear. Hence the selmax results. This needs to be rethought once we have a
better idea of how to tie a particular search space to a search algorithm/heuristic.

6. The iPDB configuration is the only one with a memory penalty. I assume this
is due to the way the sampling uses the state registry, and it's something we
should look into at some point.

Right -- I made an initial test, and the admissible landmark heuristic looks good.

LM-Cut loses two tasks (the two openstacks tasks from msg2562). I have one more
space optimization that I would like to try out, so I'll post the results later
onece I have data for that.

We should probably test something that uses per-state information - maybe the 
landmark heuristic?

There was a bit of offline discussion for this issue, and I tried out some
things to reduce the memory footprint of the changes. Here is an experiment with
blind search and various code versions:

    http://ai.cs.unibas.ch/_tmp_files/helmert/issue344-improvements.html

Explanations for the different versions (numbering follows order in the HTML file):

1. base: code before issue344
2. initial: initial implementation for issue344 for which Florian presented
   the results
3. search-space-holds-objects: builds on 2., but
   SearchSpace stores SearchNodeInfo objects directly rather than pointers
4. segmented-vector: builds on 2., but
   PerStateInfo doesn't use a plain vector but a different data structure that
   deals more gracefully with fragmented memory and doesn't need as much memory
   during resizing operations
7. tighter-registry: builds on 2., but
   State Registry stores StateRepresentation objects directly rather than
   pointers
5. combination of 4.+3.+7.
6. combination of 4.+3.

Observations on coverage:

- By themselves, 3. and 4. are not improvements, but in combination they are.
  This was somewhat expected; there is (or at least should be) a synergy
  between these.
- 7. is a substantial improvement over initial, getting back 10 of the 16
  instances lost compared to base
- 3.+4.+7. together get back 13 of the 16 instances lost compared to base;
  for the remaining three, base gets to more than 98% of the memory limit
  (2032612 for openstacks-opt08 #15, 2032460 for openstacks-opt11 #11,
   2015188 for zenotravel #8).

Regarding time, the configuration with all three improvements is within 2% of
base (looking at the overall geometric mean of "total time").

All of these seem acceptable, especially since blind search should be something
of a worst case here. What do you think? If it looks good enough for now, it may
be worth running another set of experiments with other planner configurations
than blind search.

Once this is done, we might want to have a look at issue235.

Looks good (this is just a test message for e-mail notifications)

After a discussion with Malte we decided to make some larger changes to the way
states are handled. This patch is also build with issue214 (packed state
representations) in mind.

  http://codereview.appspot.com/6461087/
  https://bitbucket.org/flogo/fast-downward/src/issue344

There are a couple of new classes and changes to existing classes:
 * StateRepresentation: contains the (packed) state data and an id. This is a
private class that is only meant to be used by StateHandle.
 * StateHandle: opaque pointer (PIMPL pattern:
http://en.wikipedia.org/wiki/Opaque_pointer) to StateRepresentation. A valid
StateHandle represents a registered State in its packed Form and can be copied
without the need to copy the state data. Creating a State from a StateHandle
would later unpack the data stored in StateRepresentation.
 * State: can be registered or unregistered. Registered States have a valid
handle (and by this a valid unique id). In the packed states scenario, the State
class would contain the unpacked, easy-to-access state data. As before States
can own their data or borrow it from another State (or, as long as we don't use
packed States, they can borrow it from their handle)
 * SearchNode: works more or less the same as before, except the SearchNodeInfo
is no longer stored in a hash_map but as per state information (i.e. in a vector
indexed by state ids).
 * StateProxy: is no longer necessary because it is replaced by StateHandle.
 * StateRegistry: now stores a hash_set instead of a hash_map, because the
handles already contain their ids.

Maybe try using a deque instead of a vector?
From http://www.cplusplus.com/reference/stl/deque/:
"While vectors are very similar to a plain array that grows by reallocating all 
of its elements in a unique block when its capacity is exhausted, the elements 
of a deques can be divided in several chunks of storage, with the class keeping 
all this information and providing a uniform access to the elements."

The analysis with indirection just finished and looks much better.

Thanks for the analysis!

hash_maps have the same problem, only worse (it may be, although I'd be
surprised, that they use an extra indirection by default, but in that case we
could achieve the same thing with a vector of pointers).

Whatever we are currently doing should also have the same problem, only worse.
Maybe we can discuss the different possible approaches offline?

I tried using the PerStateInformation class and ran into memory problems. When
the vector is resized the elements have to be copied and the vector uses double
its size for a short time. Using a large class to save for each state thus leads
to memory spikes. I attached an analysis with valgrind/massif that shows this.
The lower image uses a hash map to store the information, the upper image uses
the PerStateInformation class. Maybe storing only pointers in the vector will
produce smaller spikes (but will probably use more memory for the additional
pointers). I'll test this and post the results here.

Should we introduce another class that internally uses a hash_map instead of a
vector?

One more note on the patch: all of this is not yet tested or used in the code.
That is, the possibility to maintain state ids is there but as long as no calls
to state.get_id() are made all states will have the internal id of -1
(UNKOWN_ID). I reckon implementing an evaluation context would be a good test
case. This is the next item on my list anyway, unless there are still problems
with this issue.

I uploaded the implementation of what we discussed yesterday (see
https://bitbucket.org/flogo/fast-downward/compare/issue344..default for the full
patch). The patch also contains a fix for an issue we did not talk about: If a
state is registered and gets an id and is then changed via the array accessor
the id will not be up to date.
There was only one situation in the source were an existing state was changed.
This was the application of axioms for the initial state and every state created
using an operator application. I discussed this with Gabi and we agreed to make
the State class immutable by removing the non-const accessor. The application of
axioms is now handled in the State constructors and works directly on the buffer
instead of the State object. The constructor used to create the initial state
was changed to allow the axioms to be read first.
Unfortunately there already was a constructor with the same signature but a
different semantic so I used a static method (named constructor idom) and a
private constructor with a slight signature change. Its not so nice to have two
almost identical ctors with different semantics, but we can revert back to the
parsing constructor if/when the format for output files is changed to contain
the axioms in front of the initial state.

I split the interface for PerStateInformation into two classes to avoid the
boolean vector. We can discuss this via skype:
https://bitbucket.org/flogo/fast-downward/src/6fd7637054dd/src/search/per_state_information.h

Fine by me.

Sure, works for me.
On Jul 4, 2012 6:44 PM, "Gabi Röger" <downward.issues@googlemail.com> wrote:

>
> Gabi Röger <roeger@informatik.uni-freiburg.de> added the comment:
>
> Ok, to push this a bit I propose next Tuesday (July 10th) 2pm UTC for the
> skype
> chat. (Florian said he is available then).
>
> _______________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://issues.fast-downward.org/issue344>
> _______________________________________________________
>

Ok, to push this a bit I propose next Tuesday (July 10th) 2pm UTC for the skype
chat. (Florian said he is available then).

I would also like to join the skype chat. As a rule of thumb I don't have time
between 2 and 3pm (German time). Apart from that I am quite flexible (except
this Friday).

I would like to participate in the Skype chat as well. My calendar is rather 
flexible.

I'm busy this Friday and every Thursday from 16:30 to 17:30 but apart from that
my calendar is very empty at the moment.

I suggest we start by scheduling a Skype chat (Me, Malte, Florian and possibly 
Gabi) to discuss what we want to support that is not supported now, and a 
general direction for implementation.
I could then support Florian remotely, and if we see that it's too complex, I 
can come for a visit.
The semester is over here, so I'm mostly free - let me know when is a good time 
for you all.

Thank you Erez, I would really appreciate the help (remote or local). I'm
motivated to work on this but there are so many different use cases (multiple
heuristics, search spaces, etc.) that I'm always afraid of breaking something
when I start to change things. So the help of someone who knows the code would
be very valuable.

Hi Erez, we have money for visitors to Basel. I don't think this issue is so
difficult that we cannot resolve it remotely, but independently of this you're
always welcome to visit. Personally, I won't have an available week any time in
the near future, though.

The issue I mentioned with my first option is also relevant to the (non-
existing) caching of heuristic values, which the original LAMA had, but Fast 
Downward does not. 
We should probably have a discussion about what else we want to change, and then 
do a major change to the search code.

I would be happy to help Florian with this. 
It might even be possible to arrange for Florian to come to Israel for a short 
term scientific mission, or for me to come to Freiburg, so that we can devote a 
week to working on this.
Malte - do you know if that's still an option?

You are right, saving the id in search node and then copying it to the state is
a bit fragile. I chose this to minimize the amount of changes in existing code,
because I'm still not that familiar with it. 

I like the first option you suggested because it would also solve some other
problems I had with implementing an incrementally computed heuristic. I'm not
sure what kind of problems it would cause and how hard it would be to fix the
one you mentioned.

As for the interface to PerStateInformation, I thought about splitting this into
two classes: 
A) One for things that are copied by value (int, bool, etc.) and that have a
reasonable default value. In this case the method to remove information or check
if information for a state exists is not that useful and could be omitted.
B) Another one for (complex) classes. I thought about using pointers with a
default value of NULL for this case. Adding and removing information could then
be done with new/delete and checking if information exists fo a state would be a
test against NULL.

In both cases the boolean vector would not be needed anymore. I needed it before
because for a class that is copied by value it is not clear how to differentiate
between its default value and no set value.

I finally had some time to look at the patch.
The idea of storing a vector instead of a hash_map for anything that needs per-
state information is a good one. 
However, I think that making the ID a part of the State class, when the 
SearchSpace/SearchNode mechanism is responsible for assigning the ID is 
problematic. 

What if some heuristic needs to create some states? 
This is done by selective max, during the state space sample, where we need to 
compute the value of the LM heuristic. This would not work well under the 
suggested patch.

I propose two possible solutions:
1) Make the heuristics aware of the SearchSpace class (pass it to them in the 
constructor, pass a SearchNode to evaluate() instead of a State, ...). 
This solution assumes each heuristic will only be used with one SearchSpace, 
which might be problematic with iterative search, but I think this can be fixed.

2) Make a separate mechanism for assigning an ID to a state (possibly even a 
global singleton object). The interface and implementation would be similar to 
SearchSpace.get_node(), possibly with different functions for telling if it's a 
new or existing state. Then everything else, including SearchSpace could use 
this to get IDs of states.

Finally, there is another issue with this patch (although it's not very 
important), that the overhead of the boolean vector (empty) would be duplicated 
for each instance of PerStateInformation. However, I think this is not such a 
big problem for now.

It is possible to use the index when storing it in SearchNodeInfo. It has to be
copied to States when they are created from a SearchNode. I started developing a
patch at https://bitbucket.org/flogo/fast-downward/compare/issue344..default

A problem with option 3 (implentation as index) is that the open lists only save
a pointer to a state_var_t not a State (to save memory I guess). Without
changing the type here, storing an index will be complicated.

This is also related to a few other issues:

> http://issues.fast-downward.org/issue182
> http://issues.fast-downward.org/issue198
> http://issues.fast-downward.org/issue207
> http://issues.fast-downward.org/issue339

Each heuristic should be able to save meta information for each search node.
Adding the fields needed by all heuristics to the search node class is not
feasible/extendable. 

We could either:
* Add dynamically allocated memory (e.g. a hash map in each search node): this
makes memory management complicated because the different heuristics store
different data types.
* Use the states as indices in a hash map maintained by the heuristic (as done
e.g. in the LandmarkStatusManager)
* Assign a unique index to each state and use this index instead of the state to
map to per-state data. Heuristics can then maintain a vector instead of a hash
map and access the data by index. Since states are not removed, we can enumerate
created states.