|
Size: 393
Comment:
|
Size: 2705
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | Line 3: |
| == merge_dfp == | 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. |
| Line 6: | Line 10: |
| merge_dfp() | merge_precomputed(merge_tree) |
| Line 9: | Line 13: |
| == merge_linear == | * ''merge_tree'' ([[Doc/MergeTree|MergeTree]]): The precomputed merge tree == Merge strategy SSCs == This merge strategy implements the algorithm described in the paper * Silvan Sievers, Martin Wehrle and Malte Helmert.<<BR>> [[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. 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 12: | Line 24: |
| merge_linear(variable_order=CG_GOAL_LEVEL) | merge_sccs(order_of_sccs=topological, merge_tree=<none>, merge_selector=<none>) |
| Line 15: | Line 27: |
| * ''variable_order'' ({CG_GOAL_LEVEL, CG_GOAL_RANDOM, GOAL_CG_LEVEL, RANDOM, LEVEL, REVERSE_LEVEL}): the order in which atomic abstractions are merged | * ''order_of_sccs'' ({topological, reverse_topological, decreasing, increasing}): choose an ordering of the SCCs: topological/reverse_topological or decreasing/increasing in the size of the SCCs. The former two options refer to the directed graph where each obtained SCC is a 'supervertex'. For the latter two options, the tie-breaking is to use the topological order according to that same graph of SCC supervertices. * ''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. == 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) }}} |
| Line 17: | Line 36: |
| /* moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) */ | * ''merge_selector'' ([[Doc/MergeSelector|MergeSelector]]): The merge selector to be used. /* moin code generated by txt2tags 2.6 (http://txt2tags.org) */ |
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)
merge_tree (MergeTree): The precomputed merge tree
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>)
order_of_sccs ({topological, reverse_topological, decreasing, increasing}): choose an ordering of the SCCs: topological/reverse_topological or decreasing/increasing in the size of the SCCs. The former two options refer to the directed graph where each obtained SCC is a 'supervertex'. For the latter two options, the tie-breaking is to use the topological order according to that same graph of SCC supervertices.
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.
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)
merge_selector (MergeSelector): The merge selector to be used.