and fluents, which might be useful for planning tasks to control the generation of answer sets resp.

plans; this may be part of further investigations.

Interestingly, CCALC finds "better quality" parallel solutions for problem (β) (cf. Table 3), i.e.

solutions with fewer moves, although it is significantly slower than our system on these instances.

For the incremental encoding of problem (γ), CCALC seems even more effective than our system.

However, CCALC offers no means of optimization; it allows for admissible but not for optimal planning. This makes our approach more flexible and general. As stated above, we could fortunately exploit the fixed cost bound in this particular example for CCALC, which is not possible in general instances of problem (γ).

Problem (γ) is also intuitively harder than simply finding a shortest plan or a cheapest among all shortest plans in general: While these problems can always be solved incrementally, for (γ) we must consider all plans of all lengths. A longer plan may be cheaper, so we cannot freeze the plan length once a (shortest) plan has been incrementally found.

## 7.2.2 Tsp

Some experimental results on TSP with variable costs are reported in Tables 5 and 6. Unlike for blocks world, no comparable systems were available; none of the systems from above supports cost optimal planning as needed for solving this problem. Here, the plan length is always given by the number of cities.

Table 5 shows the results for our TSP instance on the Austrian province capitals as in Figure 5
(nine cities, 18 connections), with and without the exceptional costs as in Section 5.2 (with and without subscript exc in the table). Further instances reported in this table with different cost exceptions
(we, lwe, rnd) are described below.

Results for some bigger TSP instances, given by the capitals of the 15 members of the European Union (EU) with varying connection graphs and exceptional costs are shown in Table 6. We have used the flight distances (km) between the cities as connection costs. Instances TSPEU1–TSPEU6 have been generated by randomly choosing a given number of connections from all possible connections between the 15 cities. Note that TSPEU1 has no solution; the time reported here is until DLVK terminated, and for all other instances until the first optimal plan was found.

We have also tested some instances of more practical relevance than simply randomly choosing connections: TSPEU7 is an instance where we have taken the flight connections of three carriers
(namely, Star Alliance, Alitalia, and Luxair), and in TSPEU8 we have included only direct connections of at most 1500km. Such a "capital hopping" is of interest for a small airplane with limited range, for instance.

For each instance in Tables 5–6 we have measured the execution time:
- without exceptional costs,
- with 50% costs for all connections on Saturdays and Sundays (weekends, we)
- with 50% costs for all connections on Fridays, Saturdays and Sundays (long weekends, lwe),

- for some random cost exceptions (rnd): We have added a number of randomly generated exceptions with costs between 0 and 10 for TSP**Austria** and between 0 and 3000 for the instances EU1 to EU8.