Closing this wish issue due to lack of activity in the last 8 years. If someone wants to work on integrating symmetry code, of course feel free to reopen this, but I don't think there is value in keeping the old issue alive without an implementation or plan to work on one.

> 2) How would we integrate Bliss? Including the sources into Fast Downward is
> probably something we would not like, and providing an interface like the one
> for the LP code is something not very trivial, I assume, also because in my
> current implementation, I changed Bliss to throw exceptions when running out of
> memory or time, so that Fast Downward can intercept those and still continue
> regular search/heuristic construction nevertheless.

I think there are three main options:

1. Do not support time or memory limits for symmetry construction. This is the
easiest option but obviously not the one with which we will be able to get the
best results.

2. Use a modified version of Bliss that internally supports time and memory
limits. This will give us stronger results and is something we already have
experience with. The drawbacks are that we need to hack the Bliss code, which I
guess is generally painful and will make it difficult to move to a newer Bliss
version or to another symmetry generator. It is also in general impossible to
make such an approach completely robust if Bliss isn't already built with
something like this in mind. There is always a chance that we run out of memory
or time in contexts from which it is difficult to recover, and of course once we
have to abort a Bliss computation in a certain context, we cannot expect any
further Bliss computations to work correctly, which is problematic if we want to
use Bliss in multiple unrelated parts of the planner.

3. Use OS-level functionality to enforce time and memory limits. This requires
running Bliss in a separate process. The main drawback with this is that it
requires inter-process communication, which is more complicated to implement
than in-process argument passing and has time and memory costs for copying data.
On the positive side, this could be done very cleanly, as it would allow us
recovering from running out of time or memory at any point in the Bliss
invocation without difficulty.

Thanks for pointing this out. As I already discussed with Michael, I see two
(other) main issues that would need to be resolved when working on this issue:

1) There would be a considerable amount of refactoring needed to be done so that
the symmetries related classes have a clean design, concerning the
responsibility and the readability. I already changed some parts of the code I
took from Metis, but it is far from being in a clean state for merging.

2) How would we integrate Bliss? Including the sources into Fast Downward is
probably something we would not like, and providing an interface like the one
for the LP code is something not very trivial, I assume, also because in my
current implementation, I changed Bliss to throw exceptions when running out of
memory or time, so that Fast Downward can intercept those and still continue
regular search/heuristic construction nevertheless.

I just wanted to add a point that we discussed when we tried to implement this
for Metis.

A straight-forward implementation of orbit search was problematic for the method
reach_state():
If we reach s' from from s with o, we make the following calls in regular A* search:

    reach_state(s, o, s');
    heuristic->evaluate(s');

In orbit search, we can replace one (or both) occurrences of s' with the
canonical representative of s'.

If we don't replace s' in the call to evaluate(), then we evaluate a different
state than the one that is added to the open list. Heuristics will also see
states that are not canonical representatives. If a heuristic stores information
for each state, it will think that some states with the same canonical
representative are the same.

If we replace s' only in the call to evaluate, the heuristic might get calls to
reach_state() and evaluate() for different states. This case was problematic for
incremental LM-cut.

If we replace s' in both cases, then reach_state() no longer has the property
that applying the operator to the parent state results in the child state. This
was also problematic for incremental LM-cut.

Integration of orbit search, which is syntactically easier to integrate than the DKS 
algorithm.

Orbit search is a variant of A*, searching in a space of "state orbits", defined by 
a "canonical" symmetrical state for each state.

Up sides: orbit search is able to prune structurally symmetric states, considerably 
reducing the number of expansions on many IPC benchmarks
Down side: in the most general form, orbit search may operate with states that are 
not reachable from the initial state, while some heuristics may assume that the 
evaluated states are reachable from the initial state (example: merge and shrink).