Alternation open list

alternates between several open lists.

alt(sublists, boost=0)

• sublists (list of OpenList): open lists between which this one alternates

• boost (int): boost value for contained open lists that are restricted to preferred successors

Epsilon-greedy open list

Chooses an entry uniformly randomly with probability 'epsilon', otherwise it returns the minimum entry. The algorithm is based on

Richard Valenzano, Nathan R. Sturtevant, Jonathan Schaeffer and Fan Xie.
A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration.
In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014), pp. 375-379. AAAI Press, 2014.

epsilon_greedy(eval, pref_only=false, epsilon=0.2, random_seed=-1)

• eval (Evaluator): evaluator

• pref_only (bool): insert only nodes generated by preferred operators

• epsilon (double [0.0, 1.0]): probability for choosing the next entry randomly

• 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.

Pareto open list

Selects one of the Pareto-optimal (regarding the sub-evaluators) entries for removal.

pareto(evals, pref_only=false, state_uniform_selection=false, random_seed=-1)

• evals (list of Evaluator): evaluators

• pref_only (bool): insert only nodes generated by preferred operators

• state_uniform_selection (bool): When removing an entry, we select a non-dominated bucket and return its oldest entry. If this option is false, we select uniformly from the non-dominated buckets; if the option is true, we weight the buckets with the number of entries.

• 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.

Best-first open list

Open list that uses a single evaluator and FIFO tiebreaking.

single(eval, pref_only=false)

• eval (Evaluator): evaluator

• pref_only (bool): insert only nodes generated by preferred operators

Implementation Notes: Elements with the same evaluator value are stored in double-ended queues, called "buckets". The open list stores a map from evaluator values to buckets. Pushing and popping from a bucket runs in constant time. Therefore, inserting and removing an entry from the open list takes time O(log(n)), where n is the number of buckets.

Tie-breaking open list

tiebreaking(evals, pref_only=false, unsafe_pruning=true)

• evals (list of Evaluator): evaluators

• pref_only (bool): insert only nodes generated by preferred operators

• unsafe_pruning (bool): allow unsafe pruning when the main evaluator regards a state a dead end

Type-based open list

Uses multiple evaluators to assign entries to buckets. All entries in a bucket have the same evaluator values. When retrieving an entry, a bucket is chosen uniformly at random and one of the contained entries is selected uniformly randomly. The algorithm is based on

Fan Xie, Martin Mueller, Robert Holte and Tatsuya Imai.
Type-Based Exploration with Multiple Search Queues for Satisficing Planning.
In Proceedings of the Twenty-Eigth AAAI Conference Conference on Artificial Intelligence (AAAI 2014), pp. 2395-2401. AAAI Press, 2014.

type_based(evaluators, random_seed=-1)

• evaluators (list of Evaluator): Evaluators used to determine the bucket for each entry.

• 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.

moin code generated by txt2tags 2.6 (http://txt2tags.org) cmdline: txt2tags