Issue567

Title M&S refactoring part 2: meta issue
Priority meta Status chatting
Superseder Nosy List malte, silvan
Assigned To silvan Keywords
Optional summary
Open action items:

A. issue415: better memory management

C. TransitionSystem::compute_locally_equivalent_labels(): make computation
faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is
probably better, because we do not need to consider all transitions in the best
case. [This doesn't seem to be a huuuuuge bottleneck, though. According to
experiments (not on the tracker), it can be up to 10% of merge-and-shrink
construction time in some configs.]

D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the
code used for the IJCAI 2011 paper. See also issue431. This strategy is
also discussed in the ICAPS 2012 paper.

E. Add a max_time parameter similar as in iPDB.

F. Consider adding a max_transitions or similar parameter (see msg4485).

G. Consider performing exact label reduction in some cases where the labels have
different cost.

I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)?

J. Atomic transition system construction could be made faster w.r.t. irrelevant
operators (msg4462, item 1).

K. Atomic transition system construction could be made smarter w.r.t. multiple
conditional effects on the same variable. This would require dedicated domains
to test impact and correctness (msg4462, item 2).

Created on 2015-07-27.11:45:19 by silvan, last changed by silvan.

Summary
Open action items:

A. issue415: better memory management

C. TransitionSystem::compute_locally_equivalent_labels(): make computation
faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is
probably better, because we do not need to consider all transitions in the best
case. [This doesn't seem to be a huuuuuge bottleneck, though. According to
experiments (not on the tracker), it can be up to 10% of merge-and-shrink
construction time in some configs.]

D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the
code used for the IJCAI 2011 paper. See also issue431. This strategy is
also discussed in the ICAPS 2012 paper.

E. Add a max_time parameter similar as in iPDB.

F. Consider adding a max_transitions or similar parameter (see msg4485).

G. Consider performing exact label reduction in some cases where the labels have
different cost.

I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)?

J. Atomic transition system construction could be made faster w.r.t. irrelevant
operators (msg4462, item 1).

K. Atomic transition system construction could be made smarter w.r.t. multiple
conditional effects on the same variable. This would require dedicated domains
to test impact and correctness (msg4462, item 2).
Messages
msg6428 (view) Author: silvan Date: 2017-07-09.15:18:20
Item N is resolved with issue707.
msg6381 (view) Author: silvan Date: 2017-05-19.14:26:05
In the meantime, issue722 adapted the interface of FTS to better mimic the
concepts of applying transformations to it. There is no prune transformation
from outside yet, but issue707 will likely deal with this.
msg6146 (view) Author: silvan Date: 2017-02-20.15:32:37
issue707 will deal address item N.
msg5937 (view) Author: silvan Date: 2016-12-20.15:22:19
In issue682, we dealt with item M.
msg5579 (view) Author: silvan Date: 2016-08-23.14:55:35
issue666 makes ShrinkStrategy::shrink virtual to ease combining different shrink
strategies. It also introduces an iterator for FactoredTransitionSystem.
msg5570 (view) Author: silvan Date: 2016-08-19.12:21:01
The new design for merge strategies which eases plugging together different
types of merge strategies is in place (issue644).
msg5479 (view) Author: silvan Date: 2016-07-26.16:57:18
issue658 introduced creating merge strategies from factories.
msg5334 (view) Author: silvan Date: 2016-05-11.13:46:06
issue655 deals with simplifying the interface of shrink strategies.
msg4980 (view) Author: silvan Date: 2015-12-14.11:25:29
Items B and O, the separation of TransitionSystem into several parts and a
one-shot creation with FTSFactory can be considered done with issue604.
msg4934 (view) Author: silvan Date: 2015-12-10.11:32:08
H. has been addressed in issue599.
msg4882 (view) Author: silvan Date: 2015-12-07.10:49:19
issue601 has been merged: label reduction was moved back to its own file, and
FactoredTransitionSystem was refactored further.
msg4836 (view) Author: silvan Date: 2015-11-26.13:27:56
A few new action items from an old email:

M. heuristic representation:
  - The class that is currently called HeuristicRepresentation doesn't
  represent the heuristic. It represents the abstraction. Suggestion:
  rename it to MergeAndShrinkRepresentation, which is the name we use
  in our ICAPS 2015 paper.
  - We currently have a two-stage heuristic lookup process: map the
  concrete state to an abstract state, then map the abstract state to
  a cost value. The second step is unnecessary since we might as well
  write the cost value directly into the table of the MSR's root node
  (both costs and abstract states are represented by the same type).

N. distances:
  - Distances computation could be made more fine-grained. Which things
    do we really need to recompute after shrinking? When do we need g
    values, and when don't we? It might be a good idea to give the
    shrink strategies and merge strategies a methods that let them tell
    the overall algorithm whether they are interested in g values and/or
    h values; e.g., only shrink_fh would be interested in g values;
    merge_dfp is interested in h values; shrink_bisimulation is
    interested in h values when using greedy bisimulation or when using
    h for initialization (which at the moment we always use?).
  - Should we make pruning irrelevant and/or unreachable states
    configurable? Should it be a *separate* step that is controlled by
    the main merge-and-shrink loop? (Logically, it is a separate
    transformation of the factored transition system. In practice, it
    might be more efficient to couple it with other steps.)
  - The vector<bool> of prunable states should probably be accessed the
    same way as the g and h values, rather than using a separate
    interface as it is done currently (g and h are stored in the
    Distance object and requested individually; prunability is returned
    as a complete vector).

O. FTSFactory
  - We currently have a two-stage initialization for the atomic
    transition systems. First, they are created in an incomplete state,
    and then the factory takes over the rest of the initialization. We
    should have a constructor that generates them in one shot.
msg4790 (view) Author: silvan Date: 2015-11-13.16:36:46
issue595 addresses a bug in DFP and will also refactor it.
msg4779 (view) Author: silvan Date: 2015-11-12.09:26:35
issue583 has been merged. Item B, "splitting TransitionSystem" into several
parts, can be considered done, but the new class FactoredTransitionSystem still
allows further improvements.
msg4577 (view) Author: silvan Date: 2015-08-12.14:03:16
issue571 has been merged. There is still more to do in the spirit of item B).
msg4522 (view) Author: silvan Date: 2015-07-28.17:56:42
See issue571 for the next steps of item B).
msg4517 (view) Author: malte Date: 2015-07-28.15:05:06
Some additional items:

H. Introduce a namespace for merge-and-shrink.

I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)?

J. Atomic transition system construction could be made faster w.r.t. irrelevant
operators (msg4462, item 1).

K. Atomic transition system construction could be made smarter w.r.t. multiple
conditional effects on the same variable. This would require dedicated domains
to test impact and correctness (msg4462, item 2).

L. TransitionSystem::get_init_distance() and
TransitionSystem::get_goal_distance() should disappear; instead the Distances
object should be asked directly. This should be an inlinable code path (msg4467,
msg4468).
msg4516 (view) Author: malte Date: 2015-07-28.15:04:05
Let's assign some letters to the action items we have mentioned so far:

A. issue415: better memory management

B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.)

C. TransitionSystem::compute_locally_equivalent_labels(): make computation
faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is
probably better, because we do not need to consider all transitions in the best
case. [This doesn't seem to be a huuuuuge bottleneck, though. According to
experiments (not on the tracker), it can be up to 10% of merge-and-shrink
construction time in some configs.]

D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the
code used for the IJCAI 2011 paper. See also issue431.

E. Add a max_time parameter similar as in iPDB.

F. Consider adding a max_transitions or similar parameter (see msg4485).

G. Consider performing exact label reduction in some cases where the labels have
different cost.
msg4485 (view) Author: malte Date: 2015-07-27.11:53:50
Two additional notes that I made when we recently read the IJCAI 2015 paper on
simulation in M&S by Álvaro and Jörg:

- They use a "max_transitions" limit to control M&S generation. (See Section 8,
second paragraph.) It would be useful for us to implement this. The transitions
are harder to control than the states, but they are also more important. (They
use this to abort the construction process, rather than to control how much to
shrink. If we copy this behaviour, perhaps the name should be sufficiently
distinguished from max_states etc. to make this clear.)

- There are cases where exact label reduction is possible even though the two
labels have different cost. Perhaps we want to look into this.
msg4483 (view) Author: silvan Date: 2015-07-27.11:45:19
This meta issue is the continuation of issue432, to have a clean overview of all
upcoming issue which are due to code reviewing.

To start off, these are the open issues left over from issue432:
- issue415: better memory management
- issue561: split off TransitionSystem into several parts

Further three comments from an old refactoring list, although unclear if they
are going to be addressed:
- TransitionSystem::compute_local_equivalence_relation():
  make computation faster through sorting transitions (O(n log n)) or hashing
  (O(n)). Sorting is probably better, because we do not need to consider all
  transitions in the best case.

- Add a hybrid bisimulation/greedy bisimulation strategy, inspired from
  the code used for the IJCAI 2011 paper. See also issue431.

- Add a max_time parameter similar as in iPDB.
History
Date User Action Args
2017-07-09 15:18:20silvansetmessages: + msg6428
summary: Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). -> Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2).
2017-05-19 14:26:05silvansetmessages: + msg6381
2017-02-20 15:32:38silvansetmessages: + msg6146
2016-12-20 15:22:19silvansetmessages: + msg5937
summary: Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). -> Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector).
2016-08-23 14:55:35silvansetmessages: + msg5579
2016-08-19 12:21:01silvansetmessages: + msg5570
summary: Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). O. merge strategies: - improve interface and make a distinction between precomputed and non-precomputed merge strategies (issue644) -> Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector).
2016-07-26 16:57:18silvansetmessages: + msg5479
2016-05-11 13:46:06silvansetmessages: + msg5334
2016-04-06 18:45:17silvansetsummary: Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). -> Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). O. merge strategies: - improve interface and make a distinction between precomputed and non-precomputed merge strategies (issue644)
2016-02-17 12:17:54silvansetsummary: Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). -> Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. This strategy is also discussed in the ICAPS 2012 paper. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector).
2015-12-14 11:25:29silvansetmessages: + msg4980
summary: Open action items: A. issue415: better memory management B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.) C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). O. FTSFactory - We currently have a two-stage initialization for the atomic transition systems. First, they are created in an incomplete state, and then the factory takes over the rest of the initialization. We should have a constructor that generates them in one shot. -> Open action items: A. issue415: better memory management C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector).
2015-12-10 11:32:08silvansetmessages: + msg4934
summary: Open action items: A. issue415: better memory management B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.) C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. H. Introduce a namespace for merge-and-shrink. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). O. FTSFactory - We currently have a two-stage initialization for the atomic transition systems. First, they are created in an incomplete state, and then the factory takes over the rest of the initialization. We should have a constructor that generates them in one shot. -> Open action items: A. issue415: better memory management B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.) C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). O. FTSFactory - We currently have a two-stage initialization for the atomic transition systems. First, they are created in an incomplete state, and then the factory takes over the rest of the initialization. We should have a constructor that generates them in one shot.
2015-12-07 10:49:19silvansetmessages: + msg4882
2015-11-26 13:28:11silvansetsummary: Open action items: A. issue415: better memory management B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.) C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. H. Introduce a namespace for merge-and-shrink. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). -> Open action items: A. issue415: better memory management B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.) C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. H. Introduce a namespace for merge-and-shrink. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2). M. heuristic representation: - The class that is currently called HeuristicRepresentation doesn't represent the heuristic. It represents the abstraction. Suggestion: rename it to MergeAndShrinkRepresentation, which is the name we use in our ICAPS 2015 paper. - We currently have a two-stage heuristic lookup process: map the concrete state to an abstract state, then map the abstract state to a cost value. The second step is unnecessary since we might as well write the cost value directly into the table of the MSR's root node (both costs and abstract states are represented by the same type). N. distances: - Distances computation could be made more fine-grained. Which things do we really need to recompute after shrinking? When do we need g values, and when don't we? It might be a good idea to give the shrink strategies and merge strategies a methods that let them tell the overall algorithm whether they are interested in g values and/or h values; e.g., only shrink_fh would be interested in g values; merge_dfp is interested in h values; shrink_bisimulation is interested in h values when using greedy bisimulation or when using h for initialization (which at the moment we always use?). - Should we make pruning irrelevant and/or unreachable states configurable? Should it be a *separate* step that is controlled by the main merge-and-shrink loop? (Logically, it is a separate transformation of the factored transition system. In practice, it might be more efficient to couple it with other steps.) - The vector<bool> of prunable states should probably be accessed the same way as the g and h values, rather than using a separate interface as it is done currently (g and h are stored in the Distance object and requested individually; prunability is returned as a complete vector). O. FTSFactory - We currently have a two-stage initialization for the atomic transition systems. First, they are created in an incomplete state, and then the factory takes over the rest of the initialization. We should have a constructor that generates them in one shot.
2015-11-26 13:27:56silvansetmessages: + msg4836
2015-11-26 13:22:55silvansetsummary: Open action items: A. issue415: better memory management B. Continue splitting TransitionSystem into several parts. (issue561 is now merged.) C. TransitionSystem::compute_locally_equivalent_labels(): make computation faster through sorting transitions (O(n log n)) or hashing (O(n)). Sorting is probably better, because we do not need to consider all transitions in the best case. [This doesn't seem to be a huuuuuge bottleneck, though. According to experiments (not on the tracker), it can be up to 10% of merge-and-shrink construction time in some configs.] D. Add a hybrid bisimulation/greedy bisimulation strategy, inspired from the code used for the IJCAI 2011 paper. See also issue431. E. Add a max_time parameter similar as in iPDB. F. Consider adding a max_transitions or similar parameter (see msg4485). G. Consider performing exact label reduction in some cases where the labels have different cost. H. Introduce a namespace for merge-and-shrink. I. Reconsider default values for shrinking strategy limits (msg4429, msg4430)? J. Atomic transition system construction could be made faster w.r.t. irrelevant operators (msg4462, item 1). K. Atomic transition system construction could be made smarter w.r.t. multiple conditional effects on the same variable. This would require dedicated domains to test impact and correctness (msg4462, item 2).
2015-11-13 16:36:46silvansetmessages: + msg4790
2015-11-12 09:26:35silvansetmessages: + msg4779
2015-08-12 14:03:16silvansetmessages: + msg4577
2015-07-28 17:56:42silvansetmessages: + msg4522
2015-07-28 15:05:06maltesetmessages: + msg4517
2015-07-28 15:04:05maltesetmessages: + msg4516
2015-07-27 11:53:50maltesetmessages: + msg4485
2015-07-27 11:45:19silvancreate