Differences between revisions 12 and 13
Revision 12 as of 2022-02-11 11:05:57
Size: 4806
Editor: XmlRpcBot
Comment:
Revision 13 as of 2022-02-12 09:20:53
Size: 5106
Editor: XmlRpcBot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 30: Line 30:
 * ''pruning'' ([[Doc/PruningMethod|PruningMethod]]):  * ''pruning'' ([[Doc/PruningMethod|PruningMethod]]): the underlying pruning method to be applied
Line 33: Line 33:
'''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.

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

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

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

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

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

FastDownward: Doc/PruningMethod (last edited 2022-02-12 09:20:53 by XmlRpcBot)