fluents : on(B, L) requires block(B), location(L).

blocked(B) requires block(B).

moved(B) requires block(B).

gr.

actions : move(B, L) requires block(B), location(L) costs C where C = 7 ∗ 1.

finish costs time.

always : executable move(B, L) if B != L, not gr.

nonexecutable move(B, L) if blocked(B). nonexecutable move(B, L) if blocked(L). nonexecutable move(B, L) if move(B1, L), B < B1, block(L).

nonexecutable move(B, L) if move(B, L1), L < L1. nonexecutable move(B, B1) if move(B1, L).

caused on(B, L) if not gr after move(B, L).

caused blocked(B) if on(B1, B), not gr. caused moved(B) if not gr after move(B, L).

caused on(B, L) if not moved(B), not gr after on(B, L).

executable finish if on(1, 3), on(3, table), on(2, 4), on(4, table),
on(6, 5), on(5, table), not gr.

caused gr after finish. caused gr after gr. nonexecutable move(B, L) if finish.

initially : on(1, 2). on(2, table). on(3, 4). on(4, table). on(5, 6). on(6, table).

goal : gr? (7)
Figure 4: Computing the shortest plan for a Blocks World instance with a minimum number of actions P = h {move(3, table)}, {move(1, 3), move(5, table)},
{move(2, 4), move(6, 5)}, {finish}, ∅, ∅, ∅ i, which has costPγ(P**) = 39**. We can now compute the optimal cost wrt. optimization (γ) by subtracting the cost of finish and dividing by i + 1: (39 − 4) ÷ (i + 1) = 35 ÷ **7 = 5**. Thus, we need a minimum of 5 moves to reach the goal. The minimal number of steps is obviously all steps, except the final finish action, i.e. 3. Thus, we need at least 3 steps for a plan with five moves.

5.1.4 CHEAPEST AMONG THE SHORTEST PLANS (δ)
Again, we can use the rewriting for optimization (β). The cost functions have to be adapted similarly as in the previous subsection, such that now the cost of the action finish takes priority over all other actions costs. To this end, it is sufficient to set the cost of finish high enough, which is achieved by multiplying it with a factor F higher than the sum of all action costs of all legal action instances at all steps j = 1, . . . , i + 1. Let Pδ denote the resulting planning problem. We have: Proposition 5.3 The optimal plans for Pδ *are in 1-1 correspondence to the cheapest among the* shortest plans reaching Q in PD within i *steps. More precisely,* P = hA1, . . . , Aj+1, ∅**, . . . ,** ∅i