>
== Alternation open list ==
alternates between several open lists.
{{{
alt(sublists, boost=0)
}}}
* ''sublists'' (list of [[Doc/OpenList|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.<
>
[[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7943/8066|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'' ([[Doc/Evaluator|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 [[Doc/Evaluator|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'' ([[Doc/Evaluator|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 [[Doc/Evaluator|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.<
>
[[http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8472/8705|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 [[Doc/Evaluator|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.