# Answer Set Planning Under Action Costs

Thomas Eiter EITER@KR.TUWIEN.AC.AT Wolfgang Faber FABER@KR.TUWIEN.AC.AT
Institut fur Informationssysteme, TU Wien ¨
Favoritenstr. 9-11, A-1040 Wien, Austria Nicola Leone LEONE@UNICAL.IT
Department of Mathematics, University of Calabria I-87030 Rende (CS), Italy Gerald Pfeifer PFEIFER@DBAI.TUWIEN.AC.AT Axel Polleres POLLERES@KR.TUWIEN.AC.AT
Institut fur Informationssysteme, TU Wien ¨
Favoritenstr. 9-11, A-1040 Wien, Austria

## Abstract

Recently, planning based on answer set programming has been proposed as an approach towards realizing declarative planning systems. In this paper, we present the language Kc, which extends the declarative planning language K by action costs. Kc provides the notion of admissible and optimal plans, which are plans whose overall action costs are within a given limit resp.

minimum over all plans (i.e., cheapest plans). As we demonstrate, this novel language allows for expressing some nontrivial planning tasks in a declarative way. Furthermore, it can be utilized for representing planning problems under other optimality criteria, such as computing "shortest" plans (with the least number of steps), and refinement combinations of cheapest and fastest plans. We study complexity aspects of the language Kcand provide a transformation to logic programs, such that planning problems are solved via answer set programming. Furthermore, we report experimental results on selected problems. Our experience is encouraging that answer set planning may be a valuable approach to expressive planning systems in which intricate planning problems can be naturally specified and solved.

## 1. Introduction

Recently, several declarative planning languages and formalisms have been introduced, which allow for an intuitive encoding of complex planning problems involving ramifications, incomplete information, non-deterministic action effects, or parallel actions (see e.g., Giunchiglia & Lifschitz, 1998; Lifschitz, 1999b; Lifschitz & Turner, 1999; McCain & Turner, 1998; Giunchiglia, 2000; Cimatti &
Roveri, 2000; Eiter et al., 2000b, 2003b).

While these systems are designed to generate any plans that accomplish the planning goals, in practice one is often interested in particular plans that are optimal with respect to some objective function by which the quality (or the cost) of a plan is measured. A common and simple objective function is the length of the plan, i.e., the number of time steps to achieve the goal. Many systems are tailored to compute shortest plans. For example, CMBP (Cimatti & Roveri, 2000) and GPT
(Bonet & Geffner, 2000) compute shortest plans in which each step consists of a single action, while the Graphplan algorithm (Blum & Furst, 1997) and descendants (Smith & Weld, 1998; Weld,