|
Size: 8524
Comment:
|
← Revision 21 as of 2024-01-11 22:26:38 ⇥
Size: 8346
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 14: | Line 14: |
| atom_centric_stubborn_sets(use_sibling_shortcut=true, atom_selection_strategy=quick_skip, min_required_pruning_ratio=0.0, expansions_before_checking_pruning_ratio=1000) | atom_centric_stubborn_sets(use_sibling_shortcut=true, atom_selection_strategy=quick_skip, verbosity=normal) |
| Line 19: | Line 19: |
| * {{{fast_downward}}}: select the atom (v, d) with the variable v that comes first in the Fast Downward variable ordering (which is based on the causal graph) * {{{quick_skip}}}: if possible, select an unsatisfied atom whose producers are already marked * {{{static_small}}}: select the atom achieved by the fewest number of actions * {{{dynamic_small}}}: select the atom achieved by the fewest number of actions that are not yet part of the stubborn set |
* {{{fast_downward}}}: select the atom (v, d) with the variable v that comes first in the Fast Downward variable ordering (which is based on the causal graph) * {{{quick_skip}}}: if possible, select an unsatisfied atom whose producers are already marked * {{{static_small}}}: select the atom achieved by the fewest number of actions * {{{dynamic_small}}}: select the atom achieved by the fewest number of actions that are not yet part of the stubborn set * ''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 on verbosity parameter:''' Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (`null`). We recommend using at most normal verbosity for running experiments. == Limited pruning == Limited pruning applies another pruning method and switches it off after a fixed number of expansions if the pruning ratio is below a given value. The pruning ratio is the sum of all pruned operators divided by the sum of all operators before pruning, considering all previous expansions. {{{ limited_pruning(pruning, min_required_pruning_ratio=0.2, expansions_before_checking_pruning_ratio=1000, verbosity=normal) }}} * ''pruning'' ([[Doc/PruningMethod|PruningMethod]]): the underlying pruning method to be applied |
| Line 25: | Line 42: |
| '''Automatically disable pruning:''' Using stubborn sets to prune operators often reduces the required number of expansions but computing the prunable operators has a non-negligible runtime overhead. Whether the decrease in expansions outweighs the increased computational costs depends on the task at hand. Using the options 'min_required_pruning_ratio' (M) and 'expansions_before_checking_pruning_ratio' (E) it is possible to automatically disable pruning after E expansions if the ratio of pruned vs. non-pruned operators is lower than M. In detail, let B and A be the total number of operators before and after pruning summed over all previous expansions. We call 1-(A/B) the pruning ratio R. If R is lower than M after E expansions, we disable pruning for all subsequent expansions, i.e., consider all applicable operators when generating successor states. By default, pruning is never disabled (min_required_pruning_ratio = 0.0). In experiments on IPC benchmarks, stronger results have been observed with automatic disabling (min_required_pruning_ratio = 0.2, expansions_before_checking_pruning_ratio=1000). | * ''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 on verbosity parameter:''' Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (`null`). We recommend using at most normal verbosity for running experiments. '''Example:''' To use atom centric stubborn sets and limit them, use {{{ pruning=limited_pruning(pruning=atom_centric_stubborn_sets(),min_required_pruning_ratio=0.2,expansions_before_checking_pruning_ratio=1000) }}} in an eager search such as astar. |
| Line 28: | Line 57: |
| Line 29: | Line 59: |
| Line 30: | Line 61: |
| null() | null(verbosity=normal) |
| Line 33: | Line 64: |
| * ''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 on verbosity parameter:''' Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (`null`). We recommend using at most normal verbosity for running experiments. |
|
| Line 43: | Line 81: |
| stubborn_sets_ec(min_required_pruning_ratio=0.0, expansions_before_checking_pruning_ratio=1000) | stubborn_sets_ec(verbosity=normal) |
| Line 46: | Line 84: |
| * ''min_required_pruning_ratio'' (double [0.0, 1.0]): disable pruning if the pruning ratio is lower than this value after 'expansions_before_checking_pruning_ratio' expansions * ''expansions_before_checking_pruning_ratio'' (int [0, infinity]): number of expansions before deciding whether to disable pruning '''Automatically disable pruning:''' Using stubborn sets to prune operators often reduces the required number of expansions but computing the prunable operators has a non-negligible runtime overhead. Whether the decrease in expansions outweighs the increased computational costs depends on the task at hand. Using the options 'min_required_pruning_ratio' (M) and 'expansions_before_checking_pruning_ratio' (E) it is possible to automatically disable pruning after E expansions if the ratio of pruned vs. non-pruned operators is lower than M. In detail, let B and A be the total number of operators before and after pruning summed over all previous expansions. We call 1-(A/B) the pruning ratio R. If R is lower than M after E expansions, we disable pruning for all subsequent expansions, i.e., consider all applicable operators when generating successor states. By default, pruning is never disabled (min_required_pruning_ratio = 0.0). In experiments on IPC benchmarks, stronger results have been observed with automatic disabling (min_required_pruning_ratio = 0.2, expansions_before_checking_pruning_ratio=1000). |
* ''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 on verbosity parameter:''' Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (`null`). We recommend using at most normal verbosity for running experiments. |
| Line 51: | Line 93: |
| Stubborn sets represent a state pruning method which computes a subset of applicable operators in each state such that completeness and optimality of the overall search is preserved. As stubborn sets rely on several design choices, there are different variants thereof. The variant 'StubbornSetsSimple' resolves the design choices in a straight-forward way. For details, see the following papers: | Stubborn sets represent a state pruning method which computes a subset of applicable operators in each state such that completeness and optimality of the overall search is preserved. As stubborn sets rely on several design choices, there are different variants thereof. This stubborn set variant resolves the design choices in a straight-forward way. For details, see the following papers: |
| Line 62: | Line 105: |
| stubborn_sets_simple(min_required_pruning_ratio=0.0, expansions_before_checking_pruning_ratio=1000) | stubborn_sets_simple(verbosity=normal) |
| Line 65: | Line 108: |
| * ''min_required_pruning_ratio'' (double [0.0, 1.0]): disable pruning if the pruning ratio is lower than this value after 'expansions_before_checking_pruning_ratio' expansions * ''expansions_before_checking_pruning_ratio'' (int [0, infinity]): number of expansions before deciding whether to disable pruning '''Automatically disable pruning:''' Using stubborn sets to prune operators often reduces the required number of expansions but computing the prunable operators has a non-negligible runtime overhead. Whether the decrease in expansions outweighs the increased computational costs depends on the task at hand. Using the options 'min_required_pruning_ratio' (M) and 'expansions_before_checking_pruning_ratio' (E) it is possible to automatically disable pruning after E expansions if the ratio of pruned vs. non-pruned operators is lower than M. In detail, let B and A be the total number of operators before and after pruning summed over all previous expansions. We call 1-(A/B) the pruning ratio R. If R is lower than M after E expansions, we disable pruning for all subsequent expansions, i.e., consider all applicable operators when generating successor states. By default, pruning is never disabled (min_required_pruning_ratio = 0.0). In experiments on IPC benchmarks, stronger results have been observed with automatic disabling (min_required_pruning_ratio = 0.2, expansions_before_checking_pruning_ratio=1000). |
* ''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 69: | Line 114: |
| /* moin code generated by txt2tags 2.6 (http://txt2tags.org) */ /* cmdline: txt2tags */ |
'''Note on verbosity parameter:''' Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (`null`). We recommend using at most normal verbosity for running experiments. |
Prune or reorder applicable operators.
Atom-centric stubborn sets
Stubborn sets are a state pruning method which computes a subset of applicable actions in each state such that completeness and optimality of the overall search is preserved. Previous stubborn set implementations mainly track information about actions. In contrast, this implementation focuses on atomic propositions (atoms), which often speeds up the computation on IPC benchmarks. For details, see
Gabriele Roeger, Malte Helmert, Jendrik Seipp and Silvan Sievers.
An Atom-Centric Perspective on Stubborn Sets.
In Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), pp. 57-65. AAAI Press, 2020.
atom_centric_stubborn_sets(use_sibling_shortcut=true, atom_selection_strategy=quick_skip, verbosity=normal)
use_sibling_shortcut (bool): use variable-based marking in addition to atom-based marking
atom_selection_strategy ({fast_downward, quick_skip, static_small, dynamic_small}): Strategy for selecting unsatisfied atoms from action preconditions or the goal atoms. All strategies use the fast_downward strategy for breaking ties.
fast_downward: select the atom (v, d) with the variable v that comes first in the Fast Downward variable ordering (which is based on the causal graph)
quick_skip: if possible, select an unsatisfied atom whose producers are already marked
static_small: select the atom achieved by the fewest number of actions
dynamic_small: select the atom achieved by the fewest number of actions that are not yet part of the stubborn set
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 on verbosity parameter: Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (null). We recommend using at most normal verbosity for running experiments.
Limited pruning
Limited pruning applies another pruning method and switches it off after a fixed number of expansions if the pruning ratio is below a given value. The pruning ratio is the sum of all pruned operators divided by the sum of all operators before pruning, considering all previous expansions.
limited_pruning(pruning, min_required_pruning_ratio=0.2, expansions_before_checking_pruning_ratio=1000, verbosity=normal)
pruning (PruningMethod): the underlying pruning method to be applied
min_required_pruning_ratio (double [0.0, 1.0]): disable pruning if the pruning ratio is lower than this value after 'expansions_before_checking_pruning_ratio' expansions
expansions_before_checking_pruning_ratio (int [0, infinity]): number of expansions before deciding whether to disable pruning
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 on verbosity parameter: Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (null). We recommend using at most normal verbosity for running experiments.
Example: To use atom centric stubborn sets and limit them, use
pruning=limited_pruning(pruning=atom_centric_stubborn_sets(),min_required_pruning_ratio=0.2,expansions_before_checking_pruning_ratio=1000)
in an eager search such as astar.
No pruning
This is a skeleton method that does not perform any pruning, i.e., all applicable operators are applied in all expanded states.
null(verbosity=normal)
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 on verbosity parameter: Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (null). We recommend using at most normal verbosity for running experiments.
StubbornSetsEC
Stubborn sets represent a state pruning method which computes a subset of applicable operators in each state such that completeness and optimality of the overall search is preserved. As stubborn sets rely on several design choices, there are different variants thereof. The variant 'StubbornSetsEC' resolves the design choices such that the resulting pruning method is guaranteed to strictly dominate the Expansion Core pruning method. For details, see
Martin Wehrle, Malte Helmert, Yusra Alkhazraji and Robert Mattmueller.
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core.
In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), pp. 251-259. AAAI Press, 2013.
stubborn_sets_ec(verbosity=normal)
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 on verbosity parameter: Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (null). We recommend using at most normal verbosity for running experiments.
Stubborn sets simple
Stubborn sets represent a state pruning method which computes a subset of applicable operators in each state such that completeness and optimality of the overall search is preserved. As stubborn sets rely on several design choices, there are different variants thereof. This stubborn set variant resolves the design choices in a straight-forward way. For details, see the following papers:
Yusra Alkhazraji, Martin Wehrle, Robert Mattmueller and Malte Helmert.
A Stubborn Set Algorithm for Optimal Planning.
In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), pp. 891-892. IOS Press, 2012.Martin Wehrle and Malte Helmert.
Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies.
In Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014), pp. 323-331. AAAI Press, 2014.
stubborn_sets_simple(verbosity=normal)
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 on verbosity parameter: Setting verbosity to verbose or higher enables time measurements in each call to prune_operators for a given state. This induces a significant overhead, up to 30% in configurations like blind search with the no pruning method (null). We recommend using at most normal verbosity for running experiments.