Planning is about finding ways to achieve goals using models that help to predict how actions will affect the world. Temporal planning examines this problem in contexts where the timing (rather than simply the order) of actions matters. This might be because of deadlines, because of time-limited access to resources, because of external events or because, once started, processes run outside our direct control. Metric or numeric planning is concerned with problems where resources must be measured in quantitative terms, not just by presence or absence. In many real problems, time and numbers interact and these interactions make for temporal and metric planning. Such problems are hard to solve automatically, but this is the objective of this field of Artificial Intelligence research.

AI planning is the problem of finding a path through a state transition graph, from a specific initial state to one of a collection of target, or goal, states. The edges in the graph correspond to actions. In classical planning, states are valuations on a finite set of propositions and the path is simply an ordering of the actions that form it. However, in temporal planning things get more interesting: the transitions are labelled with the time at which they occur and constraints can be posed that enforce temporal relationships between some pairs of transitions in the graph. These constraints can represent the minimum or maximum duration it might take to complete some task, deadlines, the timing of external events forcing the corresponding transitions and so on. The planning problem is then to find a path that satisfies the temporal constraints between transitions that belong to it.

Metric, or numeric, planning is the problem of planning with states that include numeric-valued fluents. This means that states can contain non-propositional variables and the valuation represented by a state must assign these variables numeric values. One consequence of this is that state spaces are no longer necessarily finite, although domains encoded using PDDL (see below) have the property that only finitely many states are accessible in a finite number of steps. That means that the branching factor of outgoing edges from any state is always finite.

Temporal and numeric planning brings these things together. This is a complex problem and few planners really tackle the combined problem. In fact, there are several levels of difficulty involved, here.

• Numbers only appear as durations of actions (this is just temporal planning)
• Numbers appear in states, but only determine the values of constraints on durations and do not change between states (this is a slightly more complex form of temporal planning)
• Numbers appear in states and change between them, but the numbers that change do not affect durations of actions (this is a combined temporal and numeric planning problem, but the combination is simply that both elements appear in the same problem - they do not affect one another)
• Numbers that change between states affect durations (this is more complex and is the start of real temporal and numeric planning)
• The changes of numbers in states are themselves affected by durations of actions (this is a much more complex problem - duration-dependent effects change the structure of the state space dramatically)
• States themselves are assoiciated with processes that cause numeric values to change depending on how long is spent between entry to a state and exit from it (this is the problem of planning with continuous effects, or processes)

The last two of these represent very challenging problems, not least because they change the structure of the state space. Instead of offering the guarantee that each state offers only a finite number of choices by which to exit, each state offers a finite number of transitions to different logical valuations, but an infinite number of choices for how long should be spent in the state allowing processes or duration-dependent effects time to affect the numeric valuation in the state.

The image (click to enlarge) shows a fragment of a finite logical state space with the infinite sequence of numeric valuations that share the same logical state forming a vertical tube on each state. The passage of time can support transitions up these tubes as processes affect the numeric variables in each state.

PDDL was first proposed by Drew McDermott for the 1998 International Planning Competition. Since then it has been refined, extended and developed and has become the standard modelling language for domain-independent planners. There are many tools that can be used with the language, such as a plan validation system (VAL) and lots of planners. The language is action-centred: domains are described in terms of the actions that can be used to solve problems. Actions are given in terms of their preconditions and postconditions. The extension that formed PDDL2.1 introduced temporal planning into PDDL for the first time. It also refined the definition of numeric planning. Temporal planning in PDDL2.1 uses durative actions: actions that have a start, an end and, between the two, a duration of time. It allows flexible representation of the durations and also supports both continuous change during the execution of the a durative action and duration-dependent effects.

A more abitious representation of continuous processes is proposed in PDDL+ which uses explict representations of processes and events - transitions outside the direct control of the planner that are triggered by satisfaction of their preconditions in a state.

Temporal planners have tended to manage time in a simplified way. Durative actions can be compiled into a compressed form in which they are treated as though they are instantaneous. Planning can then be performed as for the classical case and time added in afterwards by scheduling the actions. This can work well when the problems being considered admit sequential solutions, but some problems require concurrent actions in order to solve them. In this case the compilation cannot work. As far as we know, LPGP, Crikey! and its cousins are the only planners that can properly handle required concurrency in temporal planning problems. These planners work by splitting durative actions into instantaneous actions representing each of the end points of the durative actions. These can be used in a classical planning approach, but the durations of the actions form constraints that govern the relationships between the times at which these actions are applied. These can be handled using a separate technology, such as a linear program (LPGP) or a simple temporal network (Crikey).

Numeric planning was first tackled with real success by Joerg Hoffmann in Metric-FF. Others have also offered ways to manage it, but the heuristic used in Metric-FF is an important tool for guiding search in numeric-logical state spaces. The idea is simply to ignore negative effects on resources and concentrate, in the heuristic evaluation of a state, on the actions required to produce resources that satisfy the precondition requirements of subsequent actions. This idea can work well, but it suffers from significant shortcomings in domains where there is flow of resources and exchange of one kind of resource for another. To address this, we have developed LPRPG, a forward search planner that uses a linear program to construct a better heuristic estimate for the cost of achieving the goals from a given state, in the context of numeric resource management. This exploits the strengths of linear programming to offer improved heuristic evaluation.

Bringing time and numbers together is tough. Crikey3 uses the Metric-FF heuristic to allow it to manage numbers, but it is not able to manage duration-dependent effects or continuous change. Our most recent planner is built on the Crikey3 chassis, but uses a linear program to tackle continuous linear effects. We replace the temporal reasoning in Crikey3, which uses a simple temporal network, with a linear program representation, that also allows us to capture the linear continuous effects and discrete numeric effects (including duration-dependent effects) in the same representation and solve them in combination. Search guidance in our planner uses an extended version of the Metric-FF heuristic, but work is ongoing to add the LPRPG heuristic to it.