By construction, it is easy to see that any optimal plan P = hA1, . . . , Aj , Aj+1**, . . . , A**i+1i for the planning problem Pβ must have Aj+1 = {finish} and Aj+2 = **. . .** = Ai+1 = ∅ for some j ∈ {0**, . . . , i**}. We thus have the following desired property.

Proposition 5.1 The optimal plans for Pβ are in 1-1 correspondence to the shortest plans reaching Q in PD*. More precisely,* P = hA1, . . . , Aj+1, ∅**, . . . ,** ∅i *is an optimal optimistic plan for* Pβ(**PD, Q, i**) and Aj+1 = {finish} *if and only if* P
′ = hA1**, . . . , A**j i *is an optimistic plan for* hPD, Q ? (j)i *where* j ∈ {0**, . . . , i**}*, and* hPD, Q ? (j
′)i *has no optimistic plan for each* j
′ < j.

In our Blocks World example, using this method we get all 2-step plans, if we choose i ≥ 2.

To compute shortest plans over all plan lengths, we can set the upper bound i large enough such that plans of length l ≤ i are guaranteed to exist. A trivial such bound is the total number of legal states which is in general exponential in the number of fluents.

However, many typical applications have an inherent, much smaller bound on the plan length.

For instance, in a Blocks World with n blocks, any goal configuration can be reached within at most 2n − sinit − s**goal** steps, where s**init** and s**goal** are the numbers of stacks in the initial and the goal state, respectively.5 Therefore, 6 is an upper bound for the plan length of our simple instance.

We remark that this approach for minimizing plan length is only efficient if an upper bound close to the optimum is known. Searching for a minimum length plan by iteratively increasing the plan length may be much more efficient if no such bound is known, since a weak upper bound can lead to an explosion of the search space (cf. the benchmarks in Section 7.2).

## 5.1.3 Shortest Among The Cheapest Plans (Γ)

In the previous subsection, we have shown how to calculate shortest plans for K programs without action costs. Combining arbitrary Kc programs and the rewriting method described there is easy.

If we want to find a shortest among the cheapest plans, we can use the same rewriting, with just a little change. All we have to do is setting the costs of all actions except finish at least as high as the highest possible cost of the finish action. This is is obviously the plan length i + 1. So, we simply modify all action declarations A requires B costs C where D.

in Pβ by multiplying the costs with factor i + 1:
A requires B costs C1 where C1 = (i **+ 1)** ∗ C, D.

This lets all other action costs take priority over the cost of finish and we can compute plans satisfying criterion (γ). Let Pγ denote the resultant planning problem. Then we have:
Proposition 5.2 The optimal plans for Pγ *are in 1-1 correspondence to the shortest among the* cheapest plans reaching Q in PD within i *steps. More precisely,* P = hA1, . . . , Aj+1, ∅**, . . . ,** ∅i is an optimal optimistic plan for Pγ(**PD, Q, i**) and Aj+1 = {finish} *if and only if (i)* P
′ =
hA1**, . . . , A**j i*is a plan for* Pj = hPD, Q ? (j)i*, where* j ∈ {0**, . . . , i**}*, and (ii) if* P
′′ = hA1**, . . . , A**j
′i is any plan for Pj
′ = hPD, Q ? (j
′)i *where* j
′ ≤ i*, then either* **cost**Pj
′(P
′′) **> cost**Pj
(P
′) or costPj
′(P
′′) = **cost**Pj
(P
′) and j
′ ≥ j.

Figure 4 shows Pγ for our Blocks World instance where i = 6. One optimal plan for Pγ is