tasks can be specified and solved. This work complements and extends the preliminary results presented in our previous work (Eiter et al., 2002a).

The remainder of this paper is organized as follows. In the next section, we briefly review the language K by informally presenting its main constituents and features on a simple planning example. After that, we define in Section 3 the extension of K by action costs, and consider some first examples for the usage of Kc. Section 4 is devoted to the analysis of complexity issues. In Section 5, we consider applications of Kc. We show that various types of particular optimization problems can be expressed in Kc, and also consider some practical examples. In Section 6, we present a transformation of Kcinto answer set programming, and in Section 7, we report about a prototype implementation and experiments. After a discussion of related work in Section 8, we conclude the paper with an outlook on ongoing and future work.

## 2. Short Review Of Language K

In this section, we give a brief informal overview of the language K, and refer to (Eiter et al., 2003b)
and to the Appendix for formal details. We assume that the reader is familiar with the basic ideas of planning and action languages, in particular with the notions of actions, fluents, goals and plans.

For illustration, we shall use the following planning problem as a running example.

Problem 1 [Bridge Crossing Problem] Four persons want to cross a river at night over a plank bridge, which can only hold up to two persons at a time. They have a lamp, which must be used when crossing. As it is pitch-dark and some planks are missing, someone must bring the lamp back to the others; no tricks (like throwing the lamp or halfway crosses, etc.) are allowed.

Fluents and states. A state in K is characterized by the truth values of fluents, describing relevant properties of the domain of discourse. A fluent may be true, false, or unknown in a state - that is, states in K are *states of knowledge*, as opposed to states of the world where each fluent is either true or false (which can be easily enforced in K, if desired). Formally, a *state* is any consistent set s of
(possibly negated) legal fluent instances.

An action is applicable only if some precondition (a list of literals over some fluents) holds in the current state. Its execution may cause a modification of truth values of some fluents.

Background knowledge. Static knowledge which is invariant over time in a K planning domain is specified in a normal (disjunction-free) Datalog program Π that has a single answer set and can be viewed as a set of facts. For our example, the background knowledge specifies the four persons:
person(joe). person(jack). person(william). person(averell).

Type declarations. Each fluent or action must have a declaration where the ranges of its arguments are specified. For instance, crossTogether(X, Y) requires person(X), person(Y), X < Y.

1 specifies the arguments of the action crossTogether, where two persons cross the bridge together, while across(X) requires person(X).