Graphplan is a parallel-optimal planner for propositional planning problems. The rough working of the Graphplan algorithm is the following. First, the parametric input is grounded. Starting with a planning graph, which only consists of the initial state in the first layer, the graph is incrementally constructed. In one stage of the algorithm, the planning graph is extended with one action and one propositional layer followed by a graph extraction phase. If this search terminates with no solution, the plan horizon is extended with one additional layer. As an example, consider the Rocket domain for transporting cargo in space (see Fig. 15.1). The layered planning graph is shown in Table 15.1.

In the forward phase the next action layer is determined as follows. For each action and each instantiation of it, a node is inserted, provided that no two preconditions are marked as mutually exclusive (mutex ). Two propositions a and b are marked mutex, if all options to generate a are exclusive to all options to generate b. Additionally, so-called noop actions are included that merely propagate existing propositions to the next layer. Next, the actions are tested for exclusiveness and for each action a list of all other actions is recorded, for which they are exclusive. To generate the next propositional layer, the add-effects are inserted and taken as the input for the next stage.

A fixpoint is reached when the set of propositions no longer changes. As one subtle problem, this test for termination is not sufficient. Consider a goal in Blocksworld given by (on a b), (on b c), and (on c a). Every two conditions are satisfiable but not all three all together. Thus, the forward phase terminates if the set of propositions and the goal set in the previous stage have not changed.

It is not difficult to see that the size of the planning graph is polynomial in the number n of objects, the number m of action schemas, the number p of propositions in the initial state, the length l of the longest add-list, and the number of layers in the planning graph. Let k be the largest number of action parameters. The number of instantiated effects is bounded by . Therefore, the maximal number of nodes in every propositional layer is bounded by . Since every action schema can be instantiated in at most different ways, the maximal number of nodes in each action layer is bounded by .

In the generated planning graph, Graphplan constructs a valid plan, chaining backward from the set of goals. In contrast to most other planners, this processing works layer by layer to take care of preserving the mutex relations. For a given time step t, Graphplan tries to extract all possible actions (including noops) from time step t − 1, which has the current subgoal as add-effects. The preconditions for these actions build the subgoals to be satisfied in time step t − 1 to satisfy the chosen subgoal at time step t. If the set of subgoals is not solvable, Graphplan chooses a different set of actions, and recurs until all subgoals are satisfied or all possible combinations have been exhausted. In the latter case, no plan (with respect to the imposed depth threshold) exists, as it can be shown that Graphplan terminates with failure if and only if there is no solution to the current planning problem. The complexity of the backward phase is exponential (and has to be unless PSPACE = P). By its layered construction, Graphplan constructs a plan that has the smallest number of parallel plan steps.

To cast a fully instantiated action planning task as a satisfiability problem we assign to each proposition a time stamp denoting when it is valid. As an example, for the initial state and goal condition of a sample Blocksworld instance, we may have generated the formulaFurther formulas express action execution. They include action effects, such asand noop clauses for propositions to persist. To express that no action with unsatisfied precondition is executed, we may introduce rules, in which additional action literals imply their preconditions, such asEffects are dealt with analogously. Moreover, (for sequential plans) we have to express that at one point in time only one action can be executed. We haveFinally, for a given step threshold N we require that at every step i < N at least one action has to be executed; for all i < N we require

The only model of this planning problem is (move a b t 1), (move b t a 2). Satplan is a combination of a planning problem encoding and an SAT solver. The planner's performance participates in the development of more and more efficient SAT solvers.

Extensions of Satplan to parallel planning encode the planning graph and the mutexes of Graphplan. For this approach, Satplan does not find the plan with the minimal total number of steps, but the one with the minimal number of parallel steps.

One of the first estimates for heuristic search planning is the max-atom heuristic. It is an approximation of the optimal cost for solving a relaxed problem in which the delete lists are ignored. An illustration is provided in Figure 15.2 (left).

The heuristic is based on dynamic programming. Consider a propositional and grounded propositional planning problem (see Ch. 1) with planning states u and v, and propositions p and q. Value is the sum of the approximations g(u, p), to reach p from u, whereis a fixpoint equation. The recursion starts with g(u, p) = 0, for p ∈ u, and g(u, p) = ∞, otherwise. The values of g are computed iteratively, until the values no longer change. The costs g(u, C) for the set C is computed as . In fact, the cost of achieving all the propositions in a set can be computed as either a sum (if sequentiality is assumed) or as a max (if parallelism is assumed instead). The max-atom heuristic chooses the maximum of the cost values with . The pseudo code is shown in Algorithm 15.1. This heuristic is consistent, since by taking the maximum cost values, the heuristic on an edge can decrease by at most 1.

As the heuristic determines the backward distance of atoms with respect to the initial state, the previous definition of the heuristic is of use only for backward or regression search. However, it is not difficult to implement a variant that is applicable to forward or progression search, too.

The max-atom heuristic has been extended to max-atom-pair to include larger atom sets, which enlarges the extracted information (without losing admissibility) by approximating the costs of atom pairs:where p & q denotes that p and q are both contained in the add list of the action, and where p|q denotes that p is contained in the add list and q is neither contained in the add list nor in the delete list. If all goal distances are precomputed, then these distances can be retrieved from a table, yielding a fast heuristic.

The extension to h^m with atom sets of elements has to be expressed with the following recursion:where R(C) denotes all pairs (D, O) that contain , , and . It is rarely used in practice.

It has been argued that the layered arrangement of propositions in Graphplan can be interpreted as a special case of a search with h².

In the following, we study how to apply pattern databases (see Ch. 4) to action planning. For a fixed state vector (in the form of a set of instantiated predicates) we provide a general abstraction function. The ultimate goal is to create admissible heuristics for planning problems fully automatically.

Planning patterns omit propositions from the planning space. Therefore, in an abstract planning problem with regard to a set , a domain abstraction is induced by . (Later on we will discuss how R can be selected automatically.) The interpretation of ϕ is that all Boolean variables for propositions not in R are mapped to don't care. An abstract planning problem of a propositional planning problem (S, A, s, T) with respect to a set of propositional atoms R is defined by , , , , where a|_R for is given as . An illustration is provided in Figure 15.2 (right).

This means that abstract actions are derived from concrete ones by intersecting their precondition, add, and delete lists with the subset of predicates in the abstraction. Restriction of actions in the concrete space may yield noop actions in the abstract planning problem, which are discarded from the action set A|_R.

A planning pattern database with respect to a set of propositions R and a propositional planning problem is a collection of pairs (d, v) with and d being the shortest distance to the abstract goal. Restriction |_R is solution preserving; that is, for any sequential plan π for the propositional planning problem P there exists a plan π_R for the abstraction . Moreover, an optimal abstract plan for P|_R is shorter than or equal to an optimal plan for P. Strict inequality holds if some abstract actions are noops, or if there are even shorter paths in the abstract space. We can also prove consistency of pattern database heuristics as follows. For each action a that maps u to v in the concrete space, we have . By the triangular inequality of shortest paths, the abstract goal distance for ϕ(v) plus one is larger than or equal to the abstract goal distance ϕ(u).

Figure 15.3 illustrates a standard (left) and multiple pattern database (right) showing that different abstractions may refer to different parts of the state vector.

There are two main problems of the relaxed planning heuristic (see Ch. 1). First, unsolvable problems can become solvable, and, second, the distance approximations may become weak. Take, for example, the two Logistics problems in Figure 15.5. In both cases, we have to deliver a package to its destination (indicated with a shaded arrow) using some trucks (initially located at the shaded nodes). In the first case (illustrated on the left) a relaxed plan exists, but the concrete planning problem (assuming traveling constraints induced by the edges) is actually unsolvable.

In the second case (illustrated on the top right) a concrete plan exists. It requires moving the truck to pick up the package and return it to its home. The relaxed planning heuristic returns a plan that is about half as good. If we scale the problem as indicated to the lower part of the figure, heuristic search planners based on the relaxed planning heuristic quickly fail.

The causal graph analysis is based on the following multivalued variable encoding, , , , , , , …, }, , and .

The causal graph of an SAS⁺ planning problem P with variable set X is a directed graph , where if and only if and there is an action , such that is defined and either or eff (u) is defined. This implies that an edge is drawn from one variable to another if the change of the second variable is dependent on the current assignment of the first variable. The causal graph of the first example (Fig. 15.5, left) is shown in Figure 15.6. These (in practice acyclic) graphs are divided into high-level (v_c) and low-level variables (v₁ and v₂).

Given an SAS⁺ planning problem with , the domain transition graph G_v is a directed labeled graph with node set D_v. Being a projection of the original state space it contains an edge if there is an action with (or undefined) and . The edge is labeled by . The domain transition graph for the example problem is shown in Figure 15.7.

Plan existence in SAS⁺ planning problems is provably hard. Hence, depending on the structure of the domain transition graph(s), a heuristic search planning algorithm approximates the original problem. The approximation, measured in the number of executed plan steps, is used as a (nonadmissible) heuristic to guide the search in the concrete planning space.

Distances are measured between different value assignments to variables. The (minimal) cost to change the assignment of v from d to is computed as follows. If v has no causal predecessor, is the shortest path distance from d to in the domain transition graph, or , if no such path exists. Let X_v be the set of variables that have v and all immediate predecessors of v in the causal graph of P. Let P_v be the subproblem induced by X_v with the initial value of v being d and the goal value of v being . Furthermore, let , where π is the shortest plan computed by the approximation algorithm (see later). The costs of the low-level variables are the shortest path costs in the domain transition graph, and 1 for the high-level variables. Finally, we define the heuristic estimate h(u) of the multivalued planning state u as

The approximation algorithm uses a queue for each high-level variable. It has polynomial running time but there are solvable instances for which no solution is obtained. Based on a queue Q it roughly works as shown in Algorithm 15.2.

Applied to an example (see Fig. 15.5, right), Q initially contains the elements . The stages of the algorithms are as follows. First, we remove D from the queue, such that . Choosing (pickup D) yields (move A B), (move B C), (move C D), (pickup D)). Next, we remove t from the queue, such that . Choosing (drop A) yields (move A B), (move B C), (move C D), (pickup D), (move D C), (move C B), (move B A), (drop A)). Choosing (drop B), (drop C), (drop D) produces similar but shorter plans. Afterward, we remove C from the queue, such that yields no improvement. Subsequently, B is removed from the queue, such that yields no improvement. Lastly, A is removed from the queue and the algorithm terminates and returns .

Metric planning involves reasoning about continuous state variables and arithmetic expressions. An example for an according PDDL action is shown in Figure 15.8.

Many existing planners terminate with the first solution they find. Optimization in metric planning, however, calls for improved exploration algorithms.

The state space of a metric planning instance is the set of assignments to the state variables with valid values. The logical state space is the result of projecting the state space to the components that are responsible for representing predicates. Analogously, the numerical state space is the result of projecting the state space to the components that represent functions. Figure 15.10 shows an instantiated problem, which refers to the domain Boxes shown in Figure 15.9.

In metric planning problems, preconditions and goals are of the form , where and are arithmetic expressions over the sets of variables and operators and where is selected from , ≤, >, <, . Assignments are of the form with head v and exp being an arithmetic expression (possibly including v). Additionally, a domain metric can be specified which has to be minimized or maximized over the end states of all valid plans. Costs in the domain metric refer to assignments to the numerical state variables.

Metric planning is an essential language extension. Since we can encode the working of random access machines in real numbers, even the decision problem, whether or not a plan exists, is undecidable. The undecidability result show that in general we cannot prove that a problem obeys no solution. However, if there is one, we may be able to find it. Moreover, as metric planning problems may span infinite state spaces, heuristics to guide the search process are even more important than for finite-domain planning problems. For example, we know that A* is complete even on infinite graphs, given that the cumulated costs of every infinite path is unbounded.

Temporal planning domains include temporal modifiers at start, over all, and at end, where label at start denotes the preconditions and effects at invocation time of the action, over all refers to an invariance condition that must hold, and at end refers to the finalization conditions and consequences of the action. An example for a PDDL action with numbers and durations is shown in Figure 15.11.

Derived predicates are predicates that are not affected by any of the actions available to the planner. Instead, the predicate's truth values are derived by a set of rules of the form if ϕ(x) then P(x). An example of a derived predicate is the above predicate in Blocksworld, which is true between blocks x and y, whenever x is transitively (possibly with some blocks in between) on y. This predicate can be defined recursively as follows:

The semantics, roughly, are that an instance of a derived predicate is satisfied if and only if it can be derived using the available rules. More formally, let R be the set of rules for the derived predicates, where the elements of R have the form – if ϕ(x) then. Then , for a set of basic facts u, is defined as follows:This definition uses the standard notations of the modeling relation between states (represented as sets of facts in our case) and formulas, and of the substitution ϕ(c) of the free variables in formula ϕ(x) with a constant vector c. In words, D(u) is the intersection of all supersets of u that are closed under application of the rules R. D(u) can be computed by the simple process shown in Algorithm 15.5. Hence, derivation rules can be included in a forward chaining heuristic search planner by inferring the truth of the derived rule for each step.

Suppose that we have grounded all derived predicates to the rules . In ϕ there can be further derived predicates, which by the acyclic definition of derived predicates cannot be directly or indirectly dependent from p. For the rule the values p and ϕ are equivalent. This implies that p is nothing more than a macro for the expression ϕ. All derived predicates can be eliminated from the planning instance by the substitution with more complex descriptions. The advantage with regard to alternative methods for handling derived predicates is that the state vector does not have to be extended.

Timed initial literals are an extension for temporal planning. Syntactically they are a very simple way of expressing a certain restricted form of exogenous events: facts that will become true or false at time points that are known to the planner in advance, independent of the actions that the planner chooses to execute. Timed initial literals are thus deterministic unconditional exogenous events.

An illustrative example considers a planning task for shopping. There is a single action that achieves the goal, which requires a shop to be open as its precondition. The shop opens at time step 9 relative to the initial state, and closes at time step 20. We can express the shop opening times by two timed initial literals:

Timed initial literals can be inserted into a heuristic search planner as follows. We associate with each (grounded) action so-called action execution time windows that specify the interval of a save execution. This is done by eliminating the preconditions that are related to the time initial literal. For ordinary literals and Strips actions, the conjunction of precondition leads to the intersection of action execution time windows. For repeated literals or disjunctive precondition lists, time windows have to be kept, while simple execution time windows can be integrated into the PERT scheduling process.

State trajectory or plan constraints provide an important step of PDDL toward temporal control knowledge and temporally extended goals. They assert conditions that must be satisfied during the execution of a plan. Through the decomposition of temporal plans into plan happenings, state trajectory constraints feature all levels of the PDDL hierarchy. For example, the constraint a fragile block can never have something above it can be expressed as

As illustrated in Chapter 13 plan constraints can be compiled away. The approach translates the constraints in linear temporal logic and compiles them into finite-state automata. The automata are simulated in parallel to the search. The initial state of the automaton is added to the initial state of the problem and the automation transitions are compiled to actions. A synchronization mechanism controls that the original actions and the automata actions alternate. Planning goals are extended with the accepting states of the automata.

Annotating individual goal conditions or state trajectory constraints with preferences model soft constraints and allow the degree of satisfaction to be scaled with respect to hard constraints that have to be fulfilled in a valid plan. The plan objective function includes special variables referring to the violation of the preference constraints and allows planners to optimize plans.

Quantified preference rules like

are grounded (one for each block), while the inverse expression

leads to only one constraint.

Preferences can be treated as variables using conditional effects, so that the heuristics derived earlier remain appropriate for effective plan-finding.