Differences between revisions 22 and 23
Revision 22 as of 2019-11-22 20:01:09
Size: 4012
Editor: XmlRpcBot
Comment:
Revision 23 as of 2019-11-22 22:30:43
Size: 4016
Editor: XmlRpcBot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 10: Line 10:
 [https://ai.dmi.unibas.ch/papers/nissim-et-al-ijcai2011.pdf Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.].<<BR>>  [[https://ai.dmi.unibas.ch/papers/nissim-et-al-ijcai2011.pdf|Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.]].<<BR>>
Line 27: Line 27:
 [https://ai.dmi.unibas.ch/papers/helmert-et-al-icaps2007.pdf Flexible Abstraction Heuristics for Optimal Sequential Planning].<<BR>>  [[https://ai.dmi.unibas.ch/papers/helmert-et-al-icaps2007.pdf|Flexible Abstraction Heuristics for Optimal Sequential Planning]].<<BR>>

This page describes the various shrink strategies supported by the planner.

Bismulation based shrink strategy

This shrink strategy implements the algorithm described in the paper:

shrink_bisimulation(greedy=false, at_limit=RETURN)
  • greedy (bool): use greedy bisimulation

  • at_limit ({RETURN, USE_UP}): what to do when the size limit is hit

shrink_bisimulation(greedy=true): Combine this with the merge-and-shrink options max_states=infinity and threshold_before_merge=1 and with the linear merge strategy reverse_level to obtain the variant 'greedy bisimulation without size limit', called M&S-gop in the IJCAI 2011 paper. When we last ran experiments on interaction of shrink strategies with label reduction, this strategy performed best when used with label reduction before shrinking (and no label reduction before merging).

shrink_bisimulation(greedy=false): Combine this with the merge-and-shrink option max_states=N (where N is a numerical parameter for which sensible values include 1000, 10000, 50000, 100000 and 200000) and with the linear merge strategy reverse_level to obtain the variant 'exact bisimulation with a size limit', called DFP-bop in the IJCAI 2011 paper. When we last ran experiments on interaction of shrink strategies with label reduction, this strategy performed best when used with label reduction before shrinking (and no label reduction before merging).

f-preserving shrink strategy

This shrink strategy implements the algorithm described in the paper:

shrink_fh(random_seed=-1, shrink_f=HIGH, shrink_h=LOW)
  • 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.

  • shrink_f ({HIGH, LOW}): prefer shrinking states with high or low f values

  • shrink_h ({HIGH, LOW}): prefer shrinking states with high or low h values

shrink_fh(): Combine this with the merge-and-shrink option max_states=N (where N is a numerical parameter for which sensible values include 1000, 10000, 50000, 100000 and 200000) and the linear merge startegy cg_goal_level to obtain the variant 'f-preserving shrinking of transition systems', called called HHH in the IJCAI 2011 paper, see bisimulation based shrink strategy. When we last ran experiments on interaction of shrink strategies with label reduction, this strategy performed best when used with label reduction before merging (and no label reduction before shrinking). We also recommend using full pruning with this shrink strategy, because both distances from the initial state and to the goal states must be computed anyway, and because the existence of only one dead state causes this shrink strategy to always use the map-based approach for partitioning states rather than the more efficient vector-based approach.

Random

shrink_random(random_seed=-1)
  • 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.

FastDownward: Doc/ShrinkStrategy (last edited 2024-01-11 22:26:38 by XmlRpcBot)