This page describes the available merge trees that can be used to precompute a merge strategy, either for the entire task or a given subset of transition systems of a given factored transition system. Merge trees are typically used in the merge strategy of type 'precomputed', but they can also be used as fallback merge strategies in 'combined' merge strategies.

## Linear merge trees

These merge trees implement several linear merge orders, which are described in the paper:

linear(random_seed=-1, update_option=use_random, variable_order=cg_goal_level)
• 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.

• update_option ({use_first, use_second, use_random}): When the merge tree is used within another merge strategy, how should it be updated when a merge different to a merge from the tree is performed.

• use_first: the node representing the index that would have been merged earlier survives

• use_second: the node representing the index that would have been merged later survives

• use_random: a random node (of the above two) survives

• variable_order ({cg_goal_level, cg_goal_random, goal_cg_level, random, level, reverse_level}): the order in which atomic transition systems are merged

• cg_goal_level: variables are prioritized first if they have an arc to a previously added variable, second if their goal value is defined and third according to their level in the causal graph

• cg_goal_random: variables are prioritized first if they have an arc to a previously added variable, second if their goal value is defined and third randomly

• goal_cg_level: variables are prioritized first if their goal value is defined, second if they have an arc to a previously added variable, and third according to their level in the causal graph

• random: variables are ordered randomly

• level: variables are ordered according to their level in the causal graph

• reverse_level: variables are ordered reverse to their level in the causal graph

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