Modeling Action Costs in IPC-2008
In the sequential (satisficing | optimization) and net benefit (satisficing | optimization) tracks of IPC-2008, actions have an associated non-negative cost. Action costs play an important part in determining plan quality in these tracks:
- In the sequential tracks, the objective is to find a plan that minimizes total cost, i.e., the sum of the costs of the actions in the plan.
- In the net benefit tracks, the objective is to find a plan that maximizes net benefit, i.e., the sum of the utilities of the goals that have been achieved, minus total cost.
Action costs can be modeled in all PDDL versions since PDDL 2.1 through using numeric state variables and :metric specifications. However, in the sequential tracks of IPC-2008 in particular, planners are not expected to support arbitrary numeric fluents. For this reason, we introduce a new PDDL requirement called :action-costs, which is a limited version of the :numeric-fluents requirement.
The :action-costs requirement
If the :action-costs requirement is included in a PDDL specification, the use of numeric fluents is enabled (similar to the :numeric-fluents requirement). However, numeric fluents may only be used in certain very limited ways:
- Numeric fluents may not be used in any conditions (preconditions, goal conditions, conditions of conditional effects, etc.).
A numeric fluent may only be used as the target of an effect if it is 0-ary and called total-cost. If such an effect is used, then the total-cost fluent must be explicitly initialized to 0 in the initial state.
The only allowable use of numeric fluents in effects is in effects of the form (increase (total-cost) <numeric-term>), where the <numeric-term> is either a non-negative numeric constant or of the form (<function-symbol> <term>*)" for a <function-symbol> different from total-cost. (The <term> here is interpreted as shown in the PDDL grammar, i.e., it is a variable symbol or an object constant. Note that this <term> cannot be a <function-term>, even if the object fluents requirement is used.)
- No numeric fluent may be initialized to a negative value.
If the problem contains a :metric specification, the objective must be (minimize (total-cost)), or - only if the :durative-actions requirement is also set - to minimize a linear combination of total-cost and total-time, with non-negative coefficients.
Note that an action can have multiple effects that increase (total-cost), which is particularly useful in the context of conditional effects.
Also note that these restrictions imply that (total-cost) never decreases throughout plan execution, i.e., action costs are never negative.
Action costs in IPC-2008
For IPC-2008, we will obey some further restrictions. However, these are not part of the specification of the :action-costs requirement:
- The PDDL specification contains no fractional numbers, i.e., all action costs are non-negative integers.
The total-cost fluent is not modified within conditional effects, and each action contains at most one atomic effect affecting total-cost.
Also note that we will not mix durative actions and action costs. The objective in the temporal tracks is always to minimize total time (makespan).