issue211

[Moritz, 2011-08-07 08:56:34]

http://codereview.appspot.com/4819063/diff/1/src/search/shrink_fh.cc
File src/search/shrink_fh.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/shrink_fh.cc#newcode30
src/search/shrink_fh.cc:30: if(abs.max_f > max_vector_size) {
I thought about using something like AdaptiveQueue here instead of the two
ordered_buckets_use_* - methods. But I think that'd be measurably slower.

The threshold max_vector_size was chosen arbitrarily.

This solution leads to improved coverage in ParcPrinter (from 7-9 in the old
version to 12), and no difference in coverage (but usually a slight improvement
in search time) in the other domains in ipc08_opt.

[Malte, 2011-08-12 14:47:04]

First round of comments.

http://codereview.appspot.com/4819063/diff/1/new-scripts/downward_configs.py
File new-scripts/downward_configs.py (right):

http://codereview.appspot.com/4819063/diff/1/new-scripts/downward_configs.py#...
new-scripts/downward_configs.py:243: ("mas-2", "--search
'astar(mas(max_states=200000,merge_strategy=5,shrink_strategy=shrink_dfp(Enable_Greedy_Bisimulation)))'"),
I suggest we stick to lower_case.

http://codereview.appspot.com/4819063/diff/1/src/search/Makefile
File src/search/Makefile (right):

http://codereview.appspot.com/4819063/diff/1/src/search/Makefile#newcode75
src/search/Makefile:75: shrink_bisimulation.h
Should be alphabetically sorted. (The order used here makes thematic sense, but
alphabetical is much easier to maintain and used elsewhere in the Makefile.)

http://codereview.appspot.com/4819063/diff/1/src/search/option_parser_util.h
File src/search/option_parser_util.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/option_parser_util.h#...
src/search/option_parser_util.h:274: static std::string toStr(ShrinkStrategy *s)
{
Our coding convention would want the method to be called to_str. Or is this name
required by some external library we're using?

(This is of course not new to this issue, but I didn't notice it before.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:132: //NOTE(mg) - is the above TODO still valid?
"AC" in the comment means "action costs". These are supported everywhere now,
right? Here it would make sense to call the simplest and fastest possible shrink
strategy -- maybe even create a dedicated one from scratch. Its only purpose is
to discard irrelevant and unreachable states, not to perform any actual state
aggregation.

I don't have enough of a full-picture view at the moment to confidently know
what the best way to handle this is here, so if you're not sure, please leave a
comment/TODO in the code (one that is clearer than the current one -- I needed a
while to figure out what "AC" is here) and add this to issue261.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:793: void Abstraction::shrink(int threshold, bool
force) {
Does the caller of this know the shrink strategy? I assume yes. In that case, it
would be good to remove the method and move the comment into the base shrink
strategy class's header file.

If it's a nontrivial change, add to issue261.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:67: friend class ShrinkBisimulation;
Eventually, it would be good if the Abstraction class didn't need to know all
shrink strategies classes so that they can be plugged in/out more easily. I've
added this to issue261.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:158: shrink_strategy = s;
I'm not sure I like to have a general setter, especially a public one. Is it
needed? (Why?)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:216: 
SuccessorSignature and Signature need a short comment explaining their purpose.
(I know I'm the original guilty party.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
File src/search/raz_mas_heuristic.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:204: || !shrink_strategy->is_bisimulation())
I think we have a logic bug here: this should logically be

"if (has_memory_limit || !is_bisimulation)".

Also, I think the logic can be changed a bit: if there is no memory limit by the
shrinking strategy and we don't have a bisimulation, I don't see why we would
need to call anything.

Suggestion:

if memory limit {
    current if branch
} else if bisimulation {
    current else branch
}


There are some other things I'm not sure about; added to issue261.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:208: nolimit.shrink(*other_abstraction,
1000000000, false);
10^9 should be numeric_limits<int>::max(). (We need to check if this can
overflow -- running some benchmarks to cover the code path should be enough; I
don't think we really need to go through the called code.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:215: shrink_strategy->shrink(*abstraction,
new_size);
Also looks dodgy. For what it's worth, I read Raz's variable name
"is_no_mem_limit_bisimulation_strategy" as

is a strategy which
  * has no limit, and
  * is based on bisimulation

Maybe a different possible bracketing of the "no" vs. "and" is the source of
confusion here?

http://codereview.appspot.com/4819063/diff/1/src/search/shrink_fh.cc
File src/search/shrink_fh.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/shrink_fh.cc#newcode30
src/search/shrink_fh.cc:30: if(abs.max_f > max_vector_size) {
On 2011/08/07 08:56:34, Moritz wrote:
> I thought about using something like AdaptiveQueue here
> instead of the two ordered_buckets_use_* - methods. But I
> think that'd be measurably slower.

I haven't read the code in context yet, but the current implementation looks
fine to me.
 
> The threshold max_vector_size was chosen arbitrarily.

I would say we care more about avoiding having too many empty buckets in
relative terms rather than having too many buckets in absolute numbers.

Hence, I would suggest using the test "abs.max_f > number of abstract states" to
decide whether to use a map-based approach. (If max_f is larger than the number
of abstract states, use the map.)

That way, we should be guaranteed to stay in the bucket-based case for uniform
cost problems, which is good, but would switch to maps if buckets contain less
than 1 element on average.

[raznissim, 2011-08-12 16:13:39]

Added comment regarding "abstraction_count == -2"

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
File src/search/raz_mas_heuristic.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:417: if (abstraction_count == -2) {
This block of code was used for when we tried out computing two abstractions,
and using their max. Since this didn't work well, we went with running them
sequentially (i.e. Hybrid). So this option was not used in our experiments.

[Malte, 2011-08-12 16:17:40]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
File src/search/raz_mas_heuristic.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:417: if (abstraction_count == -2) {
OK, we should remove it then. If we want to do similar things in the future, we
can use the regular max-of-heuristics mechanism, at least once the search code
is cleaned up. (There is currently a bit of breakage there.)

[Moritz, 2011-08-12 21:04:20]

Most of the comments will be addressed in the next patchset.

http://codereview.appspot.com/4819063/diff/1/src/search/Makefile
File src/search/Makefile (right):

http://codereview.appspot.com/4819063/diff/1/src/search/Makefile#newcode75
src/search/Makefile:75: shrink_bisimulation.h
On 2011/08/12 14:47:04, Malte wrote:
> Should be alphabetically sorted. (The order used here makes thematic sense,
but
> alphabetical is much easier to maintain and used elsewhere in the Makefile.)

Fixed.

http://codereview.appspot.com/4819063/diff/1/src/search/option_parser_util.h
File src/search/option_parser_util.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/option_parser_util.h#...
src/search/option_parser_util.h:274: static std::string toStr(ShrinkStrategy *s)
{
On 2011/08/12 14:47:04, Malte wrote:
> Our coding convention would want the method to be called to_str. Or is this
name
> required by some external library we're using?
> 
> (This is of course not new to this issue, but I didn't notice it before.)

Was accidental. Changed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:132: //NOTE(mg) - is the above TODO still valid?
Added to issue261.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:793: void Abstraction::shrink(int threshold, bool
force) {
On 2011/08/12 14:47:04, Malte wrote:
> Does the caller of this know the shrink strategy? I assume yes. In that case,
it
> would be good to remove the method and move the comment into the base shrink
> strategy class's header file.
> 
> If it's a nontrivial change, add to issue261.

Removed method, moved comment.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:67: friend class ShrinkBisimulation;
On 2011/08/12 14:47:04, Malte wrote:
> Eventually, it would be good if the Abstraction class didn't need to know all
> shrink strategies classes so that they can be plugged in/out more easily. I've
> added this to issue261.

I overestimated the entanglement between shrink strategies and the abstraction.
I can probably get rid of this by just creating a few getters.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:158: shrink_strategy = s;
On 2011/08/12 14:47:04, Malte wrote:
> I'm not sure I like to have a general setter, especially a public one. Is it
> needed? (Why?)

Was unnecessary, removed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
File src/search/raz_mas_heuristic.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:204: || !shrink_strategy->is_bisimulation())
Changed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:208: nolimit.shrink(*other_abstraction,
1000000000, false);
Yes. I haven't changed this and all the QUITE_A_LOTs because I didn't check for
possible sources of overflow yet.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:215: shrink_strategy->shrink(*abstraction,
new_size);
Fixed. Apparently I'm a bit sloppy concerning simple logic lately.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:417: if (abstraction_count == -2) {
On 2011/08/12 16:17:40, Malte wrote:
> OK, we should remove it then. If we want to do similar things in the future,
we
> can use the regular max-of-heuristics mechanism, at least once the search code
> is cleaned up. (There is currently a bit of breakage there.)

Removed.

http://codereview.appspot.com/4819063/diff/1/src/search/shrink_fh.cc
File src/search/shrink_fh.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/shrink_fh.cc#newcode30
src/search/shrink_fh.cc:30: if(abs.max_f > max_vector_size) {
> Hence, I would suggest using the test "abs.max_f > number of abstract states"
to
> decide whether to use a map-based approach. (If max_f is larger than the
number
> of abstract states, use the map.)

Ok, I'll try that.

[Moritz, 2011-08-13 08:53:52]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:216: 
On 2011/08/12 14:47:04, Malte wrote:
> SuccessorSignature and Signature need a short comment explaining their
purpose.
> (I know I'm the original guilty party.)

Is the following correct?:
"Signatures are used to represent the abstract transition graph when shrinking
abstractions."

Also, moved to shrink_strategy.h.

[Malte, 2011-08-13 09:20:16]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:216: 
On 2011/08/13 08:53:52, Moritz wrote:
> Is the following correct?:
> "Signatures are used to represent the abstract transition graph when shrinking
> abstractions."

I'm not sure about the details right now; would have to reread the SHRINK_DFP
code and Raz's new code (if they are used there). For now, I think it's better
to leave this at "TODO: Document the purpose of signatures".

[Moritz, 2011-08-13 09:26:54]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:216: 
On 2011/08/13 09:20:16, Malte wrote:
> On 2011/08/13 08:53:52, Moritz wrote:
> > Is the following correct?:
> > "Signatures are used to represent the abstract transition graph when
shrinking
> > abstractions."
> 
> I'm not sure about the details right now; would have to reread the SHRINK_DFP
> code and Raz's new code (if they are used there). For now, I think it's better
> to leave this at "TODO: Document the purpose of signatures".

Ok

[Malte, 2011-08-14 18:45:07]

Raz: these are mostly comments for Moritz, but there's a question for you
included somewhere below. If you don't want to go through all this, just search
for your name.


I went through the code of the raz_* files, with the exception of some
abstraction-related methods in raz_abstraction.cc.

I didn't go through the shrink_* files yet.

I also have a few comments on raz_operator_registry.* and
raz_variable_order_finder.*, but can't comment on them here since the files had
no changes (and hence are not included in the issue).

Moritz, the easiest thing for me would be to apply the changes to these files
directly. I can either push to your bitbucket repository if I have rights for
that, or we can merge your changes so far into master and I'll push them there,
whatever works better for you. Let me know if I should wait for this because
you're currently working on something. (I'll have to make some cosmetic changes
to the code that uses the OperatorRegistry.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:74: former; the latter maybe called
"TransitionSystem" or whatever.
The words "former" and "latter" should be swapped in line 74.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:93:
//	reduced_to_by_op.resize(g_operators.size());
Remove commented out line.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:391: }
Add blank line.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:438: abs2->normalize(simplify_labels &&
!normalize_after_compostition);
Question for Raz: If normalize_after_composition is true, do we need to call
abs1->normalize and abs2->normalize here at all? If so, why? I find it
non-obvious, so maybe the explanation should be given in the code, too?

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:511: //anyway, normalization should be done from
here and not in the shrink method of abstraction.c.
These two comment lines can be removed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:749: 
The spces before "()" should go.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:59: };
Remove this struct.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:80: vector<vector<AbstractTargetOp> >
transitions_by_source;
Remove.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:155: void dump_transitions_by_src() const;
Remove.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:161: };
Add a blank line.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:184: bool simplify_labels, bool
normalize_after_composition);
Add:
   virtual ~CompositeAbstraction();

with an implementation in the CC file, below the implementation of the
constructor. Our coding convention is to have an explicitly defined destructor
iff we have an explicitly defined constructor, and to explicitly mark methods as
virtual (for documentation purposes) if they inherit virtualness.

Same for AtomicAbstraction.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:216: 
For what it's worth: maybe this belongs into a (new) bisimulation-related base
class of ShrinkStrategy rather than ShrinkStrategy proper, since it's a concept
related to bisimulation. (SHRINK_DFP is also base on bisimulation-ish notions.)
For now, I suggest adding a comment like:

// TODO: Maybe create a common base class for ShrinkBisimulation and ShrinkDFP
and move the Signature classes there.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:217: 
Get rid of second blank line.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
File src/search/raz_mas_heuristic.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:84: << (use_expensive_statistics ? "enabled" :
"disabled") << endl;
Minor cleanup: Two cout << statements should be merged into one and source
codeline breaks moved after endl:

cout << endl
     << "Shrink strategy: " << shrink_strategy->description() << endl
     << "Label simplification: " ...

(Additional line breaks are OK where lines become long, but if we have a choice
of where to break, it looks cleaner to break after << endl.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:116: }
This block (109-116) is now wrong and should be removed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:140: }
After removing the wrong block, the method should be moved to globals.cc and
become a global function.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:148: // Check if product would exceeds max
allowed size.
=> "would exceed" (no "s")

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:175: //		cout << i << ": " <<
g_operators[i].get_name() << endl;
Remove these three lines.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:233: //		cout << endl;
We can get rid of this commented out code block.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:414: //conf 2 is the following: 5-12-1-true-none
Should get rid of this TODO block, too. (It relates to the code we removed
below.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:439: cout << "Building abstraction nr " << i <<
"..." << endl;
Small cleanup:
            cout << "Building abstraction #" << (i + 1) << "..." << endl;

=> 1-based indexing is nicer in output and "nr" is Germanism.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:443: if (!abstractions.back()->is_solvable())
Should have some output here:
    cout << "Abstract problem is unsolvable!" << endl;
    if (i + 1 < abstraction_count - 1)
        cout << "Skipping remaining abstractions." << endl;

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:450: cout << "Estimated peak memory: " <<
peak_memory << " bytes" << endl;
Should be "Estimated peak memory for abstraction: ".

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:474: }
Lines 461-474 should be removed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:497: ShrinkStrategy *def_shrink = new
ShrinkFH(HIGH, LOW);
Not sure I like this -- every time this is called, we will leak a new shrink
strategy. Can you add a TODO about this? Ideally I'd like shrink strategies to
only be created if and when they're actually used.

(I'm fine to leave this for later, though.)

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h
File src/search/raz_mas_heuristic.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h#n...
src/search/raz_mas_heuristic.h:22: MAX_MERGE_STRATEGY
It's a bit dangerous that these have to appear in the same order here as in
_parse -- if not, we'll get the wrong strategy without possibly ever finding
out. That's an accident waiting to happen. Doesn't have to be resolved
immediately, but I suggest a TODO in the code, or if you prefer a note in
issue261.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h#n...
src/search/raz_mas_heuristic.h:30: ShrinkStrategy *shrink_strategy;             
       //TODO - removed const for raz's double abstraction experiment
The four TODO variables should all be const again, and the TODOs removed.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h#n...
src/search/raz_mas_heuristic.h:36: void verify_no_axioms_no_cond_effects()
const;
Should be (re-) moved -- see comment in cc file.

[Moritz, 2011-08-14 19:19:45]

On Sun, 2011-08-14 at 18:45 +0000, malte.helmert@googlemail.com wrote:
> Moritz, the easiest thing for me would be to apply the changes to
> these
> files directly. I can either push to your bitbucket repository if I
> have
> rights for that ...


I sent you a write-invitation to my bitbucket repository. Just tell me
when you're finished, please. 

[raznissim, 2011-08-14 19:27:33]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:438: abs2->normalize(simplify_labels &&
!normalize_after_compostition);
Seems we shouldn't call normalize here at all. (I think) I inserted this option
in order to check whether normalizing before or after composition is more
efficient.

On 2011/08/14 18:45:07, Malte wrote:
> Question for Raz: If normalize_after_composition is true, do we need to call
> abs1->normalize and abs2->normalize here at all? If so, why? I find it
> non-obvious, so maybe the explanation should be given in the code, too?

[Malte, 2011-08-14 19:34:23]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:394: bool normalize_after_compostition) {
typo: "compostition" => "composition".

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:438: abs2->normalize(simplify_labels &&
!normalize_after_compostition);
Then I would suggest changing this to:

if (!normalize_after_composition) {
    if (abs1->varset.size() > 1)
        abs1->normalize(simplify_labels);
    else if (abs2->varset.size() > 1)
        abs2->normalize(simplify_labels);
}

Does this sound OK to you? If we don't call it at all, then it won't be called
ever (I think) for the bucket-based shrinking strategies, which set
"normalize_after_composition" to false.

[raznissim, 2011-08-14 19:37:30]

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:438: abs2->normalize(simplify_labels &&
!normalize_after_compostition);
Fine by me.
On 2011/08/14 19:34:23, Malte wrote:
> Then I would suggest changing this to:
> 
> if (!normalize_after_composition) {
>     if (abs1->varset.size() > 1)
>         abs1->normalize(simplify_labels);
>     else if (abs2->varset.size() > 1)
>         abs2->normalize(simplify_labels);
> }
> 
> Does this sound OK to you? If we don't call it at all, then it won't be called
> ever (I think) for the bucket-based shrinking strategies, which set
> "normalize_after_composition" to false.

[Moritz, 2011-08-15 11:57:24]

http://codereview.appspot.com/4819063/diff/1/new-scripts/downward_configs.py
File new-scripts/downward_configs.py (right):

http://codereview.appspot.com/4819063/diff/1/new-scripts/downward_configs.py#...
new-scripts/downward_configs.py:243: ("mas-2", "--search
'astar(mas(max_states=200000,merge_strategy=5,shrink_strategy=shrink_dfp(Enable_Greedy_Bisimulation)))'"),
On 2011/08/12 14:47:04, Malte wrote:
> I suggest we stick to lower_case.

fixed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:74: former; the latter maybe called
"TransitionSystem" or whatever.
On 2011/08/14 18:45:07, Malte wrote:
> The words "former" and "latter" should be swapped in line 74.

fixed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:93:
//	reduced_to_by_op.resize(g_operators.size());
On 2011/08/14 18:45:07, Malte wrote:
> Remove commented out line.

fixed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:391: }
On 2011/08/14 18:45:07, Malte wrote:
> Add blank line.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:394: bool normalize_after_compostition) {
On 2011/08/14 19:34:23, Malte wrote:
> typo: "compostition" => "composition".

fixed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:438: abs2->normalize(simplify_labels &&
!normalize_after_compostition);
On 2011/08/14 19:37:30, raznissim wrote:
> Fine by me.
> On 2011/08/14 19:34:23, Malte wrote:
> > Then I would suggest changing this to:
> > 
> > if (!normalize_after_composition) {
> >     if (abs1->varset.size() > 1)
> >         abs1->normalize(simplify_labels);
> >     else if (abs2->varset.size() > 1)
> >         abs2->normalize(simplify_labels);
> > }
> > 
> > Does this sound OK to you? If we don't call it at all, then it won't be
called
> > ever (I think) for the bucket-based shrinking strategies, which set
> > "normalize_after_composition" to false.
> 

changed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:511: //anyway, normalization should be done from
here and not in the shrink method of abstraction.c.
On 2011/08/14 18:45:07, Malte wrote:
> These two comment lines can be removed.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.cc#ne...
src/search/raz_abstraction.cc:749: 
On 2011/08/14 18:45:07, Malte wrote:
> The spces before "()" should go.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h
File src/search/raz_abstraction.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:59: };
On 2011/08/14 18:45:07, Malte wrote:
> Remove this struct.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:80: vector<vector<AbstractTargetOp> >
transitions_by_source;
On 2011/08/14 18:45:07, Malte wrote:
> Remove.

removed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:155: void dump_transitions_by_src() const;
On 2011/08/14 18:45:07, Malte wrote:
> Remove.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:161: };
On 2011/08/14 18:45:07, Malte wrote:
> Add a blank line.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:184: bool simplify_labels, bool
normalize_after_composition);
On 2011/08/14 18:45:07, Malte wrote:
> Add:
>    virtual ~CompositeAbstraction();
> 
> with an implementation in the CC file, below the implementation of the
> constructor. Our coding convention is to have an explicitly defined destructor
> iff we have an explicitly defined constructor, and to explicitly mark methods
as
> virtual (for documentation purposes) if they inherit virtualness.
> 
> Same for AtomicAbstraction.

done, and applied the conventions to the shrink_* files.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:216: 
On 2011/08/14 18:45:07, Malte wrote:
> For what it's worth: maybe this belongs into a (new) bisimulation-related base
> class of ShrinkStrategy rather than ShrinkStrategy proper, since it's a
concept
> related to bisimulation. (SHRINK_DFP is also base on bisimulation-ish
notions.)
> For now, I suggest adding a comment like:
> 
> // TODO: Maybe create a common base class for ShrinkBisimulation and ShrinkDFP
> and move the Signature classes there.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_abstraction.h#new...
src/search/raz_abstraction.h:217: 
On 2011/08/14 18:45:07, Malte wrote:
> Get rid of second blank line.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
File src/search/raz_mas_heuristic.cc (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:84: << (use_expensive_statistics ? "enabled" :
"disabled") << endl;
On 2011/08/14 18:45:07, Malte wrote:
> Minor cleanup: Two cout << statements should be merged into one and source
> codeline breaks moved after endl:
> 
> cout << endl
>      << "Shrink strategy: " << shrink_strategy->description() << endl
>      << "Label simplification: " ...
> 
> (Additional line breaks are OK where lines become long, but if we have a
choice
> of where to break, it looks cleaner to break after << endl.)

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:116: }
On 2011/08/14 18:45:07, Malte wrote:
> This block (109-116) is now wrong and should be removed.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:140: }
On 2011/08/14 18:45:07, Malte wrote:
> After removing the wrong block, the method should be moved to globals.cc and
> become a global function.

moved

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:148: // Check if product would exceeds max
allowed size.
On 2011/08/14 18:45:07, Malte wrote:
> => "would exceed" (no "s")

fixed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:175: //		cout << i << ": " <<
g_operators[i].get_name() << endl;
On 2011/08/14 18:45:07, Malte wrote:
> Remove these three lines.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:233: //		cout << endl;
On 2011/08/14 18:45:07, Malte wrote:
> We can get rid of this commented out code block.

removed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:414: //conf 2 is the following: 5-12-1-true-none
On 2011/08/14 18:45:07, Malte wrote:
> Should get rid of this TODO block, too. (It relates to the code we removed
> below.)

removed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:439: cout << "Building abstraction nr " << i <<
"..." << endl;
On 2011/08/14 18:45:07, Malte wrote:
> Small cleanup:
>             cout << "Building abstraction #" << (i + 1) << "..." << endl;
> 
> => 1-based indexing is nicer in output and "nr" is Germanism.

changed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:443: if (!abstractions.back()->is_solvable())
On 2011/08/14 18:45:07, Malte wrote:
> Should have some output here:
>     cout << "Abstract problem is unsolvable!" << endl;
>     if (i + 1 < abstraction_count - 1)
>         cout << "Skipping remaining abstractions." << endl;

Shouldn't that be "if (i + 1 < abstraction_count)" ? Otherwise there'll be no
"skipping"-message when breaking at the second-to-last abstraction.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:450: cout << "Estimated peak memory: " <<
peak_memory << " bytes" << endl;
On 2011/08/14 18:45:07, Malte wrote:
> Should be "Estimated peak memory for abstraction: ".

changed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:474: }
On 2011/08/14 18:45:07, Malte wrote:
> Lines 461-474 should be removed.

removed

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc#...
src/search/raz_mas_heuristic.cc:497: ShrinkStrategy *def_shrink = new
ShrinkFH(HIGH, LOW);
On 2011/08/14 18:45:07, Malte wrote:
> Not sure I like this -- every time this is called, we will leak a new shrink
> strategy. Can you add a TODO about this? Ideally I'd like shrink strategies to
> only be created if and when they're actually used.
> 
> (I'm fine to leave this for later, though.)

added TODO

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h
File src/search/raz_mas_heuristic.h (right):

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h#n...
src/search/raz_mas_heuristic.h:22: MAX_MERGE_STRATEGY
On 2011/08/14 18:45:07, Malte wrote:
> It's a bit dangerous that these have to appear in the same order here as in
> _parse -- if not, we'll get the wrong strategy without possibly ever finding
> out. That's an accident waiting to happen. Doesn't have to be resolved
> immediately, but I suggest a TODO in the code, or if you prefer a note in
> issue261.

Added a TODO. 
But at least the used merge strategy is correctly printed in the output, so it's
possible to notice.

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h#n...
src/search/raz_mas_heuristic.h:30: ShrinkStrategy *shrink_strategy;             
       //TODO - removed const for raz's double abstraction experiment
On 2011/08/14 18:45:07, Malte wrote:
> The four TODO variables should all be const again, and the TODOs removed.

done

http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.h#n...
src/search/raz_mas_heuristic.h:36: void verify_no_axioms_no_cond_effects()
const;
On 2011/08/14 18:45:07, Malte wrote:
> Should be (re-) moved -- see comment in cc file.

moved

[Malte, 2011-08-17 08:15:41]

One more small change suggestion.

http://codereview.appspot.com/4819063/diff/17003/src/search/shrink_fh.cc
File src/search/shrink_fh.cc (right):

http://codereview.appspot.com/4819063/diff/17003/src/search/shrink_fh.cc#newc...
src/search/shrink_fh.cc:32: if(abs.max_f > abs.num_states) {
Sorry, I have to correct myself w.r.t. the criterion when to use the
vector-based method. My intuition was to use the vector-based stuff if we can
expect that each vector entry contains at least about one entry on average, but
our current criterion doesn't do that. (I overlooked that we have a
two-dimensional vector structure indexed by f and h rather than a
one-dimensional one indexed by h.)

The maximal number of (f, h) combinations we can get is
(max_f + 1) (max_f + 2) / 2 (taking into account that we always have h <= f). We
can simplify that to max_f * max_f since we don't need to care about small
change.

So the test should be "abs.max_f * abs.max_f / 2 > abs.num_states"; however,
that can and will overflow in domains like ParcPrinter. An easy, but not
standard-compliant way to avoid that would be to convert to long long;
alternatively, we could also convert to double; some inaccuracies in the
computation won't matter.

So something like
if (static_cast<double>(max_f) * max_f / 2.0 > abs.num_states) { // convert to
double to avoid overflow
   // Use map because an average bucket in the vector
   // structure would contain less than 1 element (roughly).
...
}

it should be.

[Malte, 2011-08-17 11:13:21]

Looks good! No substantial comments.

I'm still digging through the shrink code, but I'm hopeful that we can merge
this later today.

http://codereview.appspot.com/4819063/diff/29001/new-scripts/downward_configs.py
File new-scripts/downward_configs.py (right):

http://codereview.appspot.com/4819063/diff/29001/new-scripts/downward_configs...
new-scripts/downward_configs.py:242: ("mas-1", "--search
'astar(mas(max_states=1,merge_strategy=merge_linear_reverse_level,shrink_strategy=shrink_bisimulation(true,
false)))'"),
Named arguments for true, false would be good. Easier for the user to
understand, and also the precise argument set will likely change at some point.
(I'd like to eventually change the logic for setting abstraction size to
unbounded.)

Same comment applies to other uses of mas-1 in downward-seq-opt-*.py.

http://codereview.appspot.com/4819063/diff/29001/src/search/raz_abstraction.cc
File src/search/raz_abstraction.cc (right):

http://codereview.appspot.com/4819063/diff/29001/src/search/raz_abstraction.c...
src/search/raz_abstraction.cc:134: e.g. a bucket-based one that simply generated
one good and
generate*d* => generate*s*

http://codereview.appspot.com/4819063/diff/29001/src/search/shrink_bisimulati...
File src/search/shrink_bisimulation_base.h (right):

http://codereview.appspot.com/4819063/diff/29001/src/search/shrink_bisimulati...
src/search/shrink_bisimulation_base.h:8: the are_similar()-method.
similar => bisimilar

[Malte, 2011-08-17 12:25:10]

http://codereview.appspot.com/4819063/diff/29001/src/search/shrink_bucket_bas...
File src/search/shrink_bucket_based.h (right):

http://codereview.appspot.com/4819063/diff/29001/src/search/shrink_bucket_bas...
src/search/shrink_bucket_based.h:23: virtual std::string description() const =
0;
Small note: in derived classes, we usually don't include methods in the header
file that don't have an implementation in this class (these four methods don't
have implementations in ShrinkBucketBased).

I'm currently making some small refactorings to the shrink* code and will take
care of this, so no need for action on your side.