Issue1171

Title M&S SCC merge strategy: allow working on any SCC
Priority wish Status reviewing
Superseder Nosy List davidspeck, gabi, jendrik, malte, silvan
Assigned To silvan Keywords
Optional summary
Waiting for review: https://github.com/aibasel/downward/pull/244

Created on 2025-02-02.09:36:19 by silvan, last changed by silvan.

Summary
Waiting for review: https://github.com/aibasel/downward/pull/244
Messages
msg11888 (view) Author: silvan Date: 2025-08-14.10:28:41
I agree regarding having fewer options is better. Now that we talked about this, another alternative could be to not introduce the new option, but permanently change the behavior. Doing so would even allow to remove the old option for specifying the order in which each SCC should be dealt with. I never used that option outside the experiments of the paper introducing the strategy. If we go with that alternative, we should document the changed behavior at the existing SCC merge strategy. 

I think I actually slightly prefer this alternative. What do you think?
msg11887 (view) Author: malte Date: 2025-08-11.18:36:47
I wondered about the reason why we want to merge it. It's clearer to me after your answer.

To explain my thought process:

The codebase becomes larger, and now we have more different options to choose from. That's a negative from the complexity standpoint, so we need a positive to offset it.

That you think the new way is more natural would be a stronger argument if it replaced the only way, but here we're adding an option and now have to maintain both ways in the future.

If the new options are useful for something that we will merge later, that's a good reason to include the new option. Adding the reference to the paper that uses the option is an important aspect of this for me, but of course it's fine to add this reference later when it makes more sense, in the place where it makes sense.

Is the place for the reference that you intended the user documentation for the new scoring function(s)? That sounds good to me.
msg11886 (view) Author: silvan Date: 2025-08-11.10:58:39
> You write "We used this option for combining the  "maximum factor"/"maximum SCP" scoring functions from the ICAPS 2024 paper (https://ai.dmi.unibas.ch/papers/sievers-et-al-icaps2024.pdf) with the SCC merge strategy". Who is "we" and where did you use it? In that paper itself?

Yes, "we" was meant as "the authors of that paper". For the paper, we changed the SCC strategy to allow working on any SCC partition because that was a requirement for the "filter-based merge strategy", which would stop the M&S computation once it found that there is no more merge candidate that, when selected, would improve the M&S heuristic compared to stopping the M&S computation. When insisting to consider only one SCC partition at a time, that case would often occur quickly, even though other SCC partitions could potentially offer many more good merge opportunities.

The best configurations in the paper all use the new option. I also think that the new option feels more natural than the old one, but that is probably a question of personal preference.

> If this was used in something somewhere, it would be good to add this to the documentation.
It is used in the paper. I planned to add the reference only when integrating issue1172, where I want to integrate the actual new scoring functions, but I'm happy to include the paper reference already now, if you prefer.
msg11862 (view) Author: malte Date: 2025-07-23.10:59:55
I did a code review.

From the experiments, this doesn't seem to have much of an impact, so I want to ask a bit more about the motivation to test this.

You write "We used this option for combining the  "maximum factor"/"maximum SCP" scoring functions from the ICAPS 2024 paper (https://ai.dmi.unibas.ch/papers/sievers-et-al-icaps2024.pdf) with the SCC merge strategy". Who is "we" and where did you use it? In that paper itself?

If this was used in something somewhere, it would be good to add this to the documentation. Right now it's a bit hard to see the motivation for the change, as every option makes things a little bit more complicated.
msg11799 (view) Author: silvan Date: 2025-02-14.15:54:23
Thanks! They look good to me.
msg11789 (view) Author: davidspeck Date: 2025-02-14.10:03:44
@Silvan Here are the results of the experiments:

https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1171/
msg11781 (view) Author: silvan Date: 2025-02-09.20:43:01
@Gabi: everything is ready for experiments, except the modifications required for the cluster. Could you please run experiments? Or find some other volunteer? ;)

The pull-request is also ready for being reviewed: https://github.com/aibasel/downward/pull/244
msg11777 (view) Author: silvan Date: 2025-02-07.06:53:44
I wanted to run some experiments, since I wanted to make the new option the default for the SCC merge strategy. I started preparing the scripts but I'll look into issue1173 first.
msg11776 (view) Author: davidspeck Date: 2025-02-06.14:40:24
From my understanding (given the PR), is there any experiment planned for this 
issue or has it already been done? We found some issues with the parameter order 
in issue1173 regarding M&S that may affect them.
msg11757 (view) Author: silvan Date: 2025-02-02.09:36:18
In the current implementation, the SCCs clusters are "worked on" one after the other, according to a used-specified order. In this issue, I'd like to add an option to allow merging the best candidate according to the used merge selector, where candidates stem from *all* SCC clusters. We used this option for combining the  "maximum factor"/"maximum SCP" scoring functions from the ICAPS 2024 paper (https://ai.dmi.unibas.ch/papers/sievers-et-al-icaps2024.pdf) with the SCC merge strategy.
History
Date User Action Args
2025-08-14 10:28:41silvansetmessages: + msg11888
2025-08-11 18:36:47maltesetmessages: + msg11887
2025-08-11 10:58:39silvansetmessages: + msg11886
2025-07-23 10:59:55maltesetmessages: + msg11862
2025-02-19 08:54:04silvansetsummary: Waiting for review: https://github.com/aibasel/downward/pull/244
2025-02-14 15:54:23silvansetstatus: in-progress -> reviewing
messages: + msg11799
2025-02-14 10:03:44davidspecksetmessages: + msg11789
2025-02-09 20:43:01silvansetnosy: + gabi
messages: + msg11781
2025-02-07 06:53:44silvansetmessages: + msg11777
2025-02-06 14:40:24davidspecksetnosy: + davidspeck
messages: + msg11776
2025-02-02 09:36:19silvancreate