TSP - Results Instance TSPEU8 shows the limits of our system: the given data allows for many possible tours, so finding an optimal one gets very tricky. On the other hand, a realistic instance like TSPEU7 with real airline connections is solved rather quickly, which is not very surprising: Most airlines have a central airport (for instance Vienna for Austrian Airlines) and few direct connections between the destinations served. This allows for much fewer candidate answer sets, when (as in reality) the number of airlines we consider is limited. E.g., TSPEU7 has no solution at all if only two out of Star Alliance, Alitalia, and Luxair are allowed. Of course, we cannot compete with dedicated TSP solvers/algorithms, which are able to solve much bigger TSP instances and have not been considered here. However, to our knowledge, none of these solvers can deal with features such as incomplete knowledge, defaults, time dependent exceptional costs, etc. directly. Our results even show that execution times are stable yet in case of many exceptions. In contrast, instance TSPEU8 shows that exceptions can also cause a significant speedup. This is due to the heuristics used by the underlying DLV system, which can single out better solutions faster if costs are not spread evenly like in TSPEU8 without exceptional costs.

Note that, we have also experimented with the alternative Smodels translation sketched in Section 6.3. We refrain from detailed discussion here, since the (i) translation is optimized for DLV and Smodels performance was worse (around factor 10 for the tested TSP instances) than DLV and (ii)
there is no integrated planning frontend available for Smodels providing a high-level planning language. Nevertheless, we have shown that our approach can, with minor modifications, be adopted in a planning system based on Smodels.

## 8. Related Work

In the last years, it has been widely recognized that plan length alone is only one criterion to be optimized in planning. Several attempts have been made to extend planners to also consider action costs.

The PYRRHUS system (Williams & Hanks, 1994) is an extension of UCPOP planning which allows for optimal planning with resources and durations. Domain-dependent knowledge can be added to direct the heuristic search. A "utility model" has to be defined for a planning problem which can be used to express an optimization function. This system supports a language extension of ADL (Pednault, 1989), which is a predecessor of PDDL (Ghallab et al., 1998). The algorithm is a synthesis of branch-and-bound optimization with a least-commitment, plan-space planner.

Other approaches based on heuristic search include the use of an A* strategy together with action costs in the heuristics (Ephrati, Pollack, & Mihlstein, 1996) and work by Refanidis and Vlahavas who use multi-criteria heuristics to obtain near-optimal plans, considering multiple criteria apart from plan length alone (Refanidis & Vlahavas, 2001). However, the described heuristics is not fully admissible, and only guarantees optimal plans under certain restrictions (Haslum & Geffner, 2000). In fact, most heuristic state-space planners are not able to guarantee optimality.

A powerful approach has been suggested by Nareyek, who describes planning with resources as a structural constraint satisfaction problem (SCSP), and then solves that problem by local search combined with global control. However, this work promotes the inclusion of domain-dependent knowledge; the general problem has an unlimited search space, and no declarative high-level language is provided (Nareyek, 2001).

Among other related approaches, Kautz and Walser generalize the "Planning as Satisfiability" approach to use integer optimization techniques for encoding optimal planning under resource pro-