The adoption of a stable numeric extension to the PDDL core allowed us to introduce a further extension into PDDL2.1, namely a new (optional) field within the specification of problems: a plan metric. Plan metrics specify, for the benefit of the planner, the basis on which a plan will be evaluated for a particular problem. The same initial and goal states might yield entirely different optimal plans given different plan metrics. Of course, a planner might not choose to use the metric to guide its development of a solution but just to evaluate a solution post hoc. This approach might lead to sub-optimal, and possibly even poor quality plans, but it is a pragmatic approach to the handling of metrics which was quite widely used in the competition. This issue is discussed further in the companion paper analysing the results of the 3rd IPC in this issue [Long FoxLong Fox2003b].
The value total-time can be used to refer to the temporal span of the entire plan. Other values must all be built from primitive numeric expressions defined within a domain and manipulated by the actions of the domain. As a consequence, plan metrics can only express non-temporal metrics in PDDL2.1 domains using numeric expressions. Any arithmetic expression can be used in the specification of a metric -- there is no requirement that the expression be linear. It is the domain designer's responsibility to ensure that plan metrics are well-defined (for example, do not involve divisions by zero). An example of use of a plan metric is shown in Figure 5.
The implications of having introduced this extension are far-reaching and have already helped to demonstrate some important new challenges for planning systems -- particularly fully-automated systems. An enriched descriptive power for the evaluation of plans is a crucial extension for the practical use of planners, since it is almost never the case that real plans are evaluated solely by the number of actions they contain.
Metrics are described in the problem description, allowing a modeller to easily explore the effect of different metrics in the construction of solutions to problems for the same domain. In order to define a metric in terms of a specific quantity it is necessary to instrument that quantity in the domain description. For example, if the metric is defined in terms of overall fuel use a fuel-use quantity can be initialised to zero in the initial state and then updated every time fuel is consumed. In the domain shown in Figure 5 it is possible to minimise a linear combination of fuel used by each of the vehicles such as:
The use of plan metrics is subtle and can have dramatic impact on the plans being sought. Perhaps the simplest case is where all actions increase a metric that must be minimised, or decrease one that must be maximised. This is the case in the example shown in Figure 5, where any use of the drive action can only worsen the value of the plan metric (whether we use the metric shown in the figure or the maximising metric described in the last paragraph). This situation might appear to be relatively straightforward: a planner must attempt to use as few actions to solve a problem as possible. In fact, even this case is a little more complex than it appears -- there can be rival plans in which one uses more actions but has lower overall cost than the other. A more complex case arises when some actions improve the quality metric while others degrade it. For example, if we use the maximising metric but also add a refuel action to the domain then driving will degrade plan quality (by reducing the fuel level of a vehicle) but refuelling will improve plan quality (by increasing the fuel level of a vehicle). In this case, a planner can attempt to use actions to improve the plan quality without those actions actually contributing to achieving the goals. For example, refuelling might not be necessary to get the vehicles to their destinations, but adding refuelling actions would improve the quality of a solution. This process could involve trading off finite and irreplaceable resources for the increased value of the plan. This would be the case if, for example, refuelling a vehicle took fuel from a finite reservoir. Alternatively a domain could allow plans of arbitrarily high value to be constructed by using more and more actions. This would occur in the metric vehicles domain using the maximising vehicle's fuel level metric if refuelling were not constrained, since the domain does not impose a limit on the fuel capacities of the vehicles.
The case in which plans are constrained by finite availability of resources, is an important and interesting form of the planning problem, but the case in which plans of arbitrarily high utility can be constructed, is obviously an ill-defined problem, since an optimal plan does not exist. It is non-trivial to determine whether a planning problem provided with a metric is ill-defined. In fact, as Helmert shows [HelmertHelmert2002], the introduction of numeric expressions, even in the constrained way that we have adopted in PDDL2.1, makes the planning problem undecidable. The problem of finding a collection of actions which does not consume irreplaceable resources and has an overall beneficial impact on a plan metric is at least as hard as the planning problem. Therefore it is clear that determining whether a planning problem is even well-defined is undecidable. This does not make it worthless to consider planning with metrics, of course, but it demonstrates that the modelling problem, as well as the planning problem, becomes even more complex when metrics are introduced.
One strategy available to planners working with problems subject to plan metrics is to ignore the metric and simply produce a plan to satisfy the logical goals that a problem specifies. In this case, the plan quality will simply be the value, according to the metric, of the plan that happens to be constructed. This strategy is unsophisticated and it is obviously better for a planner to construct a plan guided by the specified metric. How best to use a metric to expedite the search process in a fully-automated planner is still a research issue.
