Created on 2015-07-27.11:45:19 by silvan, last changed by silvan.
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.
|
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.
|
|
Date |
User |
Action |
Args |
2023-07-27 11:28:48 | silvan | set | messages:
+ 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:04 | silvan | set | messages:
+ 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:54 | silvan | set | messages:
+ 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:45 | silvan | set | messages:
+ 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:17 | silvan | set | messages:
+ 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:50 | silvan | set | messages:
+ 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:25 | malte | set | messages:
+ 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:01 | malte | set | messages:
+ 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:09 | silvan | set | messages:
+ 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:05 | silvan | set | messages:
+ 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:19 | silvan | set | messages:
+ 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:34 | silvan | set | messages:
+ 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:44 | silvan | set | 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). -> 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:20 | silvan | set | messages:
+ 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:05 | silvan | set | messages:
+ msg6381 |
2017-02-20 15:32:38 | silvan | set | messages:
+ msg6146 |
2016-12-20 15:22:19 | silvan | set | messages:
+ 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:35 | silvan | set | messages:
+ msg5579 |
2016-08-19 12:21:01 | silvan | set | messages:
+ 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:18 | silvan | set | messages:
+ msg5479 |
2016-05-11 13:46:06 | silvan | set | messages:
+ msg5334 |
2016-04-06 18:45:17 | silvan | set | 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).
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:54 | silvan | set | 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.
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:29 | silvan | set | messages:
+ 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:08 | silvan | set | messages:
+ 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:19 | silvan | set | messages:
+ msg4882 |
2015-11-26 13:28:11 | silvan | set | 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). -> 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:56 | silvan | set | messages:
+ msg4836 |
2015-11-26 13:22:55 | silvan | set | 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). |
2015-11-13 16:36:46 | silvan | set | messages:
+ msg4790 |
2015-11-12 09:26:35 | silvan | set | messages:
+ msg4779 |
2015-08-12 14:03:16 | silvan | set | messages:
+ msg4577 |
2015-07-28 17:56:42 | silvan | set | messages:
+ msg4522 |
2015-07-28 15:05:06 | malte | set | messages:
+ msg4517 |
2015-07-28 15:04:05 | malte | set | messages:
+ msg4516 |
2015-07-27 11:53:50 | malte | set | messages:
+ msg4485 |
2015-07-27 11:45:19 | silvan | create | |
|