% $Id: thesis.tex,v 1.4 1996/2/20 04:39:41 driver Exp $

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Formatting as a thesis 
% (we have to use OLD latex for this--bummer!)


\documentstyle[jair,11pt,theapa,epsf,epic,eepic,subfig,rotating]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definitions used from Dr. rao
%\def\mvp{\vspace*{-0.1in}}
\def\mvp{}
\def\avp{\vspace*{0.1in}}
\def\mfootnotesize{\scriptsize}
%\voffset -0.4truein
%\setlength{\textwidth}{141mm}
%\setlength{\textheight}{8.3in}
\newcommand\changline[1]{ #1 }
\def\dest{\#_{est}}
\def\dclob{\#_{clob}}
\def\ssolve{{\tt solve}}
\def\ssolves{{\tt solves}}
\newcommand{\ilink}[3]{ \langle #1 ,  #2 , #3 \rangle }
\newcommand{\plink}[3]{ \langle #2 , #3 \rangle }
\def\rp{{\tt Refine-Plan-PO}}
\def\popi{{PO }}
\def\cn{{ \cal N }}
\renewcommand{\topfraction}{0.9}
\renewcommand{\textfraction}{.01}
\renewcommand{\floatpagefraction}{.8}
\def\hdstp{{t_{\cal H}}}
\def\fc{{\tt Refine-Plan}}
\def\ha{\hspace*{0.2in}}
\def\mr{{\bf MakeRelevant}}
\def\sval{\langle s\, , p \, , w \rangle}
\def\val{\langle {\cal S}\, , p \, , w \rangle}
\def\vval{v:\langle {\cal S}\, , p \, , w \rangle}
\def\valprime{\langle {\cal S}\, , p' \, , w \rangle}
\def\tsval{ \{ s \} \stackrel{p}{\rightarrow} w}
\def\tval{{\cal S} \stackrel{p}{\rightarrow} w}
\def\cs{{\cal S}}
\def\cm{{\cal M}}
\def\cp{{\cal P}}
\def\cpeg{\cp_{E}}
\def\cv{{\cal V}}
\def\nl{{NONLIN}}
\def\ncd{{\not\approx}}
\def\ni{\noindent}
\def\fs{{|\wp_d|}}
\newtheorem{hyp}{Hypothesis}
\def\lqq{\langle \mkern-4mu\langle}
\def\rqq{\rangle \mkern-4mu\rangle}
\newcommand{\qq}[1]{\lqq#1\rqq}
\def\fc{{\tt Refine-Plan-PO}}
\newcommand{\und}[1]{\noindent {\bf #1}}
\newcommand{\mytypeout}[1]{}
\newcommand{\link}[3]{ #1 \stackrel{#2}{\rightarrow} #3}
\newcommand{\kridea}[1]{}
\newtheorem{prop}{Proposition} \newtheorem{defn}{Definition}
\newtheorem{example}{Example}
%\def\baselinestretch{.985}
\def\plan{ { {\cal P}: \langle T , O , {\cal B} , {\cal ST} , {\cal L} \rangle}}
\def\ind#1{\par\everypar{\hangindent=#1\hangafter=0\hskip-\parindent}}
\def\tmpind#1{\par\hskip#1} \def\eoc{{\sc eoc }}
\def\den#1{ {[}\!\!\!{|} #1 {]}\!\!\!{|}}
\def\mnlp{{ MP }}
\def\popi{{PO }}
\def\mnlpi{{ MP-I }}
\def\cn{{ \cal N }}
\def\mpex{{MPEX }}
\def\fc{{\tt Refine-Plan-plan-space}}
\def\cs{{\cal S}}
\def\cp{{\cal P}}
\def\cv{{\cal V}}
\def\nl{{NONLIN}}
\def\ncd{{\not\approx}}
\def\ni{\noindent}
\newcommand{\fromrao}[1]{}
\newcommand{\from}[2]{{\bf [{\sc from #1:} #2]}}
\newcommand{\Ignore}[1]{}
\def\ind#1{\par\everypar{\hangindent=#1\hangafter=0\hskip-\parindent}}
\def\tmpind#1{\par\hskip#1}
\def\eoc{{\sc eoc }}
\def\mnlp{{ MP }}
\def\popi{{\sc POPI }}
\def\mnlpi{{ MP-I }}
\def\mpex{{\sc mpex }}
\newcommand{\IGNORE}[1]{}
\def\tgg{t_{\infty}}
\def\ti{{t_{0}}}
\def\tstp{{t_{\cal T}}}

\def\we{$\wedge$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
%\jairheading{Volume}{year}{page-page}, e.g.
%% Usage: \jairheading{1}{1993}{1-15}{8/93;}{9/93}
\jairheading{8}{1998}{93--128}{5/97}{3/98}
\ShortHeadings{Synthesizing Customized Planners from Specifications}
{Srivastava \& Kambhampati}

\firstpageno{93}

%% Usage: \jairheading{1}{1993}{1-15}{8/93;}{9/93}
\title{Synthesizing Customized Planners from Specifications}
%:\\ A 
%knowledge-based software engineering approach}
%\title{Semi-automated Synthesis of Planners from Specifications}
%\title{Synthesizing customized planners: A semi-automated approach}
%\title{Semi-automated Synthesis of Customized Planners}

\author{\name Biplav Srivastava \email biplav@asu.edu\\
 \name Subbarao Kambhampati \email rao@asu.edu\\
\addr
Department of Computer Science and
  Engineering\\
Arizona State University, Tempe, AZ 85287.}
%http://rakaposhi.eas.asu.edu/yochan.html}




\maketitle
%\begin{center}
%{\bf ASU CSE TR 96-014}
%\end{center}
% bip-test 
\begin{abstract}
Existing plan synthesis approaches in artificial intelligence
fall into two categories -- 
domain independent and domain dependent.  The domain independent 
approaches are applicable across a variety of domains, but may not be 
very efficient in any one given domain.  The domain dependent 
approaches need to be (re)designed for each domain separately, but can 
be very efficient in the domain for which they are designed. 
One enticing alternative to these approaches is to automatically synthesize
domain independent planners given the knowledge about the domain and
the theory of planning. In this paper, we investigate the feasibility
of using existing automated software synthesis tools to support such
synthesis. Specifically, we describe an architecture called CLAY in which 
the Kestrel Interactive Development System (KIDS) is used to derive a
domain-customized planner through a semi-automatic combination of a 
declarative theory of planning, and the declarative 
control knowledge specific to a given domain, to semi-automatically 
combine them to derive domain-customized planners.
%CLAY shifts the focus of AI planning from the 
%problem of ``efficient plan generation'' to that of ``generation of 
%efficient planners.''   
We discuss what it means to write a declarative theory of planning and
control knowledge for KIDS, and illustrate our approach by generating a class of
domain-specific planners using state space refinements.  Our
experiments show that the synthesized planners can outperform
classical refinement planners \cite<implemented as instantiations of
  UCP,>{bip-ewsp95},  using the same
control knowledge.  We will contrast the costs and benefits of the synthesis
approach with conventional methods for customizing domain independent
planners.
\end{abstract}

\section{Introduction}
\label{sec:introduction}
\mvp

Given the current state of the world, a set of desired goals, and a
set of action templates, ``{\em planning}'' involves synthesizing a
sequence of actions which when executed from the initial state will
lead to a state of the world that satisfies all the goals
\cite{strips,snlp,rao-aimag}.  Planning is known to be a
combinatorially hard problem, and a variety of approaches for plan
synthesis have been developed over the past twenty years.  These
approaches can be classified into two broad categories -- domain independent
and domain dependent.  Domain independent planners do not make any
assumptions about the planning domains, and can thus accept and solve
planning problems from any domain. In contrast, domain specific
planners are specifically designed for a single domain and thus have
the dynamics and control knowledge of the domain hard-coded.

The advantage of domain independent planning is that once a planning 
algorithm is designed, it can be used in any domain by simply changing 
the action template that is input to the algorithm.  In contrast, 
domain-specific planners would have to be ``modified'' or 
``re-designed'' for each  domain.  On the flip-side,
domain-specific planners tend to be more efficient in their designated
domains than domain independent planners since the latter 
may not be able to  effectively exploit the control knowledge of every
domain. 

Not surprisingly, a significant amount of work in AI planning has been
aimed at improving the performance of domain independent planners by
dynamically customizing them to a given domain. This customization is
done by providing the domain writer the ability to control the search
of the planner, as is the case in task-reduction planning
\cite{rao-ucp-tr,rao-htn-sigart}, or by using learning techniques
\cite{rao-ucpopebl,minton-prodigy}. Although several approaches have
been developed for learning to improve planning performance, at
present they are not an effective match for the efficiency of
domain dependent planners.



\begin{figure}
\begin{center}
\epsfxsize=330pt
\epsfbox{plan-synth.ps}
\vspace*{-0.1in}
\end{center}
\caption{Architectural overview of planner synthesis with KIDS in the
         CLAY approach. The theories of refinement planning and domain 
         knowledge are declaratively specified to KIDS which in
         turn combines them to produce a customized planner
         for the domain. The resulting planner, like conventional planners,
         can handle any planning problem from the domain. For a  detailed 
         description, see Section~\ref{sec:synth}.}
\label{synth-ovw-fig}
\end{figure}

One intriguing alternative is to automatically synthesize
domain dependent planners given the knowledge about the domain and the
theory of planning. In this paper, we investigate the feasibility of
using existing automated software synthesis tools to support such
 a synthesis.  We introduce the CLAY architecture which supports the synthesis of
domain dependent planners using KIDS, a semi-automated software synthesis
system.  Specifically, as shown in Figure~\ref{synth-ovw-fig}, a
declarative theory of plan synthesis (theory of planning) is combined
with the control knowledge specific to a given domain in a
semi-automated software synthesis system called Kestrel
Interactive Development System -- KIDS \cite{smith-ieee,smith-gs,smith-trans}
to derive a customized planner for the domain.  We will draw the
declarative theory of plan synthesis from domain independent planning
techniques.  Domain specific control knowledge will be expressed in terms of
the types of plans that are preferred in the given domain.

Such an approach strikes a promising middle-ground between
domain independent and domain dependent planners. The theories of
planning are encoded independent of domains, and the domain control
knowledge can be encoded independent of the specific planning theory
being used. The customization step compiles the domain control
knowledge into the planning algorithm and ensures that the resulting
planners are able to exploit the structure of the domain.


\subsection{Overview of the Synthesis Approach}

As briefly mentioned above, the practicality of our approach is
predicated on the availability of a software synthesis system capable
of deriving code from formal specifications. KIDS is a powerful
semi-automated system for development of correct and efficient
programs from formal specifications.  Given a domain theory and the
input/output specification of a task, KIDS system helps in
synthesizing a program capable of solving the task.  Here, the term
{\em theory} refers to any useful body of knowledge. {\em Task}
refers to any assignment that is given to KIDS for solving and the
solution is a  {\em program} for that task. The
input to KIDS is a task  theory comprised of the task
specification and a declarative description of useful concepts and
rules to reason in the task space. In this research, we give
planning as a task to KIDS and expect it to synthesize and return a
planner as the solution.  The planner can then take planning {\em problems} as
input and return {\em results} (plans).

In order to support planner synthesis, we have to develop and input a
theory of planning  to KIDS.  As discussed in
\cite{rao-aimag}, the traditional plan synthesis techniques can be
described in terms of a common plan representation, with different
planners corresponding to different ways of refining the partial
plans such as progression, regression and plan-space refinements
(see Section~\ref{sec:ucp}). Consequently, our planning theory will consist 
of a specification of the planning task (in terms of input and output
data types) and one or more refinement
theories. Since we are also interested in domain-customized planners,
we have to provide the necessary domain knowledge to KIDS.

Given these inputs, KIDS semi-automatically synthesizes a program (in
this case, a domain dependent refinement planner) using generic
algorithm design tactics (such as branch and bound, global search).
The resulting planner, like conventional planners, can handle any
planning problem from the domain. 
%If no domain theory was given, the
%resulting planner can handle any planning task from any domain. 
See Section~\ref{sec:synth} for more details.



\subsection{Outcomes}

To understand the efficacy of plan synthesis in CLAY, in this paper,
we concentrate on the synthesis of planners using state-space
refinement theories.\footnote{In future, we plan to extend our
approach to plan-space and task-reduction refinements.}  Empirical
evaluation shows that these synthesized planners can be very
efficient. For example, in the blocks world domain where the goal was
stack inversion, a KIDS synthesized planner solved a 14 blocks problem
in under a minute. In the logistics domain, a problem with 12
packages, 4 planes and 8 places was solved in under a minute.
Similarly, in the Tyre domain \cite{russ-tyre}, the ``fixit'' problem
was solved in under a minute.  To put these performance results in
perspective, we compared KIDS' synthesized planners to a set of
classical planners implemented as the instantiations the UCP planning
system \cite{bip-ewsp95}.  As described later, instantiations of UCP
can emulate a spectrum of classical planners, including the popular
SNLP planner \cite{snlp}, by selecting the appropriate refinement.  In
our experiments, the best of the KIDS' synthesized planners
outperformed the best of the UCP instantiations when given the same
domain-specific information. We hypothesize that this is because KIDS
can profitably fold-in the domain-specific control knowledge (i.e., the
domain theory) into the planning code.
% While these observations suggest KIDS synthesized planners
% as the way to go, there are several cautious comments ...{\bf ADD A CAUTIONARY NOTE HERE.}

\subsection{Organization}

The rest of this paper describes the details of our approach, called
the CLAY architecture for planner synthesis. The paper is organized as
follows: after a brief review of traditional plan synthesis approaches
and software synthesis on KIDS in Section~\ref{sec:kids}, we walk
through the CLAY framework in Section~\ref{sec:synth}. 
%Readers
%unfamiliar with automated soft may
%want to skip Section~\ref{sec:optimiz} that explains program
%optimization details on first reading and come back to it later.
Section~\ref{sec:synth-discuss} presents a discussion on the
nature of planners synthesized by our approach. Section~\ref{sec:expt}
empirically evaluates the synthesized planners and compares them to
classical  planners.  Section~\ref{sec:relwork} discusses related
work. Section~\ref{sec:conc} describes our conclusions and discusses 
the costs and benefits of the synthesis approach. 
        

% bip-test 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Background}
\label{sec:kids}

In this section, we briefly discuss relevant background on software 
synthesis with KIDS, and plan generation that will be needed to follow the 
rest of the paper.

\subsection{Kestrel Interactive Development System}


Before discussing KIDS, we start with some preliminaries on automated
software synthesis. The holy grail of software synthesis is to :
\begin{itemize}
\item Produce highly reliable, adaptable software in a greatly reduced
      development time.
\item Automate detail intensive tasks in software production that are 
      largely non-creative in nature.
\end{itemize}

A program, or program segment, $P$, is correct with respect to an 
initial condition (assertion) $I$ and a final condition (assertion) 
$F$ if and only if whenever $I$ is true prior to the execution of $P$, 
and $P$ terminates, $F$ will be true after the execution of $P$ is 
complete.  Using a formal specification of the task, a 
knowledge-base and an inference system, knowledge-based software 
synthesis proceeds with an iterative specification refinement process 
to specialize the general knowledge of program development (in the form of 
algorithm theories) to solve specific tasks on hand.  The refinements are 
sound in that if the specification is correct, the synthesized program 
(code) will be correct.


KIDS is a program-transformation framework for the development of
programs from formal specifications of a task.  KIDS runs on Sun
workstations and  is built over REFINE, a commercial knowledge-based
programming environment and a high-level language. The REFINE language
supports first-order logic, set-theory, pattern matching and
transformation rules. Refine provides a 
compiler that generates
Common Lisp or C code for programs written in its logical
specification language. 

In the following, we describe the general steps 
involved in synthesizing software on KIDS. Figure~\ref{life-cycle} provides 
an overview of this process. The process is illustrated in more detail
in Section~\ref{sec:synth} in the context of synthesis of customized
planner code.

\begin{figure}
\begin{center}
\epsfxsize=330pt
\epsfbox{life-cycle.ps}
\vspace*{-0.1in}
\end{center}
\caption{Overview of software synthesis process in KIDS}
\label{life-cycle}
\end{figure}

\begin{enumerate}
\item {\em Develop a task theory} to state and reason about the task. 
    The user defines appropriate functions and types that describe the
    task and also gives laws that allow high-level reasoning about
    the defined functions. 
%Kestrel's experience (confirmed by our own)
%    has been that distributive and monotonic laws provide most of
%    the laws needed to support algorithm design and code-optimization
%    (see Section~\ref{sec:clay-distrib-law}).
For planning, many planning
    theories (e.g., progression and regression) 
    were written and relevant laws were specified. We also provided domain 
    theories so that KIDS could perform specialized reasoning on planners 
    it returned as solutions.

\item {\em Select and apply a  design tactic} to select  an algorithmic  
    framework that should be used to implement the task
    specification.  KIDS currently supports a variety of design
    tactics including problem reduction, divide and conquer, global
    search and local search.  For planning, we use the global search
    design tactic because our formalization of classical planning is
    driven by refinement search which can be seen as a special
    case of  global search (see below). 
\item {\em Apply optimizations} to make the generated algorithm efficient. At 
    first, the generated algorithm is well-structured and correct in that it 
    can return all valid solutions, but it can be very inefficient. The 
    algorithm is optimized through specification reduction techniques
    such as simplification, partial evaluation and
    finite-differencing.
\item {\em Compile} the algorithm to produce a program in the base
    language.
\end{enumerate}


The domain theories and specifications are written in REFINE, and KIDS
synthesizes and optimizes the algorithms in the same language. 
To transform specifications into programs as well
as to optimize the programs, KIDS uses a form of deductive reasoning
called {\em ``directed inference''} to reason about the task
specification and  domain theory.



The KIDS system has been used to derive a variety of programs in the
past. Of particular interest to us is the work on deriving efficient
scheduling software \cite{kids-kbse,kids-aips96}, as the success of
these programs provided initial impetus for our own research. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\subsection{Theories of Plan Synthesis}
\label{sec:ucp}


As mentioned earlier, using KIDS to derive 
planning software in CLAY involves figuring out (a) how declarative 
theories for different types of classical planning are specified and 
(b) what algorithmic design templates are best suited to planner
    synthesis.
\cite{rao-aimag} provides an overview of traditional plan synthesis
approaches. As discussed there, plan synthesis approaches come in many 
varieties with very little superficial commonality between them. 
In the last few years, we have developed a unifying framework that
subsumes most of these approaches  \cite{bip-ewsp95,rao-aijdes,rao-aimag}.  
In this framework, plan synthesis is modeled as a process of searching in a 
space of sets of action sequences.  These sets are represented 
compactly as collections of constraints called ``partial plans.'' The 
search process first attempts to extract a result (an action 
sequence capable of solving the problem) from the partial plan, and 
when that fails, ``refines'' (or splits) the partial plan into a set 
of new partial plans (each corresponding to sets of action sequences that 
are subsets of the action sequence set corresponding to the original partial plan), and 
considers the new plans in turn. The 
existing domain independent plan-synthesis algorithms correspond to 
four different ways of refining partial plans.  These are known, 
respectively, as Forward State Space or progression refinement (FSS),
Backward State Space Refinement or regression refinement (BSS),
Plan Space Refinement (PSS) and Task-Reduction Refinement. 
STRIPS \cite{strips} is an example
of a planner using the FSS refinement, TOPI   \cite{barrett-weld} uses
the BSS 
refinement,  SNLP  \cite{snlp} uses the plan-space refinement and
NONLIN \cite{nonlin} uses the  task-reduction refinement. Given this 
background, the declarative theory of plan generation in CLAY corresponds 
to theories of the refinements. The algorithm tactic underlying plan 
generation corresponds to ``refinement search.'' The KIDS system supports 
an algorithm tactic called ``global search''  \cite{smith-gs} which can be 
seen as a generalization of this refinement search.

\section{Developing a Planner from Declarative Specification: The CLAY
  Architecture}
\label{sec:synth}



Figure~\ref{synth-ovw-fig} summarizes how KIDS is used to synthesize a 
domain-specific refinement planner.
The domain knowledge consists of a dynamical model and control knowledge.
The dynamical model is specified in the  form of actions (also called operators) that define 
legal transformations from one state of the world to another. 
%For state space planners, the plan state is the world state. 
Control knowledge 
is a set of domain-specific criteria that helps the planner decide if a plan 
$P_1$ is better than $P_2$ and is intended to make  search 
more efficient. An example of control knowledge is that in a 
logistics domain where some packages have to be moved to their destinations 
using airplanes, planes should not touchdown at a location if they have no 
packages to pickup or deliver. 


\begin{figure}
\begin{center}
\epsfxsize=300pt
\rotatebox{0}{\epsfbox{clay.ps}}
\vspace*{-0.1in}
\end{center}
\caption{The CLAY architecture for writing planning theory. Each level answers
      a question relevant to that level of planning detail. CLAY uses KIDS' 
      feature of theory import to modularize the domain-specific planning 
      theory}
\label{clay-fig}
\end{figure}



%\paragraph{The CLAY Architecture:}

Refinement planning  and  domain control knowledge are brought together in 
the CLAY architecture for writing declarative domain-specific planning 
theory as summarized in Figure~\ref{clay-fig}. To specify a planning task,
a plan representation is selected and the constraints that should be
satisfied by a solution plan are enumerated in the planner specification.
The planner  specification is dependent on the plan representation but is 
independent of the refinement needed for search. A  refinement
strategy  uses the planner 
specification and defines how children nodes are generated from a
given partial plan, what the 
goal test will be, and also explicates any refinement specific search pruning tests. 
The refinement and the specification together form the {\em planning
theory}. To obtain a domain dependent planner, all one needs to do is import
any planning theory and provide some relevant domain-specific  planning
control knowledge that provides a preference structure among partial
plans and competing solutions. 
%*******THIS IS WHERE KAUTZ AND SELMAN STUFF SHOULD COME>..
An interesting special case is when one specifies a {\em generic} domain 
knowledge to the effect that all the plans are equally good in the domain.  In 
such a case, based on the refinement used, one gets a FSS, BSS, PSS or hybrid 
(if multiple refinements are used), general-purpose planner.


Each level in the directed tree in Figure~\ref{clay-fig} represents an 
abstraction of the planning 
task. At the root of the tree (Level 1), only a description of a planning 
task is required without specifying what  refinements strategies should 
be used. At Level 2, the refinements are specified but no assumption
is made about 
the domain. Next, characteristics of the domain are provided at 
Level 3. A progression (FSS) blocks world planner is different from a 
progression  
logistics domain planner only in terms of the domain knowledge. On the other 
hand, a progression  blocks world planner is different from a regression (BSS) 
blocks-world planner only in terms of the refinement used. 


As stated above, to ensure flexibility, the control knowledge should not change when different 
refinements are used and thereby represent substantial flexibility. 
But in practice, since control knowledge helps
prune children nodes produced by a refinement, pruning may be more effective
if the control knowledge is encoded depending on the refinement. There can
also be a middle ground that we have not implemented:
domain control knowledge may be represented in an intermediate form
depending on the partial plan representation.  Each  refinement can
provide, in addition to a termination test, a conversion function to transform
the control knowledge into the refinement specific form. 
%Thus, we can get both  flexibility and efficiency.




\subsection{Representing Domain Operators}
\label{subsec:clay-rep}

We now discuss how the  world state is represented and how the 
domain operators define state transformations.  In classical planning, the world is modeled in terms of a 
set of ``state variables.''  Each state of the world corresponds to a 
particular assignments of values to these variables.  The 
actions are described in terms of the specific variable-value 
combinations that are needed for them to be applicable, and the 
variable-value combinations they will enforce after execution.  Two 
variants of this general modeling approach have become popular in the 
planning community.  The first, called the STRIPS representation 
\cite{strips} represents the world in terms of ground atoms in a first 
order logic.  The action applicability conditions and effects are also 
described in terms of conjunctions of ground atoms.  The second 
variant \cite{back-93} models the world and actions directly in terms 
of multi-valued state variables and their values.
Since STRIPS representation can be seen as a state-variable model 
with boolean state-variables, and since any multi-valued 
state-variable system can be converted into an equivalent boolean 
state-variable system, the two representations are equivalent in 
expressive power. 



\begin{figure}
%\newlength{\lll}
%\setlength{\lll}{\linewidth}
%\addtolength{\lll}{-2\fboxsep}
%\addtolength{\lll}{-2\fboxrule}
%\noindent
%\fbox{%
%\begin{minipage}{\lll}
{\footnotesize
\parbox[t]{2.9in}{
\begin{tabbing}
{\bf ST}\={\bf RIPS representation}\\
\> Action: \= $move(A, B, C)$ \\
\> Prec: \>   $clear(A) \land clear(C) \land \land on(A,B)$\\
\> Post: \>  $on(A,C) \land clear(B) \land \neg clear(C)$\\
\>\>  $\land \neg on(A,B)$\\
\end{tabbing}
} 
\ \ \ 
\parbox[t]{2.9in}{
\begin{tabbing}
{\bf Mu}\={\bf ti-valued state-variable representation} \\
%\> variables = $\langle pos-A, clr-A, pos-B, clr-B, pos-C, clr-C  \rangle$  \\
\> Action: \= $move(A,B,C)$\\
\>  Pre: \> $\langle B, True, 0, False, 0, True \rangle$  \\
\>  Post:\>  $\langle C, True, 0, True,  0, False \rangle$ \\
\\
\>(Whe\=re a state is a 6-tuple\\
\>\>$\langle$ pos-A, clr-A, pos-B, clr-B, pos-C, clr-C $\rangle$,  \\
\>   and the zeroes represent ``don't care'' values)\\
\end{tabbing}
}}
\caption{Different representations of ``Move A from B to C''}
\label{bw-rep}
\end{figure}


We chose the state-variable representation for our implementation
since this can be directly mapped on to the primitive data structures
supported by KIDS. Figure~\ref{bw-rep} shows the action of moving 
block A from block B to the top of block C in STRIPS and state-variable 
representation. A blocks world domain is an environment in which some blocks 
are placed on a table or on top of other blocks and the problems involve
stacking them in some desired configuration.
For the purpose of exposition, we are showing values of 
state variables corresponding to block positions
(e.g., pos-A) by symbols 'B', 'C', etc. and clear conditions (e.g., clr-A) by 
True or False. In practice, we map all the valid values of state variables
to integers.




\subsection{Specification of a Planner}
\label{sec:clay-plan-spec}


KIDS uses a functional 
specification and programming language augmented with set-theoretic data 
types. A specification of the task \cite{smith-gs} is represented by 
a quadruple $ F = \langle D, R, I, O \rangle$  where 
$D$ is the input type satisfying the input condition, $I : D \rightarrow$
{\em boolean}. The output type is $R$  and the output condition, 
$O : D \times R \rightarrow$ {\em boolean}, defines a feasible solution.
If {\em O(x,z)} holds, then $z$ is a feasible solution with respect to 
input $x$. The specification of a program follows the template:
%\newpage
\begin{quote}

    {\bf function} {\em F} (x :{\em D}) : {\em set}({\em R})
    
    {\bf where} {\em I}(x)
  
    {\bf returns}  \{ z $\mid$ {\em O} (x,z) \}
    
    = {\em Body$(x)$}
 
\end{quote}

A specification for program $F$ is consistent if for all possible inputs
satisfying the input condition, the body produces a  feasible solution, 
i.e.,  $\forall(x: D) \exists (z:R) (I(x) \Longrightarrow  O(x, z))$. 



Within this view, a planner takes as inputs an initial state, a goal state 
and an operator list. The operators are assumed to define state transitions 
from valid states to valid states. A specification for the planning 
task is: given the initial state, the goal state and the operator list, 
return a sequence of operators (plan) such that:

\begin{itemize}
\item {\sc termination-test}: The goals must hold in the final state
      resulting from the execution of the plan.
   (We are only considering planning problems in which the goal 
      is to make all state-variables achieve specified values, i.e., goals 
      of achievement).
\item {\sc domain-independent-pruning-test:} The plan passes the  domain independent
      pruning tests. Each planning refinemen
      can specify conditions under which a partial-plan cannot lead to 
      a desirable 
      solution; and any partial plan satisfying such a pruning test 
      can be eliminated from further consideration. For example, the 
      state-loop pruning heuristic in forward 
      state-space refinement says that  if we have a partial plan such that
      the plan-state after executing operator 
      $O_{2}$ is a subset of the state following an earlier operator $O_{1}$, 
      then such a partial-plan can be pruned. 
%interesting that we are not saying that this is just for final plan

\item {\sc domain-dependent-pruning-test:} The plan passes the additional 
      domain-specific pruning tests.
\end{itemize}

\fromrao{Why are we only interested in pruning type control 
information? why not preference rules?}

The last one is the hook through which domain specific control
knowledge is introduced. In the current implementation of CLAY, we use
domain knowledge for rejecting undesirable partial plans.  In
Section~\ref{sec:lim},  we discuss ways in which our implementation
can be extended to support other uses of domain control knowledge.

%****Kautz stuff here?

The  specification of the planning task  above is declarative in that it states 
what constraints must be satisfied in the resulting plan produced by a planner
when given a planning problem. It does 
not suggest any algorithm that should be used to obtain the results. 
Algorithmic decisions will be made in the program development phase of KIDS.


An example of top-level specification of planning task (in REFINE) is shown
in Figure~\ref{plan-spec}. In this specification, the input
condition, $I$, is true, the input data type, $D$ includes INIT, GOAL and OPERS,
the output data type $R$  is PLAN and the output condition $O$
consists of {\sc goodness-test}, {\sc goal-test, no-moves-back}.
% and the check on range of PLAN. 
{\sc no-moves-back} is a 
domain independent pruning tests whereas {\sc goodness-test} is a
domain dependent pruning test.


Delving deeper  into representation detail, we represent a plan as a sequence
of indices in the operator list (i.e., sequence of operator identifiers). For
state-space planning, the {\em state sequence} corresponding to the
partial-plan is produced by function {\sc visited-states} and the goal
test, domain independent pruning tests and domain dependent pruning
tests are done on the state-sequence by functions {\sc goal-test,
no-moves-back} and {\sc goodness-test} respectively.  The
state-variables take integer values. Consequently, our initial and
goal states are a sequence of integers.


\begin{figure}
{\mfootnotesize
\begin{verbatim}
function PLANNER
  (INIT:  seq(integer), GOAL: seq(integer), 
   OPERS: seq(tuple(seq(integer), seq(integer))))
  returns
    (PLAN: seq(integer)
       | range(PLAN) subset {1 .. size(OPERS)}
         & GOODNESS-TEST(VISITED-STATES 
                          (PLAN, INIT, GOAL, OPERS),
                        INIT, GOAL)
         & NO-MOVES-BACK(VISITED-STATES 
                          (PLAN, INIT, GOAL, OPERS),
                        INIT, GOAL)
         & GOAL-TEST(VISITED-STATES 
                      (PLAN, INIT, GOAL, OPERS), 
                    INIT, GOAL))
\end{verbatim}
}
\caption{A declarative specification for planning}
\label{plan-spec}
\end{figure}


In words, the specification  in Figure~\ref{plan-spec}
says that a partial plan is a sequence of 
integral indices (of operators) and so the indices must not be more 
than the size of operator list. Valid plan is one whose corresponding state
sequence (produced by {\sc visited-states}) satisfies the {\sc goal-test, 
{\sc no-moves-back} }
and {\sc goodness-test}\footnote{REFINE code of all the referenced functions 
is shown in Appendix~\ref{sec:code-sample}.}. 

In the context of forward-state space refinement (FSS), 
{\sc {\sc visited-states}} returns the states obtained by the successive 
application of 
the operators in the partial plan to the initial state and the resulting 
states thereafter. {\sc goal-test}  signals that the  goal has been achieved; 
for FSS refinement it involves checking that the last 
state in the state-sequence is the goal state.
The {\sc {\sc no-moves-back}} function tests state looping; forward 
state-space looping checks 
if the state after executing operator $O_{j}$ 
(STATE $S_{j}$) is a subset of the  state following an earlier operator 
$O_{i}$$ (i < j)$ (STATE $S_{i}$), this partial-plan  can be pruned\footnote{Actually, 
we test a slightly more general condition that 
if the state after executing operator $O_{j}$ (STATE $S_{j}$) is {\em weaker} 
than a state following an earlier operator $O_{i}$ (STATE $S_{i}$), 
then this partial-plan can be pruned.
$S_{j}$ is weaker than $S_{i}$ if every  state-variable with assigned 
value in 
state $S_{i}$ has that  same assigned  value in state $S_{j}$.
By specifying  weakness rather than subset as the relationship between states 
to decide domain independent pruning in state space planning, we allow the 
synthesized planner to deal with a partially specified initial state. The 
planner will work correctly as long as all
the state-variables that are required for reasoning are specified in the 
initial state.}.


The function {\sc goodness-test}  checks for possible redundancy in the state 
sequence corresponding to the current partial plan based on domain
characteristics.
%\footnote{To be exact, {\sc goodness-test} 
%calls the function NO-REDUNDANCY for most of its work.}.
Let us explain it in 
the context of the blocks world domain. We can specify any reasonable 
checks for the blocks world as long as they do not make the planner 
lose a desired solution.  Below, we present two {\sc goodness-test}s:

%**Kautz stuff...




\begin{itemize}
\item (Heuristic H1: {\sc Limit useless moves}) 
       If a block moves between states i and (i+1), it must not change
       position between states (i+1) and (i+2). The motivation behind this 
       check is to prevent blocks from being moved around randomly in
       successive moves.
\item (Heuristic H2: {\sc Move via table}) 
      A block can only move from its initial state to the table and from 
      table only to its goal position. This is motivated by the fact 
      that a polynomial time approximate algorithm for solving blocks 
      world planning problems involves putting all blocks on table 
      first, and then constructing each of the goal configuration 
      stacks bottom-up.\footnote{Our pruning test alone doesn't 
      guarantee polynomial algorithm since 
      the order in which the blocks are to be put on the table 
      or later at the goal positions is not specified in the pruning 
      heuristic.} 
\end{itemize}
 


%In a typical classical planner like SNLP \cite{snlp} and UCPOP \cite{ucpop}, 
%it is difficult to specify domain control rules. The control rules can be 
%used to rank the children nodes based on some heuristic or prune unpromising 
%nodes, but such information needs to be explicitly encoded in the 
%planning algorithm. In contrast, we have encoded
%the information declaratively and the planning algorithm is unaffected. 
%{\em The ease with which control knowledge can be specified and incorporated 
%from one domain to another or different heuristics can be experimented in a 
%given domain, is a significant advantage of synthesizing planners on KIDS}.


%%%%%%%%%
\subsection{Implementing the  Specification using Global Search}
\label{sec:code-gs}



As discussed in Section~\ref{sec:kids}, we need to select an algorithm
design tactic to implement the task  specification in KIDS.  One of the design
tactics provided by KIDS is {\em global search}. The basic idea of
global search is to represent and manipulate sets of candidate
solutions. The principal operations are to extract candidate solutions
from a set and to split a set into subsets. Derived operations include
various filters which are used to eliminate sets containing no
feasible or optimal solutions. Global search algorithms work as
follows: starting from an initial set of potential solutions,
that contains all desired solutions to
the given problem instance, the algorithm repeatedly extracts
solutions, splits sets and eliminates sets via filters until a
candidate solution can be drawn from one of the sets. 
Sets of solutions are represented implicitly by
data structures called descriptors, and splitting is done by adding
mutually exclusive and exhaustive sets of constraints to the
descriptors.  The process can be described as a tree search in which a
node represents a set of candidates and an arc represents the split
relationship between a set and its subset. For complete details,
readers are referred to \cite{smith-gs}.


The KIDS' global search paradigm is a general form of the refinement
search model used to unify classical planners in UCP
 \cite{bip-ewsp95}. Specifically, the partial plans correspond to
 descriptors and the refinements correspond to splitting strategies. 
 To use global search to implement the
planner specification, we need to select a
suitable representation for sets of potential solutions (which, in the
refinement view of planning, are essentially the partial plans). The global
search tactic would then set up a search algorithm that can split a 
solution-set and extract solutions that meet the problem
specification. KIDS provides global search tactics for primitive
data-types such as  sequences, sets and maps. If a complex data type is
needed to represent the potential solution set of a task, the
user must implement a global search tactic for it.


Since we are interested in state-space planners initially, we chose to
represent the partial plan as a sequence of operators (actually
sequence of operator indices). This allowed us to use KIDS global
search theory for finite sequences. 

% Based on the problem
%specification, KIDS lists pre-canned global search theories to which
%it can automatically map the current problem instance using deductive
%inference(see  \cite{smith-gs} for details). Since our data type was a 
%sequence, one of the choices KIDS came up was  global search  for sequences
%over a finite domain which we selected because  it is capable of generating 
%all the operator sequences incrementally, and this is the ability needed for 
%state space refinement. 

%%%%%%%%
\subsection{Specifying Distributive and Monotonic laws}
\label{sec:clay-distrib-law}

One aspect of KIDS specification that is slightly unintuitive to new
users is the need to specify distributive and monotonic laws on all
the operations used in the input/output specification (e.g., {\sc
no-moves-back} in the specification of the progression planner shown
in Figure~\ref{plan-spec}).  Distributive laws state how a specific
operation distributes over other operations (e.g., $( A + B ) \times C
\equiv (A \times C) + (B \times C)$), while monotonic laws provide a set of
boundary conditions (e.g., $A + 0 = A$). Such laws should be explicitly
stated for all operations involved in the specification to support
instantiation of design tactics, as well as optimization of generated
code. Specifically, KIDS has a directed-inference engine called
RAINBOW which uses the task specification and the distributed laws
specified by the user to simplify and reformulate the expressions in
the synthesized code.  Deductive inference is the primary means by
which KIDS reasons about the task specification in order to apply
design tactics, and optimize the code, and derive necessary pruning conditions.
%Laws are statements that are always true, for example, axioms and 
%theorems. KIDS needs distributive and monotonic laws for efficient handling 
%of {\em special}  cases like empty sequences. 
Distributive and monotonic laws indirectly provide KIDS with
information on alternative ways of defining predicates. 


A useful heuristic in writing laws is that they should be simple,
normally expressed in terms of the main function and perhaps another
function to handle boundary cases (called cross-functions; see below).
As an example, consider Figure~\ref{plan-spec} where function {\sc
no-moves-back} is a domain independent pruning test used in the
specification of progression planners.  Recall that {\sc
no-moves-back} is called on a state sequence and checks that a later
state is not a subset of (or {\em weaker} than) an earlier
state. Calling {\sc no-moves-back} on a sequence $S$ which is a
concatenation of state sequences $S_{1}$ and $S_{2}$ is equivalent to
calling it on $S_{1}$ and $S_{2}$ and testing that no state in $S_{1}$
is weaker than a state in $S_{2}$. Notice that the first two tests can
be handled by {\sc no-moves-back} itself but the last test needs a new
function. We call this new function a cross-function for {\sc
no-moves-back} ({\sc cross-no-moves-back}). The monotonic laws for
{\sc no-moves-back} include:

\begin{itemize}
\item {\sc no-moves-back} over a singleton state sequence is true.

\item {\sc no-moves-back} over an empty state sequence is false 
     (useful when the selected 
      action is not applicable).
\end{itemize}

Similarly, the distributive laws  for {\sc no-moves-back} include:

\begin{itemize}

\item {\sc no-moves-back} over sequence concatenation is equal to {\sc no-moves-back} on 
      $S_{1}$, {\sc no-moves-back} on $S_{2}$ and {\sc cross-no-moves-back} on 
      $S_{1}$ and $S_{2}$.

\item When a state $A$ is prepended to a state sequence $S$, applying 
{\sc no-moves-back} 
      over such a combined state sequence is equivalent to applying
       {\sc cross-no-moves-back} on the 
      singleton sequence $[A]$ and $S$, and {\sc no-moves-back} on $S$.

\item When a state $A$ is appended to a state sequence $S$, 
      {\sc no-moves-back} over such a combined state sequence is the
      same as {\sc no-moves-back} on $S$ and 
      {\sc cross-no-moves-back}  on $S$ and the singleton sequence $[A]$.
\end{itemize}

All these rules, while reasonably obvious to us, are 
nonetheless very crucial for the effectiveness of KIDS as they help it
in reformulating and optimizing the generated code.  An example 
of their use, as we will see in Section~\ref{opt-cis}, occurs in 
Figure~\ref{cis} where an ``if [condition] - [then] - [else]'' 
statement gets simplified to just the ``[then]'' part because all the 
conditions in the ``[condition]'' can be proved to be true in the 
context of the input specification, given the distributive laws.

Using the task  specification, the selected design tactic -- global search, and
distributive laws, KIDS produces a correct but naive code, as shown
in Figure~\ref{first-code-1}.
% and ~\ref{first-code-2}.
The code is naive because the same checks (for example  
{\sc cross-no-moves-back} in Figure~\ref{first-code-1}) are computed
repeatedly even if they are true from their context. We discuss 
some methods to optimize the code in the next section.


%%%%%%%%%
\subsection{Program Optimization}
\label{sec:optimiz}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% All optimiz figures here %%%%%%%%%%%

%%% First progression blocks
\begin{figure}
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER
 (INIT: seq(integer), GOAL: seq(integer),
  OPERS: seq(tuple(seq(integer), seq(integer))))
 returns
  (PLAN: seq(integer)
  | range(PLAN) subset {1 .. size(OPERS)}
    & GOODNESS-TEST
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS),
       INIT, GOAL)
    & NO-MOVES-BACK
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
       INIT, GOAL)
    & GOAL-TEST
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
       INIT, GOAL))
 = if NO-MOVES-BACK
       (VISITED-STATES([], INIT, GOAL, OPERS), 
       INIT, GOAL)
    & GOODNESS-TEST
       (VISITED-STATES([], INIT, GOAL, OPERS), 
       INIT, GOAL)
   then PLANNER-AUX(INIT, GOAL, OPERS, [])
   else undefined
\end{verbatim}
}
\end{minipage}
\ \ \ 
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER-AUX
 (INIT: seq(integer), GOAL: seq(integer),
  OPERS: seq(tuple(seq(integer), seq(integer))), 
  V: seq(integer)
  | range(V) subset {1 .. size(OPERS)}
    & GOODNESS-TEST
       (VISITED-STATES(V, INIT, GOAL, OPERS), 
              INIT, GOAL)
    & NO-MOVES-BACK
       (VISITED-STATES(V, INIT, GOAL, OPERS), 
              INIT, GOAL))
 : seq(integer)
 = if ex (PLAN: seq(integer))
     (GOAL-TEST
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
          INIT, GOAL)
     & NO-MOVES-BACK
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS),
          INIT, GOAL)
     & GOODNESS-TEST
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
          INIT, GOAL)
     & range(PLAN) subset {1 .. size(OPERS)} 
     & PLAN = V)
   then some (PLAN-1: seq(integer))
     (GOAL-TEST
       (VISITED-STATES(PLAN-1, INIT, GOAL, OPERS), 
          INIT, GOAL)
    & NO-MOVES-BACK
       (VISITED-STATES(PLAN-1, INIT, GOAL, OPERS), 
          INIT, GOAL)
    & GOODNESS-TEST
       (VISITED-STATES(PLAN-1, INIT, GOAL, OPERS),
          INIT, GOAL)
    & range(PLAN-1) subset {1 .. size(OPERS)}
    & PLAN-1 = V)
   else some (PLAN-2: seq(integer))
     ex (NEW-V: seq(integer))
      (PLAN-2 = 
         PLANNER-AUX(INIT, GOAL, OPERS, NEW-V)
      & DEFINED?(PLAN-2)
      & GOODNESS-TEST
         (VISITED-STATES(NEW-V, INIT, GOAL, OPERS),
         INIT, GOAL)
      & NO-MOVES-BACK
         (VISITED-STATES(NEW-V, INIT, GOAL, OPERS), 
         INIT, GOAL)
      & ex (I: integer)
         (NEW-V = append(V, I)
         & I in {1 .. size(OPERS)}))
\end{verbatim}
}
\end{minipage}
\caption{First progression blocks world planner code synthesized by
 KIDS. Notice that the code is inefficient because the same checks
         (for example, {\sc cross-no-moves-back}) are computed
         repeatedly, even if they are true from their context.}
\label{first-code-1}

\end{figure}

%\begin{figure}
%{\footnotesize
%\begin{verbatim}
%function PLANNER
% (INIT: seq(integer), GOAL: seq(integer),
%  OPERS: seq(tuple(seq(integer), seq(integer))))
% returns
%  (PLAN: seq(integer)
%  | range(PLAN) subset {1 .. size(OPERS)}
%    & GOODNESS-TEST
%       (VISITED-STATES(PLAN, INIT, GOAL, OPERS),
%       INIT, GOAL)
%    & NO-MOVES-BACK
%       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
%       INIT, GOAL)
%    & GOAL-TEST
%       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
%       INIT, GOAL))
% = if NO-MOVES-BACK
%       (VISITED-STATES([], INIT, GOAL, OPERS), 
%       INIT, GOAL)
%    & GOODNESS-TEST
%       (VISITED-STATES([], INIT, GOAL, OPERS), 
%       INIT, GOAL)
%   then PLANNER-AUX(INIT, GOAL, OPERS, [])
%   else undefined
%
%\end{verbatim}
%\caption{First progression blocks world planner code synthesized by KIDS
%         (2 of 2)}
%\label{first-code-2}
%}
%\end{figure}


%%%%%%%%%%%%%%%%%%%
%%% context independent simplification 

\begin{figure}
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER
  (INIT: seq(integer), GOAL: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))))
  returns
    (PLAN: seq(integer) |
   range(PLAN) subset {1 .. size(OPERS)}
   and  ...)
 = if NO-MOVES-BACK
          (VISITED-STATES([], INIT, GOAL, OPERS), 
          INIT, GOAL)
      and GOODNESS-TEST
          (VISITED-STATES([], INIT, GOAL, OPERS),
          INIT, GOAL)
   then PLANNER-AUX
         (INIT, GOAL, OPERS, [], [INIT], INIT, 
          size(OPERS))
   else undefined

\end{verbatim}
}
\end{minipage}
%$\,\Rightarrow\,$
\ \ \ 
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER
  (INIT: seq(integer), GOAL: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))))
  returns
    (PLAN: seq(integer) |
   range(PLAN) subset {1 .. size(OPERS)}
   and ...)
 = PLANNER-AUX
         (INIT, GOAL, OPERS, [], [INIT], INIT, 
          size(OPERS))

\end{verbatim}
}
\end{minipage}
\caption{Example of context independent simplification in KIDS. The
  code on the right size is the simplified version of that on the left.}
\label{cis}
\end{figure}


This section explains how the initial planner code, generated by KIDS,
is optimized. Readers not familiar with automated software synthesis 
literature might want to skip this section on first read, and 
revisit it later for more details.

The first code produced by KIDS (shown in Figure~\ref{first-code-1})
is well-structured but very inefficient. There are 
several 
opportunities for optimization  and KIDS provides tools for program 
optimization. The code can be compiled and executed at any stage of 
optimization. Now, we  briefly summarize the program optimizations used 
to achieve efficiency.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% context dependent simplification 

\begin{figure}
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER-AUX 
  (INIT: seq(integer), GOAL: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))),
   V: seq(integer) 
   | range(V) subset {1 .. size(OPERS)}
   and GOODNESS-TEST(VISITED-STATES
                    (V, INIT, GOAL, OPERS),
                   INIT, GOAL)
   and NO-MOVES-BACK(VISITED-STATES
                    (V, INIT, GOAL, OPERS),
                   INIT, GOAL))
 : seq(integer)
 = if GOAL-TEST(
          VISITED-STATES(V, INIT, GOAL, OPERS), 
          INIT, GOAL)
      and NO-MOVES-BACK(VISITED-STATES
                       (V, INIT, GOAL, OPERS),
                     INIT, GOAL)
      and GOODNESS-TEST(VISITED-STATES
                       (V, INIT, GOAL, OPERS),
                      INIT, GOAL)
      and range(V) subset {1 .. size(OPERS)}
    then (if ...) ...
\end{verbatim}
}
\end{minipage}
\ \ \ 
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER-AUX 
  (INIT: seq(integer), GOAL: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))),
   V: seq(integer) 
   | range(V) subset {1 .. size(OPERS)}
   and GOODNESS-TEST(VISITED-STATES
                    (V, INIT, GOAL, OPERS),
                   INIT, GOAL)
   and NO-MOVES-BACK(VISITED-STATES
                    (V, INIT, GOAL, OPERS),
                   INIT, GOAL))
 : seq(integer)
 = if GOAL-TEST(
          VISITED-STATES(V, INIT, GOAL, OPERS), 
          INIT, GOAL)
    then (if ...) ...
\end{verbatim}
}
\end{minipage}
\caption{Example of context dependent simplification in KIDS. The
  code on the right size is the simplified version of that on the left.}
\label{cds}
\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% finite differencing

\begin{figure}
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER-AUX
  (INIT: seq(integer), GOAL: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))),
   V: seq(integer), VS: seq(seq(integer)),
   L-VS: seq(integer) | 
     SEQEQUAL(L-VS, last(VS))
     and range(V) subset {1 .. size(OPERS)}
     and ...)
= if GOAL-TEST(VS, INIT, GOAL) then V
  else some (PLAN-2: seq(integer))
    exists(I: integer)
      (I in {1 .. size(OPERS)}
      and ...
\end{verbatim}
}
\end{minipage}
\ \ \ 
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER-AUX
  (INIT: seq(integer), GOAL: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))),
   V: seq(integer), VS: seq(seq(integer)),
   L-VS: seq(integer), NUM-OPS: integer 
     |
     NUM-OPS = size(OPERS) 
     and ...)
= if GOAL-TEST(VS, INIT, GOAL) then V
  else some (PLAN-2: seq(integer))
    exists(I: integer)
      (I in {1 .. NUM-OPS} 
      and ...
\end{verbatim}
}
\end{minipage}
\caption{Example of finite differencing (on size(OPERS)). 
The
  code on the right size is the result of finite differencing on  that on the left.}
\label{fd}
\end{figure}




%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Derivational steps
\begin{figure}
{\footnotesize
\begin{verbatim}

 0. Focus Initialize PLANNER
 1. Tactic Global Search on PLANNER
 2. Simplify, context-independent-fast: if ## then ## 
       else some (PLAN-2: ##...
 3. Simplify, context-dependent, forward-0, backward-4: 
       ##(...) & ##(....
 4. Simplify, context-dependent, forward-0, backward-4: 
       if ## else und...
 5. FD (general-purpose) VS = 
       VISITED-STATES(V, INIT, GOAL, OPERS)
 6. FD (general-purpose) L-VS = last(VS)
 7. FD (general-purpose) NUM-OPS = size(OPERS)
 8. Abstract NEXT-STATE(L-VS, I, OPERS) into NS in 
       ex (I: integer) (## in ## &...
 9. Simplify, context-independent-fast: 
       if ## & ## then PLANNER-AUX(##, ##,...
10. Refine compile into Lisp: PLANNER-AUX, PLANNER

\end{verbatim}
\caption{Derivation steps to generate a progression planner for blocks world 
         domain.}
\label{transf-step}
}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Final progression planner

\begin{figure}
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER
 (INIT: seq(integer), GOAL: seq(integer),
  OPERS: seq(tuple(seq(integer), seq(integer))))
 returns
  (PLAN: seq(integer)
   | range(PLAN) subset {1 .. size(OPERS)}
    & GOODNESS-TEST
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS),
       INIT, GOAL)
    & NO-MOVES-BACK
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
       INIT, GOAL)
    & GOAL-TEST
       (VISITED-STATES(PLAN, INIT, GOAL, OPERS), 
       INIT, GOAL))
 = PLANNER-AUX
    (INIT, GOAL, OPERS, [], [INIT], 
     size(OPERS), INIT)
\end{verbatim}
}
\end{minipage}
\begin{minipage}[t]{2.9in}
{\mfootnotesize
\begin{verbatim}
function PLANNER-AUX
 (INIT: seq(integer), GOAL: seq(integer),
  OPERS: seq(tuple(seq(integer), seq(integer))),
  V: seq(integer), VS: seq(seq(integer)), 
  NUM-OPS: integer, L-VS: seq(integer)
 | SEQEQUAL(L-VS, last(VS))
   & SEQEQUAL(VS, 
       VISITED-STATES(V, INIT, GOAL, OPERS))
   & NO-MOVES-BACK
       (VISITED-STATES(V, INIT, GOAL, OPERS), 
       INIT, GOAL)
   & GOODNESS-TEST
       (VISITED-STATES(V, INIT, GOAL, OPERS), 
       INIT, GOAL)
   & range(V) subset {1 .. size(OPERS)} 
   & NUM-OPS = size(OPERS))
 : seq(integer)
 = if GOAL-TEST(VS, INIT, GOAL) then V
    else some (PLAN-2: seq(integer))
     ex (NS: seq(integer), I: integer)
       (NS = NEXT-STATE(L-VS, I, OPERS)
       & CROSS-NO-MOVES-BACK(VS, [NS], INIT, GOAL)
       & CROSS-GOODNESS-TEST(VS, [NS], INIT, GOAL) 
       & DEFINED?(PLAN-2)
       & PLAN-2
          = PLANNER-AUX
             (INIT, GOAL, OPERS, append(V, I), 
              append(VS, NS), NUM-OPS, NS)
            & I in {1 .. NUM-OPS})
\end{verbatim}
}
\end{minipage}
\caption{Final progression blocks world planner code synthesized by KIDS}
\label{final-code}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%
\subsubsection{Context Independent Simplifier}
\label{opt-cis}

This  method simplifies an expression independent
of its surrounding context. There are two possibilities for context 
independent simplification:
\begin{itemize}
\item In the first case, a set of equations are treated as left-to-right 
      rewrite rules that are fired exhaustively until none apply. Distributive
      laws are also treated
      as rewrite rules. An example  application of a rewrite rule is:
      \begin{quote} {\em $($if true then $P$ else $Q)$ $\Longrightarrow$  $P$} 
      \end{quote}
\item In the second case, all occurrences of a local variable which is defined
      by an equality is replaced by the equivalent value:
      \begin{quote}  $\{ C(x) \mid x = e \land P(x) \} \Longrightarrow
      \{ C(e) \mid P(e) \}$ \end{quote}
\end{itemize}
Figure~\ref{cis} shows an example of context-independent simplification
where all the conditions of the if-condition are true from their
respective distributive laws. Hence, the if-then-else statement is replaced 
by the then-part.


%%%%%%%%%

\subsubsection{Context Dependent Simplifier}


This method is designed to simplify a given expression 
with respect to its surrounding context and is, thus, more powerful than
context independent simplification. All the predicates that hold in the 
context of the expression are gathered by walking up the abstract syntax 
tree. The expression is then simplified 
with respect to the set of assumptions that hold in the context.
In Figure~\ref{cds}, the function calls for {\sc no-moves-back}, {\sc goodness-test} and
the range test in the ``if'' expression 
are redundant because their results follow from the input 
invariant (conditions listed after ``$\mid$'' and before 
``$:$'') of the PLANNER-AUX function. So they are removed by this 
simplification.

%%%%%%%%%
\subsubsection{Finite Differencing}
\label{sec:fd}


The idea behind finite differencing is to perform computations incrementally 
rather than repeat them from scratch every time. Let us assume that 
inside a function $f(x)$ there is an expression $g(x)$ and that $x$ changes 
in a regular way. In this case, it might be useful to create a new variable, 
equal to $g(x)$, whose value is maintained across iterations and which allows for incremental 
computation of $g(x)$ with the next $x$ value. Finite differencing can be 
decomposed into two more basic 
operations: abstraction and simplification  \cite{smith-gs}


\begin{itemize}
\item First, the function $f$ is abstracted with respect to expression $g(x)$ 
      adding a new parameter $c$ to parameter list of $f$ (now $f(x, c))$ 
      and adding
      $c = g(x)$ as a  new input invariant to $f$. All calls to $f$, whether 
      recursive calls within $f$ or external calls, must now be changed to 
      match the definition of $f$ i.e, 
      $f(x)$ is changed to $f(x, g(x))$. In this process, all occurrences of
      $g(x)$ are replaced by $c$.
\item If distributive laws apply to $g(h(x))$ yielding an expression 
      of the form $h'(g(x))$ and so $h'(c)$, the new value
      of $g(h(x))$ can be computed in terms of the old value of $g(x)$ 
      and this the  real benefit in optimization.
\end{itemize}

Let us illustrate this process with an example. Suppose that some function $f(x)$ has a call for 
function $g(x)$ which returns the square of numbers and that variable 
$x$ varies linearly. Now, suppose that we are given a distributive
law such as $g(x+1) = g(x) + 2*x + 1$. So, after finite-differencing,
$f$ becomes $f(x, c)$ and the $g(x)$ call is replaced by $c + 2*x + 1$.
An additional invariant $c = x*x$ will also be maintained for $f$.
This new expression is computationally much cheaper than the original
expression.

In Figure~\ref{fd}, finite differencing is performed on $size(OPERS)$. The 
argument of function PLANNER is expanded with the inclusion of NUM-OPS, the 
name entered by the user for the value of $size(OPERS)$. Only abstraction is 
done here as the number of operators available to the planner does not 
change during  planning. Note that NUM-OPS represents the number of 
operators in a planning problem and this is a meaningful concept for 
planning. All instances of $size(OPERS)$ are replaced by NUM-OPS. 

\subsubsection{Program Derivation}
\label{sec:prog-deriv}

Figure~\ref{transf-step} shows a  summary of the sequence of derivation 
steps carried out to obtain a blocks world domain-specific forward-state 
space planner. The final version of the planner code is shown in 
Figure~\ref{final-code}.


In step 0, the top-level planner specification is selected and in step
1, selected design tactic is applied. Step 2 involves a context
independent simplification, and steps 3 and 4 involve context
dependent simplifications. Steps 5 through 8 cover finite
differencing. Finally, an efficient planner code is compiled in step
10.


%%%%%%%%%
\section{Discussion on Synthesized Planners}
\label{sec:synth-discuss}

Section~\ref{sec:optimiz} used the synthesis of a progression planner for 
blocks world domain as a case study to walk-through the planner synthesis 
process leading to the final planner given in 
Figure~\ref{final-code}. In our research, we have
also considered regression (backward state space) planners. All 
the  planners we have synthesized to date are summarized in 
Table~\ref{tab:synth-planners}. Although each of these planners
differ in terms of the refinements they use, and the domains to which
they are customized, Figure~\ref{pseudo-final-code} attempts a pseudo-code description 
of a generic template to facilitate discussion of the synthesized
planners as a group.

The main function {\sc planner} takes {\sc initial\_state}, {\sc
goal\_state} and {\sc operator\_set} as inputs and in turn calls the
recursive function {\sc planner\_aux} with all the inputs and an
initial plan. All the pruning tests comprising the {\sc output
condition}s are maintained as ``invariants'' (in that they must hold
not only of the final plan, but also of the every partial plan leading
to the final plan).  The goal test, of course, need only hold for the
final plan, and is thus not maintained as an invariant.  Finite
differencing leads to more {\rm invariant}s.  Inside {\sc
planner\_aux}, if  a partial plan satisfies the goal test,
it is returned. Otherwise, the partial plan is refined, {\rm invariant}s are
incrementally tested in the new partial plan and {\sc planner\_aux} is
called recursively.


First thing we note is that the pseudo-code template describes a
planner for any planning domain employing any state-space refinement.
Even the requirement that the synthesized planner be state-space is
dictated by how the new partial plan ({\sc partial-plan2}) is obtained
(in this case by appending an operator to an operator sequence).  It
can be generalized to support other refinements, by modifying the
operation (in the current case ``append'') that is used to build the
new partial plan from the old one (with corresponding changes to the
distributive laws to account for the new operation).


Second, we observe that all invariants are incrementally evaluated 
(see {\sc planner\_aux}). For example, to see if the the plan in
$i^{th}$ iteration satisfies the {\sc no-moves-back} test, we only
check if the latest state is duplicated by any of the previous
states.  We hypothesize that such incremental
evaluation is the primary reason for the synthesized planner's efficiency.
Once refinement and planning domain knowledge is available, context-dependent
simplification may show that many of the tests made in the separate theories are
in fact redundant. Moreover, incremental evaluations may be cheaper than
complete evaluations of invariants if they are amenable to the operations of 
distribution and monotonicity over the abstract data-types. 


Although  domain independent planners can be given the same control 
knowledge that we give to KIDS during planner synthesis, our
approach is expected to be superior in two ways: 
\begin{enumerate}
\item Our approach separates the 
control knowledge acquisition from the specifics of the planner to some
extent and this makes the acquisition process easier\Ignore{The limitation 
comes in practice when the same control knowledge may need to be specified
in different ways depending on the refinement for pruning efficiency because
control knowledge helps prune children nodes produced by a refinement.}. 
In contrast, controlling 
the search of a domain independent planner requires the user to think 
in terms of specific ``choice-points'' in the planner's search 
strategy. 
\item More importantly, search control in 
domain independent planners typically involves generating unpromising 
partial plans first and then pruning them. In contrast, our approach
improves efficiency by 
``folding in'' 
the control knowledge into the synthesized planner code, through
incremental evaluation of pruning test. 
%Specifically, {\sc goodness-test} (the 
%domain dependent control rules) is defined for the complete state sequence 
%corresponding to a partial plan. 
Specifically, to a first approximation, conventional
domain independent planners will add the {\sc goodness-test} either to control
their search at the choice points  or to post-process the 
generated partial plans. We specify distributive laws on how the {\sc goodness-test}
can be incrementally evaluated (in terms of {\sc cross-goodness-test} and
{\sc goodness-test}) and perform context-dependent analysis on all the pieces
of available knowledge to optimize the
code.
%\footnote{Though we don't show it here, we could have  ``unfolded'' the 
%function calls and done much more optimization.}. 
This is what we mean by 
``folding in'' the control knowledge. 
\end{enumerate}

In Figure~\ref{final-code}, we can see an instance of control knowledge 
being folded into the synthesized progression planner for the blocks world 
domain. Contrast it to the first synthesized
planner shown in Figure~\ref{first-code-1}.
We notice that redundant invocation of various checks (such as {\sc
goodness-test}, {\sc visited-states}, etc) in the earlier planner have been
simplified away.  Moreover, individual checks (such as  {\sc no-moves-back} and
{\sc goodness-test}) have been further simplified based on the
distributive laws (like {\sc cross-no-moves-back} and {\sc
cross-goodness-test}) to consider just the newly added parts of the
partial plan. All these considerations lead to a very small and
efficient final planner.


\begin{figure}
{\footnotesize
\begin{verbatim}

%% The main function PLANNER calls the auxiliary function
function PLANNER (INITIAL_STATE, GOAL_STATE, OPERATOR_SET)
  returns PLAN
  such that OUTPUT CONDITIONS are satisfied
  =
   PLANNER_AUX(INITIAL_STATE, GOAL_STATE, OPERATOR_SET,
     INITIAL_PLAN, ...)
     %% Note: other parameters are added during finite differencing

%% The function PLANNER_AUX is called by PLANNER or by PLANNER_AUX
%% Note: From the set of OUTPUT CONDITIONS given as part of
%%       the problem specification, KIDS selects all but one 
%%       to be maintained as INVARIANTS. Finite differencing 
%%       gives more INVARIANTS.
function PLANNER_AUX(INITIAL_STATE, GOAL_STATE, OPERATOR_SET,
           CURRENT_PLAN, ...)
  such that INVARIANTS are satisfied for the state sequence 
           corresponding to the CURRENT_PLAN
  return type of PLAN
  =
    if state sequence ensures the satisfaction of GOAL_STATE
           when CURRENT_PLAN is executed from the INITIAL_STATE
        return CURRENT_PLAN
    else consider some PARTIAL_PLAN2 = append(CURRENT_PLAN, I)
           where I is index of a valid operator in OPERATOR_SET, and
           a) incremental test of INVARIANTS is true for
              state sequence corresponding to PARTIAL_PLAN2
           b) PARTIAL_PLAN2 = 
                 PLANNER_AUX(INITIAL_STATE, GOAL_STATE, OPERATOR_SET,
                 PARTIAL_PLAN2, ...)
 
\end{verbatim}
\caption{Pseudo-code for the state-space planners synthesized by KIDS}
\label{pseudo-final-code}
}
\end{figure}



\section{Empirical Evaluation of Synthesized Planners}
\label{sec:expt}

Table~\ref{tab:synth-planners} lists several domain dependent
state-space planners that we have synthesized to date. The planners
are characterized by the domain for which they are developed (``BW'' for
blocks world, ``LOG'' for logistics, and ``TYR'' for Tyre World -- all of
which are benchmark domains in AI planning); the type of (state-space)
refinement used (``P'' for progression and ``R'' for regression), and the type
of domain specific control knowledge used (H1 that limits useless
moves, H2 which moves blocks via table, etc.).
We will now report results of an empirical study conducted over
these synthesized planners. The study had two aims:
\begin{itemize}
\item To ascertain whether the synthesized planners are able to
  efficiently exploit domain knowledge.
\item To ascertain if the synthesized planners are better than
  traditional domain independent planners in utilizing domain control
  knowledge. 

\end{itemize}

% In this section, empirical results are reported to highlight both the 
% flexibility of the CLAY approach for synthesizing planners and also
% the different aspects of the synthesized planners such as performance, 
% effectiveness of control knowledge etc. Specifically, we wanted to confirm our
% hypothesis that since the domain control knowledge is folded into the planning
% process in CLAY while it is explicitly invoked at each iteration in 
% classical planners, synthesized planners should outperform 
% classical planners given the same control knowledge. 


Our discussion is organized as follows: In Section~\ref{sec:expt-ovw}, we describe the domains and problems 
we have considered in our  empirical work.
% to show that the  CLAY approach is not planning-task or refinement
% specific. 
In Section~\ref{sec:expt-all-dom}, we evaluate the absolute performance
of the synthesized planners in the various domains. In 
Section~\ref{sec:expt-detail-bw} we compare the performance of
synthesized planners and traditional planners. 

%%%%%%%%%
\subsection{Domains and Problems}
\label{sec:expt-ovw}



\begin{table}
\begin{center}
\begin{tabular}{||l|l|l|l||}   \hline
  Name    &   Customized for        & Refinement   &  Domain Dependent Pruning Test \\
          &  the domain &  & \\
  \hline \hline
  BW-P-H1 &   Blocks World  & Progression (FSS) &  Limit useless moves (H1) \\ 
  BW-P-H2 &   Blocks World  & Progression (FSS) &   Move via table (H2) \\ 

  \hline
  BW-R-H1 &   Blocks World  & Regression (BSS)  &  Limit useless moves (H1) \\ 
  BW-R-H2 &   Blocks World  & Regression  (BSS) &   Move via table (H2) \\ 

  \hline \hline
  LOG-P-L &   Logistics     & Progression (FSS) &   Limit inefficiency    \\

  \hline
  LOG-R-L &   Logistics     & Regression  (BSS) &   Limit inefficiency    \\
  \hline \hline

  TYR-P-M & Tyre World     & Progression (FSS)  &   Multiple control rules  \\
  \hline \hline

  INDEP-P & -none-      & Progression (FSS)  &   True (every state is OK) \\
  INDEP-R & -none-       & Regression  (BSS)  &  True (every state is OK)  \\ 
  \hline 

\end{tabular}
\end{center}
\caption{Table showing the variety of planners synthesized on
  KIDS. The names of the planners follow the format
  $<$domain$>$-$<$refinement$>$-$<$heuristic$>$.}
\label{tab:synth-planners}
\end{table}

\subsubsection{Blocks World Domain}
\label{sec:expt-bw-descp}

A blocks world domain is an environment in which each block is 
placed either on a table or on top of other blocks, and the problems involve 
stacking them in some desired configuration.
Let us focus on two states in particular: A-ON-TOP and N-ON-TOP. When there
are A .. N blocks, A-ON-TOP stands for the state where block A is on top of 
block B, block B is on top of block C, ..., block N-1 is on top of 
block N and block N is on table. Similarly, N-ON-TOP stands for the state in 
which block A is on table, block B is on top of block A, ..., block N is on
top of block N-1. Problems for the reported experiments are one of 
three types:
\begin{description}
\item[1. Stack Inversion:] Invert from A-ON-TOP to N-ON-TOP.
\item[2. Stack building:] Initial state is a collection of random stacks of up 
     to two blocks 
      height in which the last N/2 blocks  are either put on the first N/2 
      blocks or on the table. Goal state is A-ON-TOP or N-ON-TOP.

\item[3. Random blocks world problems:] A subset of random blocks world problems
      generated using Minton's algorithm \cite{minton-thesis}.
      In a problem with N blocks, the goal state can have up to N/2
      goal conditions.
      % Goal and initial state are partially
%      specified but the initial information is sufficient to solve
%      the task.
\end{description}
Some  domain dependent pruning tests  for blocks world were covered in 
Section~\ref{sec:synth}. Specifically, we covered pruning test H1 that
prevents any block from being moved in consecutive steps,  and test H2 which 
requires that all blocks have to be moved via the table. 
%Pruning test H2 is more specific than H1.



\subsubsection{Logistics Domain}
\label{sec:expt-log-descp}

The logistics domain consists of a  several planes and packages
at different places. The goals involve transporting the planes and 
packages to the specified locations.  We considered a type
of logistics domain where there are $k$ planes, $2k$ places and $3k$ packages.
There can be either 2 packages or 1 package and 1 plane at each place. 
The goal is to get all planes and packages to a distinguished place.

The domain dependent pruning test for the logistics transportation domain,
(which we  call  ``{\em Limit Inefficiency}'' heuristic) consists of 
the following pieces of advice:
\begin{enumerate}
\item Planes should not
make consecutive flights without loading or unloading a package
\item Packages should either be at the goal position to begin with, or may
be loaded inside a plane and then flown to their goal position.
\item Once a package reaches its goal position, it should not be moved. 
\end{enumerate}
\subsubsection{Tyre World Domain}
\label{sec:expt-tyrw-descp}


The Tyre world \cite{russ-tyre} is a benchmark domain with complex causal 
structure \cite{graphplan}. 
In the ``fixit'' problem from this domain, a car's tyre is flat and must be 
replaced by a spare flat tyre (which must first be inflated). The original
tyre has to be placed in the boot and all tools must be returned to the boot.
%We used the same domain description as used in Graphplan \cite{graphplan}.
The domain dependent pruning test that we devised enforces the following 
constraints:

\begin{enumerate}
\item If only one state variable changes between one state($S_{1}$) and the next 
      state($S_{2}$), it should not change in the subsequent state($S_{3}$). This is 
      because a state variable describes an attribute about an object in the domain.
      If the attribute has a value in state $S_{2}$ that will be ``overwritten''
      in state $S_{3}$, this might indicate a non-minimal
      plan.\footnote{This is not true in all domains, since in some
        domains, the only
        way a state variable can shift its value from $v_1$ to $v_3$
        is to transition through $v_2$.  The heuristic however does preserve
        completeness in the tyre world.} 
\item Work on the status of boot last.
\item Fixing up a free hub is invalid -- a wheel must be on it first.
\item If we have jacked-up the car that needs a tyre, we can not jack 
     it down without putting the tyre on it.
\item Work on the position of the pump and wrench after all the wheels 
      and the hub are in their final configuration.
\item  Once the wheels are in their goal positions, they should not 
be moved. 
\end{enumerate}

\subsection{Absolute Performance of the Synthesized Planners}
\label{sec:expt-all-dom}

In this section, we discuss the absolute performance of the synthesized
planners in different domains. 
%Attempt has been made 
%to use the legends consistently in all the graphs, but they may be filled 
%or un-filled to increase clarity.}. 
As we shall see,  the synthesized 
planners were able to solve the benchmark problems that are known to be 
hard for the traditional planners. 
A special note is in order regarding the plots that follow. 
In all the plots that follow, if a curve stops 
mid-way in a graph, it means that the
corresponding planner could not solve the given problem or all problems in the
problem class (as applicable) in the stipulated time.

\subsubsection{Planners in Blocks World}
\label{sec:expt-bw-prop}



\begin{figure}
\centerline{
\begin{tabular}{cc}
\subfigure{
\epsfxsize=150pt
%\rotatebox{-90}{
%\epsfbox{./expt/benef-bw.ps}
\epsfbox{./log-plots/log-benef-bw.ps}
%}
}
&
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/benef-logis.ps}
\epsfbox{./log-plots/log-benef-logis.ps}
}
\end{tabular}
}
\vspace*{-.5in}
\caption{Plots show that domain dependent goodness tests lead to 
         efficient planners. The problem domains are blocks world
         (left) and logistics transportation domain (right). Planners
         with domain guidance perform better than those without it.}
\label{benef-ck-plot}
\mvp
\mvp
\end{figure}

In traditional planners, domain specific information helps the planner 
return a result faster and we obtained similar results with the
synthesized planners. As can be seen from the left plot in Figure~\ref{benef-ck-plot}, 
the domain-specific blocks world heuristic H1 (``Limit useless 
moves'') helped the progression planner (BW-P-H1) solve the stack inversion 
problem (invert A-ON-TOP to N-ON-TOP) for 14 blocks
in under a minute, and for 22 blocks in under 30 minutes. 
Without such a heuristic, the progression planner (INDEP-P) could not solve 
even a 5 block stack inversion problem in the same time. 


\subsubsection{Planners in the Logistics  Domain}
\label{sec:expt-log-prop}

In the logistics domain, the progression planner with the 
Limit Inefficiency heuristic (LOG-P-L) could solve
4-plane problems in under a minute and  6-plane problems in 30 minutes
(Figure~\ref{benef-ck-plot}, right).  Without 
such a heuristic, the progression planner (INDEP-P) could not solve even 
the 2 plane problem in the same time. 


\subsubsection{Planners in the Tyre World}
\label{sec:expt-tyrw-prop}


There are 25 operators, 27 state variables and 6 control rules in our manually
encoded Tyre world \cite{russ-tyre} description. The fixit problem was 
solved in under a minute and a 31 step plan was returned. 

%%%%%%%%%%%%%%%%%%%

\subsection{Comparing Traditional and  Synthesized Planners in Blocks World}
\label{sec:expt-detail-bw}

Since our synthesized planners used domain specific control knowledge 
that is not normally used by domain independent planners, our next 
step involved comparing synthesized planners to domain independent 
planners using the same control knowledge.  Our aim is to see if 
the synthesized planners are better able to exploit the domain knowledge 
than the traditional planners.  
We restricted this detailed comparison to 
the blocks world domain. Since there are a variety of traditional 
classical planners each of which have varying tradeoffs (c.f. 
\cite{barrett-weld,rao-aijdes}), we used a ``league tournament'' 
approach in our comparison. Specifically, since most popular classical planners 
correspond to different instantiations of UCP \cite{bip-ewsp95}, we 
first ran them all on our blocks world problem distribution to isolate 
the best traditional planners. Similar study was done to isolate the 
best synthesized planners for our problem distribution. At this point, 
the best synthesized planner is compared to the best traditional 
planner. In this second round of comparison, the winning traditional 
planner is given the same control knowledge as the synthesized 
planner. 

%  Our methodology is to select a planning 
% task suite in the blocks world domain and first experiment with 
% multiple synthesized planners, each differing in the employed 
% refinement or the domain control knowledge or both.  Next, we run the 
% task suite with a set of traditional planners obtained by 
% instantiating UCP and selecting the best traditional planner.  
% Finally, we compare the best of the synthesized planners for different 
% tasks with the selected traditional planner.  From the previous 
% section, we saw that the synthesized planners can be very efficient.  
% In this section, we conduct a detailed comparative analysis of their 
% performance with the traditional planners in the context of blocks 
% world domain.  Our methodology will be to select a planning task suite 
% in the blocks world domain and first experiment with multiple 
% synthesized planners, each differing in the employed refinement or the 
% domain control knowledge or both.  Next, we run the task suite with a 
% set of traditional planners obtained by instantiating UCP and select 
% the best traditional planner.  Finally, we compare the best of the 
% synthesized planners for different tasks with the selected traditional 
% planner.

We have used two of the three blocks world test suites -- the 
random blocks world problems and the stack building problems --
in the comparisons. 
Each problem class is defined in terms of the number of blocks and an average of 
10 runs is shown in each plot. 
The total time allowed for a class of problems was 1000 seconds after
which the planner was deemed to have failed on that problem class.
All planners were run on the same problems from the problem suite.


\subsubsection{Picking the Best Synthesized Planner}
\label{sec:expt-detail-bw-kids}

In this section, we want to empirically determine the
the most effective refinement and
control knowledge (heuristics) for the blocks world problem suites. 
We ran six synthesized planners 
(BW-P-H1, BW-P-H2, INDEP-P, BW-R-H1, BW-R-H2 and INDEP-R) on 
the above test suite. Figure~\ref{synth-planner-comp} shows the 
relative performance. 
We notice that planners with the pruning test H2 perform the best when compared
with other planners using the same refinement.\footnote{We also notice that progression planners perform better in
the left plot and regression planners perform better in the right
plot.  This trend can be explained easily in terms of the way the
refinements operate \cite{rao-aimag}.  In the left figure, based on
the nature of the goals, the branching factor for the regression
planners may become enormous because it cannot detect all the
conflicts among the steps that give conditions at the goal (or at
steps which eventually support the goal condition).  Many more
operators seem to potentially give a condition than is actually the
case. On the other hand, the completely specified initial state helps
the progression planner decide all applicable operators from the
beginning itself. Consequently, progression planner BW-P-H2 is a clear
win.  In the right plot, as the initial and goal states are completely
specified, both regression and progression planners can detect all
conflicts.  As is true in realistic domains, many more operators are
applicable from the initial state than are relevant to achieving the
goal conditions. So, the regression planner BW-R-H2 performs better
than the progression planner BW-P-H2.}

% This was expected because
%H2 is more specific than H1 and H1 is more specific than no control knowledge 
%at all.


\begin{figure}
\centerline{
\begin{tabular}{ccc}
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/all-minton.ps}
\epsfbox{./log-plots/log-all-minton.ps}
}
&
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/all-is-goal.ps}
\epsfbox{./log-plots/log-all-is-goal.ps}
}
\end{tabular}
}
\vspace*{-.5in}
\caption{Performance of the synthesized progression and regression planners with H1,
         H2 or no domain dependent control knowledge. BW-P-H2 perform best 
         in the left plot and BW-R-H2 performs best in the right plot.
         As the points are close together, it is not clear but 
         BW-R-H1 and INDEP-R solve problems of upto 3 blocks in the left plot.}
\label{synth-planner-comp}
\mvp
\mvp
\end{figure}





\subsubsection{Picking the Best Traditional Planner}
\label{sec:expt-detail-bw-ucp}


%%% UCP plots
\begin{figure}
\centerline{
\begin{tabular}{ccc}
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/ucp-min.ps}
\epsfbox{./log-plots/log-ucp-min.ps}
}
&
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/ucp-is-goal.ps}
\epsfbox{./log-plots/log-ucp-is-goal.ps}
}
\end{tabular}
}
\vspace*{-.5in}
\caption{Performance of UCP instantiations with no domain dependent 
         heuristic. In the left and right plots, UCP-FSS solves all
         of the problems in the least time.  
         Based on the results, we see that UCP-FSS is a good strategy for 
         blocks world. Note  from the figure that UCP-BSS
         solves only 3 blocks problems in the given time in all the plots.}
\label{ucp-comp}
\mvp
\mvp
\end{figure}


In this section, we empirically search for the best UCP strategy in the blocks 
world. Figure~\ref{ucp-comp} shows the performance of UCP instantiations with
no domain dependent heuristic information. Instantiations of UCP which do 
only FSS, BSS or PS refinements can emulate classical forward-state space, 
backward-state space or plan-space planners, respectively. We call 
these instantiations UCP-FSS, UCP-BSS and UCP-PS. UCP-LCFR is a hybrid 
strategy which interleaves FSS, BSS and PS refinements depending on the 
lower branching factor \cite{bip-ewsp95}. In both the random blocks
world problems (left) and the stacking building problems (right),
 the left and right plots, UCP-FSS solves all
of the problems in the least time.   Based on the results,
we see that UCP-FSS is a good strategy for the blocks world problem distributions 
we used.\footnote{Note that in the case of synthesized planners,
  a planner based on regression outperformed  one based on progression in the stack building
  problems. In contrast,  UCP-FSS out performs  UCP-BSS for the same problem
  suite. The reason for this had to do with the particular
  implementation of UCP-BSS, which involves a costly unification step.}
 


\subsubsection{Comparing the Best Synthesized Planner  and Best Traditional Planner}
\label{sec:expt-detail-bw-comp}



%%%%%% UCP-KIDS comparison

\begin{figure}
\centerline{
\begin{tabular}{ccc}
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/fss-poly-minton.ps}
\epsfbox{./log-plots/log-fss-poly-2-minton.ps}
}
&
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/fss-poly-is-goal.ps}
\epsfbox{./log-plots/log-fss-poly-2-is-goal.ps}
}
\end{tabular}
}
\vspace*{-.5in}
\caption{How the best UCP strategy for blocks world, namely UCP-FSS,
         performs against the best of KIDS' synthesized planners:
         In the left plot, UCP-FSS  does better than INDEP-P i.e., without 
         any heuristic information. But when H2 heuristic is given to both  
         the planners, BW-P-H2 is a winner. In the right plot, 
         BW-R-H2  outperforms UCP-FSS with H2.}
\label{ucp-kids-comp}
\mvp
\mvp
\end{figure}


Finally, we pit the best UCP strategy for the blocks world, namely
UCP-FSS, against the best of KIDS' synthesized planners. We chose
BW-P-H2 for the random blocks world problem suite and BW-R-H2 for the
stack building problem suite. Comparison is done when all planners are
either given the same heuristic information (H2) or no domain
dependent guidance. Figure~\ref{ucp-kids-comp} plots the results.  In
the left plot, BW-P-H2 is a clear winner when both planners are given
the domain specific heuristic H2.  In the right plot, BW-R-H2
outperforms UCP-FSS with H2. So, we see that {\em given the same
heuristic information, the best of the planners synthesized by KIDS
can outperform the best instantiation of UCP for the blocks world}.




%In the left plot, although UCP-FSS  does better than INDEP-P (the 
%planner without any domain-specific
%information),
%

\begin{figure}
\centerline{
\begin{tabular}{ccc}
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/fss-poly-minton.ps}
\epsfbox{./log-plots/log-fss-poly-minton.ps}
}
&
\subfigure{
\epsfxsize=150pt
%\epsfbox{./expt/part-3/fss-poly-is-goal.ps}
\epsfbox{./log-plots/log-fss-poly-is-goal.ps}
}
\end{tabular}
}
\vspace*{-.5in}
\caption{Effect of control knowledge on UCP planners vs. KIDS
  synthesized planners.}
\label{ucp-kids-indep-comp}
\mvp
\mvp
\end{figure}

It is interesting to note that while all synthesized planners improve
drastically with domain specific knowledge, domain independent
planners do not always improve in the same way. We illustrate this in
Figure~\ref{ucp-kids-indep-comp}, where we compare UCP instantiations
and the synthesized planers with and without control heuristics. While
the synthesized planners always improve with the addition of control
knowledge, the same is not true of the UCP
instantiations. Specifically, in the right plot, we see that
UCP-FSS-H2, which uses control knowledge H2 does worse than
UCP-FSS-DOM-INDEP, which does not use any control knowledge! We
speculate that this is because UCP-FSS explicitly calls a function to
do domain-specific reasoning in each recursive invocation while the
synthesized planners have domain control knowledge folded into the
planner code (see Section~\ref{sec:synth-discuss}).

% Though it is clear that KIDS' synthesized  planners are competitive, their 
% performance depends heavily on the domain dependent heuristics that are 
% supplied. Specifically, all KIDS' planners improve drastically in
% Figure~\ref{ucp-kids-comp} after H2 is given. Performance of UCP-FSS,
% on the other hand, suffers in the right plot after the H2 heuristic was used 
% to guide the planner. This may be because UCP-FSS explicitly calls a function
% to do domain-specific reasoning in each recursive invocation while KIDS 
% planners have domain control knowledge folded into the planner code.(See
% Section~\ref{sec:synth-discuss} for discussion on folding).
% Added with the fact that code optimization is done on REFINE code, something 
% which is not possible on the manually written LISP code of UCP, KIDS
% synthesized planners use domain control knowledge very effectively.




\subsection{Summary of Results}
\label{sec:empir-result-summary}

In summary, we have demonstrated that:

\begin{itemize}

\item The CLAY approach to writing domain-specific planning theory is
      flexible.
It supports mix-and-match of refinements and control knowledge 
in generating a variety of customized planners. 
 As examples, we presented planners for blocks world, 
      logistics domain and Tyre domain, using forward and backward
      state space refinements and different types of domain-specific control
      knowledge. 

\item The synthesized planners can exploit domain dependent control
knowledge to improve performance. We showed that, in fact, they are better able to
exploit domain knowledge than the traditional planners can.



\end{itemize}



% In reality, code that user writes (specifications)
% is many times longer than the code that KIDS generates,
% as a result a user feels that he does the job that
% KIDS should and KIDS does the job he should. The code
% in KIDS is far inferior than algorithmic code that 
% a user would write, KIDS just puts the declarative 
% specifications and some deduced conclusions together.
% Also the additional need is - providing to KIDS, the
% space of all possible solutions. When the actions have
% higher arity (this is just one example), the space
% is going to explode. 
% 
% If you have to give constraints and space of all solutions,
% a user will obviously feel that KIDS is not a big help.
% 
% Also, one has to iteratively tighten, relax, modify constraint set
% till KIDS provides the desired code.

\section{Related Work}
\label{sec:relwork}

The research reported here straddles the two fields of automated 
software synthesis and AI planning. 
Although our research is the first to address the issue of planner 
synthesis, synthesis of other types of search engines has been 
addressed by Smith and his co-workers. Of particular interest to us is 
the work they did in developing automated scheduling software for 
transportation logistics problems using KIDS system 
 \cite{kids-kbse,kids-aips96}. The scheduling systems they have 
generated have been shown to significantly outperform general-purpose 
schedulers working on the same problem. Their results provided the 
initial impetus for our research. Although their original work used 
a design tactic based on global search to model scheduling, they have
also since then developed design tactics based on other local search 
regimes. Another interesting issue brought up by their work is the 
importance of ``constraint propagation'' techniques in deriving 
efficient code. This has made us explore the role (or lack thereof) 
of constraint propagation in planning. Kambhampati and Yang \citeyear{rao-kr96}
describe ways in which the refinement planning framework can be extended 
to exploit constraint satisfaction techniques. In future, we hope to 
be able to synthesize planners using this more general theory of 
refinement planning. 


Although there has not been much work on automated planner synthesis, 
a notable exception is the work of Gomes \citeyear{gomes-xx95}. 
Gomes had synthesized a state-space problem solver for the  
``missionaries and cannibals'' problem on  KIDS, and has shown that 
the synthesized code 
outperforms general purpose problem solvers in that domain. 
Our framework can be seen as a generalization of the work done by 
Gomes.  In particular, we separate planning theories from the 
dynamics  and the control knowledge, which in principle supports generation 
of planning code based on a variety of refinements. We have 
demonstrated this by deriving both progression and regression 
planners for three different domains (blocks world, logistics and tyre
world) and with two different bodies of control knowledge in each case. 
Methodologically, our work adds to Gomes' results in that we have 
shown that given the same control knowledge, planners generated by 
KIDS can outperform traditional planners using the control knowledge at 
their choice points. This makes for a fairer comparison between 
synthesized and general-purpose planners. 


In some existing planners such as 
UCPOP \cite{ucpop} and
PRODIGY \cite{fink-vel}, customization is supported by allowing the
user to specify search control rules that are checked at every choice
point during search. Such control rules can be 
used to rank the search nodes based on some heuristic, or prune unpromising 
nodes. The main difference between these approaches and the synthesis
approach described here is that ours supports a higher degree of
integration of domain knowledge into the planner by folding it  into the synthesized
code for the planner. Planners using search control rules cannot do
context dependent analysis or incremental application of control
knowledge. In contrast, in our approach, the control information is
encoded  declaratively and the planning 
algorithm can be optimized based on {\em all} the knowledge that is 
available, including the control knowledge.

Our work on utilizing explicit control knowledge in addition to 
domain dynamics in deriving planning code has some parallels with the 
recent work by Bacchus and Kabanza  \citeyear{bacc-kab95}.
They concentrate on providing a rich language in which control knowledge 
can be specified for a progression planner. They describe a 
language based on  temporal logic to specify 
domain control rules. Rather than using this knowledge to prune bad 
plans after they are generated, Bacchus and Kabanza explore ways of 
incrementally tracking the level of satisfaction of the control 
axioms as the planning progresses. Our approach facilitates the same, 
in a refinement independent setting, 
by ``folding in'' the control knowledge into the developed planning 
code, with the help of KIDS framework. 

% These Examples of such an approach
%include 


There is some work in constraint satisfaction community that is
directed towards producing specialized (customized) programs that is
relevant to the research described here. 
COASTOOL \cite{yoshi} and ALICE systems \cite{alice} take 
declarative description of CSPs and compile specialized algorithms for solving
them, and MULTI-TAC \cite{multi-tac} supports automatic configuration
of constraint satisfaction programs. The MULTI-TAC system, in
particular, provides an interesting contrast to our approach.
MULTI-TAC starts with an algorithm schema, a list of high level
heuristic rules for various decision points
(e.g., ``most-constrained-variable-first'' heuristic for variable
selection and ``least-constraining-value-first'' for value selection
in CSP search), and a list of flags indicating whether certain
procedures (e.g., forward checking in CSP) will or will not be
used. MULTI-TAC uses the domain specification to specialize the
high-level heuristics given to it. For example, in the context
of a minimum maximal matching problem in graph theory, a
most-constrained-variable-first heuristic may become ``choose the edge
with the most neighbors that have been assigned values'' .  A configuration
is a particular subset of specialized heuristics to be used, and a
particular assignment of flags.  MULTI-TAC first searches through a
space of ``configurations'' to see which configuration best fits a
given problem population. Once the best configuration is found, it is
then automatically compiled into efficient code by using specification
refinement techniques similar to those that we described in
Section~\ref{sec:optimiz}.

MULTI-TAC thus presents an interesting middle-ground between search
control rule specification approach used in UCPOP and PRODIGY
planners, and the full integration of domain-knowledge into the
synthesized code, promised by the CLAY approach. In contrast to the UCPOP
and PRODIGY search control rule approach, the MULTI-TAC compilation phase
can support folding-in of search control rules into the compiled
code.  In contrast to CLAY which advocates semi-automatic
synthesis of  a piece of software by manually guided optimization
(through the help of user specified distributive and monotonicity
laws), MULTI-TAC supports fully automating the customization of a
configurable template. For the CLAY approach to be effective, we need to
provide a declarative specification of the task and the domain
control knowledge, as well as high level algorithm tactics. KIDS deals
with instantiating the tactics into the specific problem, but the
simplification needs to be guided by careful specification of
distributive/monotonicity laws. In contrast, MULTI-TAC's configuration
approach needs an algorithm template that is already semi-customized
to the specific task, with built-in hooks for using heuristics. The
heuristics themselves are specified in the form of meta-heuristic
knowledge.

In MULTI-TAC, domain knowledge is used only in specializing the
meta-heuristics.  In theory, the CLAY approach may support a 
deeper integration of the domain knowledge into the synthesized code;
but at the expense of a significant amount of user intervention. An
interesting application of the MULTI-TAC approach in the context of
planning might involve starting with a UCP planning shell (which can
be configured to emulate many varieties of planners), a list of
high-level heuristics for guiding the decision points in the UCP shell
(e.g., refinement selection, flaw selection etc), and searching among
the configurations to pick a planner for the given problem
distribution.



\section{Conclusion}
\label{sec:conc}

In this research, we investigated the feasibility of using automated
software synthesis tools to synthesize customized domain-specific
planners. We described the  CLAY architecture for flexibly synthesizing
efficient domain dependent classical planners from a declarative theory
of planning and domain theory using a software synthesis system
(KIDS). Using this framework, any classical planner can be synthesized
enriched with domain control knowledge. As a proof of concept, forward
state-space and backward state-space planners were synthesized for
the blocks-world, the logistics and the
tyre world domains.
% Though our method can  scale up to complex domains like Tyre World,
% we felt a need for tools  to conveniently specify domain control knowledge. 
We have shown that the synthesized planners can outperform general purpose 
planners when both are using the same amount of domain-specific 
control knowledge and argueed  that this is due to their ability to fold-in 
domain specific control knowledge into the planner code.  In contrast, 
the domain independent planners test the control knowledge for each plan 
being refined, and thus suffer a significant application overhead. 

\subsection{Features and Limitations}
\label{sec:lim}


Our synthesis approach provides several interesting contrasts to 
main-stream AI planning work. To begin with, 
most AI planning work attempts to improve the efficiency of planning 
by concentrating on the way plans are generated. Our work differs 
radically in that we concentrate on how ``efficient planners'' are 
synthesized. 
The use of software synthesis techniques  lends modularity to the
planner synthesis activity.  The planning theory is specified
declaratively rather than in the form of an implemented program. This
supports changes and extensions to the planning theory.  While a  planning theory
is described independent of domains,  control knowledge and dynamical
knowledge of the domain can be specified once for each domain.  By
selecting different combinations of planning theory and  control
knowledge,
we can synthesize a variety of domain-customized refinement planners.


Despite these promises, our approach does entail several overheads. 
Some of these overheads are related to the current state of the art in
automated software synthesis while others are related to our current
implementation of CLAY architecture. In what follows, we try to
tease these apart.


The holy grail of automated software synthesis approaches is to free
the users from low-level coding, and allow them to concentrate on
declarative specification. While the KIDS system comes closest to this
promise, it is still far from perfect.  To start with, the user must
be reasonably familiar with the software synthesis process in order to
do anything substantial with KIDS. We had to go through a steep
learning curve before we could understand how to structure our
theories to make good use of the optimizations provided by KIDS.  Writing
the monotonic and distributive laws for operations such that they can
help KIDS do effective code simplification is still somewhat of an
art. Many times, we had to go back and rewrite the domain knowledge
after KIDS was unsuccessful in using the knowledge provided to it.
Advances in software synthesis technology may provide support for
automatic translation for high level control knowledge into forms
suitable for consumption by KIDS; but such support is not available
right now.

The current cost-benefit ratios are such that we would not recommend using
CLAY/KIDS approach for customizing a planner if one is interested in
customizing a single planner for a single domain.  The REFINE code the
user writes to specify the synthesis task is typically larger than any one
single synthesized planner generated by KIDS.  Thus, manually customizing
the planner for the domain may still be more appropriate. However, the
synthesized approaches may be competitive if we are interested in
being able to customize a variety of planners to a variety of domains.

In addition to the overheads entailed by KIDS, our specific
implementation of planning theories, domain knowledge, etc. also lead
to some inefficiencies. These latter can be eliminated by a better design
of the CLAY architecture.  For example, to make our work simple, we
decided to go with one of the pre-existing canned design tactics
provided by KIDS, and chose  the global search theory over finite sequences
as the candidate tactic. Because of this choice, we found
state-variable representation of domains to be more suitable from an 
implementation point of view. Although getting state-variable
representations of actions is not very hard (we wrote a couple of
utility routines for converting actions in STRIPS representation into
state-variable representation), specifying control knowledge in terms
of this representation turned out to be less than natural, especially in
larger domains like Russel's tyre world. 

Our choice of in-built design tactics also limited the types of domain
knowledge we could specify. Most of the control knowledge had to be in
the form of node-rejection rules. General global search also allows
node-preference knowledge as well as knowledge regarding effective
ways of shrinking the set of potential solutions, without splitting the
set (by eliminating non-solutions). 

We could eliminate the awkwardness of state-variable representations
as well as exploit more types of domain knowledge by designing global
search tactics specially suited to planning-specific
data structures. Although eventually the KIDS system may support a larger
variety of design tactics, customizing design tactics to task
classes is very much in line with the current practice in automated
software synthesis \cite{gomes-power}. 

%Another open issue is whether or not 
%it is easy for humans to give declarative information to KIDS in the form
%it likes. But one might expect that advance in
%Knowledge-based Software Engineering (KBSE) may provide better support
%to users to give such information.
%For example, in a complex domain like the Tyre World domain,
%we realized that tool support is needed to specify declarative
%knowledge in a form KIDS understands. With large number of state 
%variable in such domains, manually encoding the control knowledge
%is painstaking, time-consuming and error-prone.

\subsection{Future Directions}
The work presented here can be seen as the beginning of a fairly open-ended
research program that complements, rather than competes with, the research 
into efficient planning algorithms. 
Ideally, we would like to support the synthesis of customized planners 
based on the full gamut of planning technologies including partial 
order and  task-reduction planning. These latter are already subsumed 
by the refinement planning framework developed in  \cite{rao-ucp-tr} and 
supporting their synthesis is mainly a matter of supporting a more flexible 
partial plan representation in KIDS (representing plans
as sequences over actions has sufficed until now, as we were only
addressing the synthesis of state-space planners). We are currently in 
the process of doing this \cite{ase-kids}.

More generally,  any time we get insights into the internal workings of a 
family of planning algorithms, we would like to translate those insights into 
declarative specifications for KIDS and support synthesis of  more efficient 
customized domain code. An example of this is the recent 
research on plan synthesis
approaches based on constraint satisfaction. In fact, 
domain independent planners such 
as Graphplan \cite{graphplan} can solve our test suites in equal or 
better time compared to the synthesized planners. We have 
taken some preliminary steps towards integrating these approaches into the 
refinement planning framework by using the notion of disjunctive 
refinement planning \cite<see>{rao-kr96,rao-aimag,rao-graphplan,rao-ijcai-challenge}. 
In future, 
as this work matures, we intend to  explore synthesis of 
planners using the theories of disjunctive plan refinement. 

\Ignore{Currently, our partial plan representation only allows for planners 
using state space refinements.  By using a set of actions instead of a 
sequence of actions as the representation for a partial plan, the 
current work can be extended to support plan-space refinement.  More 
planners from diverse domains need to be synthesized to demonstrate 
the generality of our approach.  Issues which may be revisited include 
how the actions be represented, how can the specification of a 
planning problem be improved and formulating guidelines on how good 
domain-specific heuristics be obtained.}


%We chose state-variable representation for actions because it seemed more 
%natural than STRIPS representation. 
%All planners in practice
%test if they have been working on the current problem for than the stipulated
%time and if so, they fail on the given problem. But we avoided such
%issues because it is not a fundamental criterion for a planner.
%We specified  domain-specific heuristics which made intuitive sense but
%there could be ways better heuristics are discovered.



\subsection*{Acknowledgements}

We are grateful to Doug Smith for his help with KIDS and numerous
discussions on tactics, global search and distributive laws. We would
also like to thank Carla Gomes for discussing her work with us and
making useful suggestions on how to write theories; and Nort Fowler
for his encouragement on this line of research. Thanks are also due to
Steve Minton and the anonymous referees of {\em JAIR} for their many
helpful comments toward improving the presentation of this paper. This research is
supported by a DARPA Planning Initiative Phase 3 grant
F30602-95-C-0247 (through a subcontract from Kestrel to Arizona State
University). 

%\cleardoublepage


\appendix
\section{Sample Code Referred in the Text}
\label{sec:code-sample}


{\mfootnotesize
\begin{verbatim}

%% Get state sequence from partial plan 
function VISITED-STATES
  (PLAN: seq(integer), IS: seq(integer), 
   GS: seq(integer),
   OPERS: seq(tuple(seq(integer), seq(integer))))
  : seq(seq(integer))
  = if empty(PLAN) then [IS]
     else
     if ~empty(NEXT-STATE(IS, first(PLAN), OPERS)) then
       prepend(VISITED-STATES(rest(PLAN), 
                NEXT-STATE(IS, first(PLAN), OPERS),
                GS, OPERS), IS)

%% Used by VISITED-STATES to get next state
%% after applying an operator
function NEXT-STATE
  (STATE: seq(integer), OPER: integer,
   OPERATORS: seq(tuple(seq(integer), seq(integer))))
  : seq(integer)
  = if fa (I: integer)(I in [1 .. size(STATE)]
         => OPERATORS(OPER).1(I) = 0 or
            OPERATORS(OPER).1(I) = STATE(I)) then
      image(lambda(x) 
             if OPERATORS(OPER).2(x) = 0 then STATE(x)
               else OPERATORS(OPER).2(x),
             [1 .. size(STATE)])


%% Domain independent pruning test for FSS refinement
function NO-MOVES-BACK (VIS-STATES: seq(seq(integer)), 
  IS: seq(integer), GS: seq(integer))
  : boolean
  = fa (I: integer, J: integer)
      (I in [1 .. size(VIS-STATES)] 
         & J in [1 .. size(VIS-STATES)]
         & I < J
         => not (fa (INDEX: integer)
                  (INDEX in [1 .. size(first(VIS-STATES))] 
                    => VIS-STATES(J)(INDEX) = 
                                  VIS-STATES(I)(INDEX)
                    or VIS-STATES(I)(INDEX) = 0)))

function CROSS-NO-MOVES-BACK
  (R: seq(seq(integer)), S: seq(seq(integer)), IS: seq(integer), 
  GS: seq(integer)): boolean
  = fa (I: integer, J: integer)
      (I in [1 .. size(R)] & J in [1 .. size(S)]
         =>  not (fa (INDEX: integer)
                  (INDEX in [1 .. size(first(R))]
                   => S(J)(INDEX) = R(I)(INDEX)
                      or R(I)(INDEX) = 0)))

%% Domain independent goal test for FSS refinement
function GOAL-TEST
  (VIS-STATES: seq(seq(integer)), INIT: seq(integer), 
   GOAL: seq(integer)): boolean
  = fa (I: integer)
     (I in [1 .. size(GOAL)]
        => GOAL(I) = 0 or
           last(VIS-STATES)(I) = GOAL(I))


%% Domain dependent pruning test
%% Heuristic H1: Limit useless move for blocks world
function NO-REDUNDANCY (S: seq(seq(integer)))
: boolean
= fa (I: integer, INDEX: integer)
   (I in [1 .. size(S) - 2] 
       & INDEX in [1 .. size(first(S))]
       & INDEX mod 2 = 1 
       and S(I)(INDEX) ~= S(I + 1)(INDEX) 
       => S(I + 2)(INDEX) = S(I + 1)(INDEX))

%% Domain dependent pruning test
%% Heuristic H2: Move via table for blocks world
function NO-REDUNDANCY (S: seq(seq(integer)), 
                           INIT: seq(integer),
                           GOAL: seq(integer))
  : boolean
  = fa (I: integer, INDEX: integer)
     (I in [1 .. size(S) - 1] 
      & INDEX in [1 .. size(first(S))]
      & INDEX mod 2 = 1 
      & S(I)(INDEX) ~= S(I + 1)(INDEX) 
     =>((%% position in state I is same as 
         %% initial state
         S(I)(INDEX) = INIT(INDEX) 
         and 
         S(I + 1)(INDEX) = 
          %% position in state I+1 is on table
          (1 + real-to-nearest-integer
                    (size(first(S)) / 2)))
      or
        (S(I)(INDEX) =
          %% position in state I is on table 
          (1 + real-to-nearest-integer
                    (size(first(S))/2))
         and
         %% position in state I+1 is same as 
         %% goal state
         S(I + 1)(INDEX) = GOAL(INDEX))))



\end{verbatim}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% References

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Bacchus \BBA\ Kabanza}{Bacchus \BBA\
  Kabanza}{1995}]{bacc-kab95}
Bacchus, F.\BBACOMMA\  \BBA\ Kabanza, F. \BBOP1995\BBCP.
\newblock \BBOQ Using temporal logic to control search in a forward chaining
  planner\BBCQ\
\newblock {\Bem New Directions in AI Planning: EWSP 95, IOS Press, 141-153}.

\bibitem[\protect\BCAY{Backstrom \BBA\ Nebel}{Backstrom \BBA\
  Nebel}{1993}]{back-93}
Backstrom, C.\BBACOMMA\  \BBA\ Nebel, B. \BBOP1993\BBCP.
\newblock \BBOQ Complexity results in {\sc sas}+ planning\BBCQ\
\newblock {\Bem Research Report, Dept Comp.and Info Sc., Linkoping Univ.,
  Sweden}.

\bibitem[\protect\BCAY{Barrett \BBA\ Weld}{Barrett \BBA\
  Weld}{1994}]{barrett-weld}
Barrett, A.\BBACOMMA\  \BBA\ Weld, D. \BBOP1994\BBCP.
\newblock \BBOQ Partial order planning: Evaluating possible efficiency
  gains\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 67\/}(1).

\bibitem[\protect\BCAY{Blum \BBA\ Furst}{Blum \BBA\ Furst}{1995}]{graphplan}
Blum, A.\BBACOMMA\  \BBA\ Furst, M. \BBOP1995\BBCP.
\newblock \BBOQ Fast planning through planning graph analysis\BBCQ\
\newblock {\Bem Proc IJCAI-95}, 1636--1642.

\bibitem[\protect\BCAY{Burstein \BBA\ Smith}{Burstein \BBA\
  Smith}{1996}]{kids-aips96}
Burstein, M.\BBACOMMA\  \BBA\ Smith, D. \BBOP1996\BBCP.
\newblock \BBOQ {\sc ITAS}: A portable, interactive transportation scheduling
  tool using a search engine generated from formal specifications\BBCQ\
\newblock In {\Bem Proceedings of 3rd AI Planning Systems Conference}, \BPGS\
  35--44.

\bibitem[\protect\BCAY{Fikes \BBA\ Nilsson}{Fikes \BBA\ Nilsson}{1990}]{strips}
Fikes, R.\BBACOMMA\  \BBA\ Nilsson, N. \BBOP1990\BBCP.
\newblock \BBOQ {\sc STRIPS}: A new approach to the application of theorem
  proving to problem solving\BBCQ\
\newblock {\Bem Readings in Planning}.
\newblock Morgan Kaufmann Publ., San Mateo, CA.

\bibitem[\protect\BCAY{Fink \BBA\ Veloso}{Fink \BBA\ Veloso}{1994}]{fink-vel}
Fink, E.\BBACOMMA\  \BBA\ Veloso, M. \BBOP1994\BBCP.
\newblock \BBOQ Formalizing the prodigy planning algorithm\BBCQ\
\newblock {\Bem CMU CS Tech Report CMU-CS-94-123}.

\bibitem[\protect\BCAY{Gomes, Smith, \BBA\ Westfold}{Gomes
  et~al.}{1996}]{gomes-power}
Gomes, C., Smith, D., \BBA\ Westfold, S. \BBOP1996\BBCP.
\newblock \BBOQ Synthesis of schedulers for planned shutdowns of power
  plants\BBCQ\
\newblock {\Bem Proc. of 11th Knowledge-Based Software Engg. Conf., IEEE
  Computer Society Press, Los Alamitos,CA}, 12--20.

\bibitem[\protect\BCAY{Gomes}{Gomes}{1995}]{gomes-xx95}
Gomes, C.~P. \BBOP1995\BBCP.
\newblock \BBOQ Planning in {\sc kids}\BBCQ\
\newblock Technical report\ RL-TR-95-205, Rome Laboratory.

\bibitem[\protect\BCAY{Kambhamapti}{Kambhamapti}{1995}]{rao-htn-sigart}
Kambhamapti, S. \BBOP1995\BBCP.
\newblock \BBOQ Comparative analysis of partial order planning and {\sc htn}
  planning\BBCQ\
\newblock {\Bem ACM SIGART Bulletin}, {\Bem 6}.

\bibitem[\protect\BCAY{Kambhampati}{Kambhampati}{1997a}]{rao-ijcai-challenge}
Kambhampati, S. \BBOP1997a\BBCP.
\newblock \BBOQ Challenges in bridging plan-sythesis paradigms\BBCQ\
\newblock In {\Bem Proc. Intl. Joint Conference on Artificial Intelligence
  (IJCAI-97)}. Morgan-Kaufmann.

\bibitem[\protect\BCAY{Kambhampati}{Kambhampati}{1997b}]{rao-aimag}
Kambhampati, S. \BBOP1997b\BBCP.
\newblock \BBOQ Refinement planning as a unifying framework for plan
  synthesis\BBCQ\
\newblock {\Bem AI Magazine}, {\Bem 18\/}(2), 67--98.

\bibitem[\protect\BCAY{Kambhampati, Katukam, \BBA\ Qu}{Kambhampati
  et~al.}{1996}]{rao-ucpopebl}
Kambhampati, S., Katukam, S., \BBA\ Qu, Y. \BBOP1996\BBCP.
\newblock \BBOQ Failure driven dynamic search control for partial order
  planners: An explanation-based approach\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 88}, 253--315.

\bibitem[\protect\BCAY{Kambhampati, Knoblock, \BBA\ Yang}{Kambhampati
  et~al.}{1995}]{rao-aijdes}
Kambhampati, S., Knoblock, C., \BBA\ Yang, Q. \BBOP1995\BBCP.
\newblock \BBOQ Planning as refinement search: A unified framework for
  evaluating design tradeoffs in partial order planning\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 76}, 167--238.
\newblock Special Issue on Planning and Scheduling.

\bibitem[\protect\BCAY{Kambhampati, Parker, \BBA\ Lambrecht}{Kambhampati
  et~al.}{1997}]{rao-graphplan}
Kambhampati, S., Parker, E., \BBA\ Lambrecht, E. \BBOP1997\BBCP.
\newblock \BBOQ Understanding and extending graphplan\BBCQ\
\newblock In {\Bem Proc. 4th European Conference on Planning}. Springer Verlag.

\bibitem[\protect\BCAY{Kambhampati \BBA\ Srivastava}{Kambhampati \BBA\
  Srivastava}{1995}]{bip-ewsp95}
Kambhampati, S.\BBACOMMA\  \BBA\ Srivastava, B. \BBOP1995\BBCP.
\newblock \BBOQ Universal classical planning: An algorithm for unifying state
  space and plan space planning approaches\BBCQ\
\newblock {\Bem New Directions in AI Planning: EWSP 95, IOS Press, 61-75}.

\bibitem[\protect\BCAY{Kambhampati \BBA\ Srivastava}{Kambhampati \BBA\
  Srivastava}{1996}]{rao-ucp-tr}
Kambhampati, S.\BBACOMMA\  \BBA\ Srivastava, B. \BBOP1996\BBCP.
\newblock \BBOQ Unifying classical planning approaches\BBCQ\
\newblock \BTR\ ASU CSE TR 96-006, Arizona State University. Available
  at {\tt http://rakaposhi.eas.asu.edu/yochan.html}. 

\bibitem[\protect\BCAY{Kambhampati \BBA\ Yang}{Kambhampati \BBA\
  Yang}{1996}]{rao-kr96}
Kambhampati, S.\BBACOMMA\  \BBA\ Yang, X. \BBOP1996\BBCP.
\newblock \BBOQ On the role and utility of disjunctive representation in
  refinement planning\BBCQ\
\newblock In {\Bem Proc. Fifth Conf. Principles of Knowledge Representation and
  Reasoning (KR-96)}, \BPGS\ 135--146.

\bibitem[\protect\BCAY{Lauriere}{Lauriere}{1978}]{alice}
Lauriere, J.~L. \BBOP1978\BBCP.
\newblock \BBOQ A language and a program for stating and solving combinatorial
  problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 10}, 29--127.

\bibitem[\protect\BCAY{McAllester \BBA\ Rosenblitt}{McAllester \BBA\
  Rosenblitt}{1991}]{snlp}
McAllester, D.\BBACOMMA\  \BBA\ Rosenblitt, D. \BBOP1991\BBCP.
\newblock \BBOQ Systematic {\sc n}onlinear {\sc p}lanning\BBCQ\
\newblock {\Bem Proc. 9th NCAI-91, 634-639}.

\bibitem[\protect\BCAY{Minton}{Minton}{1988}]{minton-thesis}
Minton, S. \BBOP1988\BBCP.
\newblock \BBOQ Learning effective search control knowledge: An
  explanation-based approach\BBCQ\
\newblock {\Bem PhD thesis, Carnegie -Mellon University, Pittsburgh, PA}.

\bibitem[\protect\BCAY{Minton}{Minton}{1996}]{multi-tac}
Minton, S. \BBOP1996\BBCP.
\newblock \BBOQ Automatically configuring constraint satisfaction problems: A
  case study\BBCQ\
\newblock {\Bem Constraints}, {\Bem 1\/}(1).

\bibitem[\protect\BCAY{Minton}{Minton}{1990}]{minton-prodigy}
Minton, S. \BBOP1990\BBCP.
\newblock \BBOQ Quantitative results concerning the utility of
  explanation-based learning\BBCQ\
\newblock In {\Bem Artificial Intelligence}, \lowercase{\BVOL}~42, \BPGS\
  363--392.

\bibitem[\protect\BCAY{Penberthy \BBA\ Weld}{Penberthy \BBA\
  Weld}{1994}]{ucpop}
Penberthy, J.\BBACOMMA\  \BBA\ Weld, D. \BBOP1994\BBCP.
\newblock \BBOQ {\sc UCPOP}: A sound, complete, partial order planner for
  adl\BBCQ\
\newblock {\Bem Proc. AAAI-94, 103-114}.

\bibitem[\protect\BCAY{Russell \BBA\ Norvig}{Russell \BBA\
  Norvig}{1995}]{russ-tyre}
Russell, S.\BBACOMMA\  \BBA\ Norvig, P. \BBOP1995\BBCP.
\newblock \BBOQ Artificial {\sc i}ntelligence - {\sc a} {\sc m}odern {\sc
  a}pproach (chap 13)\BBCQ\
\newblock {\Bem Prentice Hall, Englewood Cliffs, NJ}.

\bibitem[\protect\BCAY{Smith}{Smith}{1990}]{smith-ieee}
Smith, D.~R. \BBOP1990\BBCP.
\newblock \BBOQ {\sc KIDS}: A semi-automatic program development system\BBCQ\
\newblock {\Bem IEEE Trans. on Software Engineering -- special issue on Formal
  Methods}, {\Bem 16, No.9, Sep 1990}.

\bibitem[\protect\BCAY{Smith}{Smith}{1992a}]{smith-gs}
Smith, D.~R. \BBOP1992a\BBCP.
\newblock \BBOQ Structure and design of global search algorithms\BBCQ\
\newblock {\Bem Kestrel Tech. Rep. KES.U.87.11}.

\bibitem[\protect\BCAY{Smith}{Smith}{1992b}]{smith-trans}
Smith, D.~R. \BBOP1992b\BBCP.
\newblock \BBOQ Transformational approach to scheduling\BBCQ\
\newblock {\Bem Kestrel Institute Tech. Rep. KES.U.92.2, 54pp}.

\bibitem[\protect\BCAY{Smith \BBA\ Parra}{Smith \BBA\ Parra}{1993}]{kids-kbse}
Smith, D.\BBACOMMA\  \BBA\ Parra, E. \BBOP1993\BBCP.
\newblock \BBOQ Transformational approach to transportation scheduling\BBCQ\
\newblock In {\Bem Proceedings of the 8th Knowledge-based Software Engineering
  Conference}, \BPGS\ 14--17.
\newblock Chicago, IL, Sept 1993.

\bibitem[\protect\BCAY{Srivastava, Kambhampati, \BBA\ Mali}{Srivastava
  et~al.}{1997}]{ase-kids}
Srivastava, B., Kambhampati, S., \BBA\ Mali, A. \BBOP1997\BBCP.
\newblock \BBOQ A structured approach for synthesizing planners from
  specifications\BBCQ\
\newblock {\Bem Proc. of 12th IEEE Intl. Conf. on Automated Software Engg.,
  Lake Tahoe, NV}.

\bibitem[\protect\BCAY{Tate}{Tate}{1977}]{nonlin}
Tate, A. \BBOP1977\BBCP.
\newblock \BBOQ Generating project networks\BBCQ\
\newblock {\Bem Proc. 5th IJCAI}, 888--893.

\bibitem[\protect\BCAY{Yoshikawa, Kaneko, Nomura, \BBA\ Watanabe}{Yoshikawa
  et~al.}{1994}]{yoshi}
Yoshikawa, M., Kaneko, K., Nomura, Y., \BBA\ Watanabe, M. \BBOP1994\BBCP.
\newblock \BBOQ A constraint-based approach to high school timetabling
  problems: A case study\BBCQ\
\newblock {\Bem Proc. NCAI-94}, 1111--1116.

\end{thebibliography}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}






