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.]

More generally, investigate different algorithms and data structures for 
computing local equivalence relations to potentially further accelerate the
computation of label reductions. It would be useful to analyze which parts of
label reductions are bottlenecks of the computation.

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. (issue802)

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 => issue851). Some ideas on how to further improve 
performance can be found in the summary of issue851.

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).

P. The current design of merge strategy factories is a bit flawed: they require
knowledge about the task (its variables, in case of linear merge strategies; or
the causal graph, in case of hybrid strategies like the SCC framework). In
particular, using merge trees (and their factories) within hybrid strategies is
not easily possible without storing further knowledge on the task, such as which
variables are contained in which components. We want to discuss this issue and
come up with a better design that matches our view 
of factored transition systems consisting of variables (the factors).

Q. Merge-and-shrink should internally use separate plug-ins like we do in other 
cases, too; it is not really in keeping with the overall component architecture 
for merge-and-shrink to be all or nothing.

R. Separate the merge-and-shrink computation from the heuristic. (issue849)

S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914)

T. Rework data structures used to store labels and their transitions: get rid of
using list and unordered_map and use vectors instead. (issue927)

U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. 
In particular, move everything related to local labels (introduced in issue927)
to their own class, similar to what LabelEquivalenceRelation used to be, but
hopefully with an improved interface which makes sure that label groups and
their transitions are always in a valid state when doing something in
TransitionSystem.

V. Working on item T (issue927), we noted in some experiments that label
reduction, and in particular computing the theta combinability equivalence
relation using class EquivalenceRelation, can be a bottle neck of the 
merge-and-shrink computation. We should investigate if EquivalenceRelation
can be implemented more efficiently or if data structures used for label
reductions can be improved to allow faster computation.

W. Introduce a caching option for the MIASM scoring function to avoid repeatedly
computing the product systems for all merge candidates (issue1092).

X. Working on issue1092, we realized that for introducing global
caching mechanisms in scoring functions, we would need to have a
mechanism to let the merge-and-shrink algorithm (with its general
strategy) notify all transformation strategies (in particular, the
merge strategy for the feature mentioned before) of each transformation
(or maybe rather: the properties of the transformation and which
factors were affected) applied to the factored transition system.
Having a common interface for transformation strategies could be useful
for that change.

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.]

More generally, investigate different algorithms and data structures for 
computing local equivalence relations to potentially further accelerate the
computation of label reductions. It would be useful to analyze which parts of
label reductions are bottlenecks of the computation.

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. (issue802)

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 => issue851). Some ideas on how to further improve 
performance can be found in the summary of issue851.

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).

P. The current design of merge strategy factories is a bit flawed: they require
knowledge about the task (its variables, in case of linear merge strategies; or
the causal graph, in case of hybrid strategies like the SCC framework). In
particular, using merge trees (and their factories) within hybrid strategies is
not easily possible without storing further knowledge on the task, such as which
variables are contained in which components. We want to discuss this issue and
come up with a better design that matches our view 
of factored transition systems consisting of variables (the factors).

Q. Merge-and-shrink should internally use separate plug-ins like we do in other 
cases, too; it is not really in keeping with the overall component architecture 
for merge-and-shrink to be all or nothing.

R. Separate the merge-and-shrink computation from the heuristic. (issue849)

S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914)

T. Rework data structures used to store labels and their transitions: get rid of
using list and unordered_map and use vectors instead. (issue927)

U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. 
In particular, move everything related to local labels (introduced in issue927)
to their own class, similar to what LabelEquivalenceRelation used to be, but
hopefully with an improved interface which makes sure that label groups and
their transitions are always in a valid state when doing something in
TransitionSystem.

V. Working on item T (issue927), we noted in some experiments that label
reduction, and in particular computing the theta combinability equivalence
relation using class EquivalenceRelation, can be a bottle neck of the 
merge-and-shrink computation. We should investigate if EquivalenceRelation
can be implemented more efficiently or if data structures used for label
reductions can be improved to allow faster computation.

W. Introduce a caching option for the MIASM scoring function to avoid repeatedly
computing the product systems for all merge candidates (issue1092).

X. Working on issue1092, we realized that for introducing global
caching mechanisms in scoring functions, we would need to have a
mechanism to let the merge-and-shrink algorithm (with its general
strategy) notify all transformation strategies (in particular, the
merge strategy for the feature mentioned before) of each transformation
(or maybe rather: the properties of the transformation and which
factors were affected) applied to the factored transition system.
Having a common interface for transformation strategies could be useful
for that change.
Messages
msg11209 (view) Author: silvan Date: 2023-07-27.11:28:48
Add item X: broader refactoring for introducing transformation strategies
and a notify mechanism for informing transformation strategies of transformations
applied by the merge-and-shrink algorithm (aka. the general strategy).
msg11207 (view) Author: silvan Date: 2023-07-27.11:05:04
add item W - issue1092
msg11019 (view) Author: silvan Date: 2023-02-14.16:36:54
Add item V:

V. Working on item T (issue927), we noted in some experiments that label
reduction, and in particular computing the theta combinability equivalence
relation using class EquivalenceRelation, can be a bottle neck of the 
merge-and-shrink computation. We should investigate if EquivalenceRelation
can be implemented more efficiently or if data structures used for label
reductions can be improved to allow faster computation.
msg11018 (view) Author: silvan Date: 2023-02-14.16:34:45
Add items T (already done in issue927) and U:

T. Rework data structures used to store labels and their transitions: get rid of
using list and unordered_map and use vectors instead. (issue927)

U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. 
In particular, move everything related to local labels (introduced in issue927)
to their own class, similar to what LabelEquivalenceRelation used to be, but
hopefully with an improved interface which makes sure that label groups and
their transitions are always in a valid state when doing something in
TransitionSystem.
msg8965 (view) Author: silvan Date: 2019-09-26.14:21:17
Add item S: 
Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function.
msg8392 (view) Author: silvan Date: 2018-12-18.16:32:50
Add a note to item J about further possible ideas for improvements that are
left-over from issue851.
msg7853 (view) Author: malte Date: 2018-10-03.16:25:25
Actually, what I made item S was already in the list as item J. I have removed
the item and instead added a pointer to the relevant issue851 to item J.
msg7852 (view) Author: malte Date: 2018-10-03.16:24:01
Add item S.
msg7832 (view) Author: silvan Date: 2018-10-02.18:56:09
Add issue802 to item E. Add item R.
msg7175 (view) Author: silvan Date: 2018-06-04.18:26:05
Extend item C to further investigate making label reductions faster more
generally, e.g. through using different algorithms and data structures for label
equivalence relations.
msg7162 (view) Author: silvan Date: 2018-06-04.14:19:19
Add new action item (quoted from Malte @ issue668).
msg7065 (view) Author: silvan Date: 2018-04-22.14:24:34
Change item letter.
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
2023-07-27 11:28:48silvansetmessages: + msg11209
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem. V. Working on item T (issue927), we noted in some experiments that label reduction, and in particular computing the theta combinability equivalence relation using class EquivalenceRelation, can be a bottle neck of the merge-and-shrink computation. We should investigate if EquivalenceRelation can be implemented more efficiently or if data structures used for label reductions can be improved to allow faster computation. W. Introduce a caching option for the MIASM scoring function to avoid repeatedly computing the product systems for all merge candidates (issue1092). -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem. V. Working on item T (issue927), we noted in some experiments that label reduction, and in particular computing the theta combinability equivalence relation using class EquivalenceRelation, can be a bottle neck of the merge-and-shrink computation. We should investigate if EquivalenceRelation can be implemented more efficiently or if data structures used for label reductions can be improved to allow faster computation. W. Introduce a caching option for the MIASM scoring function to avoid repeatedly computing the product systems for all merge candidates (issue1092). X. Working on issue1092, we realized that for introducing global caching mechanisms in scoring functions, we would need to have a mechanism to let the merge-and-shrink algorithm (with its general strategy) notify all transformation strategies (in particular, the merge strategy for the feature mentioned before) of each transformation (or maybe rather: the properties of the transformation and which factors were affected) applied to the factored transition system. Having a common interface for transformation strategies could be useful for that change.
2023-07-27 11:05:04silvansetmessages: + msg11207
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem. V. Working on item T (issue927), we noted in some experiments that label reduction, and in particular computing the theta combinability equivalence relation using class EquivalenceRelation, can be a bottle neck of the merge-and-shrink computation. We should investigate if EquivalenceRelation can be implemented more efficiently or if data structures used for label reductions can be improved to allow faster computation. -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem. V. Working on item T (issue927), we noted in some experiments that label reduction, and in particular computing the theta combinability equivalence relation using class EquivalenceRelation, can be a bottle neck of the merge-and-shrink computation. We should investigate if EquivalenceRelation can be implemented more efficiently or if data structures used for label reductions can be improved to allow faster computation. W. Introduce a caching option for the MIASM scoring function to avoid repeatedly computing the product systems for all merge candidates (issue1092).
2023-02-14 16:36:54silvansetmessages: + msg11019
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem. -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem. V. Working on item T (issue927), we noted in some experiments that label reduction, and in particular computing the theta combinability equivalence relation using class EquivalenceRelation, can be a bottle neck of the merge-and-shrink computation. We should investigate if EquivalenceRelation can be implemented more efficiently or if data structures used for label reductions can be improved to allow faster computation.
2023-02-14 16:34:45silvansetmessages: + msg11018
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914) T. Rework data structures used to store labels and their transitions: get rid of using list and unordered_map and use vectors instead. (issue927) U. Follow-up to T.: refactor TransitionSystem to reduce the size of the class. In particular, move everything related to local labels (introduced in issue927) to their own class, similar to what LabelEquivalenceRelation used to be, but hopefully with an improved interface which makes sure that label groups and their transitions are always in a valid state when doing something in TransitionSystem.
2019-09-26 14:21:17silvansetmessages: + msg8965
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. Let the merge-and-shrink heuristic filter "trivial factors" when the merge-and-shrink algorithm terminates with more than one factor (through imposing a time limit). A factor is trivial iff all of its states are goal states and the corresponding merge-and-shrink representation is a total function. (issue914)
2018-12-18 16:32:50silvansetmessages: + msg8392
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). Some ideas on how to further improve performance can be found in the summary of issue851. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849)
2018-10-03 16:25:25maltesetmessages: + msg7853
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. more efficient computation of transitions of irrelevant operators (issue851) -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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 => issue851). 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849)
2018-10-03 16:24:01maltesetmessages: + msg7852
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849) S. more efficient computation of transitions of irrelevant operators (issue851)
2018-10-02 18:56:09silvansetmessages: + msg7832
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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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. (issue802) 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. R. Separate the merge-and-shrink computation from the heuristic. (issue849)
2018-06-04 18:26:05silvansetmessages: + msg7175
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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing. -> 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.] More generally, investigate different algorithms and data structures for computing local equivalence relations to potentially further accelerate the computation of label reductions. It would be useful to analyze which parts of label reductions are bottlenecks of the computation. 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing.
2018-06-04 14:19:19silvansetmessages: + msg7162
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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). -> 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). Q. Merge-and-shrink should internally use separate plug-ins like we do in other cases, too; it is not really in keeping with the overall component architecture for merge-and-shrink to be all or nothing.
2018-04-22 14:24:34silvansetmessages: + msg7065
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). L. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors). -> 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). P. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors).
2018-03-14 18:05:44silvansetsummary: 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). -> 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). L. The current design of merge strategy factories is a bit flawed: they require knowledge about the task (its variables, in case of linear merge strategies; or the causal graph, in case of hybrid strategies like the SCC framework). In particular, using merge trees (and their factories) within hybrid strategies is not easily possible without storing further knowledge on the task, such as which variables are contained in which components. We want to discuss this issue and come up with a better design that matches our view of factored transition systems consisting of variables (the factors).
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