Differences between revisions 8 and 21 (spanning 13 versions)
⇤ ← Revision 8 as of 2016-04-12 17:43:08 →
Size: 3187
Editor: XmlRpcBot
Comment:
← Revision 21 as of 2024-01-11 22:26:36 → ⇥
Size: 5246
Editor: XmlRpcBot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 2: Line 2:

== Delete relaxation constraints ==

Operator-counting constraints based on the delete relaxation. By default the constraints encode an easy-to-compute relaxation of h^+^. With the right settings, these constraints can be used to compute the optimal delete-relaxation heuristic h^+^ (see example below). For details, see

 * Tatsuya Imai and Alex Fukunaga.<<BR>>
 [[https://www.jair.org/index.php/jair/article/download/10972/26119/|On a practical, integer-linear programming model for delete-freetasks and its use as a heuristic for cost-optimal planning]].<<BR>>
 ''Journal of Artificial Intelligence Research'' 54:631-677. 2015.

{{{
delete_relaxation_constraints(use_time_vars=false, use_integer_vars=false)
}}}

 * ''use_time_vars'' (bool): use variables for time steps. With these additional variables the constraints enforce an order between the selected operators. Leaving this off (default) corresponds to the time relaxation by Imai and Fukunaga. Switching it on, can increase the heuristic value but will increase the size of the constraints which has a strong impact on runtime. Constraints involving time variables use a big-M encoding, so they are more useful if used with integer variables.
 * ''use_integer_vars'' (bool): restrict auxiliary variables to integer values. These variables encode whether operators are used, facts are reached, which operator first achieves which fact, and in which order the operators are used. Restricting them to integers generally improves the heuristic value at the cost of increased runtime.

'''Example:''' To compute the optimal delete-relaxation heuristic h^+^, use
{{{
operatorcounting([delete_relaxation_constraints(use_time_vars=true, use_integer_vars=true)], use_integer_operator_counts=true))
}}}
Line 5: Line 25:
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 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
Line 9: Line 29:
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press 2014.  In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press, 2014.
Line 13: Line 33:
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268-2274. 2013.  In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268-2274. AAAI Press, 2013.
Line 25: Line 45:
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2357-2364. 2013.  In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2357-2364. AAAI Press, 2013.
Line 32: Line 52:
Line 33: Line 54:
Line 37: Line 59:
 In ''Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming (CP 2007)'', pp. 651-665. 2007.  In ''Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming (CP 2007)'', pp. 651-665. Springer-Verlag, 2007.
Line 41: Line 63:
 In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268-2274. 2013.  In ''Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013)'', pp. 2268-2274. AAAI Press, 2013.
Line 45: Line 67:
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press 2014.  In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 226-234. AAAI Press, 2014.
Line 48: Line 70:
state_equation_constraints() state_equation_constraints(verbosity=normal)
Line 51: Line 73:
/* moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) */
/* cmdline: txt2tags */		  * ''verbosity'' ({silent, normal, verbose, debug}): Option to specify the verbosity level.
     * {{{silent}}}: only the most basic output
     * {{{normal}}}: relevant information to monitor progress
     * {{{verbose}}}: full output
     * {{{debug}}}: like verbose with additional debug output

Contents

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

Delete relaxation constraints

Operator-counting constraints based on the delete relaxation. By default the constraints encode an easy-to-compute relaxation of h+. With the right settings, these constraints can be used to compute the optimal delete-relaxation heuristic h+ (see example below). For details, see 

delete_relaxation_constraints(use_time_vars=false, use_integer_vars=false)

  • use_time_vars (bool): use variables for time steps. With these additional variables the constraints enforce an order between the selected operators. Leaving this off (default) corresponds to the time relaxation by Imai and Fukunaga. Switching it on, can increase the heuristic value but will increase the size of the constraints which has a strong impact on runtime. Constraints involving time variables use a big-M encoding, so they are more useful if used with integer variables.

  • use_integer_vars (bool): restrict auxiliary variables to integer values. These variables encode whether operators are used, facts are reached, which operator first achieves which fact, and in which order the operators are used. Restricting them to integers generally improves the heuristic value at the cost of increased runtime.

Example: To compute the optimal delete-relaxation heuristic h+, use 

operatorcounting([delete_relaxation_constraints(use_time_vars=true, use_integer_vars=true)], use_integer_operator_counts=true))

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 

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 

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 

state_equation_constraints(verbosity=normal)

  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.

    • silent: only the most basic output

    • normal: relevant information to monitor progress

    • verbose: full output

    • debug: like verbose with additional debug output

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