Each move is penalized with cost 1, which results in a minimization of the total number of moves.

Let Pl denote the planning problem for plan length l.

For l = 2, we have an optimal plan which involves six moves, i.e. **cost**∗P2

= 6:
P2 = h {move(1, table), move(3, table), move(5, table)}, {move(1, 3), move(2, 4), move(6, 5)} i By unfolding the steps, this plan gives rise to similar plans of length l = 3**, . . . ,** 6 that have cost 6. For l = 3, we can find among others the following optimal plan, which has cost 5:
P3 = h {move(3, table)}, {move(1, 3), move(5, table)}, {move(2, 4), move(6, 5)} i This plan can not be further parallelized to having only two steps. For any plan length l > 3, we will obtain optimal plans similar to P3, extended by void steps. Thus a plan which is cheapest over all plan lengths has cost 5 and needs three steps. Note that shortest parallel plans (of length 2) are more expensive, as explained above.

## 5.1.2 Shortest Plans (Β)

Intuitively, it should be possible to include the minimization of time steps in the cost function. We describe a preprocessing method which, given a K planning domain PD, a list Q of ground literals, and an upper bound i ≥ 0 for the plan length, generates a planning problem Pβ(**PD, Q, i**) such that the optimal plans for Pβ correspond to shortest plans which reach Q in PD in at most i steps, i.e.,
to plans for hPD, Q ? (l)i such that l ≤ i is minimal. We assume that no action costs are specified in the original planning domain PD, and minimizing time steps is our only target.

First we rewrite the planning domain PD to PDβ as follows: We introduce a new distinct fluent gr and a new distinct action finish, defined as follows:
fluents : gr. actions : finish costs time.

Intuitively, the action finish represents a final action, which we use to finish the plan. The later this action occurs, the more expensive the plan as we assign time as cost. The fluent gr ("goal reached") shall be true and remain true as soon as the goal has been reached, and it is triggered by the finish action.

This can be modeled in Kc by adding the following statements to the always section of the program:
executable finish if Q, not gr.

caused gr after finish. caused gr after gr.

Furthermore, we want finish to occur exclusively and we want to block the occurrence of any other action once the goal has been reached. Therefore, for every action A in PD, we add nonexecutable A if finish.

and add not gr to the if-part of each executability condition for A. Finally, to avoid any inconsistencies from static or dynamic effects as soon as the goal has been reached, we add not gr to the if part of any causation rule of the PD except nonexecutable rules which remain unchanged.4 We define now Pβ(PD, Q, i) = hPDβ, gr ?(i **+ 1)**i. We take i + 1 as the plan length since we need one additional step to execute the finish action.