3984
Comment:

4270

Deletions are marked like this.  Additions are marked like this. 
Line 24:  Line 24: 
* ''eval'' ([[Doc/ScalarEvaluatorScalarEvaluator]]): scalar evaluator  * ''eval'' ([[Doc/EvaluatorEvaluator]]): evaluator 
Line 35:  Line 35: 
* ''evals'' (list of [[Doc/ScalarEvaluatorScalarEvaluator]]): scalar evaluators  * ''evals'' (list of [[Doc/EvaluatorEvaluator]]): evaluators 
Line 39:  Line 39: 
== Standard open list == Standard open list that uses a single evaluator 
== Bestfirst open list == Open list that uses a single evaluator and FIFO tiebreaking. 
Line 46:  Line 46: 
* ''eval'' ([[Doc/ScalarEvaluatorScalarEvaluator]]): scalar evaluator  * ''eval'' ([[Doc/EvaluatorEvaluator]]): evaluator 
Line 48:  Line 48: 
'''Implementation Notes:''' Elements with the same evaluator value are stored in doubleended 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. 

Line 54:  Line 56: 
* ''evals'' (list of [[Doc/ScalarEvaluatorScalarEvaluator]]): scalar evaluators  * ''evals'' (list of [[Doc/EvaluatorEvaluator]]): evaluators 
Line 68:  Line 70: 
* ''evaluators'' (list of [[Doc/ScalarEvaluatorScalarEvaluator]]): Evaluators used to determine the bucket for each entry.  * ''evaluators'' (list of [[Doc/EvaluatorEvaluator]]): Evaluators used to determine the bucket for each entry. 
Contents
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
Epsilongreedy 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 KnowledgeBased GBFS Enhancements and KnowledgeFree Exploration.
In Proceedings of the TwentyFourth International Conference on Automated Planning and Scheduling (ICAPS 2014), pp. 375379. 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 Paretooptimal (regarding the subevaluators) 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 nondominated bucket and return its oldest entry. If this option is false, we select uniformly from the nondominated 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.
Bestfirst 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 doubleended 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.
Tiebreaking 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
Typebased 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.
TypeBased Exploration with Multiple Search Queues for Satisficing Planning.
In Proceedings of the TwentyEigth AAAI Conference Conference on Artificial Intelligence (AAAI 2014), pp. 23952401. 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.