|
Size: 2717
Comment:
|
← Revision 21 as of 2024-01-11 22:26:38 ⇥
Size: 4193
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 11: | Line 11: |
| * ''sublists'' (list of [[Doc/OpenList|OpenList]]): sub open lists * ''boost'' (int): boost value for sub-open-lists that are restricted to preferred operator nodes '''Preferred operators:''' Preferred operators are only taken from sub-open-lists that do not consider the evaluated state a dead end. |
* ''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 |
| Line 15: | Line 14: |
| '''Dead ends:''' A state is considered a dead end if either all alternated open lists agree that it is a dead end or at least one reliable open list considers it a dead end. A state is never inserted into a sub-open-list that considers it a dead end. | == Epsilon-greedy open list == |
| Line 17: | Line 16: |
| '''Note:''' The treatment of dead ends is different from the one described in the [[http://tr.informatik.uni-freiburg.de/reports/report258/report00258.ps.gz|technical report]] "The More, the Merrier: Combining [[Doc/Heuristic|Heuristic]] Estimators for Satisficing Planning (Extended Version)" (Department of Computer Science at Freiburg University, No. 258, 2010) | 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.<<BR>> [[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7943/8066|A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration]].<<BR>> 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. |
| Line 20: | Line 32: |
| Line 21: | Line 34: |
| Line 22: | Line 36: |
| pareto(evals, pref_only=false, state_uniform_selection=false) | pareto(evals, pref_only=false, state_uniform_selection=false, random_seed=-1) |
| Line 25: | Line 39: |
| * ''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. |
|
| Line 26: | Line 44: |
| * ''evals'' (list of [[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar 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. == Standard open list == Standard open list that uses a single evaluator |
== Best-first open list == Open list that uses a single evaluator and FIFO tiebreaking. |
| Line 35: | Line 52: |
| * ''eval'' ([[Doc/Evaluator|Evaluator]]): evaluator * ''pref_only'' (bool): insert only nodes generated by preferred operators |
|
| Line 36: | Line 55: |
| * ''eval'' ([[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluator * ''pref_only'' (bool): insert only nodes generated by preferred operators == Bucket-based open list == Bucket-based open list implementation that uses a single evaluator {{{ single_buckets(eval, pref_only=false) }}} |
'''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. |
| Line 44: | Line 57: |
| == Tie-breaking open list == | |
| Line 45: | Line 59: |
| * ''eval'' ([[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluator * ''pref_only'' (bool): insert only nodes generated by preferred operators == Tie-breaking open list == |
|
| Line 52: | Line 63: |
* ''evals'' (list of [[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluators |
* ''evals'' (list of [[Doc/Evaluator|Evaluator]]): evaluators |
| Line 57: | Line 67: |
| /* moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) */ /* cmdline: txt2tags */ |
== 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.<<BR>> [[http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8472/8705|Type-Based Exploration with Multiple Search Queues for Satisficing Planning]].<<BR>> 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. |
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
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.