5026
Comment:
|
5240
|
Deletions are marked like this. | Additions are marked like this. |
Line 16: | Line 16: |
[[Automated Creation of Pattern Database Search Heuristics|http://www.springerlink.com/content/20613345434608x1/]].<<BR>> In ''In Proceedings of the 4th Workshop on Model Checking and Artificial Intelligence (!MoChArt 2006)'', pp. 35-50. 2007. |
[[http://www.springerlink.com/content/20613345434608x1/|Automated Creation of Pattern Database Search Heuristics]].<<BR>> In ''Proceedings of the 4th Workshop on Model Checking and Artificial Intelligence (!MoChArt 2006)'', pp. 35-50. 2007. |
Line 47: | Line 47: |
hillclimbing(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity) | hillclimbing(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity, random_seed=-1) |
Line 56: | Line 56: |
* ''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 60: | Line 61: |
[[Getting the Most Out of Pattern Databases for Classical Planning|http://ijcai.org/papers13/Papers/IJCAI13-347.pdf]].<<BR>> | [[http://ai.cs.unibas.ch/papers/pommerening-et-al-ijcai2013.pdf|Getting the Most Out of Pattern Databases for Classical Planning]].<<BR>> |
Contents
Factory for pattern collections
combo
combo(max_states=1000000)
max_states (int [1, infinity]): maximum abstraction size for combo strategy
Genetic Algorithm Patterns
The following paper describes the automated creation of pattern databases with a genetic algorithm. Pattern collections are initially created with a bin-packing algorithm. The genetic algorithm is used to optimize the pattern collections with an objective function that estimates the mean heuristic value of the the pattern collections. Pattern collections with higher mean heuristic estimates are more likely selected for the next generation.
Stefan Edelkamp.
Automated Creation of Pattern Database Search Heuristics.
In Proceedings of the 4th Workshop on Model Checking and Artificial Intelligence (MoChArt 2006), pp. 35-50. 2007.
genetic(pdb_max_size=50000, num_collections=5, num_episodes=30, mutation_probability=0.01, disjoint=false)
pdb_max_size (int [1, infinity]): maximal number of states per pattern database
num_collections (int [1, infinity]): number of pattern collections to maintain in the genetic algorithm (population size)
num_episodes (int [0, infinity]): number of episodes for the genetic algorithm
mutation_probability (double [0.0, 1.0]): probability for flipping a bit in the genetic algorithm
disjoint (bool): consider a pattern collection invalid (giving it very low fitness) if its patterns are not disjoint
Note: This pattern generation method uses the zero/one pattern database heuristic.
Implementation Notes
The standard genetic algorithm procedure as described in the paper is implemented in Fast Downward. The implementation is close to the paper.
Initialization
In Fast Downward bin-packing with the next-fit strategy is used. A bin corresponds to a pattern which contains variables up to pdb_max_size. With this method each variable occurs exactly in one pattern of a collection. There are num_collections collections created.Mutation
With probability mutation_probability a bit is flipped meaning that either a variable is added to a pattern or deleted from a pattern.Recombination
Recombination isn't implemented in Fast Downward. In the paper recombination is described but not used.Evaluation
For each pattern collection the mean heuristic value is computed. For a single pattern database the mean heuristic value is the sum of all pattern database entries divided through the number of entries. Entries with infinite heuristic values are ignored in this calculation. The sum of these individual mean heuristic values yield the mean heuristic value of the collection.Selection
The higher the mean heuristic value of a pattern collection is, the more likely this pattern collection should be selected for the next generation. Therefore the mean heuristic values are normalized and converted into probabilities and Roulette Wheel Selection is used.
Language features supported:
action costs: supported
conditional effects: not supported
axioms: not supported
hillclimbing
hillclimbing(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity, random_seed=-1)
pdb_max_size (int [1, infinity]): maximal number of states per pattern database
collection_max_size (int [1, infinity]): maximal number of states in the pattern collection
num_samples (int [1, infinity]): number of samples (random states) on which to evaluate each candidate pattern collection
min_improvement (int [1, infinity]): minimum number of samples on which a candidate pattern collection must improve on the current one to be considered as the next pattern collection
max_time (double [0.0, infinity]): maximum time in seconds for improving the initial pattern collection via hill climbing. If set to 0, no hill climbing is performed at all.
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.
Systematically generated patterns
Generates all (interesting) patterns with up to pattern_max_size variables. For details, see
Florian Pommerening, Gabriele Roeger and Malte Helmert.
Getting the Most Out of Pattern Databases for Classical Planning.
In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013), pp. 2357-2364. 2013.
systematic(pattern_max_size=1, only_interesting_patterns=true)
pattern_max_size (int [1, infinity]): max number of variables per pattern
only_interesting_patterns (bool): Only consider the union of two disjoint patterns if the union has more information than the individual patterns.