which work under all circumstances, including nondeterministic action effects. Kcis a flexible language which, by exploiting time-dependent action costs, allows for the representation of planning under various optimality criteria such as cheapest plans, shortest plans, and combinations thereof.

Our experiments have shown that various instances of the problems we considered, including realistic instances of the TSP variant, could be decently solved. On the other hand, the current version of DLVK does not scale to large problem instances in general, and, unsurprisingly, can not compete with high-end planning tools or specialized algorithms for a particular problem such as TSP. We do not see this as a shortcoming, though, since our main goal at this point was to demonstrate the usefulness of the expressive capabilities of our formalism to easily represent non-trivial planning and optimization tasks, which are especially involved from the viewpoint of knowledge representation. In this way, non-trivial instances of such problems of medium size (which one may often encounter) can be solved with little effort.

Several issues remain for further work. As for the implementation, performance improvements may be gained via improvements of the underlying DLV engine, which are subject of current work.

Furthermore, alternative, more efficient transformations of Kcto logic programming might be researched, e.g. ones that involve preprocessing of the planning problem performing means-end analysis to simplify the logic program constructed.

Another issue is further language extensions. For example, a crucial difference between our approach and resource-based approaches is that the former hinges on action costs, while the latter build on fluent values, which is a somewhat different view of the quality of a plan. A possible way to encompass this in our language is to allow that dynamic fluent values contribute to action costs; this needs to be carefully elaborated, though: While for deterministic planning under complete knowledge this extension is straightforward, in non-deterministic domains with incomplete knowledge it would possibly result in ambiguities. Different trajectories of the same plan possibly yield different costs when fluent values contribute to action costs. In favor of an intuitive definition of plan costs and optimality we refrained from this extension at the current state.

A further possible extension are negative action costs, which are useful for modeling producer/consumer relations among actions and resources. Allowing for different priorities among actions, i.e., different cost levels, would increase the flexibility and allow for optimizing different criteria at once. Finally, the duration of actions is an important issue. In the current language, the effects of actions are assumed to materialize in the next state. While by coding techniques, we may express delayed effects over several states in time and/or interleaving actions, constructs in the language would be desirable. Investigating these issues is part of our ongoing and future work.

## Acknowledgments

We are are grateful to Joohyung Lee for his help on using CCALC and to Paul Walser for his useful informations on ILPPLAN. Furthermore, we thank Michael Gelfond for interesting discussions and suggestions, and the anonymous reviewers for their detailed and helpful comments.

This work was supported by FWF (Austrian Science Funds) under the projects P14781 and Z29-N04 and the European Commission under project FET-2001-37004 WASP and IST-200133570 INFOMIX.

A preliminary, shorter version of this paper was presented at the 8th European Conference on Logics in Artificial Intelligence (JELIA'02), Cosenza, Italy, September 2002.