Enables issue800.

I suggest to move this discussion to issue1108 where we talk about updating the terminology in this section of the code.

From a quick glance at the code, I think it is neither UCP nor OUCP but some kind of hybrid. (If memory serves, this was out original inspiration for OUCP.) The special treatment of action landmarks is similar to OUCP, but it looks like after all action landmarks are processed, the "rest" is like a regular UCP.

Looks like an opportunity to improve things. This can include any subset of:

1) changing the parameter strings
2) updating the documentation
3) updating the code (class names, method names, variable names, comments etc.)

If I read the code correctly, this also raises the question whether we should offer a full OUCP which would dominate what I think the existing algorithm does but might also be more expensive to compute. We might want to makes this a separate issue.

I think cost_partitioning=uniform actually computes an opportunistic uniform cost partitioning, so we should probably rename the option value to cost_partitioning=opportunistic_uniform.

Merged! Thank you Jendrik. :)

Looks good to me.

Suggestion for the commit message:

[issue1091] Change landmark cost partitioning option from bool to enum.

Users of the landmark cost partitioning heuristic must specify which cost
partitioning strategy to use. There are two strategies available right now,
namely uniform or optimal cost partitioning. Previously, the command line option
to choose between them was a boolean "optimal=(false|true)". This changed to an
enum option "cost_partitioning=(uniform|optimal)" to prepare for more choices to
be implemented in the future.


Thoughts or comments?

I'd clean up the terminology in the follow-up issue. The aliases and test configs are tested automatically by the GitHub Actions. I also think this is ready to be merged.

Apparently the old option "optimal=true" was never used in aliases or other pre-defined configs, so nothing more to be changed in my opinion. So I think this is good to be merged.

Good point, I'll open a new issue to discuss further details there. But is it okay if we leave the terminology inconsistent until we get to work on that issue or should I use "assignment" rather than "partitioning" in the added/adapted code?

Given that I changed the user interface, I should also look at aliases and test-configurations etc. to make sure they still work. I forgot to do that so far. What about experiments? Does anybody see the need to run something?

I like your suggestion. I'd do this in a separate issue though to keep the diffs small and separate the user-facing change from the renaming change.

Thanks! While we're at it: Should we change the terminology from cost assignment to cost partitioning? I used cost partitioning in some of the new additions and in particular the command line option, so at the moment it's a bit inconsistent. Is there a good argument for "assignment" because to me it feels a bit outdated.

Looks good to me. I added two small comments.

I forgot to add a link to the pull request... here it is: https://github.com/aibasel/downward/pull/173

I've created a pull request for this issue. The solution I opted for is not creating plugins but simply choosing from an enum. I've found other places in the code base where things are done similarly. Proper plugins might still be a nicer solution, but I didn't find a nice way to do it...

Would somebody mind looking at the pull request? It is very small and I would like to have a discussion whether this is the way to go. If yes, I personally don't think experiments would be necessary, but I could set up a quick one nevertheless.

> Thanks for your input, Silvan and Florian! I suggest we discuss the sub-directory
> topic somewhere else, for example in a Fast Downward meeting. Silvan, can you
> note that down somewhere? I'll also try to remember when you're asking for topics
> for a meeting next time.

If you're interested in the subdirectory discussion, I suggest you also look at issue1100.

Thanks for your input, Silvan and Florian! I suggest we discuss the sub-directory topic somewhere else, for example in a Fast Downward meeting. Silvan, can you note that down somewhere? I'll also try to remember when you're asking for topics for a meeting next time.

I'd like to comment on Florian's suggestion to make the landmarks an argument of the cost-partitioning strategy. I've thought about that, but I think it makes other things more complicated. To give some more context, we currently have an abstract class LandmarkHeuristic which expects a landmark generation strategy (LandmarkFactory) as input. The LandmarkHeuristic offers a function to add this as an option to the feature. We then have two implementations of LandmarkHeuristic, i.e., LandmarkCostPartitioningHeuristic and LandmarkSumHeuristic. Both of them are symmetric in the sense that the first argument they expect is the landmark factory. The cost partitioning strategy is (obviously) only relevant for the LandmarkCostPartitioningHeuristic. I think it wouldn't be a big step to specify the landmark factory inside the cost partitioning, but it removes some symmetries we currently have in all implementations of LandmarkHeuristic which is something I like. Also, to me it feels more natural to specify what kinds of landmarks you want to use on the level of the heuristic rather than the cost partitioning strategy.

Of course it would be nice to have cost partitioning strategies defined only once for different kinds of heuristi, not only landmark heuristics. Nevertheless, I don't think this should keep us from moving forward with this issue or issue800 because I fear it would mean we'd just not implement more cost partitionings for landmarks for a while.

Regarding the subdirectories: As far as I remember the idea was to synchronize them with namespaces (i.e., namespace X is in subdirectory X), with exceptions for directories that group many small namespaces (like "heuristics"). Having nested directories would imply nested namespaces. I'm don't have a strong opinion either way, I just wanted to point out the connection to namespaces.

Regarding the component interaction: maybe one option would be to change the nesting. Instead of "landmarks(partitioning=optimal())" it could be "optimal_partitioning(landmarks())". I don't know this code well enough to make this more concrete, though. In general, it would be nice to think about a more general interface of cost partitioning where different heuristics that support it could be cost partitioned in different ways. I'm not sure if we can find a solution that fits all cases though.

Finally, regarding the implementation within the feature class: we should definitely discuss this first. Making the feature class and the factory class the same could be an option but this is the bleeding edge of the component interaction problem and we should consider this carefully before committing to one solution.

I don't think there is a problem here. You should be able to define LandmarkCostAssignmentFactory classes which are generated through the plugin and which have a method "generate" that accept the landmark graph (and what not else) to compute the LandmarkCostAssignment object when the heuristic wants. We use this kind of two-stage factory/builder/generator approach in M&S, for instance. It has the drawback that you have two classes for each plugin instead of one. I think with the new option parser, if the factory is sufficiently small, you could also consider implementing the factory not as a standalone class, but within the plugin definition. At least this is what Florian said that we could do - but we don't have any convention yet as far as I know.

Thanks for your input Silvan! I would be very interested in such a discussion. 

I started working on this issue but it is not as straightforward as I thought; the component interaction problem strikes again (I believe). The constructor for these cost assignments depends on the landmark graph to be constructed first. Since we want to define the landmark factory on the same level as the cost partitioning strategy (i.e., within the heuristic), this is not possible. Instead of plugins or a binary option, we could of course use an enum, but maybe there's a better way that I did not consider so far. Any ideas or pointers to similar cases?

Same issue for the M&S directory which is huge and would benefit from having subdirectories. I vaguely remember that I once asked Malte about introducing subdirectories and that there were some (technical?) reasons not to do so, but this might be completely wrong. Maybe we can discuss this if/when we have a story that includes this issue.

Currently, all cost partitioning strategies are implemented in the same file *landmark_cost_assignment.cc*. Given that we plan to add more of these strategies, it might be a good idea to split this up into separate files for every concept. Do you agree? If yes, I think it would make sense to also do this within this setup issue rather than the one where we add new features.

If we do this, it means we'll add several new files to the directory "src/search/landmarks". While I believe this is a good thing, because it makes each individual file cleaner, I don't particularly like the implications for this directory. 
On the one hand, I personally think it would make my life easier if we had a subdirectory "cost_partitioning" within the "landmark" directory, but this is not something we typically do. One thing I would especially like about this is the following: When I split the file "landmark_cost_assignment" into one for every concrete implementation, I would prefer "landmark_*_cost_assignment" over "landmark_cost_assignment_*" where * is a placeholder for one of {uniform, optimal, zero_one, saturated, ...}. In the current structure, the second option would keep everything cost-assignment-related close together (when sorted alphabetically) while the first scatters them throughout the directory. With a sub-directory for cost assignments/partitionings, everything would always be found at close to the related stuff. 
On the other hand, sub-directories would allow to have shorter filenames. With names like "landmark_cost_partitioning_*" the term that really distinguishes these files is the last part of the filename, which I don't like too much. It would be much nicer, in my opinion, if the file starts with the information that distinguishes it from other similar stuff. But again, if the name would start with the important information, then the (alphabetical) order of the files is not as clear anymore, that's probably why we don't usually do that.

This is probably not the right place to discuss this, but I would like to understand whether there are strong reasons to have the "flat" directory structure we have or what your take on this topic is.

The landmark cost partitioning heuristic currently supports two types of cost partitioning strategies: optimal cost partitioning and uniform cost partitioning. In the plugin, the user can specify which one to use by specifying "optimal=true|false". We want to implement more cost partitioning strategies in issue800. This means we can no longer use a binary option to choose the cost partitioning strategy.

I think it makes sense to separate adding new features (i.e., new strategies) from the setup. It makes the changes smaller and easier to understand. Hence, in this issue I'd like to switch from binary option to a proper plugin for choosing the cost partitioning strategy in the landmark cost partitioning heuristic.