Bismulation based shrink strategy

This shrink strategy implements the algorithm described in the paper:

• Raz Nissim, Joerg Hoffmann and Malte Helmert.
  Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning..
  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1983-1990. 2011.

shrink_bisimulation(max_states=-1, max_states_before_merge=-1, threshold=-1, greedy=false, at_limit=RETURN)

• max_states (int): maximum transition system size allowed at any time point.

• max_states_before_merge (int): maximum transition system size allowed for two transition systems before being merged to form the synchronized product.

• threshold (int): If a transition system, before being merged, surpasses this soft transition system size limit, the shrink strategy is called to possibly shrink the transition system.

• greedy (bool): use greedy bisimulation

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

shrink_bisimulation(max_states=infinity, threshold=1, greedy=true): Greedy bisimulation without size bound (called M&S-gop in the IJCAI 2011 paper).Combine this with the linear merge strategy REVERSE_LEVEL to match the heuristic in the paper. This strategy performs best when used with label reduction before shrinking (and no label reduction before merging).

shrink_bisimulation(max_states=N, greedy=false): Exact bisimulation with a size limit (called DFP-bop in the IJCAI 2011 paper), where N is a numerical parameter for which sensible values include 1000, 10000, 50000, 100000 and 200000. Combine this with the linear merge strategy REVERSE_LEVEL to match the heuristic in the paper. This strategy performs 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:

• Malte Helmert, Patrik Haslum and Joerg Hoffmann..
  Flexible Abstraction Heuristics for Optimal Sequential Planning..
  In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), pp. 176-183. 2007.

shrink_fh(max_states=-1, max_states_before_merge=-1, threshold=-1, shrink_f=HIGH, shrink_h=LOW)

• max_states (int): maximum transition system size allowed at any time point.

• max_states_before_merge (int): maximum transition system size allowed for two transition systems before being merged to form the synchronized product.

• threshold (int): If a transition system, before being merged, surpasses this soft transition system size limit, the shrink strategy is called to possibly shrink the transition system.

• 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(max_states=N): f-preserving shrinking of transition systems (called HHH in the IJCAI 2011 paper, see shrink_bisimulation).Here, N is a numerical parameter for which sensible values include 1000, 10000, 50000, 100000 and 200000. Combine this with the linear merge strategy CG_GOAL_LEVEL to match the heuristic in the paper. This strategy performs best when used with label reduction before merging (and no label reduction before shrinking).

Random

shrink_random(max_states=-1, max_states_before_merge=-1, threshold=-1)

• max_states (int): maximum transition system size allowed at any time point.

• max_states_before_merge (int): maximum transition system size allowed for two transition systems before being merged to form the synchronized product.

• threshold (int): If a transition system, before being merged, surpasses this soft transition system size limit, the shrink strategy is called to possibly shrink the transition system.

moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) cmdline: txt2tags