Actually, let me close it now, and if you are interested, just go ahead and set it back to another status again. That way this won't be left hanging for many more years with the last message saying "I'd close this".

We haven't really touched this for 8 years, with the last message from 7 years ago. Is someone interested in working on this? Otherwise I'd close this wish due to lack of sufficient interest to work on this. (Which would of course not prevent anyone from working on this in the future if they are interested.)

When we continue to work on this, we should also consider the impact on POR. See 
issue629 and in particular msg5601.

There is a bit of the stuff Florian mentions in msg4512 here and there, but I'm
surprised to see this occur with such regularity in configurations as benign as
--search astar(blind()) (e.g. in the first airport task: 12 vs. 11 evaluations).

Would it be possible to get an explanation for this? Maybe it could be useful
for the future to strive for a bit more reproducibility, like we already to in
the translator and preprocessor.

Feel free to punt this for now -- if it isn't a clear-cut win, and something 
fishy is going on with the expansions, then it may not be worth the 
development cycles (that said, I'm not sure what the priorities are for you 
guys across the pond).

Toby and I planned on having a closer look at these types of ideas (and 
others) for successor generators in the coming months, so it hopefully won't 
sit unresolved for too long!

As far as I know, most things should be deterministic, but I'm not that familiar
with the satisficing configs. I guess it could be a some part of the code that
orders things according to their adress or something like this. I can have a
closer look, but won't have much time this week.

We have a fundamental disconnect here then, no? If the applicable operators 
are ordered, how could there ever be a difference in expansions? Is there a 
random number being drawn on that would change the behaviour elsewhere in the 
solver?

I ran another experiment for some satisficing configs with the added order
according to domain size [1]. Also, both greedy strategies now use domain size
as tie breaking. I also sorted the successors before returning them [2], but I
still get different numbers of expansions/evaluations.

[1] http://ai.cs.unibas.ch/_tmp_files/pommeren/issue556-issue556-v2.html
[2]
https://bitbucket.org/flogo/downward-issues-issue556/pull-request/1/issue556/diff#Lsrc/search/successor_generator.ccT492

1) Compile time option would work fine (that or a default on the SG constructor that 
other parts of the code could modify).

2) Sorting the applicable operators post-shuffle (or having an arbitrary consistent 
tie-breaking scheme from the start) is what I had in mind. Anything would work, as long 
as it doesn't depend on the structure of the SG or the order of actions that are 
returned from it. Sorting is probably going to hurt the performance ultimately, but it 
at least lets you test the effect of the variable ordering on the SG separate from the 
issue of applicable action ordering.

Various comments:

1) I understand the desire to make the variable order of the successor generator
a user-controllable option, but as Florian notes, the effort required is
substantial. I thought about working on this issue last weekend (before Florian
beat me to it), and at the end I shied away from it because I thought the order
should be user-controllable and that doing this cleanly would require some deep
thinking and substantial preparation.

To understand the issue, successor generators are only created "internally" and
(at least currently) we want to use the same successor generator in multiple
contexts if possible. (For what it's worth, do we currently generate two
successor generators when running --search astar(ipdb())?) Their main users are
the search algorithms, which are not yet converted to use the new task
interface, which complicates things further.

On the one hand, if we have already implemented various options, I think it
would be a pity to lose the code for all but one of them. On the other hand, I'd
rather not wait with merging this issue until we've resolved all the open
questions regarding the task interface in the search algorithms. One possibility
could be to merge this as a compile-time option for now, with a view to changing
this to a runtime-controllable one once we've worked on the infrastructure for that.

2) I agree with Christian that optimizing variable order for efficient successor
generation vs. optimizing variable order for good tie-breaking during search are
two separate things. While we see some strong effects in the experiments of this
issue, they tend to be negligible for more interesting configs (where heuristic
computation dominates successor generation), and also we should keep in mind
that operator order for tie-breaking can have a vastly more pronounced effects.
(IIRC, we say factors of 1000+ in some domains with greedy search.)

In some ways, it's a bit unfortunate to have the successor generator operator
order, which is a bit of an implementation detail, bleed into the search code.
One possibility to get rid of this is to sort the operators. Do we want to try
this? In any case, if we want to merge this, I think we need to experiment on
the impact of the new order on the search code, i.e., do a whole-planner
experiment, at least for our major configs and especially for the satisficing
ones where tie-breaking matters most. It's a bit unfortunate, but we know that
poor orders can frequently make a huge difference in overall planner runtime
(factors 10+, 100+, 1000+). (If from now on we make the successor generator sort
the operators at the end, we wouldn't have to worry about this so much in the
future. But of course the question is whether the sorted order is good and
whether sorting causes an acceptable overhead.)

3) Christian also made comments regarding separating the quality of the
successor generator from its construction time. If we were to write a paper on
this at some point, I think this would be absolutely necessary. On the other
hand, if we just think of this as one of 143 open issues we want to resolve with
a good "improvement for developer effort" ratio, I wouldn't bother. The main
question is: do we have enough time and motivation to look into this "properly".
(If yes, one of the first things I'd do is add some new metrics we can measure,
such as successor generator size, average number of branches traversed,
construction time, average traversal time, etc.)

Aye, sorting post-read of the successor generator. It's likely not something you would want 
to encourage for the default planner behaviour, but at least it levels the playing field for 
comparing these things. As I mentioned earlier, I really think that (1) the ability to 
retrieve the applicable actions, and (2) breaking ties on which ones to check first, are two 
distinct issues worth studying in isolation.

You could always alter the successor generator read function to give you different orders of 
actions (e.g., go down the dont-care edge first, sort the operators in the buckets, etc). 
But the simple time-to-compute-successors is the interesting part. Perhaps static-greedy and 
dynamic-greedy behave precisely the same for successor generation, but that in itself would 
be interesting as I've found the dynamic version very helpful for other things (e.g., using 
match trees for policies that come from regression of plans or deadends).

Also worth keeping construction time on the sidelines for the moment -- always ways to boost 
the performance there if it's really worth putting in the more complicated ordering :p.

@Christian:
I don't think its always possible to keep the order stable. Checking variable
v_1 first will order all operators with a precondition on v_1 before all
operators without a precondition on v_1. If another variable is checked first,
the order can be completely different. I think within the tree nodes, operators
remain sorted by the way we add them, but that doesn't help. We could order the
operators when we retrieve the applicable operators during the search. Is that
what you had in mind?

I'll add sorting by domain size and also try using that as a tie-breaker for the
greedy strategy. Then I'll re-run the experiments with ordered successors.

In the dynamic approach I also re-compute at every node. (I only scan for the
maximum instead of sorting, and I try to only iterate over things that are not
handled yet, but that should not change anything.)

You should have access to the pull request now.

@Jendrik:
We currently create the successor generator in read_everything() before we parse
the command line options, so using an option is very hacked right now. If we
really want to support different strategies, we have to think about the design a
bit more.

Since both the greedy and the current strategy seem to be a very good choice for 
some domains, I'd propose to support at least these two strategies. This might be 
useful whe trying to achieve good performance on a single domain (e.g. with 
parameter configuration). Of course, this is only recommendable if it doesn't 
require too much extra code.

Interesting stuff...

One big thing that jumps out to me here is the intertwined issue of tie-breaking in the 
action applicability. When focusing on the successor generator in particular, shouldn't the 
actions be sorted to make the comparison more meaningful? This would mean having the exact 
same number of expansions for all approaches, since the applicable action set never changes.

I see the choice of tie-breaking in applicable actions as a separate issue altogether, and 
the arbitrary nature of the current approaches is what's given you wildly different results. 
A more informative (at least to me) metric is the time / node spent on computing successors. 
I used the match trees for things other than just action applicability (and so have some in 
the group there I think), so maybe it's worth keeping the bigger picture in mind (e.g., if 
one uses the match tree to represent a policy, then there will be many evaluations where /no/ 
item is returned).

Other notes:

* You've tested 4 approaches, but that 5th one Malte pointed out (static sort based on 
variable domain size) might be worth checking out as well.

* The greedy-dynamic might not be that far off the static one depending on the approach you 
take. I think I re-compute and sort at each step, but you could potentially be much smarter 
and amortize things.

* Couldn't see the pull request, as it's marked private.

I tried a first implementation today. Its a bit hacky, especially the way
options to switch between the different options. My plan was to not merge the
different options and instead just find a good option with some experiments and
then only support that (and reimplement it with less member variables).

I tested four options:
- "input": variable order from the input (currently used in the default branch)
- "random": random shuffle of the previous order
- "greedy": statically sorted by the number of times a variables is used in a
precondition
- "greedy-dynamic": same as before, but the maximizing variable is computed
independently at at every node in the tree.

Random and input order are worse than the greedy orders on average but there are
cases domains where they work better, e.g., psr. In psr, the number of nodes in
the successor generator tree decreases with greedy strategies but the number of
expansions increases, so the change could be caused just by the different order
of operators in the tree.

There is not too much difference between greedy and greedy-dynamic and not a
clear enough trend that would justify the additional construction time the
greedy-strategy takes (up to 3 minutes in large airport tasks) in my opinion.


Detailed results:
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue556-issue556.html

Compare search time against current variable order:
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue556_v1_input_astar_blind_greedy_dynamic_search_time.png
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue556_v1_input_astar_blind_greedy_search_time.png
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue556_v1_input_astar_blind_random_search_time.png

Construction time:
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue556-cactusplot.png

The code is on bitbucket, but I guess its too early for a review, isn't it?
https://bitbucket.org/flogo/downward-issues-issue556/pull-request/1

Hi Christian, I remembered your experiments, and we wanted to notify you of this
issue, but you were faster. :-)

The performance difference between the old and new order is usually not huge,
and in particular the *average* difference is not all that large, but at the
level of individual domains, either order can be much better than the other.

The order used by the preprocessor ("old order") is just the order in which the
translator generates the variables. I'd have to check to be sure, but this is
probably more or less the same as sorting by decreasing domain size with
arbitrary tie-breaking because of the way the variables are selected by greedily
covering the mutex groups.

The order used by the search component ("new order") is the variable order
generated by the preprocessor. For tasks with acyclic causal graphs, this is a
topological sort of the causal graph, starting with the "low-level" variables
that are only modified by operators that depend on any other variables and
ending with the variables that are not used in any preconditions of operators
modifying other variables.

I've played around with this quite a bit in my own work. Best I've found so far is 
to dynamically choose (be smart about how you count the number of remaining 
operators a variable appears as a precondition for, and branch on the variable 
appearing in the most at that stage).

Why is the order chosen so drastically different between the translator generated 
one and the preprocessor generated one? Or is it still very close and just 
drastically different in performance?

Experiments for issue547 showed huge differences between the variable order used
by the preprocessor (generated by the translator) and the variable order used by
the planner (generated by the preprocessor). Choosing a specific variable order
for the successor generator could lead to dramatic speed-ups in generating
successors.

In general, the successor generator only branches if a node has a "star edge",
i.e., if there are operators that do not mention the current variable in their
precondition. The fewer star edges we have to follow, the faster the generation.
One idea to order the variables would thus be to order the variables by the
number of times they occur as preconditions. This could be done statically
(compute the order once) or dynamically (re-compute the order at every node in
the tree).