|
Size: 4896
Comment:
|
← Revision 36 as of 2024-01-11 22:26:37 ⇥
Size: 4380
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Merge strategy DFP == | == Precomputed merge strategy == |
| Line 7: | Line 7: |
| This merge strategy implements the algorithm originally described in the paper "Directed model checking with distance-preserving abstractions" by Draeger, Finkbeiner and Podelski (SPIN 2006), adapted to planning in the following paper: | This merge strategy has a precomputed merge tree. Note that this merge strategy does not take into account the current state of the factored transition system. This also means that this merge strategy relies on the factored transition system being synchronized with this merge tree, i.e. all merges are performed exactly as given by the merge tree. {{{ merge_precomputed(merge_tree, verbosity=normal) }}} * ''merge_tree'' ([[Doc/MergeTree|MergeTree]]): The precomputed merge tree. * ''verbosity'' ({silent, normal, verbose, debug}): Option to specify the verbosity level. * {{{silent}}}: only the most basic output * {{{normal}}}: relevant information to monitor progress * {{{verbose}}}: full output * {{{debug}}}: like verbose with additional debug output '''Note:''' An example of a precomputed merge startegy is a linear merge strategy, which can be obtained using: {{{ merge_strategy=merge_precomputed(merge_tree=linear(<variable_order>)) }}} == Merge strategy SSCs == This merge strategy implements the algorithm described in the paper |
| Line 10: | Line 30: |
| [[http://ai.cs.unibas.ch/papers/sievers-et-al-aaai2014.pdf|Generalized Label Reduction for Merge-and-Shrink Heuristics]].<<BR>> In ''Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014)'', pp. 2358-2366. AAAI Press 2014. |
[[https://ai.dmi.unibas.ch/papers/sievers-et-al-icaps2016.pdf|An Analysis of Merge Strategies for Merge-and-Shrink Heuristics]].<<BR>> In ''Proceedings of the 26th International Conference on Planning and Scheduling (ICAPS 2016)'', pp. 2358-2366. AAAI Press, 2016. |
| Line 13: | Line 33: |
| Using this command line option is deprecated, please use the equivalent call: merge_strategy=merge_stateless(merge_selector=score_based_filtering(scoring_functions=[goal_relevance,dfp,total_order(<order_option>))]))if specifying tie-breaking order criteria or: merge_strategy=merge_stateless(merge_selector=score_based_filtering(scoring_functions=[goal_relevance,dfp,single_random()]))if using full random tie-breaking. | In a nutshell, it computes the maximal SCCs of the causal graph, obtaining a partitioning of the task's variables. Every such partition is then merged individually, using the specified fallback merge strategy, considering the SCCs in a configurable order. Afterwards, all resulting composite abstractions are merged to form the final abstraction, again using the specified fallback merge strategy and the configurable order of the SCCs. |
| Line 16: | Line 36: |
| merge_dfp(atomic_ts_order=reverse_level, product_ts_order=new_to_old, atomic_before_product=false, random_seed=-1, randomized_order=false) | merge_sccs(order_of_sccs=topological, merge_tree=<none>, merge_selector=<none>, verbosity=normal) |
| Line 19: | Line 39: |
| * ''atomic_ts_order'' ({reverse_level, level, random}): The order in which atomic transition systems are considered when considering pairs of potential merges. * {{{reverse_level}}}: the variable order of Fast Downward * {{{level}}}: opposite of reverse_level * {{{random}}}: a randomized order * ''product_ts_order'' ({old_to_new, new_to_old, random}): The order in which product transition systems are considered when considering pairs of potential merges. * {{{old_to_new}}}: consider composite transition systems from most recent to oldest, that is in decreasing index order * {{{new_to_old}}}: opposite of old_to_new * {{{random}}}: a randomized order * ''atomic_before_product'' (bool): Consider atomic transition systems before composite ones iff true. * ''random_seed'' (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed. * ''randomized_order'' (bool): If true, use a 'globally' randomized order, i.e. all transition systems are considered in an arbitrary order. This renders all other ordering options void. == Linear merge strategies == These merge strategies implement several linear merge orders, which are described in the paper: |
* ''order_of_sccs'' ({topological, reverse_topological, decreasing, increasing}): how the SCCs should be ordered * {{{topological}}}: according to the topological ordering of the directed graph where each obtained SCC is a 'supervertex' * {{{reverse_topological}}}: according to the reverse topological ordering of the directed graph where each obtained SCC is a 'supervertex' * {{{decreasing}}}: biggest SCCs first, using 'topological' as tie-breaker * {{{increasing}}}: smallest SCCs first, using 'topological' as tie-breaker * ''merge_tree'' ([[Doc/MergeTree|MergeTree]]): the fallback merge strategy to use if a precomputed strategy should be used. * ''merge_selector'' ([[Doc/MergeSelector|MergeSelector]]): the fallback merge strategy to use if a stateless strategy should be used. * ''verbosity'' ({silent, normal, verbose, debug}): Option to specify the verbosity level. * {{{silent}}}: only the most basic output * {{{normal}}}: relevant information to monitor progress * {{{verbose}}}: full output * {{{debug}}}: like verbose with additional debug output |
| Line 33: | Line 52: |
| * Malte Helmert, Patrik Haslum and Joerg Hoffmann.<<BR>> [[http://ai.cs.unibas.ch/papers/helmert-et-al-icaps2007.pdf|Flexible Abstraction Heuristics for Optimal Sequential Planning]].<<BR>> In ''Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007)'', pp. 176-183. 2007. |
== Stateless merge strategy == |
| Line 37: | Line 54: |
| Using this command line option is deprecated, please use the equivalent call: merge_strategy=merge_precomputed(merge_tree=linear(<variable_order>)) | This merge strategy has a merge selector, which computes the next merge only depending on the current state of the factored transition system, not requiring any additional information. |
| Line 40: | Line 57: |
| merge_linear(random_seed=-1, update_option=use_random, variable_order=CG_GOAL_LEVEL) | merge_stateless(merge_selector, verbosity=normal) |
| Line 43: | Line 60: |
| * ''random_seed'' (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed. * ''update_option'' ({use_first, use_second, use_random}): When the merge tree is used within another merge strategy, howshould it be updated when a merge different to a merge from the tree is performed: choose among use_first, use_second, and use_random to choose which node of the tree should survive and represent the new merged index. Specify use_first (use_second) to let the node represententing the index that would have been merged earlier (later) survive. use_random chooses a random node. * ''variable_order'' ({CG_GOAL_LEVEL, CG_GOAL_RANDOM, GOAL_CG_LEVEL, RANDOM, LEVEL, REVERSE_LEVEL}): the order in which atomic transition systems are merged == Precomputed merge strategy == This merge strategy has a precomputed merge tree. Note that this merge strategy does not take into account the current state of the factored transition system. This also means that this merge strategy relies on the factored transition system being synchronized with this merge tree, i.e. all merges are performed exactly as given by the merge tree. |
* ''merge_selector'' ([[Doc/MergeSelector|MergeSelector]]): The merge selector to be used. * ''verbosity'' ({silent, normal, verbose, debug}): Option to specify the verbosity level. * {{{silent}}}: only the most basic output * {{{normal}}}: relevant information to monitor progress * {{{verbose}}}: full output * {{{debug}}}: like verbose with additional debug output '''Note:''' Examples include the DFP merge strategy, which can be obtained using: |
| Line 49: | Line 69: |
| merge_precomputed(merge_tree) | merge_strategy=merge_stateless(merge_selector=score_based_filtering(scoring_functions=[goal_relevance,dfp,total_order(<order_option>))])) |
| Line 51: | Line 71: |
* ''merge_tree'' (Merge Tree): The precomputed merge tree == Stateless merge strategy == This merge strategy has a merge selector, which computes the next merge only depending on the current state of the factored transition system, not requireing any additional information. |
and the (dynamic/score-based) MIASM strategy, which can be obtained using: |
| Line 57: | Line 73: |
| merge_stateless(merge_selector) | merge_strategy=merge_stateless(merge_selector=score_based_filtering(scoring_functions=[sf_miasm(<shrinking_options>),total_order(<order_option>)] |
| Line 59: | Line 75: |
* ''merge_selector'' (Merge Selector): The merge selector to be used. /* moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) */ /* cmdline: txt2tags */ |
This page describes the various merge strategies supported by the planner.
Precomputed merge strategy
This merge strategy has a precomputed merge tree. Note that this merge strategy does not take into account the current state of the factored transition system. This also means that this merge strategy relies on the factored transition system being synchronized with this merge tree, i.e. all merges are performed exactly as given by the merge tree.
merge_precomputed(merge_tree, verbosity=normal)
merge_tree (MergeTree): The precomputed merge tree.
verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
silent: only the most basic output
normal: relevant information to monitor progress
verbose: full output
debug: like verbose with additional debug output
Note: An example of a precomputed merge startegy is a linear merge strategy, which can be obtained using:
merge_strategy=merge_precomputed(merge_tree=linear(<variable_order>))
Merge strategy SSCs
This merge strategy implements the algorithm described in the paper
Silvan Sievers, Martin Wehrle and Malte Helmert.
An Analysis of Merge Strategies for Merge-and-Shrink Heuristics.
In Proceedings of the 26th International Conference on Planning and Scheduling (ICAPS 2016), pp. 2358-2366. AAAI Press, 2016.
In a nutshell, it computes the maximal SCCs of the causal graph, obtaining a partitioning of the task's variables. Every such partition is then merged individually, using the specified fallback merge strategy, considering the SCCs in a configurable order. Afterwards, all resulting composite abstractions are merged to form the final abstraction, again using the specified fallback merge strategy and the configurable order of the SCCs.
merge_sccs(order_of_sccs=topological, merge_tree=<none>, merge_selector=<none>, verbosity=normal)
order_of_sccs ({topological, reverse_topological, decreasing, increasing}): how the SCCs should be ordered
topological: according to the topological ordering of the directed graph where each obtained SCC is a 'supervertex'
reverse_topological: according to the reverse topological ordering of the directed graph where each obtained SCC is a 'supervertex'
decreasing: biggest SCCs first, using 'topological' as tie-breaker
increasing: smallest SCCs first, using 'topological' as tie-breaker
merge_tree (MergeTree): the fallback merge strategy to use if a precomputed strategy should be used.
merge_selector (MergeSelector): the fallback merge strategy to use if a stateless strategy should be used.
verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
silent: only the most basic output
normal: relevant information to monitor progress
verbose: full output
debug: like verbose with additional debug output
Stateless merge strategy
This merge strategy has a merge selector, which computes the next merge only depending on the current state of the factored transition system, not requiring any additional information.
merge_stateless(merge_selector, verbosity=normal)
merge_selector (MergeSelector): The merge selector to be used.
verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
silent: only the most basic output
normal: relevant information to monitor progress
verbose: full output
debug: like verbose with additional debug output
Note: Examples include the DFP merge strategy, which can be obtained using:
merge_strategy=merge_stateless(merge_selector=score_based_filtering(scoring_functions=[goal_relevance,dfp,total_order(<order_option>))]))
and the (dynamic/score-based) MIASM strategy, which can be obtained using:
merge_strategy=merge_stateless(merge_selector=score_based_filtering(scoring_functions=[sf_miasm(<shrinking_options>),total_order(<order_option>)]