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 Kc and 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.

---

Extracted Text

Journal of Artificial Intelligence Research 19 (2003) 25-71 Submitted 10/02;
published 08/03

Answer Set Planning Under Action Costs Thomas Eiter EITER@KR.TUWIEN.AC.ATWolfgang
Faber

FABER@KR.TUWIEN.AC.AT Institut f"ur Informationssysteme, TU WienFavoritenstr.
9-11, A-1040 Wien, Austria

Nicola Leone LEONE@UNICAL.IT Department of Mathematics, University of CalabriaI-87030
Rende (CS), Italy

Gerald Pfeifer PFEIFER@DBAI.TUWIEN.AC.ATAxel Polleres

POLLERES@KR.TUWIEN.AC.AT Institut f"ur Informationssysteme, TU Wien Favoritenstr.
9-11, A-1040 Wien, Austria

Abstract Recently, planning based on answer set programming has been proposed
as an approach to-wards realizing declarative planning systems. In this paper,
we present the language K

c, which

extends the declarative planning language K by action costs. Kc provides
the notion of admissi-ble 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 forexpressing 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 Kc and provide a transformation
to logic programs, suchthat planning problems are solved via answer set programming.
Furthermore, we report experimental results on selected problems. Our experience
is encouraging that answer set planning maybe 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,

cfl2003 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

EITER, FABER, LEONE, PFEIFER & POLLERES 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

26

ANSWER SET PLANNING UNDER ACTION COSTS 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 Kc
into 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
Pi  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).

1. "<" here is used instead of inequality to avoid symmetric rules.

27

EITER, FABER, LEONE, PFEIFER & POLLERES specifies a fluent describing that
a specific person is on the other side of the river. Here the literals after
"requires" must be classical literals of the static background knowledge
(like person(X) and person(Y)), or literals of built-in predicates (such
as X < Y). Our implementation of K, the DLVKsystem (Eiter, Faber, Leone,
Pfeifer, & Polleres, 2003a), currently supports the built-in predicates "A
< B", "A <= B", "A != B" with the obvious meaning of less-than, less-or-equal
and inequality for strings and numbers, the arithmetic built-ins "A = B +
C" and "A = B * C" which stand for integer addition and multiplication, and
the predicate "#int(X)" which enumerates all integers (up to a user-defined
limit).

Causation rules. Causation rules ("rules" for brevity) are syntactically
similar to rules of the action language C (Giunchiglia & Lifschitz, 1998;
Lifschitz, 1999a; Lifschitz & Turner, 1999) and are of the basic form:

caused f if B after A. where A is a conjunction of fluent and action literals,
possibly including default negation, B is a conjunction of fluent literals,
again possibly including default negation, and f is a fluent literal. Informally,
such a rule reads: if B is known to be true in the current state and A is
known to be true in the previous state, then f is known to be true in the
current state as well. Both the if-part and the after-part are allowed to
be empty (which means that they are true). A causation rule is called dynamic,
if its after-part is not empty, and is called static otherwise.

Causation rules are used to express effects of actions or ramifications.
For example,

caused across(X) after cross(X), -across(X). caused -across(X) after cross(X),
across(X).

describe the effects of a single person crossing the bridge in either direction.

Initial state constraints. Static rules can apply to all states or only to
the initial states (which may not be unique). This is expressed by the keywords
"always :" and "initially :" preceding sequences of rules where the latter
describes initial state constraints that must be satisfied only in the initial
state. For example,

initially : caused -across(X).

enforces the fluent across to be false in the initial state for any X satisfying
the declaration of the fluent across, i.e., for all persons. The rule is
irrelevant for all subsequent states.

Executability of actions. This is expressed in K explicitly. For instance,

executable crossTogether(X, Y) if hasLamp(X). executable crossTogether(X,
Y) if hasLamp(Y).

declares that two persons can jointly cross the bridge if one of them has
a lamp. The same action may have multiple executability statements. A statement

executable cross(X). with empty body says that cross is always executable,
provided that the type restrictions on X are respected. Dually,

nonexecutable a if B. prohibits the execution of action a if condition B
is satisfied. For example,

nonexecutable crossTogether(X, Y) if differentSides(X, Y).

28

ANSWER SET PLANNING UNDER ACTION COSTS says that persons X and Y can not
cross the bridge together if they are on different sides of the bridge. In
case of conflicts, nonexecutable A overrides executable A.

Default and strong negation. K supports strong negation ("~," also written
as "-"). Note, however, that for a fluent f, in a state neither f nor -f
needs to hold. In this case the knowledge about f is incomplete. In addition,
weak negation ("not"), interpreted like default negation in answer set semantics
(Gelfond & Lifschitz, 1991), is permitted in rule bodies. This allows for
natural modeling of inertia and default properties, as well as dealing with
incomplete knowledge in general. For example,

caused hasLamp(joe) if not hasLamp(jack), not hasLamp(william), not hasLamp(averell).
expresses the conclusion that by default, joe has the lamp, whenever it is
not evident that any of the other persons has it.

Macros. K provides a number of macros as "syntactic sugar". For example,

inertial across(X). informally states that across(X) holds in the current
state, if across(X) held at the previous state, unless -across(X) is explicitly
known to hold. This macro expands to the rule

caused across(X) if not -across(X) after across(X). Moreover, we can "totalize"
the knowledge of a fluent by declaring total f. which is a shortcut for

caused f if not -f. caused -f if not f. The intuitive meaning of these rules
is that unless a truth value for f can be derived, the cases where f resp.
-f is true will both be considered.

Planning domains and problems. In K, a planning domain PD = hPi , hD, Rii
has a background knowledge Pi , action and fluent declarations D, and rules
and executability conditions R; a planning problem P = hPD, qi has a planning
domain PD and a query

q = g1, . . . , gm, not gm+1, . . . , not gn ? (l) where g1, . . . , gn are
ground fluents and l >= 0 is the plan length. For instance, the goal query

across(joe), across(jack), across(william), across(averell)? (5) asks for
plans which bring all four persons across in 5 steps.

Plans are defined using a transition-based semantics, where the execution
of a set of actions transforms a current state into a new state. An (optimistic)
plan for P is a sequence P = hA1, . . . , Ali of sets of action instances
A1, A2, . . . , Al in a trajectory T = hhs0, A1, s1i, hs1, A2, s2i, . . .
,h

sl-1, Al, slii from a legal initial state s0 to state sl in which all literals
of the goal are true. That is, starting in s0, the legal transition t1 =
hs0, A1, s1i, modeling the execution of the actions in A1 (which must be
executable), transforms s0 into the state s1. This is then followed by legal
transitions ti = hsi-1, Ai, sii, for i = 2, 3, . . . , l (cf. Appendix for
details). A plan is sequential, if |Ai| <= 1 for all i = 1, . . . , l, i.e.,
each step consists of at most one action; such plans can be enforced by including
the keyword noConcurrency.

Besides optimistic plans, in K we also support stronger secure (or conformant)
plans. A secure plan must be guaranteed to work out under all circumstances
(Eiter et al., 2000b), regardless of incomplete information about the initial
state and possible nondeterminism in the action effects.

29

EITER, FABER, LEONE, PFEIFER & POLLERES For better readability, in the following
we will not always describe K planning problems P strictly in terms of sets
of declarations, rules and executability conditions, but optionally use the
more compact representation of K programs of the following general form:

fluents : FD actions : AD initially : IR always : CR goal : q

where the (optional) sections fluents through always consist of lists of
fluent declarations FD, action declarations AD, initial state constraints
IR and executability conditions and causation rules CR, respectively. Together
with the background knowledge Pi  and the goal query q, they specify a K
planning problem P = hhPi , hD, Rii, qi, where D is given by FD plus AD
and R by IR plus CR. 2

2.1 Solving the Bridge Crossing Problem Using the above constructs, a K encoding
of the Bridge Crossing Problem, assuming that joeinitially carries the lamp,
is shown in Figure 1. There are simple five-step plans (

l = 5), in which joe always carries the lamp and brings all others across.
One of them is:

P = h {crossTogether(joe, jack)}, {cross(joe)}, {crossTogether(joe, william)},{

cross(joe)}, {crossTogether(joe, averell)} i

3. Actions with Costs Using the language K and the system prototype, DLVK,
we can already express and solve some involved planning tasks, cf. (Eiter
et al., 2003b). However, K and DLVK alone offer no means for finding optimal
plans under an objective cost function. In general, different criteria of
plan optimality can be relevant, such as optimality wrt. action costs as
shown in the next example, which is a slight elaboration of the Bridge Crossing
Problem, and a well-known brain teasing riddle:

Problem 2 [Quick Bridge Crossing Problem] The persons in the bridge crossing
scenario need different times to cross the bridge, namely 1, 2, 5, and 10
minutes, respectively. Walking in two implies moving at the slower rate of
both. Is it possible that all four persons get across within 17 minutes?

On first thought this is infeasible, since the seemingly optimal plan where
joe, who is the fastest, keeps the lamp and leads all the others across takes
19 minutes altogether. Surprisingly, as we will see, the optimal solution
indeed only takes 17 minutes.

In order to allow for an elegant and convenient encoding of such optimization
problems, we extend K to the language Kc in which one can assign costs to
actions.

3.1 Syntax of Kc Let oeact, oefl, and oevar denote (finite) sets of action
names, fluent names and variable symbols. Furthermore, let Lact, Lfl, and
Ltyp denote the sets of action, fluent, and type literals, respectively,

2. This is also the format of the input files of our system prototype, which
will be presented in Section 7.

30

ANSWER SET PLANNING UNDER ACTION COSTS actions : cross(X) requires person(X).

crossTogether(X, Y) requires person(X), person(Y), X < Y. takeLamp(X) requires
person(X).

fluents : across(X) requires person(X).

differentSides(X, Y) requires person(X), person(Y). hasLamp(X) requires person(X).

initially : -across(X). hasLamp(joe). always : executable crossTogether(X,
Y) if hasLamp(X).

executable crossTogether(X, Y) if hasLamp(Y). nonexecutable crossTogether(X,
Y) if differentSides(X, Y).

executable cross(X) if hasLamp(X). executable takeLamp(X). nonexecutable
takeLamp(X) if hasLamp(Y), differentSides(X, Y).

caused across(X) after crossTogether(X, Y), -across(X). caused across(Y)
after crossTogether(X, Y), -across(Y). caused -across(X) after crossTogether(X,
Y), across(X). caused -across(Y) after crossTogether(X, Y), across(Y).

caused across(X) after cross(X), -across(X). caused -across(X) after cross(X),
across(X).

caused hasLamp(X) after takeLamp(X). caused -hasLamp(X) after takeLamp(Y),
X != Y, hasLamp(X).

caused differentSides(X, Y) if across(X), -across(Y). caused differentSides(X,
Y) if -across(X), across(Y).

inertial across(X). inertial -across(X). inertial hasLamp(X).

noConcurrency. goal : across(joe), across(jack), across(william), across(averell)?
(l)

Figure 1: K encoding of the Bridge Crossing Problem

formed from the action names, fluent names, and predicates in the background
knowledge (including built-in predicates), respectively, using terms from
a nonempty (finite) set of constants oecon.K

c extends action declarations as in K with costs as follows.

Definition 3.1 An action declaration d in Kc is of the form:

p(X1, . . . , Xn) requires t1, . . . , tm costs C where c1, . . . , ck. (1)
where (1) p 2 oeact has arity n >= 0, (2) X1, . . . , Xn 2 oevar, (3) t1,
. . . , tm, c1, . . . , ck are fromL

typ such that every Xi occurs in t1, . . . , tm, (4) C is either an integer
constant, a variable from theset of all variables occurring in

t1, . . . , tm, c1, . . . , ck (denoted by oevar(d)), or the distinguished

variable time, (5) oevar(d) ` oevar [ {time}, and (6) time does not occur
in t1, . . . tm.

31

EITER, FABER, LEONE, PFEIFER & POLLERES If m = 0, the keyword `requires'
is omitted; if k = 0, the keyword `where' is omitted and `costs C' is optional.
Here, (1) and (2) state that parameters to an action must be variables, and
not fixed values. Informally, (3) means that all parameters of an action
must be "typed" in the requires part. Condition (4) asserts that the cost
is locally defined or given by the stage of the plan, which is referenced
through the global variable time. Conditions (5) and (6) ensure that all
variables are known and that type information of action parameters is static,
i.e., does not depend on time.

Planning domains and planning problems in Kc are defined as in K.

For example, in the elaborated Bridge Crossing Problem, the declaration of
cross(X) can be extended as follows: suppose a predicate walk(Person, Minutes)
in the background knowledge indicates that Person takes Minutes to cross.
Then, we may simply declare

cross(X) requires person(X) costs WX where walk(X, WX).

3.2 Semantics of Kc Semantically, Kc extends K by the cost values of actions
at points in time. In any plan P =h

A1, . . . , Ali, at step 1 <= i <= l, the actions in Ai are executed to reach
time point i.

A ground action p(x1, . . . , xn) is a legal action instance of an action
declaration d wrt. a Kc planning domain PD = hPi , hD, Rii, if there exists
some ground substitution ` for oevar(d) [{

time} such that Xi` = xi, for 1 <= i <= n and {t1`, . . . , tm`} ` M , where
M is the unique answer set of the background knowledge Pi . Any such ` is
called a witness substitution for p(x1, . . . , xn). Informally, an action
instance is legal, if it satisfies the respective typing requirements. Action
costs are now formalized as follows.

Definition 3.2 Let a = p(x1, . . . , xn) be a legal action instance of a
declaration d of the form (1) and let ` be a witness substitution for a.
Then

cost`(p(x1, . . . , xn)) = 8!:

0, if the costs part of d is empty; val(C`), if {c1`, . . . , ck`} ` M ;
undefined otherwise.

where M is the unique answer set of Pi  and val : oecon ! IN is defined
as the integer value for integer constants and 0 for all non-integer constants.

By reference to the variable time, it is possible to define time-dependent
action costs; we shall consider an example in Section 5.2. Using cost`, we
now introduce well-defined legal action instances and define action cost
values as follows.

Definition 3.3 A legal action instance a = p(x1, . . . , xn) is well-defined
iff it holds that (i) for any time point i >= 1, there is some witness substitution
` for a such that time = i and cost`(a) is an integer, and (ii) cost`(a)
= cost`0(a) holds for any two witness substitutions `, `0 which coincide
on time and have defined costs. For any well-defined a, its unique cost at
time point i >= 1 is given by costi(a) = cost`(a) where ` is as in (i).

In this definition, condition (i) ensures that some cost value exists, which
must be an integer, and condition (ii) ensures that this value is unique,
i.e., any two different witness substitutions ` and `0 for a evaluate the
cost part to the same integer cost value.

32

ANSWER SET PLANNING UNDER ACTION COSTS An action declaration d is well-defined,
if all its legal instances are well-defined. This will be fulfilled if, in
database terms, the variables X1, . . . , Xn together with time in (1) functionally
determine the value of C. In our framework, the semantics of a Kc planning
domain PD = hPi , hD, Rii is only well-defined for well-defined action declarations
in PD. In the rest of this paper, we assume well-definedness of Kc unless
stated otherwise.

Using costi, we now define costs of plans.

Definition 3.4 Let P = hPD, Q ? (l)i be a planning problem. Then, for any
plan P = hA1, . . . , Ali for P, its cost is defined as

costP (P ) = Plj=1 iPa2Aj costj(a)j . A plan P is optimal for P, if costP(P
) <= costP(P 0) for each plan P 0 for P, i.e., P has least cost among all
plans for P. The cost of a planning problem P, denoted cost*P , is given
by cost*P = costP(P *), where P * is an optimal plan for P.

In particular, costP(P ) = 0 if P = hi, i.e., the plan is void. Note that
cost*P is only defined if a plan for P exists.3

Usually one only can estimate some upper bound of the plan length, but does
not know the exact length of an optimal plan. Although we have only defined
optimality for a fixed plan length l, we will see in Section 5.1 that by
appropriate encodings this can be extended to optimality for plans with length
at most l.

Besides optimal plans, also plans with bounded costs are of interest, which
motivates the following definition.

Definition 3.5 A plan P for a planning problem P is admissible wrt. cost
c, if costP(P ) <= c.

Admissible plans impose a weaker condition on the plan quality than optimal
plans. They are particularly relevant if optimal costs are not a crucial
issue, as long as the cost stays within a given limit, and if optimal plans
are difficult to compute. We might face questions like "Can I make it to
the airport within one hour?", "Do I have enough change to buy a coffee?"
etc. which amount to admissible planning problems. As we shall see, computing
admissible plans is complexity-wise easier than computing optimal plans.

3.3 An Optimal Solution for the Quick Bridge Crossing Problem To model the
Quick Bridge Crossing Problem in Kc, we first extend the background knowledge
as follows, where the predicate `walk' describes the time a person needs
to cross and `max' determines which of two persons is slower:

walk(joe, 1). walk(jack, 2). walk(william, 5). walk(averell, 10). max(A,
B, A) :- walk( , A), walk( , B), A >= B. max(A, B, B) :- walk( , A), walk(
, B), B > A.

Next, we modify the declarations for cross and crossTogether from Figure
1 by adding costs:

3. In the following, subscripts will be dropped when clear from the context.

33

EITER, FABER, LEONE, PFEIFER & POLLERES cross(X) requires person(X) costs
WX where walk(X, WX). crossTogether(X, Y) requires person(X), person(Y),
X < Y

costs Wmax where walk(X, WX), walk(Y, WY), max(WX, WY, Wmax).

The declaration of takeLamp remains unchanged, as the time to hand over the
lamp is negligible.Using this modified planning domain, the 5-step plan reported
in Section 2.1 has cost 19. Actually, it is optimal for plan length l = 5.
However, when we relinquish the first intuition that thefastest person,

joe, always has the lamp and consider the problem under varying plan length,
thenwe can find the following 7-step plan:

P = h {crossTogether(joe, jack)}, {cross(joe)}, {takeLamp(william)},{

crossTogether(william, averell)}, {takeLamp(jack)}, {cross(jack)},{ crossTogether(joe,
jack)} i

Here, costP (P ) = 17, and thus P is admissible with respect to cost 17.
This means that the Quick Bridge Crossing Problem has a positive answer.
In fact, P has least cost over all plans of length l = 7, and is thus an
optimal 7-step plan. Moreover, P has also least cost over all plans that
emerge if we consider all plan lengths. Thus, P is an optimal solution for
the Quick Bridge Crossing Problem under arbitrary plan length.

3.4 Bridge Crossing under Incomplete Knowledge The language K is well-suited
to model problems which involve uncertainty such as incomplete initial states
or non-deterministic action effects at a qualitative level. The enriched
language Kc gracefully extends to secure (conformant) plans as well, which
must reach the goal under all circumstances (Eiter et al., 2000b, 2003b).
More precisely, an optimistic plan hA1, . . . , Ani is secure, if it is applicable
under any evolution of the system: starting from any legal initial state
s0, the first action set A1 (for plan length l >= 1) can always be executed
(i.e., some legal transition hs0, A1, s1i exists), and for every such possible
state s1, the next action set A2 can be executed etc., and after having performed
all actions, the goal is always accomplished (cf. Appendix for a formal definition).

While secure plans inherit costs from optimistic plans, there are different
possibilities to define optimality of secure plans. We may consider a secure
plan as optimal, if it has least cost either

* among all optimistic plans, or*

among all secure plans only.

In the first alternative, there might be planning problems which have secure
plans, but no optimal secure plans. For this reason, the second alternative
appears to be more appropriate.

Definition 3.6 A secure plan P is optimal for a planning problem P, if it
has least cost among all secure plans for P, i.e., costP(P ) <= costP (P
0) for each secure plan P 0 for P. The secure cost ofP

, denoted cost*sec(P), is cost*sec(P) = costP (P *), where P * is any optimal
secure plan for P.

The notion of admissible secure plans is defined analogously.

For example, assume that it is known that at least one person in the bridge
scenario has a lamp, but that neither the exact number of lamps nor the allocation
of lamps to persons is known. If the four desperate persons now ask for a
plan which brings them safely across the bridge, we need a (fast) secure
plan that works under all possible initial situations. In Kc, this can be
modeled by replacing the initially-part with the following declarations:

34

ANSWER SET PLANNING UNDER ACTION COSTS initially : total hasLamp(X).

caused false if -hasLamp(joe), -hasLamp(jack),-

hasLamp(william), -hasLamp(averell).

The first statement says that each person either has a lamp or not, and the
second that at least one of them must have a lamp. For a detailed discussion
on the use of the "total" statement for modeling incomplete knowledge and
non-determinism we refer to (Eiter et al., 2003b).

As we can easily see, an optimal secure solution will take at least 17 minutes,
since the original case (where only joe has a lamp) is one of the possible
initial situations, for which the cost of an optimistic plan which is optimal
over all plan lengths was 17. However, a secure plan which is optimal over
all plan lengths requires at least 8 steps now (but no higher cost): Different
from optimistic plans, we need one extra step at the beginning which makes
sure that one of those who walk first (above, joe and jack) has the lamp,
which is effected by the proper takeLamp action.

An example of such a plan is the following which has cost 17:

P = h {takeLamp(joe)}, {crossTogether(joe, jack)}, {cross(joe)},{

takeLamp(william)}, {crossTogether(william, averell)}, {takeLamp(jack)},{
cross(jack)}, {crossTogether(joe, jack)} i

We can easily check that P works for every possible initial situation. Thus,
it is an optimal (secure) plan for plan length 8, and moreover also for arbitrary
plan length.

4. Computational Complexity In this section, we will address the computational
complexity of Kc, complementing similar results for the language K (Eiter
et al., 2003b).

4.1 Complexity Classes We assume that the reader is familiar with the basic
notions of complexity theory, such as P, NP, problem reductions and completeness;
see e.g. (Papadimitriou, 1994) and references therein. We recall that the
Polynomial Hierarchy (PH) contains the classes Sigma P0 = Pi P0 = Delta
P0 = P and Sigma Pi+1 =

NPSigma 

Pi , Pi P

i+1 = co-Sigma Pi+1, Delta Pi+1 = PSigma 

Pi , for i >= 0. In particular, Sigma P

1 = NP and Delta P2 = PNP.Note that these classes contain decision problems
(i.e., problems where the answer is "yes" or

"no"). While checking well-definedness and deciding plan existence are such
problems, computing a plan is a search problem, where for each problem instance
I a (possibly empty) finite set S(I) of solutions exists. To solve such a
problem, a (possibly nondeterministic) algorithm must compute the alternative
solutions from this set in its computation branches, if S(I) is not empty.
More precisely, search problems are solved by transducers, i.e., Turing machines
equipped with an output tape. If the machine halts in an accepting state,
then the contents of the output tape is the result of the computation. Observe
that a nondeterministic machine computes a (partial) multi-valued function.

As an analog to NP, the class NPMV contains those search problems where S(I)
can be computed by a nondeterministic Turing machine in polynomial time;
for a precise definition, see (Selman, 1994). In analogy to Sigma Pi+1,
by Sigma Pi+1MV = NPMVSigma 

Pi , i >= 0, we denote the generalization of

NPMV where the machine has access to a Sigma Pi oracle.

Analogs to the classes P and Delta Pi+1, i >= 0, are given by the classes
FP and FDelta Pi+1, i >= 0, which contain the partial single-valued functions
(that is, |S(I)| <= 1 for each problem instance

35

EITER, FABER, LEONE, PFEIFER & POLLERES I) computable in polynomial time
using no resp. a Sigma Pi oracle. We say, abusing terminology, that a search
problem A is in FP (resp. FDelta Pi+1), if there is a partial (single-valued)
function f 2 FP (resp. f 2 FDelta Pi+1) such that f (I) 2 S(I) and f (I)
is undefined iff S(I) = ;. For example, computing a satisfying assignment
for a propositional CNF (FSAT) and computing an optimal tour in the Traveling
Salesperson Problem (TSP) are in FDelta P2 under this view, cf. (Papadimitriou,
1994).

A partial function f is polynomial-time reducible to another partial function
g, if there are polynomial-time computable functions h1 and h2 such that
f (I) = h2(I, g(h1(I))) for all I and g(h1(I)) is defined whenever f (I)
is defined. Hardness and completeness are defined as usual.

4.2 Problem Setting We will focus on the following questions:

Checking Well-Definedness: Decide whether a given action description is well-defined
wrt. a

given planning domain PD, resp. whether a given planning domain PD is well-defined.

Admissible Planning: Decide whether for planning problem P an admissible
(optimistic/secure)

plan exists wrt. a given cost value c, and find such a plan.

Optimal Planning: Find an optimal (optimistic/secure) plan for a given planning
problem.

Notice that (Eiter et al., 2003b) focused on deciding the existence of optimistic/secure
plans, rather than on actually finding plans, and presented a detailed study
of the complexity of this task under various restrictions for ground (propositional)
planning problems. In this paper, we confine the discussion to the case of
planning problems P = hPD, Q ? (l)i which look for polynomial length plans,
i.e., problems where the plan length l is bounded by some polynomial in the
size of the input.

We shall consider here mainly ground (propositional) planning, and assume
that the planning domains are well-typed and that the unique model of the
background knowledge can be computed in polynomial time. In the general case,
by well-known complexity results on logic programming, cf. (Dantsin, Eiter,
Gottlob, & Voronkov, 2001), already evaluating the background knowledge is
EXPTIME-hard, and the problems are thus provably intractable. We recall the
following results, which appear in (or directly follow from) previous work
(Eiter et al., 2003b).

Proposition 4.1 Deciding, given a propositional planning problem P and a
sequence P = hA1, . . . , Ali of action sets, (i) whether a given sequence
T = ht1, . . . , tli is a legal trajectory witnessing that P is an optimistic
plan for P is feasible in polynomial time, and (ii) whether P is a secure
plan forP

is Pi P2 -complete.

4.3 Results We start by considering checking well-definedness. For this problem,
it is interesting to investigate the non-ground case, assuming that the background
knowledge is already evaluated. This way we can assess the intrinsic difficulty
of this task obtaining the following result.

Theorem 4.2 (Complexity of checking well-definedness) Given a Kc planning
domain PD =h

Pi , hD, Rii and the unique model M of Pi , checking (i) well-definedness
of a given action declaration d of form (1) wrt. PD and (ii) well-definedness
of PD are both Pi P2 -complete.

36

ANSWER SET PLANNING UNDER ACTION COSTS Proof. Membership: As for (i), d is
violated if it has a nonempty costs part and a legal action instance a =
p(x1, . . . , xn) such that either (1) there exist witness substitutions
` and `0 for a such that time` = time`0, cost`(a) = val(C`) and cost`0(a)
= val(C`0), and val(C`) 6= val(C`0), or (2) there is no witness substitution
` for a such that cost`(a) = val(C`) is an integer. Such an a can be guessed
and checked, via a witness substitution, in polynomial time, and along with
a also ` and `0 as in (1); note that, by definition, all variables must be
substituted by constants from the background knowledge (including numbers),
and so must be values for time if it occurs in c1, . . . , ck. Given a, we
can decide (2) with the help of an NP oracle. In summary, disproving welldefinedness
of d is nondeterministically possible in polynomial time with an NP oracle.
Hence, checking well-definedness of d is in co-Sigma P2 = Pi P2 . The membership
part of (ii) follows from (i), since well-definedness of PD reduces to well-definedness
of all action declarations in it, and Pi P2 is closed under conjunctions.
Hardness: We show hardness for (i) by a reduction from deciding whether a
quantified Boolean formula (QBF)

Q = 8X9Y.c1 ^ * * * ^ ck

where each ci = Li,1 . * * * . Li,`i, i = 1, . . . , k, is a disjunction
of literals Li,j on the atoms X = x1, . . . , xn and Y = xn+1 . . . , xm,
is true. Without loss of generality, we may assume that each ci contains
three (not necessarily distinct) literals, which are either all positive
or all negative.

We construct a planning domain PD and d as follows. The background knowledge,
Pi , is

bool(0). bool(1). pos(1, 0, 0). pos(0, 1, 0). pos(0, 0, 1). pos(1, 1, 0).
pos(1, 0, 1). pos(0, 1, 1). pos(1, 1, 1). neg(0, 0, 0). neg(1, 0, 0). neg(0,
1, 0). neg(0, 0, 1). neg(1, 1, 0). neg(1, 0, 1). neg(0, 1, 1).

Here, bool declares the truth values 0 and 1. The facts pos(X1, X2, X3) and
neg(X1, X2, X3) state those truth assignments to X1, X2, and X3 such that
the positive clause X1 . X2 . X3 resp. the negative clause ~X1 . ~X2 . ~X3
is satisfied.

The rest of the planning domain PD consists of the single action declaration
d of form

p(V1, ..., Vn) requires bool(V1), ..., bool(Vn) costs 0 where c*1, ..., c*k.
where

c*i = ae pos(Vi,1, Vi,2, Vi,3), if ci = xi,1 . xi,2 . xi,3,neg(V

i,1, Vi,2, Vi,3), if ci = ~xi,1 . ~xi,2 . ~xi,3, i = 1, . . . , k.

For example, the clause c = x1 . x3 . x6 is mapped to c* = pos(V1, V3, V6).
It is easy to see that each legal action instance a = p(b1, . . . , bn) of
d corresponds 1-1 to the truth assignment oea of X given by oea(xi) = bi,
for i = 1, . . . , n. Furthermore, a has a cost value defined (which is 0)
iff the formula 9Y (c1oea ^ * * * ^ ckoea) is true. Thus, d is well-defined
wrt. PD iff Q is true. Since PD and d are efficiently constructible, this
proves Pi P2 -hardness. 2

Observe that in the ground case, checking well-definedness is much easier.
Since no substitutions need to be guessed, the test in the proof of Theorem
4.2 is polynomial. Thus, by our assumption on the efficient evaluation of
the background program, we obtain:

Corollary 4.3 In the ground (propositional) case, checking well-definedness
of an action description d wrt. a Kc planning domain PD = hPi , hD, Rii,
resp. of PD as a whole, is possible in polynomial time.

37

EITER, FABER, LEONE, PFEIFER & POLLERES We remark that checking well-definedness
can be expressed as a planning task in K, and also by a logic program; we
refer to (Eiter, Faber, Leone, Pfeifer, & Polleres, 2002b) for details.

We now turn to computing admissible plans.

Theorem 4.4 (Complexity of admissible planning) For polynomial plan lengths,
deciding whether a given (well-defined) propositional planning problem hPD,
qi has (i) some optimistic admissible plan wrt. to a given integer b is NP-complete,
and finding such a plan is complete for NPMV, (ii) deciding whether hPD,
qi has some secure admissible plan wrt. to a given integer b is Sigma P3
-complete, and computing such a plan is Sigma P3 MV-complete. Hardness holds
in both cases for fixed plan length.

As for the proof we refer to the Appendix. We finally address the complexity
of computing optimal plans.

Theorem 4.5 (Complexity of optimal planning) For polynomial plan lengths,
(i) computing an optimal optimistic plan for hPD, Q ? (l)i in Kc is FDelta
P2 -complete, and (ii) computing an optimal secure plan for hPD, Q ? (l)i
in Kc is FDelta P4 -complete. Hardness holds in both cases even if the plan
length l is fixed.

The proof again can be found in the in the Appendix. We remark that in the
case of unbounded plan length, the complexity of computing plans increases
and requires (at least) exponential time in general, since plans might have
exponential length in the size of the planning problem. Thus, in practical
terms, constructing such plans is infeasible, since they occupy exponential
space. Furthermore, as follows from previous results (Eiter et al., 2003b),
deciding the existence of an admissible optimistic resp. secure plan for
a planning problem wrt. a given cost is PSPACE-complete resp. NEXPTIME-complete.
We leave a more detailed analysis of complexity aspects of Kc for further
work.

5. Applications 5.1 Cost Efficient versus Time Efficient Plans In this section,
we show how the language Kc can be used to minimize plan length in combination
with minimizing the costs of a plan. This is especially interesting in problem
settings where parallel actions are allowed (cf. (Kautz & Walser, 1999; Lee
& Lifschitz, 2001)).

For such domains with parallel actions, Kautz and Walser propose various
criteria to be optimized, for instance the number of actions needed, or the
number of necessary time steps when parallel actions are allowed, as well
as combinations of these two criteria (1999). By exploiting action costs
and proper modeling, we can solve optimization problems of this sort. For
example, we can single out plans with a minimal number of actions simply
by assigning cost 1 to all possible actions.

We consider the following optimization problems:

(ff) Find a plan with minimal cost (cheapest plan) for a given number of
steps.

(fi) Find a plan with minimal time steps (shortest plan).

(fl) Find a shortest among the cheapest plans.

38

ANSWER SET PLANNING UNDER ACTION COSTS (ffi) Find a cheapest among the shortest
plans.

Problem (ff) is what we have already defined as optimal plans so far. We
will now show how to express (fi) in terms of optimal cost plans as well,
and how to extend this elaboration with respect to the combinations (fl)
and (ffi).

5.1.1 CHEAPEST PLANS WITH GIVEN PLAN LENGTH (ff) As a guiding example, we
refer to Blocks World with parallel moves allowed, where apart from finding
shortest plans also minimizing the total number of moves is an issue. A Kc
encoding for this domain, where plans are serializable, is shown in Figure
2. Serializability here means that parallel actions are non-interfering and
can be executed sequentially in any order, i.e. the parallel plan can be
arbitrarily "unfolded" to a sequential plan.

fluents : on(B, L) requires block(B), location(L).

blocked(B) requires block(B). moved(B) requires block(B).

actions : move(B, L) requires block(B), location(L) costs 1. always : executable
move(B, L) if B != L.

nonexecutable move(B, L) if blocked(B). nonexecutable move(B, L) if blocked(L).
nonexecutable move(B, L) if move(B1, L), B < B1, block(L). nonexecutable
move(B, L) if move(B, L1), L < L1. nonexecutable move(B, B1) if move(B1,
L).

caused on(B, L) after move(B, L). caused blocked(B) if on(B1, B). caused
moved(B) after move(B, L). caused on(B, L) if not moved(B) after on(B, L).

Figure 2: Kc encoding for the Blocks World domain The planning problem emerging
from the initial state and the goal state depicted in Figure 3 can be modeled
using the background knowledge Pi bw:

block(1). block(2). block(3). block(4). block(5). block(6). location(table).
location(B) :- block(B).

and extending the program in Figure 2 as follows:

initially : on(1, 2). on(2, table). on(3, 4). on(4, table). on(5, 6). on(6,
table).

goal : on(1, 3), on(3, table), on(2, 4), on(4, table), on(6, 5), on(5, table)
?(l)

42 31

3 4

21 6 5

5 6

Figure 3: A simple Blocks World instance

39

EITER, FABER, LEONE, PFEIFER & POLLERES Each move is penalized with cost
1, which results in a minimization of the total number of moves. Let Pl denote
the planning problem for plan length l.For

l = 2, we have an optimal plan which involves six moves, i.e. cost*P2 = 6:

P2 = h {move(1, table), move(3, table), move(5, table)}, {move(1, 3), move(2,
4), move(6, 5)} i By unfolding the steps, this plan gives rise to similar
plans of length l = 3, . . . , 6 that have cost 6.For

l = 3, we can find among others the following optimal plan, which has cost
5:

P3 = h {move(3, table)}, {move(1, 3), move(5, table)}, {move(2, 4), move(6,
5)} i

This plan can not be further parallelized to having only two steps. For any
plan length l > 3, we will obtain optimal plans similar to P3, extended by
void steps. Thus a plan which is cheapest over all plan lengths has cost
5 and needs three steps. Note that shortest parallel plans (of length 2)
are more expensive, as explained above.

5.1.2 SHORTEST PLANS (fi) Intuitively, it should be possible to include the
minimization of time steps in the cost function. We describe a preprocessing
method which, given a K planning domain PD, a list Q of ground literals,
and an upper bound i >= 0 for the plan length, generates a planning problem
Pfi(PD, Q, i) such that the optimal plans for Pfi correspond to shortest
plans which reach Q in PD in at most i steps, i.e., to plans for hPD, Q ?
(l)i such that l <= i is minimal. We assume that no action costs are specified
in the original planning domain PD, and minimizing time steps is our only
target.

First we rewrite the planning domain PD to PDfi as follows: We introduce
a new distinct fluent gr and a new distinct action finish, defined as follows:

fluents : gr. actions : finish costs time.

Intuitively, the action finish represents a final action, which we use to
finish the plan. The later this action occurs, the more expensive the plan
as we assign time as cost. The fluent gr ("goal reached") shall be true and
remain true as soon as the goal has been reached, and it is triggered by
the finish action.

This can be modeled in Kc by adding the following statements to the always
section of the program:

executable finish if Q, not gr. caused gr after finish. caused gr after gr.

Furthermore, we want finish to occur exclusively and we want to block the
occurrence of any other action once the goal has been reached. Therefore,
for every action A in PD, we add

nonexecutable A if finish.

and add not gr to the if-part of each executability condition for A. Finally,
to avoid any inconsistencies from static or dynamic effects as soon as the
goal has been reached, we add not gr to the if part of any causation rule
of the PD except nonexecutable rules which remain unchanged.4

We define now Pfi(PD, Q, i) = hPDfi , gr ?(i + 1)i. We take i + 1 as the
plan length since we need one additional step to execute the finish action.

4. There is no need to rewrite nonexecutable rules because the respective
actions are already "switched off" by

rewriting the executability conditions.

40

ANSWER SET PLANNING UNDER ACTION COSTS By construction, it is easy to see
that any optimal plan P = hA1, . . . , Aj , Aj+1, . . . , Ai+1i for the planning
problem Pfi must have Aj+1 = {finish} and Aj+2 = . . . = Ai+1 = ; for some
j 2 {0, . . . , i}. We thus have the following desired property.

Proposition 5.1 The optimal plans for Pfi are in 1-1 correspondence to the
shortest plans reaching Q in PD. More precisely, P = hA1, . . . , Aj+1, ;,
. . . , ;i is an optimal optimistic plan forP

fi(PD, Q, i) and Aj+1 = {finish} if and only if P 0 = hA1, . . . , Aji is
an optimistic plan forh PD, Q ? (j)i where j 2 {0, . . . , i}, and hPD, Q
? (j0)i has no optimistic plan for each j0 < j.

In our Blocks World example, using this method we get all 2-step plans, if
we choose i >= 2.

To compute shortest plans over all plan lengths, we can set the upper bound
i large enough such that plans of length l <= i are guaranteed to exist.
A trivial such bound is the total number of legal states which is in general
exponential in the number of fluents.

However, many typical applications have an inherent, much smaller bound on
the plan length. For instance, in a Blocks World with n blocks, any goal
configuration can be reached within at most 2n - sinit - sgoal steps, where
sinit and sgoal are the numbers of stacks in the initial and the goal state,
respectively.5 Therefore, 6 is an upper bound for the plan length of our
simple instance.

We remark that this approach for minimizing plan length is only efficient
if an upper bound close to the optimum is known. Searching for a minimum
length plan by iteratively increasing the plan length may be much more efficient
if no such bound is known, since a weak upper bound can lead to an explosion
of the search space (cf. the benchmarks in Section 7.2).

5.1.3 SHORTEST AMONG THE CHEAPEST PLANS (fl) In the previous subsection,
we have shown how to calculate shortest plans for K programs without action
costs. Combining arbitrary Kc programs and the rewriting method described
there is easy. If we want to find a shortest among the cheapest plans, we
can use the same rewriting, with just a little change. All we have to do
is setting the costs of all actions except finish at least as high as the
highest possible cost of the finish action. This is is obviously the plan
length i + 1. So, we simply modify all action declarations

A requires B costs C where D.

in Pfi by multiplying the costs with factor i + 1:

A requires B costs C1 where C1 = (i + 1) * C, D.

This lets all other action costs take priority over the cost of finish and
we can compute plans satisfying criterion (fl). Let Pfl denote the resultant
planning problem. Then we have:

Proposition 5.2 The optimal plans for Pfl are in 1-1 correspondence to the
shortest among the cheapest plans reaching Q in PD within i steps. More precisely,
P = hA1, . . . , Aj+1, ;, . . . , ;i is an optimal optimistic plan for Pfl
(PD, Q, i) and Aj+1 = {finish} if and only if (i) P 0 =h

A1, . . . , Aji is a plan for Pj = hPD, Q ? (j)i, where j 2 {0, . . . , i},
and (ii) if P 00 = hA1, . . . , Aj0i is any plan for Pj0 = hPD, Q ? (j0)i
where j0 <= i, then either costPj0 (P 00) > costPj (P 0) or costPj0 (P 00)
= costPj (P 0) and j0 >= j.

Figure 4 shows Pfl for our Blocks World instance where i = 6. One optimal
plan for Pfl is 5. One can solve any Blocks World problem sequentially by
first unstacking all blocks which are not on the table

(n - sinit steps) and then building up the goal configuration (n - sgoal
steps).

41

EITER, FABER, LEONE, PFEIFER & POLLERES fluents : on(B, L) requires block(B),
location(L).

blocked(B) requires block(B). moved(B) requires block(B). gr.

actions : move(B, L) requires block(B), location(L) costs C where C = 7 *
1.

finish costs time.

always : executable move(B, L) if B != L, not gr.

nonexecutable move(B, L) if blocked(B). nonexecutable move(B, L) if blocked(L).
nonexecutable move(B, L) if move(B1, L), B < B1, block(L). nonexecutable
move(B, L) if move(B, L1), L < L1. nonexecutable move(B, B1) if move(B1,
L).

caused on(B, L) if not gr after move(B, L). caused blocked(B) if on(B1, B),
not gr. caused moved(B) if not gr after move(B, L). caused on(B, L) if not
moved(B), not gr after on(B, L).

executable finish if on(1, 3), on(3, table), on(2, 4), on(4, table),

on(6, 5), on(5, table), not gr. caused gr after finish. caused gr after gr.
nonexecutable move(B, L) if finish.

initially : on(1, 2). on(2, table). on(3, 4). on(4, table). on(5, 6). on(6,
table). goal : gr? (7)

Figure 4: Computing the shortest plan for a Blocks World instance with a
minimum number of

actions

P = h {move(3, table)}, {move(1, 3), move(5, table)},{

move(2, 4), move(6, 5)}, {finish}, ;, ;, ; i,

which has costPfl (P ) = 39. We can now compute the optimal cost wrt. optimization
(fl) by subtracting the cost of finish and dividing by i + 1: (39 - 4) /
(i + 1) = 35 / 7 = 5. Thus, we need a minimum of 5 moves to reach the goal.
The minimal number of steps is obviously all steps, except the final finish
action, i.e. 3. Thus, we need at least 3 steps for a plan with five moves.

5.1.4 CHEAPEST AMONG THE SHORTEST PLANS (ffi) Again, we can use the rewriting
for optimization (fi). The cost functions have to be adapted similarly as
in the previous subsection, such that now the cost of the action finish takes
priority over all other actions costs. To this end, it is sufficient to set
the cost of finish high enough, which is achieved by multiplying it with
a factor F higher than the sum of all action costs of all legal action instances
at all steps j = 1, . . . , i + 1. Let Pffi denote the resulting planning
problem. We have:

Proposition 5.3 The optimal plans for Pffi are in 1-1 correspondence to the
cheapest among the shortest plans reaching Q in PD within i steps. More precisely,
P = hA1, . . . , Aj+1, ;, . . . , ;i

42

ANSWER SET PLANNING UNDER ACTION COSTS is an optimal optimistic plan for
Pffi(PD, Q, i) and Aj+1 = {finish} if and only if (i) P 0 =h

A1, . . . , Aji is a plan for Pj = hPD, Q ? (j)i, where j 2 {0, . . . , i},
and (ii) if P 00 = hA1, . . . , Aj0i is any plan for Pj0 = hPD, Q ? (j0)i
where j0 <= i, then either j0 > j, or j0 = j and costPj0 (P 00) >= costPj
(P 0).

In our example, there are 36 possible moves. Thus, we could take F = 36 *
(i + 1) and would set the costs of finish to time * 36 * (i + 1). However,
we only need to take into account those actions which can actually occur
simultaneously. In our example, at most six blocks can be moved in parallel.
Therefore, it is sufficient to set F = 6 * (i + 1) and assign finish cost
time * F = time * 42. Accordingly, the action declarations are modified as
follows:

actions : move(B, L) requires block(B), location(L) costs 1.

finish costs C where C = time * 42.

An optimal plan for the modified planning problem Pffi is:

P = h {move(1, table), move(3, table), move(5, table)},{

move(1, 3), move(2, 4), move(6, 5)}, {finish}, ;, ;, ;, ;i

We have costPffi (P ) = 132. Here, we can compute the optimal cost wrt. optimization
(ffi) by simply subtracting the cost of finish, i.e. 132 - 3 * 42 = 6, since
finish occurs at time point 3. Consequently, we need a minimum of 6 moves
for a shortest plan, which has length 3 - 1 = 2.

And indeed, we have seen that (and how) the optimization problems (ff) through
(ffi) can be represented in Kc. We remark that the transformations Pfi, Pfl
, and Pffi all work under the restrictions to secure and/or sequential plans
as well.

5.2 Traveling Salesperson As another illustrating example for optimal cost
planning, we will now introduce some elaboration of the Traveling Salesperson
Problem.

Traveling Salesperson Problem (TSP). We start with the classical Traveling
Salesperson Problem (TSP), where we have a given set of cities and connections
(e.g., roads, airways) of certain costs. We want to know a most economical
round trip which visits all cities exactly once and returns to the starting
point (if such a tour exists). Figure 5 shows an instance representing the
capitals of all Austrian provinces. The dashed line is a flight connection,
while all other connections are roads; each connection is marked with the
costs in traveling hours.

brg ... Bregenz eis ... Eisenstadt gra ... Graz ibk ... Innsbruck kla ...
Klagenfurt lin  ... Linz sbg ... Salzburg stp ... St. Po"lten vie ... Vienna

1 2 5

2

121 2 1lin stp

2 brg ibk 2 3 2

2 2 1

eis

vie

kla

gra

sbg1 3

Figure 5: TSP in Austria

43

EITER, FABER, LEONE, PFEIFER & POLLERES We represent this in Kc as follows.
The background knowledge Pi T SP defines two predicates city(C) and conn(F,
T, C) representing the cities and their connections with associated costs.
Connections can be traveled in both ways:

conn(brg, ibk, 2). conn(ibk, sbg, 2). conn(ibk, vie, 5). conn(ibk, kla, 3).
conn(sbg, kla, 2). conn(sbg, gra, 2). conn(sbg, lin, 1). conn(sbg, vie, 3).
conn(kla, gra, 2). conn(lin, stp, 1). conn(lin, vie, 2). conn(lin, gra, 2).
conn(gra, vie, 2). conn(gra, eis, 1). conn(stp, vie, 1). conn(eis, vie, 1).
conn(stp, eis, 2). conn(vie, brg, 1). conn(B, A, C) :- conn(A, B, C). city(T)
:- conn(T, , ).

A possible encoding of TSP starting in Vienna (vie) is the Kc program in
Figure 6. It includes two actions for traveling from one city to another
and for directly returning to the starting point at the end of the round
trip as soon as all cities have been visited.

actions : travel(X, Y) requires conn(X, Y, C) costs C.

return from(X) requires conn(X, vie, C) costs C.

fluents : unvisited. end.

in(C) requires city(C). visited(C) requires city(C).

always : executable travel(X, Y) if in(X).

nonexecutable travel(X, Y) if visited(Y). executable return from(X) if in(X).
nonexecutable return from(X) if unvisited.

caused unvisited if city(C), not visited(C). caused end after return from(X).
caused in(Y) after travel(X, Y). caused visited(C) if in(C). inertial visited(C).

noConcurrency. initially : in(vie). goal : end? (9)

Figure 6: Traveling Salesperson The problem has ten optimal 9-step solutions
with cost 15. We show only the first five here, as the others are symmetrical:

P1 = h {travel(vie, stp)}, {travel(stp, eis)}, {travel(eis, gra)}, {travel(gra,
lin)},{

travel(lin, sbg)}, {travel(sbg, kla)}, {travel(kla, ibk)}, {travel(ibk, brg)},{
return from(brg)} i P2 = h {travel(vie, eis)}, {travel(eis, stp)}, {travel(stp,
lin)}, {travel(lin, sbg)},{

travel(sbg, gra)}, {travel(gra, kla)}, {travel(kla, ibk)}, {travel(ibk, brg)},{
return from(brg)} i P3 = h {travel(vie, eis)}, {travel(eis, stp)}, {travel(stp,
lin)}, {travel(lin, gra)},{

travel(gra, kla)}, {travel(kla, sbg)}, {travel(sbg, ibk)}, {travel(ibk, brg)},{
return from(brg)} i P4 = h {travel(vie, lin)}, {travel(lin, stp)}, {travel(stp,
eis)}, {travel(eis, gra)},{

travel(gra, kla)}, {travel(kla, sbg)}, {travel(sbg, ibk)}, {travel(ibk, brg)},

44

ANSWER SET PLANNING UNDER ACTION COSTS {return from(brg)} i P5 = h {travel(vie,
gra)}, {travel(gra, eis)}, {travel(eis, stp)}, {travel(stp, lin)},{

travel(lin, sbg)}, {travel(sbg, kla)}, {travel(kla, ibk)}, {travel(ibk, brg)},{
return from(brg)} i

TSP with variable costs. Let us now consider an elaboration of TSP, where
we assume that the costs of traveling different connections may change during
the trip. Note that three of the five solutions in our example above include
traveling from St.P"olten to Eisenstadt or vice versa on the second day.
Let us now assume that the salesperson, who starts on Monday, has to face
some exceptions which might increase the cost of the trip. For instance,
(i) heavy traffic jams are expected on Tuesdays on the route from St.P"olten
to Eisenstadt or (ii) the salesperson shall not use the flight connection
between Vienna and Bregenz on Mondays as only expensive business class tickets
are available on this connection in the beginning of the week. So we have
to deal with different costs for the respective connections depending on
the particular day.

To this end, we first add to the background knowledge Pi T SP a new predicate
cost(A, B, W, C) representing the cost C of traveling connection A to B on
weekday W which can take exceptional costs into account:

cost(A, B, W, C) :- conn(A, B, C), #int(W), 0 < W, W <= 7, not ecost(A, B,
W). ecost(A, B, W) :- conn(A, B, C), cost(A, B, W, C1), C != C1.

The original costs in the predicate conn(A, B, C) now represent defaults,
which can be overridden by explicitly adding different costs. For instance,
to represent the exceptions (i) and (ii), we add:

cost(stp, eis, 2, 10). cost(vie, brg, 1, 10). setting the exceptional costs
for these two critical connections to 10. Weekdays are coded by integers
from 1 (Monday) to 7 (Sunday). We represent a mapping from time steps to
the weekdays by the following rules which we also add to Pi T SP :

weekday(1, 1). weekday(D, W) :- D = D1 + 1, W = W1 + 1, weekday(D1, W1),
W1 < 7. weekday(D, 1) :- D = D1 + 1, weekday(D1, 7).

Note that although the modified background knowledge Pi T SP is not stratified
(since cost is defined by cyclic negation), it has a total well-founded model,
and thus a unique answer set.

Finally, we change the costs of traveling and returning in the Kc program
from Figure 6:

actions : travel(X, Y) requires conn(X, Y, C1) costs C

where weekday(time, W), cost(X, Y, W, C). return from(X) requires conn(X,
vie, C1) costs C

where weekday(time, W), cost(X, vie, W, C).

Since now the costs for P1 (which includes traveling from St.P"olten to Eisenstadt)
on the second day have increased due to exception (i), only four of the plans
from above remain optimal. Note that unlike the default costs, exceptional
costs do not apply bidirectionally, so the exception does not affect P2 and
P3. Furthermore, due to exception (ii) the symmetrical round trips starting
with the flight trips to Bregenz are no longer optimal.

The presented encoding proves to be very flexible, as it allows for adding
arbitrary exceptions for any connection on any weekday by simply adding the
respective facts; moreover, even more involved scenarios, where exceptions
are defined by rules, can be modeled.

45

EITER, FABER, LEONE, PFEIFER & POLLERES 5.3 A Small Example for Planning
under Resource Restrictions Although planning with resources is not the main
target of our approach, the following encoding shows that action costs can
also be used in order to model optimization of resource consumption in some
cases. An important resource in real world planning is money. For instance,
let us consider a problem about buying and selling (Lee & Lifschitz, 2001):

"I have $6 in my pocket. A newspaper costs $1 and a magazine costs $3. Do
I have enough money to buy one newspaper and two magazines?"

In Kc, this can be encoded in a very compact way by the following background
facts:

item(newspaper, 1). item(magazine, 2). combined with the following short
Kc program:

actions : buy(Item, Number) requires item(Item, Price), #int(Number)

costs C where C = Number * Price.

fluents : have(Item, Number) requires item(Item, Price), #int(Number). always
: executable buy(Item, Number).

nonexecutable buy(Item, N1) if buy(Item, N2), N1 < N2. caused have(Item,
Number) after buy(Item, Number).

goal : have(newspaper, 1), have(magazines, 2) ? (1) The action buy is always
executable, but one must not buy two different amounts of a certain item
at once. Obviously, no admissible plan wrt. cost 6 exists, as the optimal
plan for this problem,h{

buy(newspaper, 1), buy(magazine, 2)} i has cost*P = 7. Therefore, the answer
to the problem is "no."

Our approach considers only positive action costs and does not directly allow
modeling full consumer/producer/provider relations on resources in general,
in favor of a clear non-ambiguous definition of optimality. For instance,
by allowing negative costs one could always add a producer action to make
an existing plan cheaper, whereas in our approach costs are guaranteed to
increase monotonically, allowing for a clear definition of plan costs and
optimality.

On the other hand, we can encode various kinds of resource restrictions by
using fluents to represent these resources. We can then model production/consumption
as action effects on these fluents and add restrictions as constraints. This
allows us to model even complex resource or scheduling problems; optimization,
however, remains restricted to action costs.

6. Transformation to Logic Programming In this section, we describe how planning
under action costs can be implemented by means of a transformation to answer
set programming. It extends our previous transformation (Eiter et al., 2003a),
which maps ordinary K planning problems to disjunctive logic programs under
the answer set semantics (Gelfond & Lifschitz, 1991), and takes advantage
of weak constraints, cf. (Buccafurri, Leone, & Rullo, 1997, 2000), as implemented
in the DLV system (Faber & Pfeifer, 1996; Eiter, Faber, Leone, & Pfeifer,
2000a). In addition, we show how this translation can be adapted to the language
of Smodels (Simons, Niemel"a, & Soininen, 2002).

6.1 Disjunctive Logic Programs with Weak Constraints First, we give a brief
review of disjunctive logic programs with weak constraints.

46

ANSWER SET PLANNING UNDER ACTION COSTS Syntax A disjunctive rule (for short,
rule) R is a construct

a1 v * * * v an :- b1, * * * , bk, not bk+1, * * * , not bm. (2) where all
ai and bj are classical literals over a function-free first-order alphabet,
and n >= 0, m >= k >= 0. The part left (resp. right) of ":-" is the head
(resp. body) of R, where ":-" is omitted if m = 0. We let H(R) = {a1, . .
., an} be the set of head literals and B(R) = B+(R) [ B-(R) the set of body
literals, where B+(R) = {b1,. . . , bk} and B-(R) = {bk+1, . . . , bm}. A
(strong) constraint is a rule with empty head (n = 0).

A weak constraint is a construct

:, b1, * * * , bk, not bk+1, * * * , not bm. [w :] (3) where w is an integer
constant or a variable occurring in b1, . . . , bk and all bi are classical
literals.6 B(R) is defined as for (2).

A disjunctive logic program (DLPw) (simply, program) is a finite set of rules,
constraints and weak constraints; here, superscript w indicates the potential
presence of weak constraints.

Semantics The answer sets of a program Pi  without weak constraints are
defined as usual (Gelfond & Lifschitz, 1991; Lifschitz, 1996). There is one
difference, though: We do not consider inconsistent answer sets. The answer
sets of a program Pi  with weak constraints are defined by selection from
the answer sets S of the weak-constraint free part Pi 0 of Pi  as optimal
answer sets.

A weak constraint c of form (3) is violated, if it has an instance for which
its conjunction is satisfied with respect to the candidate answer set S,
i.e., there exists a substitution mapping ` from the variables in c to the
Herbrand base of Pi  such that {b1`, * * * , bk`} ` S and {bk+1`, * * *
, bm`}" M = ;; we then call w` the violation value of c wrt. `.7 The violation
cost of c wrt. S, denoted costc(S), is the sum of all violation values over
all violating substitutions for c wrt. S; the cost of S, denoted costPi
(S), is then

costPi (S) = X

c 2 weak constraints of Pi 

costc(S),

i.e., the sum of violation costs of weak constraints in Pi  wrt. S. An answer
set M of Pi  is now selected (called an optimal answer set), if costPi
(M ) is minimal over all answer sets of Pi .

From (Buccafurri et al., 2000) we know that given a head-cycle-free disjunctive
program, deciding whether a query q is true in some optimal answer set is
Delta P2 -complete. The respective class for computing such an answer set
is FDelta P2 -complete. Together with the results from Section 4 this indicates
that translations of optimal planning problems to head-cycle-free disjunctive
logic programs with weak constraints or the language of Smodels are feasible
in polynomial time.

6.2 Translating Kc to DLPw We extend our original transformation lp(P), which
naturally maps a K planning problem P into a weak-constraint free program
(Eiter et al., 2003a), to a new translation lpw(P), such that the optimal
answer sets of lpw(P) correspond to the optimal cost plans for the Kc planning
problem P.

6. The colon in [w :] stems from the DLV language, which allows to specify
a priority layer after the colon. We do not

need priority layers in our translation, but stick to the DLV syntax. 7.
A weak constraint c is only admissible, if all possible violation values
in all candidate answer sets S are integers.

Thus, if w is a variable, then Pi  must guarantee that w can only be bound
to an integer.

47

EITER, FABER, LEONE, PFEIFER & POLLERES Basically, in lp(P) fluent and action
literals are extended by an additional time parameter, and executability
conditions as well as causations rules are modularly translated (rule by
rule) into corresponding program rules and constraints; disjunction is used
for guessing the actions which should be executed in the plan at each point
in time.

6.2.1 REVIEW OF THE TRANSLATION lp(P) The basic steps of the translation
from K programs to logic programs are as follows (cf. (Eiter et al., 2003a)
for details):

Step 0 (Macro Expansion): First, replace all macros in the K program by their
definitions. Step 1 (Background Knowledge): The background knowledge Pi
of P is already given as a logic program and is included in lp(P), without
further modification.

Step 2 (Auxiliary Predicates): To represent steps, we add the following facts
to lp(P)

time(0)., . . . , time(l). next(0, 1)., . . . , next(l - 1, l). where l is
the plan length of the query q = G?(l) in P at hand.

Step 3 (Causation Rules): Causation rules are mapped to rules in lp(P) by
adding type information and extending fluents and actions with a time stamp
using time and next. For example,

caused across(X) after cross(X), -across(X). leads to rule across(X, T1)
:- cross(X, T0), -across(X, T0), person(X), next(T0, T1). in lp(P) where
T1, T0 are new variables. Here, type information person(X) for across(X),
and -across(X), taken from the type declaration, is added, which helps to
avoid unsafe logic programming rules.

Step 4 (Executability Conditions): Similarly, each executability condition
is translated to a disjunctive rule "guessing" whether an action occurs at
a certain time step. In our running example,

executable cross(X) if hasLamp(X). becomes cross(X, T0) . -cross(X, T0) :-
hasLamp(X, T0), person(X), next(T0, T1). which encodes a guess whether at
time point T0 action cross(X) should happen; again, type information person(X)
is added as well as next(T0, T1) to ensure that T0 is not the last time point.

Step 5 (Initial State Constraints): Initial state constraints are transformed
like static causation rules in Step 3, but using the constant 0 instead of
the variable T1 and thus need no auxiliary predicate for the time stamp.
For instance,

initially : caused -across(X). becomes, by again adding the type information
-across(X, 0) :- person(X).

Step 6 (Goal Query): Finally, the query q:

goal : g1(t1), . . . , gm(tm), not gm+1(tm+1), . . . , not gn(tn) ? (l).
is translated as follows, where goal reached is a new 0-ary predicate symbol:

goal reached :- g1(t1, l), . . . , gm(tm, l), not gm+1(tm+1, l), . . . ,
not gn(tn, l). :- not goal reached.

48

ANSWER SET PLANNING UNDER ACTION COSTS 6.2.2 EXTENDING THE TRANSLATION TO
ACTION COSTS The extended translation lpw(P) for a Kc problem P first includes
all rules of lp(Pnc), where Pnc results from P by stripping off all cost
parts. Furthermore, the following step is added:

Step 7 (Action Costs): For any action declaration d of form (1) with a nonempty
costs-part, add:

(i) A new rule rd of the form costp(X1, . . . , Xn, T, C`) :- p(X1, . . .
, Xn, T), t1, . . . , tm,c

1`, . . . , ck`, U = T + 1. (4)

where costp is a new symbol, T and U are new variables and ` = {time ! U}.
As an optimization, U = T + 1 is only present if U occurs elsewhere in rd.

(ii) A weak constraint wcd of the form :, costp(X1, . . . , Xn, T, C). [C
:] (5) For example, the cross action from the Quick Bridge Crossing Problem
is translated to

costcross(X, T, WX):- cross(X, T), person(X), walk(X, WX). :, costcross(X,
T, WX). [WX :] As we showed in previous work (Eiter et al., 2003a), the answer
sets of lp(P) correspond to trajectories of optimistic plans for P. The following
theorem states a similar correspondence result for lpw(P) and optimal plans
for P. We define, for any consistent set of ground literals S, the sets ASj
= {a(t) | a(t, j - 1) 2 S, a 2 oeact} and sSj = {f (t) | f (t, j) 2 S, f
(t) 2 Lfl}, for all j >= 0.

Theorem 6.1 (Answer Set Correspondence) Let P = hPD, qi be a (well-defined)
Kc planning problem, and let lpw(P) be the above program. Then,

(i) for each optimistic plan P = hA1, . . . , Ali of P and supporting trajectory
T = hhs0, A1, s1i,h

s1, A2, s2i, . . . , hsl-1, Al, slii of P , there exists some answer set
S of lpw(P) such that Aj = ASj for all j = 1, . . . , l, sj = sSj , for all
j = 0, . . . , l and costP(P ) = costlpw(P) (S);

(ii) for each answer set S of lpw(P), the sequence P = hA1, . . . , Ali is
a solution of P, i.e., an

optimistic plan, witnessed by the trajectory T = hhs0, A1, s1i, hs1, A2,
s2i, . . . , hsl-1, Al, slii with costP(P ) = costlpw(P) (S), where Aj =
ASj and sk = sSk for all j = 1, . . . , l and k = 0, . . . , l.

The proof is based on the resp. correspondence result for K (Eiter et al.,
2003a). For the details, we refer to the Appendix.

From this result and the definitions of optimal cost plans and optimal answer
sets, we conclude the following result:

Corollary 6.2 (Optimal answer set correspondence) For any well-defined Kc
planning problemP

= hPD, Q ? (l)i, the trajectories T = hhs0, A1, s1i, . . . , hsl-1, Al, slii
of optimal plans P for P correspond to the optimal answer sets S of lpw(P),
such that Aj = ASj for all j = 1, . . . , l and

sj = sSj , for all j = 0, . . . , l.

Proof. For each a 2 Aj, the weak constraint (5) causes a violation value
of costj(a). Furthermore, these are the only cost violations. Thus, a candidate
answer set S is optimal if and only if costlpw(P) (S) = Plj=1 Pa2Aj costj(a)
= costP (P ) is minimal, i.e., S corresponds to an optimal plan. 2

A similar correspondence result also holds for admissible plans:

49

EITER, FABER, LEONE, PFEIFER & POLLERES Corollary 6.3 (Answer set correspondence
for admissible plans) For any well-defined Kc planning problem P = hPD, Q
? (l)i, the trajectories T = hhs0, A1, s1i, . . . , hsl-1, Al, slii of admissible
plans P for P wrt. cost c correspond to the answer sets S of lpw(P) having
costlpw(P) (S) <= c, such that Aj = ASj for all j = 1, . . . , l and sj =
sSj , for all j = 0, . . . , l.

As for secure planning, we have introduced a technique to check security
of an optimistic plan for certain planning problem instances by means of
a logic program (Eiter et al., 2003a). This method carries over to planning
with action costs in a straightforward way, and optimal resp. admissible
secure plans can be similarly computed by answer set programming.

6.3 Alternative Translation for Smodels Apart from the presented translation
using weak constraints, one could also choose an alternative approach for
the translation to answer set programming. Smodels (Simons et al., 2002)
supports another extension to pure answer set programming allowing to minimize
over sets of predicates.

This approach could be used in an alternative formulation of Step 7:

Step 7a: For action declarations with nonempty costs-parts, we add a new
rule of form

cost(p, X1, . . . , Xn, 0, . . . , 0, T, C`) :- t1, . . . , tm, c1`, . .
. , ck`, U = T + 1. (6) similar to Step 7 above, with two differences: (1)
action name p is now a parameter, and (2) we add l - n parameters with constant
"0" between Xn and T where l is the maximum arity of all actions in PD. This
is necessary in order to get unique arity l + 2 for predicate cost. Furthermore,
we add

occurs(p, X1, . . . , Xn, 0, . . . , 0, T) :- p(X1, . . . , Xn, T), t1, .
. . , tm,. (7) This second rule adds the same "0" parameters as for to achieve
unique arity l + 1 of the new predicate occurs. Using Smodels syntax, we
can now compute optimal plans by adding

minimize[occurs(A, X1, ..., Xl, T) : cost(A, X1, ..., Xl, T, C) = C]. Note
that Smodels does not support disjunction in rule heads, so we also need
to modify Step 4, expressing the action guess via unstratified negation or
Smodels' choice rules.

7. Implementation We have implemented an experimental prototype system, DLVK,
for solving K planning problems (Eiter et al., 2003a). An improved version
of this prototype it is now capable of optimal and admissible planning with
respect to the extended syntax of Kc, available for experiments at http://www.dlvsystem.com/K/
.

DLVK has been realized as a frontend to the DLV system (Faber & Pfeifer,
1996; Eiter et al., 2000a). First, the planning problem at hand is transformed
as described in the previous section. Then, the DLV kernel is invoked to
produce answer sets. For optimistic planning the (optimal, if action costs
are defined) answer sets are then simply translated back into suitable output
for the user and printed.

In case the user specified that secure/conformant planning should be performed,
our system has to check security of the plans computed. In normal (non-optimal)
planning, this is simply done by checking each answer set returned right
before transforming it back to user output. In the case of

50

ANSWER SET PLANNING UNDER ACTION COSTS optimal secure planning, on the other
hand, the candidate answer set generation of the DLV kernel has to be "intercepted":
The kernel proceeds computing candidate answer sets, returning an answer
set with minimal violation cost value, by running through all candidates.
Here, in order to generate optimal secure plans, the planning frontend interrupts
computation, allowing only answer sets which represent secure plans to be
considered as candidates.

Checking plan security is done by rewriting the translated program wrt. the
candidate answer set/plan in order to verify whether the plan is secure.
The rewritten "check program" is tested by a separate invocation of the DLV
kernel. As for further details on the system architecture we refer to (Eiter
et al., 2003a)

7.1 Usage Suppose the background knowledge and the program depicted in Figure
1 with the cost extensions from Section 3.3 are stored in files crossing.bk
and crossing.plan; then, by invoking the program with the command line

dlv - FPcrossing.plancrossing.bk - planlength = 7 we compute all optimal
plans solving this problem in seven steps. In the output we find, after asupporting
trajectory, the following optimal plan:

PLAN : crossTogether(joe, jack) : 2; cross(joe) : 1; takeLamp(william);

crossTogether(william, averell) : 10; takeLamp(jack); cross(jack) : 2; crossTogether(joe,
jack) : 2 COST : 17

For each action, its cost is shown after a colon, if it is non-zero. The
switch -planlength=i can be used to set the plan length; it overrides any
plan length given in the query-part of the planing problem. Using -planlength=5,
we get plans with cost 19, as there are no cheaper plans of that length.

The user is then asked whether to perform the optional security check and
whether to look for further (optimal) plans, respectively. The switch -FPsec
can be used instead of -FP to obtain secure plans only.

The command line option -costbound=N effects the computation of all admissible
plans with respect to cost N . For example, the resource problem described
in Section 5.3 can be solved by the following call to our prototype:

dlv - FPbuying.bkbuying.plan - N = 10 - planlength = 1 - costbound = 6 Correctly,
no admissible plan is found. When calling the system again without cost bound,
theprototype calculates the following optimal cost plan:

PLAN : buy(newspaper, 1) : 1, buy(magazine, 2) : 6 COST : 7

The current prototype supports simple bounded integer arithmetics. The option
-N=10 used above sets an upper bound of N = 10 for the integers which may
be used in a program; the builtin predicate #int is true for all integers
0 . . . N . Setting N high enough, taking into account the outcome of built-in
arithmetic predicates A = B + C and A = B * C, is important to get correct
results. Further details on the prototype are given on the DLVK web site
at http://www. dlvsystem.com/K/.

51

EITER, FABER, LEONE, PFEIFER & POLLERES 7.2 Experiments Performance and experimental
results for DLVK (without action costs and optimal planning) were reported
in previous work (Eiter et al., 2003a). In this section, we present some
encouraging experimental results for planning with action costs, in particular
for parallel Blocks World and TSP. All experiments were performed on a Pentium
III 733MHz machine with 256MB of main memory running SuSE Linux 7.2. We set
a time limit of 4000 seconds for each tested instance where exceeding this
limit is indicated by "-" in the result tables.

Where possible, we also report results for CCALC and CMBP, two other logic-based
planning systems whose input languages (C+ resp. AR) have capabilities similar
to K resp. Kc.

CCALC. The Causal Calculator (CCALC) is a model checker for the languages
of causal theories (McCain & Turner, 1997). It translates programs in the
action language C+ into the language of causal theories which are in turn
transformed into SAT problems; these are then solved using a SAT solver (McCain
& Turner, 1998). The current version of CCALC uses mChaff (Moskewicz et al.,
2001) as its default SAT solver. Minimal length plans are generated iteratively
increasing the plan length up to an upper bound. CCALC is written in Prolog.
For our tests, we used version 2.04b of CCALC which we obtained from  and a trial version of SICStus Prolog 3.9.1. We used encodings taken from
(Lee & Lifschitz, 2001) for parallel Blocks World adapted for CCALC 2.0.
These encodings are included in the current download version of the system.
For sequential Blocks World we adapted the encodings by adding the C+ command
"noConcurrency." which resembles the respective K command. All results for
CCALC include 2.30sec startup time.

CMBP. The Conformant Model Based Planner (CMBP) (Cimatti & Roveri, 2000)
is based on the model checking paradigm and exploits symbolic Boolean function
representation techniques such as Binary Decision Diagrams (Bryant, 1986).
CMBP allows for computing sequential minimal length plans, where the user
has to declare an upper bound for the plan length. Its input language is
an extension of AR (Giunchiglia, Kartha, & Lifschitz, 1997). Unlike K or
action languages such as C+ (Lee & Lifschitz, 2001), this language only supports
propositional actions. CMBP is tailored for conformant planning. The results
reported complement a previous comparison which also shows the encoding for
sequential Blocks World in CMBP (Eiter et al., 2003a). For our tests, we
used CMBP 1.0, available at .

7.2.1 BLOCKS WORLD Tables 1-4 show the results for our different Blocks World
encodings in Section 5.1 on several configurations: P0 denotes our simple
instance from Figure 3, while P1-P5 are instances used in previous work (Eiter
et al., 2003a; Erdem, 1999).

Table 1 shows the results for finding a shortest sequential plan. The second
and third column show the number of blocks and the length of a shortest plan
(i.e., the least number of moves) solving the respective blocks world instance.
The execution time for solving the problem using the shortestplan encoding
Pfi in Section 5.1 is shown in column five, using the upper bound shown in
the fourth column on the plan length. Column six shows the execution time
for finding the shortest plan in an incremental plan length search starting
from 0, similar to the method used for CCALC. The remaining two columns show
the results for CCALC and CMBP.

52

ANSWER SET PLANNING UNDER ACTION COSTS Problem #blocks min. #moves (=#steps)
upper bound #steps DLVK DLVKinc CCALC CMBP P0 6 5 6 0.48s 0.29s 4.65s 21.45s
P1 4 4 4 0.05s 0.08s 3.02s 0.13s P2 5 6 7 0.24s 0.27s 4.02s 8.44s P3 8 8
10 25.32s 2.33s 10.07s P4 11 9 16 - 8.28s 27.19s P5 11 11 16 - 12.63s 32.27s
Table 1: Sequential Blocks World - shortest plans

Problem #blocks #steps(fixed) min. #moves DLVK P0 6 2 6 0.05s P0 6 3 5 0.09s
P1 4 3 4 0.04s P2 5 5 6 0.10s P3 8 4 9 0.21s P4 11 5 13 0.81s P5 11 7 15
327s

Table 2: Parallel Blocks World - cheapest plans: Minimal number of moves
at fixed plan length (ff)

Table 2 shows the execution times for parallel blocks world with fixed plan
length where the number of moves is minimized, i.e. problem (ff) in Section
5.1. We used the encoding in Figure 2, which generates parallel serializable
plans. As CCALC and CMBP do not allow for optimizing other criteria than
plan length, we only have results for DLVK here.

Next, Table 3 shows some results for finding a shortest parallel plan, i.e.
problem (fi) in Section 5.1. First, the minimal possible number of steps
is given. We processed each instance (i) using the encoding Pfi from Section
5.1, (ii) without costs by iteratively increasing the plan length and (iii)
using CCALC, by iteratively increasing the plan length until a plan is found.
For every result, the number of moves of the first plan computed is reported
separately. As CMBP only supports sequential planning, it is not included
in this comparison.

Finally, Table 4 shows the results for the combined optimizations (fl) and
(ffi) for parallel Blocks World as outlined in Section 5.1. The second column
again contains the upper bound for the plan

upper bound min. #steps DLVK DLVKinc CCALC

#moves time #moves time #moves time P0 6 2 6 0.52s 6 0.09s 6 4.05s P1 4 3
5 0.07s 5 0.08s 4 2.95s P2 7 5 9 0.39s 9 0.21s 6 3.70s P3 10 4 - - 12 0.43s
9 7.69s P4 16 5 - - 18 1.54s 13 20.45s P5 16 7 - - 26 3.45s 15 23.22s

Table 3: Parallel Blocks World - shortest plan (fi)

53

EITER, FABER, LEONE, PFEIFER & POLLERES

(fl) (ffi) upper bound steps/moves DLVK DLVKinc CCALC steps/moves DLVK DLVKinc
P0 6 3/5 38.5s 0.18s 5.89s 2/6 0.26s 0.09s P1 4 3/4 0.07s 0.11s 3.47s 3/4
0.08s 0.08s P2 7 5/6 2.08s 0.21s 5.65s 5/6 0.78s 0.28s P3 10 5/8 - 1.57s
15.73s 4/9 177s 0.45s P4 16 9/9 - - 73.64s 5/13 - 1.86s P5 16 11/11 - - 167s
7/15 - 323s

Table 4: Parallel Blocks World - (fl),(ffi)

length of the respective instance. The following three columns present the
results on finding a shortest among the cheapest plans, i.e. problem (fl)
in Section 5.1:

DLVK refers to the results for our combined minimal encoding Pfl and as described
in Section 5.1; DLVKinc refers to the results for incrementally searching
for the shortest among the cheapest plans:

This is done by means of the -costbound=i command line option taking the
minimal sequential costs (i.e., the shortest sequential plan length as computed
in Table 1) as an upper cost limit. As our encodings compute serializable
plans, the minimal sequential length can be used as cost limit in this special
case.

CCALC A similar technique can be used with CCALC when encoding bound costs
through "additive fluents" (Lee & Lifschitz, 2001).

Note that the incremental strategy (used by DLVKinc and CCALC) takes advantage
of our specific formulation of the parallel Blocks World problem: In general,
when allowing parallel actions which are not necessarily serializable and
have arbitrary costs, the optimal parallel cost might differ from the optimal
sequential solution. In particular, plans which are longer than the cheapest
sequential plans (which, in this example, coincide with the shortest sequential
plans) may need to be considered. This makes incremental search for a solution
of problem (fl) infeasible in general.

The last test is finding a cheapest among the shortest plans, that is, problem
(ffi) in Section 5.1. Again we have tested the integrated encoding with an
upper bound (Pffi) resp. incrementally finding the shortest plan. Unlike
for problem (fl), we cannot derive a fixed cost limit from the sequential
solution here; we really need to optimize costs, which makes an encoding
in CCALC infeasible.

Blocks World - Results The Blocks World experiments show that DLVK can solve
various optimization tasks in a more effective and flexible way than the
systems compared. On the other hand, as already stated above, for the minimal
plan length encodings in Section 5.1, we can only solve the problems where
a tight upper bound for the plan length is known. Iteratively increasing
the plan length is more effective, especially if the upper bound is much
higher than the actual optimal solution. This becomes drastically apparent
when execution times seem to explode from one instance to the next, in a
highly non-linear manner as in Table 1 where a solution for P3 can be found
in reasonable time whereas P4 and P5 could not be solved within the time
limit of 4000 seconds. This observation is also confirmed in the other tables
(instance P5 in Table 2, etc.) and is partly explained by the behavior of
the underlying DLV system, which is not geared towards plan search, and as
a general purpose problem solver uses heuristics which might not work out
well in some cases. In particular, during the answer set generation process
in DLV, no distinction is made between actions

54

ANSWER SET PLANNING UNDER ACTION COSTS and fluents, which might be useful
for planning tasks to control the generation of answer sets resp. plans;
this may be part of further investigations.

Interestingly, CCALC finds "better quality" parallel solutions for problem
(fi) (cf. Table 3), i.e. solutions with fewer moves, although it is significantly
slower than our system on these instances. For the incremental encoding of
problem (fl), CCALC seems even more effective than our system. However, CCALC
offers no means of optimization; it allows for admissible but not for optimal
planning. This makes our approach more flexible and general. As stated above,
we could fortunately exploit the fixed cost bound in this particular example
for CCALC, which is not possible in general instances of problem (fl).

Problem (fl) is also intuitively harder than simply finding a shortest plan
or a cheapest among all shortest plans in general: While these problems can
always be solved incrementally, for (fl) we must consider all plans of all
lengths. A longer plan may be cheaper, so we cannot freeze the plan length
once a (shortest) plan has been incrementally found.

7.2.2 TSP Some experimental results on TSP with variable costs are reported
in Tables 5 and 6. Unlike for blocks world, no comparable systems were available;
none of the systems from above supports cost optimal planning as needed for
solving this problem. Here, the plan length is always given by the number
of cities.

Table 5 shows the results for our TSP instance on the Austrian province capitals
as in Figure 5 (nine cities, 18 connections), with and without the exceptional
costs as in Section 5.2 (with and without subscript exc in the table). Further
instances reported in this table with different cost exceptions (we, lwe,
rnd) are described below.

Results for some bigger TSP instances, given by the capitals of the 15 members
of the European Union (EU) with varying connection graphs and exceptional
costs are shown in Table 6. We have used the flight distances (km) between
the cities as connection costs. Instances TSPEU1-TSPEU6 have been generated
by randomly choosing a given number of connections from all possible connections
between the 15 cities. Note that TSPEU1 has no solution; the time reported
here is until DLVK terminated, and for all other instances until the first
optimal plan was found.

We have also tested some instances of more practical relevance than simply
randomly choosing connections: TSPEU7 is an instance where we have taken
the flight connections of three carriers (namely, Star Alliance, Alitalia,
and Luxair), and in TSPEU8 we have included only direct connections of at
most 1500km. Such a "capital hopping" is of interest for a small airplane
with limited range, for instance.

For each instance in Tables 5-6 we have measured the execution time:

* without exceptional costs,

* with 50% costs for all connections on Saturdays and Sundays (weekends,
we)

* with 50% costs for all connections on Fridays, Saturdays and Sundays (long
weekends, lwe),

* for some random cost exceptions (rnd): We have added a number of randomly
generated exceptions with costs between 0 and 10 for TSPAustria and between
0 and 3000 for the instances EU1 to EU8.

55

EITER, FABER, LEONE, PFEIFER & POLLERES

Instance #cost exceptions cost/time TSPAustria 0 15/0.31s TSPAustria,exc
2 15/0.32s TSPAustria,we 36 12/0.34s TSPAustria,lwe 54 11/0.35s TSPAustria,rnd
10 14/0.30s TSPAustria,rnd 50 15/0.31s TSPAustria,rnd 100 23/0.35s TSPAustria,rnd
200 36/0.37s

Table 5: TSP - Results for TSPAustria with varying exceptions

Instance #conn. #except. cost/time TSPEU1 30 0 -/9.11s TSPEU1,we 30 60 -/11.93s
TSPEU1,lwe 30 90 -/13.82s TSPEU1,rnd 30 100 -/11.52s TSPEU1,rnd 30 200 -/12.79s
TSPEU1,rnd 30 300 -/14.64s TSPEU1,rnd 30 400 -/16.26s TSPEU2 30 0 16213/13.27s
TSPEU2,we 30 60 13195/16.41s TSPEU2,lwe 30 90 11738/18.53s TSPEU2,rnd 30
100 15190/15.54s TSPEU2,rnd 30 200 13433/16.31s TSPEU2,rnd 30 300 13829/18.34s
TSPEU2,rnd 30 400 13895/20.59s TSPEU3 35 0 18576/24.11s TSPEU3,we 35 70 15689/28.02s
TSPEU3,lwe 35 105 14589/30.39s TSPEU3,rnd 35 100 19410/26.75s TSPEU3,rnd
35 200 22055/29.64s TSPEU3,rnd 35 300 18354/31.54s TSPEU3,rnd 35 400 17285/32.66s
TSPEU4 35 0 16533/36.63s TSPEU4,we 35 70 12747/41.72s TSPEU4,lwe 35 105 11812/43.12s
TSPEU4,rnd 35 100 15553/39.17s TSPEU4,rnd 35 200 13216/41.19s TSPEU4,rnd
35 300 16413/43.51s TSPEU4,rnd 35 400 13782/45.69s TSPEU5 40 0 15716/91.83s
TSPEU5,we 40 80 12875/97.73s TSPEU5,lwe 40 120 12009/100.14s TSPEU5,rnd 40
100 13146/85.69s TSPEU5,rnd 40 200 12162/83.44s TSPEU5,rnd 40 300 12074/76.81s
TSPEU5,rnd 40 400 12226/82.97s TSPEU5,rnd 40 500 13212/82.53s

Instance #conn. #except. cost/time TSPEU6 40 0 17483/142.7s TSPEU6,we 40
80 14336/150.3s TSPEU6,lwe 40 120 13244/154.7s TSPEU6,rnd 40 100 15630/142.5s
TSPEU6,rnd 40 200 14258/137.2s TSPEU6,rnd 40 300 11754/120.5s TSPEU6,rnd
40 400 11695/111.4s TSPEU6,rnd 40 500 12976/120.8s TSPEU7 55 0 15022/102.6s
TSPEU7,we 55 110 12917/112.2s TSPEU7,lwe 55 165 11498/116.2s TSPEU7,rnd 55
100 13990/104.2s TSPEU7,rnd 55 200 12461/100.8s TSPEU7,rnd 55 300 13838/106.9s
TSPEU7,rnd 55 400 12251/96.58s TSPEU7,rnd 55 500 16103/109.2s TSPEU7,rnd
55 600 14890/110.3s TSPEU7,rnd 55 700 17070/110.7s TSPEU8 64 0 10858/3872s
TSPEU8,we 64 128 9035/3685s TSPEU8,lwe 64 192 8340/3324s TSPEU8,rnd 64 100
10283/2603s TSPEU8,rnd 64 200 9926/1372s TSPEU8,rnd 64 300 10028/1621s TSPEU8,rnd
64 400 8133/597.7s TSPEU8,rnd 64 500 8770/573.3s TSPEU8,rnd 64 600 8220/360.7s
TSPEU8,rnd 64 700 6787/324.6s TSPEU8,rnd 64 800 11597/509.5s

Table 6: TSP - Various instances for the capitals of the 15 EU members

56

ANSWER SET PLANNING UNDER ACTION COSTS TSP - Results Instance TSPEU8 shows
the limits of our system: the given data allows for many possible tours,
so finding an optimal one gets very tricky. On the other hand, a realistic
instance like TSPEU7 with real airline connections is solved rather quickly,
which is not very surprising: Most airlines have a central airport (for instance
Vienna for Austrian Airlines) and few direct connections between the destinations
served. This allows for much fewer candidate answer sets, when (as in reality)
the number of airlines we consider is limited. E.g., TSPEU7 has no solution
at all if only two out of Star Alliance, Alitalia, and Luxair are allowed.
Of course, we cannot compete with dedicated TSP solvers/algorithms, which
are able to solve much bigger TSP instances and have not been considered
here. However, to our knowledge, none of these solvers can deal with features
such as incomplete knowledge, defaults, time dependent exceptional costs,
etc. directly. Our results even show that execution times are stable yet
in case of many exceptions. In contrast, instance TSPEU8 shows that exceptions
can also cause a significant speedup. This is due to the heuristics used
by the underlying DLV system, which can single out better solutions faster
if costs are not spread evenly like in TSPEU8 without exceptional costs.

Note that, we have also experimented with the alternative Smodels translation
sketched in Section 6.3. We refrain from detailed discussion here, since
the (i) translation is optimized for DLV and Smodels performance was worse
(around factor 10 for the tested TSP instances) than DLV and (ii) there is
no integrated planning frontend available for Smodels providing a high-level
planning language. Nevertheless, we have shown that our approach can, with
minor modifications, be adopted in a planning system based on Smodels.

8. Related Work In the last years, it has been widely recognized that plan
length alone is only one criterion to be optimized in planning. Several attempts
have been made to extend planners to also consider action costs.

The PYRRHUS system (Williams & Hanks, 1994) is an extension of UCPOP planning
which allows for optimal planning with resources and durations. Domain-dependent
knowledge can be added to direct the heuristic search. A "utility model"
has to be defined for a planning problem which can be used to express an
optimization function. This system supports a language extension of ADL (Pednault,
1989), which is a predecessor of PDDL (Ghallab et al., 1998). The algorithm
is a synthesis of branch-and-bound optimization with a least-commitment,
plan-space planner.

Other approaches based on heuristic search include the use of an A* strategy
together with action costs in the heuristics (Ephrati, Pollack, & Mihlstein,
1996) and work by Refanidis and Vlahavas who use multi-criteria heuristics
to obtain near-optimal plans, considering multiple criteria apart from plan
length alone (Refanidis & Vlahavas, 2001). However, the described heuristics
is not fully admissible, and only guarantees optimal plans under certain
restrictions (Haslum & Geffner, 2000). In fact, most heuristic state-space
planners are not able to guarantee optimality.

A powerful approach has been suggested by Nareyek, who describes planning
with resources as a structural constraint satisfaction problem (SCSP), and
then solves that problem by local search combined with global control. However,
this work promotes the inclusion of domain-dependent knowledge; the general
problem has an unlimited search space, and no declarative high-level language
is provided (Nareyek, 2001).

Among other related approaches, Kautz and Walser generalize the "Planning
as Satisfiability" approach to use integer optimization techniques for encoding
optimal planning under resource pro57

EITER, FABER, LEONE, PFEIFER & POLLERES 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 Kc to 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, Kc allows 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 Kc is that, via the underlying language K, states of knowledge,
i.e., incomplete states, can be suitably respected in secure plans, i.e.,
conformant plans

58

ANSWER SET PLANNING UNDER ACTION COSTS which work under all circumstances,
including nondeterministic action effects. Kc is 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 Kc to 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-2001- 33570 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.

59

EITER, FABER, LEONE, PFEIFER & POLLERES Appendix A. The Language K This appendix
contains, in shortened form, the definition of the language K and a translation
of K to answer set programs; see (Eiter et al., 2003b, 2003a) for more details
and examples.

A.1 Basic Syntax We assume oeact, oefl, and oetyp disjoint sets of action,
fluent and type names, respectively, i.e., predicate symbols of arity >=
0, and disjoint sets oecon and oevar of constant and variable symbols. Here,
oefl, oeact describe dynamic knowledge and oetyp describes static background
knowledge. An action (resp. fluent, type) atom is of form p(t1, . . . , tn),
where p 2 oeact (resp. oefl, oetyp) has arity n and t1, . . . , tn 2 oecon
[ oevar. An action (resp. fluent, type) literal l is an action (resp. fluent,
type) atom a or its negation ~a, where "~" (alternatively, "-") is the true
negation symbol. We define~

.l = a if l = ~a and ~.l = ~a if l = a, where a is an atom. A set L of literals
is consistent, if L " ~.L = ;. Furthermore, L+ (resp. L-) is the set of positive
(resp. negative) literals in L. The set of all action (resp. fluent, type)
literals is denoted as Lact (resp. Lfl, Ltyp). Furthermore, Lfl,typ = Lfl
[ Ltyp, Ldyn= Lfl [ L+act, and L = Lfl,typ [ L+act.

All actions and fluents must be declared using statements as follows.

Definition A.1 (action, fluent declaration) An action (resp. fluent) declaration,
is of the form:

p(X1, . . . , Xn) requires t1, . . . , tm (8) where p 2 L+act (resp. p 2
L+fl), X1, . . . , Xn 2 oevar where n >= 0 is the arity of p, t1, . . . ,
tm 2L

typ, m >= 0, and every Xi occurs in t1, . . . , tm.

If m = 0, the keyword requires may be omitted. Causation rules specify dependencies
of fluents on other fluents and actions.

Definition A.2 (causation rule) A causation rule (rule, for short) is an
expression of the form

caused f if b1, . . . , bk, not bk+1, . . . , not bl after a1, . . . , am,
not am+1, . . . , not an (9) where f 2 Lfl [{false}, b1, . . . , bl 2 Lfl,typ,
a1, . . . , anL, l >= k >= 0, and n >= m >= 0. Rules where n = 0 are static
rules, all others dynamic rules. When l = 0 (resp. n = 0), "if" (resp. "after")
is omitted; if both l = n = 0, "caused" is optional.

We access parts of a causation rule r by h(r) = {f }, post+(r) = {b1, . .
. , bk}, post-(r) ={ bk+1, . . . , bl}, pre+(r) = {a1, . . . , am}, pre-(r)
= {am+1, . . . , an}, and lit(r) = {f, b1, . . . , bl, a1, . . . , an}. Intuitively,
pre(r) = pre+(r) [ pre-(r) (resp. post(r) = post+(r) [ post-(r)) accesses
the state before (resp. after) some action(s) happen.

Special static rules may be specified for the initial states.

Definition A.3 (initial state constraint) An initial state constraint is
a static rule of the form (9) preceded by "initially."

The language K allows conditional execution of actions, where several alternative
executability conditions may be specified.

60

ANSWER SET PLANNING UNDER ACTION COSTS Definition A.4 (executability condition)
An executability condition e is an expression of the form

executable a if b1, . . . , bk, not bk+1, . . . , not bl (10) where a 2 L+act
and b1, . . . , bl 2 L, and l >= k >= 0. If l = 0 (i.e., executability is
unconditional), "if" is skipped. The parts of e are accessed by h(e) ={

a}, pre+(e) = {b1, . . . , bk}, pre-(e) = {bk+1, . . . , bl}, and lit(e)
= {a, b1, . . . , bl}. Intuitively, pre(e) = pre+(e) [ pre-(e) refers to
the state at which some action's suitability is evaluated. The state after
action execution is not involved; for convenience, we define post+(e) = post-(e)
= ;.

All causal rules and executability conditions must satisfy the following
condition, which is similar to safety in logic programs: Each variable in
a default-negated type literal must also occur in some literal which is not
a default-negated type literal. No safety is requested for variables appearing
in other literals. The reason is that variables appearing in fluent and action
literals are implicitly safe by the respective type declarations.

Notation. For any causal rule, initial state constraint, and executability
condition r and * 2 {post, pre, b}, we define *(r) = *+(r) [ *-(r), where
bs(r) = posts(r) [ pres(r).

A.1.1 PLANNING DOMAINS AND PLANNING PROBLEMS Definition A.5 (action description,
planning domain) An action description hD, Ri consists of a finite set D
of action and fluent declarations and a finite set R of safe causation rules,
safe initial state constraints, and safe executability conditions which do
not contain positive cyclic dependencies among actions. A K planning domain
is a pair PD = hPi , ADi, where Pi  is a disjunction-free normal Datalog
program (the background knowledge) which is safe and has a total well-founded
model (cf. (van Gelder, Ross, & Schlipf, 1991))8 and AD is an action description.
We call PD positive, if no default negation occurs in AD.

Definition A.6 (planning problem) A planning problem P = hPD, qi is a pair
of a planning do-main

PD and a query q, i.e.,

g1, . . . , gm, not gm+1, . . . , not gn ? (i) (11) where g1, . . . , gn
2 Lfl are variable-free, n >= m >= 0, and i >= 0 denotes the plan length.

A.2 Semantics We start with the preliminary definition of the typed instantiation
of a planning domain. This is similar to the grounding of a logic program,
with the difference being that only correctly typed fluent and action literals
are generated.

Let PD = hPi , hD, Rii be a planning domain, and let M be the (unique) answer
set of Pi  (Gelfond & Lifschitz, 1991). Then, `(p(X1, . . . , Xn)) is a
legal action (resp. fluent) instance of an action (resp. fluent) declaration
d 2 D of the form (8), if ` is a substitution defined over X1, . . . , Xn
such that {`(t1), . . . , `(tm)} ` M . By LPD we denote the set of all legal
action and fluent instances. The instantiation of a planning domain respecting
type information is as follows.

8. A total well-founded model, if existing, corresponds to the unique answer
set of a datalog program. Allowing for

multiple answer sets of Pi  would eventually lead to ambiguities in our
language.

61

EITER, FABER, LEONE, PFEIFER & POLLERES Definition A.7 (typed instantiation)
For any planning domain PD = hPi , hD, Rii, its typed instantiation is given
by PD# = hPi #, hD, R#ii, where Pi # is the grounding of Pi  (over oecon)
and R# = {`(r) | r 2 R, ` 2 Theta r}, where Theta r is the set of all substitutions
` of the variables in r using oecon, such that lit(`(r)) " Ldyn ` LPD [ (~.LPD
" L-fl).

In other words, in PD# we replace Pi  and R by their ground versions, but
keep of the latter only rules where the atoms of all fluent and action literals
agree with their declarations. We say that a PD = hPi , hD, Rii is ground,
if Pi  and R are ground, and moreover that it is well-typed, if PD and PD#
coincide.

A.2.1 STATES AND TRANSITIONS Definition A.8 (state, state transition) A state
w.r.t a planning domain PD is any consistent set s ` Lfl " (lit(PD) [ lit(PD)-)
of legal fluent instances and their negations. A state transition is any
tuple t = hs, A, s0i where s, s0 are states and A ` Lact " lit(PD) is a set
of legal action instances in PD.

Observe that a state does not necessarily contain either f or ~f for each
legal instance f of a fluent, and may even be empty (s = ;). State transitions
are not constrained; this will be done in the definition of legal state transitions
below. We proceed in analogy to the definition of answer sets (Gelfond &
Lifschitz, 1991), considering first positive (i.e., involving a positive
planning domain) and then general planning problems.

In what follows, we assume that PD = hPi , hD, Rii is a well-typed ground
planning domain and that M is the unique answer set of Pi . For any other
PD, the respective concepts are defined through its typed grounding PD#.

Definition A.9 (legal initial state) A state s0 is a legal initial state
for a positive PD, if s0 is the least set (w.r.t. `) such that post(c) `
s0 [ M implies h(c) ` s0, for all initial state constraints and static rules
c 2 R.

For a positive PD and a state s, a set A ` L+act is called executable action
set w.r.t. s, if for each a 2 A there exists an executability condition e
2 R such that h(e) = {a}, pre+(e)"Lfl,typ ` s[M , pre+(e)"L+act ` A, and
pre-(e)"(L+act [s[M ) = ;. Note that this definition allows for modeling
dependent actions, i.e. actions which depend on the execution of other actions.

Definition A.10 (legal state transition) Given a positive PD, a state transition
t = hs, A, s0i is called legal, if A is an executable action set w.r.t. s
and s0 is the minimal consistent set that satisfies all causation rules w.r.t.
s [ A [ M . That is, for every causation rule r 2 R, if (i) post(r) ` s0
[ M , (ii) pre(r) " Lfl,typ ` s [ M , and (iii) pre(r) " Lact ` A all hold,
then h(r) 6= {false} and h(r) ` s0.

This is now extended to general a well-typed ground PD containing default
negation using a Gelfond-Lifschitz type reduction to a positive planning
domain (Gelfond & Lifschitz, 1991).

Definition A.11 (reduction) Let PD be a ground and well-typed planning domain,
and let t =h

s, A, s0i be a state transition. Then, the reduction PDt = hPi , hD, Rtii
of PD by t is the planning domain where Rt is obtained from R by deleting

62

ANSWER SET PLANNING UNDER ACTION COSTS 1. each r 2 R, where either post-(r)"(s0
[ M ) 6= ; or pre-(r)"(s[A[M ) 6= ;, and 2. all default literals not L (L
2 L) from the remaining r 2 R.

Note that PDt is positive and ground. We extend further definitions as follows.
Definition A.12 (legal initial state, executable action set, legal state
transition) For any planning domain PD, a state s0 is a legal initial state,
if s0 is a legal initial state for PDh;,;,s0i; a set A is an executable action
set w.r.t. a state s, if A is executable w.r.t. s in PDhs,A,;i; and, a state
transition t = hs, A, s0i is legal, if it is legal in PDt.

A.2.2 PLANS Definition A.13 (trajectory) A sequence of state transitions
T = hhs0, A1, s1i, hs1, A2, s2i, . . .,h

sn-1, An, snii, n >= 0, is a trajectory for PD, if s0 is a legal initial
state of PD and all hsi-1, Ai, sii, 1 <= i <= n, are legal state transitions
of PD.

If n = 0, then T = hi is empty and has s0 associated explicitly.

Definition A.14 (optimistic plan) A sequence of action sets hA1, . . . ,
Aii, i >= 0, is an optimistic plan for a planning problem P = hPD, qi, if
a trajectory T = hhs0, A1, s1i, hs1, A2, s2i, . . . ,h

si-1, Ai, siii exists in PD which accomplishes the goal, i.e., {g1, . . .
gm} ` si and {gm+1, . . . , gn}" si = ;.

Optimistic plans amount to "plans", "valid plans" etc as defined in the literature.
The term "optimistic" should stress the credulous view in this definition,
with respect to incomplete fluent information and nondeterministic action
effects. In such cases, the execution of an optimistic plan P might fail
to reach the goal. We thus resort to secure plans.

Definition A.15 (secure plans (alias conformant plans)) An optimistic plan
hA1, . . . , Ani is a secure plan, if for every legal initial state s0 and
trajectory T = hhs0, A1, s1i, . . . , hsj-1, Aj, sjii such that 0 <= j <=
n, it holds that (i) if j = n then T accomplishes the goal, and (ii) if j
< n, then Aj+1 is executable in sj w.r.t. PD, i.e., some legal transition
hsj, Aj+1, sj+1i exists.

Note that plans admit in general the concurrent execution of actions. We
call a plan hA1, . . . , Ani sequential (or non-concurrent), if |Aj| <= 1,
for all 1 <= j <= n.

A.3 Macros K includes several macros as shorthands for frequently used concepts.
Let a 2 L+act denote an action atom, f 2 Lfl a fluent literal, B a (possibly
empty) sequence b1, . . . , bk, not bk+1, . . . , not bl where each bi 2
Lfl,typ, i = 1, . . . , l, and A a (possibly empty) sequence a1, . . . ,
am, not am+1, . . . , not an where each aj 2 L, j = 1, . . . , n.Inertia
To allow for an easy representation of fluent inertia, K provides

inertial f if B after A. , caused f if not ~.f, B after f, A. Defaults A
default value of a fluent can be expressed by the shortcut

default f. , caused f if not ~.f. It is in effect unless some other causation
rule provides evidence to the opposite value.

63

EITER, FABER, LEONE, PFEIFER & POLLERES Totality For reasoning under incomplete,
but total knowledge K provides (f positive):

total f if B after A. , caused f if not -f, B after A.caused -f if not f,
B after A. This is is for instance useful to model non-deterministic action
effects. For a discussion of the full impact of this statement in modeling
planning under incomplete knowledge and non-determinism, we refer to our
previous paper on the language K (Eiter et al., 2003b).

State Integrity For integrity constraints that refer to the preceding state,
K provides

forbidden B after A. , caused false if B after A.

Non-executability For specifying that some action is not executable, K provides

nonexecutable a if B. , caused false after a, B. By this definition, nonexecutable
overrides executable in case of conflicts.Sequential Plans To exclude simultaneous
execution of actions, K provides

noConcurrency. , caused false after a1, a2. where a1 and a2 range over all
possible actions such that a1, a2 2 LPD " Lact and a1 6= a2.

In all macros, "if B" (resp. "after A") can be omitted, if B (resp. A) is
empty.

Appendix B. Proofs Proof of Theorem 4.4: Membership (i): The problems are
in NP resp. NPMV, since if l is polynomial in the size of P, any optimistic
plan P = hA1, . . . , Ali for P with a supporting trajectory T = ht1, . .
. , tii for P can be guessed and, by Proposition 4.1, verified in polynomial
time. Furthermore, costP(P ) <= b can be efficiently checked, since costP(P
) is easily computed (all costs are constants). Hardness (i): K is a fragment
of Kc, and each K planning problem can be viewed as the problem of deciding
the existence of resp. finding an admissible plan wrt. cost 0. As was previously
shown (Eiter et al., 2003b), deciding existence of an optimistic plan for
a given K planning problem is NP-hard for fixed plan length l; hence, it
is also NP-hard for Kc.

We show that finding an optimistic plan is hard for NPMV by a reduction from
the well-known SAT problem, cf. (Papadimitriou, 1994), whose instances are
CNFs OE = c1 ^* * *^ck of clauses ci = Li,1 . * * * . Li,mi , where each
Li,j is a classical literal over propositional atoms X = {x1, . . . , xn}.

Consider the following planning domain PDOE for OE:

fluents : x1. . . . xn. state0. state1. actions : c1 costs 1. . . . ck costs
1.

ax1. . . . axn. initially : total x1. . . . total xn.

caused state0. always : caused state1 after state0.

executable c1 after ~.L1,1, . . . , ~.L1,m1. forbidden after ~.L1,1, . .
. , ~.L1,m1, not c1.* * *

executable ck after ~.Lk,1, . . . , ~.Lk,mk . forbidden after ~.Lk,1, . .
. , ~.Lk,mk , not ck. executable ax1 after x1. forbidden after x1, not ax1.*
* *

executable axn after xn. forbidden after xn, not axn.

64

ANSWER SET PLANNING UNDER ACTION COSTS The fluents xi and state0 and the
total statements in the initially-section encode the candidate truth assignments.
The subsequent statements force cj to be executed iff the corresponding clause
is violated by the truth assignment encoded in the initial state. The final
pairs of executable and forbidden statements force actions axi to be executed
iff the corresponding fluents xi hold. This is because it is necessary to
directly extract the computed truth assignments from the plan, since we are
dealing with a function class. The fluent state1 identifies the state at
time 1.

Consider now the planning problem POE = hPDOE, state1?(1)i. Clearly, each
optimistic plan P for P corresponds to a truth assignment oeP of X and vice
versa, and costPOE(P ) is the number of clauses violated by oeP . Thus, the
admissible optimistic plans for POE wrt. cost 0 correspond 1-1 to the satisfying
assignments of OE. Clearly, constructing POE from OE is efficiently possible,
as is constructing a satisfying truth assignment oe from a corresponding
plan P (because of the actions axi). This concludes the hardness proof. Membership
(ii): Since the security of each optimistic plan admissible wrt. cost k can
be checked, by Proposition 4.1, with a call to a Pi P2 -oracle, membership
in Sigma P3 resp. in Sigma P3 MV follows by analogous considerations as
in (i) (where no oracle was needed). Hardness (ii): For the decision variant,
Sigma P3 -hardness is again immediately inherited from the Sigma P3 - completeness
of deciding the existence of a secure plan of a problem in the language K,
with hardness even for fixed plan length (Eiter et al., 2003b). For the plan
computation variant, we give a reduction from the following Sigma P3 MV-complete
problem: An instance I is an open QBF

Q[Z] = 8X9Y Phi [X, Y, Z] where X = x1, . . . , xl, Y = y1, . . . , ym,
and Z = z1, . . . , zn, respectively, and Phi [X, Y, Z] is (w.l.o.g.) a
3CNF formula over X, Y , and Z. The solutions S(I) are all truth assignments
over Z for which Q[Z] is satisfied.

Suppose that Phi [X, Y, Z] = c1 ^ . . . ^ ck where ci = ci,1 . ci,2 . ci,3.
Now consider the following planning domain PDQ[Z] for Q[Z], which is a variant
of the planning domain given in the proof of Theorem 5.5 in (Eiter et al.,
2003b):

fluents : x1. . . . xl. y1. . . . ym. z1. . . . zn. state0. state1. actions
: az1 costs 0. . . . azn costs 0. initially : total x1. . . . total xl.

caused state0. always : caused state1 after state0.

executable az1. executable az2. . . . executable azn. caused x1 after x1.
caused - x1 after - x1.* * *

caused xl after xl. caused - xl after - xl. total y1 after state0. . . .
total ym after state0. caused z1 after az1. caused - z1 after not az1.* *
*

caused zn after azn. caused - zn after not azn. forbidden ~.C1,1, ~.C1,2,
~.C1,3 after state0.* * *

forbidden ~.Ck,1, ~.Ck,2, ~.Ck,3 after state0. There are 2|X| many legal
initial states s1, . . . , s2|

X| for PD

Q[Z], which correspond 1-1 to thepossible truth assignments to

X and all these initial states contain state0. Starting from any initial

state si, executing a set of actions represents a truth assignment to the
variables in Z. Since all

65

EITER, FABER, LEONE, PFEIFER & POLLERES actions are always executable, there
are 2|Z| executable action sets A1, . . . , A2|Z|, which represent all truth
assignments to Z.

For each pair si and Aj there exist 2|Y | many successor state candidates
si,1, . . . , si,2|

Y |, which

contain fluents according to the truth assignment to X represented by si,
fluents according to the truth assignment to Z represented by Aj, and fluents
according to a truth assignment to Y , and the fluent state1. Of these candidate
states, only those satisfying all clauses in Phi [X, Y, Z] are legal, by
virtue of the forbidden statements.

It is not hard to see that an optimistic plan of form P = hA1i (where A1
` {azi | zi 2 Z}) for the goal state1 exists wrt. PDQ[Z] iff there is an
assignment to all variables in X [ Y [ Z such that the formula Phi [X, Y,
Z] is satisfied. Furthermore, P is secure iff A1 represents an assignment
to the variables in Z such that, regardless of which assignment to the variables
in X is chosen (corresponding to a legal initial state si), there is some
assignment to the variables in Y such that all clauses of Phi [X, Y, Z]
are satisfied (i.e., there is at least one state si,k reachable from si by
executing A1); any such si,k contains state1. In other words, P is secure
iff Phi [X, Y, Z] is true. Thus, the admissible secure plans of PDQ[Z] wrt.
cost 0, correspond 1-1 with the assignments to Z for which Q[Z] is true.

Since PDQ[Z] is constructible from Phi [X, Y, Z] in polynomial time, it
follows that computing a secure plan for P = hPDQ[Z], qi, where q = state1
? (1), is Sigma P3 MV-hard. 2

Proof of Theorem 4.5: Membership (i): Concerning membership, by performing
a binary search on the range [0, max] (where max is an upper bound on the
plan costs for a plan of polynomial length l given by l times the sum of
all action costs) we can find out the least integer v such that any optimistic
plan P for P which is admissible wrt. cost v exists (if any optimistic plan
exists); clearly, we have costP(P ) = v and cost*P = v, and thus any such
plan P is optimal. Since max is single exponential in the representation
size of P, the binary search, and thus computing cost*P, is, by Theorem 4.4,
feasible in polynomial time with an NP oracle. Subsequently, we can construct
an optimistic plan P such that costP (P ) = cost*P by extending a partial
plan Pi = hA1, . . . , Aii, i = 0, . . . , l - 1 step by step as follows.
Let A = {a1, . . . , am} be the set of all legal action instances. We initialize
Bi+1 := A and ask the oracle whether Pi can be completed to an optimistic
plan P = hA1, . . . , Ali admissible wrt. cost*P such that Ai+1 ` (Bi+1 
{a1}). If the answer is yes, then we update Bi+1 := Bi+1  {a1}, else we
leave Bi+1 unchanged. We then repeat this test for aj, j = 2, 3, . . . ,
m; the resulting Bi+1 is an action set such that Pi+1 = hA1, . . . , Ai,
Ai+1i where Ai+1 = Bi+1 can be completed to an optimistic plan admissible
wrt. cost*P. Thus, Ai+1 is polynomial-time constructible with an NP oracle.
In summary, we can construct an optimal optimistic plan in polynomial time
with an NP oracle. Thus, the problem is in FDelta P2 . Hardness (i): We
show hardness for plan length l = 1 by a reduction from problem MAX WEIGHT
SAT (Papadimitriou, 1994), where an instance is a SAT instance OE = c1 ^
* * * ^ ck as in the proof of Theorem 4.4.(i), plus positive integer weights
wi, where i = 1, . . . , k. Then, S(I) contains those truth assignments oe
of X for which wsat(oe) = Pi : cioe=true wi is maximal.

To that end, we take the planning domain PDOE as in the proof of Theorem
4.4 and modify the cost of ci to wi, for i = 1, . . . , k, thus constructing
a new planning domain PDI . Consider now the planning problem PI = hPDI ,
state1?(1)i. Since the actions cj are the only actions with nonzero cost,
any plan (corresponding to a truth assignment oe) will be associated with
the sum of weights of violated clauses, wvio(oe) = (Pki=1 wi) - wsat(oe).
Since Pki=1 wi is constant for I, minimizing

66

ANSWER SET PLANNING UNDER ACTION COSTS wvio(oe) is equivalent to maximizing
wsat(oe). Hence, there is a one-to-one correspondence between optimal optimistic
plans of PI (for which wvio(oe) is minimal) and maximal truth assignments
for I. Furthermore, computing PI from I and extracting a MAX-WEIGHT SAT solution
from an optimal plan P is efficiently possible. This proves FDelta P2 -hardness.
Membership (ii): The proof is similar to the membership proof of (i), but
uses an oracle which asks for completion of a partial secure plan Pi = hA1,
. . . , Aii to a secure plan P = hA1, . . . , Ali such that Ai+1 ` (Bi+1
 {aj}) and P is admissible wrt. cost*P , rather than of a partial optimistic
plan. This oracle is, as easily seen, in Sigma P3 . Thus, computing an optimal
secure plan is in FDelta P4 . Hardness (ii): We show hardness by a reduction
from the following problem, which is FDelta P4 - complete (cf. (Krentel,
1992)): Given an open QBF Q[Z] = 8X9Y Phi [X, Y, Z] like in the proof of
Theorem 4.4.(ii), compute the lexicographically first truth assignment of
Z for which Q[Z] is satisfied.

This can be accomplished by changing the cost of each action azi in PDQ[Z]
from 0 to 2n-i, i = 1, . . . , n. Let PD0[Q[Z]] be the resulting planning
domain. Since the cost of azi (i.e., assigning zi the value true) is greater
than the sum of the costs of all azj for i + 1 <= j <= n, an optimal secure
plan for the planning problem hPD0[Q[Z]], state1 ? (1)i amounts to the lexicographically
first truth assignment for Z such that Q[Z] is satisfied. Thus, FDelta P4
-hardness of the problem follows. 2

Proof of Theorem 6.1: We prove the result by applying the well-known Splitting
Set Theorem for logic programs (Lifschitz & Turner, 1994). This theorem applies
to logic programs ss that can be split into two parts such that one of them,
the "bottom" part, does not refer to predicates defined in the "top" part
at all. The answer sets of the "bottom" part can then be extended to the
answer sets of the whole program by looking at the remaining ("top") rules.
Informally, a splitting set of ss is a set U of ground literals defining
the "bottom" part bU (ss) of a program. Each answer set Sb of bU (ss) can
then be used to reduce the remaining rules ss  bU (ss) to a program eU (ss
 bU (ss), Sb) involving only classical literals which do not occur in bU
(ss), by evaluating the literals from bU (ss) wrt. Sb. For each answer set
Se of eU (ss  bU (ss), Sb), the set S = Sb [ Se then is an answer set of
the original program.

Disregarding weak constraints, we can split the program lpw(P) into a bottom
part consisting of lp(Pnc), where Pnc is P with the cost information stripped
off, and a top part containing the remaining rules; we then derive the correspondence
between optimistic plans for P and answer sets of lpw(P) from a similar correspondence
result for lp(Pnc) (Eiter et al., 2003a).

In detail, Theorem 3.1 in (Eiter et al., 2003a) states for any K-planning
problem P a correspondence between the answer sets S of lp(P) and supporting
trajectories T of optimistic plans P = hA1, . . . , Ali as in items (i) and
(ii), with costs discarded. Thus, any answer set S0 of lp(Pnc) corresponds
to some trajectory T 0 of an optimistic plan P 0 for Pnc and vice versa.

In what follows, when talking about lp(Pnc) and lpw(P), we mean the respective
grounded logic programs. lpw(P) augments lp(Pnc) by rules (4) and weak constraints
(5). Let now U = lit(lp(Pnc)) be the set of all literals occurring in lp(Pnc).
Clearly, U splits lpw(P) as defined in (Lifschitz & Turner, 1994), where
we disregard weak constraints in lpw(P), since the rules of form (4) introduce
only new head literals. Consequently, we get bU (lpw(P)) = lp(Pnc). Then,
for any answer set S0 of lp(Pnc), each rule in eU (lpw(P)  bU (lpw(P)),
S0) is of the form

costa(x1, . . . , xn, t, c) :- Body.

67

EITER, FABER, LEONE, PFEIFER & POLLERES From the fact that all these rules
are positive, we can conclude that with respect to the split by U , any answer
set S0 of lp(Pnc) induces a unique answer set S ' S0 of lpw(P). Therefore,
modulo costs, a correspondence between supporting trajectories T and candidate
answer sets S as claimed follows directly from Theorem 3.1 in (Eiter et al.,
2003a).

It remains to prove that costP (P ) = costlpw(P) (S) holds for all candidate
answer sets S corresponding to an optimistic plan P = hA1, . . . , Ali for
P. By the correspondence shown above, any action p(x1, . . . , xn) 2 Aj corresponds
to exactly one atom p(x1, . . . , xn, j - 1) 2 ASj , j 2 {1, . . . , l}.
Therefore, if p(x1, . . . , xn) is declared with a non-empty cost part, by
(4) and well-definedness, modulo x1, . . . , xn, there is exactly one fact
costp(x1, . . . , xn, j - 1, c) in the model of eU (lpw(P)  bU (lpw(P)),
S).

Furthermore, by definition of (4), we have that c = costj(p(x1, . . . , xn)),
i.e., the cost of action instance p(x1, . . . , xn) at time j. Consequently,
the violation value of the weak constraint wc of form (5) for p in lpw(P)
is costwc(S) = Plj=1 Pp(x1,...,xn)2Aj costj(p(x1, . . . , xn)). Since all
violation values stem from weak constraints (5), in total we have costlpw(P)
(S) = costP(P ). This proves the result. 2

References Blum, A. L., & Furst, M. L. (1997). Fast Planning Through Planning
Graph Analysis. Artificial

Intelligence, 90, 281-300.

Bonet, B., & Geffner, H. (2000). Planning with Incomplete Information as
Heuristic Search in

Belief Space. In Chien, S., Kambhampati, S., & Knoblock, C. A. (Eds.), Proceedings
of the Fifth International Conference on Artificial Intelligence Planning
and Scheduling (AIPS'00), pp. 52-61, Breckenridge, Colorado, USA.

Bryant, R. E. (1986). Graph-based algorithms for boolean function manipulation.
IEEE Transactions on Computers, C-35(8), 677-691.

Buccafurri, F., Leone, N., & Rullo, P. (1997). Strong and Weak Constraints
in Disjunctive Datalog.

In Dix, J., Furbach, U., & Nerode, A. (Eds.), Proceedings of the 4th International
Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'97), No.
1265 in Lecture Notes in AI (LNAI), pp. 2-17, Dagstuhl, Germany. Springer
Verlag.

Buccafurri, F., Leone, N., & Rullo, P. (2000). Enhancing Disjunctive Datalog
by Constraints. IEEE

Transactions on Knowledge and Data Engineering, 12(5), 845-860.

Cimatti, A., & Roveri, M. (2000). Conformant Planning via Symbolic Model
Checking. Journal of

Artificial Intelligence Research, 13, 305-338.

Dantsin, E., Eiter, T., Gottlob, G., & Voronkov, A. (2001). Complexity and
Expressive Power of

Logic Programming. ACM Computing Surveys, 33(3), 374-425.

Dimopoulos, Y., Nebel, B., & Koehler, J. (1997). Encoding Planning Problems
in Nonmonotonic

Logic Programs. In Proceedings of the European Conference on Planning 1997
(ECP-97), pp. 169-181. Springer Verlag.

Eiter, T., Faber, W., Leone, N., & Pfeifer, G. (2000a). Declarative Problem-Solving
Using the

DLV System. In Minker, J. (Ed.), Logic-Based Artificial Intelligence, pp.
79-103. Kluwer Academic Publishers.

68

ANSWER SET PLANNING UNDER ACTION COSTS Eiter, T., Faber, W., Leone, N., Pfeifer,
G., & Polleres, A. (2000b). Planning under Incomplete

Knowledge. In Lloyd, J., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Palamidessi,
C., Pereira, L. M., Sagiv, Y., & Stuckey, P. J. (Eds.), Computational Logic
- CL 2000, First International Conference, Proceedings, No. 1861 in Lecture
Notes in AI (LNAI), pp. 807-821, London, UK. Springer Verlag.

Eiter, T., Faber, W., Leone, N., Pfeifer, G., & Polleres, A. (2002a). Answer
Set Planning under

Action Costs. In Flesca, S., Greco, S., Ianni, G., & Leone, N. (Eds.), Proceedings
of the 8th European Conference on Artificial Intelligence (JELIA), No. 2424
in Lecture Notes in Computer Science, pp. 186-197.

Eiter, T., Faber, W., Leone, N., Pfeifer, G., & Polleres, A. (2002b). Answer
Set Planning under Action Costs. Tech. rep. INFSYS RR-1843-02-13, Institut
f"ur Informationssysteme, Technische Universit"at Wien.

Eiter, T., Faber, W., Leone, N., Pfeifer, G., & Polleres, A. (2003a). A Logic
Programming Approach

to Knowledge-State Planning, II: the DLVK System. Artificial Intelligence,
144(1-2), 157- 211.

Eiter, T., Faber, W., Leone, N., Pfeifer, G., & Polleres, A. (2003b). A Logic
Programming Approach

to Knowledge-State Planning: Semantics and Complexity. To appear in ACM Transactions
on Computational Logic.

Ephrati, E., Pollack, M. E., & Mihlstein, M. (1996). A Cost-directed Planner:
Preliminary Report.

In Proceedings of the Thirteenth National Conference on Artificial Intelligence
(AAAI-96), pp. 1223 - 1228. AAAI Press.

Erdem, E. (1999). Applications of Logic Programming to Planning: Computational
Experiments.

Unpublished draft. http://www.cs.utexas.edu/users/esra/papers.html.

Faber, W., & Pfeifer, G. (since 1996). DLV homepage.. http://www.dlvsystem.com/.
Ferraris, P., & Giunchiglia, E. (2000). Planning as Satisfiability in Nondeterministic
Domains. In

Proceedings of the Seventeenth National Conference on Artificial Intelligence
(AAAI'00), July 30 - August 3, 2000, Austin, Texas USA, pp. 748-753. AAAI
Press / The MIT Press.

Fourer, R., Gay, D. M., & Kernighan, B. W. (1993). AMPL: A Modeling Language
for Mathematical

Programming. Duxbury Press.

Gelfond, M., & Lifschitz, V. (1991). Classical Negation in Logic Programs
and Disjunctive

Databases. New Generation Computing, 9, 365-385.

Ghallab, M., Howe, A., Knoblock, C., McDermott, D., Ram, A., Veloso, M.,
Weld,

D., & Wilkins, D. (1998). PDDL -- The Planning Domain Definition language.
Tech. rep., Yale Center for Computational Vision and Control. Available at
http://www.cs.yale.edu/pub/mcdermott/software/pddl.tar.gz.

Giunchiglia, E. (2000). Planning as Satisfiability with Expressive Action
Languages: Concurrency,

Constraints and Nondeterminism. In Cohn, A. G., Giunchiglia, F., & Selman,
B. (Eds.), Proceedings of the Seventh International Conference on Principles
of Knowledge Representation and Reasoning (KR 2000), April 12-15, Breckenridge,
Colorado, USA, pp. 657-666. Morgan Kaufmann.

69

EITER, FABER, LEONE, PFEIFER & POLLERES Giunchiglia, E., Kartha, G. N., &
Lifschitz, V. (1997). Representing Action: Indeterminacy and

Ramifications. Artificial Intelligence, 95, 409-443.

Giunchiglia, E., & Lifschitz, V. (1998). An Action Language Based on Causal
Explanation: Preliminary Report. In Proceedings of the Fifteenth National
Conference on Artificial Intelligence (AAAI '98), pp. 623-630.

Haslum, P., & Geffner, H. (2000). Admissible Heuristics for Optimal Planning.
In Chien, S., Kambhampati, S., & Knoblock, C. A. (Eds.), Proceedings of the
Fifth International Conference on Artificial Intelligence Planning and Scheduling
(AIPS'00), pp. 140-149, Breckenridge, Colorado, USA. AAAI Press.

Kautz, H., & Walser, J. P. (1999). State-space planning by integer optimization.
In Proceedings of

the 16th National Conference on Artificial Intelligence (AAAI-99), pp. 526-533.

Koehler, J. (1998). Planning Under Resource Constraints. In Proceedings of
the 13th European

Conference on Artificial Intelligence (ECAI'98), pp. 489-493.

Krentel, M. (1992). Generalizations of Opt P to the Polynomial Hierarchy.
Theoretical Computer

Science, 97(2), 183-198.

Lee, J., & Lifschitz, V. (2001). Additive Fluents. In Provetti, A., & Cao,
S. T. (Eds.), Proceedings

AAAI 2001 Spring Symposium on Answer Set Programming: Towards Efficient and
Scalable Knowledge Representation and Reasoning, pp. 116-123, Stanford, CA.
AAAI Press.

Lifschitz, V., & Turner, H. (1994). Splitting a Logic Program. In Van Hentenryck,
P. (Ed.), Proceedings of the 11th International Conference on Logic Programming
(ICLP'94), pp. 23-37, Santa Margherita Ligure, Italy. MIT Press.

Lifschitz, V., & Turner, H. (1999). Representing Transition Systems by Logic
Programs. In Gelfond,

M., Leone, N., & Pfeifer, G. (Eds.), Proceedings of the 5th International
Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99), No.
1730 in Lecture Notes in AI (LNAI), pp. 92-106, El Paso, Texas, USA. Springer
Verlag.

Lifschitz, V. (1996). Foundations of Logic Programming. In Brewka, G. (Ed.),
Principles of Knowledge Representation, pp. 69-127. CSLI Publications, Stanford.

Lifschitz, V. (1999a). Action Languages, Answer Sets and Planning. In Apt,
K., Marek, V. W.,

Truszczy'nski, M., & Warren, D. S. (Eds.), The Logic Programming Paradigm
- A 25-Year Perspective, pp. 357-373. Springer Verlag.

Lifschitz, V. (1999b). Answer Set Planning. In Schreye, D. D. (Ed.), Proceedings
of the 16th

International Conference on Logic Programming (ICLP'99), pp. 23-37, Las Cruces,
New Mexico, USA. The MIT Press.

McCain, N. (1999). The Causal Calculator Homepage.. http://www.cs.utexas.edu/

users/tag/cc/.

McCain, N., & Turner, H. (1997). Causal Theories of Actions and Change. In
Proceedings of the

15th National Conference on Artificial Intelligence (AAAI-97), pp. 460-465.

McCain, N., & Turner, H. (1998). Satisfiability Planning with Causal Theories.
In Cohn, A. G.,

Schubert, L., & Shapiro, S. C. (Eds.), Proceedings Sixth International Conference
on Principles of Knowledge Representation and Reasoning (KR'98), pp. 212-223.
Morgan Kaufmann Publishers.

70

ANSWER SET PLANNING UNDER ACTION COSTS Moskewicz, M. W., Madigan, C. F.,
Zhao, Y., Zhang, L., & Malik, S. (2001). Chaff: Engineering an

Efficient SAT Solver. In Proceedings of the 38th Design Automation Conference,
DAC 2001, Las Vegas, NV, USA, June 18-22, 2001, pp. 530-535. ACM.

Nareyek, A. (2001). Beyond the Plan-Length Criterion. In Local Search for
Planning and Scheduling, ECAI 2000 Workshop, Vol. 2148 of Lecture Notes in
Computer Science, pp. 55-78. Springer.

Niemel"a, I. (1998). Logic Programs with Stable Model Semantics as a Constraint
Programming

Paradigm. In Niemel"a, I., & Schaub, T. (Eds.), Proceedings of the Workshop
on Computational Aspects of Nonmonotonic Reasoning, pp. 72-79, Trento, Italy.

Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley. Pednault,
E. P. D. (1989). Exploring the Middle Ground between STRIPS and the Situation
Calculus. In Proceedings of the 1st International Conference on Principles
of Knowledge Representation and Reasoning (KR'89), pp. 324-332, Toronto,
Canada. Morgan Kaufmann Publishers, Inc.

Refanidis, I., & Vlahavas, I. (2001). A Framework for Multi-Criteria Plan
Evaluation in Heuristic

State-Space Planning. In IJCAI-01 Workshop on Planning with Resources.

Selman, A. L. (1994). A Taxonomy of Complexity Classes of Functions. Journal
of Computer and

System Sciences, 48(2), 357-381.

Simons, P., Niemel"a, I., & Soininen, T. (2002). Extending and Implementing
the Stable Model

Semantics. Artificial Intelligence, 138, 181-234.

Smith, D. E., & Weld, D. S. (1998). Conformant Graphplan. In Proceedings
of the Fifteenth

National Conference on Artificial Intelligence, (AAAI'98), pp. 889-896. AAAI
Press / The MIT Press.

Son, T. C., & Pontelli, E. (2002). Reasoning About Actions in Prioritized
Default Theory. In Flesca,

S., Greco, S., Ianni, G., & Leone, N. (Eds.), Proceedings of the 8th European
Conference on Artificial Intelligence (JELIA), No. 2424 in Lecture Notes
in Computer Science, pp. 369-381.

Subrahmanian, V., & Zaniolo, C. (1995). Relating Stable Models and AI Planning
Domains. In

Sterling, L. (Ed.), Proceedings of the 12th International Conference on Logic
Programming, pp. 233-247, Tokyo, Japan. MIT Press.

van Gelder, A., Ross, K., & Schlipf, J. (1991). The Well-Founded Semantics
for General Logic

Programs. Journal of the ACM, 38(3), 620-650.

Weld, D. S., Anderson, C. R., & Smith, D. E. (1998). Extending Graphplan
to Handle Uncertainty

& Sensing Actions. In Proceedings of the Fifteenth National Conference on
Artificial Intelligence, (AAAI'98), pp. 897-904. AAAI Press / The MIT Press.

Williams, M., & Hanks, S. (1994). Optimal Planning with a Goal-Directed Utility
Model. In

Hammond, K. J. (Ed.), Proceedings of the Second International Conference
on Artificial Intelligence Planning Systems (AIPS-94), pp. 176-181. AAAI
Press.

71