\documentstyle[jair,twoside,11pt,theapa,epsf]{article}
\input{psfig}
\input{shaul-macros}

\jairheading{8}{1998}{223--263}{11/97}{6/98}
\ShortHeadings{Selective Macro-learning for Solving the $N \times N$ Puzzle}
{Finkelstein \& Markovitch}
\firstpageno{223}

%%%%% Definitions

\newtheorem{Definition}{Definition}
\newtheorem{Lemma}{Lemma}
\newtheorem{Theorem}{Theorem}
\newcounter{CompactE}

%%Usage: 
%%\begin{CompactEnumerate}
%%\end{CompactEnumerate}
\newenvironment{CompactEnumerate}{\begin{list}{\arabic{CompactE}.}
{\usecounter{CompactE}
\setlength{\itemsep}{0ex plus0.2ex}
\setlength{\parsep}{0.5ex plus0.1ex minus0.1ex}
\setlength{\topsep}{0ex}
}}
{\end{list}}

\newcommand{\NN}{\mbox{$N \times N$}}
\newcommand{\ALG}{\mbox{\sc Micro-Hillary}}
\newcommand{\PARALG}{\mbox{\sc Parametric Micro-Hillary}}
\newcommand{\MACLEARN}{\mbox{\sc MacLearn}}
\newcommand{\MORRIS}{\mbox{\sc Morris}}
\newcommand{\MD}{\mbox{\sc md}}
\newcommand{\RR}{\mbox{\sc rr}}
\newcommand{\TABLINE}[1]{\hspace*{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\= 
\kill}


\newcommand{\PROOF}{\noindent {\bf Proof:}\\ \indent } 
\newcommand{\ENDPROOF}{\mbox{$\Box$}}

%\newcommand{\S}{\scriptstyle}
\newcommand{\SS}{\scriptscriptstyle}
%\newcommand{\arr_str}{\renewcommand{\arraystretch}{0.6}}
\newcommand{\arrstr}{0.5}
\newcommand{\eqnstr}{0.7}
\newcommand{\STD}{\scriptsize}




\begin{document}

\title{A Selective Macro-learning Algorithm and its Application to 
the \NN\ Sliding-Tile Puzzle}
 
\author{\name Lev Finkelstein \email lev@haifa.vnet.ibm.com\\
\addr IBM - Haifa Research Laboratory,\\
Matam, Haifa, 
Israel.\\
\name Shaul Markovitch \email shaulm@cs.technion.ac.il\\
\addr Computer Science Department,\\
Technion, Haifa 32000,
Israel\\
}


\maketitle
\begin{abstract}
One of the most common mechanisms used for speeding up problem solvers
is macro-learning.  Macros are sequences of basic operators
acquired during problem solving.  Macros are used by the problem 
solver as if they were basic operators. 
The major problem that macro-learning presents is the vast number of
macros that are available for acquisition.    Macros increase the 
branching factor of the search space and can severely
degrade problem-solving efficiency.  To make macro
learning useful, a program must be selective in acquiring and
utilizing macros.  This paper describes a general method for 
selective acquisition of macros. Solvable training problems 
are generated in increasing order of difficulty.  
The only macros acquired are those
that take the problem solver out of a local minimum to a better 
state. 
The utility of
the method is demonstrated in several domains, including   
the domain of \NN\ sliding-tile
puzzles. After learning on small puzzles, the system is able to 
efficiently solve
puzzles of any size.

\end{abstract}

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

\section{Introduction}


The goal of a learning system is to modify
 a performance element so as to
improve its performance
with respect to some given criterion.  The learning 
system 
does so by using its experience to generate knowledge for use by the 
performance element.  Most of the machine learning community is 
concerned with improving the {\em classification accuracy} of {\em 
classifiers} based on {\em classified examples}.  A smaller part of 
the 
community is concerned with improving the {\em speed} of {\em search 
programs} based on {\em problem-solving experience}.  This type of 
learning is 
commonly termed {\em speedup learning} \cite{Tadepalli:1996:FFS}.


One of the most common methods of speedup learning is the acquisition
of macro-operators 
\cite{Fikes:1972:LEG,Iba:1989:HADb,Korf:1985:LSPb,Laird:1986:CSA,Markovitch:1988:RFL,Minton:1985:SGP,Ruby:1992:EISa}.
Given the traditional definition of
a search space with a set of states and a set of basic operators that
connect them, a macro-operator is defined as a finite sequence of 
basic
operators.  Macro-operators are typically acquired during problem solving and
are used in the same manner as basic operators.  The process of
acquiring macros is relatively simple.  A system needs only to solve
training problems and pass the search tree to the acquisition
procedure, which, in turn, can add
 any sub-sequence of operators from the tree
  to its
macro knowledge-base.  The acquired macros, however, carry costs as
well as benefits.  One of the most significant costs
 associated with using macros is the 
increased branching factor of the search space.  
When the costs outweigh the benefits, we face a
phenomenon called the {\em utility problem} 
\cite{Minton:1988:LSC,Gratch:1992:CPS,Markovitch:1993:IFS,Mooney:1989:ERU}.
%More references to the utility problem

Due to the very large number of macros available for acquisition,
 a learning program
must be selective in order to obtain a macro set with high utility.
The goal of this research is to demonstrate that a simple 
macro-learning
technique, combined with the right selection mechanisms, can lead to 
a speedup learning algorithm that is powerful and general, yet simple
as well.


We start by defining a framework for selective macro-learning
and describe the general architecture of a macro learner.  
The {\em information filtering} framework \cite{Markovitch:1993:IFS} 
is used to describe
the various logical components of a macro learner.  In particular,
the framework emphasizes the important role of the selection
mechanisms used during the learning process.  
We continue by describing the \ALG\ algorithm.  
To make the presentation and the experiments clearer,
we present the algorithm in two stages.  We first
describe a simplified version of the algorithm that 
learns macros for a single domain at a time.  We then show a generalized
version that can handle a family of domains.

\ALG, like all other macro-learners, is useful for
{\em satisficing} search.  
Macro-learning has a negative utility when used for {\em optimizing search} 
\cite{Markovitch:1992:SEDa}.  Even when the learned macros
are optimal they are not useful for optimizing search procedures:
knowing the shortest way
from point $A$ to point $B$ and the shortest way from
$B$ to  $C$ does not tell us anything about 
the optimality of their concatenation.

The input for the \ALG\ algorithm is a domain, specified 
by a set of basic operators, a heuristic function (not necessarily 
admissible) for evaluating the merit of
states, and a function for generating random goal states.
The \ALG\ algorithm performs {\em learning by experimentation} 
\cite{Mitchell:1983:LEA}.
It generates solvable
training problems with an increasing level of difficulty.
The training problems are solved by a search program that
performs hill-climbing combined with a procedure for escaping
local minima.  The escape routes are then recorded as macros.
The problem solver uses the same search procedure, using
macros as if they were basic operators.
\ALG\ performs the maximal possible generalization 
by trying all the macros in all the states.  Such a method increases 
the branching factor by the number of macros and would be too 
expensive when used in search procedures such as best-first search.  Using
this method in hill-climbing significantly reduces this overhead (unless
the solutions found are significantly longer).

The architecture of \ALG\ contains building blocks that are inspired
by the earlier works  of many other researchers.
  Generating training problems with increasing 
difficulty was done {\em manually} by several researchers 
 \cite<for example>{Iba:1985:LDM,Minton:1985:SGP,Mitchell:1983:LEA}.  
EASe \cite{Ruby:1992:EISa} used hill-climbing to avoid exponential 
increase in search time as a result of adding macros.  \MORRIS\ 
\cite{Minton:1985:SGP} and \MACLEARN\ \cite{Iba:1985:LDM} used 
macro selection methods that inspired the one used by \ALG.  The 
\ALG\ architecture is a well-balanced and well-tuned combination of 
these building blocks that emerged after extensive experimental study.


The main domain upon which \ALG\ was tested is 
the general \NN\ sliding-tile puzzle  \cite{Ratner:1990:NPR} which 
includes
as special cases the 8-puzzle, 15-puzzle and
the 24-puzzle.  The 8-puzzle and
the 15-puzzle problems have long been popular among
mathematicians \cite{Johnson:1879,Kraitchik:1953:MR,Tait:1880:NTP} 
and AI researchers.
The sliding-tile puzzles are among the most commonly used 
domains for testing heuristic search algorithms  and
macro-learning 
\cite{Bui:1997:s8p,Iba:1985:LDM,Korf:1985:LSPb,Laird:1986:CSA,%
Ruby:1992:EISa,Schofield:1967:CSP}.
The reason for the popularity of
sliding-tile puzzles is the simplicity of their specification
combined with the very large size of their associated
 search space \cite[p.~4]{Pearl:1984:HIS}.
An \NN\ puzzle problem has an associated search graph
of size $N^2!/2$.  
The {\em optimizing} \NN\ puzzle problem
is NP-hard \cite{Ratner:1990:NPR}, although some research efforts
 have been made in finding optimal solutions to the
 15-puzzle \cite{Korf:1985:DFI}
and the 24-puzzle \cite{Korf:1996:FOS}.   
It is not difficult to devise
a domain-specific algorithm for solving the {\em satisficing}
 \NN\ puzzle problem \cite<see for example>{Ratner:1990:NPR}. 
However, the attempts to find even
non-optimal solutions for the puzzle {\em using weak methods} 
were successful only for small puzzles. 
A notable exception is the paper by  Korf \citeyear{Korf:1990:RTS}, who
outlined a search algorithm for solving \NN\ puzzles.  
\MACLEARN \cite{Iba:1989:HADb}, for example, one of the most successful
macro-learners, was demonstrated solving only a single
$5 \times 5$ puzzle problem.

It is therefore a worthwhile challenge to devise a simple, 
domain-independent, learning algorithm that will be able 
to acquire the ability to efficiently solve any solvable \NN\ puzzle
problem.  The paper includes a comprehensive set of experiments that
test the properties of the algorithm mostly in the \NN\ puzzle domain.
We show that 
the learned macros can solve very large puzzles, and 
supply a formal proof that the generated macros are sufficient
for efficiently solving puzzles of any size. 

While the \NN\ puzzle is the main domain tried, the \ALG\ 
algorithm is completely domain-independent.  We made efforts to build
a minimal domain-independent architecture that is sufficient to
solve the \NN\ puzzle, as well as problems in other domains, 
without introducing domain-dependent enhancements. 
We include
experiments in other domains to demonstrate that the 
algorithm is indeed domain-independent.  

Section \ref{sec:background} defines selective macro-learning and 
identifies the choices to be made when designing a macro-learning
system.
Section \ref{sec:hillary} describes the general \ALG\footnote{
\ALG\ is a simplified version of a system called Hillary 
\cite{Finkelshtein:1992:SAU}.
The program was named after Sir Edmund Hillary.  We
did not notice that the name Hillary had already been used by
Iba, Wogulis and Langley \citeyear{Iba:1988:TSC}.}  algorithm
for learning macro-operators.  Section \ref{sec:exper}
describes experiments with \ALG\ in various domains, mainly
the 15-puzzle domain.  Section \ref{sec:scalable} describes
an extension of \ALG\ that is able to learn a family of domains
that are differentiated by a single numeric parameter, and
describes the application of the parameterized algorithm
to the family of \NN\ puzzle domains.  Finally, Section 
\ref{sec:discussion}
discusses and sums up \ALG's strengths and weaknesses,
in comparison to other macro-learning algorithms.



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

\section{Background: Selective Macro-Learning}
\label{sec:background}


Let $S$ be a finite set of {\em states}.  Let $O$ be a finite 
set of {\em operators}
where each operator $o \in O$ is a function $o : S \rightarrow S \cup 
\{ \emptyset \}$.  If $o(s)=\emptyset$, we say that $o(s)$ is 
undefined.
A {\em problem} is a pair of states $\left \langle s_i , s_g \right
\rangle$, where $s_i \in S$ is called the {\em initial state} and 
$s_g \in S$ is called the {\em goal state}.\footnote{The formalization 
could have used a goal predicate that returns
true for states that are goal states.  For simplicity we assumed
a single specified goal state.}  A {\em solution} is a sequence
of operators $\left \langle o_1 , \ldots , o_k \right \rangle$, such
that $o_k\left(\ldots o_1\left(s_i\right)\ldots\right)=s_g$.
A problem  $p=\left \langle s_i , s_g \right \rangle$ is {\em 
solvable}
if there exists a solution for $p$ (specified
by $solvable(s_i,s_g)$).


A {\em macro-operator} is a sequence of operators
$m=\left \langle o_1 , \ldots , o_k \right \rangle$. 
A macro-operator  $m$ is applied to a state  $s \in S$ by applying 
its basic
operators in a sequence.  If while applying the sequence of operators we encounter
an undefined application, the application of the macro is undefined.

\[
m(s)=
\left\{
\begin{array}{ll}
o_k\left(\ldots o_1\left(s \right) \ldots \right) &
\forall i \leq k \left [ o_i\left(\ldots o_1\left(s \right) \ldots 
\right) \neq
\emptyset \right ]\\
\emptyset & \mbox{otherwise.}

\end{array}
\right.
\]

A {\em problem solver} $\varphi$ is an algorithm that takes a problem 
$p$
and a set of operators $O$ and applies operators to states, searching
 for a solution
to $p$.
Given a solvable problem $p$, a problem solver $\varphi$ 
and a set of operators
$O$, we define $SearchCost(\varphi,p,O)$,
the {\em cost} of solving $p$ using  $\varphi$ and 
$O$, as the number of operator applications performed by $\varphi$ 
until a solution is found. Note that SearchCost is different from
the solution cost---the cost of the solution path according to some
cost function.  In this work we are only interested in {\em 
satisficing} search---minimizing the 
cost of the search regardless of the cost of the resulting solution.

The {\em utility} of a set of macros $M$, with respect to a problem 
$p$, 
a problem solver $\varphi$ and a set of operators $O$, is defined as 
\begin{equation}
\label{eqn:utility-problem}
U_{p,\varphi,O}(M)= 
SearchCost(\varphi,p,O)
- SearchCost(\varphi,p,O \cup M).
\end{equation}
Thus, the utility of a set of macro operators with respect
to a given problem and a given problem solver is the time saved
by using these operators.
When the problems are drawn from some fixed distribution $D$, we
 use expectation values
for a problem randomly drawn from $D$:
  \begin{equation}
\label{eqn:utility}
U_{\varphi,O}(M)= 
E_{D(p)}[SearchCost(\varphi,p,O)
- SearchCost(\varphi,p,O \cup M)].
\end{equation}
In general, the utility of knowledge depends on the criteria used for 
evaluating the performance of the problem solver 
\cite{Markovitch:1993:IFS}.  
Equation \ref{eqn:utility} assumes a {\em speedup 
learner}, i.e., a learner whose goal is to increase the speed of 
solving problems.  

Most of the macro-learning systems perform
{\em learning by experimentation} \cite{Mitchell:1983:LEA}.  The 
program
solves training problems and acquires sequences of operators applied
during the search.  Given a set of operators $O$, 
a distribution of problems $D$, 
and a problem solver $\varphi$, the goal of a macro-learning 
system is to acquire a set
of macro-operators $M$, such that $U_{\varphi,O}(M)$ is positive,
and as high as possible.  It is quite possible, however, that
the utility of $M$ will be negative, as the added macros 
also increase the branching factor.

Markovitch and Scott \citeyear{Markovitch:1993:IFS} introduced the 
{\em information
filtering} framework, which offers a systematic way of dealing with the
utility
problem by being more selective.
The framework identifies five logical types of selection
processes in learning systems: selective experience, selective
attention, selective acquisition, selective retention and selective
utilization.  The framework views learning programs as information
processing systems where information flows from the experience space
through some attention mechanism, through an acquisition procedure to
the knowledge base and finally  to the problem solver.  The
five filters are defined with respect to their logical location within
the information flow.



\begin{figure}[t]
\centerline{\hbox{
\psfig{figure=pictures/architecture.eps,width=4.5in}
}}
\caption{\label{fig:architecture}
\small 
The architecture of an off-line macro-learning system.  Training 
problems
are generated and filtered by the experience filter.  The attention 
procedure
converts the search traces into operator sequences that are filtered
by the attention filter.  The sequences are converted to 
macro-operators.
The acquisition filter decides whether to add new macros to the macro 
set.
The retention filter deletes macros with negative utility.  The
utilization filter allows only a subset of the macro set to be used 
by the
problem solver.
}
\end{figure}

The general architecture offered by the information-filtering
framework, instantiated to  off-line macro-learning,  is
shown in Figure \ref{fig:architecture}.
Markovitch and Scott argue that the art of building successful
learning systems  often lies in selecting the right combination of
filters.  A careful examination of existing macro-learning systems
reveals that those containing sophisticated filtering mechanisms
performed the most successful learning.

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


\section{\ALG}
\label{sec:hillary}

In this section we discuss \ALG---a particular instantiation of the 
architecture described above that is both very simple, yet powerful 
enough
to perform efficient learning in a large class of problem domains.
\ALG, like most macro-learners, works with {\em satisficing} 
\cite{Simon:1975:OPS} 
search programs, i.e., programs whose goal is to find 
solutions as fast as possible regardless of the length of the 
solution 
found \cite[p. 14]{Pearl:1984:HIS}.  
Such programs typically use heuristic functions which serve 
as preference predicates---the search strategy prefers to expand states with 
a lower value.  In this work we consider heuristic functions which are
not necessarily underestimating, but are always positive, except in
the goal states where they have a zero value.  We call such heuristic
functions {\em well-behaved}.
Many of these heuristic functions order states reasonably well
except in a small number of local minima.  
The basic idea of \ALG\ is to acquire macro-operators
for escaping from local minima, i.e., macros that lead
from a local minimum to a state with a better heuristic value.

\ALG\ works by generating training problems and solving them.
 A good way to detect local minima is to
use  a search method such as hill-climbing, which is susceptible 
to local minima.  Therefore, \ALG\ uses simple 
hill-climbing\footnote{Simple hill-climbing means that the problem
solver steps forward as soon as an improvement is detected without
waiting for the {\em best} improvement.}
 for its
problem solver, both in the learning and in the problem-solving mode.
When trapped in a local minimum, \ALG\ searches
for a way out to a state with a better heuristic value, 
and records this escape route as a macro-operator.
Let $Q$ be a predefined limit.  We say that \ALG\ is 
in {\em quiescence} when it solves $Q$ consecutive
training problems without acquiring any new macros.
\ALG\ quits when it detects quiescence.

When used for solving externally supplied problems,
\ALG\ uses the union of the basic operators and the learned macros.
When faced with a local minimum, it searches for an escape
route but does not acquire macros.
An alternative version can perform on-line learning.
Figure \ref{fig:algorithm} shows the \ALG\ algorithm.
To complete the algorithm we need to specify a method for generating
training problems and a method for escaping from local minima.
The {\em SolveProblem} procedure serves both
for learning and for solving externally supplied problems.

\begin{figure}[htb]
\begin{center}
\fbox{
\begin{minipage}{\textwidth}
\begin{tabbing}
\TABLINE{0.5cm}
procedure \ALG(BasicOps,h)\\
\>  Macros $\leftarrow \{  \}$\\
\>  $q \leftarrow 0$     \`; q is the quiescence counter\\
\>  loop until $q > Q$   \`; Q is the quiescence parameter\\
\>  \>  $\langle s_i , s_g \rangle \leftarrow$ 
GenerateTrainingProblem() \\
\>  \>  $q \leftarrow q + 1$\\
\>  \>  MacrosBefore $\leftarrow |\mbox{Macros}|$\\
\>  \>  SolveProblem$(s_i,s_g,\mbox{BasicOps},\mbox{Macros},h)$\\
\>  \>  If $|\mbox{Macros}| > \mbox{MacrosBefore}$ then $q \leftarrow
0$   \`; New macros were learned\\
\>  Return Macros\\
\\
procedure SolveProblem$(s_i,s_g,\mbox{BasicOps},\mbox{Macros},h)$\\
\>  Solution $\leftarrow \{  \}$\\
\>  $s \leftarrow s_i$\\
\>  loop until $s = s_g$\\
\>  \>  $LocalMinimum \leftarrow TRUE$\\
\>  \>  loop for $o \in$ BasicOps $\cup$ Macros while LocalMinimum\\
\>  \>  \>  if $h(o(s),s_g) < h(s,s_g)$ then  \`; Progress was
achieved.  Step forward.\\
\>  \>  \>  \>  $\mbox{Solution} \leftarrow \mbox{Solution} || o$\\
\>  \>  \>  \>  $s \leftarrow o(s)$\\
\>  \>  \>  \>  $LocalMinimum \leftarrow FALSE$\\
\>  \>  if $LocalMinimum$ then   \`; No progress---local minimum.\\
\>  \>  \>  $O \leftarrow$ FindEscapeRoute$(s,s_g)$\\
\>  \>  \>  $s \gets O(s)$\\
\>  \>  \>  $\mbox{Solution} \leftarrow \mbox{Solution} || O$\\
\>  \>  \>  if LearningMode then Macros $\gets$ Macros $\cup \{O\}$\\
\>  Return Solution
\end{tabbing}
FindEscapeRoute$(s,s_g)$:  A procedure that finds a sequence of
operators $O=o_1,\ldots ,o_k$ such that $h(o_k(\ldots 
o_1(s)\ldots),s_g) < h(s,s_g)$.
\end{minipage}
}
\end{center}
\caption{\label{fig:algorithm}
\small
The \ALG\ algorithm}
\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Selective Experience:  Generating Solvable Problems
with Increasing Levels of Difficulty}

The basic architecture of a macro-learning system requires
a mechanism for generating training problems and a method
for filtering them (or, alternatively, a method for ordering
them).  The main goal of the filter is to save learning resources by
concentrating on helpful problems.
To focus the attention of the learner, our acquisition
method considers only macros that are parts of the solution path.
Therefore, to save learning resources, a good problem generator should 
generate only solvable problems.  In addition, it is desirable to order
the training problems in increasing levels of difficulty.  
This saves learning resources by acquiring as much
knowledge as possible using easy problems.


One good way to implement such a problem generation methodology
is to require a domain-specific generator for each domain.  
For example, solvable problems in the \NN\ puzzle domain can be 
generated by performing an even permutation on the goal 
state. 
Since one of our main goals was to make the algorithm as
 domain-independent as possible, we have supplied a default 
domain-independent generator that works in many domains, including the
sliding-tile puzzle.
Our default problem generator 
assumes
the following:
\begin{itemize}
\item The specification of the
problem domain includes an algorithm for generating random goal states
(unless there is only one goal state).
\item  All the operators are {\em reversible}.  If there
is an operator connecting state $s_1$ to state $s_2$ then there
is also a sequence of operators connecting $s_2$ to $s_1$: 
\[
\forall s_1,s_2
\in S \left [ \exists o \in O \left [ s_2=o(s_1) \right ]
\rightarrow \exists O'=\left\langle o_1,\ldots,o_k\right \rangle,
o_i \in O \left [ s_1=O'(s_2) \right ] \right ].
\]
Alternatively, the specification of the domain includes a list of 
reverse operators.
\end{itemize}
Problems are generated by applying a random sequence of operators to a
randomly generated goal state.  This process is known as 
{\em random walk}.  The length of the random sequence is 
increased after each problem generation.   In some domains, when the random
sequences are short enough compared to the size of the search space, and 
when there are no ``bottlenecks'' in the search graph, longer 
sequences are likely to yield ``harder'' problems (problems with 
larger distance between the start and goal states).  In other domains 
the hardness of  the problems may be uniformly distributed and not correlate 
                with the length of the random walk.
In such domains we can use the heuristic function as an estimate
 of the problem difficulty by which
 the random problems will be ordered.
The generator sets a threshold on the heuristic distance
between the initial state and the goal state and performs a
random walk until a state with the required heuristic distance is 
found.  The threshold is incremented with each iteration.
This approach is still problematic in domains with
``bottlenecks'' where parts of the search graph are difficult
to access. For such domains it is best to use a domain-dependent
generator.

In Section \ref{sec:scalable} we describe a method for increasing
 the difficulty of training problems
by increasing the parameter that characterizes the domain 
(such as $N$ in the case of \NN\ puzzles).
For most parameterized domains, such as the \NN\ puzzle, increasing
the parameter indeed increases the difficulty of problems.
The framework of processing input examples by
order of difficulty, called {\em learning
from exercises}, was studied formally by Natarajan
\citeyear{Natarajan:1989:OLF} and empirically by
Reddy and Tadepalli \citeyear{Reddy:1997:LGD}.
Both works assume a teacher who supplies a sequence of problems
in increasing order of difficulty.  Our default generator attempts to
produce such a sequence automatically, freeing the learner from
the need of a teacher.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Selective Attention: Acquiring Macros Leading from Local
Minima to Better States}
\label{sec:selective}

Given a search trace, every subpath of it can be recorded as a macro.
Obviously, there are too many subpaths, so we need to employ a filter
in order to acquire a set of macros with high utility.
What properties of macros are likely to indicate high utility?  There
are three requirements that should be fulfilled:
\begin{enumerate}
\item The macros should be useful, i.e., they should save the system
significant search resources.
\item There should be as few macros as possible.  Redundant macros
increase the branching factor of the search graph without 
associated benefits.
\item The macros should be as short as possible, for two reasons:
\begin{itemize}
\item Long macros tend to be less general.  The main reason is that
applying a long sequence of basic operators to a state is likely to
encounter an illegal state.
\item For the learning method of \ALG, longer macros require
significantly more learning resources (for the escape procedure).
\end{itemize}
\end{enumerate}
The filtering method we use for \ALG\ only acquires macros leading
from a local minimum to a better state.  Whenever not in a local
minimum, the search procedure can use the heuristic function, so
macros that do not start in a local minimum are not necessary.
The macros acquired by this filtering method
are useful since they enable the search procedure to
continue from a local minimum.  These macros are also the shortest that
satisfy that condition.
We call this method a {\em minimum-to-better} filtering.
Let $h$ be a {\em well-behaved} heuristic function (not necessarily admissible), let $e=\left\langle s_{init}, s_g \right 
\rangle$
be a training problem, and let $T = \left \langle o_1, \ldots , o_n
\right \rangle$ be a 
solution to $e$. 
Let $s_l = o_{l} (o_{l-1} (\ldots o_{1}(s_{init})))$ denote the state
resulting from the application of
 the sequence $\left \langle o_1, \ldots , o_l
\right \rangle$ to the initial state.
A subpath $\left \langle o_{j} , o_{j+1}, \ldots , o_{j+k} \right
\rangle$ is selected by 
the {\em minimum-to-better} attention filter if and only if the
following condition holds:
\begin{equation}\label{eqn:minimum-to-better-filter}
\begin{array}{l}
 \forall o \in O [h(s_{j},s_g) \leq 
h(o(s_{j}),s_g)] \wedge \\
h(s_{j+k},s_g) < h(s_{j},s_g) \wedge \\
 \forall y [0 < y < k\rightarrow h(s_{j},s_g) \leq 
h(s_{j+y},s_g)]
\end{array}
\end{equation}
The first conjunct says that the first state of a macro must be a
local minimum.  It serves to satisfy requirement 2 above---that there
should be as few macros as possible.  The second conjunct says that the
last state must be a better state.  It serves to satisfy requirement 1
above---that macros should be useful.  The third conjunct says that
the macro is the shortest satisfying the former two conjuncts.  It
serves to satisfy the third requirement above---that macros should be as
short as possible. 
When a sufficient number of such macros has been acquired, the search 
program
may be able to advance toward the goal state without ever 
being trapped in local minima.
\begin{Definition}
\label{def:complete}
Let $S$ be a set of states and $O$ a set of operators.
Let $s_g$ be a goal state.  Let $h$ be a {\em well-behaved}
heuristic function.
Let $M$ be a set of macro-operators.  
We say that $M$ is {\em complete} with respect to $h$ and $s_g$
if and only if 
\[
\forall s \in S - \{s_g\} [solvable(s,s_g) \rightarrow 
\exists o \in O \cup M [h(o(s),s_g) < h(s,s_g)].
\]
\end{Definition}
A {\em complete} macro set ``smooths'' the heuristic
function by eliminating local minima.  The length of the individual
macros in a complete set depends on the distance between local minima
and their associated better state.  
\begin{Definition}
Let $S$ be a set of states and $O$ be a set of operators.
Let $s_g$ be a goal state.  Let $h$ be a {\em well-behaved}
heuristic function.  Let $d(s_1,s_2)$ denote the graph distance
between $s_1$ and $s_2$ in the graph defined by $O$.
The {\em radius} of a state $s_0 \in S $
with respect to $h$, $s_g$ and $O$
is defined as:
\[
radius(s_0)=\min_{s \in S \wedge h(s,s_g)<h(s_0,s_g)}d(s_0,s).
\]
The radius of the goal state is 0.  The radius of a state which is not a
local minimum is 1.  
\end{Definition}


\begin{figure}[htp]
\twofig{pictures/ptop-example2.eps}{pictures/ptop-example1.eps}
\caption{\label{fig:ptop-example}
\small 
An illustration of the differences between the {\em minimum-to-minimum}
and {\em minimum-to-better} filtering methods.
The X axis stands for the sequence of states along the solution path.
The Y axis stands for the heuristic values of states.
(a)  A situation where
the {\em minimum-to-better} strategy acquires short macros
that are just sufficient to allow  progress in the
heuristic search while 
the {\em minimum-to-minimum} strategy acquires unnecessarily long
macros that are likely to be less applicable.
 (b)  A situation where
the {\em minimum-to-minimum} strategy acquires a macro
that leads from a local minimum to a state with {\em worse}
(higher) value.
The {\em minimum-to-better} strategy always acquires macros
that lead to a state with a better (lower) value.
}
\end{figure}


The {\em minimum-to-better} filter looks similar to the
{\em minimum-to-minimum}\footnote{The original name given by Iba is
peak-to-peak.
To make the name of the filter 
more appropriate for heuristic functions that consider lower values as
better, we  call Iba's method minimum-to-minimum.}  filtering method used by Iba
\citeyear{Iba:1989:HADb}.  However, there are
several problems with the {\em minimum-to-minimum} method that the
{\em minimum-to-better} filter avoids.
When the distance between minima is large, the minimum-to-minimum
filter will acquire very long macros.  This violates the third
requirement above.
 Figure \ref{fig:ptop-example}(a) illustrates this problem.
The X axis stands for the sequence of states along the solution path.
The Y axis stands for the heuristic values of states.
Long macros such as those acquired by the minimum-to-minimum filter
 tend to be much less general (they are more likely to fail).  
This problem is intensified with incremental
learning.  In the first stages of learning, the minima 
are close together and short macros are learned.
These macros, however, make minima more sparse in later stages
of learning, leading to the acquisition of very long macros.
This problem becomes extreme when there is only one minimum in the 
solution path.  In such a case, the minimum-to-minimum filter will either 
learn nothing, or will use Iba's approach and consider the start and 
end states of the solution path as minima, leading to the acquisition 
of two very long macros.
Indeed, when we tried to replace the 
{\em minimum-to-better} with the  {\em minimum-to-minimum} 
filter, \ALG\ went into a very long session of acquiring
very long macros.  Iba had to introduce an acquisition filter that 
blocks
long macros in order to reduce the harmfulness of this
phenomenon.


Another problem with the {\em minimum-to-minimum} method is 
that it may learn routes from a minimum to a {\em worse} (higher)
minimum.  This violates the first requirement above.
Figure \ref{fig:ptop-example}(b) illustrates this problem.
Of course, it may 
then learn another macro from the worse minimum, but the total number of 
macros still increases needlessly.
The {\em minimum-to-better} strategy always acquires macros
that lead to a state with a better (lower) value.  
In Section \ref{sec:discussion} we discuss further differences
between \MACLEARN\ and \ALG.

The T-Macros acquired by \MORRIS\ \cite{Minton:1985:SGP} also 
resemble the macros acquired by \ALG.  A T-Macro is ``locally 
anomalous. Its initial segment appears to make no progress, but the 
sequence as a whole is rated as advantageous'' 
\cite{Minton:1985:SGP}. It is therefore possible to call the 
selection strategy employed by \MORRIS\ {\em any-to-better}.  
This method, which does not insist on starting a macro from a local 
minimum, will acquire more macros than the
minimum-to-better strategy.  These macros are not necessary and
violate the second requirement above.
The larger number of  (possibly unnecessary)
macros will increase the branching factor and
may deteriorate  the performance of the program that uses them.  

\begin{figure}[htb]
\centerline{\hbox{
\psfig{figure=pictures/any-to-better.eps,width=3in}
}}
\caption{\label{fig:any-to-better}
\small 
An illustration of the difference between the {\em any-to-better}
and {\em minimum-to-better} selection methods.
The X axis stands for the sequence of states along the solution path.
The Y axis stands for the heuristic value of states.
The any-to-better strategy acquires more (possibly unnecessary) macros.
}
\end{figure}

Figure~\ref{fig:any-to-better} illustrates the 
difference between the two strategies.  While the {\em minimum-to-better} 
strategy will acquire one macro that smooths the path, the {\em 
any-to-better} strategy acquires many macros that will unnecessarily
increase the branching factor.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Escaping from Local Minima}
\label{escaping}
In Section \ref{sec:selective} we defined the {\em radius} of a state as
the shortest graph distance to a state with a better (lower)
heuristic value.  The radius affects the resources needed to
find an escape route from a local minimum.
There are several possible ways to escape from a local minimum.  
Exhaustive search methods, such as
breadth-first search (BFS) or iterative deepening (ID),  guarantee
finding an escape route if such a route exists.  
However, an exhaustive search
requires too much computation  for any non-trivial escape
task.  We can try to make some use of the heuristic function by
calling A* or IDA*.  Both methods, however, waste much effort
to ensure that the route to the goal state is 
optimal.
We are looking for a search method that will find solutions quickly 
if the
heuristic function is sufficiently accurate, 
but also guarantees finding a solution
even if the heuristic function is poor.  

\begin{figure}[htb]
\begin{center}
\fbox{
\begin{minipage}{10cm}
\begin{tabbing}
\TABLINE{0.5cm}
procedure ILB(state, goal, h, D)\\
\>  b $\leftarrow$ number of basic operators\\
\>  loop for exp = 1 to D\\
\>  \>  BreadthLimit $\leftarrow k+b^{exp}$\\
\>  \>  Path $\leftarrow$ LBFS(BreadthLimit, D, State, Goal, h)\\
\>  \>  If Path is not empty return path\\
\\
procedure LBFS(BreadthLimit, State, Goal, h, D)\\
\>  InitValue $\leftarrow$ h(State,Goal)\\
\>  NewOpen $\gets$ (Node(State,NIL))\\
\>  loop for d = 1 to D\\
\>  \>  Open $\gets$ NewOpen; NewOpen $\gets$ NIL\\
\>  \>  loop for $Node \in$ Open\\
\>  \>  \>  loop for Op in Operators\\
\>  \>  \>  \>  NewState $\gets$ Op(State)\\
\>  \>  \>  \>  if h(NewState) $<$ InitValue\\
\>  \>  \>  \>  \>   return Node.Op $||$ op\\
\>  \>  \>  \>  else\\
\>  \>  \>  \>  \>   NewOpen $\gets$ Insert(Node(NewState,Node.Op 
$||$op), NewOpen)\\
\>  \>  \>  \>  \>   if length(NewOpen) $>$ BreadthLimit\\
\>  \>  \>  \>  \>   \>  Remove from NewOpen a node with maximum h\\
\end{tabbing}
\end{minipage}
}
\end{center}
\caption{\label{fig:ILB-ALG}
\small
The ILB algorithm}
\end{figure}

We came up with a search
method that we call Iterative Limited BFS (ILB).  The basic procedure
is Limited BFS, which gets an initial state, a goal predicate, a
breadth limit $B$ and a depth limit\footnote{
$D$ is a predefined upper limit ($D=100$ was used for the experiments 
described here) on the maximal radius.  If, for some reason, the escape 
route is longer than $D$, we can iterate the algorithm with a larger $D$.}
 $D$.  It performs a BFS search to
depth $D$.  Whenever the number of nodes kept in memory exceeds $B$, it
deletes the node with the worst heuristic value.  This search is
different from beam search.  Limited BFS keeps the $B$ best nodes of 
the current depth, while beam search keeps the  $B$ best nodes 
regardless 
of their depth.  When $B$ approaches infinity, beam search becomes 
best-first search, while limited BFS becomes BFS.
ILB calls limited BFS iteratively
until either a full BFS to depth $D$ is performed or a solution is found.  The
breadth limit $B$ is increased for each iteration and is set to the
value $k+b^i$, where $k$ is some constant, $b$ is the maximum branching 
factor and
$i$ is the iteration number.  This scheme guarantees that ILB will 
perform
full BFS to depth $D$ after $D$ iterations.  Figure \ref{fig:ILB-ALG} shows the
algorithm.  Note that this method is somewhat similar to 
iterative broadening \cite{Ginsberg:1992:IBR}, but there the broadening 
is performed at the node level.  That means that for  domains such as 
the sliding-tile puzzles which have a branching factor of less than 3,
only 3 iterations would be performed.

\begin{figure}[t]
\centerline{\hbox{
\psfig{figure=pictures/ILB-1.eps,width=4in}
}}
\caption{\label{fig:ILB-1}
\small 
An illustration of the way that ILB works.  The state at the top is
the local minimum.  The state at the bottom left is a state with a
lower (better) heuristic value.  The states are ordered in levels
according to their distance from the local minimum.  In each level
they are ordered by their heuristic value (the lowest value to the 
left).  The gray states are the escape route. 
The gray rectangle shows the states visited in the last iteration
of ILB.
ILB will find the 
route
when using a breadth limit of 4 and will require linear time ($4 
\times 11$) for its last iteration.  ID will require exponential time
for its last iteration ($3^{11}$ if the branching factor is 3).
}
\end{figure}

Figure \ref{fig:ILB-1} illustrates the way that ILB works.
The state at the top is
the local minimum.  The state at the left bottom is a state with a
lower (better) heuristic value.  The states are ordered in levels
according to their distance from the local minimum.  In each level
they are ordered by their heuristic value (the lowest value to the 
left).  The gray states are the escape route.  ILB would find the 
route
when using a breadth limit of 4 and will require linear time ($4 
\times 11$) for its last iteration.  ID will require exponential time
for its last iteration ($3^{11}$ if the branching factor is 3).  The
last iteration is dominant for both algorithms.
Note that ILB works differently from iterative beam search.  
Beam search could progress to the right portion of the search graph 
instead of going deeper as ILB does.


The particular escape method is not an inherent part of \ALG.
In the experimental section we will show that for the \NN\ puzzle domain,
ILB is much faster than iterative deepening.
In domains where the heuristic function does not indicate
 the direction of the escape route, ILB
 may reduce to full BFS and require too much memory.  
Furthermore, if $D \gg Length(Escape)$, ILB will also require
much more computation time because all the iterations except the last
one will be performed to depth $D$, while ID would search to a depth
that is equal to the length of the escape route.
In such cases, using iterative deepening as an escape algorithm
may be more appropriate.

One important issue to consider when designing an escape
procedure is whether acquired macros are used during the escape
search.
Using macros increases the branching factor, which can lead to 
a prohibitively expensive search, but it also allows deeper penetrations.
In the experiments performed,
we found  that it is more beneficial to search for an escape route
using only basic operators.  It is quite possible, however, that 
in some domains it is beneficial to use macros.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Generalization and Use of Macros}
A major factor that determines the utility of macros
is the decision regarding where to use them.
The major contributor to the utility problem in macro
learning is the
increased branching factor of the search graph as a result
of the added macros.
At one extreme, we can avoid generalization and apply
a macro only at the same state where it was acquired.
This approach will reduce the cost of the added branching
factor but will also reduce the benefit of macros since
they will be rarely applicable.
At the other extreme, we can aim for full generalization
and apply a macro at any state as if it were a basic
operator.  This approach has the potential
of significantly increasing the benefit of macros, but it
also increases the cost dramatically because every acquired
macro increments the branching factor by one.
\MACLEARN, which uses best-first search, cannot use the
second approach because it will make the search prohibitively
expensive.  Therefore, it uses a domain-specific pattern language
and domain-specific abstraction procedures
to perform a more restricted generalization of macros.
Since in \ALG\ we tried to avoid domain-specific procedures,
we took the second approach of full generalization.
Fortunately, the hill-climbing search employed by the problem solver
in \ALG\ does not suffer from the extreme increase in search time
as a result of the increase in the branching factor.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Using \ALG\ for a Specific Domain}

To use \ALG\ for learning in a specific domain, the following
domain-specific information should be supplied:
\begin{CompactEnumerate}
\item A function that generates a random goal state.
\item A set of operators that accept a state and return either 
another state or $\emptyset$.
\item A {well-behaved} heuristic function.
\end{CompactEnumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Correctness of \ALG}
A problem solver is {\em complete} if it terminates with a solution
when one exists \cite[p. 75]{Pearl:1984:HIS}.
If, when starting from a solvable state, we never reach unsolvable
states, and if the range of the heuristic function is finite,
then a complete set of macros yields a complete problem solver.

Let $S$ be a set of states and $O$ a set of basic operators. Let
$P \subseteq S \times S$ be a set of solvable problems with the
following
property: 
\[
\forall \left \langle s_i , s_g \right \rangle \in P,
\forall s \in S \left [ solvable(s_i,s) \rightarrow solvable(s,s_g)
\right ].
\]
Let $h$ be a well-behaved heuristic function with a finite range, $R_h$,
over S ($R_h=|\{h(s) | s \in S \}| < \infty$).
Let $M$ be a complete set of macros.  Then, SolveProblem using $M$
 is a complete
problem solver with respect to $P$.  Furthermore, the number of
operator applications is bounded by $(|O|+B_m) R_h$ where $B_m$ is the total
length of macros in $M$.\\  
\PROOF
In every step of the hill-climbing procedure we are guaranteed (by the
completeness of $M$) to find a state with a heuristic value which is
lower than the value of the current state.  Since $h$ is well-behaved,
and since it has a finite number of values, $R_h$, we can make at most
$R_h$ steps before reaching a goal state with $h(s)=0$.  At every
step, in the worst case, we try all the basic operators and all the
macros before finding the one that makes  progress.  Therefore the
total number of operator applications is bounded by  $(|O|+B_m) R_h$.
\ENDPROOF

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experimenting with \ALG}
\label{sec:exper}
To test the effectiveness of the \ALG\ algorithm, we
experimented with it in various domains.
Most of the experiments were done in the 15-puzzle domain. 
The basic operators in this domain are {\em Up}, {\em Down},
 {\em Left} and {\em Right}, 
indicating the direction in which the empty tile ``moves''.  
The heuristic function, which we denote by \RR,
 is similar to the one used by 
Iba \citeyear{Iba:1989:HADb} and by Korf \citeyear{Korf:1990:RTS}.
The function contains three factors that are ordered
lexicographically: 
the total number of tiles minus the count
of tiles consecutively placed in a left-to-right, top-to-bottom,
 row-by-row order,
the Manhattan distance of the first tile that is not in place to its
destination, and the Manhattan distance of that tile from the empty 
square.  
Consider, for example,  the following puzzle:
\[
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
1 & 2 & 3 & 4 & 5  \\
\hline
6 & 7 & 8 & 19 & 16  \\
\hline
14 &   & 17 & 18 & 15  \\
\hline
20 & 24 & 13 & 22 & 21  \\
\hline
23 & 9 & 10 & 11 & 12  \\
\hline
\end{array}
\].
There are 8 tiles placed in the specified order; therefore, the first
component is $24-8=16$.  The first tile not in its goal location is 9,
so the second component (the Manhattan distance between 9 and 
 its destination) is 5.  The third component (the Manhattan distance
between 9 and the empty square) is 2.
This function essentially tells the problem solver to try  
ordering the tiles row by row.\footnote{Table \ref{tbl:puzzle-parameters} 
specifies the exact definition of this
function for the general \NN\ case.}  This heuristic encodes
 subgoaling of puzzle problems which is quite
natural, and is immediately
inferred by most people trying to solve the sliding-tile puzzle.
However, many people have difficulties solving the puzzle 
even after inferring this heuristic.  We will also report
results for other heuristic functions such as the sum of Manhattan distances.


We begin by describing the experimental methodology used, and continue
with a description of the experiments performed.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Methodology}
\label{sec:methodology}
Most of the experiments described here consist of a learning phase 
and a
testing phase.  The training problems are generated by \ALG.
We let every learning phase  run until \ALG\ reaches quiescence and 
halts. 
Since the training problems are generated by random sequences, we repeat each
learning session 100 times.  We test each resulting macro set by
allowing the problem solver to use the macros for solving a set of 
100 test problems.  A random test-problem is
generated in the same manner as a training problem.  The only
difference is the length of the random sequence of operators applied
to the goal state.  For testing we  used random sequences of
length 1,000,000 to ensure that the problems will be sufficiently
difficult (or sufficiently random). 
For the sliding-tile domains, the {\em test} problems were generated
using a known domain-dependent method for creating random solvable
problems.  The generator continuously creates random permutations of 
the goal state and returns the first even permutation.
The domain-specific method does not harm the generality of \ALG\ since
it is used only by the experimenter.  This method allows us to
compare 
the results obtained by \ALG\ to the results obtained by other researchers.
When in testing mode, we allow \ALG\ to escape from local minima but 
we do not allow it to acquire new macros (see the SolveProblem 
procedure in Figure \ref{fig:algorithm}).  
For all the experiments described in 
this paper, \ALG\ was able to solve all the problems 
while in testing mode; therefore, no special handling of ``censored
data'' \cite{Etzioni:94:SMA,Segre:1991:CLE} was necessary.  
Recall that the quiescence test lets \ALG\ stop only after it is 
able to solve 50 problems without getting stuck in any local minima.  This 
significantly reduces 
the likelihood that it will  encounter a local minimum after 
learning.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Dependent Variables}
We measure three aspects of the learning process:  the resources consumed
during learning, the characteristics of the resulting macro set and
its utility:
\begin{itemize}
\item{\em Learning resources:} The resources consumed
during the learning process until the learning system decides that
it has learned enough. Note that the quiescence parameter significantly 
affects the 
learning resources.  A higher value for this parameter
increases resource consumption, but also decreases the
likelihood that the problem solver will encounter a local minimum
during testing.
\begin{itemize}
\item{\em Training problems:} The total number of problems solved
during training.  The problem with this dependent 
variable is that it ignores the time invested in the search and the time 
invested in generating training problems.
\item{\em Operator applications:} Since the basic operation that is 
used both in search and in problem generation is the application of a basic
operator to a state, we use the total number of operator applications 
 as the principle measurement for the learning 
resources consumed.
\end{itemize}
\item {\em Macro-set statistics:} Statistics about the characteristics
of the generated macro set.
\begin{itemize}
\item {\em Total number:}  The total number of macros acquired
during the learning session.
\item {\em Mean Length:}  The average length of a macro.
\item {\em Max length:} The maximum length of a macro.  This variable
approximates the maximum {\em radius}.
\end{itemize}
\item {\em The utility of the acquired macros:}
According to Equation~\ref{eqn:utility}, the utility of the acquired
macros depends on the cost of the search when using them.  Therefore, 
our principle dependent variable should measure problem-solving speed.
\begin{itemize}
\item {\em CPU time:}   The most 
	obvious candidate for measuring problem-solving speed is 
        CPU time spent 
	during search.  However, such a measurement is overly affected by 
	irrelevant factors such as hardware\footnote{For example, all
the CPU time figures reported here were achieved running a
 Common Lisp program on an outdated Sun.  
Recent experiments on an UltraSparc yield times which are
about 4.4 times faster than those reported here.}, software and 
        programming quality.
\item{\em Expanded nodes:} The number of nodes expanded during the
search.  This is a common method for measuring search speed.
 Nevertheless, this measurement may be misleading 
	in the context of macro-learning, since the branching factor 
        increases when acquiring macros.
\item{\em Generated nodes:} The number of nodes generated during
search.  This measurement takes into account the increased branching
factor, but it does not account for the higher cost of generating a
node by a macro due to the application of several basic operators.
\item{\em Operator applications:} The number of applications of a basic operator
        to a state.  Note that we count every application,
        including those which are part of macro-operators and 
those which fail.  This is the principle dependent
variable, as it represents most accurately the problem-solving speed.
\item {\em Solution quality:}  Macro-learning is not a suitable  
	technique when the macros are used by an optimizing search 
	procedure \cite{Markovitch:1992:SEDa}.
	We are still interested, however, in the quality of the solution
        obtained.  We measure the quality of the solution by its
        length in basic operators.
\end{itemize}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Independent Variables}
\label{sec:independent}
There are many independent variables that affect the performance of
the learning system.  For the experiments described here we look at
the following variables:
\begin{itemize}
\item {\em Selection method:}  
\begin{itemize}
\item {\em Minimum-to-better}: The main selection method defined by
Equation~\ref{eqn:minimum-to-better-filter}.
\item {\em Minimum-to-minimum}: Our implementation of \MACLEARN's
selection method.
\item {\em Any-to-better}: Our implementation of \MORRIS's
selection method.
\end{itemize}
\item {\em Heuristic function:}  
\begin{itemize}
\item {\em \RR}:  The heuristic function described above.
\item {\em Row-by-row-2} : The \RR\ heuristic without the third
component.
%\item {\em Row-by-row-1} : The row-by-row heuristic without the second
%and the third component.  Thus, it only counts the number of tiles
%placed in the row-by-row order.
\item {\em Reduction} : A variation of the \RR\ heuristic
that leads
to placing of tiles in the first row, then the last column, then the 
second
row, then the second to last column etc. This heuristic was 
suggested by Korf \citeyear{Korf:1990:RTS}.
\item {\em Spiral}:  A variation of the \RR\ heuristic
that leads
to placing the tiles in a spiral order from outside in.
\item {\em Sum-of-Manhattan-distances} : The sum of the Manhattan 
distances between each tile and its destination (will be denoted by
\MD).
\end{itemize}
\item {\em Domain:}  Most of the experiments described here were 
performed in
the 15-puzzle domain.  However, we have tried \ALG\ in several
other domains.  In all the domains, the initial states are generated
using the domain-independent training-problem generator which 
applies a random sequence of operators to the goal state. 
\begin{itemize}
\item {\em 24-puzzle:} $5 \times 5$ sliding tile puzzle.
\item {\em 10-cannibals:} The cannibals and missionaries problem
\cite{Nilsson:1980:PAI}.  To make
it non-trivial, we use 10 cannibals and 10 missionaries
instead of the usual 3 and 3.  10 cannibals and 10 missionaries
are situated on the two banks of a river.  They 
must all be moved onto one target bank.  They can use
a boat which can ship one or two persons.  The cannibals should never 
outnumber the missionaries on either bank.   The heuristic function
used is the number of persons that are not yet located on the target bank.
\item {\em 10-stones:} A puzzle that appeared in Nilsson's book
 \citeyear{Nilsson:1980:PAI}.
\def\b5#1{\framebox[5mm]{\rule[0mm]{0cm}{8pt}#1}}
Instead of using 3 black stones and 3 white stones we use 5 black
stones and 5 white stones.  The goal configuration is 
\b5{W}\b5{W}\b5{W}\b5{W}\b5{W}\b5{B}\b5{B}\b5{B}\b5{B}\b5{B}\b5{}.
A stone may move into an adjacent empty cell or may hop over one or
two other stones into an empty cell.  
The heuristic function used is
the number of stones not yet in their goal position. 
\item {\em 5-Hanoi:} The Towers of Hanoi problem with 5 rings
in increasing sizes.  There
are 3 pegs and 5 rings.  The goal position has the 5 rings placed
on the left peg.  A ring may be moved to the top of another peg provided that
it is not placed on a smaller ring as a result.  The heuristic function used is
the number of rings not yet placed on their target peg.
\item {\em Grid:} A grid of $50 \times 50$ with random parallel walls
inserted to make the Manh\-attan-distance heuristic inaccurate.
There are four basic operators (North, South, West and East).  A goal
state can be any location on the grid.  The objective is to find a
path from the initial location to the goal location.  Figure
\ref{fig:grid} shows the grid used.
\end{itemize}
The emphasis of this paper is on building a general learning algorithm
that is able to solve the \NN\ puzzle problem.  The goal of testing 
the algorithm on these other domains was to show that the learning
algorithm is indeed general and does not include domain-specific 
procedures.
\end{itemize}

\begin{figure}
\begin{center}
\psfig{figure=pictures/grid.eps,width=2in}
\end{center}
\caption{\label{fig:grid} The grid domain}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Learning to Solve Problems in the 
15-puzzle Domain}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{\bf Learning Resources} & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
& Mean   & Std.  & Mean & Std. & Mean & Std. \\
\cline{2-7}
& 498,172 & {\STD 74,047} & 735 & {\STD 218} & 60 & {\STD 4.2} \\
\hline
{\bf Generated Macros} & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
& Mean   & Std.  & Mean & Std. & Mean & Std. \\
\cline{2-7}
& 14.16 & {\STD 0.74} & 8.38 & {\STD 0.2} & 18 & {\STD 0.0} \\
\hline
\end{tabular}
\caption{\label{table:fifteen-learning} \small  The upper part of the table 
shows the learning resources consumed while learning macros in the 
15-puzzle
domain.  The results are averaged over 100 learning sessions.
The lower part of the table lists the statistics of the generated
macro sets (averaged over the 100 databases). }
\end{center}
\end{table}

The basic experiment tests the ability of \ALG\ 
to learn the 15-puzzle domain.  Table
\ref{table:fifteen-learning}
 shows the 
learning
resources and the macro statistics
averaged over the 100 learning sessions.  
We also tested
the utility of the learned knowledge by comparing the performance of 
the problem solver that uses the learned macros to the 
following problem solvers:
\begin{enumerate}
\item \ALG\ without the learned knowledge and with learning turned 
off.
\item Best-first search\footnote{Best-first search has several meanings in the AI 
literature.  Here we mean a heuristic search method that keeps the 
whole front of the search, expands the node with the best heuristic 
value and replaces it with its children.  When two nodes have
equivalent heuristic value, the one with the shorter distance from the
initial state is prefered. }
using the \MD\ heuristic.
\item Best-first search
 using the \RR\ heuristic.
\item Weighted-A* with the \MD\ heuristic. 
 We selected a node evaluation function
$f(n)=(1-w)g(n)+wh(n)$ with $w=0.75$, which was reported by Korf
\citeyear{Korf:1993:LSB}
as the best weight for the 15-puzzle domain (Korf uses the
equivalent notation $f(n)= g(n)+Wh(n)$ with W=3).
\item IDA* with the \MD\ heuristic.  Since we used
random problems generated using the same method as Korf, we used the
results reported in \cite{Korf:1993:LSB}. The number 
of operator applications for Korf's data was estimated based on the 
ratio between generated nodes and operator applications in our run of 
best-first search.
\end{enumerate}
Table \ref{table:utility} shows the results of this experiment.
The results are averaged over the 100 
problems in the test set.  The results for \ALG\ after learning are 
also averaged over the 100 learning sessions.  

\begin{table}[ht]
{\small
\begin{center}
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|l|*{10}{r|}}
\hline
 &  
\multicolumn{2}{c|}{Operator} & 
\multicolumn{2}{c|}{Generated} & 
\multicolumn{2}{c|}{Expanded} & 
\multicolumn{2}{c|}{CPU}  & 
\multicolumn{2}{c|}{Solution} \\
 Search&
\multicolumn{2}{c|}{applications} & 
\multicolumn{2}{c|}{nodes} & 
\multicolumn{2}{c|}{nodes} & 
\multicolumn{2}{c|}{seconds}  & 
\multicolumn{2}{c|}{length} \\
\cline{2-11}
 method & Mean   & Std.  & Mean & Std. & Mean & Std.  & 
Mean & Std. & Mean & Std. \\
\hline
{\small \ALG}  & 
221,552 & {\STD 51,188} &
181,422   & {\STD 45,044}&
55,372.9 & {\STD 12,794.0} &
618.92 & {\STD 137.75} &
141.0 & {\STD 26.40} \\
{\small (before learning)}&&&&&&&&&&\\
\hline
{\small \ALG} & 
 688 & {\STD 21} & 
196  & 4 &
47.4 & {\STD 1.3} &
0.30 & {\STD 0.01} & 
149.5 & {\STD 0.19}\\
{\small (after learning)} &&&&&&&&&&\\
\hline
Best first &
 13,320 & {\STD 8,686} & 
6,868 & {\STD 4,500} & 
3,330.5 & {\STD 2,171.6} &
53.95 & {\STD 39.81} & 
145.8 & {\STD 35.48} \\
{\small (\MD)} &&&&&&&&&&\\
\hline
Best first &
 $>$192,811 & {\STD 26,365} & 
$>$98,101 & {\STD 13,294} & 
$>$48,203 & {\STD 6591.4} &
$>$5920 & {\STD 11,989} & 
 &  \\
{\small (\RR)} &&&&&&&&&&\\
\hline
WA* & 40,385 & {\STD 44,396} & 20,181 & {\STD 21,917} & 10,096 & {\STD
11099.0} & 439.28 & {\STD 1206.00} & 74.2 & {\STD 12.64}\\
{\small W=3} &&&&&&&&&&\\
\hline
IDA* & 704,067,291 & & 363,028,090 & &  & & & & 53.0 & \\
{\small Korf \citeyear{Korf:1993:LSB}} &&&&&&&&&&\\
\hline
\end{tabular}
\caption{\label{table:utility} \small The utility of the learned 
macros.  
The resources 
required for solving the testing set compared with various
non-learning problem solvers.  The results are averaged over the 100 
problems in the test set.  The results for \ALG\ after learning are 
also averaged over the 100 learning sessions.}
\end{center}
}
\end{table}

\ALG, after learning, solves problems much faster than the other 
algorithms.  It uses 19 times fewer operator applications 
 than best-first search using the \MD\ heuristic,
 with solutions of 
comparable length.  If we compare the CPU time of best-first search to that 
of \ALG\ we can see that \ALG\ is more than 100 times faster than 
best-first search.   This is because best-first search has an  
 overhead per generated node which is much higher than
\ALG's.\footnote{ 
We used a fast implementation of best-first search with 
efficient data structures:  a heap and a hash table for the OPEN list, 
a hash table for the CLOSED list.}
 \ALG\ also has the advantage of a very small standard deviation.
 \ALG\ after learning  is 322 times faster than \ALG\ before learning.
\ALG\ is 59 times faster than WA* with $W=3$, but yields solutions 
that are twice as long.  \ALG\ is more than 1,000,000 times faster 
than IDA* with solutions that are 2.8 times longer (than the optimal 
solutions found by IDA*).

During the testing phase, \ALG\ never encountered local minima.
Thus, according to definition \ref{def:complete}, all the sets
of macros learned by \ALG\ were apparently {\em complete}.
This was also the case with the rest of the experiments
described in this paper.

We have tried using iterative deepening (ID) for escape instead of
ILB.  We used an improved version of ID that tests each new state
against the states along the path to the root to avoid loops.
Table \ref{table:escape-learning} shows the resources consumed during
learning.  Table  \ref{table:escape-macros} shows the statistics of
the macro sets acquired.  As expected, learning with ILB is 
faster than with ID (by a factor of 9), 
but produces macros that are slightly longer (ID
finds the shortest escape routes).

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
Escape method & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
ILB & 498,172 & {\STD 74,047} & 735 & {\STD 218} & 60 & {\STD 4.2} \\
\hline
ID & 4,553,319 & {\STD 767,093} & 2,542 & {\STD 457} & 60 & {\STD
5.4} \\
\hline
\end{tabular}
\caption{\label{table:escape-learning} \small 
The learning resources consumed while learning in the 15-puzzle domain 
using various escape methods. 
 Each number represents the mean over 100 learning 
sessions.
}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
Escape method & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
ILB & 14.16 & {\STD 0.74} & 8.38 & {\STD 0.20} & 18.0 & {\STD 0.0} \\
\hline
ID & 14.39 & {\STD 0.88} & 8.12 &{\STD  0.22} & 17.0 & {\STD 0.0} \\
\hline
\end{tabular}
\caption{\label{table:escape-macros} \small 
The statistics of the macro sets acquired
with various escape methods.  
Each number represents the mean over 100 databases.
}
\end{center}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Effect of the Selection Method on Learning}
\label{sec:exp-selection}
We tested \ALG\ with the minimum-to-minimum and 
any-to-better selection strategies.  The learning resources consumed
are shown in Table~\ref{table:selection-learning}.  The statistics of 
the acquired macro sets
are shown in Table~\ref{table:selection-macros}.  The performance of 
the problem solver using
these macros is shown in Table~\ref{table:selection-utility}.

 
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
Selection method & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
Minimum-to-better & 498,172 & {\STD 74,047} & 735 & {\STD 218} & 60 & {\STD 4.2} \\
\hline
Minimum-to-minimum & 22,211,450 & {\STD 27,096,382} & 5,461 & {\STD 5,298} & 426 & {\STD
434.0} \\
\hline
Any-to-better & 572,622 & {\STD  117,330} & 618  & {\STD 362} & 65 & {\STD
9.3} \\
\hline
\end{tabular}
\caption{\label{table:selection-learning} \small 
The learning resources consumed while learning in the 15-puzzle domain 
using various selection methods. 
 Each number represents the mean over 100 learning 
sessions.
}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
Selection method & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
Minimum-to-better & 14.16 & {\STD 0.74} & 8.38 & {\STD 0.20} & 18.0 & {\STD 0.0} \\
\hline
Minimum-to-minimum & 104.04 & {\STD 98.92} & 109.90 &{\STD  90.38} & 348.4 & {\STD 172.8} \\
\hline
Any-to-better & 42.06 & {\STD 4.43} & 8.20 & {\STD 0.15} & 18.0 & {\STD 0.3} \\
\hline
\end{tabular}
\caption{\label{table:selection-macros} \small 
The statistics of the macro sets acquired
with various selection methods.  
Each number represents the mean over 100 databases.
}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|*{8}{r|}}
\hline
 &  
\multicolumn{2}{c|}{Operator} & 
\multicolumn{2}{c|}{Expanded} & 
\multicolumn{2}{c|}{CPU}  & 
\multicolumn{2}{c|}{Solution} \\
 &
\multicolumn{2}{c|}{applications} & 
\multicolumn{2}{c|}{nodes} & 
\multicolumn{2}{c|}{seconds}  & 
\multicolumn{2}{c|}{length} \\
\cline{2-9}
 Selection & Mean   & Std.  & Mean & Std.  & 
Mean & Std. & Mean & Std. \\
\hline
Minimum-to-better & 
 688 & {\STD 21} & 
 47.4 & {\STD 1.3} &
0.30 & {\STD 0.01} & 
149.5 & {\STD 0.19}\\
\hline
Minimum-to-minimum & 
1281  & {\STD 332} & 
43.5 & {\STD 2.1} &
0.84 & {\STD 0.12} & 
251.5 & {\STD 50.08}\\
\hline
Any-to-better & 
 1396 & {\STD 132} & 
 46.4 & {\STD 0.7} &
0.39 & {\STD 0.03} & 
143.8 & {\STD 3.20}\\
\hline
\end{tabular}
\caption{\label{table:selection-utility} \small The utility of the learned 
macros with various selection methods.  
The results are first averaged over the 100 
problems in the test set and then averaged again
 over the 100 macro sets.}
\end{center}
\end{table}

These results confirm our analysis in the previous section.  The
minimum-to-minimum strategy acquires macros that are unnecessarily
long, causing a large increase in the learning resources required.
Also, because the macros are longer, they are less general and many of
them are acquired before quiescence.
The any-to-better strategy acquires unnecessary macros, which leads
to a larger branching factor and lower utility.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Effect of the 
Heuristic Function on Learning}
\label{sec:exp-heuristic}

The \ALG\ algorithm is based upon the availability of a
``generally good'' heuristic function to start with.  The heuristic
 function
should be able to lead the search program towards the goal, except in 
a
small number of local minima where an exhaustive search and learning 
take
place.  The next experiment tests the effect of the heuristic function
on the performance of \ALG.  We have conducted 100 learning sessions
and testing sessions with each of the heuristic functions described 
in Section
\ref{sec:independent}. 
Tables \ref{table:heuristics-learning}, \ref{table:heuristics-macros}
and \ref{table:heuristics-utility} show the results obtained.  

 
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
Heuristic & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
\RR & 498,172 & {\STD 74,047} & 735 & {\STD 218} & 60 & {\STD 4.2} \\
\hline
Row-by-row-2 & 4,391,468 & {\STD 1,805,776} & 2191 & {\STD 1,181} & 247 & {\STD
62.9} \\
\hline
Reduction & 552,463 & {\STD  128,769} & 878  & {\STD 334} & 63 & {\STD
9.1} \\
\hline
Spiral & 891,728  & {\STD 144,633} & 1,621 & {\STD 47} & 74 & {\STD
15.3} \\
\hline
\MD & 228,487,090 & {\STD  44,106,048} & 98,659 & {\STD 2,341} & 1,917 & {\STD 210.3} \\
\hline
\end{tabular}


\caption{\label{table:heuristics-learning} \small 
The learning resources consumed while learning in the 15-puzzle domain 
using various heuristic 
functions.  Each number represents the mean over 100 learning 
sessions.
}
\end{center}
\end{table}


\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
Heuristic & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
\RR & 14.16 & {\STD 0.74} & 8.38 & {\STD 0.20} & 18.0 & {\STD 0.0} \\
\hline
Row-by-row-2 & 73.44 & {\STD 3.65} & 5.60 &{\STD  0.14} & 27.7 & {\STD 2.1} \\
\hline
Reduction & 16.59 & {\STD 0.76} & 6.08 & {\STD 0.08} & 13.0 & {\STD 0.0} \\
\hline
Spiral & 24.10 & {\STD 1.04} & 6.43 & {\STD 0.09} & 13.0 & {\STD 0.0} \\
\hline
\MD & 730.00 & {\STD  40.09} & 16.37 & {\STD 0.23} & 48.2 & {\STD 1.0} \\
\hline
\end{tabular}

\caption{\label{table:heuristics-macros} \small 
The statistics of the macro sets acquired
with various heuristic 
functions.  Each number represents the mean over 100 databases.
}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|*{8}{r|}}
\hline
 &  
\multicolumn{2}{c|}{Operator} & 
\multicolumn{2}{c|}{Expanded} & 
\multicolumn{2}{c|}{CPU}  & 
\multicolumn{2}{c|}{Solution} \\
 &
\multicolumn{2}{c|}{applications} & 
\multicolumn{2}{c|}{nodes} & 
\multicolumn{2}{c|}{seconds}  & 
\multicolumn{2}{c|}{length} \\
\cline{2-9}
 Heuristic & Mean   & Std.  & Mean & Std.  & 
Mean & Std. & Mean & Std. \\
\hline
\RR & 
 688 & {\STD 21} & 
 47.4 & {\STD 1.3} &
0.30 & {\STD 0.01} & 
149.5 & {\STD 0.19}\\
\hline
Row-by-row-2 & 
 2,827 & {\STD 21} & 
57.24 & {\STD 144.8} &
1.33 & {\STD 3.60} & 
148.2 & {\STD 0.19}\\
\hline
Reduction & 
 738 & {\STD 19} & 
 42.67 & {\STD 0.4} &
0.29 & {\STD 0.01} & 
125.5 & {\STD 1.60}\\
\hline
Spiral & 
 944 & {\STD 34} & 
44.76 & {\STD 0.5} &
0.37 & {\STD 0.02} & 
130.1 & {\STD 5.27}\\
\hline
\MD & 
 11,520 & {\STD 1009} & 
175.00 & {\STD 83.6} &
2.40 & {\STD 0.01} & 
142.0 & {\STD 2.04}\\
\hline
\end{tabular}
\caption{\label{table:heuristics-utility} \small The utility of the learned 
macros with various heuristic functions.  
The resources 
required for solving the testing set compared with various
non-learning problem solvers.  The results are first averaged over the 100 
problems in the test set and then averaged again
 over the 100 macro sets.}
\end{center}
\end{table}
The  row-by-row-2 function is a crippled version of the
\RR\ heuristic.  It is therefore not surprising that the
performance degraded by all measures when using it.  
It is more surprising to note
that the performance also degraded with the powerful
\MD\ heuristic, which, according to Table~\ref{table:utility},
is much better than \RR\ even for satisficing search.
The lower performance is expressed in two main differences:
\begin{enumerate}
\item The learning resources with the \MD\ heuristic 
are 460 times higher
than with the \RR\ heuristic.
\item The utility of the learned macro sets is lower---the number of
operator applications is 16 times higher with the \MD\ heuristic.
\end{enumerate}

To understand the reasons for these differences we can look at 
 the statistics of the acquired macros 
(Table~\ref{table:heuristics-macros}).
The total number of macros acquired with \MD\ is 50 times larger than
the number of macros acquired with \RR.  A larger number of macros
implies a larger branching factor, which explains the lower
efficiency of the problem solver using the \MD\ macros.
The high learning resources can be explained by three factors:
\begin{enumerate}
\item The problem solver is used during training.  Therefore,  lower
efficiency of the problem solver implies slower learning.
\item The larger number of macros indicates a larger number of training
problems before quiescence.  Indeed, with the \MD\ heuristic, \ALG\
solved 30 times more problems during training.
\item The mean length of the macros acquired with the \MD\ heuristic is
twice as large as the mean length of macros acquired with the
\RR\ heuristic.  Even more significant is the difference in the
maximal length of a macro.  With the \MD\ heuristic \ALG\ acquires
macros that are 48 operators long, while the maximal length of a macro
using the \RR\ heuristic is only 18.  This indicates that the
maximal radius of the \MD\ heuristic is much larger than that of
the \RR\ heuristic.  Larger radius implies  more resources invested in
escaping from local minima.
\end{enumerate}

The above explanation is only partially satisfactory, since it does
not tell us the {\em source} of the problem.  To understand why  the
\MD\ heuristic has a large radius, look at the following puzzle:
\[
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
2 & 1 & 3 & 4 & 5  \\
\hline
6 & 7 & 8 & 9 & 10  \\
\hline
11 & 12  & 13 & 14 & 15  \\
\hline
16 & 17 & 18 & 19 & 20  \\
\hline
21 & 22 & 24 & 23 &   \\
\hline
\end{array}
\]
The sum-of-Manhattan distances for this puzzle is only 
 4, yet a very long sequence of
moves is required to reduce the distance.  The larger radius implies
longer (and less general) macros and more resources for the escape
processes. 




\begin{table}[ht]
\begin{center}
{\small 
\begin{tabular}{|cp{2.6cm}c|cp{2.6cm}c|}
\hline
\multicolumn{3}{|c|}{\MD} & \multicolumn{3}{c|}{\RR}\\
\hline
Start & Macro & End & Start & Macro & End \\
\hline
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 2 & 1 & 4 & 8  \\
\hline
13 & 6 & 15 & 12  \\
\hline
5 & 11  & 3 & 10  \\
\hline
9 &  & 7 & 14 \\
\hline
\end{array}
$
&
{\scriptsize r r u u u}
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 2 & 1 & 4 &   \\
\hline
13 & 6 & 15 & 8  \\
\hline
5 & 11  & 3 & 12  \\
\hline
9 & 7 & 14 & 10 \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 &  4 \\
\hline
5 & 6 & 7 & 8  \\
\hline
9 & 13  & 10 &   \\
\hline
11 & 14 & 15 & 12 \\
\hline
\end{array}
$
&
{\scriptsize d l l u r}
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 &  4 \\
\hline
5 & 6 & 7 & 8  \\
\hline
9 & 10  &  & 12  \\
\hline
11 & 13 & 14 & 15 \\
\hline
\end{array}
$
\\
\hline
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
  & 2 & 3 & 4  \\
\hline
5 & 9 & 7 & 8  \\
\hline
1 & 10  & 11 & 12  \\
\hline
13 & 6 & 15 & 14 \\
\hline
\end{array}
$
&
{\scriptsize r d l d r u u l d r d}
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
1  & \makebox[3.4mm]{2} & 3 & 4  \\
\hline
9 & 5 & 7 & 8  \\
\hline
10 &   & 11 & 12  \\
\hline
13 & 6 & 15 & 14 \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 & 12  \\
\hline
8 & 15 &  & 4  \\
\hline
14 & 5  & 13 & 6  \\
\hline
9 & 11 & 7 & 10 \\
\hline
\end{array}
$
&
{\scriptsize l u r r d l u l d}
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 & 4  \\
\hline
8 &   & 12 & 15  \\
\hline
14 & 5  & 13 & 6  \\
\hline
9 & 11 & 7 & 10 \\
\hline
\end{array}
$
\\
\hline
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 &  4 \\
\hline
9 & 6 & 8 & 7  \\
\hline
5 & 10  & 11 & 12  \\
\hline
13 & 14 & 15 &  \\
\hline
\end{array}
$
&
\raisebox{1.0ex}{\parbox{2.5cm}{\scriptsize u l u r d l l l u r r r d d l l u r u l l r d d r r l r u d l l l u r u l d d}}
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 \makebox[3.5mm]{1} & 2 & 3 &  4 \\
\hline
5 & 6 & 7 & 8  \\
\hline
9 & 10  & 11 & 12  \\
\hline
& 13 & 14 & 15   \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 &  4 \\
\hline
5 & 6 & 7 & 8  \\
\hline
9 & 10  & 11 & 12  \\
\hline
14 & 15 & 13 &    \\
\hline
\end{array}
$
&
{\scriptsize u l d l l u r d r u l l d r r u r d}
&
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{4}{|c}|}
\hline
 1 & 2 & 3 &  4 \\
\hline
5 & 6 & 7 & 8  \\
\hline
9 & 10  & 11 & 12  \\
\hline
15 & 13 & 14 &    \\
\hline
\end{array}
$
\\
\hline
\end{tabular}
}
\end{center}
\caption{\label{table:coverage-examples}
\small Examples for macros acquired with the \RR\ and the
\MD\ heuristics. Each example shows the state where the macro was
acquired, the macro itself, and the state after the application of 
the acquired macro.}
\end{table}

It is more difficult to explain the larger number of macros.  A larger
number of macros means that during training \ALG\ encounters many
states where none of the previously learned macros is useful, and new
macros are acquired.  This implies that
 the likelihood of a macro acquired with \MD\ to be useful in
a state is much lower than that of a macro acquired with \RR.
One reason for this difference is the longer macros acquired with \MD.
As we stated before, longer macros tend to be less general.
There are, however, other reasons which are best understood 
by examples.
Table~\ref{table:coverage-examples}  shows three macros acquired with
each of the two heuristics, along with the states before and after the
macro acquisition.


The \MD\ macro at the first line, $rruuu$, is applicable only in
states where the empty tile is in the last row at one of the two leftmost
locations.  Five tiles are moved and the Manhattan distance of each is
either increased or decreased by one.  The macro is useful only
in states where the distance of at least three of the tiles is
decreased.  Compare this to the equally long \RR\ macro $dllur$.
It is applicable in states where the empty tile is in one of 6
locations (last two columns and last three rows), and is therefore
much more likely to be applicable than the \MD\ macro.  It is useful
in states where the blank is to the right of the next tile to be moved
and the direction of the movement is to the left.  Since the \RR\
heuristic imposes a particular order on the placement of tiles, {\em
any} attempt to solve a problem will get to a state where, for
example,
 the first 9
tiles are in place and tile 10 should be placed next.  At a
certain point tile 10 will be at distance 1 from its target location,
 either below the target location or to the right of  it.  
In all the states where the tile is to the right of its target
location, and the blank tile is to its right, the macro $dllur$ will
be useful.  Thus, this macro has high likelihood of being useful.

The \MD\ macro in the second line is, again, useful for a very
particular situation.  The \RR\ macro, however, is useful for at least
half of the problems.  While solving a problem with \RR\ there must
be a situation where the first 3 tiles are in their target location
and the fourth tile is at distance one from its target.  If the blank is
to its left, then the macro is useful.
The \MD\ macro in the last row of the table is the most extreme case
of low usefulness.  It is useful only if the tiles are placed in a
particular order, with the tiles in the 
first, third and fourth row  placed before the tiles in the second
row.  Contrast this macro with the longest \RR\ macro shown to its
right.  This macro is useful for most problems since there will always be
a situation where the first three rows are ordered and  tile 13
should be moved towards its goal.

To conclude, the difference between \RR\ and \MD\ that makes the \RR\
macros more useful is the restriction that  \RR\ puts on the order
of solving subproblems.  This strict order makes the problem solver go
through similar states regardless of the initial state.
The freedom given by \MD\ allows the problem solver pick any of the
$N^2!$ possible orders for tile placement.  Furthermore, it allows
macros that move tiles away from their target location, provided that
other tiles are moved towards their target.  Such macros are useful
only in very particular states. 

The {\em particular} order used by \RR\ reduces the maximal radius by
making it possible to place tiles without the need to (even
temporarily) displace too many already-placed tiles.  The other two
heuristics, Reduction and Spiral, also have this property.  Consider,
however, a  heuristic similar to \RR\ where the tiles are placed
in order from tile 2 to tile 15 after which tile 1 is placed.  Such a
placement order increases the maximal radius significantly.
In Section \ref{sec:discussion} we discuss the differences between the
two heuristics when used for the \NN\ puzzle domain.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\subsection{Learning Macros in Other Domains}

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
Domain & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
24-puzzle & 859,497  & {\STD 186,823} & 4842.0 & {\STD 2270.0} & 62.8 & {\STD 7.2} \\
\hline
10-Cannibals & 216,572 & {\STD 88,467} & 14.2 & {\STD 6.0} & 63.9 & {\STD 12.0} \\
\hline
10-Stones & 144,303 & {\STD 1,653} & 8.4 & {\STD 1.9} & 52.0 & {\STD 0.3} \\
\hline
5-Hanoi & 377,671 & {\STD 80,968} & 35.2 & {\STD 3.5} & 76.2 & {\STD 9.5} \\
\hline
Grid & 1,956,972 & {\STD 1,191,383} & 58.8 & {\STD 35.0} & 185.0 & {\STD 60.2} \\
\hline
\end{tabular}
\caption{\label{table:domains-learning-resources}
\small The  resources  consumed while learning in various
domains.  Each number represents the mean over 100 learning sessions.
}
\end{center}
\end{table}


\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
Domain & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
24-puzzle & 15.32  & {\STD 0.79} & 8.68 & {\STD 0.24} & 18.00 & {\STD 0.0} \\
\hline
10-cannibals & 2.16 & {\STD 0.39} & 2.93 & {\STD 0.15} & 3.98 & {\STD 0.2} \\
\hline
10-stones & 1.20 & {\STD 0.40} & 2.00 & {\STD 0.00} & 2.00 & {\STD 0.0} \\
\hline
5-Hanoi & 11.47 & {\STD 0.71} & 7.24 & {\STD 0.25} & 16.00 & {\STD 0.0} \\
\hline
Grid & 17.50 & {\STD 3.14} & 8.62 & {\STD 0.82} & 16.36 & {\STD 1.5} \\
\hline
\end{tabular}
\caption{\label{table:domains-macros}
\small Statistics of the macro sets generated in various
domains.  Each number represents the mean over 100 sets.
}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
 & 
\multicolumn{2}{c|}{Before learning} & \multicolumn{2}{c|}{After learning}\\
\cline{2-5}
Domain & Mean   & Std.  & Mean & Std. \\
\hline
24-puzzle & 711,545 & {\STD 134,807.0} & 1540.0 & {\STD 57.5}  \\
\hline
10-cannibals & 57 & {\STD 40.5} & 31.6 & {\STD 0.4}  \\
\hline
10-stones & 206 & {\STD 84.8} & 126.6 & {\STD 8.1}  \\
\hline
5-Hanoi & 10,993 & {\STD 14,623.3} & 156.0 & {\STD 9.4}  \\
\hline
Grid & 1,529 & {\STD 1313} & 369.0 & {\STD 35.0}  \\
\hline
\end{tabular}
\caption{\label{table:domains-utility}
\small The performance of \ALG\ (in operator applications)
before and after learning in various domains.
}
\end{center}
\end{table}



We have applied \ALG\ to the other domains specified in Section 
\ref{sec:methodology}.
Tables \ref{table:domains-learning-resources}, 
\ref{table:domains-macros} and \ref{table:domains-utility}
show the mean results for 100 learning 
sessions.
\ALG\ was able to reach quiescence in all the domains. The 10-stones
and 10-cannibals domains are very simple.  One or two macros were
sufficient to reach quiescence.  Note that we used the same
quiescence parameter, 50 problems, for all the domains.
After solving each problem,
\ALG\ increases  by 100 the length of the random sequence
used for generating a training problem.
Therefore, \ALG\ spends 125,000 operator applications
just to make sure that there is nothing new to learn.
In the simple domains, this amounts to most of the resources 
used by \ALG.

It is interesting to look at the macros learned in the grid domain.
Most of the macros have a structure of ${\scriptstyle SSS \ldots S W 
N \ldots NNN}$,
where $S$ stands for south, $W$ for west, $N$ for north,
and $S$ and $N$ are equal in number.  Such macros are used to make
detours around walls that block the search.  
 
\ALG\ was able to improve the performance of problem solving
in each of the domains.  The most notable improvement is
in the 24-puzzle domain where the performance after learning 
is 462 times better than the performance before learning.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Solving the General \NN\ Puzzle}
\label{sec:scalable}
Some domains can be scaled up or down by adjusting a certain 
parameter,
such that the same operators are applicable in the scaled domain
(perhaps by using the parameter in their definition).
For example, we can define a family of domains called the \NN\ puzzle,
where each $N$ defines a different puzzle domain. When $N=3$ we get 
the
 8-puzzle domain, when $N=4$ we get the 15-puzzle domain, 
etc.
All the domains in this family use the same operators: {\em Up}, {\em 
Down}, 
{\em Left} and {\em Right}. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Using \ALG\ in Scalable Domains}


In the previous section we showed how \ALG\ can be used
to efficiently solve problems in the 15-puzzle and 
the 24-puzzle domains.  Is it possible
to use \ALG\ to efficiently solve  general \NN\ sliding-tile puzzle
problems?
We have developed a learning algorithm called \PARALG\ 
that uses \ALG\ in scalable domains.  
The original \ALG\ gets a set of basic operators and a well-behaved
heuristic function.  \PARALG\ gets in addition the name of the domain
parameter and an initial value for it.  The basic operators and the
heuristic function can use the domain parameter in their definition.
The algorithm
sets the parameter to its initial value and calls \ALG.
When \ALG\ returns (due to quiescence), the parameter is increased
and \ALG\ is called again.  The algorithm stops when no new
macros are added.  The  algorithm is shown
in Figure \ref{fig:par-algorithm}.

\begin{figure}[htb]
\begin{center}
\fbox{
\begin{minipage}{8cm}
\begin{tabbing}
\TABLINE{0.5cm}
procedure \PARALG(BasicOps,h,InitialParameterValue)\\
\>  Macros $\leftarrow \{  \}$\\
\>  DomainParameter $\gets$ InitialParameterValue\\
\>  Loop\\
\>  \>  MacrosBefore $\gets$ Macros \\
\>  \>  Macros $\gets$ \ALG(BasicOps,h)\\
 \`; BasicOps and h can use DomainParemeter in their definition \\
\>  \>  DomainParameter $\gets$ DomainParameter + 1\\
\>  Until MacrosBefore = Macros\\
\>  Return Macros
\end{tabbing}
\end{minipage}
}
\end{center}
\caption{\label{fig:par-algorithm}
\small
The \PARALG\ algorithm}
\end{figure}

The idea behind this algorithm is to extend the 
strategy of generating training problems of increasing difficulty.
\ALG\ increases the length of the random sequences to generate
more complex problems, while \PARALG\ also increases the domain
parameter.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimenting with \PARALG\ in the \NN\ Puzzle Domains}

We have experimented with the \PARALG\ algorithm in the \NN\ puzzle
domains using the above specifications.
The resulting macro sets
were tested on random $10 \times 10$ puzzles. 

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{\bf Learning Resources} & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
& Mean   & Std.  & Mean & Std. & Mean & Std. \\
\cline{2-7}
& 1084571 & {\STD 126338} & 270.7  & {\STD 62.7} & 232.8 & {\STD 13} \\
\hline
{\bf Generated Macros} & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
& Mean   & Std.  & Mean & Std. & Mean & Std. \\
\cline{2-7}
& 14.87 & {\STD 0.83} & 8.82 & {\STD 0.23} & 18 & {\STD 0} \\
\hline
{\bf Performance} & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Solution Length}\\
\cline{2-7}
& Mean   & Std.  & Mean & Std. & Mean & Std. \\
\cline{2-7}
& 15891 & {\STD 1020} & 15.64 & {\STD 0.85} & 3028 & {\STD 268} \\
\hline
\end{tabular}
\caption{\label{table:n-puzzle} \small  The upper part of the table 
lists the learning resources consumed by learning macros in the 
\NN\ puzzle
domain.  The middle part of the table contains
 the statistics of the generated
macro sets.  The lower part shows the performance of \ALG\ while using
the macros to solve 100 random $10 \times 10$ puzzle problems.
 All the reported data is averaged over 100 learning sessions. }
\end{center}
\end{table}
 
Table \ref{table:n-puzzle}
shows the summary of 100 learning sessions.   \ALG\ learned most
of its macros by solving $3 \times 3$ and $4 \times 4$ puzzles.  It 
typically
learned one or two macros while solving $5 \times 5$ puzzles, 
and reached quiescence while solving $6 \times 6$ problems without
learning any new macros.  Note that on average at least 85\% 
of the training problems 
and at least half of the learning time (operator applications)
were used just for testing quiescence.  Although \PARALG\
solved 232 training problems on average compared with an average of 60
problems solved by \ALG\ in the 15-puzzle domain, the total learning CPU time
is almost 3 times shorter than the time spent for learning the
15-puzzle.  
This is an indication that the method of solving problems in
increasing level of difficulty indeed saves learning resources.
\PARALG\ was able to learn part of the macros while solving $3 \times
3$ puzzles, thus saving time by escaping local minima in a domain with
a lower complexity.




A second test was performed with one of the macro sets (we 
arbitrarily 
selected the one
that was learned first).
We generated sets of $10$ random testing problems for various sizes
up to $50 \times 50$ and solved these problems using the macro set.
The random problems were generated, as in the previous section, by
even random permutations.
\begin{figure}[htb]
\twofig{plots/exp4-generated-20.eps}{plots/exp4-generated.eps}
\caption{\label{fig:n-puzzle-ops}
\small Testing the macros learned by \PARALG\ on large puzzles.
The graphs show mean number of operator applications as a 
function of the puzzle 
size.
The error bars are one standard deviation away on either side
of the mean.  
  (a)  Results for sizes up to 20. (b)   Results up to size 50.
}
\end{figure}
Figure \ref{fig:n-puzzle-ops} shows the mean number of operator 
applications 
as a function of the puzzle size. 
\ALG\ solved the whole test set in a reasonable time.
It looks as if the program can now efficiently 
solve any \NN\ solvable problem.
We have indeed succeeded in proving that the set of macros learned is
{\em complete} and that \ALG\ can solve any solvable problem in
$O(N^3)$ with a reasonable constant (288).  The proof is given in the 
appendix.  This proof is supported by our empirical testing.  \ALG\ 
never resorted to the escape procedure throughout the whole testing 
phase.
The proof is for a specific macro set, but can be repeated for 
the other macro sets as well.  A variation of that proof shows that
\ALG\ can solve any solvable problem in
$O(N^3)$ even without learning.  However, the constant
in this upper limit is prohibitively high ($10^{12}$).
We do not claim that \ALG\ will always
perform successful learning.  It is possible that \ALG\ will
reach  quiescence and quit
learning, having missed essential macros.  
The probability of such an event, however, diminishes with an increase in 
the size of the quiescence parameter.  

Note that both the empirical results and the formal proof show that
the maximal radius of any puzzle problem, regardless of the puzzle
size, with respect to the \RR\ heuristic, is bounded by 18. 
This bounded-radius property is a necessary condition for \ALG\ to
scale up its acquired macros for domains with a larger parameter. 
It can be easily shown that the \MD\ heuristic
does not have such a  property.  


%We have plotted a curve fit of degree 3 to illustrate that
%point. . 
                                                 
\begin{figure}[htb]
\twofig{plots/exp4-length.eps}{plots/exp4-ratio.eps}
\caption{\label{fig:n-puzzle-length}
\small 
(a)  The solution length (in basic moves) 
as a function of the puzzle size.
 (b)  The ratio 
between the solution length and
the heuristic lower-bound on the shortest solution 
as a function of the puzzle size. 
In both graphs the error bars 
are one standard deviation 
away on either side
of the mean.
}
\end{figure}

Figure \ref{fig:n-puzzle-length}(a) shows
the mean solution length as a function of the puzzle
size.   Figure \ref{fig:n-puzzle-length}(b)
shows the upper bound
on the ratio
of the solution length to the optimal solution length 
as a function of the puzzle size
(the solution length divided by the 
sum-of-Manhattan-distances).
It is interesting to note that the graph is flattened at a value
of 5.  
Ratner and Warmuth \citeyear{Ratner:1986:FSS,Ratner:1990:NPR} 
sketch a (quite 
complicated)
hand-crafted approximation algorithm for the \NN\ puzzle.  In their
earlier paper they give a constant factor of 22 to the approximation.
Looking
at Figure \ref{fig:n-puzzle-length}, it is quite possible 
that \ALG\ could have found
such an algorithm by itself.  The constant factor of \ALG\ seems to be
close to 5, but it is measured with respect to {\em random} problems,
while Ratner and Warmuth's constant is a worst-case upper bound.
In the appendix, we prove
that the length of the
solutions found by \ALG\ for \NN\ puzzle problems is $O(N^3)$ with a
constant of 50 (which is substantially worse than  Ratner and Warmuth's).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimenting with \PARALG\ in Other Scalable Domains}

We tested \PARALG\ in other parameterized domains.  In
the N-Cannibals and N-Stones domains, \PARALG\ learned all the macros
with the minimal value of the parameter (3).
The test was performed using problems with a parameter of 20 in both 
domains.
\ALG's performance indeed improved in both domains and 
problem solving proceeded without encountering local minima.

The N-Hanoi domain family is recursive in nature and we did not expect
\ALG\ to find a complete macro set for these domains.  
The length of the macros
should grow with the number of rings; therefore,
 \ALG\ should not reach quiescence in these domains.  
We were surprised to find that
\PARALG\  achieved quiescence after solving problems of 7 or
8 rings (7.13 on average).  This error was caused by
the domain-independent training-problems generator.  The probability
that the largest ring will be moved from its target location
after a random sequence of moves is very low.  Indeed,
when we increased the length of the sequences used
for generating training problems and increased the 
quiescence parameter, learning continued, but \ALG\ still
reached quiescence after solving problems with 
9 rings.
In both cases, the macros learned were not sufficient for
solving problems with a  parameter that is larger than the
values encountered during training.  The test was performed
with problems of 6 rings.
For solving domain families such as  N-Hanoi,
we should extend \ALG\ and endow it with the capability
of generating recursive macros.  To avoid the problem
of \PARALG\ quitting prematurely, we can modify the 
problem generator of \ALG\ to use random sequences with
lengths that are based on the domain parameter.  Alternatively, we can
use domain-specific problem generators.
The results of this experiment are summarized in Tables
\ref{table:n-domains-learning-resources}, \ref{table:n-domains-macros} and
\ref{table:n-domains-utility}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Operator applications} & 
\multicolumn{2}{c|}{CPU seconds} & \multicolumn{2}{c|}{Problems}\\
\cline{2-7}
Domain & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
N-Cannibals & 331,183 & {\STD 59723} & 20.84 & {\STD 3.8} & 112 & {\STD 8.5} \\
\hline
N-Stones & 277,852 & {\STD 3384} & 11.53 & {\STD 2.7} & 1030 & {\STD 0.6} \\
\hline
N-Hanoi & 2,427,186 & {\STD 508,093} & 579.00 & {\STD 176.0} & 370 & {\STD 43.7} \\
\hline
\end{tabular}
\caption{\label{table:n-domains-learning-resources}
\small Summary of the  learning resources  consumed in various
domains.  Each number represents the mean over 100 learning sessions.
}
\end{center}
\end{table}


\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
 & \multicolumn{2}{c|}{Total number} & 
\multicolumn{2}{c|}{Mean Length} & \multicolumn{2}{c|}{Max Length}\\
\cline{2-7}
Domain & Mean   & Std.  & Mean & Std. & Mean & Std. \\
\hline
N-Cannibals & 4.40 & {\STD 0.5} & 2.4 & {\STD 0.05} & 4.0 & {\STD 0.0} \\
\hline
N-Stones & 1.22 & {\STD 0.4} & 2.0 & {\STD 0.00} & 2.0 & {\STD 0.0} \\
\hline
N-Hanoi & 16.08 & {\STD 0.9} & 12.5 & {\STD 1.24} & 33.2 & {\STD 6.6} \\
\hline
\end{tabular}
\caption{\label{table:n-domains-macros}
\small Statistics of the macro sets generated in various
domains.  Each number represents the mean over 100 sets.
}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
 & 
\multicolumn{2}{c|}{Before learning} & \multicolumn{2}{c|}{After learning}\\
\cline{2-5}
Domain & Mean   & Std.  & Mean & Std. \\
\hline
N-Cannibals & 150 & {\STD 85} & 105 & {\STD 10}  \\
\hline
N-Stones & 3,671 & {\STD 605} & 2,009 & {\STD 155}  \\
\hline
N-Hanoi & 171,956 & {\STD 168,338} & 2,913 & {\STD 16,530}  \\
\hline
\end{tabular}
\caption{\label{table:n-domains-utility}
\small The performance of \ALG\ before and after learning in various domains.
}
\end{center}
\end{table}



Another related experiment involved
transfer of knowledge between two similar domains (but not
parameterized as the domains above).  We generated a random
grid, different from the one used for the experiments above,
and performed a testing session with \ALG,
using macros that were learned in the first grid.
Using the macros
improved \ALG's performance---from 1529 operator applications
without macros down to 594 with macros.  This ability
of transferring skill from one grid to another arises from the similar shape
of obstacles.  A macro such as {\sc SSSSSWNNNNN} can be helpful in getting
around walls of various sizes in the original grid used for learning
and in the 
grid used for testing.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\section{Discussion}
\label{sec:discussion}

Despite its simplicity, the \ALG\ algorithm presented in this paper
was able to learn macros that
allow an efficient solution of any solvable
\NN\ puzzle problem.  It also performed well
in a number of other domains.
In this section, we  compare
\ALG\ to other macro-learning algorithms and 
discuss its strengths and weaknesses.

Most of the existing macro-learning programs are based on
the notion of subgoaling: the learner tries to
acquire macros that achieve some subgoal without
undoing previously satisfied subgoals 
\cite{Korf:1985:LSPb,Laird:1986:CSA,Ruby:1989:LSS,Ruby:1992:EISa,Tadepalli:1991:FEB,Tadepalli:1996:FFS}.  
\ALG, like \MACLEARN\ \cite{Iba:1985:LDM}, 
does not assume  subgoaling, but assumes the existence of
a heuristic function.  EASe \cite{Ruby:1992:EISa} combines subgoaling
with a heuristic function to guide the search for the current
subgoal.
The subgoal-oriented macro-learners use various methods
to guard the previously achieved subgoals. 
\ALG\ is much simpler, requiring only that the macro acquired lead 
from
a local minimum to a state with a better heuristic value.
It is possible to implicitly enforce subgoaling by using
an appropriate evaluation function.  For example, the \RR\
heuristic used for the \NN\ puzzle domain encodes a subgoal-oriented
strategy for solving puzzle problems.
 However, the algorithm works
even in domains where such natural subgoaling is not evident.
For example, in the grid domain, the local minima are located
behind obstacles---the search procedure cannot move forward
and all other directions increase the Manhattan distance from the goal
location.  \ALG\ acquires macros that allow a detour around the
obstacles.  Such local minima cannot be called subgoals since
we would prefer to avoid them.  However, once the search program
is trapped in  those minima, it can use the macros
to escape from them.  

While \ALG\ and \MACLEARN\ are similar in their use of the heuristic
function as a guide to the macro learner, they are different
in several other aspects.  
\MACLEARN\ uses best-first search as its
training and testing problem solver.  \ALG\
uses hill-climbing (with
an escape procedure).  This difference is significant since
the increased branching factor resulting from the macros
is extremely  harmful in best-first search but 
adds only to the constant in hill-climbing search (provided that
the hill-climbing search does not find solutions that are
significantly longer than those found by best-first search).
Related to this difference is the different approaches that 
\MACLEARN\ and \ALG\  take toward generalization of macros.  
\MACLEARN, using best-first search, cannot afford trying
every macro in every state.  Therefore, it uses domain-specific 
pattern language to specify for each macro the states at which it should
be applied.  \ALG, using hill-climbing, can afford more liberal 
and domain-independent generalization  using
a macro wherever it is legal.  Another difference between the
two algorithms is the attention filters that they use.  \MACLEARN\
uses the minimum-to-minimum method while \ALG\ uses the
minimum-to-better method.  The minimum-to-minimum method has the
weakness of acquiring longer macros, as local minima
become scarce and far apart during the learning
process.  \MACLEARN\ needed a special filter for avoiding the
acquisition of long macros.  

\ALG\ is a completely
autonomous algorithm---it generates its own examples and
uses the concept of {\em quiescence} to decide when to
increase the domain parameter and when to stop learning.
\MACLEARN\ used a more supervised approach, processing
 hand-crafted training examples.
To learn to solve sliding-tile puzzles, \MACLEARN\ was given first 
a single problem of a 6-tile puzzle, then a single instance of
an 8-puzzle and a 15-puzzle (after which it was able to solve a single
instance of a 24-puzzle).  \ALG\ 
 was demonstrated solving large sets of random problems of large size.
One advantage that \MACLEARN\ has over \ALG\ is its ability to
handle domains with parameterized operators.
\ALG\ tries all the applicable macros in every state. 
Had parameterized macros  been used, \ALG\ would have had to try all the
ways of binding the parameters, resulting in a potentially
large branching factor.
The peg-solitaire domain cannot be handled
efficiently by \ALG\ since it does not use a small set
of fixed operators.  \MACLEARN\ solves it by using parameterized 
operators.

Unlike some speedup learners that provide us
with either statistical or theoretical
guarantees \cite{Cohen:1992:UDF,Gratch:1992:CPS,Greiner:1989:IRL,Subramanian:1992:MUD,Tadepalli:1996:FFS}, 
\ALG\ has a heuristic nature and does
not provide us with any guarantee.
Indeed, while it performs very well in some domains,
it fails in other domains such
as the N-Hanoi.
To handle such domains, we would have to endow \ALG\ with the 
capability
of learning parameterized recursive macros \cite{Shavlik:1990:ARI}.  A related
weakness of \ALG\ is the sensitivity of the algorithm to the
heuristic function available.  We have shown an example
where \ALG\ has extreme difficulties with a seemingly
good heuristic (the sum of Manhattan distances for the 15-puzzle)
while learning easily with another one.

There are two features of the heuristic function that are
necessary for a successful performance of \ALG:
\begin{itemize}
\item  There is a ``small''
set of operator sequences that completely smooth the heuristic
function to eliminate any local minima.  This can be achieved either
by a heuristic function that has a small number of local minima or,
when the set of local minima is large, by  macros that 
generalize well over this set.
\item The maximal {\em radius} of the local minima should be small
enough to allow the escape procedure to find an escape route.
In addition, to use the scalable version of \ALG, the maximal radius should
not increase with the size.
\end{itemize}
The experiments described in this paper and the theorem in the
appendix
show that the
\RR\ heuristic of the \NN\ puzzle domain has a maximal
 radius of 18, regardless of the puzzle size.  This
feature does not hold for the \MD\ heuristic.  The 
example puzzle in 
Section \ref{sec:exp-heuristic}
 illustrates the problem.  When
scaling up the puzzle, the maximal radius scales up as well.

Another weakness of \ALG\ is its sensitivity to the
quiescence parameter.  This parameter tells \ALG\ when
to quit learning.  For \PARALG\ it is used to determine
when to increase the domain parameter for training.
Setting the quiescence parameter to a low value can
make \ALG\ quit prematurely before learning all the
necessary macros.  Setting it to a high value can lead
to a great waste of learning resources.  Indeed, for the
simple domains such as the N-Cannibals and N-Stones, \ALG\ 
spent most of its learning time making sure that there
is nothing new to learn.
Note that the  quiescence mechanism is needed only when performing
{\em off-line} learning.  \ALG\ could also be used in an on-line mode,
where macros are learned while solving user problems.  In such a case
there is no need to use the quiescence parameter.
Whenever \ALG\
 encounters a local minimum, it will use the escape mechanism to find a
path and record it as a macro.

While the above weaknesses are significant, we should also consider
the strengths of the algorithm.  \ALG\ is extremely simple, yet it is 
able
to learn to efficiently solve problems in a number of known domains.  
The ability of such a simple learning
algorithm to find an efficient procedure for
solving general \NN\ puzzle problems shows the
potential in using selective learning for speeding up problem solvers.
Our research goal of building the simplest domain-independent
learning algorithm to solve the \NN\ puzzle was achieved.  
A Common-Lisp implementation of \ALG\ and the \NN\ domain 
is included in the online appendix.
This short code (less than 200 lines long)
 underscores the simplicity of the algorithm.


Even with the simple architecture of \ALG, there is much future work
to be done.
One of the interesting directions is the application of macro-learning
to more complex domains such as scheduling.  Macro-learning, like
most learning techniques, works best when there 
are regularities in the domain that it can exploit.  It is not yet
clear whether there are such regularities in the scheduling domain, for 
example.  It is possible that macros can encode 
groups of variable assignments that should be tried together.



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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section*{Appendix A. Applying \PARALG\ to the \NN\ Puzzle}
To show a more concrete example of defining the parameters for
\PARALG\ 
we list here the exact definitions used to apply the algorithm to the
\NN\ puzzle domains.  The domain parameter used is $N$ with an initial
value of 3.  

\begin{figure}
\begin{center}
\begin{tabular}{ll}
$
\renewcommand{\arraystretch}{1.0}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
1 & 2 & 3 & 4 & 5  \\
\hline
6 & 7 & 8 & 19 & 16  \\
\hline
14 &   & 17 & 18 & 15  \\
\hline
20 & 24 & 13 & 22 & 21  \\
\hline
23 & 9 & 10 & 11 & 12  \\
\hline
\end{array}
$
&
$
\begin{array}{l}
s_g=\left\langle 1,2,3,4,\ldots,23,24,0\right\rangle \\
\begin{array}{lll}
tile_s(0,0) = 1 & tile_s(0,4) = 5 & tile_s(4,4) = 12 \\
loc_{s}(4)=(0,3) & loc_{s}(0)=(2,1) & loc_{s}(12)=(4,4) \\
placed(s,s_{g})=8 & NextTile(s)=9 & NextLoc(s)=(1,3)\\
\end{array}
\end{array}
$
\end{tabular}
\end{center}
\caption{\label{fig:puzzle-example}
\small
An example for the notations used for the \NN\ puzzle. }
\end{figure}

  To make the specifications more concise, we use the 
following
definitions and notations.
A {\em puzzle state} is a permutation
of the sequence $\left\langle 0, 1, \ldots , N^2-1\right\rangle$.
 Each of
the elements of the puzzle state is called a {\em tile}.  $0$ is
called the {\em empty tile}.
For convenience, we will represent a
puzzle state by an \NN\ row-major matrix.  Let $s$ be a state, let
$i,j \leq N$. We define $tile_s(i,j)$ to be the tile located in row
$i$ column $j$ of $s$, where $s$ is represented by
a row-major $N \times N$ matrix.
For every state $s$ and tile $t \in s$,
we define the tile location $loc_s(t)=(i,j)$ where $tile_s(i,j)=t$.
Let $l_1=(i_1,j_1)$ and $l_2=(i_2,j_2)$ be two locations.  The {\em  
distance}
between $l_1$ and $l_2$ is defined as $d(l_1,l_2)=|i_1 - i_2|+|j_1 - 
j_2|$.
Let $s=\left\langle t_1, \ldots ,t_{N^2} \right\rangle$ be a state.
Let $s_g=\left\langle g_1, \ldots ,g_{N^2-1}, 0 \right\rangle$ be the 
goal
state.  The number of {\em placed} tiles is the largest $p$ such that
$t_i=g_i$ for all $i \leq p$.  The expression of $p+1$ in the matrix
notation is called {\em the next location} and is marked as 
$NextLoc(s)$.  $g_p$ is called the {\em next tile} and is marked as
$NextTile(s)$.  Figure \ref{fig:puzzle-example} shows examples for 
the above notations.  The heuristic function is the one described in
the beginning of Section~\ref{sec:exper}, generalized to the \NN\
puzzle.  It is a linear combination of three factors.  The weights
were chosen to be high enough to enforce a lexicographic order.
The least significant factor is the Manhattan distance between the empty tile
and the next tile.  Since it is bounded above by $2(N-1)$, the second factor
is multiplied by $2N$ to make sure that it is dominant.  For the same
reason, we multiply the most significant factor by $4N^2$. 

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|p{11cm}|}
\hline
Domain parameter & N\\
\hline
Initial value & 3 \\
\hline
Generate-goal & 
Let $t_1, \ldots ,t_{N^2-1}$ be a random permutation of 
$1,\ldots,N^2-1$.
Generate-goal returns $\left\langle t_1, \ldots ,t_{N^2-1}, 0 
\right\rangle$.\\
\hline
Basic-operators & $\left\{ u, d, l, r\right\}$.  Let
$loc_s(0)=\left(i_0,j_0\right)$.
$d(s)$ is defined as:
\[
tile_{u(s)}(i,j)=\left\{
\begin{array}{l@{\quad:\quad}l}
tile_s(i_0+1,j_0) & i=i_0,j=j_0\\
0  & i=i_0+1,j=j_0\\
tile_s(i,j) & otherwise
\end{array}
\right.
\]
$d(s)$ is undefined for $i_0 = N - 1$.  $u,l,r$ are defined similarly.\\
\hline
Heuristic-function & 
$h(s,s_g)=4 \cdot N^2 \left ( N^2 - placed(s,s_g) \right ) + 
2 \cdot  N \cdot d 
( NextLoc(s) ,$ \hfill 
 $loc_s(NextTile(s))  )+ d ( loc_s ( 0),
 loc_s(NextTile(s)) )$\\
\hline
\end{tabular}
\caption{\label{tbl:puzzle-parameters}
\small The definitions of the parameters that were used to apply
\ALG\ to the \NN\ puzzle domains.}
\end{center}
\end{table}

Table \ref{tbl:puzzle-parameters} lists the exact parameters 
used for \ALG\ in the
\NN\ puzzle domain.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Appendix B. The Efficiency of Solving \NN\ Puzzles by \ALG}
\renewcommand{\bottomfraction}{0.7}

This section contains a proof that a specific set of macros learned by
\ALG\ 
is {\em complete} with respect to the heuristic function $h$ defined 
in
Table  \ref{tbl:puzzle-parameters}, and that a problem solver that 
uses these macros 
can solve any solvable \NN\ puzzle problem in $O(N^3)$ 
with a reasonable constant.
The proof can be easily
generalized to specify sufficient conditions for a set of macros to be
{\em complete}.
  

\begin{Lemma}
\label{lemma:empty}
Let $h$ be the heuristic function 
and $B$ the set of basic operators defined in Table 
\ref{tbl:puzzle-parameters}.
Let $s_g$ be a goal state of \NN\ puzzle.  
Let $s=\left\langle t_1, \ldots , t_{N^2} \right\rangle$ 
be a puzzle state different from $s_g$ such that 
$solvable(s,s_g)$.\\  
If $d \left(loc_s(0), loc_s(nextTile(s))\right) > 1$,  
then there exists a basic operator $o \in B$ 
such that $h(o(s),s_g) < h(s,s_g)$.
\end{Lemma}

\PROOF
Let  $loc_s(NextTile(s))=\left\langle i_{p}, j_{p} \right\rangle$,
 $loc_s(0)=\left\langle i_{0}, j_{0} \right\rangle$ and 
$NextLoc(s)=\left\langle i_{t}, j_{t} \right\rangle$.  
The following basic operators will decrease the value of $h$: 

\begin{equation}
o=\left\{
\begin{array}{ll}
j_{p} > j_{0} & r \\
j_{p} =  j_{0} &
\left\{
\begin{array}{ll}
i_{p} > i_{0} & d \\
i_{p} < i_{0} & u
\end{array}
\right .
\\
j_{p} <  j_{0} &
\left\{
\begin{array}{ll}
i_{p} > i_{0} & d \\
i_{p} \leq i_{0} & l
\end{array}
\right .
\\
\end{array}
\right .
\end{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[b]
\begin{tabular}{|c|c|c|c|l|c|c|}
\hline
$j_{p}=j_{0}$ & 
$\begin{array}{c}
i_{p}>i_{0}\\
\scriptstyle{(i_{p}=i_{0}+1)}
\end{array}$&               
&  
&
d &
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{10} & \SS{18}  \\
\hline
\SS{20} & \SS{19} & \SS{17} & \SS{ } & \SS{14}  \\
\hline
\SS{11} & \SS{12} & \SS{15} & \SS{[9]} & \SS{16}  \\
\hline
\SS{23} & \SS{22} & \SS{13} & \SS{24} & \SS{21}  \\
\hline
\end{array}
$
& 
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{10} & \SS{18}  \\
\hline
\SS{20} & \SS{19} & \SS{17} & \SS{[9]} & \SS{14}  \\
\hline
\SS{11} & \SS{12} & \SS{15} & \SS{ } & \SS{16}  \\
\hline
\SS{23} & \SS{22} & \SS{13} & \SS{24} & \SS{21}  \\
\hline
\end{array}
$
\\
\hline
              &
$\begin{array}{c}
i_{p}<i_{0}\\
\scriptstyle{(i_{p}=i_{0}-1)}
\end{array}$&      
$j_{p}>j_{t}$ &
& 
lur &
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{16} & \SS{23} & \SS{14} & \SS{10}  \\
\hline
\SS{15} & \SS{17} & \SS{22} & \SS{12} & \SS{20}  \\
\hline
\SS{11} & \SS{13} & \SS{24} & \SS{[7]} & \SS{9}  \\
\hline
\SS{21} & \SS{8} & \SS{19} & \SS{ } & \SS{18}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{16} & \SS{23} & \SS{14} & \SS{10}  \\
\hline
\SS{15} & \SS{17} & \SS{22} & \SS{12} & \SS{20}  \\
\hline
\SS{11} & \SS{13} & \SS{[7]} & \SS{ } & \SS{9}  \\
\hline
\SS{21} & \SS{8} & \SS{24} & \SS{19} & \SS{18}  \\
\hline
\end{array}
$
\\
\hline
   %cond1
&
   %cond2
& 
   $j_{p}<j_{t}$ %cond3
&              
   %cond4
& 
rul
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{15} & \SS{12}  \\
\hline
\SS{18} & \SS{[9]} & \SS{10} & \SS{17} & \SS{20}  \\
\hline
\SS{13} & \SS{ } & \SS{22} & \SS{11} & \SS{14}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{15} & \SS{12}  \\
\hline
\SS{18} & \SS{} & \SS{[9]} & \SS{17} & \SS{20}  \\
\hline
\SS{13} & \SS{22} & \SS{10} & \SS{11} & \SS{14}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
& 
$j_{p}=j_{t}$  %cond3
&  
$j_{p}<N$      %cond4
& 
ruuld 
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{20} & \SS{19}  \\
\hline
\SS{21} & \SS{22} & \SS{16} & \SS{[14]} & \SS{18}  \\
\hline
\SS{24} & \SS{17} & \SS{23} & \SS{ } & \SS{15}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{[14]} & \SS{20}  \\
\hline
\SS{21} & \SS{22} & \SS{16} & \SS{ } & \SS{19}  \\
\hline
\SS{24} & \SS{17} & \SS{23} & \SS{15} & \SS{18}  \\
\hline
\end{array}
$
\\
\hline
   %cond1
&  
   %cond2
&
   %cond3
&  
$j_{p}=N$   %cond4
& 
uuldrdluurd 
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{13}  \\
\hline
\SS{21} & \SS{20} & \SS{19} & \SS{14} & \SS{[10]}  \\
\hline
\SS{16} & \SS{22} & \SS{23} & \SS{18} & \SS{ }  \\
\hline
\SS{24} & \SS{17} & \SS{12} & \SS{11} & \SS{15}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{[10]}  \\
\hline
\SS{21} & \SS{20} & \SS{19} & \SS{14} & \SS{  }  \\
\hline
\SS{16} & \SS{22} & \SS{23} & \SS{13} & \SS{18}  \\
\hline
\SS{24} & \SS{17} & \SS{12} & \SS{11} & \SS{15}  \\
\hline
\end{array}
$
\\
\hline
\end{tabular}
\caption{\label{table:proof1}
\small  The macro used for each of the conditions on the
tile indices.  The right column shows an example 
for a state before and after the macro application.}
\end{table}
\begin{Lemma}
\label{lemma:macros}
Let $h$, $B$, $s_g$ and $s$ be defined as in Lemma \ref{lemma:empty}.
Let $M$ be the following set of macros:
\[
M= \left\{\parbox{11.5cm}{\raggedright lur, rul, uld, ruuld, dllur, drrul, 
urrdluld,
        urrdluld, uuldrdluurd,
	lurrdluld, urdrrullldrrur, urdrrullldrrurd, llurdrrullldrrurd,
        uldllurdrulldrrurd}
\right\}
\]
Then the set $M$ is a {\em complete} set of macros, i.e.,
there is always an operator $o \in B \cup M$ such that 
$h(o(s),s_g) < h(s,s_g)$.
\end{Lemma}

\PROOF  
By Lemma \ref{lemma:empty}, we need to prove only for the cases where 
$d \left(loc_s(0),loc(NextTile(s)) \right )=1$.  
There are four possible cases.  Tables \ref{table:proof1} and
\ref{table:proof2}
show which operator  can 
be applied 
in each of the cases  to decrease the value of $h$.
To make the proof simpler, the tables assume $N > 4$.


\begin{table}[p]
\begin{tabular}{|c|c|c|c|l|c|c|}
\hline
$\begin{array}{c}
j_p>j_0\\
\scriptstyle{(j_{p}=j_{0}+1)}
\end{array}   
$  
  %cond1 
& 
$i_{p}=i_{0}$ %cond2
& 
$j_{p}>j_{t}$ %cond3
&              
   %cond4
& 
r 
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{22} & \SS{ } & \SS{[12]} & \SS{17}  \\
\hline
\SS{18} & \SS{13} & \SS{15} & \SS{14} & \SS{20}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{22} & \SS{[12]} & \SS{ } & \SS{17}  \\
\hline
\SS{18} & \SS{13} & \SS{15} & \SS{14} & \SS{20}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
   %cond2
& 
$j_{p}<j_{t}$ %cond3
& 
$i_{p}<N$ %cond4             
& 
drrul
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{12}  \\
\hline
\SS{18} & \SS{11} & \SS{ } & \SS{[10]} & \SS{20}  \\
\hline
\SS{13} & \SS{15} & \SS{17} & \SS{22} & \SS{14}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{12}  \\
\hline
\SS{18} & \SS{11} & \SS{17} & \SS{ } & \SS{[10]}  \\
\hline
\SS{13} & \SS{15} & \SS{22} & \SS{14} & \SS{20}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
 %cond1
&
  %cond2
& 
  %cond3
& 
$
\begin{array}{c}
i_{p}=N\\
i_{t}<N-1
\end{array}
$  
  %cond4  
& 
urrdluld
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{18}  \\
\hline
\SS{23} & \SS{20} & \SS{16} & \SS{17} & \SS{22}  \\
\hline
\SS{ } & \SS{[15]} & \SS{21} & \SS{19} & \SS{24}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{18}  \\
\hline
\SS{23} & \SS{20} & \SS{21} & \SS{17} & \SS{22}  \\
\hline
\SS{ } & \SS{16} & \SS{[15]} & \SS{19} & \SS{24}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
& \
  %cond3
& 
  $
\renewcommand{\arraystretch}{\eqnstr}              
\begin{array}{c}
i_{p}=N\\
i_{t}=N-1\\
j_t - j_p \leq 1
\end{array}
$  
  %cond4
& 
urrdluld
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{22} & \SS{20}  \\
\hline
\SS{21} & \SS{ } & \SS{[19]} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{24} & \SS{20}  \\
\hline
\SS{21} & \SS{ } & \SS{22} & \SS{[19]} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
& 
  %cond3
& 
  $
\renewcommand{\arraystretch}{\eqnstr}              
\begin{array}{c}
i_{p}=N\\
i_{t}=N-1\\
j_t - j_p > 1
\end{array}
$  
  %cond4
& 
urdrrullldrrurd
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{22}  \\
\hline
\SS{21} & \SS{ } & \SS{[20]} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{22}  \\
\hline
\SS{21} & \SS{24} & \SS{23} & \SS{[20]} & \SS{}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
&
  $j_p = j_t$  %cond3
&
  $j_0 > 1$  %cond4
&
lurrdluld
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{12}  \\
\hline
\SS{18} & \SS{11} & \SS{17} & \SS{ } & \SS{[10]}  \\
\hline
\SS{13} & \SS{15} & \SS{22} & \SS{14} & \SS{20}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{[10]}  \\
\hline
\SS{18} & \SS{11} & \SS{ } & \SS{12} & \SS{17}  \\
\hline
\SS{13} & \SS{15} & \SS{22} & \SS{14} & \SS{20}  \\
\hline
\SS{19} & \SS{21} & \SS{16} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
&
  %cond3
&
   $j_0 = 1$ %cond4
&
urdrulldrur
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{23} & \SS{20} & \SS{18} & \SS{19}  \\
\hline
\SS{ } & \SS{[17]} & \SS{21} & \SS{24} & \SS{22}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{[17]} & \SS{ } & \SS{18} & \SS{19}  \\
\hline
\SS{21} & \SS{23} & \SS{20} & \SS{24} & \SS{22}  \\
\hline
\end{array}
$
\\
\hline
$\begin{array}{c}
j_p<j_0\\
\scriptstyle{(j_{p}=j_{0}-1)}
\end{array}   
$  
  %cond1 
& 
$i_{p}=i_{0}$ %cond2
& 
$j_{p}>j_{t}$ %cond3
&
$              
\begin{array}{c}
i_{t} < N\\
i_{p} < N
\end{array}
$   
%cond4
& 
dllur
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{21} & \SS{[17]} & \SS{ } & \SS{20}  \\
\hline
\SS{18} & \SS{19} & \SS{24} & \SS{22} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{[17]} & \SS{ } & \SS{22} & \SS{20}  \\
\hline
\SS{18} & \SS{21} & \SS{19} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
&
  %cond3
&
$              
\begin{array}{c}
i_{t} < N\\
i_{p} = N
\end{array}
$   
%cond4
& 
uld
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{22} & \SS{21} & \SS{23}  \\
\hline
\SS{20} & \SS{19} & \SS{24} & \SS{[18]} & \SS{ }  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{22} & \SS{[18]} & \SS{21}  \\
\hline
\SS{20} & \SS{19} & \SS{24} & \SS{ } & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
&
  %cond3
&
$
\renewcommand{\arraystretch}{\eqnstr}                            
\begin{array}{c}
i_{t} =  N\\
j_{0} < N
\end{array}
$   
%cond4
& 
llurdrrullldrrurd
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{20}  \\
\hline
\SS{22} & \SS{23} & \SS{[21]} & \SS{ } & \SS{24}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{20}  \\
\hline
\SS{22} & \SS{[21]} & \SS{24} & \SS{23} & \SS{ }  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
&
  %cond3
&
$
\renewcommand{\arraystretch}{\eqnstr}              
\begin{array}{c}
i_{t} = N\\
j_{0} = N\\
J_{t} < N - 2\\
\end{array}
$   
%cond4
& 
uldllurdrulldrrurd
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{20}  \\
\hline
\SS{22} & \SS{24} & \SS{23} & \SS{[21]} & \SS{ }  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{20}  \\
\hline
\SS{22} & \SS{23} & \SS{[21]} & \SS{24} & \SS{ }  \\
\hline
\end{array}
$
\\
\hline
  %cond1
&
  %cond2
&
  %cond3
&
$              
\begin{array}{c}
i_{t} = N\\
j_{0} = N\\
J_{t} \geq N - 2\\
\end{array}
$   
%cond4
&
Unsolvable puzzle
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{18} & \SS{19} & \SS{20}  \\
\hline
\SS{21} & \SS{22} & \SS{24} & \SS{[23]} & \SS{ }  \\
\hline
\end{array}
$
&
\\
\hline
  %cond1
&
  %cond2
&
$j_p < j_t$ %cond3
&
  %cond4
&
l
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{19} & \SS{22} & \SS{20}  \\
\hline
\SS{[18]} & \SS{ } & \SS{21} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{12} & \SS{13} & \SS{14} & \SS{15}  \\
\hline
\SS{16} & \SS{17} & \SS{19} & \SS{22} & \SS{20}  \\
\hline
\SS{ } & \SS{[18]} & \SS{21} & \SS{24} & \SS{23}  \\
\hline
\end{array}
$
\\
\hline
  %cond1 
&
  %cond2
&
  %cond3
&
  $j_p = j_t$ %cond4
&
uld
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{20} & \SS{17} & \SS{16} & \SS{18}  \\
\hline
\SS{19} & \SS{[12]} & \SS{ } & \SS{15} & \SS{14}  \\
\hline
\SS{23} & \SS{22} & \SS{13} & \SS{24} & \SS{21}  \\
\hline
\end{array}
$
&
$
\renewcommand{\arraystretch}{\arrstr}
\setlength{\arraycolsep}{0.5mm}
\begin{array}{*{5}{|c}|}
\hline
\SS{1} & \SS{2} & \SS{3} & \SS{4} & \SS{5}  \\
\hline
\SS{6} & \SS{7} & \SS{8} & \SS{9} & \SS{10}  \\
\hline
\SS{11} & \SS{[12]} & \SS{20} & \SS{16} & \SS{18}  \\
\hline
\SS{19} & \SS{ } & \SS{17} & \SS{15} & \SS{14}  \\
\hline
\SS{23} & \SS{22} & \SS{13} & \SS{24} & \SS{21}  \\
\hline
\end{array}
$
\\
\hline
\end{tabular}
\caption{\label{table:proof2}
\small (Cont.) The macro used for each of the conditions on the
tile indices.  The right column shows an example 
for a state before and after the macro application.}
\end{table}


\begin{Theorem}
Let $h$ and $M$ be defined as in Lemma \ref{lemma:macros}.
\ALG, using $M$, can solve any solvable
\NN\ puzzle problem performing no more than $288N^3-301N^2$
basic operator applications.
The length of
the solution is bounded by $50N^3-66N^2$.
\end{Theorem}

\PROOF
By Lemma \ref{lemma:macros}, we can move from each state to a state
with a lower heuristic value.  Therefore, after a finite number
of states, we will reach the state $s$ with $h(s,s_g)=0$, which is 
the goal
state.  $N^2$ tiles are moved into their goal location.
The maximum distance of each tile from its goal location is $2(N-1)$.
Each  movement of a tile towards its goal location involves moving the blank 
tile to be adjacent to the next tile, and then using either a basic
operator or a macro operator to advance the next tile.
At the beginning of this operation the blank tile can be anywhere, so
we need to advance it  at most $(N-1)+(N-2)$ times to bring it to 
distance 1 from the
next tile. After that, for the remaining $2(N-1)-1$ times,
a macro operator can move the blank away from the next
tile, but the distance will be at most 4 (this is a property of the
specific $M$), so we will need to advance it at most 3 times
 to bring it next to the
next tile.  By Lemma~\ref{lemma:empty}, the blank tile can be brought
to distance 1 using only basic operators.
After bringing the empty tile next to the next tile, 
in the worst case, the algorithm may try all the 4 basic operators and 
all the macros (with a total length of 124) before
finding the one that reduces the heuristic value.
All this leads to the following  bound on the
total number of basic operators applied while solving a problem $p$
using $B$ and $M$:
\[
 N^2[4((N-1)+(N-2)+3(2(N-1)-1))+2(N-1)(124+4)]=288N^3-301N^2
\]
The maximal length
of a macro is 18.  Therefore, the length of a solution found by\\
 \ALG\
is bounded by 
\[
N^2[4((N-1)+(N-2)+3(2(N-1)-1))+2(N-1)18]=50N^3-66N^2 \; \ENDPROOF
\]

We can use the same lemmas to prove that 
 \ALG\ can solve any solvable problem in $O(N^3)$
even without learning simply
by performing BFS search in each place where a macro is used
in the original proof.
However, instead of using 128 in the above formula,
we will use $4^{18}$ (18, the length of the longest
macro, can be used as an upper bound on the
depth of the search).  This gives a bound
of  $137,438,953,504N^3 - 137,438,953,520N^2$, which is about 477,218,588
times larger than the constant for \ALG\ after learning.  
While in the pure
sense of computational complexity both bounds
belong to the same complexity class,
the huge constant makes this fact meaningless for any practical
purpose.



\bibliography{shaul,shauls-papers}
\bibliographystyle{theapa}
\end{document}

endofispell

