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.