Differences between revisions 3 and 15 (spanning 12 versions)
 ⇤ ← Revision 3 as of 2015-07-18 02:55:46 → Size: 2025 Editor: XmlRpcBot Comment: ← Revision 15 as of 2019-03-08 12:08:33 → ⇥ Size: 4272 Editor: XmlRpcBot Comment: Deletions are marked like this. Additions are marked like this. Line 8: Line 8: alt(sublists=, boost=0) alt(sublists, boost=0) Line 13: Line 13: == 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. Line 16: Line 31: pareto(evals=, pref_only=false, state_uniform_selection=false) pareto(evals, pref_only=false, state_uniform_selection=false, random_seed=-1) Line 20: Line 35: * ''evals'' (list of [[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluators * ''evals'' (list of [[Doc/Evaluator|Evaluator]]): evaluators Line 23: Line 38: == Standard open list ==Standard open list that uses a single evaluator * ''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. Line 26: Line 42: single(eval=, pref_only=false) single(eval, pref_only=false) Line 30: Line 46: * ''eval'' ([[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluator * ''eval'' ([[Doc/Evaluator|Evaluator]]): evaluator Line 32: Line 48: == Bucket-based open list ==Bucket-based open list implementation that uses a single evaluator. Ties are broken in FIFO order. '''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 == Line 35: Line 52: single_buckets(eval=, pref_only=false) tiebreaking(evals, pref_only=false, unsafe_pruning=true) Line 39: Line 56: * ''eval'' ([[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluator * ''evals'' (list of [[Doc/Evaluator|Evaluator]]): evaluators Line 41: Line 58: == Tie-breaking open list == * ''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. Line 43: Line 67: tiebreaking(evals=, pref_only=false, unsafe_pruning=true) type_based(evaluators, random_seed=-1) Line 46: Line 70: * ''evals'' (list of [[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar 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 * ''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.

## 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

`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

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

FastDownward: Doc/OpenList (last edited 2019-03-08 12:08:33 by XmlRpcBot)