duction/consumption (Kautz & Walser, 1999). First, they recall that integer logic programming generalizes SAT, as a SAT formula can be translated to a system of inequalities. Second, they extend effects and preconditions of actions similar to a STRIPS extension proposed by Koehler for modeling resource consumption/production (Koehler, 1998). Kautz and Walser allow for arbitrary optimization functions but they use a non-declarative, low-level representation based on the algebraic modeling language AMPL (Fourer, Gay, & Kernighan, 1993). They mention that Koehler's STRIPS-like formalization can be mapped to their approach. However, they can not express nondeterminism or incomplete knowledge. There is an implementation of this approach called ILPPLAN, which uses the AMPL package (http://www.ampl.com/). Unfortunately, AMPL is not freely available, so we could not compare the system with our approach experimentally.

Lee and Lifschitz describe the extension C+ of the action language C which allows for an intuitive encoding of resources and costs by means of so called "additive fluents" (Lee & Lifschitz, 2001). This way admissible planning can be realized, but optimization has not been considered in that framework so far. An implementation of a planner based on this language is CCALC (McCain, 1999) which has already been described in the previous section. Another implementation of a planning system based on the action language C is Cplan (Giunchiglia, 2000; Ferraris & Giunchiglia, 2000). The Cplan system mainly focuses on conformant planning and does not support the advanced features of C+. Furthermore, the code is no longer maintained.

Son and Pontelli propose to translate action language B to prioritized default theory and answer set programming. They allow to express preferences between actions and rules at the object level in an interpreter but not as a part of the input language (Son & Pontelli, 2002). However, these preferences are orthogonal to our approach as they model qualitative preferences as opposed to our overall value function of plans/trajectories.

## 9. Conclusion And Outlook

This work continues a research stream which pursues the usage of answer set programming for building planning systems which offer declarative planning languages based on action languages, where planning tasks are specified at a high level of abstraction (Lifschitz, 1999a, 1999b). For representation of practical planning problems, such languages must have high expressiveness and provide convenient constructs and language elements.

Towards this goal, we have presented the planning language Kc, which extends the declarative planning language K (Eiter et al., 2000b, 2003a) by action costs which are taken into account for generating optimal plans, i.e., plans that have least total execution cost, and for admissible plans wrt. a given cost bound, i.e., plans whose total execution cost stays within a given limit. As a basis for implementation issues, we have investigated the computational complexity of the major planning tasks in this language, where we have derived complexity results sharply characterizing their computational cost. Furthermore, we have presented a transformation of optimal and admissible planning problems in Kcto logic programming under the optimal answer set semantics (Buccafurri et al., 1997, 2000), and we have described the DLVK prototype implemented on top of the KR tool DLV, which computes this semantics.

As we have shown, Kcallows for the representation of intricate planning problems. In particular, we have demonstrated this for a variant of the Traveling Salesperson Problem (TSP), which could be conveniently specified in Kc. A strength of Kcis that, via the underlying language K, states of knowledge, i.e., incomplete states, can be suitably respected in secure plans, i.e., conformant plans