Differences between revisions 1 and 10 (spanning 9 versions)
⇤ ← Revision 1 as of 2015-10-30 22:15:06 →
Size: 5855
Editor: XmlRpcBot
Comment:
← Revision 10 as of 2019-11-22 20:01:08 → ⇥
Size: 3226
Editor: XmlRpcBot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 6: Line 6:
 * Florian Pommerening, Gabriele Röger, Malte Helmert and Blai Bonet.<<BR>>
 [[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892/8031|LP-based Heuristics for Cost-optimal Planning]].<<BR>>
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press 2014.
* Florian Pommerening, Gabriele Roeger, Malte Helmert and Blai Bonet.<<BR>>
 [http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892/8031 LP-based Heuristics for Cost-optimal Planning].<<BR>>
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press, 2014.
Line 10: Line 12:
 [[http://ijcai.org/papers13/Papers/IJCAI13-335.pdf|An admissible heuristic for SAS+ planning obtained from the state equation]].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268–2274. 2013.		  [http://ijcai.org/papers13/Papers/IJCAI13-335.pdf An admissible heuristic for SAS+ planning obtained from the state equation].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268-2274. AAAI Press, 2013.
Line 17: Line 19:
== Posthoc optimization constraints for iPDB patterns == == Posthoc optimization constraints ==
Line 19: Line 21:
A pattern collection is discovered, using iPDB hillclimbing (see [Doc/[[Doc/Heuristic#iPDB|iPDB]]]).The generator will compute a PDB for each pattern and add the constraint h(s) <= sum_{o in relevant(h)} Count_o. For details, see
 * Florian Pommerening, Gabriele Röger and Malte Helmert.<<BR>>
 [[http://ijcai.org/papers13/Papers/IJCAI13-347.pdf|Getting the Most Out of Pattern Databases for Classical Planning]].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2357-2364. 2013.		 The generator will compute a PDB for each pattern and add the constraint h(s) <= sum_{o in relevant(h)} Count_o. For details, see

 * Florian Pommerening, Gabriele Roeger and Malte Helmert.<<BR>>
 [http://ijcai.org/papers13/Papers/IJCAI13-347.pdf Getting the Most Out of Pattern Databases for Classical Planning].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2357-2364. AAAI Press, 2013.
Line 25: Line 28:
pho_constraints_ipdb(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity) pho_constraints(patterns=systematic(2))
Line 28: Line 31:
 * ''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.
== Posthoc optimization constraints for manually specified patterns ==
The generator will compute a PDB for each pattern and add the constraint h(s) <= sum_{o in relevant(h)} Count_o. For details, see
 * Florian Pommerening, Gabriele Röger and Malte Helmert.<<BR>>
 [[http://ijcai.org/papers13/Papers/IJCAI13-347.pdf|Getting the Most Out of Pattern Databases for Classical Planning]].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2357-2364. 2013.

{{{
pho_constraints_manual(patterns=<none>, combo=false, max_states=1000000)
}}}

 * ''patterns'' (list of list of int): list of patterns (which are lists of variable numbers of the planning task). Default: each goal variable is used as a single-variable pattern in the collection.
 * ''combo'' (bool): use the combo strategy
 * ''max_states'' (int [1, infinity]): maximum abstraction size for combo strategy
== Posthoc optimization constraints for systematically generated patterns ==
All (interesting) patterns with up to pattern_max_size variables are generated. The generator will compute a PDB for each pattern and add the constraint h(s) <= sum_{o in relevant(h)} Count_o. For details, see
 * Florian Pommerening, Gabriele Röger and Malte Helmert.<<BR>>
 [[http://ijcai.org/papers13/Papers/IJCAI13-347.pdf|Getting the Most Out of Pattern Databases for Classical Planning]].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2357-2364. 2013.

{{{
pho_constraints_systematic(pattern_max_size=1, only_interesting_patterns=true)
}}}

 * ''pattern_max_size'' (int): 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.		  * ''patterns'' ([[Doc/PatternCollectionGenerator|PatternCollectionGenerator]]): pattern generation method
Line 60: Line 34:
Line 61: Line 36:
 [[http://link.springer.com/chapter/10.1007/978-3-540-74970-7_46|An LP-based heuristic for optimal planning]].<<BR>>
 In ''Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming (CP 2007)'', pp. 651–665. 2007.		  [http://link.springer.com/chapter/10.1007/978-3-540-74970-7_46 An LP-based heuristic for optimal planning].<<BR>>
 In ''Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming (CP 2007)'', pp. 651-665. Springer-Verlag, 2007.
Line 64: Line 40:
 [[http://ijcai.org/papers13/Papers/IJCAI13-335.pdf|An admissible heuristic for SAS+ planning obtained from the state equation]].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268–2274. 2013.
 * Florian Pommerening, Gabriele Röger, Malte Helmert and Blai Bonet.<<BR>>
 [[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892/8031|LP-based Heuristics for Cost-optimal Planning]].<<BR>>
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press 2014.		  [http://ijcai.org/papers13/Papers/IJCAI13-335.pdf An admissible heuristic for SAS+ planning obtained from the state equation].<<BR>>
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268-2274. AAAI Press, 2013.

 * Florian Pommerening, Gabriele Roeger, Malte Helmert and Blai Bonet.<<BR>>
 [http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892/8031 LP-based Heuristics for Cost-optimal Planning].<<BR>>
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press, 2014.
Line 74: Line 51:
/* moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) */ /* moin code generated by txt2tags 2.6 (http://txt2tags.org) */

Contents

  1. LM-cut landmark constraints
  2. Posthoc optimization constraints
  3. State equation constraints

LM-cut landmark constraints

Computes a set of landmarks in each state using the LM-cut method. For each landmark L the constraint sum_{o in L} Count_o >= 1 is added to the operator counting LP temporarily. After the heuristic value for the state is computed, all temporary constraints are removed again. For details, see

  • Florian Pommerening, Gabriele Roeger, Malte Helmert and Blai Bonet.
    [http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892/8031 LP-based Heuristics for Cost-optimal Planning].
    In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014), pp. 226-234. AAAI Press, 2014.

  • Blai Bonet.
    [http://ijcai.org/papers13/Papers/IJCAI13-335.pdf An admissible heuristic for SAS+ planning obtained from the state equation].
    In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013), pp. 2268-2274. AAAI Press, 2013. 

lmcut_constraints()

Posthoc optimization constraints

The generator will compute a PDB for each pattern and add the constraint h(s) <= sum_{o in relevant(h)} Count_o. For details, see

  • Florian Pommerening, Gabriele Roeger and Malte Helmert.
    [http://ijcai.org/papers13/Papers/IJCAI13-347.pdf 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. AAAI Press, 2013. 

pho_constraints(patterns=systematic(2))

State equation constraints

For each fact, a permanent constraint is added that considers the net change of the fact, i.e., the total number of times the fact is added minus the total number of times is removed. The bounds of each constraint depend on the current state and the goal state and are updated in each state. For details, see

  • Menkes van den Briel, J. Benton, Subbarao Kambhampati and Thomas Vossen.
    [http://link.springer.com/chapter/10.1007/978-3-540-74970-7_46 An LP-based heuristic for optimal planning].
    In Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming (CP 2007), pp. 651-665. Springer-Verlag, 2007.

  • Blai Bonet.
    [http://ijcai.org/papers13/Papers/IJCAI13-335.pdf An admissible heuristic for SAS+ planning obtained from the state equation].
    In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013), pp. 2268-2274. AAAI Press, 2013.

  • Florian Pommerening, Gabriele Roeger, Malte Helmert and Blai Bonet.
    [http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892/8031 LP-based Heuristics for Cost-optimal Planning].
    In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014), pp. 226-234. AAAI Press, 2014. 

state_equation_constraints()

FastDownward: Doc/ConstraintGenerator (last edited 2024-01-11 22:26:36 by XmlRpcBot)