Prune or reorder applicable operators.

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

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

stubborn_sets_ec(min_required_pruning_ratio=0.0, expansions_before_checking_pruning_ratio=1000)

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

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. The variant 'StubbornSetsSimple' resolves the design choices in a straight-forward way. For details, see the following papers:

stubborn_sets_simple(min_required_pruning_ratio=0.0, expansions_before_checking_pruning_ratio=1000)

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

FastDownward: Doc/PruningMethod (last edited 2018-04-15 08:02:28 by XmlRpcBot)