\documentclass[twoside,11pt]{article}
\usepackage{jair}
\usepackage{theapa}

\usepackage{theorem}
\usepackage{epsfig}
\usepackage{xspace}\usepackage{times}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{url}

\jairheading{19}{2003}{25-71}{10/02}{08/03}
\firstpageno{25}
\ShortHeadings{Answer Set Planning Under Action Costs}
{Eiter, Faber, Leone, Pfeifer \& Polleres}

% Switch for report-text / paper-text 
\newif\ifreport
%\reporttrue

%\theorembodyfont{\rmfamily}

\newenvironment{changemargin}{%
 \begin{list}{}{%
  \setlength{\topsep}{0pt}%
  %\setlength{\leftmargin}{#1}%
  \setlength{\leftmargin}{2em}
  %\setlength{\rightmargin}{#2}%
  %\setlength{\listparindent}{\parindent}%
  \setlength{\listparindent}{0pt}%
  %\setlength{\itemindent}{\parindent}%
  \setlength{\itemindent}{0pt}%
  %\setlength{\parsep}{\parskip}%
  \setlength{\parsep}{0pt}%
 }%
\item[]}{\end{list}}


\newtheorem{problem}{Problem}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{definition}{Definition}[section]

\newenvironment{proof}{\noindent{\it Proof.\ }}{\hfill$\Box\,$} 


%\newtheorem{zdefinition}{Definition}[section]
%\newenvironment{definition}[1][\mbox{}]{\begin{zdefinition}\begin{rm}#1}{\end{rm}\end{zdefinition}}

%\newtheorem{zexample}{Example}[section]
%\newenvironment{example}[1][\mbox{}]{\begin{zexample}\begin{rm}#1}{\end{rm}\end{zexample}}

\newcommand{\nop}[1]{}
\newcommand{\TODO}[1]{{\large\bf TODO: }#1\ensuremath{\Box}}

% numbers
\def\Nat{\mbox{\rm I\hspace{-0.2em}N}}
\def\Real{\mbox{\rm I\hspace{-0.2em}R}}
\def\Int{\mbox{\sf Z\hspace{-0.45em}Z}}
\def\Rat{\mbox{\rm\hspace{0.2em}\rule[.1ex]{.05em}{1.37ex}\hspace{-0.27em}Q}}
\def\Complex{\mbox{\rm\hspace{0.2em}\rule[.1ex]{.05em}{1.37ex}\hspace{-0.27em}C}}

%complexity stuff
 \newcommand{\NP}{\mathrm{NP}}
 \newcommand{\NPMV}{\mathrm{NPMV}}
 \newcommand{\FP}{\mathrm{FP}}
 \newcommand{\FPNP}{\FP^{\NP}}
 \newcommand{\coNP}{\textrm{co-}\NP}
 \newcommand{\CONP}{\coNP}
 \newcommand{\SigmaP}[1]{{\Sigma}_{#1}^{P}}
 \newcommand{\SigmaPMV}[1]{{\Sigma}_{#1}^{P}\mathrm{MV}}
 \newcommand{\PiP}[1]{{\Pi}_{#1}^{P}}
 \newcommand{\DeltaP}[1]{{\Delta}_{#1}^{P}}
 \newcommand{\FDeltaP}[1]{\mathrm{F}\DeltaP{#1}}
 \newcommand{\Pol}{\mathrm{P}}
 \newcommand{\DP}{\mathrm{D}^{P}}
 \newcommand{\PSPACE}{\mathrm{PSPACE}} 

%the translated logic program for a planning problem
\newcommand{\LPP}[1][ ]{\ensuremath{lp(\PP)_{#1}}\xspace} 
\newcommand{\LPPw}[1][ ]{\ensuremath{lp^w(\PP)_{#1}}\xspace} 
\newcommand{\LPPwsc}[1][ ]{\ensuremath{lp^w_{sc}(\p)_{#1}}\xspace}

\newcommand{\dlv}{\texttt{\small DLV}\xspace}
\newcommand{\dlvk}{\ensuremath{\dlv^{\K}}\xspace}
\newcommand{\dlvkinc}{\ensuremath{\dlv^{\K}_{inc}}\xspace}

\newcommand{\K}{\ensuremath{\cal K}\xspace}
\newcommand{\Kc}{\ensuremath{\mathcal{K}^c}\xspace}

\newcommand{\inlinek}[1]{\ensuremath{\mathtt{#1}}}
% Strong (true) and weak (default) negation
\newcommand{\tneg}{\ensuremath{\neg}}
\newcommand{\TNEG}{\textrm{-}}
\newcommand{\dnegsymbol}{\ensuremath{\mathtt{not}}}
\newcommand{\dneg}[1]{\ensuremath{\mathtt{not}\ }#1}
\newcommand{\naf}{\ensuremath{\mathtt{not}}\xspace}
\newcommand{\Or}{\ensuremath{\ \mathtt{v}\ }}
\newcommand{\derives}{\mbox{\texttt{:\hspace{-0.15em}-}}\xspace}
\newcommand{\wc}{\ensuremath{:\sim}}
\newcommand{\kuneq}{\ensuremath{\mathtt{\,!\!\!=}\,}}

\newcommand{\grd}{\ensuremath{ground}}

\newcommand{\GR}{\ensuremath{\grd(\R)}}
\newcommand{\HR}{\ensuremath{H(\R)}}
\newcommand{\BR}{\ensuremath{B(\R)}}
\newcommand{\BpR}{\ensuremath{B^+(\R)}}
\newcommand{\BnR}{\ensuremath{B^-(\R)}}

\newenvironment{kprogram}[1][]
{\begin{changemargin}
    \tt\small
    \begin{tabbing}
      \phantom{\inlinek{initially:}\ }\= \kill
      }
{\end{tabbing}\end{changemargin}\vspace{-2.5ex}}
% K program item
\newcommand{\kpi}[2]{\inlinek{#1}\>\inlinek{#2}\\}

\newcommand{\kpl}[1]{\ensuremath{\p_{#1}=\inlinek{\langle}}}

\newenvironment{kplan}[1][]
{\tt\small
\begin{tabbing}
\phantom{\kpl{1}\,}\=\kill
}
{\end{tabbing}\vspace{-2.5ex}}
% K plan item:
\newcommand{\kpli}[2]{#1\>\inlinek{#2}\\}

% Background Knowledge
\newenvironment{bgprogram}[1][]
{\begin{changemargin}
 \small\vspace*{0.8ex}
}
{\end{changemargin}
 \vspace*{-1.8ex}
}

%Background Knowledge item
\newcommand{\bgpi}[1]{\inlinek{#1}\\}

% Strong complement ``function''
\newcommand{\tcomp}[1]{\tneg.#1}

% Sometimes we need to tag something as being fluent, action, or type.
\newcommand{\actiontag}{act}
\newcommand{\fluenttag}{fl}
\newcommand{\typetag}{typ}
\newcommand{\dynamictag}{dyn}

% Sets of fluent, action, type, constant, and variable symbols
\newcommand{\symbolset}[1]{\ensuremath{\sigma^{#1}}}
\newcommand{\acts}{\symbolset{\actiontag}\xspace}
\newcommand{\fls}{\symbolset{\fluenttag}\xspace}
\newcommand{\typs}{\symbolset{\typetag}\xspace}
\newcommand{\consts}{\symbolset{con}\xspace}
\newcommand{\vars}{\symbolset{var}\xspace}

% Sets of fluent, action, type, dynamic, and general literals
\newcommand{\literalset}[1]{\ensuremath{{\cal L}_{#1}}}
\newcommand{\lact}{\literalset{\actiontag}\xspace}
\newcommand{\lfl}{\literalset{\fluenttag}}
\newcommand{\ltyp}{\literalset{\typetag}}
\newcommand{\lfltyp}{\literalset{\fluenttag,\typetag}}
\newcommand{\ldyn}{\literalset{\dynamictag}}
\newcommand{\lgen}{\literalset{}}

\newcommand{\positive}[1]{#1\ensuremath{^+}}
\newcommand{\negative}[1]{#1\ensuremath{^-}}

\newcommand{\head}[1]{\ensuremath{\mathsf{h}(}#1\ensuremath{)}}
\newcommand{\post}[1]{\ensuremath{\mathsf{post}(}#1\ensuremath{)}}
\newcommand{\ppost}[1]{\ensuremath{\mathsf{post}^+(}#1\ensuremath{)}}
\newcommand{\npost}[1]{\ensuremath{\mathsf{post}^-(}#1\ensuremath{)}}
\newcommand{\pre}[1]{\ensuremath{\mathsf{pre}(}#1\ensuremath{)}}
\newcommand{\ppre}[1]{\ensuremath{\mathsf{pre}^+(}#1\ensuremath{)}}
\newcommand{\npre}[1]{\ensuremath{\mathsf{pre}^-(}#1\ensuremath{)}}
\newcommand{\body}[1]{\ensuremath{\mathsf{b}(}#1\ensuremath{)}}
\newcommand{\pbody}[1]{\ensuremath{\mathsf{b}^+(}#1\ensuremath{)}}
\newcommand{\nbody}[1]{\ensuremath{\mathsf{b}^-(}#1\ensuremath{)}}
\newcommand{\literals}[1]{\ensuremath{\mathsf{lit}(}#1\ensuremath{)}}

\newcommand{\tuple}[1]{\ensuremath{\langle}#1\ensuremath{\rangle}}
\newcommand{\set}[1]{ \{ #1 \} }

\newcommand{\ground}[1]{\mbox{\ensuremath{#1\!\!\downarrow}}}

\newcommand{\PP}[1][ ]{\ensuremath{\mathcal{P}_{#1}}\xspace} % planning problem
\newcommand{\PD}[1][ ]{\ensuremath{P\!D_{#1}}\xspace} % planning domain
\newcommand{\AD}[1][ ]{\ensuremath{A\!D_{#1}}\xspace} % action description
\newcommand{\q}[1][ ]{\ensuremath{q_{#1}}\xspace} % goal
\newcommand{\p}{\ensuremath{P}\xspace} % plan
\renewcommand{\P}{\p}

\newcommand{\BK}[1][ ]{\ensuremath{\Pi_{#1}}\xspace} % background knowledge
\newcommand{\D}[1][ ]{\ensuremath{D_{#1}}\xspace} % declarations
\newcommand{\DA}[1][ ]{\ensuremath{A_{\D[#1]}}\xspace} % action declaration
\newcommand{\DF}[1][ ]{\ensuremath{F_{\D[#1]}}\xspace} % fluent declaration
\newcommand{\R}[1][ ]{\ensuremath{R_{#1}}\xspace} % rules
\newcommand{\RC}[1][ ]{\ensuremath{C_{\R[#1]}}\xspace} % 'always' rules
\newcommand{\RI}[1][ ]{\ensuremath{I_{\R[#1]}}\xspace} % 'initially' rules

 % AD definition with D and R as parameters
 \newcommand{\ADtupleDR}[2]{\tuple{#1,#2}}
 % AD definition with default names (with optional subscript)
 \newcommand{\ADtupleDRdef}[1][]{\ADtupleDR{\D[#1]}{\R[#1]}}
 % PD definition with BK and AD as parameters
 \newcommand{\PDtupleBKAD}[2]{\tuple{#1,#2}}
 % PD definition with BK and AD and default names (with optional subscript)
 \newcommand{\PDtupleBKADdef}[1][ ]{\PDtupleBKAD{\BK[#1]}{\AD[#1]}}
 % PD definition with BK, D and R as parameters 
 \newcommand{\PDtupleBKDR}[3]{\tuple{#1,\ADtupleDR{#2}{#3}}}
 % PD definition with BK, D and R with default names (with optional subscript)
 \newcommand{\PDtupleBKDRdef}[1][ ]{\PDtupleBKAD{\BK[#1]}{\ADtupleDRdef[#1]}}

\newcommand{\plancost}[2]{\ensuremath{cost_{#1}(#2)}}
\newcommand{\optcost}[1]{\ensuremath{cost^{*}_{#1}}}
\newcommand{\seccost}[1]{\ensuremath{cost_{sec}^*(#1)}}

\def\qed{\relax\ifmmode\hskip2em \Box\else\unskip\nobreak\hskip1em $\Box$\fi}

\begin{document}

\title{Answer Set Planning Under Action Costs}

\author{%
\name Thomas Eiter \email eiter@kr.tuwien.ac.at\\
\name Wolfgang Faber \email faber@kr.tuwien.ac.at\\
\addr Institut f{\"u}r Informationssysteme, TU Wien\\
Favoritenstr. 9-11, A-1040 Wien, Austria
%
\AND 
%
\name Nicola Leone \email leone@unical.it\\
\addr Department of Mathematics, University of Calabria\\
I-87030 Rende (CS), Italy
%
\AND
%
\name Gerald Pfeifer \email pfeifer@dbai.tuwien.ac.at\\
\name Axel Polleres \email polleres@kr.tuwien.ac.at\\
\addr Institut f{\"u}r Informationssysteme, TU Wien\\
Favoritenstr. 9-11, A-1040 Wien, Austria
}
%
% the next line MUST come first 
%
\maketitle

\begin{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.
\end{abstract}

\medskip

%\noindent{\bf Keywords:}  answer set planning, optimal plans, conformant plans,
%logic-based AI, logic programming, expressive planning formalisms,
%knowledge representation, non-monotonic reasoning.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sc:intro}

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.,
\shortciteR{giun-lifs-98,lifs-99a,lifs-turn-99,mcca-turn-98,giun-2000,cima-rove-2000,eite-etal-2000d,eite-etal-2001d}).

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 \cite{cima-rove-2000} and
GPT \cite{bone-geff-2000} compute shortest plans in which each step
consists of a single action, while the Graphplan algorithm
\cite{blum-furs-97} and descendants \cite{smit-weld-98,weld-etal-98}
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 that plan. 

In answer set planning~\cite{subr-zani-96,dimo-etal-97,niem-98,lifs-99a},
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~\ref{sec:rel-works} for more details). In this paper, we
address this issue and present an extension of the planning language
\K \cite{eite-etal-2000d,eite-etal-2001d}, 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.

\begin{itemize}
\item 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.

\item 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.

\item 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
\url{http://www.dlvsystem.com/K/}.

\item 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.    
\end{itemize}

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 \emph{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 tasks can be 
specified and solved.
This work complements and extends the preliminary results presented 
in our previous work \shortcite{eite-etal-2002c}.

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~\ref{sec:Kc} the extension of $\K$ by action costs,
and consider some first examples for the usage of
$\Kc$. Section~\ref{sec:complexity} is devoted to the analysis of
complexity issues. In Section~\ref{sec:applications}, 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~\ref{sec:transformation}, we
present a transformation of $\Kc$ into answer set programming, and
in Section~\ref{sec:implementation}, we report about a prototype
implementation and experiments. After a discussion of related work in
Section~\ref{sec:rel-works}, we conclude the paper with an outlook on
ongoing and future work. 

\section{Short Review of Language \K}
\label{sec:review}

In this section, we give a brief informal overview of the language \K,
and refer to \cite{eite-etal-2001d} 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.  

\begin{problem}\label{prob:BCP} {\rm\bf [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.
\end{problem}

\paragraph{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 \emph{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 {\em 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.

\paragraph{Background knowledge.}
Static knowledge which is invariant over time in a \K planning domain
is specified in a normal (disjunction-free) Datalog program \BK that has a 
single answer set and can be viewed as a set of facts.
\nop{
This is the case if, for instance, the  well-founded model of $\BK$, 
cf.\ \cite{vang-etal-91}, is total, which is guaranteed for stratified 
logic programs and other (syntactic) classes of programs.
}
%
For our example, the background knowledge specifies the four persons:
\begin{bgprogram}
\bgpi{person(joe).\quad person(jack).\quad person(william).\quad person(averell).}
\end{bgprogram}
\paragraph{Type declarations.} Each fluent or action must have a declaration
where the ranges of its arguments are specified. For instance,
\begin{bgprogram}
\inlinek{crossTogether(X,Y)\ requires\ person(X),\ person(Y),\ X < Y.}\footnote{``$<$'' here is used instead of inequality to avoid symmetric rules.}\\
\end{bgprogram}
specifies the arguments of the action \inlinek{crossTogether}, where
two persons cross the bridge together, while
\begin{bgprogram}
\bgpi{across(X)\ requires\ person(X).}
\end{bgprogram}
specifies a fluent describing that a specific person is on the other side of
the river.
Here the literals after ``\inlinek{requires}'' must be classical 
literals of the static background knowledge (like  \inlinek{person(X)} and
\inlinek{person(Y)}), or literals of built-in predicates (such as \inlinek{X
  < Y}).
Our implementation of $\K$, the \dlvk-system~\cite{eite-etal-2001e}, 
currently  supports the built-in predicates
``\inlinek{A<B}'', ``\inlinek{A<=B}'', ``\inlinek{A\kuneq B}''
with the obvious meaning of less-than, less-or-equal and inequality for
strings and numbers, the arithmetic built-ins ``\inlinek{A=B+C}'' and
``\inlinek{A=B*C}'' which stand for integer addition and multiplication,
and the predicate ``\inlinek{\#int(X)}'' which enumerates all 
integers (up to a user-defined limit).

\paragraph{Causation rules.} Causation rules (``rules'' for brevity)
%are the main construct of \K. They 
are syntactically similar to rules of the action language 
$\cal C$~\cite{giun-lifs-98,lifs-99,lifs-turn-99}
and are of the basic form:
\begin{bgprogram}
\bgpi{caused\ f\ if\ B\ after\ A.}
\end{bgprogram}
where \inlinek{A} is a conjunction of fluent and action literals, 
possibly including default negation, \inlinek{B} is a conjunction of fluent 
literals, again possibly including default negation, and \inlinek{f}
is a fluent literal. Informally, such a rule reads: if \inlinek{B} is
known to be true in the current state and \inlinek{A} is known to be
true in the previous state, then \inlinek{f} is known to be true in
the current state as well.  Both the \inlinek{if}-part and the
\inlinek{after}-part are allowed to be empty (which means that they
are true).  A causation rule is called \emph{dynamic}, if its
\inlinek{after}-part is not empty, and is called \emph{static}
otherwise.

Causation rules are used to express effects of actions or ramifications.
For example, 
%the following two rules
\begin{bgprogram}
\bgpi{caused\ across(X)\ after\ cross(X),\ \TNEG across(X).}
\bgpi{caused\ \TNEG across(X)\ after\ cross(X),\ across(X).}
\end{bgprogram}
describe the effects of a single person crossing the bridge in either 
direction.

\paragraph{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 
``\inlinek{always:}''
and ``\inlinek{initially:}'' preceding sequences of rules
where the latter describes {\em initial state constraints} that 
must be satisfied only in the initial state.
For example, 
\begin{kprogram}
\kpi{initially:}{caused\ \TNEG across(X).} 
\end{kprogram}
enforces the fluent 
\inlinek{across} to be false in the initial state for any \inlinek{X} 
satisfying the declaration of the fluent \inlinek{across}, i.e., for all
persons. The rule is irrelevant for all subsequent states. 

\paragraph{Executability of actions.} This is expressed in \K\ explicitly.
For instance,
\begin{bgprogram}
\bgpi{executable\ crossTogether(X,Y)\ if\ hasLamp(X).}
\bgpi{executable\ crossTogether(X,Y)\ if\ hasLamp(Y).}
\end{bgprogram}
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
\begin{bgprogram}
\bgpi{executable\ cross(X).}
\end{bgprogram}
with empty body says that \inlinek{cross} is always executable, provided that the 
type restrictions on $\tt X$ are respected. 
Dually,
\begin{bgprogram}
\bgpi{nonexecutable\ a\ if\ B.}
\end{bgprogram}
prohibits the execution of action \inlinek{a} if condition
\inlinek{B} is satisfied. 
%The keyword \inlinek{false} in the head of a rule describes a contradiction,
%which can be used to model integrity constraints.
For example, 
\begin{bgprogram}
\bgpi{nonexecutable\ crossTogether(X,Y)\ if\ differentSides(X,Y).}
\end{bgprogram}
says that persons \inlinek{X} and \inlinek{Y} can not cross the bridge together
if they are on different sides of the bridge. In case of conflicts,
\inlinek{nonexecutable\ A} overrides \inlinek{executable\ A}.

\nop{
\paragraph{Parallel actions.}  By default, \K allows simultaneous execution of
actions. This is prohibited by
% the statement 
\begin{bgprogram}
\bgpi{noConcurrency.}
\end{bgprogram}
which enforces the execution of at most one action at a time.
}

\paragraph{Default and strong negation.} \K supports strong negation
(``$\tneg{}$,'' also written as ``\TNEG''). Note, however, that
for a fluent \inlinek{f}, in a state neither \inlinek{f} nor
\inlinek{\TNEG{f}} needs to hold. In this case the knowledge about 
\inlinek{f} is incomplete. 
In addition, weak negation (``\dnegsymbol''), interpreted like default
negation in answer set semantics \cite{gelf-lifs-91}, 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,
% the statement
\begin{bgprogram}
\bgpi{caused\ hasLamp(joe)\ if\ \dneg{hasLamp(jack)}, \dneg{hasLamp(william)},
\dneg{hasLamp(averell)}.}
\end{bgprogram}
expresses the conclusion that by default, \inlinek{joe} has the lamp,  
whenever it is not evident that any of the other persons has it.

\paragraph{Macros.} \K provides a number of macros as ``syntactic sugar''.
For example,
\begin{bgprogram}
\bgpi{inertial\ across(X).}
\end{bgprogram}
informally states that \inlinek{across(X)} holds in the current state, if 
\inlinek{across(X)} held at the previous state, unless 
\inlinek{\TNEG across(X)} is explicitly known to hold.
This macro expands to the rule 
\begin{bgprogram}
\bgpi{caused\ across(X)\ if\ \dneg{\TNEG across(X)}\ after\ across(X).}
\end{bgprogram}
Moreover, we can ``totalize'' the knowledge of a fluent by declaring
\inlinek{total\ f.}
which is a shortcut for
% a pair of rules: 
\begin{bgprogram}
\bgpi{caused\ f\ if\ not\ \TNEG f. \qquad caused\ \TNEG f\ if\ not\ f.}
\end{bgprogram}
The intuitive meaning of these rules is that unless a truth value for {\tt f} 
can be derived, the cases where {\tt f} resp.\ {\tt -f} is true will both be
considered. 
\ifreport
This is is for instance useful to model non-deterministic action effects: 
\inlinek{total f after a}.
\fi
%Furthermore, \inlinek{default\ -across(X,Y).}
%states that {\tt -across(X)} is assumed, unless {\tt across(X)} is known to 
%hold (as it has been explicitly entailed by some causation rule). 
%An equivalent rule stating this would be
%\begin{bgprogram}
%\bgpi{caused\ \TNEG across(X)\ if\ \dneg{across(X)}.}
%\end{bgprogram}

\paragraph{Planning domains and problems.}
In \K, a {\em planning domain} \mbox{$\PD = \PDtupleBKDRdef$} has a
background knowledge \BK, action and fluent declarations $D$,
and rules and executability conditions $R$; a {\em
planning problem}\/ $\PP=\tuple{\PD,\q}$ has a planning domain
$\PD$ and a {\em query}
$$q = g_1, \ldots , g_m, \dneg{g_{m+1}},
\ldots, \dneg{g_n}\inlinek{\ ?\ (}l\inlinek{)}
$$ where $g_1,\ldots,g_n$ are ground fluents and $l \ge 0$ is the
plan length. 
For instance, the goal query
\begin{bgprogram}
\bgpi{across(joe),\ across(jack),\ across(william),\ across(averell)?\ (5)}
\end{bgprogram}
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 {\em (optimistic) plan} for $\PP$ is a sequence $\p =
\tuple{A_1,\ldots,A_l}$ of sets of action instances
$A_1,A_2,\ldots,A_l$ in a {\em trajectory}
$T=\tuple{\tuple{s_0,A_1,s_1}$, $\tuple{s_1,A_2,s_2},$ \ldots,
$\tuple{s_{l-1},A_l,s_l}}$ from a legal initial state $s_0$ to state
$s_l$ in which all literals of the goal are true. That is, starting in
$s_0$, the legal transition $t_1 = \tuple{s_0,A_1,s_1}$, modeling the
execution of the actions in $A_1$ (which must be executable),
transforms $s_0$ into the state $s_1$. This is then followed by legal
transitions $t_i=\tuple{s_{i-1},A_i,s_i}$, for $i=2,3,\ldots,l$ (cf.\
Appendix for details). A plan is {\em sequential}, if $|A_i|\leq 1$
for all $i=1,\ldots,l$, i.e., each step consists of at most one
action; such plans can be enforced by including the keyword \inlinek{noConcurrency}.

Besides optimistic plans, in $\K$ we also support
stronger {\em secure (or conformant) plans}. A secure plan must be
guaranteed to work out under all circumstances \cite{eite-etal-2000d},
regardless of incomplete information about the initial state and
possible nondeterminism in the action effects.

For better readability, in the following we will not always describe
\K planning problems $\PP$ strictly in terms of sets of declarations,
rules and executability conditions, but optionally use the more compact
representation of \K\ {\em programs} of the following general form:

\begin{kprogram}
\kpi{fluents:}{\mbox{$\DF$}}
\kpi{actions:}{\mbox{$\DA$}}
\kpi{initially:}{\mbox{$\RI$}}
\kpi{always:}{\mbox{$\RC$}}
\kpi{goal:}{\mbox{$\q$}}
\end{kprogram}
\noindent where the (optional) sections \inlinek{fluents} through
\inlinek{always} consist of lists of 
fluent declarations \DF, action declarations \DA, initial state constraints 
\RI and executability conditions and causation rules \RC, respectively.
Together with the background knowledge \BK
% given in a separate program
and the goal query $q$,  they specify a \K planning 
problem %of the form 
$\PP=\tuple{\PDtupleBKDRdef,\q}$, where \D is given by \DF plus \DA 
and 
\R by \RI plus \RC.~\footnote{This is also the format of the input
files of our system prototype, which will be presented in
Section~\ref{sec:implementation}.}

\subsection{Solving the Bridge Crossing Problem}
\label{sec:solving_bridge}

\begin{figure}[htb]
\begin{kprogram}
\kpi{actions: }{cross(X)\ requires\ person(X).}
\kpi{}{crossTogether(X,Y)\ requires\ person(X),\ person(Y),\ X < Y.}
\kpi{}{takeLamp(X)\ requires\ person(X).}[1.5ex]
\kpi{fluents: }{across(X)\ requires\ person(X).}
\kpi{}{differentSides(X,Y)\ requires\ person(X),\ person(Y).}
\kpi{}{hasLamp(X)\ requires\ person(X).}[1.5ex]
\kpi{initially:}{\TNEG across(X).\ hasLamp(joe).}[1.5ex]
\kpi{always:}{executable\ crossTogether(X,Y)\ if\ hasLamp(X).}
\kpi{}{executable\ crossTogether(X,Y)\ if\ hasLamp(Y).}
\kpi{}{nonexecutable\ crossTogether(X,Y)\ if\ differentSides(X,Y).}[1.5ex]
\kpi{}{executable\ cross(X)\ if\ hasLamp(X).}[1.5ex]
\kpi{}{executable\ takeLamp(X).}
\kpi{}{nonexecutable\ takeLamp(X)\ if\ hasLamp(Y),\ 
differentSides(X,Y).}[1.5ex]
\kpi{}{caused\ across(X)\ after\ crossTogether(X,Y),\ \TNEG across(X).}
\kpi{}{caused\ across(Y)\ after\ crossTogether(X,Y),\ \TNEG across(Y).}
\kpi{}{caused\ \TNEG across(X)\ after\ crossTogether(X,Y),\ across(X).}
\kpi{}{caused\ \TNEG across(Y)\ after\ crossTogether(X,Y),\ across(Y).}[1.5ex]
\kpi{}{caused\ across(X)\ after\ cross(X),\ \TNEG across(X).}
\kpi{}{caused\ \TNEG across(X)\ after\ cross(X),\ across(X).}[1.5ex]
\kpi{}{caused\ hasLamp(X)\ after\ takeLamp(X).}
\kpi{}{caused\ \TNEG hasLamp(X)\ after\ takeLamp(Y),\ X \kuneq Y,\ hasLamp(X).}[1.5ex]
\kpi{}{caused\ differentSides(X,Y)\ if\ across(X),\ \TNEG across(Y).}
\kpi{}{caused\ differentSides(X,Y)\ if\ \TNEG across(X),\ across(Y).}[1.5ex]
\kpi{}{inertial\ across(X).}
\kpi{}{inertial\ \TNEG across(X).}
\kpi{}{inertial\ hasLamp(X).}[1.5ex]
\kpi{noConcurrency.}{}[1.5ex]
\kpi{goal:}{across(joe),\ across(jack),\ across(william),\ across(averell)?\ (\mbox{$l$})}
\end{kprogram}
\caption{\K\ encoding of the Bridge Crossing Problem}
\label{fig:crossing}
\end{figure}

Using the above constructs, a \K encoding of the Bridge Crossing
Problem, assuming that \inlinek{joe} initially carries the lamp, is
shown in Figure~\ref{fig:crossing}. There are simple five-step plans
$(l=5)$, in which \inlinek{joe} always carries the lamp and brings all
others across. One of them is:
\begin{kplan}
\kpli{\kpl{}}{\set{crossTogether(joe,jack)},\ \set{cross(joe)},\ \set{crossTogether(joe,william)},}
\kpli{}{\set{cross(joe)},\ \set{crossTogether(joe,averell)}\ \rangle}
\end{kplan}

\section{Actions with Costs}
\label{sec:Kc}

Using the language \K and the system prototype, \dlvk, we can already
express and solve some involved planning tasks, cf.\ \cite{eite-etal-2001d}.
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:

\begin{problem}\label{prob:QBCP}
{\rm\bf [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?
\end{problem}

On first thought this is infeasible, since the seemingly optimal 
plan where \inlinek{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.

\subsection{Syntax of \Kc}

%We will quickly recall some preliminaries from \K:
Let \acts, \fls, and \vars 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, 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 \consts{}.

\Kc extends action declarations as in \K with costs as follows.

\begin{definition}
An \emph{action declaration} $d$ in $\Kc$ is of the form:
  \begin{equation}
p(X_1, \ldots, X_n)\; \inlinek{requires}\; t_1, \ldots, t_m\; \inlinek{costs}\; 
  C\; \inlinek{where}\; c_1, \ldots, c_k.
\label{stmt:actdecl}
\end{equation}
where
(1) $p \in \acts$ has arity $n\geq 0$,
(2) $X_1, \ldots, X_n \in \vars$, 
(3) $t_1, \ldots, t_m$, $c_1, \ldots, c_k$ are
from $\ltyp$ such that every $X_i$ occurs in $t_1, \ldots, t_m$, 
(4) $C$ is either an integer constant, a variable from the set of all
variables occurring in  $t_1, \ldots, t_m$, $c_1, \ldots, c_k$ (denoted 
by  $\vars(d)$),  or the distinguished variable \inlinek{time}, 
(5) $\vars(d) \subseteq \vars \cup \{\inlinek{time}\}$, and 
(6) \inlinek{time} does not occur in $t_1, \ldots t_m$. 
\end{definition}
If $m=0$, the keyword `\inlinek{requires}' is omitted; if $k=0$, the
keyword `\inlinek{where}' is omitted and `\inlinek{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 \inlinek{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 \inlinek{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.

\smallskip\noindent
Planning domains and planning problems in $\Kc$ are defined as in \K.

\medskip

For example, in the elaborated Bridge Crossing Problem, the
declaration of \inlinek{cross(X)} can be extended as follows: suppose
a predicate \inlinek{walk(Person,Minutes)} in the background knowledge
indicates that \inlinek{Person} takes \inlinek{Minutes} to cross.
Then, we may simply declare
\begin{bgprogram}
\inlinek{cross(X)\ requires\ person(X)\ costs\ WX\ where\
walk(X,WX).}
\end{bgprogram}

\subsection{Semantics of \Kc}

Semantically, \Kc extends \K by the cost values of actions at points
in time. In any plan $\p = \tuple{A_1,\ldots,A_l}$, at step $1 \leq i
\leq l$, the actions in $A_i$ are executed to reach time point $i$.

A ground action $p(x_1,\ldots, x_n)$ is a \emph{legal
action instance} of an action declaration $d$ wrt.\ a \Kc planning
domain $\PD = \PDtupleBKDRdef$, if there exists some ground substitution
$\theta$ for $\vars(d)\cup\{\inlinek{time}\}$ such that $X_i\theta=x_i$, for
$1 \leq i \leq n$  and $\{t_1\theta, \ldots, t_m\theta\} \subseteq
M$, where $M$ is the unique answer set of the background knowledge
\BK.  Any such $\theta$ is called a \emph{witness substitution} for
$p(x_1,\ldots,x_n)$.  Informally, an action instance is legal, if it
satisfies the respective typing requirements.  Action costs are now
formalized as follows. 

\begin{definition}
Let $a = p(x_1,\ldots, x_n)$ be a legal action instance of a
declaration $d$ of the form (\ref{stmt:actdecl})
%, let $i\geq 1$ be a time point, 
and let $\theta$ 
be a witness substitution for $a$.
% such that $\inlinek{time}\,\theta=i$.
Then
$$
cost_{\theta}(p(x_1,\ldots, x_n)) =
\left\{\begin{array}{ll}
0, & \textrm{ if the \inlinek{costs} part of $d$ is empty;} \\
val(C\theta), & \textrm{ if  
$\{c_1\theta, \ldots, c_k\theta\} \subseteq M$}; \\
\textrm{undefined} & \textrm{ otherwise}.
\end{array}
\right.
$$
where $M$ is the unique answer set of \BK and $val: \consts{} \rightarrow \Nat$
is defined as the integer value for integer constants and 0 for all non-integer constants.
\end{definition}
By reference to the variable \inlinek{time}, it is possible to define
time-dependent action costs; we shall consider an example in
Section~\ref{sec:tsp}. Using $cost_{\theta}$, we now introduce
well-defined legal action instances and define action cost values as
follows.

\begin{definition}
\label{def:wd}
A legal action instance $a = p(x_1,\ldots, x_n)$ is \emph{well-defined}
iff it holds that (i) for any time point $i\geq 1$, there is some
witness substitution $\theta$ for $a$ such that $\inlinek{time}=i$
and $cost_{\theta}(a)$ is an %non-negative 
integer, and (ii)
$cost_{\theta}(a) = cost_{\theta'}(a)$ holds for any two witness 
substitutions $\theta, \theta'$ which coincide on $\inlinek{time}$ and
have defined costs.
\nop{\footnote{This implies that, in order to write well-defined 
declarations, one may use only variables bound to an integer value for the 
costs of an action.}}
For any well-defined $a$, its unique cost at time point
$i\geq 1$ is given by $cost_{i}(a) =
cost_{\theta}(a)$ where $\theta$ is as in (i).
\end{definition}

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 $\theta$ and
$\theta'$ for $a$ evaluate the \inlinek{cost} part to
the same integer cost value.
\nop{***
Note that especially $M$ has to be unique to guarantee a unique 
cost value which is guaranteed by the restriction that \BK has to have a 
total well-founded model.
***}

An action declaration $d$ is \emph{well-defined}, if all its legal 
instances are well-defined. This will be fulfilled
if, in database terms, the variables $X_1,\ldots,X_n$ together
with \inlinek{time} in (\ref{stmt:actdecl}) functionally determine the 
value of $C$.
%if, e.g.\ in database terms the variables $X_1,\ldots,X_n$ in 
%(\ref{stmt:actdecl}) functionally determine the 
%value of each other variable except \inlinek{time}, i.e., each
%tuple of values $(x_1,\ldots x_n)$ for $X_1,\ldots,X_n$ has a unique
%extension to a tuple of values for all variables in $d$ except
%\inlinek{time}.
In our framework, the semantics of a \Kc 
planning domain $\PD = \PDtupleBKDRdef$
\ifreport 
(resp.\ a planning problem $\PP=\tuple{PD,q}$)
\fi
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. 
\ifreport
Note that violations of well-definedness 
can be detected by a simple logic program extending 
\BK, as shown in Section~\ref{sec:WD}.
\fi
 
Using $cost_i$, we now define costs of 
\nop{***
trajectories and 
***}
plans.

\nop{***
\begin{definition}
Let $T=\tuple{t_1,\ldots,t_l}$ be a trajectory, 
where $t_j=\tuple{s_{j-1},A_j,s_j}$, $j=1,\ldots,l$. 
Then, the cost of $T$ wrt.\ a planning domain \PD is defined as 
$$
cost(T) = \textstyle \sum_{j=1}^{l}\left( \sum_{a \in A_j} cost_{j}(a) \right).
$$
\end{definition}

Similarly, we define the cost of a plan:
***}
\begin{definition}
Let $\PP = \tuple{\PD, Q\,?\,(l)}$ be a planning problem. Then, for
any plan $\p = \tuple{A_1,\ldots,A_l}$ for \PP, its cost is defined as
$$
\plancost{\PP}{\P} = \textstyle \sum_{j=1}^{l}\left( \sum_{a \in A_j} cost_{j}(a) \right).
$$
A plan $\p$ is {\em optimal} for \PP, if $\plancost{\PP}{\P} \leq
\plancost{\PP}{\p'}$ for each plan $\p'$ for $\PP$, i.e., $\p$ has least
cost among all plans for $\PP$. The cost of a planning problem \PP,
denoted $\optcost{\PP}$, is given by $\optcost{\PP} = \plancost{\PP}{\P^*}$, where
$\P^*$ is an optimal plan for $\PP$.
\end{definition}

In particular, $\plancost{\PP}{\p}=0$ if $\p=\tuple{}$, i.e., the plan is void.
Note that $\optcost{\PP}$ is only defined if a plan for $\PP$ exists.%
\footnote{In the following, subscripts will be dropped when clear from the
context.}

Usually one only can estimate some \emph{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~\ref{sec:blocksworld} that by 
appropriate encodings this can be extended to optimality for plans with 
length \emph{at most} $l$. 

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

\begin{definition}
A plan $\p$ for a planning problem \PP is {\em admissible}
wrt.\ cost $c$, if $\plancost{\PP}{\p}\!\leq\!c$.  
\end{definition}

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. 


\subsection{An Optimal Solution for the Quick Bridge Crossing Problem}
\label{sec:crossingopt}

To model the Quick Bridge Crossing Problem in \Kc,
we first extend the background knowledge as follows, where the predicate 
`\inlinek{walk}' describes the time a person needs to cross and
`\inlinek{max}' determines which of two persons is slower:
\begin{bgprogram}
%\bgpi{person(joe).\ person(jack).\ person(william).\ person(averell).}
\bgpi{walk(joe,1).\ walk(jack,2).\ walk(william,5).\ walk(averell,10).}[.5ex]
\bgpi{max(A,B,A)\ \derives\ walk(\_,A),\ walk(\_,B),\  A >= B.}
\bgpi{max(A,B,B)\ \derives\ walk(\_,A),\ walk(\_,B),\ B > A.}
\end{bgprogram}

\medskip
\noindent
Next, we modify the declarations for 
\inlinek{cross} and \inlinek{crossTogether} from Figure~\ref{fig:crossing}
by adding costs:
\begin{kprogram}
\inlinek{crossTogether(X,Y)} \= \kill
\inlinek{cross(X)\ requires\ person(X)\ costs\ WX\ where\ walk(X,WX).}\\
\inlinek{crossTogether(X,Y)\ }\=\inlinek{requires\ person(X),\ 
person(Y),\ X < Y}\\
\>\inlinek{costs\ Wmax\ where\ }\=\inlinek{walk(X,WX), walk(Y,WY), max(WX,WY,Wmax).} \\
%\\
%\>\>\inlinek{max(WX,WY,Wmax).}\\ 
\end{kprogram}

\medskip

\noindent The declaration of \inlinek{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~\ref{sec:solving_bridge} has cost 19. Actually, it is optimal
for plan length $l=5$.  However, when we relinquish the first
intuition that the fastest person, \inlinek{joe}, always has the lamp
and consider the problem under varying plan length, then we can find
the following 7-step plan:
\begin{kplan}
\kpli{\kpl{}}{\set{crossTogether(joe,jack)},\ \set{cross(joe)},\ \set{takeLamp(william)},}
\kpli{}{\set{crossTogether(william,averell)},\ \set{takeLamp(jack)},\ \set{cross(jack)},}
\kpli{}{\set{crossTogether(joe,jack)}\ \rangle}
\end{kplan}
Here, $\plancost{\PP}{\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. 
\nop{***
\footnote{Note that plans are defined for queries, which prescribe the exact
plan length. However, any planning problem $\PP=\tuple{\PD,\q}$
can be transformed into a planning problem $\PP'=\tuple{\PD',\q'}$
such that plans for $\PP'$ of length $l+1$ correspond to trajectories in
$\PP$ of length $\leq l$ which accomplish $G$ in $\q = G \ ? \ (l)$.}
***}

\subsection{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
\cite{eite-etal-2000d,eite-etal-2001d}. More precisely, an optimistic
plan $\tuple{A_1,\ldots,A_n}$ is {\em secure}, if it is applicable
under any evolution of the system: starting from any legal initial
state $s_0$, the first action set $A_1$ (for plan length $l \geq 1$) can 
always be executed (i.e., some legal transition $\tuple{s_{0},A_1,s_1}$ 
exists), and for every such possible state $s_1$, the next action set 
$A_2$ can be executed etc., and
%eventually,
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
\begin{itemize}
\item among all optimistic plans%
%(like in the definition above)
, or

\vspace{-.5\baselineskip}

\item among all secure plans only.
\end{itemize}
In the first alternative, there might be planning problems which have
secure plans, but no optimal secure plans. For this reason,
% extending the definition of optimal plans according to 
the second alternative appears to be more appropriate.
\begin{definition}
A secure plan $\p$ is {\em optimal} for a planning problem \PP, 
% and fixed plan length $l$,
if it has least cost among all secure plans for \PP, 
% of length $l$, 
i.e., $\plancost{\PP}{\p}\leq \plancost{\PP}{\p'}$ for each secure 
plan $\p'$ for $\PP$. The {\em secure cost} of \PP, denoted $\seccost{\PP}$, is
$\seccost{\PP} = \plancost{\PP}{\P^*}$, where $P^*$ is any optimal secure plan for $\PP$.
\end{definition}

\noindent
The notion of admissible secure plans is defined analogously. 

\medskip

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 
\inlinek{initially}-part
with the following declarations:
\begin{kprogram}
\kpi{initially:}{total\ hasLamp(X).}
\>\inlinek{caused\ false\ if\ }\= \inlinek{\TNEG hasLamp(joe),\ \TNEG
  hasLamp(jack),}\\
\>\>\inlinek{ \TNEG hasLamp(william),\ \TNEG hasLamp(averell).}\\
\end{kprogram}

The first statement says that each person either has a lamp or not, 
and the second that at least one of them
% guys 
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~\cite{eite-etal-2001d}.

As we can easily see, an optimal secure solution will take at least 17 minutes,
since the original case (where only \inlinek{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): 
% i.e. $\seccost{\PP} = 17$, for plan length $i \ge 8$: 
Different from optimistic plans, we need one extra step at the
beginning which makes sure that one of those who walk first (above, \inlinek{joe} and \inlinek{jack}) has the lamp, which is effected
by the proper \inlinek{takeLamp} action.

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

\begin{kplan}
\kpli{\kpl{}}{\set{takeLamp(joe)},\ \set{crossTogether(joe,jack)},\ \set{cross(joe)},}
\kpli{}{\set{takeLamp(william)},\ \set{crossTogether(william,averell)}, \set{takeLamp(jack)},}
\kpli{}{\set{cross(jack)},\ \set{crossTogether(joe,jack)}\ \rangle}
\end{kplan}
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.

\section{Computational Complexity}
\label{sec:complexity}

In this section, we will address the computational complexity of \Kc,
complementing similar results for the language \K \cite{eite-etal-2001d}. 

\subsection{Complexity Classes}

We assume that the reader is familiar with the basic notions of
complexity theory, such as $\Pol$, $\NP$, problem reductions and
completeness; see e.g.\ \cite{papa-94} and references therein. We
recall that the Polynomial Hierarchy (PH) contains the classes
$\SigmaP{0}=\PiP{0}=\DeltaP{0}=\Pol$ and $\SigmaP{i+1} =
\NP^{\SigmaP{i}}$, $\PiP{i+1} =$ co-$\SigmaP{i+1}$, $\DeltaP{i+1} =
\Pol^{\SigmaP{i}}$, for $i\geq 0$. In particular, $\SigmaP{1}=\NP$
and $\DeltaP{2}=\Pol^{\NP}$. 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 {\em 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 \cite{selm-94b}. In
analogy to $\SigmaP{i+1}$, by $\SigmaPMV{i+1} = \NPMV^{\SigmaP{i}}$,
$i\geq 0$, we denote the generalization of $\NPMV$ where the machine has
access to a $\SigmaP{i}$ oracle.

Analogs to the classes $\Pol$ and $\DeltaP{i+1}$, $i\geq 0$, are given
by the classes $\FP$ and $\FDeltaP{i+1}$, $i\geq 0$, which contain the
partial single-valued functions (that is, $|S(I)|\leq 1$ for each problem instance
$I$) computable in polynomial time using no resp.\ a $\SigmaP{i}$
oracle. We say, abusing terminology, that a search problem $A$ is in
$\FP$ (resp.\ $\FDeltaP{i+1}$), if there is a partial (single-valued)
function $f \in \FP$ (resp.\ $f\in \FDeltaP{i+1}$) such that $f(I) \in
S(I)$ and $f(I)$ is undefined iff $S(I)=\emptyset$. For example,
computing a satisfying assignment for a propositional CNF (FSAT) and
computing an optimal tour in the Traveling Salesperson Problem (TSP)
are in $\FDeltaP{2}$ under this view, cf.\ \cite{papa-94}.

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

\subsection{Problem Setting}

We will focus on the following questions:

\begin{description}
\item[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.

\item[Admissible Planning:] Decide whether for planning problem $\PP$ an admissible
(optimistic/secure) plan  exists wrt.\ a
given cost value $c$, and find such a plan.
\item[Optimal Planning:] Find an optimal (optimistic/secure)
plan for a given planning problem.
\end{description}

Notice that \cite{eite-etal-2001d} 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 $\PP = \tuple{\PD,Q\,?\,(l)}$ which look for {\em polynomial length plans},
i.e., problems where the plan length $l$ is bounded by some polynomial
%$p(\cdot)$
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.\ \cite{dant-etal-01},
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
\cite{eite-etal-2001d}.

\begin{proposition}
\label{prop:prelim}
Deciding, given a propositional planning problem $\PP$ and a sequence
$\P=\tuple{A_1,\ldots,$ $A_l}$ of action sets, (i) whether a given sequence
$T=\tuple{t_1,\ldots,t_l}$ is a legal trajectory witnessing that 
$\P$ is an optimistic plan for $\PP$ is feasible in polynomial time,
and (ii) whether $\P$ is a secure plan for $\PP$ is $\PiP{2}$-complete. 
\end{proposition}

\subsection{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.

\begin{theorem}[Complexity of checking well-definedness]
\label{theo:check-wdef}
Given a \Kc planning domain
$\PD=\tuple{\BK,\tuple{D,R}}$ and the unique model $M$ of \BK,
checking (i) well-definedness of a given action declaration $d$ of
form (\ref{stmt:actdecl}) wrt.\ $\PD$ and  (ii) well-definedness of $\PD$
are both $\PiP{2}$-complete.
\end{theorem}

\begin{proof}
\noindent{\it Membership:} As for (i), $d$ is violated if it has a
nonempty \inlinek{costs} part and a legal action instance
$a=p(x_1,\ldots,x_n)$ such that either (1) there exist witness
substitutions $\theta$ and $\theta'$ for $a$ such that
$\inlinek{time}\theta = \inlinek{time} \theta'$, $cost_\theta(a)=
val(C\theta)$ and $cost_{\theta'}(a)=val(C\theta')$, and
$val(C\theta)\neq val(C\theta')$, or (2) there is no witness substitution
$\theta$ for $a$ such that $cost_{\theta}(a)=val(C\theta)$ is an
integer.  Such an $a$ can be guessed and checked, via a witness substitution, in polynomial time, and along
with $a$ also $\theta$ and $\theta'$ 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
\inlinek{time} if it occurs in $c_1,\ldots,c_k$. Given $a$, we can
decide (2) with the help of an $\NP$ oracle. In summary,
disproving well-definedness of $d$ is nondeterministically possible in
polynomial time with an $\NP$ oracle. Hence, checking well-definedness
of $d$ is in co-$\SigmaP{2}$ = $\PiP{2}$. The membership part of (ii)
follows from (i), since well-definedness of $\PD$ reduces to
well-definedness of all action declarations in it, and $\PiP{2}$ is
closed under conjunctions. 

\noindent{\it Hardness:} We show hardness for (i) by a reduction from
deciding whether a quantified Boolean formula (QBF) 
$$
Q = \forall X\exists Y.c_1 \land\cdots\land c_k
$$
where each $c_i =
L_{i,1}\lor\cdots\lor L_{i,\ell_i}$, $i=1,\ldots,k$,  is a disjunction of
literals $L_{i,j}$ on the atoms $X = x_1,\ldots,x_n$ and $Y=x_{n+1}\ldots,x_m$, is true. Without loss of generality, we may assume
that each $c_i$ 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, $\BK$, is 
\begin{bgprogram}
\bgpi{bool(0).~~ bool(1).}
\bgpi{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).}
\bgpi{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).}
\end{bgprogram}
Here, \inlinek{bool} declares the truth values 0 and 1. The facts
\inlinek{pos(X_1,X_2,X_3)} and \inlinek{neg(X_1,X_2,X_3)} state those
truth assignments to $X_1$, $X_2$, and $X_3$ such that the positive
clause $X_1 \lor X_2 \lor X_3$ resp.\ the negative clause $\neg X_1 \lor
\neg X_2 \lor \neg X_3$ is satisfied.

The rest of the planning domain $\PD$ consists of the single action
declaration $d$ of form
\begin{bgprogram}
\bgpi{p(V_1,...,V_n)\ \ requires\ \ bool(V_1),...,\ bool(V_n)\ \ costs\ 0\ \ where\ \ \mbox{$c^*_1$},...,\mbox{$c^*_k$}.}
\end{bgprogram}
where 
$$
c^*_i = \left\{
\begin{array}{ll}
\inlinek{pos(V_{i,1}, V_{i,2}, V_{i,3})}, & \textrm{if $c_i =
x_{i,1} \lor x_{i,2} \lor x_{i,3}$}, \\ 
\inlinek{neg(V_{i,1}, V_{i,2}, V_{i,3})}, & \textrm{if $c_i =
\neg x_{i,1} \lor \neg x_{i,2} \lor \neg x_{i,3}$},
\end{array}
\right. \quad i=1,\ldots,k.
$$
For example, the clause $c=x_1\lor x_3 \lor x_6$ is mapped to $c^* = \inlinek{pos(V_1,V_3,V_6)}$.
It is easy to see that each legal action instance $a=p(b_1,\ldots,b_n)$ of
$d$ corresponds 1-1 to the truth assignment $\sigma_a$ of $X$ given
by $\sigma_a(x_i)=b_i$, for $i=1,\ldots,n$. Furthermore, $a$ has a
cost value defined (which is 0) iff the formula $\exists
Y(c_1\sigma_a\land\cdots\land c_k\sigma_a)$ is true. Thus, $d$ is well-defined wrt.\
$\PD$ iff $Q$ is true. Since $\PD$ and $d$ are efficiently constructible,
this proves $\PiP{2}$-hardness.
\end{proof}

\bigskip

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~\ref{theo:check-wdef} is polynomial. Thus, by our
assumption on the efficient evaluation of the background program, we
obtain: 
\begin{corollary}
In the ground (propositional) case, checking well-definedness of an action
description $d$ wrt.\
a \Kc planning domain $\PD=\tuple{\BK,\tuple{D,R}}$, resp.\ of $\PD$ as a
whole, is possible in polynomial time.  
\end{corollary}

We remark that checking well-definedness can be expressed as a
planning task in $\K$, and also by a logic program;
\ifreport
this will be considered in Section~\ref{sec:WD}. 
\else
we refer to \cite{eite-etal-2002costs-TR_without_note} for details. 
\fi

We now turn to computing admissible plans. 

\begin{theorem}[Complexity of admissible planning]
\label{theo:comp-admissible}
For polynomial plan lengths, deciding whether a given (well-defined)
propositional planning problem $\tuple{\PD,\q}$ 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 $\tuple{\PD,\q}$ has some secure
admissible plan wrt.\ to a given integer $b$ is $\SigmaP{3}$-complete, and
computing such a plan is $\SigmaPMV{3}$-complete.
% and (b) $\PSPACE$-complete in general. 
Hardness holds in both cases for fixed plan length.
\end{theorem}

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

\begin{theorem}[Complexity of optimal planning]
\label{theo:comp-optimal}
For polynomial plan lengths, (i) computing an optimal optimistic plan for
$\tuple{\PD,Q\,?\,(l)}$ in \Kc is $\FDeltaP{2}$-complete, and (ii) computing an
optimal secure plan for $\tuple{\PD,Q\,?\,(l)}$ in \Kc is
$\FDeltaP{4}$-complete. Hardness holds in both cases even if the
plan length $l$ is fixed. 
\end{theorem}

The proof again can be found in the in the Appendix.

\medskip

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 \cite{eite-etal-2001d}, 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.

\section{Applications}
\label{sec:applications}

\subsection{Cost Efficient versus Time Efficient Plans}
\label{sec:blocksworld}
\label{sec:opt}

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.~\cite{kaut-wals-99,lee-lifs-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 \citeyear{kaut-wals-99}.
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.

\medskip

We consider the following optimization problems:

\begin{enumerate}
\item[($\alpha$)] Find a plan with minimal cost ({\em cheapest plan}) for a 
given number of steps.
\item[($\beta$)] Find a plan with minimal time steps ({\em shortest plan}).
\item[($\gamma$)] Find a shortest among the cheapest plans.  
\item[($\delta$)] Find a cheapest among the shortest plans.
\end{enumerate}

Problem ($\alpha$) is what we have already defined as optimal plans 
so far. We will now show how to express ($\beta$) in terms of optimal 
cost plans as well, and how to extend this elaboration with 
respect to the combinations ($\gamma$) and ($\delta$).

\subsubsection{Cheapest Plans with Given Plan Length ($\alpha$)}
\label{sec:alpha}

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~\ref{fig:bwprog}. 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.

\begin{figure}[ht]
\begin{kprogram}
\kpi{fluents:}{on(B,L)\ requires\ block(B),\ location(L).}
\kpi{}{blocked(B)\ requires\ block(B).}
\kpi{}{moved(B)\ requires\ block(B).}[1.5ex]
\kpi{actions:}{move(B,L)\ requires\ block(B),\ location(L)\ costs\ 1.}[1.5ex]
\kpi{always:}{executable\ move(B,L)\ if\ B \kuneq L.}
\kpi{}{nonexecutable\ move(B,L)\ if\ blocked(B).}
\kpi{}{nonexecutable\ move(B,L)\ if\ blocked(L).}
\kpi{}{nonexecutable\ move(B,L)\ if\ move(B1,L),\ B < B1,\ block(L).}
\kpi{}{nonexecutable\ move(B,L)\ if\ move(B,L1),\ L < L1.}
\kpi{}{nonexecutable\ move(B,B1)\ if\ move(B1,L).}[1.5ex]
\kpi{}{caused\ on(B,L)\ after\ move(B,L).}
\kpi{}{caused\ blocked(B)\ if\ on(B1,B).}
\kpi{}{caused\ moved(B)\ after\ move(B,L).}
\kpi{}{caused\ on(B,L)\ if\ not\ moved(B)\ after\ on(B,L).}
\end{kprogram}
\caption{\Kc encoding for the Blocks World domain}
\label{fig:bwprog}
\end{figure}

\begin{figure}

\bigskip

\centering
\epsfig{file=bw.eps,width=4.5cm}
\caption{A simple Blocks World instance}
\label{fig:bw}
\end{figure}

The planning problem emerging from the initial state and the goal
state depicted in Figure~\ref{fig:bw} can be modeled using
the background knowledge $\BK[bw]$:
\begin{bgprogram}
\bgpi{block(1).\quad block(2).\quad block(3).\quad block(4).\quad block(5).\quad block(6).}
\bgpi{location(table).}
\bgpi{location(B)\ \derives\ block(B).}
\end{bgprogram}
and extending the program in Figure~\ref{fig:bwprog} as follows:
\begin{kprogram}
\kpi{initially:}{on(1,2).\ on(2,table).\ on(3,4).\ on(4,table).\ on(5,6).\ on(6,table).}[1.0ex]
\kpi{goal:} {on(1,3),\ on(3,table),\ on(2,4),\ on(4,table),\ on(6,5),\ on(5,table)\ ? (\mbox{$l$})}
\end{kprogram}

\noindent
Each move is penalized with cost 1, which results in a minimization of the total number of 
moves. Let $\PP[l]$ denote the planning problem for plan length $l$.  

For $l=2$, we have an optimal plan which involves 
six moves, i.e. $\optcost{\PP[2]} = 6$:
\begin{kplan}
\kpli{\kpl{2}}{\set{move(1,table),move(3,table),move(5,table)},\ \set{move(1,3),move(2,4),move(6,5)}\, \rangle}
\end{kplan}
By unfolding the steps, this plan gives rise to similar plans of length
$l=3,\ldots, 6$ that have cost 6. For $l=3$, we can find among others the following
optimal plan, which has cost 5: 
\begin{kplan}
\kpli{\kpl{3}}{\set{move(3,table)},\ \set{move(1,3), move(5,table)},\ \set{move(2,4), move(6,5)}\, \rangle}
\end{kplan}
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
$\p_3$, 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.

\nop{**
\Kc only allows for plans of fixed length $l$. This means, by assigning cost
1 to all moves, we only solve criterion ($\alpha$) mentioned in the beginning 
of this section for our Blocks World example.
***}

\subsubsection{Shortest Plans ($\beta$)}
\label{sec:beta}


Intuitively, it should be possible to include the minimization of time
steps in the cost function. 
% For the moment,
We describe a preprocessing method
which, given a \K planning domain $\PD$, a list $Q$ of ground
literals, and an upper bound $i\geq 0$ for the plan length, generates a 
planning problem $\PP[\beta](\PD,Q,i)$ such
that the optimal plans for $\PP[\beta]$ correspond to shortest plans which 
reach $Q$ in $\PD$ in at most $i$ steps, i.e., to plans for
$\tuple{\PD,Q\,?\,(l)}$ such that $l\leq 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.  

%We modify the \inlinek{always}-section of the original
%program depending on the original goal $Q$
%\begin{kprogram}
%\kpi{goal:}{g_1, \ldots , g_m, \dneg{g_{m+1}}, \ldots, \dneg{g_n}\ ?\ (i)}
%\end{kprogram}

First we rewrite the planning domain $\PD$ to 
$\PD[\beta]$ as follows:
We introduce a new distinct fluent \inlinek{gr} and a new 
distinct action \inlinek{finish},
% to our domain,
defined as follows:
\begin{kprogram}
\kpi{fluents:}{gr.}
\kpi{actions:}{finish\ costs\ time.}
\end{kprogram}
Intuitively, the action \inlinek{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
\inlinek{time} as cost. The fluent \inlinek{gr} (``goal reached'')
shall be true and remain true as soon as the goal has been reached, and it is
triggered by the \inlinek{finish} action.

This can be modeled in \Kc by adding the following statements to the 
\inlinek{always} section of the program:
\begin{kprogram}
%\kpi{always:}{executable\ finish\ if\ g_1,\ \ldots,\ g_m,\ \dneg{g_{m+1}},\ \ldots,\ \dneg{g_n},\ \dneg{gr}.}\\
\kpi{\phantom{always:}}{executable\ finish\ if\ \mbox{$Q$}, \ \dneg{gr}.}
\kpi{}{caused\ gr\ after\ finish.}
\kpi{}{caused\ gr\ after\ gr.}
\end{kprogram}

Furthermore, we want \inlinek{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 \inlinek{A} in $\PD$, we add 
\begin{kprogram}
\kpi{}{nonexecutable\ A\ if\ finish.}
\end{kprogram}
and add\ \ \inlinek{\dneg{gr}}\ \
to the \inlinek{if}-part of each executability condition for 
\inlinek{A}.
Finally, to avoid any inconsistencies from static or dynamic effects
as soon as the goal has been reached, we add\ \ \inlinek{\dneg{gr}}\ \
to the \inlinek{if} part of any causation rule of the $\PD$ except 
\inlinek{nonexecutable} rules which remain unchanged.%
\footnote{There is no need 
to rewrite \inlinek{nonexecutable} rules because the respective actions
are already ``switched off'' by rewriting the executability conditions.}


We define now $\PP[\beta](\PD,Q,i) = \tuple{\PD[\beta],\inlinek{gr}\,? (i+1)}$.
We take $i+1$ as the plan length since 
we need one additional step to execute the \inlinek{finish} action.

By construction, it is easy to see that any optimal plan $\p =
\tuple{A_1,\ldots,A_j, A_{j+1}, \ldots, A_{i+1}}$ for the planning
problem $\PP[\beta]$ must have $A_{j+1} = \{\inlinek{finish}\}$ and
$A_{j+2} = \ldots = A_{i+1} = \emptyset$ for some $j \in\{0,\ldots,
i\}$. We thus have the following desired property.

\begin{proposition}
The optimal plans for $\PP[\beta]$ are in 1-1 correspondence to the
shortest plans reaching $Q$ in \PD. More precisely, $\p =
\tuple{A_1,\ldots,A_{j+1}, \emptyset, \ldots, \emptyset}$ is an optimal
optimistic plan for $\PP[\beta](\PD,Q,i)$ and $A_{j+1} =
\{\inlinek{finish}\}$ if and only if $\p' = \tuple{A_1,\ldots,A_{j}}$
is an optimistic plan for $\tuple{\PD,Q\,?\,(j)}$ where $j\in\{0,\ldots,i\}$, and $\tuple{\PD,Q\,?\,(j')}$ has
no optimistic plan for each $j'<j$.
\end{proposition}

\noindent In our Blocks World example, using this method we get all 2-step
plans, if we choose $i\geq 2$.

To compute shortest plans over all plan lengths, we can
set the upper bound $i$ large enough such that plans of 
length $l\leq 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-s_{init}-s_{goal}$ steps, where $s_{init}$ and $s_{goal}$ are the
numbers of stacks in the initial and the goal state, respectively.%
\footnote{One can solve any Blocks World problem sequentially
by first unstacking all blocks which are not on the table
($n-s_{init}$ steps) and then building up the goal configuration
($n-s_{goal}$ steps).}  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~\ref{sec:bench}).

\subsubsection{Shortest among the Cheapest Plans ($\gamma$)} 
\label{sec:gamma}

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 \inlinek{finish} at least as high as the
highest possible cost of the \inlinek{finish} action.  This is 
% highest action cost for \inlinek{finish} 
is obviously the plan length $i+1$.  So, we simply modify all action
declarations 
\begin{kprogram}
\kpi{}{A\ requires\ B\ costs\ C\ where\ D.}
\end{kprogram}
in $\PP[\beta]$ by multiplying the costs with factor $i+1$:
\begin{kprogram}
\kpi{}{A\ requires\ B\ costs\ C_1\ where\ C_1=\mbox{$(i+1)$}*C,\ D.}
\end{kprogram}
 This lets all other action costs take priority over the cost of
\inlinek{finish} and we can compute plans satisfying criterion
($\gamma$). Let $\PP[\gamma]$ denote the resultant planning problem.
Then we have:

\begin{proposition}
The optimal plans for $\PP[\gamma]$ are in 1-1 correspondence to the
shortest among the cheapest plans reaching $Q$ in \PD within $i$ steps. More precisely, $\p =
\tuple{A_1,\ldots,A_{j+1}, \emptyset, \ldots, \emptyset}$ is an optimal
optimistic plan for $\PP[\gamma](\PD,Q,i)$ and $A_{j+1} =
\{\inlinek{finish}\}$ if and only if  (i) $\p' = \tuple{A_1,\ldots,A_{j}}$
is a plan for $\PP[j]=\tuple{\PD,Q\,?\,(j)}$, where $j\in\{0,\ldots,i\}$,  and (ii) if  $\p'' = \tuple{A_1,\ldots,A_{j'}}$
is any plan for $\PP[j']=\tuple{\PD,Q\,?\,(j')}$ where $j'\leq i$, then
either $\plancost{\PP[j']}{\p''} > \plancost{\PP[j]}{\p'}$ or
$\plancost{\PP[j']}{\p''} = \plancost{\PP[j]}{\p'}$ and $j'\geq j$. 
\end{proposition}

\begin{figure}[ht]
\begin{kprogram}
\kpi{fluents:}{on(B,L)\ requires\ block(B),\ location(L).}
\kpi{}{blocked(B)\ requires\ block(B).}
\kpi{}{moved(B)\ requires\ block(B).}
\kpi{}{gr.}[1.5ex]
\kpi{actions:}{move(B,L)\ requires\ block(B),\ location(L)\ costs\ C\ where\ C=7*1.}
\kpi{}{finish\ costs\ time.}[1.5ex]
\kpi{always:}{executable\ move(B,L)\ if\ B \kuneq L, \dneg{gr}.}
\kpi{}{nonexecutable\ move(B,L)\ if\ blocked(B).}
\kpi{}{nonexecutable\ move(B,L)\ if\ blocked(L).}
\kpi{}{nonexecutable\ move(B,L)\ if\ move(B1,L),\ B < B1,\ block(L).}
\kpi{}{nonexecutable\ move(B,L)\ if\ move(B,L1),\ L < L1.}
\kpi{}{nonexecutable\ move(B,B1)\ if\ move(B1,L).}[1.5ex]
\kpi{}{caused\ on(B,L)\ if\ \dneg{gr}\ after\ move(B,L).}
\kpi{}{caused\ blocked(B)\ if\ on(B1,B),\ \dneg{gr}.}
\kpi{}{caused\ moved(B)\ if\ \dneg{gr}\ after\ move(B,L).}
\kpi{}{caused\ on(B,L)\ if\ \dneg{moved(B)},\ \dneg{gr}\ 
after\ on(B,L).}[1.5ex]
\>\inlinek{executable\ finish\ if\ }\=
\inlinek{on(1,3),on(3,table),on(2,4),on(4,table),}\\
\>\>\inlinek{on(6,5),on(5,table),\dneg{gr}.}\\
\kpi{}{caused\ gr\ after\ finish.}
\kpi{}{caused\ gr\ after\ gr.}
\kpi{}{nonexecutable\ move(B,L)\ if\ finish.}[1.5ex]
\kpi{initially:}{on(1,2).\ on(2,table).\ on(3,4).\ on(4,table).\ on(5,6).\ on(6,table).}[1.5ex]
\kpi{goal:}{gr?\ (7)}
\end{kprogram}
\caption{Computing the shortest plan for a Blocks World instance with a minimum
number of actions}
\label{fig:bwmin}
\end{figure}

Figure~\ref{fig:bwmin} shows $\PP[\gamma]$ for our Blocks World instance
where $i=6$. One optimal plan for $\PP[\gamma]$ is 
% Computing this plan is rather slow: takes 37.65s on my machine
% (einem.kr.tuwien.ac.at: PIII 733MHz, 256 MB RAM)
%   time dl bwgamma.plan bw.bk -planlength=7 -FPsec -silent -N=7 -n=1
% plan length higher than 7 seems to be beyond our range:
% I skipped a first try with plan length 12 after 1hr20min. 
\begin{kplan}
\kpli{\kpl{}}{\set{move(3,table)},\ \set{move(1,3),move(5,table)},}
\kpi{}{\set{move(2,4),move(6,5)},\ \set{finish},\ \emptyset,\ \emptyset,\
\emptyset\ \rangle,}  
\end{kplan}
which has $\plancost{\PP[\gamma]}{\p} = 39$. 
%As mentioned above, 6 is an upper bound for
%the plan length. But we have to take plan length $i+1=7$ to add the final
%\inlinek{finish} action. 
We can now compute the optimal cost wrt.\ optimization ($\gamma$)
by subtracting the cost of \inlinek{finish} and dividing by $i+1$: 
$(39 - 4) \div (i+1) = 35 \div 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 \inlinek{finish} action, 
i.e. $3$. Thus, we need at least 3 steps for a plan with five moves.

\subsubsection{Cheapest among the Shortest Plans ($\delta$)} 
\label{sec:delta}

Again, we can use the rewriting for optimization ($\beta$).  The cost
functions have to be adapted similarly as in the previous subsection, such
that now the cost of the action \inlinek{finish} takes priority over
all other actions costs. To this end, it is sufficient to set the cost
of \inlinek{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,\ldots,i+1$. Let $\PP[\delta]$
denote the resulting planning problem. We have:

\begin{proposition}
The optimal plans for $\PP[\delta]$ are in 1-1 correspondence to the
cheapest among the shortest plans reaching $Q$ in \PD within
$i$ steps. More precisely, $\p = \tuple{A_1,$ $\ldots,A_{j+1}, \emptyset,
\ldots, \emptyset}$ is an optimal optimistic plan for
$\PP[\delta](\PD,Q,i)$ and $A_{j+1} = \{\inlinek{finish}\}$ if and only if
(i) $\p' = \tuple{A_1,\ldots,A_{j}}$ is a plan for
$\PP[j]=\tuple{\PD,Q\,?\,(j)}$, where $j\in \{0,\ldots,i\}$, and (ii) if $\p'' =
\tuple{A_1,\ldots,A_{j'}}$ is any plan for
$\PP[j']=\tuple{\PD,Q\,?\,(j')}$ where $j'\leq i$, then either $j'>
j$, or $j'=j$ and $\plancost{\PP[j']}{\p''} \geq \plancost{\PP[j]}{\p'}$.
\end{proposition}

In our example, there are 36 possible moves. Thus, we could take $F =
36*(i+1)$ and would set the costs of \inlinek{finish} to
$\inlinek{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 
\inlinek{finish} cost $\inlinek{time}*F=\inlinek{time}*42$. 
Accordingly, the action declarations are modified as follows:
\begin{kprogram}
\kpi{actions:}{move(B,L)\ requires\ block(B),\ location(L)\ costs\ 1.}
\kpi{}{finish\ costs\ C\ where\ C=time*42.}[1.5ex]
\end{kprogram}
% This plan is computed rather quick (0.340s):
%  time dl bwdelta.plan bw.bk -planlength=7 -FPsec -silent -N=49   
An optimal plan for the modified planning problem $\PP[\delta]$ is:
\begin{kplan}
\kpli{\kpl{}}{\set{move(1,table), move(3,table), move(5,table)},}
\kpi{}{\set{move(1,3), move(2,4), move(6,5)},\ \set{finish},\ \emptyset,\ \emptyset,\ \emptyset,\ \emptyset \rangle}
\end{kplan}
We have $\plancost{\PP[\delta]}{\p} = 132$. Here, we can compute the optimal 
cost wrt.\ optimization ($\delta$) by simply subtracting the cost 
of \inlinek{finish}, i.e. $132 - 3*42 = 6$, since \inlinek{finish} 
occurs at time point $3$. 
Consequently, we need a minimum of
$6$ moves for a shortest plan, which has length $3-1=2$.

\medskip

And indeed, we have seen that (and how) the optimization problems ($\alpha$)
through $(\delta)$ can be represented in $\Kc$. We remark that the
transformations $\PP[\beta]$, $\PP[\gamma]$, and $\PP[\delta]$ all work
under the restrictions to secure and/or sequential plans as well.

\subsection{Traveling Salesperson}
\label{sec:tsp}

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

\paragraph{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~\ref{fig:tspaustria} 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.

\begin{figure}[h!]
\centering
\epsfig{file=tsp-austria.eps,width=10cm}
\caption{TSP in Austria}
\label{fig:tspaustria}
\end{figure}

We represent this in \Kc as follows. The background knowledge \BK[TSP] defines two predicates \inlinek{city(C)} 
and \inlinek{conn(F,T,C)} representing the cities and their connections with
associated costs. Connections can be traveled in both ways:
\begin{bgprogram}
\bgpi{conn(brg,ibk,2).\ conn(ibk,sbg,2).\ conn(ibk,vie,5).\ conn(ibk,kla,3).}
\bgpi{conn(sbg,kla,2).\ conn(sbg,gra,2).\ conn(sbg,lin,1).\ conn(sbg,vie,3).}
\bgpi{conn(kla,gra,2).\ conn(lin,stp,1).\ conn(lin,vie,2).\ conn(lin,gra,2).}
\bgpi{conn(gra,vie,2).\ conn(gra,eis,1).\ conn(stp,vie,1).\ conn(eis,vie,1).}
\bgpi{conn(stp,eis,2).\ conn(vie,brg,1).}
\bgpi{conn(B,A,C)\ \derives\ conn(A,B,C).}
\bgpi{city(T)\ \derives\ conn(T,\_,\_).}
\end{bgprogram}
A possible encoding of TSP starting in
Vienna (\inlinek{vie}) is the \Kc program in Figure~\ref{fig:tsp}. 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. 

\begin{figure}[ht]
\begin{kprogram}
\kpi{actions: }{travel(X,Y)\ requires\ conn(X,Y,C)\ costs\ C.}
\kpi{}{return\_from(X)\ requires\ conn(X,vie,C)\ costs\ C.}[1.0ex]
\kpi{fluents:} {unvisited.\ end.}
\kpi{}{in(C)\ requires\ city(C).}
\kpi{}{visited(C)\ requires\ city(C).}[1.0ex]
\kpi{always:}{executable\ travel(X,Y)\ if\ in(X).}
\kpi{}{nonexecutable\ travel(X,Y)\ if\ visited(Y).}
\kpi{}{executable\ return\_from(X)\ if\ in(X).}
\kpi{}{nonexecutable\ return\_from(X)\ if\ unvisited.}[1.0ex]
\kpi{}{caused\ unvisited\ if\ city(C),\ not\ visited(C).}
\kpi{}{caused\ end\ after\ return\_from(X).}
\kpi{}{caused\ in(Y)\ after\ travel(X,Y).}
\kpi{}{caused\ visited(C)\ if\ in(C).}
% We could also write ``caused visited after visited.'' here! 
\kpi{}{inertial\ visited(C).}[1.0ex]
\kpi{noConcurrency.}{}[1.0ex]
\kpi{initially:}{in(vie).}
\kpi{goal:}{end?\ (9)}
\end{kprogram}
\caption{Traveling Salesperson}
\label{fig:tsp}
\end{figure}

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

{\footnotesize
\begin{kplan}
\kpli{\kpl{1}}{\set{travel(vie,stp)},\ \set{travel(stp,eis)},\ \set{travel(eis,gra)},\ \set{travel(gra,lin)},}
\kpli{}{\set{travel(lin,sbg)},\ \set{travel(sbg,kla)},\ \set{travel(kla,ibk)},\ \set{travel(ibk,brg)},}
\kpli{}{\set{return\_from(brg)}\ \rangle}
\kpli{\kpl{2}}{\set{travel(vie,eis)},\ \set{travel(eis,stp)},\ \set{travel(stp,lin)},\ \set{travel(lin,sbg)},} 
\kpli{}{\set{travel(sbg,gra)},\ \set{travel(gra,kla)},\ \set{travel(kla,ibk)},\ \set{travel(ibk,brg)},}
\kpli{}{\set{return\_from(brg)}\ \rangle}
\kpli{\kpl{3}}{\set{travel(vie,eis)},\ \set{travel(eis,stp)},\ \set{travel(stp,lin)},\ \set{travel(lin,gra)},}
\kpli{}{\set{travel(gra,kla)},\ \set{travel(kla,sbg)},\ \set{travel(sbg,ibk)},\ \set{travel(ibk,brg)},}
\kpli{}{\set{return\_from(brg)}\ \rangle}
\kpli{\kpl{4}}{\set{travel(vie,lin)},\ \set{travel(lin,stp)},\ \set{travel(stp,eis)},\ \set{travel(eis,gra)},}
\kpli{}{\set{travel(gra,kla)},\ \set{travel(kla,sbg)},\ \set{travel(sbg,ibk)},\ \set{travel(ibk,brg)},}
\kpli{}{\set{return\_from(brg)}\ \rangle}
\kpli{\kpl{5}}{\set{travel(vie,gra)},\ \set{travel(gra,eis)},\ \set{travel(eis,stp)},\ \set{travel(stp,lin)},}
\kpli{}{\set{travel(lin,sbg)},\ \set{travel(sbg,kla)},\ \set{travel(kla,ibk)},\ \set{travel(ibk,brg)},}
\kpli{}{\set{return\_from(brg)}\ \rangle}
\end{kplan}
}
\paragraph{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{\"o}lten 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{\"o}lten 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 \BK[TSP] a new
predicate \inlinek{cost(A,B,W,C)} representing the cost \inlinek{C} of
traveling connection \inlinek{A} to \inlinek{B} on weekday \inlinek{W}
which can take exceptional costs into account:
\begin{kprogram}
\inlinek{cost(A,B,W,C)\ }\=\inlinek{\derives\ conn(A,B,C),\ \#int(W),
\ 0 < W,\ W <= 7,\ not\ ecost(A,B,W).}\\
\inlinek{ecost(A,B,W)}\>\inlinek{\derives\ conn(A,B,C),\ cost(A,B,W,C1),\ C \kuneq C1.}\\
\end{kprogram}
The original costs in the predicate \inlinek{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:
\begin{bgprogram}
\bgpi{cost(stp,eis,2,10).\quad cost(vie,brg,1,10).}
\end{bgprogram}
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 \BK[TSP]:
\begin{bgprogram}
\bgpi{weekday(1,1).}
\bgpi{weekday(D,W)\ \derives\ D=D1+1,\ W=W1+1,\ weekday(D1,W1),\ W1 < 7.}
\bgpi{weekday(D,1)\ \derives\ D=D1+1,\ weekday(D1,7).}
\end{bgprogram}
Note that although the modified background knowledge \BK[TSP] is not 
stratified (since \inlinek{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~\ref{fig:tsp}:
\begin{kprogram}
\inlinek{actions:}\>$\,$\inlinek{~~travel(X,Y)\ }\=
\inlinek{requires\ conn(X,Y,C1)\ costs\ C}\\
\>\>\inlinek{where\ weekday(time,W),\ cost(X,Y,W,C).}\\
\>\inlinek{return\_from(X)\ }\=\inlinek{requires\ conn(X,vie,C1)\ costs\ C}\\
\>\>\inlinek{where\ weekday(time,W),\ cost(X,vie,W,C).}\\
\end{kprogram}

Since now the costs for $\p_1$ (which includes traveling
from St.P{\"o}lten 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 $\p_2$ and
$\p_3$.  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.

\subsection{A Small Example for Planning under Resource Restrictions}
\label{sec:buying}

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 \cite{lee-lifs-2001}: 
\begin{quote}
``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?'' 
\end{quote}

\noindent In \Kc, this can be encoded in a very compact way by the following 
background facts:
\begin{bgprogram}
\bgpi{item(newspaper,1).\quad item(magazine,2).}
\end{bgprogram}
combined with the following short \Kc program:
\begin{kprogram}
\inlinek{actions: }\>\inlinek{buy(Item,Number)\ }\=
\inlinek{requires\ item(Item,Price),\ \#int(Number)}\\
\>\>\inlinek{costs\ C\ where\ C = Number * Price.}\\[1.0ex]
\kpi{fluents:}{have(Item,Number)\ requires\ item(Item,Price),\ \#int(Number).}[1.0ex]
\kpi{always:}{executable\ buy(Item, Number).}
\kpi{}{nonexecutable\ buy(Item, N1)\ if\ buy(Item, N2),\ N1 < N2.}
\kpi{}{caused\ have(Item,Number)\ after\ buy(Item,Number).}[1.0ex]
\kpi{goal:}{have(newspaper,1),\ have(magazines,2)\mbox{$\,$}?\mbox{$\,$}(1)}
\end{kprogram}

The action \inlinek{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,
\inlinek{\langle \set{buy(newspaper,1), buy(magazine,2)}\, \rangle}
has  $\optcost{\PP} = 7$. Therefore, the answer to the problem is ``no.''

\medskip

Our approach considers only positive action costs and does not directly allow 
modeling full consumer/produ\-cer/provider relations on resources
in general, in favor of a clear non-ambiguous definition of
optimality. 
% Action costs allow us only to model positive resource consumption 
% directly, but not negative (production or provider) effects on the contrary. 
% Mixed consumer/poducer/provider relations do not allow for a direct and 
%clear definition of optimality of a plan without ambiguity: 
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.

\section{Transformation to Logic Programming}
\label{sec:transformation}

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 \cite{eite-etal-2001e},
which maps ordinary \K planning problems
to disjunctive logic programs under the answer set semantics
\cite{gelf-lifs-91}, and takes advantage
of weak constraints, cf.\ \cite{bucc-etal-97a,bucc-etal-99b}, as
implemented in the \dlv system~\cite{dlv-web,eite-etal-2000c}.
In addition, we show how this translation can be adapted to the
language of Smodels~\cite{simo-etal-2002}.

\subsection{Disjunctive Logic Programs with Weak Constraints}

First, we give a brief review of disjunctive logic programs with weak
constraints.

\paragraph{Syntax}
% First, let us review Disjunctive logic programs with 
% weighted weak constraints.

A {\em disjunctive rule} (for short, {\em rule}) \R{} is a construct
\begin{equation}
a_1\ \Or\ \cdots\ \Or\ a_n\ \derives\  b_1,\cdots, b_k,\ 
        \naf\ b_{k+1},\cdots,\ \naf\ b_m.
\label{stmt:dlrule}
\end{equation}
where all $a_i$ and $b_j$ are classical literals over a function-free
first-order alphabet, and $n\geq 0,$ $m\geq
k\geq 0$. The part left (resp.\ right) of ``\derives'' is the 
{\em head} (resp.\ {\em body}) of \R{}, where
``\derives'' is omitted if \mbox{$m=0$}.  We let
$H(R)=\{a_1,\ldots$, $a_n \}$ be the set of head literals and
\mbox{$\BR{}=\BpR \cup \BnR$} the set of body literals, where $\BpR=$
$\{b_1,$\ldots, $b_k\}$ and $\BnR=\{b_{k+1},$ \ldots, $b_m \}$.
A {\em (strong) constraint} is a rule with empty head ($n=0$). 

A {\em weak constraint} is a construct
\begin{equation}
\wc\ b_1,\cdots, b_k,\ \naf\ b_{k+1},\cdots,\ \naf\ b_m.\ [w:]
 \label{stmt:wconstr}
\end{equation}
where $w$ is an integer constant or a variable occurring in 
$b_1, \ldots, b_k$ and all $b_i$ are classical literals.%
\footnote{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.}
$\BR$ is defined as for (\ref{stmt:dlrule}).

A {\em disjunctive logic program (DLP$^w$)}
(simply, {\em program}) is a finite set of rules, constraints and
weak constraints; here, superscript $w$ indicates the
potential presence of weak constraints. 

\paragraph{Semantics}

The answer sets of a program $\Pi$ without weak constraints are defined as usual
\cite{gelf-lifs-91,lifs-96}. 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'$ of $\Pi$ as optimal answer sets.

A weak constraint $c$ of form (\ref{stmt:wconstr}) 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 $\theta$ from the
variables in $c$ to the Herbrand base of $\Pi$ such that
$\{b_1\theta,\cdots,\ b_k\theta\} \subseteq S$ and
$\{b_{k+1}\theta,\cdots,\ b_m\theta\} \cap M = \emptyset$; we then
call $w\theta$ the \emph{violation value} of $c$ wrt.\ $\theta$.%
\footnote{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.} The \emph{violation
cost} of $c$ wrt.\ $S$, denoted $\mathsf{cost}_c(S)$, is the sum of
all violation values over all violating substitutions for $c$ wrt.\
$S$; the {\em cost of $S$}, denoted $\mathsf{cost}_\Pi(S)$, is then
$$
\mathsf{cost}_\Pi(S) = \sum_{c\,\in\,\mathrm{weak\ constraints\ of\ \Pi}}\mathsf{cost}_c(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 \emph{optimal answer set}), if
$\mathsf{cost}_\Pi(M)$ is minimal over all answer sets of  $\Pi$.

From~\cite{bucc-etal-99b} we know that given a 
head-cycle-free disjunctive program, deciding whether a query $q$ is true 
in some optimal answer set is $\DeltaP{2}$-complete. The respective class 
for computing such an answer set 
is $\FDeltaP{2}$-complete. Together with the results from
Section~\ref{sec:complexity} 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.

\subsection{Translating \Kc to DLP$^w$}

We extend our original transformation \LPP, which naturally maps a $\K$
planning problem \PP into a weak-constraint free program
\cite{eite-etal-2001e},
to a new translation \LPPw, such that the optimal answer sets
of \LPPw correspond to the optimal cost plans for the $\Kc$ planning
problem $\PP$.

Basically, in \LPP 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.
\nop{***
For example, the executability condition of action \inlinek{cross}, 
\begin{bgprogram}
\bgpi{executable\ cross(X)\ if\ hasLamp(X).}
\end{bgprogram}
results in the rule:
\begin{bgprogram}
\bgpi{cross(X,T)\ \vee\ \TNEG cross(X,T)\ \derives\ hasLamp(X,T),person(X),\ 
next(T,T1).}
\end{bgprogram}
which encodes a guess whether at time point $T$ action
\inlinek{cross(X)} should happen; \inlinek{next(T,T1)} indicates that
the final point in time has not been reached yet, i.e., some action
remains to be done. Causation rules are translated similarly; e.g., 
\begin{bgprogram}
\bgpi{caused\ across(X)\ after\ cross(X),\ \TNEG across(X).}
\end{bgprogram}
results in:
\begin{bgprogram}
\bgpi{across(X,T1)\ \derives\ cross(X,T),\ \TNEG across(X,T), next(T,T1).}
\end{bgprogram}
For further details, we refer to \cite{eite-etal-2001e}. 
***}

\subsubsection{Review of the Translation \LPP}

The basic steps of the translation from \K programs to logic programs are 
as follows (cf.\ \cite{eite-etal-2001e} 
\ifreport
and the Appendix
\fi
for details): 
\paragraph{Step 0 (Macro Expansion):} First, replace
all macros in the \K program by their definitions.

\paragraph{Step 1 (Background Knowledge):}
The background knowledge \BK of $\PP$ is already given as a logic program and is 
included in $\LPP$, without further modification.

\paragraph{Step 2 (Auxiliary Predicates):}
To represent steps, we add the following facts to $\LPP$
\begin{bgprogram}
$\mathtt{time(0)., \ldots, time(}l\mathtt{).}\quad \mathtt{next(0,1)., \ldots, next(}l-1, l\mathtt{).}$\\
\end{bgprogram}
where $l$ is the plan length of the query $\q = G?(l)$ in $\PP$ at hand.

\paragraph{Step 3 (Causation Rules):}
Causation rules are mapped to rules in \LPP by adding type information
and extending fluents and actions with a time stamp using
$\mathtt{time}$ and $\mathtt{next}$. For example,
\begin{bgprogram}
\bgpi{caused\ across(X)\ after\ cross(X),\ \TNEG across(X).}
\end{bgprogram}
leads to rule\ \  {\small\inlinek{ across(X,T_1)\ \derives\ cross(X,T_0),\ \TNEG across(X,T_0),\ person(X),\ next(T_0,T_1).}}\\
in \LPP where \inlinek{T_1,T_0} are new variables.
Here, type information \inlinek{person(X)} for \inlinek{across(X)}, 
and \inlinek{\TNEG across(X)}, taken from the type declaration, is added,    
which helps to avoid unsafe logic programming rules.

\paragraph{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, 
%the executability condition of action \inlinek{cross}, 
\begin{bgprogram}
\bgpi{executable\ cross(X)\ if\ hasLamp(X).}
\end{bgprogram}
becomes\ \ 
{\small\inlinek{cross(X,T_0)\ \vee\ \TNEG cross(X,T_0)\ \derives\ hasLamp(X,T_0),\ person(X),\ next(T_0,T_1).}}\\
which encodes a guess whether at time point \inlinek{T_0}  action
\inlinek{cross(X)} should happen;  again, 
type information \inlinek{person(X)} is added as well as
\inlinek{next(T_0,T_1)} to ensure that \inlinek{T_0} is not the last
time point. 

\paragraph{Step 5 (Initial State Constraints):}
Initial state constraints 
% in $I_{R'}$ 
are transformed like static
causation rules in Step~3, but using the constant 0 instead of the 
variable \inlinek{T_1} and thus need no auxiliary predicate for the time stamp.
For instance,
\begin{kprogram}
\kpi{initially:}{caused\ \TNEG{across(X)}.}
\end{kprogram}
\indent becomes, by again adding the type information\ \ \ 
{\small\inlinek{ \TNEG across(X,0)\ \derives\ person(X).}}
\paragraph{Step 6 (Goal Query):}
Finally, the query \q:
\begin{kprogram}
\inlinek{goal:}\ \ $g_1(\overline{t_1}), \ldots, g_m(\overline{t_m}), 
\dneg{g_{m+1}(\overline{t_{m+1}})}, \ldots, 
\dneg{g_n(\overline{t_n})}~?~(l).$  \\
\end{kprogram}
is translated as follows, where \inlinek{goal\_reached} is a new 0-ary predicate symbol:
\begin{bgprogram}
\inlinek{goal\_reached}\ \derives\ $g_1(\overline{t_1},l), \ldots,
g_m(\overline{t_m},l), \dneg{g_{m+1}(\overline{t_{m+1}},l)}, \ldots, 
\dneg{g_n(\overline{t_n},l)}$.\\
%\phantom{\inlinek{goal\_reached}\ }
\derives\ \dneg{\inlinek{goal\_reached}}.\\ 
\end{bgprogram}

\subsubsection{Extending the Translation to Action Costs}

The extended translation \LPPw for a \Kc problem $\PP$ first includes
all rules of $lp(\PP[nc])$, where $\PP[nc]$ results from $\PP$ by stripping
off all cost parts. Furthermore, the following step is added:

\paragraph{Step 7 (Action Costs):} For any action declaration
$d$ of form (\ref{stmt:actdecl}) with a nonempty \inlinek{costs}-part,
add:
\begin{equation}
\mbox{(i) A new rule $r_d$ of the form\ \ \ \ \ }
\begin{array}{rl}
\inlinek{cost_p(X_1, \ldots, X_n,T,C\theta)\ \derives} & 
\inlinek{p(X_1, \ldots, X_n,T),\, t_1,\ldots, t_m,} \\
& \inlinek{c_1\theta, \ldots, c_k\theta, U = T+1}.
\end{array}
\label{stmt:costrule}
\end{equation}
where \inlinek{cost_p} is a new symbol, \inlinek{T} and \inlinek{U} are new variables and $\theta= \{
\inlinek{time\rightarrow U}\}$. As an optimization, \inlinek{U = T+1} is only present if \inlinek{U} occurs 
elsewhere in $r_d$. 
% In the actual implementation we simply add %nexttime(T,T1) and 
% replace all occurrences of "time" by T1. 
\begin{equation}
\mbox{(ii) A weak constraint $wc_d$ of the form\ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }
\inlinek{\wc\ cost_p(X_1, \ldots, X_n,T,C). \ [C:]\ \ \ \ \ \ \ \ \ \ \ }
\label{stmt:costconstr}
\end{equation}

\noindent For example, the \inlinek{cross} action from 
the Quick  Bridge Crossing Problem is translated to
\begin{bgprogram}
\begin{tabbing}
\inlinek{cost_{cross}(X, T, WX) \derives\ }\= \inlinek{cross(X,T),\ person(X),\ walk(X,WX).}\\[1ex]
\inlinek{\wc\ cost_{cross}(X, T, WX).\ [WX:]}
\end{tabbing}
\end{bgprogram}

\bigskip

As we showed in previous work \cite{eite-etal-2001e}, the answer sets of \LPP
correspond to trajectories of optimistic plans for \PP.  The following
theorem states a similar correspondence result for $\LPPw$ and optimal
plans for $\PP$.
% for plans with action costs.
We define, for any consistent set of ground literals $S$, the sets
$A_j^{S} = \{a(\overline{t}) \mid a(\overline{t},j-1) \in S$, $a \in \acts{}\}$ 
and
$s_j^{S} = \{f(\overline{t}) \mid f(\overline{t},j) \in S,\, f(\overline{t}) \in \lfl\}$, for all
$j\geq 0$.

\begin{theorem}[Answer Set Correspondence]
\label{theo:answersetcorr}
Let $\PP=\tuple{\PD,\q}$ be a (well-defined) \Kc planning problem, and
let \LPPw be the above program.
 Then,
\begin{itemize}
\item[(i)] for each optimistic plan $\p =
\tuple{A_1,\ldots,A_l}$ of \PP and supporting trajectory
$T=\tuple{\tuple{s_0,A_1,s_1}$, $\tuple{s_1,A_2,s_2},$ \ldots,
$\tuple{s_{l-1},A_l,s_l}}$ of $P$, 
there exists some answer set $S$ of \LPPw such 
that $A_j = A_j^S$ for all $j=1,\ldots,l$,  $s_j = s_j^S$, 
for all $j=0,\ldots,l$ and $\plancost{\PP}{\p} = \mathsf{cost}_{\LPPw}(S)$;

\item[(ii)] for each answer set $S$ of \LPPw, the sequence $\p = \tuple{A_1,\ldots,A_l}$ is
a solution of \PP, i.e., an optimistic plan, witnessed by the trajectory 
$T=\tuple{\tuple{s_0,A_1,s_1}$, $\tuple{s_1,A_2,s_2},$ \ldots, 
$\tuple{s_{l-1},A_l,s_l}}$ with $\plancost{\PP}{\p} = \mathsf{cost}_{\LPPw}(S)$,
where $A_j=A_j^S$ and $s_k=s_k^S$ for all $j=1,\ldots,l$ and $k=0,\ldots,l$.
\end{itemize}
\end{theorem}

The proof is based on the resp.\ correspondence result for \K
\cite{eite-etal-2001e}. 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:

\begin{corollary}[Optimal answer set correspondence] For any
well-defined \Kc planning problem $\PP = \tuple{\PD,Q\,?\,(l)}$, the 
trajectories $T=\tuple{\tuple{s_0,A_1,s_1}$, \ldots, 
$\tuple{s_{l-1},A_l,s_l}}$ of optimal
plans $\p$ for $\PP$  correspond to the 
optimal answer sets $S$ of \LPPw, such that $A_j = A_j^S$ for 
all $j=1,\ldots,l$  and $s_j = s_j^S$, for all $j=0,\ldots,l$. 
\end{corollary}

\begin{proof} For each $a\in A_j$, the weak constraint (\ref{stmt:costconstr})
causes a violation value of $cost_{j}(a)$. Furthermore, these
are the only cost violations. Thus, a candidate answer set $S$ is 
optimal if and only if 
$\mathsf{cost}_{\LPPw}(S) = \sum_{j=1}^l \sum_{a\in A_j} cost_{j}(a) = \plancost{\PP}{P}$ 
is minimal, i.e., $S$ corresponds to an optimal plan.
\end{proof}

\bigskip

A similar correspondence result also holds for admissible plans:

\begin{corollary}[Answer set correspondence for admissible plans] For any
well-defined \Kc planning problem $\PP = \tuple{\PD,Q\,?\,(l)}$, the trajectories
$T=\tuple{\tuple{s_0,A_1,s_1}$, \ldots, $\tuple{s_{l-1},A_l,s_l}}$ of
admissible plans $\p$ for $\PP$ wrt.\ cost $c$ correspond to the
answer sets $S$ of \LPPw having
$\mathsf{cost}_{\LPPw}(S)\leq c$, such that $A_j = A_j^S$ for all
$j=1,\ldots,l$ and $s_j = s_j^S$, for all $j=0,\ldots,l$.
\end{corollary}

%\subsubsection{Secure Planning}

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 \cite{eite-etal-2001e}.
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. 

\subsection{Alternative Translation for Smodels}
\label{sec:smodelstrans}
Apart from the presented translation using weak constraints,
one could also choose an alternative 
approach for the translation to answer set programming.
 Smodels~\cite{simo-etal-2002} supports another extension to pure answer 
set programming allowing to minimize over sets of predicates.
% (see~\cite{simo-etal-2002} for details).

This approach could be used in an alternative formulation of Step 7:
\paragraph{Step 7a:} For action declarations with nonempty \inlinek{costs}-parts, we add a new rule of form
\begin{equation}
\begin{array}{rl}
\inlinek{cost(p,X_1, \ldots, X_n,0,\ldots,0,T,C\theta)\ \derives\ 
t_1,\ldots, t_m,}\ \inlinek{c_1\theta, \ldots, c_k\theta, U = T+1}.
\end{array}
\end{equation}
similar to Step 7 above, with two differences: (1) action name \inlinek{p} is now a parameter, and (2) we add $l-\inlinek{n}$ parameters with constant ``0'' 
between \inlinek{X_n} and \inlinek{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 \inlinek{cost}.
Furthermore, we add 
\begin{equation}
\begin{array}{rl}
\inlinek{occurs(p,X_1, \ldots, X_n,0,\ldots,0,T)\ \derives\  
p(X_1, \ldots, X_n,T),\, t_1,\ldots, t_m,}.
\end{array}
\end{equation}
This second rule adds the same ``0'' parameters as for to achieve 
unique arity $l+1$ of the new predicate \inlinek{occurs}.
Using Smodels syntax, we can now compute optimal plans by adding 
\begin{bgprogram}
\inlinek{minimize[occurs(A,X_1,...,X\mbox{\small$_l$},T) : cost(A,X_1,...,X\mbox{\small$_l$},T,C) = C]}.\\
\end{bgprogram}
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.

% Include this subsection only in the report 
\ifreport 

\subsubsection{Checking Well-Definedness}
\label{sec:WD}

As already mentioned earlier, it is possible to check the
well-definedness of a planning problem $\PP = \tuple{\PD,Q\,?\,(l)}$ 
by evaluating a logic program.%
\footnote{Note that such check is not yet included in the current
implementation.}
We construct such a logic program \BK[WD] extending the background
knowledge \BK as follows. Similar to Step 7 of the translation
$\LPPw$, for any action declaration in \PD with a non-empty
\inlinek{costs} part
\begin{bgprogram}
\bgpi{p(X_1,\ldots,X_n)\ requires\ \mbox{$B$}\ costs\ \mbox{$C$}\ 
where\ \mbox{$W$}.} 
\end{bgprogram}
\noindent we add the rules:
\begin{bgprogram}
\bgpi{c_p(X_1,\ldots,X_n,T,\mbox{$C\theta$})\ \derives\ \mbox{$B,W\theta$}, t(T).}
\bgpi{\ \ \ \ \ sc_p(X_1,\ldots,X_n,T)\ \derives\ c_p(X_1,\ldots,X_n,T,C).}
\end{bgprogram}
to \D[WD], where $\theta = \{\inlinek{time}/\inlinek{T}\}$ and
\inlinek{T} is a new variable and \inlinek{t} a new
predicate. Furthermore, we add the facts:
\begin{bgprogram}
\bgpi{t(1).\ \ldots\ t(\mbox{$l$}).}
\end{bgprogram}
For each action declaration in \AD, we add three constraints:
%using the auxiliary predicates defined before:
\begin{bgprogram}
\bgpi{\derives\ \mbox{$B$}, t(T), 
                \dneg{sc_p(X_1,\ldots,X_n,\inlinek{T})}.}
\bgpi{\derives\ c_p(X_1,\ldots,X_n,\inlinek{T},C),\ \dneg{\#int(C).}}
\bgpi{\derives\ c_p(X_1,\ldots,X_n,\inlinek{T},C),\ 
                       c_p(X_1,\ldots,X_n,\inlinek{T},C1),\ C < C1.}
\end{bgprogram}
where $B$ again is the \inlinek{requires} part of the respective declaration.

Knowing that \BK has a unique answer set, the following result is
obvious as the three constraints exactly check the conditions of
well-definedness (i.e. that for any legal action instance costs are 
defined, integer and unique):

\begin{proposition}
The logic program \BK[WD] has an answer set if and only if
the planning problem $\PP$ is well-defined wrt.\ action costs.
\end{proposition}

Note that by predicate \inlinek{t(X)} we only consider a limited time 
range from 1 up to the plan length $l$ of \PP in our translation in order to 
keep the program finite. 
 Although this does not exactly reflect Definition~\ref{def:wd} where we 
claimed that an action-declaration is only well-defined if costs are 
uniquely defined for all integers, this is sufficient for well-definedness 
of the costs of a plan: 
Concerning the unique costs of a plan for problem \PP, only the observed 
range between 1 and $l$ is relevant, while ambiguous costs for integers 
outside this range do not influence plan costs. 
 If we would, on the other hand, define the predicate \inlinek{t(X)} over 
all integers, this would result in a logic program over an infinite domain, 
which is, in general, undecidable.

\medskip
\noindent
In a similar way, checking well-definedness is alternatively possible
via planning in the language \K: From the original \Kc
planning problem $\PP = $\tuple{\PD,Q\,?\,(l)}, we construct a \K
planning domain \PD[WD] and goal $q$, such that the planning problem
$\tuple{\PD[WD],\,q}$ has a plan just if $\PD$ is
well-defined.

As background knowledge, we take the background knowledge \BK augmented by the facts
\begin{bgprogram}
\bgpi{t(1).\ \ldots\ t(\mbox{$l$}).}
\end{bgprogram}
for a fresh predicate \inlinek{t}. Similar as above, we add for any
action declaration in \D fluent declarations
\begin{bgprogram}
\bgpi{c_p(X_1,\ldots,X_n,T,\mbox{$C\theta$})\ requires\ \mbox{$B,W\theta$}, t(T).}
\bgpi{sc_p(X_1,\ldots,X_n,\inlinek{T})\ requires\ \mbox{$B$}, t(T).}
\end{bgprogram}
to \D[WD], where $\theta = \{\inlinek{time}/\inlinek{T}\}$ and
\inlinek{T} is a new variable. Furthermore, we add a distinct fluent \inlinek{wd} with an empty 
\inlinek{requires} part in its declaration.
The \inlinek{initially}-section in \PD[WD] merely contains
\begin{bgprogram}
\bgpi{caused\ wd.}
\end{bgprogram}
In order to check well-definedness, it is now sufficient
to add the following rules in the \inlinek{initially}-section of 
\PD[WD]:
\begin{bgprogram}
\bgpi{caused\ c_p(X_1,\ldots,X_n,\inlinek{T},C).}
\bgpi{caused\ sc_p(X_1,\ldots,X_n,\inlinek{T})\ if\ 
              c_p(X_1,\ldots,X_n,\inlinek{T},C).} 
\bgpi{forbidden\ c_p(X_1,\ldots,X_n,\inlinek{T},C), 
c_p(X_1,\ldots,X_n,T,C1),\ C < C1.}
\bgpi{forbidden\ \dneg{sc_p(X_1,\ldots,X_n,\inlinek{T})}.}
\bgpi{forbidden\ c_p(X_1,\ldots,X_n,\inlinek{T},C),\ \dneg{\#int(C)}.}
\end{bgprogram}
The \inlinek{always}-section in \PD[WD] is empty. The rules are
similar to those in the logic program $\Pi_{WD}$, but exploit implicit
typing. 

\begin{proposition}
A $\Kc$ planning problem \PP is well-defined, if and only if the
planning problem $\PP[WD] = \tuple{\PD[WD],\inlinek{wd?(0)}}$ has an
optimistic plan.
%if and only if $\PD[WD]$ has a legal initial state.
\end{proposition}

Similar considerations upon the finiteness of the background predicate 
\inlinek{t(X)} as above apply here.
\fi 

% End of additional subsection 

\section{Implementation}
\label{sec:implementation}

We have implemented an experimental prototype system, \dlvk, for
solving \K planning problems%; a detailed description is given in
~\cite{eite-etal-2001e}.  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 \url{http://www.dlvsystem.com/K/}$\,$.

\dlvk has been realized as a frontend to the \dlv
system~\cite{dlv-web,eite-etal-2000c}.
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 \emph{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 \emph{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
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 \emph{optimal secure plans},
the planning frontend interrupts computation, allowing only answer
sets which represent secure plans to be considered as candidates.
\nop{The computation of candidate answer sets in the \dlv 
kernel which is paused during this plan check, is resumed after the check.
}

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. 
\nop{To avoid duplicate secure
checking of a plan, the checked plans are cached.}
As for further details on
the system architecture we refer to \cite{eite-etal-2001e}

\subsection{Usage}
Suppose the background knowledge and the program depicted in
Figure~\ref{fig:crossing} with the cost extensions from 
Section~\ref{sec:crossingopt} are stored in files \texttt{crossing.bk} and
\texttt{crossing.plan}; then, by invoking the program with the command line
\begin{bgprogram}
\bgpi{dlv -FP crossing.plan crossing.bk -planlength=7}
\end{bgprogram}
we compute all optimal plans solving this problem in seven steps.
In the output we find, after a supporting trajectory, the following
optimal plan: 
\begin{kplan}
\kpli{\inlinek{PLAN:}}{crossTogether(joe,jack):2;\ cross(joe):1;\ takeLamp(william);}
\kpli{}{crossTogether(william,averell):10;\ takeLamp(jack);}
\kpli{}{cross(jack):2;\ crossTogether(joe,jack):2\ \ COST:\ 17}
\end{kplan}
For each action, its cost is shown after a colon, if it is
non-zero. The switch \texttt{-planlength=}$i$ can be used to set the
plan length; it overrides any plan length given in the
\inlinek{query}-part of the planing problem. Using \texttt{-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
\texttt{-FPsec} can be used instead of \texttt{-FP} to obtain secure
plans only.

The command line option \texttt{-costbound=}$N$ effects the
computation of all admissible plans with respect to cost $N$. For example, 
the resource problem described in Section~\ref{sec:buying} can be solved 
by the following call to our prototype:
\begin{bgprogram}
\bgpi{dlv -FP buying.bk buying.plan -N=10 -planlength=1 -costbound=6}
\end{bgprogram}
Correctly, no admissible plan is found. 
When calling the system again without
cost bound, the prototype calculates the following 
optimal cost plan:
\begin{kplan}
\kpli{\inlinek{PLAN:}}{buy(newspaper,1):1,\ buy(magazine,2):6\ \ COST:\ 7}
\end{kplan}

The current prototype supports simple bounded integer
arithmetics. The option \texttt{-N=10} used above sets an upper bound of $N=10$ for the integers which may be used in a program;
the built-in predicate \inlinek{\#int} is true for all integers 0
\ldots $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.   
\nop{***
In general, it is not sufficient to set \texttt{-N} simply to the
maximum integer occurring in the background knowledge in our system
since the pre-defined arithmetic predicates ``$a$ = $b$ + $c$'' and
``$a$ = $b$ * $c$'' might produce larger results.
You have to keep in mind to set the upper bound higher than the 
maximum expected integers occurring in the program with respect to these
pre-defined predicates.

As for the the cost function in the \inlinek{where} part of the declaration 
of action \inlinek{buy} (see Section~\ref{sec:buying}), buying 2 magazines 
would result in $C$ to be instantiated with 6.
If now option \texttt{-N} would be set too low, 
we get a bogus result, for instance:
\begin{bgprogram}
\bgpi{dlv -FP buying.bk buying.plan -N=3 -planlength=1 -costbound=6}
\end{bgprogram}
computes the same plan as above but with the wrong cost value
\inlinek{COST:\ 1}.
***}
Further details on the prototype are given on the \dlvk web site at \url{http://www.dlvsystem.com/K/}.

\subsection{Experiments}
\label{sec:bench}

% Optimization $\delta$ seems to be computed overall faster than $\gamma$
% with our system, at least with our Blocks World encoding/examples.
%   Actually $\gamma$ is a harder problem also in an intuitive sense: 
% For example, if you want to compute $\delta$ incrementally you can start 
% with plan length 1 and proceed until a plan is found or an upper bound
% is reached. For $\gamma$ on the other hand, you ALWAYS have to compute all 
% models up to the upper bound: As you cannot be sure whether you do not 
% find a cheaper plan which is longer, you cannot cut off, when a plan 
% of a certain length is found. 
%
%  P0 is the example from this paper.
% 
% Some sample Blocks World instances:
% AMD Athlon 1200MHz, 256 MB RAM
%
% Sequential:
%
%             beta or incr.
%    | time | time$_i$ | steps = moves |
% P0 |0.300s|  0.110s  |     5         |
% P1 |0.030s|  0.050s  |     4         |
% P2 |0.150s|  0.150s  |     6         |
% P3 |20.05s|  1.640s  |     8         |
% P4 |  -   |  7.240s  |     9         |
% P5 |  -   | 11.420s  |    11         |
%
%
% Parallel:
%
%    |    alpha:        || upper ||     beta :                              |
%    |                  || bound:|| -planlength=ub+1 or incr.               |
%    +------------------++-------++------+-----+-----+----------+-----+-----+
%    | time |steps|moves||       || time |steps|moves| time$_i$ |steps|moves|
% P0 |0.030s|   2 |  6  ||   6   ||0.340s|  2  |  6  | 0.040s   |  2  |  6  |
% P1 |0.020s|   3 |  4  ||   4   ||0.040s|  3  |  5  | 0.030s   |  3  |  5  |
% P2 |0.050s|   5 |  6  ||   7   ||0.260s|  5  |  9  | 0.110s   |  5  |  9  |
% P3 |0.140s|   4 |  9  ||  10   ||  -   |  4  |  ?  | 0.260s   |  4  | 12  |
% P4 |0.590s|   5 | 13  ||  16   ||  -   |  5  |  ?  | 1.010s   |  5  | 18  |
% P5 | 249s |   7 | 15  ||  16   ||  -   |  7  |  ?  | 2.420s   |  7  | 26  |
%
%    |     gamma:                  ||           delta:            |
%    |                             ||                             |
%    +-----------------+-----+-----++------+----------+-----+-----+
%    | time | time$_i$ |steps|moves|| time | time$_i$ |steps|moves|
% P0 |26.59s| 0.080s   |  3  |  5  ||0.180s| 0.040s   |  2  |  6  |
% P1 |0.050s| 0.050s   |  3  |  4  ||0.050s| 0.050s   |  3  |  4  |
% P2 |1.430s| 0.160s   |  5  |  6  ||0.510s| 0.150s   |  5  |  6  |
% P3 |  -   | 1.000s   |  5  |  8  || 149s | 0.300s   |  4  |  9  |
% P4 |  -   |   -      |  9  |  9  ||  -   | 1.250s   |  5  | 13  |
% P5 |  -   |   -      | 11  | 11  ||  -   |  251s    |  7  | 15  |

Performance and experimental results for \dlvk (without action costs
and optimal planning) were reported in previous work \cite{eite-etal-2001e}.
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
($\mathcal{C+}$ resp.\ $\mathcal{AR}$) have capabilities similar 
to \K resp.\ \Kc.

\paragraph{CCALC.}
The \emph{Causal Calculator} (\emph{CCALC}) is a model checker for the
languages of causal theories \cite{mcca-turn-97}. It translates
programs in the action language $\mathcal{C+}$ into the language of
causal theories which are in turn transformed into SAT problems;
these are then solved using a SAT solver \cite{mcca-turn-98}.
The current version of CCALC uses 
mChaff \shortcite{mosk-etal-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 
\url{<URL:http://www.cs.utexas.edu/users/tag/cc/>}
and a trial version of SICStus Prolog 3.9.1.
We used encodings taken from~\cite{lee-lifs-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
$\mathcal{C+}$ command ``\inlinek{noConcurrency.}'' which resembles the 
respective \K command. 
All results for CCALC include 2.30sec startup time.

\paragraph{CMBP.}
The \emph{Conformant Model Based Planner} (CMBP)~\cite{cima-rove-2000}
is based on the model checking paradigm and exploits symbolic Boolean function
representation techniques such as Binary Decision Diagrams \cite{brya-86}. 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 $\mathcal{AR}$~\cite{giun-etal-97}.  Unlike \K or action languages such
as $\mathcal{C+}$~\cite{lee-lifs-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 \cite{eite-etal-2001e}.
For our tests, we used CMBP 1.0, available at
\url{<URL:http://sra.itc.it/people/roveri/cmbp/>}.


\subsubsection{Blocks World}

Tables~\ref{tab:bwseq}--\ref{tab:bwpargammadelta} show the results for 
our different Blocks World encodings in Section~\ref{sec:blocksworld} on several configurations: 
P0 denotes our simple instance from Figure~\ref{fig:bw}, while P1--P5 are 
instances used in previous work \cite{eite-etal-2001e,erde-99}.

Table~\ref{tab:bwseq} shows the results for finding a shortest
sequential plan.
%, i.e., plans with no parallel actions (which is
%enforced by the "\inlinek{noConcurrency.}" statement).
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
shortest-plan encoding $\PP[\beta]$ in Section~\ref{sec:blocksworld}
is shown in column five, using the upper bound shown in the fourth
column on the plan length.  Column six
% on the other hand
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.

\begin{table}
\begin{center}
{\footnotesize
\begin{tabular}{|l|c|c|c|c|c||c||c|}\cline{1-8}
\rule{0mm}{3.5mm}
Problem  & \#blocks & min. \#moves (=\#steps) & upper bound \#steps & \dlvk &
\dlvkinc & CCALC & CMBP \\
\cline{1-8}
 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 &   - \\ 
\cline{1-8}
\end{tabular}
}\\
\caption{Sequential Blocks World - shortest plans}
\label{tab:bwseq}
\end{center}
\end{table}

Table~\ref{tab:bwalpha} shows the execution times for parallel blocks
world with fixed plan length where the number of moves is minimized,
i.e.\ problem ($\alpha$) in Section~\ref{sec:opt}. We used the
encoding in Figure~\ref{fig:bwprog}, 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.
\begin{table}
\begin{center}
{\footnotesize
\begin{tabular}{|l|c|c|c|r|}\cline{1-5}
\rule{0mm}{3.5mm}
Problem & \#blocks & \#steps(fixed) & min. \#moves & \dlvk \\
\cline{1-5}
 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 \\ 
\cline{1-5}
\end{tabular}
}\\
\caption{Parallel Blocks World - cheapest plans: Minimal number of moves at fixed plan length ($\alpha$)}
\label{tab:bwalpha}
\end{center}
\end{table}

Next, Table~\ref{tab:bwparbeta} shows some results for finding
a shortest parallel plan, i.e.\ problem ($\beta$) in Section~\ref{sec:opt}.
First, the minimal possible number of steps is given. We processed
each instance (i) using the encoding $\PP[\beta]$ from 
Section~\ref{sec:blocksworld}, (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.

\begin{table}
\begin{center}
{\footnotesize
\begin{tabular}{|l|c|c||c|c||c|c||c|c|}
\cline{1-9}
\rule{0mm}{3.5mm}
   & upper bound & min. \#steps & \multicolumn{2}{c||}{\dlvk} & 
\multicolumn{2}{c||}{\dlvkinc} & \multicolumn{2}{c|}{CCALC}\\
   & & & \#moves & time & \#moves & time &  \#moves & time\\
\cline{1-9}
 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 \\
\cline{1-9}
\end{tabular}
}\\
\caption{Parallel Blocks World - shortest plan ($\beta$)}
\label{tab:bwparbeta}
\end{center}
\end{table}

Finally, Table~\ref{tab:bwpargammadelta} shows the results for the
combined optimizations ($\gamma$) and ($\delta$) for parallel Blocks
World as outlined in Section~\ref{sec:blocksworld}.  The second column
again contains the upper bound for the plan length of the respective
instance. The following three columns present the results on finding
a shortest among the cheapest plans, i.e.\ problem ($\gamma$) in
Section~\ref{sec:opt}:
\begin{description}
\item[\dlvk] refers to the results
for our combined minimal encoding $\PP[\gamma]$ and as 
described in Section~\ref{sec:blocksworld};
\item[\dlvkinc] refers to  the results
for incrementally searching for the shortest among the
cheapest plans: This is done by means of the \texttt{-costbound=}$i$ 
command line option taking the minimal sequential costs 
(i.e., the shortest sequential plan length as computed in 
Table~\ref{tab:bwseq}) 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.
\item[CCALC] A similar technique can be used with CCALC when encoding bound 
costs through ``additive fluents''% like the encoding used in
~\cite{lee-lifs-2001}.
\end{description}

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
($\gamma$) infeasible in general.

The last test is finding a cheapest among the
shortest plans, that is, problem ($\delta$) in Section~\ref{sec:opt}.
Again we have tested the integrated
encoding with an upper bound ($\PP[\delta]$) resp.\ incrementally finding 
the shortest plan. Unlike for problem ($\gamma$), 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.

\begin{table}
\begin{center}
{\footnotesize
\begin{tabular}{|l|c||c|c|c|c||c|c|c|}\cline{1-9}
 &  & \multicolumn{4}{c|}{($\gamma$)} & \multicolumn{3}{c|}{($\delta$)}\\
\cline{3-9}
\rule{0mm}{3.5mm}
 & upper bound & steps/moves& \dlvk & \dlvkinc & CCALC &
steps/moves& \dlvk & \dlvkinc \\
\cline{1-9}
 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 \\
\cline{1-9}
\end{tabular}
}\\
\caption{Parallel Blocks World - ($\gamma$),($\delta$)}
\label{tab:bwpargammadelta}
\end{center}
\end{table}

\paragraph{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~\ref{sec:blocksworld}, 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~\ref{tab:bwseq} 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~\ref{tab:bwalpha}, 
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 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.
% This influences further
% investigations twofold: On the one hand in examining methods to 
% optimize the translation such that the search space is pruned, on the other
% by learning from these hard instances for the further development of
% the underlying \dlv engine itself.

Interestingly, CCALC finds ``better quality'' parallel solutions for
problem ($\beta$) (cf.\ Table~\ref{tab:bwparbeta}), i.e. solutions
with fewer moves, although it is significantly slower than our system
on these instances. For the incremental encoding of problem
($\gamma$), 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 ($\gamma$).

Problem ($\gamma$) 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 ($\gamma$) 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.

\subsubsection{TSP}

Some experimental results on TSP with variable costs are reported in
Tables~\ref{tab:tsp-austria} and~\ref{tab:tsp-eu}. 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~\ref{tab:tsp-austria} shows the results for our TSP instance on
the Austrian province capitals as in Figure~\ref{fig:tspaustria} (nine
cities, 18 connections), with and without the exceptional costs as in
Section~\ref{sec:tsp} (with and without subscript $exc$ in the table). Further
instances reported in this table with different cost exceptions ($we$,
$lwe$, $rnd$) are described below.

\begin{table}
\begin{center}
{\footnotesize
\begin{tabular}{|l|c|c|}\cline{1-3}
Instance & \#cost exceptions & cost/time\\
\cline{1-3}
 TSP$_{Austria}$          &   0 &  15/0.31s\\
 TSP$_{Austria,exc}$      &   2 &  15/0.32s\\
 TSP$_{Austria,we}$       &  36 &  12/0.34s\\
 TSP$_{Austria,lwe}$      &  54 &  11/0.35s\\
 TSP$_{Austria,rnd}$      &  10 &  14/0.30s\\
 TSP$_{Austria,rnd}$      &  50 &  15/0.31s\\
 TSP$_{Austria,rnd}$      & 100 &  23/0.35s\\
 TSP$_{Austria,rnd}$      & 200 &  36/0.37s\\
\cline{1-3}
\end{tabular}
}
\end{center}
\caption{TSP -- Results for TSP$_{Austria}$ with varying exceptions}
\label{tab:tsp-austria}

\bigskip
\bigskip

{\footnotesize
\begin{center}
\begin{tabular}{c@{\qquad}c}
\begin{tabular}{|l|c|c|c|}\cline{1-4}
Instance & \#conn. & \#except. & cost/time\\
\cline{1-4}
 TSP$_{EU1}$            &  30 &   0 &   -/9.11s\\
 TSP$_{EU1,we}$         &  30 &  60 &  -/11.93s\\
 TSP$_{EU1,lwe}$        &  30 &  90 &  -/13.82s\\
 TSP$_{EU1,rnd}$        &  30 & 100 &  -/11.52s\\
 TSP$_{EU1,rnd}$        &  30 & 200 &  -/12.79s\\
 TSP$_{EU1,rnd}$        &  30 & 300 &  -/14.64s\\
 TSP$_{EU1,rnd}$        &  30 & 400 &  -/16.26s\\
\cline{1-4}
 TSP$_{EU2}$            &  30 &   0 &  16213/13.27s\\
 TSP$_{EU2,we}$         &  30 &  60 &  13195/16.41s\\
 TSP$_{EU2,lwe}$        &  30 &  90 &  11738/18.53s\\
 TSP$_{EU2,rnd}$        &  30 & 100 &  15190/15.54s\\
 TSP$_{EU2,rnd}$        &  30 & 200 &  13433/16.31s\\
 TSP$_{EU2,rnd}$        &  30 & 300 &  13829/18.34s\\
 TSP$_{EU2,rnd}$        &  30 & 400 &  13895/20.59s\\
\cline{1-4}
 TSP$_{EU3}$            &  35 &   0 &  18576/24.11s\\
 TSP$_{EU3,we}$         &  35 &  70 &  15689/28.02s\\
 TSP$_{EU3,lwe}$        &  35 & 105 &  14589/30.39s\\
 TSP$_{EU3,rnd}$        &  35 & 100 &  19410/26.75s\\ 
 TSP$_{EU3,rnd}$        &  35 & 200 &  22055/29.64s\\
 TSP$_{EU3,rnd}$        &  35 & 300 &  18354/31.54s\\ 
 TSP$_{EU3,rnd}$        &  35 & 400 &  17285/32.66s\\ 
\cline{1-4}
 TSP$_{EU4}$            &  35 &   0 &  16533/36.63s\\
 TSP$_{EU4,we}$         &  35 &  70 &  12747/41.72s\\
 TSP$_{EU4,lwe}$        &  35 & 105 &  11812/43.12s\\
 TSP$_{EU4,rnd}$        &  35 & 100 &  15553/39.17s\\ 
 TSP$_{EU4,rnd}$        &  35 & 200 &  13216/41.19s\\
 TSP$_{EU4,rnd}$        &  35 & 300 &  16413/43.51s\\ 
 TSP$_{EU4,rnd}$        &  35 & 400 &  13782/45.69s\\ 
\cline{1-4}
 TSP$_{EU5}$            &  40 &   0 &  15716/91.83s\\
 TSP$_{EU5,we}$         &  40 &  80 &  12875/97.73s\\
 TSP$_{EU5,lwe}$        &  40 & 120 &  12009/100.14s\\
 TSP$_{EU5,rnd}$        &  40 & 100 &  13146/85.69s\\ 
 TSP$_{EU5,rnd}$        &  40 & 200 &  12162/83.44s\\
 TSP$_{EU5,rnd}$        &  40 & 300 &  12074/76.81s\\ 
 TSP$_{EU5,rnd}$        &  40 & 400 &  12226/82.97s\\ 
 TSP$_{EU5,rnd}$        &  40 & 500 &  13212/82.53s\\
\cline{1-4}
\end{tabular}
&
\begin{tabular}{|l|c|c|c|}\cline{1-4}
Instance & \#conn. & \#except. & cost/time\\
%Instance & \#connections & \#cost exceptions & cost/time\\
\cline{1-4}
 TSP$_{EU6}$            &  40 &   0 &  17483/142.7s\\
 TSP$_{EU6,we}$         &  40 &  80 &  14336/150.3s\\
 TSP$_{EU6,lwe}$        &  40 & 120 &  13244/154.7s\\
 TSP$_{EU6,rnd}$        &  40 & 100 &  15630/142.5s\\ 
 TSP$_{EU6,rnd}$        &  40 & 200 &  14258/137.2s\\
 TSP$_{EU6,rnd}$        &  40 & 300 &  11754/120.5s\\ 
 TSP$_{EU6,rnd}$        &  40 & 400 &  11695/111.4s\\ 
 TSP$_{EU6,rnd}$        &  40 & 500 &  12976/120.8s\\ 
\cline{1-4}
 TSP$_{EU7}$            &  55 &   0 &  15022/102.6s\\
 TSP$_{EU7,we}$         &  55 & 110 &  12917/112.2s\\
 TSP$_{EU7,lwe}$        &  55 & 165 &  11498/116.2s\\
 TSP$_{EU7,rnd}$        &  55 & 100 &  13990/104.2s\\ 
 TSP$_{EU7,rnd}$        &  55 & 200 &  12461/100.8s\\
 TSP$_{EU7,rnd}$        &  55 & 300 &  13838/106.9s\\ 
 TSP$_{EU7,rnd}$        &  55 & 400 &  12251/96.58s\\ 
 TSP$_{EU7,rnd}$        &  55 & 500 &  16103/109.2s\\ 
 TSP$_{EU7,rnd}$        &  55 & 600 &  14890/110.3s\\ 
 TSP$_{EU7,rnd}$        &  55 & 700 &  17070/110.7s\\
\cline{1-4}
 TSP$_{EU8}$            &  64 &   0 &  10858/3872s\\
 TSP$_{EU8,we}$         &  64 & 128 &  9035/3685s\\
 TSP$_{EU8,lwe}$        &  64 & 192 &  8340/3324s\\
 TSP$_{EU8,rnd}$        &  64 & 100 &  10283/2603s\\ 
 TSP$_{EU8,rnd}$        &  64 & 200 &  9926/1372s\\
 TSP$_{EU8,rnd}$        &  64 & 300 &  10028/1621s\\ 
 TSP$_{EU8,rnd}$        &  64 & 400 &  8133/597.7s\\
 TSP$_{EU8,rnd}$        &  64 & 500 &  8770/573.3s\\ 
 TSP$_{EU8,rnd}$        &  64 & 600 &  8220/360.7s\\ 
 TSP$_{EU8,rnd}$        &  64 & 700 &  6787/324.6s\\
 TSP$_{EU8,rnd}$        &  64 & 800 &  11597/509.5s\\
\cline{1-4}
\multicolumn{4}{c}{}\\
\multicolumn{4}{c}{}\\
\multicolumn{4}{c}{}\\
\multicolumn{4}{c}{}\\
\multicolumn{4}{c}{}\\
\multicolumn{4}{c}{}\\
\multicolumn{4}{c}{}\\
\end{tabular}
\end{tabular}
\end{center}
}
\caption{TSP -- Various instances for the capitals of the 15 EU members}
\label{tab:tsp-eu}
\end{table}

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~\ref{tab:tsp-eu}. 
We have used the flight distances (km) between the cities as connection 
costs. Instances TSP$_{EU1}$--TSP$_{EU6}$ have been generated by randomly 
choosing a given number of connections from all possible connections between 
the 15 cities. Note that TSP$_{EU1}$ 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: TSP$_{EU7}$ is an instance where we have taken
the flight connections of three carriers (namely, Star Alliance,
Alitalia, and Luxair), and in TSP$_{EU8}$ 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~\ref{tab:tsp-austria}--\ref{tab:tsp-eu} we 
have measured the execution time: 
\begin{itemize}
\item without exceptional costs,
\item with 50\% costs for all connections on Saturdays and Sundays (weekends, $we$) 
\item with 50\% costs for all connections on Fridays, Saturdays and 
      Sundays (long weekends, $lwe$), 
\item for some random cost exceptions ($rnd$): We have added a number of randomly generated
      exceptions with costs between 0 and 10 for TSP$_{Austria}$ and 
      between 0 and 3000 for the instances {\em EU1} to {\em EU8}.
\end{itemize}

\paragraph{TSP -- Results}

Instance TSP$_{EU8}$ 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 TSP$_{EU7}$ 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., TSP$_{EU7}$ 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
TSP$_{EU8}$ 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 TSP$_{EU8}$ without exceptional costs.


Note that, we have also experimented with the alternative Smodels translation
sketched in Section~\ref{sec:smodelstrans}. 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.

\section{Related Work}
\label{sec:rel-works}

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~\cite{will-hank-94} 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 \cite{pedn-89}, which is a predecessor of PDDL \shortcite{ghal-etal-98}.  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 \cite{ephr-etal-96} and work by
Refanidis and Vlahavas who use multi-criteria heuristics to obtain
near-optimal plans, considering multiple criteria apart from plan length
alone \cite{refa-vlah-2001}. However, the
described heuristics is not fully admissible, and only
guarantees optimal plans under certain
restrictions~\cite{hasl-geff-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 \cite{nare-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
production/consumption \cite{kaut-wals-99}.
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 \cite{koehler-98}.
Kautz and Walser allow
for arbitrary optimization functions but they use a non-declarative,
low-level representation based on the algebraic modeling language
AMPL~\cite{four-etal-93}.  They mention that Koehler's STRIPS-like
formalization can be mapped to their approach. However, they can not
express non-determinism or incomplete knowledge. There is an
implementation of this approach called ILPPLAN, which uses the AMPL package
(\url{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 $\mathcal{C}+$ of the action
language $\mathcal{C}$ which allows for an intuitive
encoding of resources and costs by means of so called ``additive
fluents'' \cite{lee-lifs-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~\cite{ccalc-web} which has already been described in the
previous section. Another implementation of a planning system based on
the action language $\mathcal{C}$ is
Cplan~\cite{giun-2000,ferr-giun-2000}. The Cplan system mainly focuses
on conformant planning and does not support the advanced features of
$\mathcal{C}+$. Furthermore, the code is no longer maintained.

Son and Pontelli propose to translate action language $\mathcal{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~\cite{son-pont-2002}. 
However, these preferences are orthogonal to our
approach as they model qualitative preferences as opposed to our
overall value function of plans/trajectories.

\section{Conclusion and Outlook}
\label{sec:conclusion}

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 \cite{lifs-99,lifs-99a}.
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
\cite{eite-etal-2000d,eite-etal-2001e} 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
\cite{bucc-etal-97a,bucc-etal-99b}, 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, 
%are first-class objects of the language which 
can be suitably
respected in secure plans, i.e., conformant plans 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.

% Furthermore, there is room for implementation improvements. 


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.

\section*{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 \mbox{P14781} and \mbox{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.

\input{K_appendix-long}

{
\bibliography{bibtex}
\bibliographystyle{theapa}
}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
