This page describes various merge scoring functions. A scoring function, given a list of merge candidates and a factored transition system, computes a score for each candidate based on this information and potentially some chosen options. Minimal scores are considered best. Scoring functions are currently only used within the score based filtering merge selector.
DFP scoring
This scoring function computes the 'DFP' score as descrdibed in the paper "Directed model checking with distance-preserving abstractions" by Draeger, Finkbeiner and Podelski (SPIN 2006), adapted to planning in the following paper:
Silvan Sievers, Martin Wehrle and Malte Helmert.
Generalized Label Reduction for Merge-and-Shrink Heuristics.
In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), pp. 2358-2366. AAAI Press 2014.
dfp()
Goal relevance scoring
This scoring function assigns a merge candidate a value of 0 iff at least one of the two transition systems of the merge candidate is goal relevant in the sense that there is an abstract non-goal state.All other candidates get a score of positive infinity.
goal_relevance()
Single random
This scoring function assigns exactly one merge candidate a score of 0, chosen randomly, and infinity to all others.
single_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.
Total order
This scoring function computes a total order on the merge candidates, based on the specified options. The score for each merge candidate correponds to its position in the order. This scoring function is mainly intended as tie-breaking, and has been introduced in the following paper:
Silvan Sievers, Martin Wehrle and Malte Helmert.
An Analysis of Merge Strategies for Merge-and-Shrink Heuristics.
In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), pp. 294-298. AAAI Press 2016.
Furthermore, using the atomic_ts_order option, this scoring function, if used alone in a score based filtering merge selector, can be used to emulate the corresponding (precomputed) linear merge strategies reverse level/level (independently of the other options).
total_order(atomic_ts_order=reverse_level, product_ts_order=new_to_old, atomic_before_product=false, random_seed=-1)
atomic_ts_order ({reverse_level, level, random}): The order in which atomic transition systems are considered when considering pairs of potential merges.
reverse_level: the variable order of Fast Downward
level: opposite of reverse_level
random: a randomized order
product_ts_order ({old_to_new, new_to_old, random}): The order in which product transition systems are considered when considering pairs of potential merges.
old_to_new: consider composite transition systems from most recent to oldest, that is in decreasing index order
new_to_old: opposite of old_to_new
random: a randomized order
atomic_before_product (bool): Consider atomic transition systems before composite ones iff true.
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.