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* j
′ > j*, or* j
′ = j and **cost**Pj
′(P
′′) ≥
costPj
(P
′).

In our example, there are 36 possible moves. Thus, we could take F = 36 ∗ (i **+ 1)** and would set the costs of finish to time ∗ 36 ∗ (i **+ 1)**. However, we only need to take into account those actions which can actually occur simultaneously. In our example, at most six blocks can be moved in parallel. Therefore, it is sufficient to set F = 6 ∗ (i **+ 1)** and assign finish cost time ∗ F = time ∗ 42. Accordingly, the action declarations are modified as follows:
actions : move(B, L) requires block(B), location(L) costs 1.

finish costs C where C = time ∗ 42.

An optimal plan for the modified planning problem Pδ is:
P = h {move(1, table), move(3, table), move(5, table)},
{move(1, 3), move(2, 4), move(6, 5)}, {finish}, ∅, ∅, ∅, ∅i We have **cost**Pδ
(P**) = 132**. Here, we can compute the optimal cost wrt. optimization (δ) by simply subtracting the cost of finish, i.e. 132 − 3 ∗ **42 = 6**, since finish occurs at time point 3.

Consequently, we need a minimum of 6 moves for a shortest plan, which has length 3 − **1 = 2**.

And indeed, we have seen that (and how) the optimization problems (α) through (δ) can be represented in Kc. We remark that the transformations Pβ, Pγ, and Pδ all work under the restrictions to secure and/or sequential plans as well.

## 5.2 Traveling Salesperson

As another illustrating example for optimal cost planning, we will now introduce some elaboration of the Traveling Salesperson Problem.

Traveling Salesperson Problem (TSP). We start with the classical Traveling Salesperson Problem (TSP), where we have a given set of cities and connections (e.g., roads, airways) of certain costs.

We want to know a most economical round trip which visits all cities exactly once and returns to the starting point (if such a tour exists). Figure 5 shows an instance representing the capitals of all Austrian provinces. The dashed line is a flight connection, while all other connections are roads; each connection is marked with the costs in traveling hours.

brg ... Bregenz eis ... Eisenstadt gra ... Graz ibk ... Innsbruck kla ... Klagenfurt lin ... Linz sbg ... Salzburg stp ... St. Pölten vie ... Vienna

![0_image_0.png](0_image_0.png)

