Anderson, & Smith, 1998) compute shortest plans where in each step actions might be executed in parallel.

However, there are other, equally important objective functions to consider. In particular, if executing actions causes some cost, we may desire a plan which minimizes the overall cost of the actions.

In answer set planning (Subrahmanian & Zaniolo, 1995; Dimopoulos, Nebel, & Koehler, 1997; Niemel¨a, 1998; Lifschitz, 1999b), a recent declarative approach to planning where plans are encoded by the answer sets of a logic program, the issue of optimal plans under an objective value function has not been addressed in detail so far (see Section 8 for more details). In this paper, we address this issue and present an extension of the planning language K (Eiter et al., 2000b, 2003b),
where the user may associate costs with actions, which are then taken into account in the planning process. The main contributions of our work are as follows.

- We define syntax and semantics of the planning language Kc, which modularly extends the language K: Costs are associated to an action by extending the action declarations with an optional cost construct which describes the cost of executing the respective action.
The action costs can be static or dynamic, as they may depend on the current stage of the plan when an action is considered for execution. Dynamic action costs are important and have natural applications, as we show on a simple variant of the well-known Traveling Salesperson Problem, which is cumbersome to model and solve in other, similar languages.

- We analyze the computational complexity of planning in the language Kc, and provide completeness results for major planning tasks in the propositional setting, which locate them in suitable slots of the Polynomial Hierarchy and in classes derived from it. These results provide insight into the intrinsic computational difficulties of the respective planning problems, and give a handle for efficient transformations from optimal planning to knowledge representation formalisms, in particular to logic programs.

- We show, in awareness of the results of the complexity analysis, how planning with action costs can be implemented by a transformation to answer set programming, as done in a system prototype that we have developed. The prototype, ready for experiments, is available at http://www.dlvsystem.com/K/.

- Finally, we present some applications which show that our extended language is capable of easily modeling optimal planning under various criteria: computing (1) "cheapest" plans (which minimize overall action costs); (2) "shortest" plans (with the least number of steps);
and, refinement combinations of these, viz. (3) shortest plans among the cheapest, and (4)
cheapest plans among the shortest. Notice that, to our knowledge, task (3) has not been addressed in other works so far.
The extension of K by action costs provides a flexible and expressive tool for representing various problems. Moreover, since K's semantics builds on states of knowledge rather than on states of the world, we can deal with both incomplete knowledge and plan quality, which is, to the best of our knowledge, completely novel.

Our experience is encouraging that answer set planning, based on powerful logic programming engines, allows for the development of declarative planning systems in which intricate planning