
%\input{article-prolog}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\input{JAIR-prolog}

%\documentstyle[fullpage,12pt,doublespace]{article}

%\documentstyle[jair,11pt,epsfig,theapa]{article}
\documentstyle[jair,twoside,11pt,theapa]{article}

\input psfig

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\input{format}
% switch to Austrian German
%\setlanguage{\austrian}

% switch to German captions
% \captionsgerman
% depth of numbering for sections (default 3)
%%% \setcounter{secnumdepth}{4}
% depth of table of contents (default 3)
%%% \setcounter{tocdepth}{4}
% \newcommand{\iff}{iff}

\newcommand{\mlmin}{\mbox{\tlmin}}
\newcommand{\tlmin}{$L_{\min}$}
\newcommand{\lmin}{\ifmmode\mlmin\else\tlmin\fi}


\newcommand{\taeps}{{{$\maeps$}}}
\newcommand{\tastern}{{{$\xastern$}}}
\newcommand{\ttree}{{{\sc Tree}}}
\newcommand{\topen}{{{\sc Open}}}
\newcommand{\tclosed}{{{\sc Closed}}}
\newcommand{\tfocal}{{{\sc Focal}}}          

\newcommand{\maeps}{A_\varepsilon^\ast}
\newcommand{\xastern}{A^\ast}
\newcommand{\mtree}{\mbox{\ttree}}
\newcommand{\mopen}{\mbox{\topen}}
\newcommand{\mclosed}{\mbox{\tclosed}}
\newcommand{\mfocal}{\mbox{\tfocal}}
\newcommand{\mwin}{W\!I\!N}
\newcommand{\mloss}{L\!O\!S\!S}

\newcommand{\mhpa}{{\mbox{\it HPA}}}
\newcommand{\mhpastern}{{\mbox{\it HPA}}^\ast}
\newcommand{\mbhpa}{{\mbox{\it BHPA}}}
\newcommand{\mbsstern}{{\mbox{\it BS\/}}^\ast}
\newcommand{\midastern}{{\mbox{\it IDA\/}^\ast}}
\newcommand{\mwidastern}{{\mbox{\it WIDA\/}^\ast}}
\newcommand{\mrbfs}{{\mbox{\it RBFS}}}
\newcommand{\Mbhffa}{{\mbox{\it BHFFA}}}
\newcommand{\mbhpaw}{{\mbox{\it BHPA}}_w}
\newcommand{\mbhpaeps}{{\mbox{\it BHPA}}_\varepsilon}
\newcommand{\mibhpaeps}{{\mbox{\it IBHPA}}_\varepsilon}
\newcommand{\mibhpadeps}{{\mbox{\tibhpadeps}}}
\newcommand{\mbswstern}{{\mbox{\it BS\/}}_w^\ast}
\newcommand{\mbsepsstern}{{\mbox{\it BS\/}}_\varepsilon^\ast}
\newcommand{\mibsepsstern}{{\mbox{\it IBS\/}}_\varepsilon^\ast} 
\newcommand{\mibsdepsstern}{{\mbox{\tibsdepsstern}}}
\newcommand{\mbaepsstern}{{\mbox{\it BA}}_\varepsilon^\ast}
\newcommand{\mbadepsstern}{{\mbox{\it BA}}_{\delta,\varepsilon}^\ast}
\newcommand{\mbsaepsstern}{{\mbox{\it BSA}}_\varepsilon^\ast}
\newcommand{\mbsadepsstern}{{\mbox{\it BSA}}_{\delta,\varepsilon}^\ast}
\newcommand{\mifp}{{\mbox{\it IFP}}}
\newcommand{\msifp}{{\mbox{\it SIFP}}}
\newcommand{\muifp}{{\mbox{\it UIFP}}}
\newcommand{\mrbfsl}{{\mbox{\it RBFSL}}}
\newcommand{\mbhw}{{\mbox{\it BHW}}}
\newcommand{\mbhr}{{\mbox{\it BHR}}}
\newcommand{\mbai}{{\mbox{\it BAI}}}

\newcommand{\mdfbb}{{\mbox{\it DFBB}}}
\newcommand{\mbabb}{{\mbox{\it BABB}}}
\newcommand{\mtcbb}{{\mbox{\it TCBB}}}
\newcommand{\mmrec}{{\mbox{\it MREC}}}
\newcommand{\mdfid}{{\mbox{\it DFID}}}
\newcommand{\mmastern}{{\mbox{\it MA\/}^\ast}}
\newcommand{\msmastern}{{\mbox{\it SMA\/}^\ast}}
\newcommand{\mits}{{\mbox{\it ITS}}}
\newcommand{\mmove}{{\mbox{\it Move}}}
\newcommand{\midpsstern}{{\mbox{\it IDPS\/}^\ast}}
\newcommand{\mprobing}{{\mbox{\it Probing}}}
\newcommand{\mreverse}{{\mbox{\it Reverse}}}
\newcommand{\mtrans}{{\mbox{\it Trans}}}
\newcommand{\mDiff}{{\mbox{\it Diff}}}
\newcommand{\mDiffstern}{{\mbox{\it Diff\/}^\ast}}
\newcommand{\mMindiff}{{\mbox{\it Mindiff}}}



\newcommand{\thpa}{$\mhpa$}
\newcommand{\thpastern}{$\mhpastern$}
\newcommand{\tbhpa}{$\mbhpa$}
\newcommand{\tbsstern}{$\mbsstern$}
\newcommand{\tidastern}{$\midastern$}
\newcommand{\twidastern}{$\mwidastern$}
\newcommand{\trbfs}{$\mrbfs$}
\newcommand{\tbhffa}{$\Mbhffa$}
\newcommand{\tbhpaw}{$\mbhpaw$}
\newcommand{\tbhpaeps}{$\mbhpaeps$}
\newcommand{\tibhpaeps}{$\mibhpaeps$}
\newcommand{\tibhpadeps}{{\it IBHPA}$_{\delta,\varepsilon}$}
\newcommand{\tbswstern}{$\mbswstern$}
\newcommand{\tbsepsstern}{$\mbsepsstern$}
\newcommand{\tibsepsstern}{$\mibsepsstern$}
\newcommand{\tibsdepsstern}{{\it IBS\/}$_{\delta,\varepsilon}^\ast$}
\newcommand{\tbaepsstern}{$\mbaepsstern$}
\newcommand{\tbadepsstern}{$\mbadepsstern$}
\newcommand{\tbsaepsstern}{$\mbsaepsstern$}
\newcommand{\tbsadepsstern}{$\mbsadepsstern$}
\newcommand{\tifp}{$\mifp$}
\newcommand{\tsifp}{$\msifp$}
\newcommand{\tuifp}{$\muifp$}
\newcommand{\trbfsl}{$\mrbfsl$}
\newcommand{\tbhw}{$\mbhw$}
\newcommand{\tbhr}{$\mbhr$}
\newcommand{\tbai}{$\mbai$}

\newcommand{\tdfbb}{$\mdfbb$}
\newcommand{\tbabb}{$\mbabb$}
\newcommand{\ttcbb}{$\mtcbb$}
\newcommand{\tmrec}{$\mmrec$}
\newcommand{\tdfid}{$\mdfid$}
\newcommand{\tmastern}{$\mmastern$}
\newcommand{\tsmastern}{$\msmastern$}
\newcommand{\tits}{$\mits$}
\newcommand{\tmove}{$\move$}
\newcommand{\tidpsstern}{$\midpsstern$}
\newcommand{\tprobing}{$\mprobing$}
\newcommand{\treverse}{$\mreverse$}
\newcommand{\ttrans}{$\mtrans$}
\newcommand{\tDiff}{$\mDiff$}
\newcommand{\tDiffstern}{$\mDiffstern$}
\newcommand{\tMindiff}{$\mMindiff$}





%\newcommand{\win}{\ifmmode\mwin\else\twin\fi}
%\newcommand{\loss}{\ifmmode\mloss\else\tloss\fi}
%\newcommand{\WIN}{\win}
%\newcommand{\LOSS}{\loss}
%\newcommand{\MIN}{M\!I\!N}
%\newcommand{\MAX}{M\!A\!X}
%\newcommand{\mm}{M\!M}
\newcommand{\open}{\ifmmode\mopen\else\topen\fi}
\newcommand{\closed}{\ifmmode\mclosed\else\tclosed\fi}
\newcommand{\focal}{\ifmmode\mfocal\else\tfocal\fi}
\newcommand{\tree}{\ifmmode\mtree\else\ttree\fi}


\newcommand{\idastern}{\ifmmode\midastern\else\tidastern\fi}
\newcommand{\widastern}{\ifmmode\mwidastern\else\twidastern\fi}
\newcommand{\rbfs}{\ifmmode\mrbfs\else\trbfs\fi}
\newcommand{\hpastern}{\ifmmode\mhpastern\else\thpastern\fi}
\newcommand{\bhpa}{\ifmmode\mbhpa\else\tbhpa\fi}
\newcommand{\hpa}{\ifmmode\mhpa\else\thpa\fi}
\newcommand{\bsstern}{\ifmmode\mbsstern\else\tbsstern\fi}
\newcommand{\bhffa}{\ifmmode\Mbhffa\else\tbhffa\fi}
\newcommand{\bhpaw}{\ifmmode\mbhpaw\else\tbhpaw\fi}
\newcommand{\bhpaeps}{\ifmmode\mbhpaeps\else\tbhpaeps\fi}
\newcommand{\ibhpaeps}{\ifmmode\mibhpaeps\else\tibhpaeps\fi}
\newcommand{\ibhpadeps}{\ifmmode\mibhpadeps\else\tibhpadeps\fi}
\newcommand{\bswstern}{\ifmmode\mbswstern\else\tbswstern\fi}
\newcommand{\bsepsstern}{\ifmmode\mbsepsstern\else\tbsepsstern\fi}
\newcommand{\ibsepsstern}{\ifmmode\mibsepsstern\else\tibsepsstern\fi}
\newcommand{\ibsdepsstern}{\ifmmode\mibsdepsstern\else\tibsdepsstern\fi}
\newcommand{\baepsstern}{\ifmmode\mbaepsstern\else\tbaepsstern\fi}
\newcommand{\badepsstern}{\ifmmode\mbadepsstern\else\tbadepsstern\fi}
\newcommand{\bsaepsstern}{\ifmmode\mbsaepsstern\else\tbsaepsstern\fi}
\newcommand{\bsadepsstern}{\ifmmode\mbsadepsstern\else\tbsadepsstern\fi}
\newcommand{\ifp}{\ifmmode\mifp\else\tifp\fi}
\newcommand{\sifp}{\ifmmode\msifp\else\tsifp\fi}
\newcommand{\uifp}{\ifmmode\muifp\else\tuifp\fi}
\newcommand{\rbfsl}{\ifmmode\mrbfsl\else\trbfsl\fi}
\newcommand{\bhw}{\ifmmode\mbhw\else\tbhw\fi}
\newcommand{\bhr}{\ifmmode\mbhr\else\tbhr\fi}
\newcommand{\bai}{\ifmmode\mbai\else\tbai\fi}

\newcommand{\dfbb}{\ifmmode\mdfbb\else\tdfbb\fi}
\newcommand{\babb}{\ifmmode\mbabb\else\tbabb\fi}
\newcommand{\tcbb}{\ifmmode\mtcbb\else\ttcbb\fi}
\newcommand{\mrec}{\ifmmode\mmrec\else\tmrec\fi}
\newcommand{\dfid}{\ifmmode\mdfid\else\tdfid\fi}
\newcommand{\mastern}{\ifmmode\mmastern\else\tmastern\fi}
\newcommand{\smastern}{\ifmmode\msmastern\else\tsmastern\fi}
\newcommand{\its}{\ifmmode\mits\else\tits\fi}
\newcommand{\move}{\ifmmode\mmove\else\tmove\fi}
\newcommand{\idpsstern}{\ifmmode\midpsstern\else\tidpsstern\fi}
\newcommand{\probing}{\ifmmode\mprobing\else\tprobing\fi}
\newcommand{\reverse}{\ifmmode\mreverse\else\treverse\fi}
\newcommand{\trans}{\ifmmode\mtrans\else\ttrans\fi}
\newcommand{\Diff}{\ifmmode\mDiff\else\tDiff\fi}
\newcommand{\Diffstern}{\ifmmode\mDiffstern\else\tDiffstern\fi}
\newcommand{\Mindiff}{\ifmmode\mMindiff\else\tMindiff\fi}



%%% {\renewcommand{\arraystretch}{0.8}}
%%% \arraycolsep1mm    


\newcommand{\tmeetingnode}{{\em MeetingNode}}
\newcommand{\mmeetingnode}{{$\em MeetingNode$}}
\newcommand{\meetingnode}{\ifmmode\tmeetingnode\else\mmeetingnode\fi}
\newcommand{\aeps}{\ifmmode\maeps\else\taeps\fi}
\newcommand{\astern}{\ifmmode\xastern\else\tastern\fi}

\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
%%%\newtheorem{model}{Modell}
\newenvironment{proof}{\noindent
{\bf Proof:}\em}{\hfill $\Box$}
\newenvironment{proofsketch}{\noindent
{\bf Proof sketch:}\em}{\hfill $\Box$}



%%%   \newtheorem{definition}{Definition}[chapter]
%%%   \newtheorem{proposition}{Proposition}[chapter]
%%%   \newtheorem{lemma}{Lemma}[chapter]
%%%   \newenvironment{proof}{{\bf Beweis:}}{\hfill $\Box$}
%%%   
%%%   \newenvironment{rlist}{\begin{list}{}{
%%%                          \settowidth{\labelwidth}{\bf Resultat 1:} \setlength{\leftmargin}{\labelwidth}
%%%                          \addtolength{\leftmargin}{\labelsep} \addtolength{\leftmargin}{\itemindent}
%%%                          \rightmargin1cm \addtolength{\leftmargin}{\rightmargin}
%%%                          }}{\end{list}}
%%%   
%%%   
%%%   \newcommand{\rb}[1]{\raisebox{1.5ex}[-1.5ex]{#1}}
%%%   
%%%   \newcommand{\br}[1]{\raisebox{-1.5ex}[1.5ex]{#1}}
%%%   

\newcommand{\eps}{\varepsilon}
\newcommand{\wa}{\hpastern}
\newcommand{\maxn}{Nodes_{max}}
\newcommand{\w}{\widastern}

\newcommand{\savet}{safethresh}
\newcommand{\basict}{basicthresh}
\newcommand{\binc}{INC_{min}}
\newcommand{\upper}{UPPER}
\newcommand{\rbfslower}{LOWER}






%JAIR\setstretch{1.6}
%\setstretch{1.7}
%\setstretch{1}


\hyphenation{Spei-cher-be-darf}
\hyphenation{Russell}
\hyphenation{Champeaux}
\hyphenation{Manhattan}
\hyphenation{Khorsand}
\hyphenation{Edinburgh}
\hyphenation{Kaufman}
\hyphenation{Vienna}
\hyphenation{be-grenz-tem}
\hyphenation{Tech-ni-sche}


\jairheading{7}{1997}{283-317}{8/97}{12/97}
\ShortHeadings{Bidirectional Heuristic Search Reconsidered}
{Kaindl \& Kainz}
\firstpageno{283}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{
%JAIR\vspace*{-10mm}
%JAIR{\footnotesize Submitted to 
%{\it Artificial Intelligence Journal} or to
%JAIR{\it Journal of Artificial Intelligence Research}}\\
%\vspace*{-2cm}
Bidirectional Heuristic Search Reconsidered}
%JAIR\thanks{
%JAIRParts of this paper already appeared in 
%JAIR{\em Proc.\ Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95)}.
%JAIR%\thanksref{IJCAI-95}}
%JAIRand in 
%JAIR{\em Proc.\ Thirteenth National Conference on Artificial Intelligence (AAAI-96)}.}}
%JAIR%\thanksref{AAAI-96}


%\thanks[IJCAI-95]{Part of this paper already appeared in {\em Proc.\ Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95)}.}
%\cite{Kaindl_et_al_95}}

\author{\name Hermann Kaindl \email hermann.kaindl@siemens.at \\
        \name Gerhard Kainz \email gerhard.kainz@siemens.at \\
        \addr Siemens AG \"Osterreich, PSE\\
              Geusaugasse 17\\
              A--1030 Vienna, Austria}



\maketitle


%JAIR\vspace*{-10mm}


\begin{abstract}

%JAIR\parindent0mm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\input{bidir-abstract}

%Problem:\\
%JAIR\parindent0mm
The assessment of bidirectional heuristic search has been incorrect since it was first published more than a quarter of a century ago.
For quite a long time,
this search strategy did not achieve the expected results, and there was a major misunderstanding about the reasons behind
it.
%was assessed wrongly for quite a long time: it was considered inefficient for a wrong reason.
%Solution:\\
Although there is still wide-spread belief 
%about the conjecture 
that bidirectional heuristic search is afflicted by the problem of search frontiers passing each other, we demonstrate that this conjecture is wrong.
Based on this finding,
we present both
a new 
%non-traditional 
generic approach to bidirectional heuristic search
and
a new approach to dynamically improving heuristic values that is feasible in bidirectional search only.
These approaches are put into perspective with both the traditional and more recently proposed approaches in order to facilitate a better overall understanding.
% of this paradigm.
%Why solution:\\
Empirical results of experiments with our new approaches show that
bidirectional heuristic search can be performed very efficiently and also with limited memory.
%They 
These results
suggest that
bidirectional 
heuristic
search appears to be 
%the best 
%method
better for
%to 
solving certain difficult problems
than corresponding 
unidirectional search.
%, and t
This provides some evidence for the usefulness of a 
%paradigm 
search strategy
that was 
long
neglected.
%Point sentence:\\
In summary,
we show that bidirectional heuristic search is viable and 
%Consequence:\\
consequently
propose that 
it
%this paradigm 
be reconsidered.

\end{abstract}


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


%JAIR\newpage


%JAIR-CR\input{notation}

%JAIR\vspace*{-10mm}


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


%\newpage
%
%\tableofcontents
%
%
%
%\pagebreak





\section{Background and Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

When a problem is represented as a {\it state space} graph, {\it solutions} to such a problem are paths from a given {\it start} node $s$ to some {\it goal/target} node $t$.
Finding such a solution can be attempted by searching this graph.
If the search is guided by heuristic information, it is called a {\it heuristic search}.
Most of the work on heuristic search for problem solving deals with {\it unidirectional} approaches, that start from $s$ heading towards some node $t$  \cite<see, e.g.,>
%, e.g., 
%the book by Pearl 
{Pearl_84}.


When there is one goal node $t$ explicitly given and the search operators are reversible, {\it bidirectional search} is possible, which proceeds both 
in the forward direction
from $s$ to $t$ and 
in the backward direction
from $t$ to $s$ \cite<see, e.g.,>{Nilsson_80}.
%(see, e.g., \cite{Nilsson_80}).
Strictly speaking, it is not even required that operators have inverses.
It is just necessary that for a given node $n$ the set of parent nodes $p_i$ can be determined for which there exist operators that lead from $p_i$ to $n$.
Searching backwards means generating parent nodes successively from the goal node $t$ \cite<see, e.g.,>{Russell_and_Norvig_95}.
%(see, e.g., \cite{Russell_and_Norvig_95}).
In other words, backward search implements {\it reasoning} about the operators in the backward direction.

As an illustrating example of a class of problems where bidirectional search can be usefully applied, consider finding find a shortest path between two given places $s$ and $t$ using a given map of some city.
In case of one-way streets, bidirectional search implements reasoning like the following: ``in order to arrive at $t$, some one-way street leading towards $t$ may be used''.
In a slightly adapted problem class, the cost of driving some street may be different, depending on the driving direction.
A steep street to the top of a mountain may serve as an example.
Bidirectional search works also correctly in such a case: the backward search implements reasoning in the backward direction but takes account of the cost of
driving in the forward direction.
More formally, $k_1(m,n) = k_2(n,m)$ is the cost of an optimal path from $m$ to $n$.
$k_2$ is used for notational convenience only.\footnote{
The notation is explained in the Appendix.}
All the bidirectional search algorithms dealt with in this paper work correctly under these conditions and do {\it not} require that the operators are reversible or that the cost of a path is the same in either direction.

Bidirectional search was shown to be more efficient than its unidirectional counterpart when heuristic knowledge is unavailable,
but the inverse result was originally found in experiments for bidirectional {\it heuristic} search by Pohl \citeyear{Pohl_71}.
Since this kind of search did not work as expected, there was consensus about the conjecture that bidirectional heuristic search is afflicted by the problem of search frontiers passing each other without intersecting.
This situation was metaphorically compared by Pohl to missiles that pass each other, and illustrated in a figure that was reprinted by Nilsson 
%in 
\citeyear[Fig.\ 2.11]{Nilsson_80}.
Nilsson conjectured that in such a case the bidirectional search may expand twice as many nodes as would a unidirectional one.


While the 
%originally proposed algorithm BHPA \cite{Pohl_71} 
original algorithm BHPA proposed by Pohl \citeyear{Pohl_71} 
may actually show such inefficient performance, the {\it missile metaphor} is wrong and misleading.
We demonstrate that
bidirectional heuristic search is actually {\it not} afflicted by the problem of search frontiers passing each other.
%, but the
The performance of BHPA is much worse than originally expected because of two very different reasons:

\begin{enumerate}

\item	BHPA's search frontiers typically go {\it through each other}.

\item	The major effort is spent {\it after} the search frontiers have already met:
for 
%improving the solution quality of the solution 
finding better solutions
than the one
found at the first meeting of the search frontiers
up to an optimal one; 
and finally for proving that there is indeed no better solution possible.

\end{enumerate}

The first reason is specific for BHPA and was incidentally resolved by some of the technical improvements introduced in the related algorithm BS* 
%in 
by Kwa \citeyear{Kwa_89}.
The second issue, however, is also the major obstacle for efficiency of BS* and actually for any bidirectional search algorithm that performs heuristic {\it front-to-end} evaluations,
i.e., evaluations that estimate the minimal cost of some path from the evaluated node on the search front to $t$.
Note, that this is the kind of evaluations also performed by typical unidirectional search.

%\sloppy
Because of the common belief in the missile metaphor, however, so-called wave-shaping algorithms were developed 
by de Champeaux \citeyear{de_Champeaux_83}, de Champeaux and Sint \citeyear{de_Champeaux_and_Sint_77}, and Politowski and Pohl \citeyear{Politowski_and_Pohl_84},
with the idea to steer the search ``wave-fronts'' together.
% \cite{de_Champeaux_83,de_Champeaux_and_Sint_77,Politowski_and_Pohl_84}.
In contrast to BHPA and BS*, these algorithms perform {\it front-to-front} evaluations,
i.e., evaluations that estimate the minimal cost of some path from the evaluated node on one search front to the nodes in the opposing front.
In fact, these algorithms achieve large reductions in the number of nodes searched 
%--- while having other severe problems --- 
compared to algorithms that perform {\it front-to-end} evaluations.
However, they 
are either excessively
computationally demanding, or they have no restriction on the solution quality.
Still,
where do these reductions in the number of nodes searched using {\it front-to-front} evaluations come from?
After all, 
%When 
the algorithms performing {\it front-to-end} evaluations do not suffer from the problem of search frontiers passing each other.
%the question may arise where these reductions in nodes searched come from.
%\fussy


In order to answer this important question, let us shortly focus on a common property of heuristic evaluation functions that estimate the minimal cost of some path 
%to $t$ 
by
applying heuristic knowledge to the {\it static} information encoded in the state information of the node evaluated.
Such
static evaluation functions typically evaluate with some error, i.e., the difference between the minimal cost of a path and its heuristic estimate is in most cases greater than zero.
%With increasing cost also the error increases on average.
%Some quantitative data about this error of the Manhattan distance heuristic in the 8-Puzzle can be found in \cite{Davis_et_al_89,Gaschnig_79}.
An approach to improve the accuracy of a given static evaluation function is to perform a 
%bounded look-ahead 
search and to utilize its results.
%For instance, {\it minimin look-ahead search} (as employed by RTA* \cite{Korf_90}) evaluates the nodes at the horizon of a fixed-depth search using the given static evaluation function.
%It backs up these values to the root node of this search taking always the minimum.
%The backed-up values are mostly better estimates of the real cost than the static values\footnote{
%An analysis of the effects of bounded look-ahead search in this context and in game playing can be found in \cite{Kaindl_and_Scheucher_92}.
%It includes a result about minimin search stating that its improvements with increasing search depth actually depend on a reduction of the error of the static evaluation function with decreasing distance to a goal node.}.
%We can view the bounded look-ahead search as an evaluation function.
%Since this function employs search itself which investigates changes, 
Since this involves dynamic changes, we call it a {\it dynamic} evaluation function.
Dynamic evaluations through bounded look-ahead search were studied in various contexts 
%in 
by Kaindl and Scheucher \citeyear{Kaindl&Scheucher_92}.


The static evaluation errors are typically smaller for paths with smaller cost, as also observed 
%in 
by Pearl \citeyear{Pearl_84}.
{\it Front-to-front} evaluations are therefore typically more accurate than {\it front-to-end} evaluations.
In addition, the costs of the paths from the nodes on the opposing search frontier to $t$ 
(or $s$, respectively)
are 
%partly even exactly 
known, and so the overall evaluations by the 
{\it front-to-front}
%wave-shaping 
algorithms are much more accurate than {\it front-to-end} evaluations.
Since the former utilize the results of the search in the opposing direction, we may view this as an approach 
%The effect of wave shaping is not so much steering the search fronts together, but rather
to dynamically improving heuristic values from the static evaluation function.
Due to this 
%yet unrecognized 
asset, wave-shaping algorithms achieve large reductions in terms of nodes generated
since they perform {\it front-to-front} evaluations.
However,  
they are quite expensive in terms of running time (per node examined),
which calls for finding an appropriate balance.
In fact,  
Dillenburg and Nelson \citeyear{Dillenburg_and_Nelson_94} as well as Manzini \citeyear{Manzini_95} developed
a more recent non-traditional approach to bidirectional search called {\it perimeter search} 
that
achieves exactly this.
% \cite{Dillenburg_and_Nelson_94,Manzini_95}.


We devised a new 
and computationally 
much
cheaper
approach to dynamic improvements that we call 
{\it difference} approach.
It utilizes differences of known costs and their heuristic estimates from a given evaluation function to improve other heuristic estimates from this function.
%We devised a {\it difference} approach, that utilizes some known errors of heuristic values of a given evaluation function to improve other heuristic estimates from this function.
This difference approach 
%is universal in the sense that it 
can be applied in 
%a wide variety of known search algorithms.
bidirectional heuristic search algorithms that perform heuristic {\it front-to-end} evaluations.
It is exemplified in two new methods for dynamic improvements of heuristic evaluations during search.


We also devised a new approach to bidirectional heuristic search that performs heuristic {\it front-to-end} evaluations, where these dynamic improvements of heuristic evaluations during search can be embedded efficiently and effectively.
This approach is generic in the sense that it encompasses a whole class of (non-traditional) bidirectional search algorithms.
As we show in this paper, it can be instantiated for the case of the availability of sufficient memory as well as for the case of limited memory.
%This form of bidirectional heuristic search can also work with limited memory.

%bidirectional heuristic search can be performed very efficiently with limited memory.


Our 
%empirical 
results from experiments suggest that
bidirectional heuristic search can improve on unidirectional heuristic search with respect to both generated nodes and running time (for certain problems of finding optimal solutions).
Since the missile metaphor is wrong, bidirectional heuristic search can do so using our approach {\it without} the very time-consuming {\it front-to-front} evaluations.
%	Point sentence(s):
%We show that 
So, bidirectional heuristic search is viable and 
we
propose that it be reconsidered.


%Overview
This paper is organized in the following manner.
First, we discuss previous work and present some new theoretical and empirical results on existing approaches to bidirectional heuristic search. 
Then we describe our new generic approach to non-traditional bidirectional search and two of its instantiations.
Thereafter we propose a new approach to dynamically improving heuristic values that is based on differences between known costs and heuristic estimates.
After the presentation of experimental results from applying these approaches, we discuss them in the context of the various approaches to bidirectional heuristic search that were previously proposed.





\section{Previous Work}
%%%%%%%%%%%%%%%%%%%%%%%


In order to make this paper self-contained, we sketch here 
the 
essentials of 
%the 
previous work 
on heuristic search algorithms with a focus
on bidirectional heuristic search, without going into more detail than necessary to understand both our new results on this previous work and our new approaches.



\subsection{Unidirectional Heuristic Search Algorithms}


Many unidirectional search algorithms have been presented, so it would be prohibitive to review all of them here.
Rather, we focus on those unidirectional algorithms that form the basis of bidirectional search as discussed in this paper.
%We refer to selected previous work on {\it unidirectional} search below in the results and the discussion sections. 
First, we review the traditional {\it best-first} search algorithm A* \cite{Hart_et_al_68}.
Then, we shortly explain the linear-space algorithm IDA* 
(iterative-deepening-A*) 
%\cite<iterative-deepening-A*;>
proposed by Korf
\citeyear{Korf_85}.
Finally, we review an algorithm called {\it Trans}  \cite{Reinefeld_and_Marsland_94} that implements a form of enhanced iterative-deepening search.


A* maintains the set {\open} of so-called {\it open} nodes that have been generated but not yet expanded, i.e., the frontier nodes.
Much as any best-first search algorithm, it 
always
selects 
%at each cycle 
a node from {\open} with minimum estimated cost, one of those it considers ``best''.
This node is expanded and moved from {\open} to {\closed}.
A* specifically estimates the cost of some node $n$ with an evaluation function of the form $f(n) = g(n) + h(n)$, where $g(n)$ is the (sum) cost of a path found from $s$ to $n$, and $h(n)$ is a heuristic estimate of the cost of reaching a goal from $n$, i.e., 
the cost of
an optimal path from $s$ to some goal $t$.
If $h(n)$ never overestimates this cost (it is said to be {\it admissible}) 
and if a solution exists,
then A* is guaranteed to return an optimal (minimum-cost) solution (it is also said to be {\it admissible}).


Under certain conditions, A* is optimal over admissible unidirectional heuristic search algorithms using the same information, in the sense that it never expands more nodes than any of these \cite{Dechter_and_Pearl_85}.
We emphasize here that
this optimality result of A* only compares 
it with
{\it unidirectional} competitors, so a {\it bidirectional} approach may 
well
improve on the performance of A*.
The major limitation of A* is its memory requirement, which is proportional to the number of nodes stored and therefore in most practical cases exponential.


IDA* was designed to address this memory problem, while using the same heuristic evaluation function $f(n)$ as A*.
IDA* performs iterations of {\it depth-first} searches.
Consequently, it has linear-space requirements only.
Although performing depth-first searches iteratively deeper and deeper has been heavily used in computer chess programs in the context of {\it alpha-beta minimax} search since the sixties and is still in use 
%(see \cite{Kaindl_90}), 
\cite<see>{Kaindl_90},
the application of this approach in problem-solving searches marked a breakthrough for solving more difficult problems.
IDA*'s depth-first searches are guided by a threshold that is initially set to the estimated cost of $s$; the threshold for each succeeding iteration is the minimum $f$-value that exceeded the threshold on the previous iteration.


While IDA* shows its best performance on trees, one of its major problems is that in its pure form it cannot deal with duplicate nodes in the sense of {\it transpositions}.
A transposition arises, when several paths lead to the same node,
and such a search space is represented by a {\it directed acyclic graph} (DAG).
This disadvantage of IDA* relates to its advantage of requiring only linear space.


Fortunately, most computers have more memory available than needed for IDA*.
This memory can be utilized for recognizing duplicate nodes in two ways,
using a {\it finite state machine} \cite{Taylor_and_Korf_93}, or a {\it transposition table} implemented as a hash table \cite{Reinefeld_and_Marsland_94}. 
Due to its more general applicability in a wider variety of domains, and since our bidirectional algorithms partly make use of it, we focus on the latter technique.


The algorithm Trans 
%presented in \cite{Reinefeld_and_Marsland_94} 
proposed by Reinefeld and Marsland \citeyear{Reinefeld_and_Marsland_94}
uses a transposition table for IDA*.
Since the size of such a table can be deliberately parameterized, this is an approach to utilizing limited memory.
Analogously to earlier applications of transposition tables in computer chess programs, Trans utilizes its table actually for two purposes:

\begin{itemize}

\item	for recognizing transpositions;

\item	for caching the best heuristic values acquired dynamically.

\end{itemize}

Since the latter use is more difficult to understand, we explain its underlying idea in more depth.
This {\it back-up} idea is illustrated in Fig.\ \ref{backup}.
When during the normal search 
the
nodes $B_i$ are statically evaluated but not stored, these values can still be used by backing them up to some node $A$ that is stored --- in the case of Trans in its transposition table.
The {\it dynamic} value of $A$ is the minimum of the estimated costs of the best  paths found through the nodes $B_i$.
Unless the static evaluator is consistent, it is useful to store the maximum of the dynamic and the static value of a node.
When such a cached node is re-searched, an improved value can often be used instead of the value assigned directly by the static evaluation function.



\begin{figure}[t]
\vspace*{-141.5mm}
\hspace*{-13mm}
\centerline{\psfig{figure=d_backu1.eps,width=241mm,clip=}}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_backu1.eps,clip=}}
\vspace*{-162mm}

\caption{An illustration of the {\it back-up} idea.}

\label{backup}
\end{figure}


Apart from its use in Trans, 
this back-up idea is 
actually
widely applied in many algorithms like
MA* \cite{Chakrabarti_et_al_89}, 
MREC \cite{Sen_and_Bagchi_89}, 
RTA* \cite{Korf_90},
SMA* \cite{Russell_92}
and
ITS \cite{Gosh_et_al_94}.
% and
%Trans \cite{Reinefeld_and_Marsland_94}.
Its advantages are 
very little overhead
and steady (though often modest) improvement with increasing memory size.
% + useful also for problems with several goal nodes
In addition, 
%it 
this idea also works when a goal condition instead of a goal node is specified, i.e., it does not require that a goal node is explicitly given.
However, it is 
only applicable for re-searched and cached nodes,
and we cannot see how it could make sense in the context of traditional best-first search like A*.





\subsection{The Traditional Approach to Bidirectional Heuristic Search}


First, we look at the older approach to bidirectional heuristic search where forward and backward searches alternate.
We call this 
%here 
the traditional approach.
It encompasses both algorithms performing {\it front-to-end} and others performing {\it front-to-front} evaluations.



\subsubsection{Front-to-end Evaluations}


Since the first proposed algorithm on bidirectional heuristic search called BHPA \cite{Pohl_71} performed {\it front-to-end} evaluations, let us begin with this approach.
It employs
heuristic evaluation functions $h_d(n)$ 
that
estimate the cost of an optimal path 
from the evaluated node $n$
to 
%the appropriate endpoint 
$t$ or $s$, respectively, depending on the search direction $d$.
More precisely, 
%(i.e., 
$h_1(n)$ 
%uses 
estimates the cost of an optimal path from $n$ to
$t$ 
%as the target for 
in
the forward search, and $h_2(n)$ 
%uses 
%analogously to
from 
$s$ 
to $n$
%as the target for 
in
the backward search.
Note, that always 
%the 
an optimal path from $s$ to $t$ is to be found 
(i.e., {\it not} from $t$ to $s$)
and therefore also the cost of such a path is estimated by the evaluation function $f_d$ that uses $h_d$ as its heuristic component.
From the viewpoint of the backward search that targets node $s$, however, it may seem that the cost from its frontier to $s$ is estimated heuristically, while it is more precisely the cost from $s$ to the frontier.
This issue matters when the cost of some path is {\it not} the same in either direction.


We can view 
%such 
a 
BHPA
search essentially as two A*-type searches in opposite directions,
i.e., traditional {\it best-first} searches.\footnote{More precisely,
%The origin is clearly BHPA \cite{Pohl_71}, 
%which can be intuitively 
BHPA can be 
viewed to consist of two HPA searches 
\cite{Pohl_70} 
in opposing directions. As long as the heuristic function used is consistent
and its values are weighted equally as the $g_d$-values, 
the only relevant difference is a check whether {\open} has become empty.
%we can ignore the specific differences for our discussion here.
For {\it admissible} but not {\it consistent} heuristic functions, 
the option to move nodes back from {\closed} to {\open} is important, if a new better
$g_d$-value is found.
%\footnote{
A heuristic function is {\it consistent} if
$h_d(m) \le  h_d(n) + k_d(m,n)$ for all nodes $m$ and $n$.
This implies that $h_d$ is {\it admissible}, i.e., the heuristic function never overestimates the real cost.}
%}
These are performed quasi-simultaneously, i.e.,
on a sequential machine one node is expanded after another, but the search direction is changed 
(at least) 
from time to time.
The decision for searching in the forward or backward direction is made anew for each node expansion according to the 
{\it cardinality criterion} \cite{Pohl_71}:

\vspace*{5mm}
{\bf if} $|\open_1| \le |\open_2|$ {\bf then} $ d \gets 1$ {\bf else} $d \gets 2$
\vspace*{5mm}


Whenever the search frontiers meet
at some node $n$, 
a solution is found.
Its cost is $g_1(n) + g_2(n)$, i.e., the cost of the path found by the forward search from $s$ to $n$, plus the cost of the path found by the backward search from $n$ to $t$.
%%%%In contrast to a typical admissible algorithm like A* or IDA*, however, 
Even when the two parts of such a solution of the forward and the backward search are optimal, however, the concatenated solution path is not necessarily optimal.
Therefore, such an algorithm requires a special termination condition for guaranteeing optimal solutions.
The termination condition of BHPA is as follows: 
%\begin{small}
\begin{eqnarray}
L_{min} \le \max
[\min_{x \in {\open} _1} f_1(x), \min_{x \in {\open} _2} f_2(x)]
\label{m:TC1}
\end{eqnarray}
%\end{small}
This condition essentially means that the cost 
$L_{min}$
of the best (least costly) complete path from $s$ to $t$ found so far is not larger than an estimate computed from the $f_d$-values in both search frontiers.
If the heuristic used for these estimates is admissible,
this path must already be an optimal solution in order to satisfy this termination condition.
Since understanding this condition is important for this paper, we elaborate 
%on 
it in more depth below.


Implicitly this is also the condition for successful termination of the improved algorithm BS* \cite{Kwa_89}, which removes all nodes $n$ whose $f_d$-values are 
$\ge L_{min}$ and terminates when {\open}$_1$ or {\open}$_2$ is empty.
This technique of removing nodes is called {\it trimming} in BS*, and such newly generated nodes are not placed into the sets of open nodes at all, which is called {\it screening}.
While these techniques improve on BHPA ``just'' with respect to saving memory, BS* additionally includes improvements that reduce the number of nodes generated.
%Due to its major improvements over BHPA, BS* can avoid to explore part of the search space twice as BHPA does.\footnote{
These major improvements are the following: 

\begin{itemize}

%(i) 
\item	{\it nipping}: if a node is
selected for expansion which is already in 
%the 
{\closed} 
%list of 
in
the opposite search tree,
it can just be put into 
%the 
{\closed} 
%list of 
in
the current search tree {\it without} expansion;

%(ii) 
\item	{\it pruning}: in the
same situation, descendants of this node in 
%the opposing 
{\open} 
%list 
in the opposite search tree
can be removed.

%\dots trimming \dots ???

\end{itemize}
%} 


Both BHPA and BS* are {\it admissible} if $f_d$ is {\it consistent}.
However,
BHPA's results
%is 
were 
clearly less efficient than 
those of
A* for finding optimal solutions, and also BS* was never shown to be really more efficient than A*.


K\"{o}ll and Kaindl \citeyear{Koell_and_Kaindl_93} were the first to conjecture that the missile metaphor is misleading as an explanation and provided some (preliminary) evidence for this finding.
Based on it
and realizing that fulfilling 
the termination 
condition (\ref{m:TC1}) is a key issue, 
they developed efficient $\varepsilon$-admissible search algorithms, that typically find solutions with a known error bound faster and generate fewer nodes than a corresponding derivative of A* that guarantees the same error bound.
These algorithms provided, however, no improvements for finding optimal solutions, and they require exponential space like BHPA, BS* and A*.


Based on the same approach, Kaindl and Khorsand \citeyear{Kaindl_and_Khorsand_94} showed that 
%also finding optimal solutions 
%to difficult problems 
%is possible rather efficiently through 
bidirectional heuristic search using limited memory is possible through using a unidirectional search algorithm that can cope with limited memory --- SMA* \cite{Russell_92}.
However, the  
%in terms of 
runtime 
efficiency
was insufficient.




\subsubsection{Front-to-front Evaluations}


Since for a long time there was consensus about the belief that the search frontiers would pass each other, research focused on algorithms that would force the ``wavefronts'' to meet through ``wave-shaping'' techniques:
%Wave-shaping techniques like those used in 
BHFFA \cite{de_Champeaux_and_Sint_77}, BHFFA2 
\cite{de_Champeaux_83},
d-node retargeting
\cite{Politowski_and_Pohl_84}
and 
%Davis  presented 
a generalized algorithm (encompassing
%containing 
BHPA and BHFFA2) \cite{Davis_84}.
%and analyzed it theoretically
These algorithms
perform {\it front-to-front} evaluations
and
they
show that bidirectional heuristic search
can be 
%rather 
efficient
%, especially 
in terms of the number of
%expanded 
nodes generated.



\begin{figure}[t]
\vspace*{-142.5mm}
\hspace*{-19mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_ftof1.eps,width=245mm,clip=}}
\centerline{\psfig{figure=d_ftof1.eps,width=245mm,clip=}}
\vspace*{-166.5mm}

\caption{An illustration of the {\it front-to-front} idea.}

\label{ftof}
\end{figure}



%The idea of the {\it front-to-front} method is illustrated in
Since the basic idea 
of {\it front-to-front} evaluations
is important for understanding this paper, we illustrate it using Fig.\ \ref{ftof}.
When for the evaluation of some node $A$ 
the
nodes $B_i$ on the opposite search front are available in storage, the costs of optimal paths from $A$ to every $B_i$ can be estimated.
Adding these to known costs of paths from $B_i$ to the goal node $t$, normally more accurate dynamic estimates can be gained than from a static {\it front-to-end} evaluator
that directly estimates the cost from $A$ to $t$.

However, the algorithms performing {\it front-to-front} evaluations are either excessively
computationally demanding, or they have no restriction on the solution quality.
%\footnote{Wave-shaping has 
They have
to compute heuristic estimates 
between all nodes in one search frontier and all nodes in the other,
in order to estimate all the paths going through all nodes in the opposite frontier and vice versa.
So, 
%, i.e., 
their effort for the evaluations needed for a single node selection and expansion 
%is 
may even seem to be
proportional to the cross product of the numbers of nodes in 
%the 
both
frontiers.
%}.
Through the use of appropriate data structures, this effort can be reduced to become proportional to the number of descendants of the expanded node times the size of the opposite search frontier.\footnote{
According to personal communication with Dennis de Champeaux.}
Still, this is excessively computationally demanding for frontiers that may contain in the order of millions of nodes.
%In order to keep 
For keeping
this effort practical for non-trivial problems, such an algorithm may either restrict this computation to a certain (small) number of nodes with promising values or keep the search direction focused on a single target node of the opposing frontier for several steps before retargeting it.
Both approaches 
typically terminate with non-optimal solutions and therefore obviously lose admissibility,
%imply the loss of admissibility, 
i.e, the guarantee for finding optimal solutions.





\subsection{The Non-traditional Approach to Bidirectional Heuristic Search}


So, the traditional approaches did not succeed to improve on unidirectional search
for finding and guaranteeing optimal solutions.
In particular, all these algorithms are based on traditional best-first search that has exponential storage requirements.
It may seem that bidirectional search needs to store nodes of 
at least
one frontier so that the search from the opposing side can recognize meeting this frontier (typically implemented through some hashing scheme).
Instead of storing both frontiers for having forward and backward searches alternate, it is possible to search in one direction first storing nodes, and then to search in the other direction.
We call this here the non-traditional approach to bidirectional heuristic search.

Such an approach is 
the
{\it perimeter search} \cite{Dillenburg_and_Nelson_94,Manzini_95}.
In perimeter search, a breadth-first search generates and stores all the nodes around $t$ up to a predetermined (and fixed) {\it perimeter depth}.
The final frontier of this breadth-first search is called {\it perimeter}.
After this search is finished and the nodes are stored, a forward search starts from $s$, targeting all of the perimeter nodes.
Depending on the given problem and the available storage, this forward search can be performed in an A* or IDA* fashion.
The former is implemented in PS* \cite{Dillenburg_and_Nelson_94}, and the latter both in IDPS* \cite{Dillenburg_and_Nelson_94} and in BIDA* \cite{Manzini_95}.
For the same perimeter depth, IDPS* and BIDA* search exactly the same nodes.
%But 
%through utilizing the consistency of a given heuristic function,
However, BIDA* temporarily removes from the perimeter the nodes that cannot affect the computation of its evaluation function and consequently reduces the number of heuristic {\it front-to-front} evaluations compared to IDPS*.
Due to this improvement,
BIDA* is far more efficient in terms of running time than IDPS*. 
%by avoiding many of the {\it front-to-front} evaluations from the IDA* frontier to the stored perimeter.

%Especially 
BIDA* achieves very good results in the (sliding-tile) Fifteen Puzzle domain.
We investigate below why this is the case in contrast to the traditional approaches to bidirectional heuristic search.
In particular, we show the results of experiments with varying perimeter depth, i.e., varying perimeter size or storage use.


%uses wave shaping

%from one side only





\section{Some New Results on the Previous Approaches}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Still, it seems that these previous approaches to bidirectional heuristic search are not understood properly.
Therefore, we present some new results about them before we propose our new approaches.



\subsection{Theoretical Results}


We present some new theoretical results on bounds on the number of nodes expanded by traditional bidirectional heuristic search with {\it front-to-end} evaluations.
% in the form of BHPA and partly BS*.
Since 
its
%their 
runtime performance is proportional to the number of nodes expanded, these are bounds on the potential efficiency.
% of BHPA and BS*.
%We show here some new theoretical results on traditional bidirectional heuristic search with {\it front-to-end} evaluations.
We assume the availability of a consistent heuristic evaluation function  
$h_d$ in both directions.

%%%% example that wave shaping cannot generally dominate A* in terms of node expansions?!


First we make explicit a principally known result in the form of a lemma,
since we 
%will 
need this particular result for proving the new results.
In addition, 
understanding it is important for understanding these results.
Note, however, that this termination condition for bidirectional search is significantly different from termination conditions for unidirectional search like A* as given 
%in 
by Pearl \citeyear{Pearl_84}.


\lemma{ {\em (a sufficient condition for successful termination of }BHPA {\em or }BS*{\em ):} 

If there is a solution path from $s$ to $t$, BHPA or BS* 
%will 
terminate successfully (i.e., by finding such a path) iff both the following conditions are satisfied:

(i) in at least one of the search frontiers $d$ of BHPA or BS* the minimum $f$-value must have been raised at least to the value of an optimal solution $C^\ast$, that is,
$\min_{x \in {\open} _d} f_d(x) \ge C^\ast$; and

(ii) an optimal solution must have been found, that is, $L_{\min} = C^\ast$.
}

\proof{
We need not be concerned about whether these algorithms indeed find optimal solutions, since the corresponding proofs 
%can be found in 
were given by Pohl \citeyear{Pohl_71} and Kwa \citeyear{Kwa_89}, respectively.
We only focus here on how exactly the termination condition in Formula (\ref{m:TC1}) is fulfilled --- for BHPA this is the explicit termination condition, for BS* it is implicit as 
%argued 
explained above.
The minimum $f$-values of ${\open} _d$ are at first the values $f_1(s)$ and $f_2(t)$, respectively.
Since $f_d$ is consistent they do not exceed $C^\ast$.
The minimum $f$-values of ${\open} _d$ 
%will only gradually be increased 
increases only gradually
until all the nodes with $f$-values $< C^\ast$ 
of at least one search frontier
are expanded (or nipped or pruned by BS*).
%their maximum becomes $\ge C^\ast$.
Since the maximum of the minimum $f$-values of ${\open} _d$ is used, only one but at least one of them must become $\ge C^\ast$.
During the search, $L_{\min} \ge C^\ast$ 
%will 
always holds, and when an optimal solution is found, $L_{\min} = C^\ast$. \hfill $\Box$
}


In order to establish bounds on the number of node expansions, let us first focus on an upper bound on the number of nodes expanded by BHPA.


\theorem{ The number of node expansions of BHPA can be bounded from above by
\begin{eqnarray*}
\#(\bhpa) < \#(\astern)_1 + \#(\astern)_2
\end{eqnarray*}
}
\proof{ In the worst case, BHPA may have to perform its A*-type searches in both directions completely, with the exception of at least one node expansion.
Even when $L_{min} = C^\ast$ is achieved only in the last node expansion in one direction, immediately thereafter the termination condition is fulfilled according to Lemma 1. Therefore, 
in the opposite direction at least one node expansion can be saved.
 \hfill $\Box$
}


In some sense, this bound may look quite weak, but 
actually
%the conjecture can be found 
%in 
Nilsson \citeyear{Nilsson_80} 
conjectured
that a bidirectional heuristic search may expand twice as many nodes as would a corresponding unidirectional one.
This conjecture was based on the assumption originally published 
%in 
by Pohl \citeyear{Pohl_71} that the search frontiers may pass each other without intersecting.

More recently, however, some empirical evidence was found 
by K\"{o}ll and Kaindl \citeyear{Koell_and_Kaindl_93}
that this assumption is invalid, i.e., the frontiers typically meet rather early even without using wave-shaping techniques.
So, the question may arise 
as to
whether and under which conditions the result of Theorem 3.1 is reasonable and useful.
In order to show such conditions, we define a 
strong
symmetry
property of search spaces.
Although this may seem to be a
completely
unrealistic assumption, it is not too difficult to imagine a search space with this property.
Searches for optimal solutions to TSP (traveling salesman problem) instances need to generate nodes that represent visiting 
%of 
all the neighboring cities of the start city.
Since this same city is also the final city to be visited, a reverse search in the opposing direction needs to generate nodes for exactly the same cities, etc.
So, at least a straight-forward implementation of bidirectional search for the TSP works in a symmetric space.
For symmetric TSP instances (where the arc costs are the same independent of the direction) 
and for usual heuristic evaluations functions for the TSP (like the minimum spanning tree heuristic),
it turns out to be a {\it perfectly A*-symmetric} search space.



\definition{ Let $f^1_1 = h_1(s), f^2_1, \dots, f^{k-1}_1, f^k_1 = C^\ast$ be the different $f$-values of expanded nodes in the forward direction and analogously $f^1_2 = h_2(t), f^2_2, \dots, f^{k-1}_2, f^k_2 = C^\ast$ in the backward direction.
A search space is {\em perfectly A*-symmetric} iff A* expands the same number of nodes for each $f$-value in the forward direction as in the backward direction, that is, $\#^j(\astern)_1 = \#^j(\astern)_2$ for each $j=1\dots k$. \hfill $\Box$
}



\theorem{ If the search space is {\em perfectly A*-symmetric} and the $f$-values are all distinct in each direction, then
\begin{eqnarray*}
\#(\bhpa) = 2 \cdot \#(\astern) - \delta \hbox{ with } 1 \le \delta \le 3
\end{eqnarray*}
}
\proof{ 
In a perfectly A*-symmetric search space, the numbers of nodes expanded in both directions by the A*-type searches within BHPA is strictly the same up to the last but 2 $f$-values, because no termination is possible up to this point; and since these are all distinct in each direction, this amounts to 2 nodes each for the remaining 2 $f$-values:
\begin{eqnarray*}
\#(\astern)_1 - 2 = \#(\astern)_2 - 2
\end{eqnarray*}
Depending on when $L_{min} = C^\ast$ is achieved, 1 up to 3 more nodes must be expanded to fulfill the termination condition.
Summing up proves the theorem. \hfill $\Box$
}


Since in practice the $f$-values are normally not all distinct (in each direction), we show the consequence of a more realistic assumption --- the occurrence of many different $f$-values.
This is meant in the sense that the number of nodes with the same $f$-value is small compared to the number of nodes expanded.


\corollary{ If the search space is {\em perfectly symmetric} and there are many different $f$-values, then
\begin{eqnarray*}
\#(\bhpa) \approx 2 \cdot \#(\astern)
\end{eqnarray*}
}
\proof{ Since there can be several nodes with the same $f$-value, 
the expansion of more than 3 nodes may be saved when an optimal solution has already been found.
Because the number of nodes with the same $f$-value is small compared to the number of nodes expanded, however, $\delta \ll \#(\bhpa)$. \hfill $\Box$
}



So, under this 
strong 
assumption on symmetry BHPA expands close to twice as many nodes as A*.
How is it possible that this conjecture of 
Nilsson \citeyear{Nilsson_80} is supported although its original assumption appears not to be valid?

The point is that the search frontiers of BHPA meet early, i.e., they do {\it not} pass each other without intersecting, but they go {\it through each other}!
So, there is a possibly large region of the search space explored twice (as illustrated in Fig.\ \ref{bidir-illustr}).


%Fig. "through each other"

\begin{figure}[t]
\vspace*{-1.5mm}
\hspace*{68mm}
\centerline{\psfig{figure=a_bs.eps,width=210mm,clip=}}
\vspace*{-221mm}

\caption{An illustration of traditional bidirectional heuristic search with {\it front-to-end} evaluations.}

\label{bidir-illustr}
\end{figure}


BS* avoids such double exploration (see again Fig.\ \ref{bidir-illustr}).
Unfortunately, it appears to be difficult to quantify the size of this region.
So, we cannot determine a tighter upper bound on the number of nodes expanded by BS* without further assumptions.


Fig.\ \ref{bidir-illustr} also illustrates that 
the search frontiers of BS* are typically ``ragged''.
This means that the meetings occur in the ``middle'' as well as near $s$ or $t$
%one or the other of the endpoints
(as observed in our experiments).



Now let us have a look at {\it lower} bounds on the number of nodes expanded by BHPA.
We do not need the assumption on symmetry here but we can show more general results.


\theorem{ The numbers of nodes expanded by BHPA can be bounded from below by
\begin{eqnarray*}
\min(X_1,X_2) + 1 \le \#(\bhpa)
\end{eqnarray*}
where 
$X_d = \#_d(\astern) - \#_d^k(\astern)$
is the number of nodes that $\astern$ would expand in search direction $d$
minus the number of nodes with value $f^k_d = C^\ast$.
}\\
\proof{ This lower bound represents the case of earliest termination according to Lemma 1. (At least 1 node is expanded in each direction.) \hfill $\Box$
}



\corollary{ If the $f$-values are all distinct in each direction, then
the number of nodes expanded by BHPA can be bounded from below by
\begin{eqnarray*}
\min(\#_1(\astern),\#_2(\astern)) \le \#(\bhpa)
\end{eqnarray*}
}
\proof{ $X_d = \#_d(\astern) - 1$ since there is only 1 node $n$ with $f_d(n) = C^\ast$. \hfill $\Box$
}




\corollary{ The maximal improvement of BHPA over $\astern$ is given by 
\begin{eqnarray*}
\#(\astern) - \min(X_1,X_2) - 1.
\end{eqnarray*}
}
\proof{ $\min(X_1,X_2) + 1$ is the minimum number of nodes expanded by BHPA. \hfill $\Box$
}




%\corollary{ The numbers of nodes expanded by BHPA and can be bounded by
%\begin{eqnarray*}
%\min(X_1,X_2) + 1 \le \#(\bhpa) < \#(\astern)_1 + \#(\astern)_2
%\end{eqnarray*}
%}
%\proof{ These bounds have been established in Theorems 3.1 and 3.3. \hfill $\Box$
%}





In essence, we have shown that under certain conditions traditional bidirectional heuristic search with {\it front-to-end} evaluations as exemplified by BHPA 
%and BS* 
can expand close to twice as many nodes as A*.
While the original conjecture for such a result was based on an apparently wrong assumption, we found that another --- even more obvious --- effect is (partly) responsible.


In addition, we have shown that BHPA cannot be much more efficient than A* with respect to node expansions even in the best case.
For a variant of BS* without the {\it pruning} technique, the same lower bound on the number of nodes expanded applies.
In general, the major problem of traditional bidirectional heuristic search with {\it front-to-end} evaluations is the cost of satisfying the termination condition.






\subsection{Empirical Results}

\label{Empirical Results}


In order to provide evidence that the missile metaphor is misleading, we present some new empirical data on the performance of BS*.
Since perimeter search seems to become more and more efficient with increasing perimeter depth \cite{Manzini_95}, we have investigated its behavior through experiments in two different domains.
We present new empirical results from these experiments and provide some explanation why perimeter search works so well in the Fifteen Puzzle domain.



\subsubsection{BS*}


BS* is a classical best-first search algorithm and requires exponential memory.
So, we are not aware of any BS* implementation yet that 
%were 
is able to solve difficult problem instances of the Fifteen Puzzle, given no domain-specific knowledge about the puzzle other than the Manhattan distance heuristic.
In our experiments, BS* was able to solve 59 of the 100 instances 
%from 
used by Korf \citeyear{Korf_85}, having available up to 256 Mbytes of main storage (on a Convex C3220).


We gathered some data during these runs of BS* which provide empirical evidence that the missile metaphor is misleading (in addition to the data already given 
%in \cite{Koell_and_Kaindl_93}
by K\"{o}ll and Kaindl \citeyear{Koell_and_Kaindl_93}).
In the average, BS* found the first solution 
%already 
after the generation of 7.2 percent of the total number of nodes generated.
The quality of this solution is on average just 6.3 percent worse than that of an optimal solution.
After continuing its searches, BS* 
%already 
found optimal solutions after the generation of 22.4 percent of the total number of nodes generated 
(again on average).
That is, most of the search effort of BS* was spent to verify optimality.


That means that the search frontiers of BS* meet relatively early {\it without} the use of wave-shaping techniques, and even optimal solutions are found rather quickly. 
However, even when BS* has already found an optimal solution to some problem instance, it does not ``know'' that this solution is optimal.
So, it must continue the search and generate the remaining nodes in order to prove that there is in fact no better solution available.


Relatively to its overall 
higher
effort, BHPA would find a first solution even ``earlier'' than BS*.
Of course, BHPA needs exactly the same number of nodes as BS* for having its search frontiers meet.
After this first meeting, however, it would have to generate more nodes than BS* because its search frontiers go through each other.
If the search frontiers would, however, pass each other as illustrated by the missile metaphor, solutions could not be found that early.




\subsubsection{Perimeter Search}


Perimeter search achieved very good results in the Fifteen Puzzle domain, where it can solve any Fifteen Puzzle problem instance relatively fast and with limited memory.
However, this approach to bidirectional heuristic search also seems not to be understood sufficiently yet.
So, we made experiments with increasing perimeter depth in two different domains.
The results may seem to be quite surprising.
While we cannot yet explain them theoretically, they are important in their own right, and we try to explain them intuitively.



\begin{figure*}[t]
%\unitlength 1mm
\vspace*{-95mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/StandComp/c_puzzl1.eps,width=210mm}}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/StandComp/c_puzzl1.eps}}
%\centerline{\psfig{figure=c_puzzl1.eps}}
\centerline{\psfig{figure=c_puzzl1.eps,width=184mm}}
\vspace*{-103mm}

\caption{Comparison of BIDA* for different perimeter depths on the Fifteen Puzzle (100 instances) --- time optimum.}

\label{BIDA-puzzl}
\end{figure*}


For these experiments, it was 
%possible 
feasible to use the complete set of 100 Fifteen Puzzle problem instances 
%from 
as used by Korf \citeyear{Korf_85}.
Fig.\ \ref{BIDA-puzzl} shows that in this domain BIDA* works very well, especially in terms of the number of nodes generated.
The data are normalized to the respective search effort of IDA* (in Korf's implementation), since it was the first algorithm able to solve random instances of the Fifteen Puzzle.\footnote{
Just to give an idea of the overall difficulty of the given problem set, note that IDA* generates some 363 million nodes on average, which needs slightly less than half an hour on a Convex C3220.}
Also the running times are very good.\footnote{
BIDA*'s result here is worse than the data reported by Manzini \citeyear{Manzini_95}.
This is primarily due to 
the use of a different machine and
a different implementation that is based on the very efficient code of IDA* for the puzzle 
provided to us
by Korf that we are using.
In such an implementation the overhead especially of wave shaping shows up more clearly even when using the runtime optimizations described 
%in 
by Manzini \citeyear{Manzini_95}.
While we had no access to the implementation by Manzini, in E-mail 
communication with him we were given some hints about it, and there was agreement about the overall effect on the relative running times due to the different implementations of IDA*.}


Consistently with \cite[Table 1]{Manzini_95}, Fig.\ \ref{BIDA-puzzl} shows a steady decrease of both the number of nodes generated and the required running time for increasing perimeter depth until it reaches 16.
At this perimeter depth, however, BIDA* achieves its minimum running time.
The exact perimeter depth where such an optimum occurs may depend on several factors such as the 
machine used and the
efficiency of the implementation.
The new and important finding is, however, {\it that} such an optimum actually exists
for BIDA*.
While an optimum perimeter depth was shown to exist for PS* 
%in 
by Dillenburg and Nelson \citeyear{Dillenburg_and_Nelson_94}, 
the data 
%in 
presented by Manzini \citeyear{Manzini_95} suggested that for increasing perimeter depth the number of evaluations performed by BIDA* even decreases.
For larger perimeter depths, 
however,
the savings in terms of node generation are obviously outweighed by the larger cost of the {\it front-to-front} evaluations.
Note, that the data 
%in 
presented by Manzini \citeyear{Manzini_95} did not show this optimum because of the 
%large 
amount of memory required for storing the perimeter for depths greater than 14 that exhausted the resources available for the experiments reported there.



Knowing about the existence of such an optimum helps us better understand the improvement of perimeter search over the traditional approach to bidirectional heuristic search based on {\it front-to-front} evaluations as exemplified, e.g., by BHFFA.
The advantage of improved evaluation accuracy is to be balanced with the large overhead in time consumption
for node evaluations.
While BIDA* can be tuned towards this optimum, an algorithm like BHFFA is typically out of balance in this regard.
While BHFFA can for this reason only find optimal solutions to quite easy problems, perimeter search
is comparably much cheaper per node searched, since 
%one of its fronts is constant.
a much smaller frontier is ``targeted''.

%much cheaper, but still computationally expensive per node searched



Although the performance of perimeter search cannot be improved deliberately through using more and more memory, the optimum running time of BIDA* for the Fifteen Puzzle problems is very good.
So, 
we wanted to see whether and how such results can also be achieved in another domain which we used for experimenting with our own algorithms.
We made
experiments
%al results for 
of
finding optimal solutions to a set of maze problems.\footnote{
Our use of this domain was inspired 
%by 
through its use 
%in 
by Rao {\it et al.\/} \citeyear{Rao_et_al_91}.
%Since it is not so widely known, we sketch it shortly.
Problem instances in this domain model the task of navigation in the presence of obstacles.
100 instances were drawn randomly using the approach behind the Xwindows demo package Xmaze.
As a heuristic evaluator, we use the Manhattan distance 
%as in 
like Rao {\it et al.\/} \citeyear{Rao_et_al_91}.\\
For our experiments, we made the following adaptations.
In order to allow transpositions, 
%(they arise when different paths lead to the same node), 
we do not ``install'' a wall in three percent of the cases.
This leads to roughly the same ``density'' of transpositions as in the Fifteen Puzzle.
Moreover, we use much larger mazes --- $2000 \times 2000$, and in order to focus on the more difficult instances of these, we only use instances with $h_1(s) \ge 2000$.}
For these
problems, BIDA* based on IDA* is inefficient due to the high number of iterations.
So, we used here PS* \cite{Dillenburg_and_Nelson_94} which implements the common underlying idea --- perimeter search --- based on A*.
While A* works very well for such maze problems, it seems that the runtime optimization of BIDA* cannot be practically used in an A*-based algorithm due to excessive storage requirements,
since for every node in {\open} information about 
%the estimated distance to 
every perimeter node would have to be stored
that may affect the computation of the {\it front-to-front} evaluations.
In fact, Manzini 
\citeyear{Manzini_95}
only states that his technique can be applied to any {\it depth-first} search algorithm.


\begin{figure}[t]
%\vspace*{-70mm}
%\hspace*{-30mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/StandComp/c_maze1.eps,width=140mm,clip=}}
%\centerline{\psfig{figure=c_maze1.eps,width=140mm,clip=}}
%\vspace*{-78mm}
\vspace*{-100mm}
\centerline{\psfig{figure=c_maze1.eps}}
\vspace*{-107mm}

\caption{Comparison of PS* for different perimeter depths on the maze problems (100 instances).}

\label{PS-maze}
\end{figure}



%This seems, however, not to be important in this domain, since 
Based on these experiments, the perimeter search
approach appears not to work satisfactorily as illustrated in Fig.\ \ref{PS-maze} --- neither in terms of generated nodes nor in terms of running time.
The data are normalized to the respective search effort of A*,
%(in Korf's implementation), 
since it seems to be the most efficient algorithm for such problem instances that fit into memory \cite<see also the optimality result of A* over unidirectional competitors by>{Dechter_and_Pearl_85}.\footnote{
Just to give an idea of the overall difficulty of the given problem set, note that A* generates some 2.7 million nodes on average, which needs less than two minutes on a Convex C3220.}
Even for comparably larger perimeter depths (50, 100, \dots, 250), the numbers of generated nodes only marginally improve (up to 93.9 percent of the number of  nodes generated by A*
as shown 
in this figure), while the running time becomes quite high (up to 358.7 percent).
The running time can be reduced for perimeter depths smaller than 25, but for these no real savings in the number of nodes generated and therefore no improvement over A* can be observed.


When considering these very different performances of perimeter search in these domains, the question arises, {\it why} it works so well for the Fifteen Puzzle and why not satisfactorily for the maze.
Let us consider 
%some 
a reason for the good results first, having a closer look at the case of perimeter depth 1.
This minimal perimeter around the node $t$ in the Fifteen Puzzle just contains two nodes.
Still, the perimeter approach saves about half of the node generations of IDA*. 


%Fortunately, t
This major improvement can be explained quite simply when looking at an approach to improving the heuristic evaluation function.
Perimeter search ``discovers'' during the search 
%the same 
an analogous improvement of the Manhattan distance heuristic 
%as 
to that presented 
%in 
by Korf and Taylor \citeyear[p.\ 1203]{Korf_and_Taylor_96} under the name ``last moves heuristic'' (more precisely the part dealing exactly with the very last move).\footnote{
This heuristic is based on the last move of a solution, which must return the blank to its goal position.
In order to allow the blank to this position, those tiles next to the blank in the goal position must be in certain places.
If they are not then the Manhattan distance will not accommodate a corresponding path and can therefore be increased
by two units.}
More precisely, 
in most cases
the dynamic values increase $h_1(n)$ by 
%1
two
units, i.e., 
twice
the (unit) cost of either of the arcs from the two perimeter nodes.\footnote{
This also relates to a property of the Manhattan distance heuristic itself.
In most cases, the increase of the cost through the known arc (with cost 1) is added to an increase of the heuristic estimate from the evaluated node to the perimeter node (also by 1) compared to the estimate to $t$.
In the remaining cases, the heuristic estimate from the evaluated node to the perimeter node reduces (by 1) compared to the estimate to $t$, which cancels out the cost through the known arc.}
Through such improved evaluations, 
many node generations can be saved even when using just very few perimeter nodes.

% $H_1(n) = h_1(n) + 1$

% Fig.\ \ref{ftof}: nodes $B_1$ and $B_2$ with $k = c = 1$


Still, the question remains why such improvements are not observed in the maze domain.
While in both domains the arcs have unit costs, we found some 
%important 
major
differences that help us explain this phenomenon.
Fifteen Puzzle problems have relatively short 
(optimal)
solutions, and due to the unit costs of the arcs the overall cost of a solution is also relatively small (53.1 on average).
In comparison, maze problems (in mazes of the size we used) have relatively long (optimal)
solutions and relatively high cost of 
such
a solution (5262 on average).
These differences are also reflected in differences of the heuristic values (although we used in both domains more or less the same heuristic).
For the given set of Fifteen Puzzle problem instances, $h_1(s) = 37.1$ is on average much smaller than $h_1(s) = 2361$ for the given set of problem instances in the maze domain.
While we do not have data on the heuristic values in the ``Think-A-Dot'' problems as used 
%in 
by Dillenburg and Nelson \citeyear{Dillenburg_and_Nelson_94}, note that the mean path length was given there as 18.4, i.e., even much smaller than for the Fifteen Puzzle.


Let us assume now that in both 
the Fifteen Puzzle and the maze domain 
with the same number of perimeter nodes 
twice
the cost of an arc (i.e., two
units) can be added.
This means that the resulting dynamic evaluation improves on the static evaluation by the same {\it absolute} amount, but by a quite different {\it relative} amount: 5.4 percent for the Fifteen Puzzle compared to 0.08 percent in the maze domain.
So, the dynamic improvement of the heuristic is in effect much higher for the Fifteen Puzzle, which leads to much larger savings in terms of node generations for the same effort through {\it front-to-front} evaluations.

%very few node generations can be saved even when using larger perimeter depths


In summary, for the Fifteen Puzzle just some few perimeter nodes improve the static evaluation, since 
twice
the (unit) costs of their arcs 
or even more
%are often 
is in most cases
simply added.
This has a large effect in this domain where the heuristic values are typically smaller than about 40.
In the maze instances of the size we experimented with, the heuristic values  are two orders of magnitude larger, and therefore many more perimeter nodes would be required to achieve much effect.
These, however, make perimeter search very expensive both in terms of running time and probably also in storage requirement.
%A more in-depth investigation of the advantages and disadvantages of perimeter search can be found in \cite{Kainz_96}.


From these considerations, it should be clear that the effect of {\it front-to-front} evaluations is not so much steering the frontiers together,
but rather to improve the heuristic evaluations dynamically.
In particular, the example of having just two perimeter nodes illustrates both that ``wave shaping'' is not the real effect, but rather improvement of evaluation accuracy.



%see again the illustration of the {\it front-to-front} method in Fig.\ \ref{ftof}


%It typically has an 
%optimum in time efficiency for 
%comparably
%low perimeter depths.


%The runtime optimization presented in \cite{Manzini_95} shifts the optimum to higher perimeter depths which save more node generations.
%This makes it successful for the Fifteen Puzzle (only Fifteen Puzzle results are published yet).

%for other domains no such success is guaranteed, and the applicability of this optimization in traditional best-first search like A* is hindered by large memory requirements for each stored node.






\section{A Generic Approach to Non-Traditional Bidirectional Search}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


We developed a new generic approach to 
bidirectional 
heuristic search that integrates various 
%approaches 
search algorithms
and typically leads to hybrid combinations. 
%of search algorithms.
Since this approach does not allow for changing the search direction more than once, it can be viewed as a non-traditional form of bidirectional search.


%First, we explain the {\it generic approach} generally. Its 
The major steps of our {\it generic approach} are:\footnote{
This approach is different from the one that we proposed 
%in
earlier \cite{Kaindl_et_al_95}.}
%as follows:

\begin {list} {bullet} {\topsep 0.0 cm \itemsep 0.0 cm \leftmargin 0.0 cm \parskip 0.0 cm \labelwidth 0.0 cm \partopsep 0.0 cm}
\begin{enumerate}

\item Assign 
a search direction and 
some or even nearly all of the available
memory to the traditional best-first search. 
%Assign the search directions and the available memory to the 
%%traditional best-first and the linear-space algorithm
%forward and the backward search, respectively.

\item Perform traditional best-first search 
in the assigned direction
using 
the given
memory.

\item Unless the best-first search has already found an optimal solution,
%use a linear-space algorithm 
perform a search
in the reverse direction. 
Use the memory structure built up by the previous best-first search, possibly together with additional memory that is still available,
but compute and use {\it front-to-end} evaluations.

\end{enumerate}
\end {list} 


It would not be too difficult to perceive an even more general approach that subsumes perimeter search.
Because of the expensive {\it front-to-front} evaluations, however, we wanted to devise an approach that avoids the need to find a balance between the cost of such evaluations and their beneficial effect.



\begin{figure}[t]
\vspace*{-75mm}
\hspace*{8mm}
%\centerline{\psfig{figure=ij_c.eps,width=260mm}}
\centerline{\psfig{figure=ij_c2.eps,width=260mm}}
\vspace*{-275mm}
%\caption{An approach to using memory on both sides.}
\caption{A specialization of our generic approach.}
\label{genmem}
\end{figure}



A useful {\it specialization} of our generic approach that uses memory on both sides of the search space is illustrated in Fig.\ \ref{genmem}.
The traditional best-first search uses its assigned memory as usual, e.g., in A*, and the linear-space search uses as much memory as still available in
a transposition table \cite{Reinefeld_and_Marsland_94}.
The former first of all orders the sequence of node generations and 
%helps finding 
finds
transpositions.
The latter 
%is used 
uses its memory
for finding transpositions 
in another part of the search space, 
and 
for
caching more accurate heuristic evaluations closer to 
%the goal
$t$.


%In case of 
When limited memory 
is available, this approach is very flexible. 
For instance, when no memory for a transposition table is assigned, this approach combines linear-space search with conventional best-first search in a bidirectional style.
While this may look quite similar to BIDA*, note that our approach in contrast performs {\it front-to-end} evaluations.
The memory of the best-first search is used 
%to find transpositions also for the reverse search and, even more importantly, 
to find solutions earlier
by meeting its frontier (rather than $t$). 


When sufficient memory is available even for solving the most difficult problem instances in a domain, also the search in the reverse direction may be performed as a traditional best-first search like A*.
After all, A* is under certain conditions and in a certain sense optimal with respect to node expansions \cite{Dechter_and_Pearl_85}.




\subsection{Instantiating for Limited Memory}


First we show how our generic approach can be instantiated 
%for 
%the case of 
when only limited memory 
is available.
Of course, any 
such
instantiation 
%of our generic approach
should make use of any 
available
domain-specific information.
In particular, it should combine those unidirectional search algorithms that best suit the properties of the domain
%(see, e.g., \cite{Rao_et_al_91,Zhang_and_Korf_93}).
\cite<see, e.g.,>{Rao_et_al_91,Zhang_and_Korf_93}.
For example, in some domains IDA* is the choice, while in others {\it depth-first branch-and-bound} \cite{Lawler_and_Wood_66} is much better.
In the case of limited memory, either of them is to be preferred over A*.


Below we will present experimental results on the Fifteen Puzzle,  
a domain that is characterized by having only few distinct cost values.
Under this condition, it is reasonable to select IDA* as a linear-space search algorithm, since difficult problem instances of the Fifteen Puzzle require too much memory using A*, when only the Manhattan distance heuristic is used.
%Moreover, we can assume to have a {\it monotone} evaluation function: the Manhattan distance.
Since A* makes good use of consistent heuristics like this one \cite{Dechter_and_Pearl_85}, we select it for the part of the best-first search.


Based on the key idea of bidirectional search, we let A* and IDA* search in opposite directions in steps 2 and 3 of our generic approach, respectively. 
%Fig.\ \ref{dergen} illustrates 
This instantiation of our generic approach leads to BAI (Bidirectional A* -- IDA*).

%According to the idea of using memory in various ways, 
Optionally,
we may also give the IDA* search some part of the available memory as a transposition table.
Fig.\ \ref{genmem} illustrates this 
%approach generally.
instantiation.
We call this variant of BAI due to the use of this table BAI-Trans.
% (see also Fig.\ \ref{dergen}).


If A* cannot find a solution using the given memory,
then IDA* searches
in the reverse direction
towards the frontier of the prior search.
Since we consider the case of finding {\it optimal} solutions,
this search cannot always terminate immediately after a solution is
found.
A better solution may exist, and the algorithm must find an optimal one and subsequently prove that it is optimal. 



More technically, the IDA* part must be changed slightly. 
Instead of having to find the goal node, a solution
is found whenever the depth-first search meets the frontier
of the opposing A* search. If the cost of this solution is
smaller than the cost of the best solution found so far (or if it
is the first solution found) then its value is stored.
%a variable called $L_{min}$ is
%updated (see line 2 of $DFS$ in Fig.\ \ref{BHW}). 
Of course, the cost of the best solution found so far may
be sub-optimal, 
or the algorithm does not yet know that it is already optimal. 
However, if the stored value
%$L_{min}$ 
does not exceed the
non-overestimating
threshold of the IDA* part, then its depth-first search is exited successfully
with an optimal solution.

%\begin{figure}[t]
%In pseudocode, the algorithm is as follows:
%\vspace{-5mm}
%\input{pseudo-bhw.tex}
%\caption{Pseudocode of BAI.}
%\label{BHW}
%\end{figure}

In addition to these necessary changes, the IDA* part has the advantage to start with an
increased initial threshold based on an {\it admissible}
estimate of the optimal solution cost as determined by the A* part. Since we assume a 
%monotone 
consistent heuristic $h$, the minimum of $f=g+h$ for all nodes in {\open}
is always an admissible estimate. 
%(we call it $gplush_{min}$).
Therefore, if this estimate is higher than 
the usual
initial threshold of IDA*,
then it can be used here instead. 


Moreover, it is not necessary to have the IDA* part search again in the space already explored by A*.
More technically, when the depth-first
search invoked by IDA* meets a closed node of the opposing
A* search frontier, this branch can be cut off (meeting an open node is in general insufficient).
We call this {\it nipping} according to the analogous method described 
%in 
by Kwa \citeyear{Kwa_89}.

%It would even seem that this form of nipping is possible here
%already when meeting {\open},
%i.e., ... !!!!!!!!!!!!??????????.
%In fact, the termination is based on the threshold
%of the linear-space search only,
%and in the stored tree the requirement for proper computation of
%the $\varepsilon$-admissible estimate is fulfilled since reopening
%of nodes is done.
%However, if all $\varepsilon$-admissible solution paths
%lead through edges not yet stored between some nodes in {\open}
%then they would not be uncovered.}
%However, nipping cannot be performed when just meeting {\open} since in this case
%an $\varepsilon$--admissible solution path {\it not} leading through
%{\open} could be missed. ???????????????????????????


In an efficient implementation of the Fifteen Puzzle even the effort of hashing at every node causes an overhead that cannot be ignored.
Therefore, we implemented BAI in such a way that it avoids hashing at those nodes where --- based on the heuristic estimate --- it knows that the frontier of the opposing A* search is 
%yet 
still out of reach.


%Apart from
%the necessary and optional changes described above, the iterative
%deepening part is like the original IDA*. At each
%iteration, it performs a depth-first search, cutting off a branch
%when its $f$-value exceeds the given threshold.
%% $T_n$. 
%The threshold used
%for the next iteration
%% $T_{n+1}$ 
%is the minimum of all values that exceeded the current threshold.

%BAI takes several arguments: the nodes $s_1$ and $s_2$,
%the worst-case bound $\varepsilon$, the factor $\kappa$ guiding
%A*, and the maximum number of nodes to be stored by
%A*. The top-level call to BAI is made on the start
%node, the goal node, the bound and factor chosen by the user, and
%the available memory in terms of the number of nodes.

According to step 1 of our generic approach, the search directions must be assigned to the A* and the IDA* part, respectively.
For traditional bidirectional search,
Pohl \citeyear{Pohl_71}
proposed and used a {\it cardinality criterion}
for the problem of determining the frontier from which to select a
node for expansion:
continue searching from the frontier with fewer open nodes.
While this is utilized for each node expansion
in traditional bidirectional search algorithms, BAI has to
decide this issue once at the very beginning of the whole
search. 

When the search space is sufficiently symmetric, the initial
search direction can be determined at random. 
When the search space is at least slightly asymmetric and no specific
knowledge for determining the search direction is available, it
seems reasonable to make shallow probes into the search space from
both sides and to use the idea 
%of 
behind the cardinality criterion.
Since BAI incorporates IDA*, using this algorithm also for {\it probing} is consistent with the overall approach.
For example in the Fifteen Puzzle, 
the first few iterations of IDA* are searched from both sides,
and the direction with fewer generated nodes
is assigned to the IDA* part of the overall search, since especially for difficult problems it will have to search much deeper than the A* part. 


%generate only very few nodes but already indicate the better search direction %with a relatively high reliability of 80 percent. This direction 




%exact use of $gplush_{min}$ (max(..., UPPER)


%useful in domains with more different values
%like route planning and for $\varepsilon=0$ !?


%use of IE \cite{Russell_92}:


%BHI !?


%useful in domains with more different values
%like route planning and for $\varepsilon>0$ !?



%INFORMAL DISCUSSION OF THE BEHAVIOR OF BAI:

%Due to lack of space, 
Let us shortly
%just informally 
discuss the behavior
of BAI.
In the {\it best case}, it would seem to be the same as
A*.
In fact, BAI can even be better than pure A*. 
BAI assigns the search direction dynamically, which can lead to better
results than systematically going in one direction.
In the {\it worst case}, BAI has to perform the part of
A*, without savings in the IDA*
part (except the effect of nipping).

% available memory must surpass a |critical mass| (quantify??)


A key question is how BAI saves effort
without having enough memory available for
completing the A* search.
Primarily, it can save one or more of IDA*'s iterations.
Due to the better initial threshold, some of the early iterations
can be saved.
Since the earlier iterations are comparably cheap, this helps much less
than saving the last iteration.
%immediate termination after the increase
%of the threshold.
% (in line 7 of BAI in Fig.\ \ref{BHW}).
%The recursive procedure $DFS$ performs the depth-first search
%within the iterations of (the adapted) IDA*.
%It is important to note that a
%(and consequently before a new iteration)
%$L_{min}$ 
The search can also be terminated
{\it after a complete} iteration of IDA* 
if the cost of the best solution already found 
is not larger than the new increased threshold.
%can be used to terminate the search 
%(in line 7 of
%BAI) 
%after the threshold has been increased.
% (in line 10).
Therefore, large savings are possible when BAI terminates 
%one iteration 
earlier than pure IDA*.

%This can happen since it can {\it find} a solution earlier than
%IDA* (because of the stored tree of A*). 

%When a new and better solution is found {\it during} the final iteration, the search may immediately prove that it is
%sufficiently good
%when the cost of this solution is equal to
%the non-overestimating threshold of IDA*.
%Therefore, savings are possible in the final iteration
%searched by BAI through finding a different solution than
%IDA*. In contrast, nipping has normally only second order
%effects on the efficiency.





\subsection{Instantiating for Sufficient Memory}


Now let us sketch how our generic approach can be instantiated for
the case 
%of 
that sufficient memory 
is available in the sense that 
even for solving the most difficult problem instances in a domain,
traditional best-first search can terminate successfully with the given memory.
This case is of interest in order to see whether bidirectional search can be better than A*, which is in some sense optimal over unidirectional algorithms.

%a domain that is characterized by having {\it many} distinct cost values:


When sufficient memory is available, instead of IDA* (or depth-first branch-and-bound) the reverse search can employ A*.
In fact, it is easy to construct such an algorithm analogously to BAI as described above, just by using A* instead of IDA*.
This instantiation of our generic approach leads to BAA (Bidirectional A* -- A*).
This algorithm changes the search direction only once in contrast to BS*.
For 
a
better utilization of our approach to dynamically improving heuristic values based on differences, we will introduce a slight variation of this algorithm below.


%mazes !!!???


%Add-A*

%BDA in Diss p.\ 42






\section{An Approach to Dynamically Improving Heuristic Values based on Differences}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Our new approach to dynamic improvements of heuristic evaluations during search is based on differences between known costs and heuristic estimates.
Such differences are utilized by two concrete methods as presented below.
%Difference approach: Add, Max
The basic idea common to these methods is that for many nodes during the search, the actual cost of a path to or from them is already known.
Since the static heuristic values can normally be gained rather cheaply, the {\it differences} can be computed that signify the error made in their evaluation compared to the cost of the known path.
These differences are utilized to improve other heuristic estimates during the same search.


In order to be able to compute such differences, the search must be bidirectional.
We focus here on 
%the application in 
the context of our non-traditional approach to bidirectional heuristic search described above.
Actually, application is also possible in the context of traditional bidirectional search like BS*.
This involves, however, intricacies that are beyond the scope of this paper.
So, the interested reader is referred to \cite{Kainz_96}.



%These methods 
%%are universal in the sense that they 
%can be employed in a wide variety of known search algorithms.
%We present our new methods and their implementation in some important search algorithms.




\subsection{The {\it Add} Method}


%	Add	(Backward Difference)

The first method instantiates this approach by {\it adding} a constant derived from such differences to the heuristic values of the static evaluation function.
Therefore, we call it the {\it Add} method.

%termination condition \dots

Note, that adding a constant to all evaluations does not change the order of node expansions in a unidirectional search algorithm 
like A*.
% \cite{Hart_et_al_68}.
So, the benefit from this approach may not be immediately obvious.
However, in 
%most 
bidirectional search algorithms
using {\it front-to-end} evaluations, estimates are compared to the cost of the best solution found so far (which is not necessarily already an optimal one), and having better estimates available for such comparisons improves the efficiency due to earlier termination.
We explain in more detail below
how we apply this approach in 
%various search algorithms 
the context of our non-traditional approach to bidirectional heuristic search.



\begin{figure}[t]
\vspace*{-145mm}
\hspace*{-19mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_add1.eps,width=245mm,clip=}}
\centerline{\psfig{figure=d_add1.eps,width=245mm,clip=}}
\vspace*{-163mm}

\caption{An illustration of the {\it Add} idea.}

\label{add}
\end{figure}



%Let us use 
See Fig.\ \ref{add} 
%to explain 
for the key idea of this method.
We assume consistency of the static heuristic evaluator $h_d$.
Around the goal node $t$, a search has examined a part of the graph and
stored all the optimal paths from nodes $B_i$ on its closed fringe to $t$.
For each node $B_i$, its heuristic value $h_1(B_i)$ is computed
and subtracted from the optimal path cost $g_2(B_i) = g^\ast_2(B_i) = h^\ast_1(B_i)$,
%\footnote{
%It is a simplifying assumption for the purpose of presentation here that optimal paths to the nodes $B_i$ must be known during the search.
%Actually it is sufficient that optimal paths from the successors of $B_i$ to $t$ are known.} 
resulting in $\Diff^{\hspace*{.7mm}\ast}_1(B_i)$.
This is actually the error made by the heuristic evaluation of node $B_i$.
The minimum of $\Diff^{\hspace*{.7mm}\ast}_1(B_i)$ for all nodes $B_i$ on the fringe is computed --- we call it $\Mindiff_1$.


The point of the {\it Add} method is that any consistent heuristic value $h_1(A)$ for some node $A$ outside this stored graph underestimates $h^\ast_1(A)$ by {\it at least} $\Mindiff_1$.
We prove this precisely below, but first we need to show a result about $\Diff^{\hspace*{.7mm}\ast}_1$.



\lemma{ If the heuristic $h_1$ is consistent, then 
on any optimal path from some node $n$ to $t$ with an intermediary node $m$
\begin{eqnarray*}
{\Diff^{\hspace*{.7mm}\ast}_1(m)} \le {\Diff^{\hspace*{.7mm}\ast}_1(n)}
\end{eqnarray*}
holds, i.e.,
$\Diff^{\hspace*{.7mm}\ast}_1$ 
can only decrease
%never decreases 
on an optimal path with 
%in
decreasing distance 
%from 
to the goal node $t$.
}\\
\proof{ 
If the heuristic $h_1$ is consistent, then we have
\begin{eqnarray*}
h_1(n) \le h_1(m) + k_1(n,m)
\end{eqnarray*}
%After simple calculations we obtain
From this we simply obtain
\begin{eqnarray*}
g^\ast_2(m) - h_1(m) \le g^\ast_2(m) + k_1(n,m) - h_1(n)
\end{eqnarray*}
Since $n$ and $m$ are on one optimal path to $t$, we know that
\begin{eqnarray*}
g^\ast_2(n) = g^\ast_2(m) + k_1(n,m)
\end{eqnarray*}
After substitutions we obtain
\begin{eqnarray*}
g^\ast_2(m) - h_1(m) \le g^\ast_2(n) - h_1(n)
\end{eqnarray*} 
and equivalently
\begin{eqnarray*}
{\Diff^{\hspace*{.7mm}\ast}_1(m)} \le \Diff^{\hspace*{.7mm}\ast}_1(n)
\end{eqnarray*} 
which proves the lemma. \hfill $\Box$
}


\theorem{ If the heuristic $h_1$ is consistent, then 
it is possible to compute an admissible heuristic $H_1$ for some node $A$ outside the search frontier around $t$ by
\begin{eqnarray*}
H_1(A) = h_1(A) + \Mindiff_1  \le h^\ast_1(A)
\end{eqnarray*}
}
\proof{ When some path exists from node $A$ to $t$, also an optimal path must exist,
and let it go through the frontier node $B_j$.
(If no such path exists, $h^\ast_1(A)$ is infinite and the theorem holds.)
From Lemma 1 and the definition of $\Mindiff_1$ we know that
\begin{eqnarray*}
{\Mindiff_1} \le {\Diff^{\hspace*{.7mm}\ast}_1(B_j)} \le \Diff^{\hspace*{.7mm}\ast}_1(A)
\end{eqnarray*}
Since $\Diff^{\hspace*{.7mm}\ast}_1$ is the error made by the heuristic $h_1$, we can write 
\begin{eqnarray*}
h_1(A) + \Diff^{\hspace*{.7mm}\ast}_1(A) = h^\ast_1(A)
\end{eqnarray*}
After substitution we obtain
\begin{eqnarray*}
h_1(A) + \Mindiff_1  \le h^\ast_1(A)
\end{eqnarray*}
which proves the theorem. \hfill $\Box$
}


\corollary{ $H_1(A)$ is also an admissible estimate if $A$ is a frontier node.
}\\
\proof{ We can replace $A$ by $B_j$ in the proof of Theorem 3.1 without changing its validity. 
\hspace*{5mm} 
\hfill $\Box$
}


\theorem{ If the heuristic $h_1$ is consistent, then 
$H_1
%(A)
$ is consistent.
}\\
\proof{ 
If the heuristic $h_1$ is consistent, then we have
\begin{eqnarray*}
h_1(n) \le h_1(m) + k_1(n,m)
\end{eqnarray*}
Adding the constant $\Mindiff_1$ on both sides leads to
\begin{eqnarray*}
h_1(n) + \Mindiff_1 \le h_1(m) + \Mindiff_1 + k_1(n,m)
\end{eqnarray*}
This means that
\begin{eqnarray*}
H_1(n) \le H_1(m) + k_1(n,m)
\end{eqnarray*}
which proves the theorem. \hfill $\Box$
}



Now let us sketch how this {\it Add} method can be utilized in 
the context of our non-traditional approach to bidirectional heuristic search.
%some important known search algorithms.
When using it 
in BAA, for example,
%based on a unidirectional algorithm like A*, it is necessary to perform an additional search from $t$ before the ``normal'' search starts from node $s$, in order 
the first A* search must be used
to compute some value $\Mindiff_1$
(we assume that it starts from node $t$).
%If this search around $t$ is also guided by a best-first search like A*,
Optimal paths to all nodes within the search frontier are guaranteed but not to all frontier nodes themselves.
If a suboptimal path was found to some frontier node, however, it is known that an optimal path leads through another frontier node with an optimal path to $t$.
So, this does not change $fmin$, since the costs of suboptimal paths cannot influence the minimum.
$\Mindiff_1$ is during the 
%normal 
reverse A* 
search just a constant to be added to $h_1$.
We call the resulting algorithm Add-BAA.


Of course, a larger value of $\Mindiff_1$ is to be preferred for a given amount of search.
So, 
the search starting around $t$ should be better
%this search is actually 
guided by expanding always one of those nodes $n$ with minimal $\Diff^{\hspace*{.7mm}\ast}_1(n)$.
We call this variant here Add-BDA.\footnote{
%In \cite{Kainz_and_Kaindl_96} it was called 
Earlier we called it Add-A* \cite{Kainz_and_Kaindl_96}.}



It is also necessary to check, whether a node to be evaluated is outside or on the fringe of the graph around $t$.
This is simply achieved 
in Add-BAA and Add-BDA
through hashing, which is to be done anyway.
When a node on the fringe 
of the first A* search
is matched, a solution is already found, and when the first node of a path inside the stored graph around $t$ is matched, this path need not be pursued any further, since its optimal continuation is already known.
So, only the evaluator $H_1$ is actually used, which is consistent, and therefore A* does not have to re-open nodes \cite{Pearl_84}.
The search terminates when it selects some node $n$ for expansion with $f_1(n) = g_1(n) + H_1(n)$ 
not
being 
%equal to 
smaller than
the cost of the best solution found so far, which is proven this way to be an optimal one.
%We call the resulting algorithm Add-A*.


%Analogously to A*, IDA* can also utilize the {\it Add} method ???!!!.
%Again, it is necessary first to perform an additional search from $t$, that has an extra storage requirement for this graph.
%In this graph IDA* must perform hashing in addition to its normal procedure. 
%When using such storage around $t$, it is easily possible to utilize it also for another purpose --- finding a solution earlier as implemented in BAI \cite{Kaindl_et_al_95}.
%We call the resulting algorithm Add-BAI.


%!!!???		Add-BS*:
%compute $Mindiff$ on both sides while searching as BS* normally does;
%use it after the first meeting of the search frontiers in the termination condition.
%
%!!!???		Der eine Beweis nimmt an, dass optimale Pfade zu den Knoten $B_i$ bekannt sind,
%BS* garantiert dies aber im allgemeinen NICHT!?


For more details on this method and its theoretical properties 
%and its use in various search algorithms 
we refer the interested reader to \cite{Kainz_94}.





\subsection{The {\it Max} Method}


%	Max	(Forward Difference)

The second method computes its own estimate based on such differences and uses the {\it maximum} of this and the static estimate.
Therefore, we call it the {\it Max} method.




\begin{figure}[t]
\vspace*{-137mm}
\hspace*{-18mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_max1.eps,width=239mm,clip=}}
\centerline{\psfig{figure=d_max1.eps,width=239mm,clip=}}
\vspace*{-157mm}

\caption{An illustration of the {\it Max} idea.}

\label{max}
\end{figure}




%Let us use 
See Fig.\ \ref{max} 
%to explain 
for the key idea of this method.
We assume consistency of the static heuristic evaluator $h_d$,
and that a path from $s$ to $A$ with cost $g_1(A)$ is known.
So we know for its evaluation of node $A$: $h_2(A) \le g_1(A)$.
The difference is $\Diff_2(A) = g_1(A) - h_2(A)$. 
We use this difference for the construction of an admissible estimate $F_1(A)$ of the cost of an optimal path from $s$ to $t$ that is constrained to go through $A$.
Note, that $g_1(A) = g^\ast_1(A)$ is {\it not} necessary, so we call the difference used here $\Diff_2(A)$ instead of $\Diff^{\hspace*{.7mm}\ast}_2(A)$.


In addition, we assume that a search has been performed from $t$ in the reverse direction.
From this search, we assume that from all nodes $B_i$ on its closed fringe
%frontier nodes $B_i$ 
optimal paths to $t$ are known, with cost $g^\ast_2(B_i)$.
Therefore, it is possible to compute 
\begin{eqnarray*}
fmin_2 = \min\limits_i(g^\ast_2(B_i) + h_2(B_i))
\end{eqnarray*}


Based on these assumptions, we can again construct a dynamic evaluation function as follows.


\theorem{ If the heuristic $h_1$ is consistent, then 
it is possible to compute an admissible heuristic $h'_1$ for some node $A$ outside the search frontier around $t$ by
\begin{eqnarray*}
h'_1(A) = fmin_2 - h_2(A) \le h^\ast_1(A)
\end{eqnarray*}
}
\proof{ 
Every path from $A$ to $t$ must go through some frontier node $B_j$.
The cost $C_j$ of any such path is bounded from below as follows:
\begin{eqnarray*}
C_j \ge k_1(A, B_j) + g^\ast_2(B_j)
\end{eqnarray*}
If $h_1$ is consistent, it is possible to estimate the optimal cost of a path between two nodes 
through 
\begin{eqnarray*}
k_1(A, B_j) \ge h_2(B_j) - h_2(A)
\end{eqnarray*}
Therefore, we can write
\begin{eqnarray*}
C_j \ge h_2(B_j) - h_2(A) + g^\ast_2(B_j)
\end{eqnarray*}
Since $fmin_2 = \min\limits_i(g^\ast_2(B_i) + h_2(B_i))$, we can also write
\begin{eqnarray*}
C_j \ge fmin_2 - h_2(A)
\end{eqnarray*}
This is valid for the cost of any path from $A$ to $t$ including an optimal one, and so we can conclude
\begin{eqnarray*}
h^\ast_1(A) \ge fmin_2 - h_2(A)
\end{eqnarray*}
which proves the theorem. \hfill $\Box$
}


\corollary{ $h'_1(A)$ is also an admissible estimate if $A$ is a frontier node.
}\\
\proof{ We can replace $A$ by $B_j$ in the proof of Theorem 3.3 without changing its validity. 
\hspace*{5mm} 
\hfill $\Box$
}


This dynamic evaluation function is not necessarily better for all nodes than the static function, and so it is useful to combine these functions:
\begin{eqnarray*}
H_1(A) = \max (h_1(A), fmin_2 - h_2(A))
\end{eqnarray*}
Since both are admissible the resulting function is also admissible.
When the value $fmin_2$ changes during the search, however, $H_1$ is not consistent.



%In order to show how the
Since in the formula for computing $H_1$ the originally derived 
difference $\Diff_2(A) = g_1(A) - h_2(A)$ is 
%involved in this method
not included, we also derive here the overall evaluation function
\begin{eqnarray*}
F_1(A) = \max (f_1(A), fmin_2 + \Diff_2(A))
\end{eqnarray*}






Now let us sketch how this {\it Max} method can be utilized in 
the context of our non-traditional approach to bidirectional heuristic search.
%some important known search algorithms.
When using it 
in BAI, for example,
%based on a unidirectional algorithm, it is again necessary to perform an additional search from $t$ in order 
the A* search starting first must be used
to compute some value $fmin_2$
(we assume that it starts from node $t$).
%This search can be performed either before or concurrently to the ``normal'' search starting from node $s$.
Again, like in the {\it Add} method, it is not necessary that optimal paths from $t$ to all frontier nodes are known.
For getting values $fmin_2$ that are as large as possible for a given amount of search, the usual strategy of selecting a node with minimal $f_2$ is appropriate here.


%During the normal search, it is again necessary to check, whether a node to be evaluated is outside or on the fringe of the graph around $t$.



%!!!???		Max-A*: was sollen wir dazu sagen?


%IDA* can utilize the {\it Max} method similarly to the {\it Add} method in the compound search algorithm BAI. 
The subsequent IDA* search within BAI 
%It 
must 
%again 
perform hashing in the graph stored around $t$
in order to check, whether 
a node to be evaluated is outside or on the fringe of the graph around $t$.
In the latter case a new solution is found.
%, as BAI does anyway. 
We call the resulting algorithm Max-BAI.
When a transposition table \cite{Reinefeld_and_Marsland_94} is used in addition as in BAI-Trans,
% \cite{Kaindl_et_al_95}, 
we call it Max-BAI-Trans.



%!!!???		Max-IDA* (linear space):

Most interestingly, IDA* can also utilize the {\it Max} method {\it without additional storage requirements}.
Let us sketch the basic approach for such a {\it linear-space} application of this method here.
While IDA* 
normally
%traditionally 
searches in one direction only, we let it alternate the search direction
after each iteration until a solution is found.
Actually, this procedure is outside our generic approach to bidirectional search as presented above.
But we include it here since a linear-space approach is of special interest.
%It computes 
$fmin_i$ 
is computed
in one iteration to be used in the subsequent iteration, which must search in the alternate direction so that it can use this value.
For example, in an iteration searching from $t$ to $s$,
the adapted IDA* computes $hmax_1 = \max (h_1(B_i))$ for all nodes $B_i$.
This value is used as
an estimate in the subsequent iteration for checking, whether a node $A$ to be evaluated is ``outside'':
if $h_1(A) > hmax_1$ is true, then node $A$ cannot be ``inside'' and $H_1(A)$ can be safely used.
This check substitutes hashing in a stored graph.
Since the static heuristic function normally underestimates, however, for some nodes 
the heuristic
$H_1$ is not used although it would theoretically be correct to use it.
We call the resulting algorithm that is based on this idea Max-IDA*.

%several ``levels'' of $fmin$ and the $\max (h(m)$ of the corresponding nodes $m$





%!!!???		Max-BS*:
%welche Variante?
%
%!!!???		Der Beweis nimmt an, dass optimale Pfade zu den Knoten $B_i$ bekannt sind,
%BS* garantiert dies aber im allgemeinen NICHT!?
%
%advantage of large start search: use it;
%advantage of large target search: provide it;
%balance



For more details on this method and its theoretical properties 
%and its use in various search algorithms 
we refer the interested reader to \cite{Kainz_96}.








\section{Results of Experiments with these New Approaches}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


In order to provide some empirical evidence for the effectiveness and the efficiency of our new approaches, we made experiments in two 
% three 
different domains: 
Fifteen Puzzle and 
mazes.
% route planning




\subsection{Fifteen Puzzle}


First let us have a look on specific experimental results for finding optimal solutions to a set of 
%(sliding-tile) 
Fifteen Puzzle problems, once again
the complete set of 100 instances 
%from 
used by Korf \citeyear{Korf_85}.
We compare algorithms that achieve the previously best results in this domain 
with 
our new algorithms.
%one of these algorithms (BAI-Trans) enhanced by our new {\it difference} approach to dynamic improvements of heuristic evaluations.
All the compared algorithms use no domain-specific knowledge about the puzzle other than the Manhattan distance heuristic.\footnote{
With much improved heuristic functions, much more efficient searches result \cite{Culberson_and_Schaeffer_96} and even solving Twenty-Four Puzzle instances has become feasible \cite{Korf_and_Taylor_96}.}
The main storage available on the Convex C3220 used was up to 256 Mbytes.



\begin{figure}[t]
%\vspace*{-74mm}
%\vspace*{-22mm}
\vspace*{-5mm}
%\hspace*{-30mm}
\hspace*{-4mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_puzzl1.eps,width=140mm,clip=}}
%\centerline{\psfig{figure=ai_resul.eps,width=200mm,clip=}}
\centerline{\psfig{figure=ai_resul.eps,width=192mm,clip=}}
%\centerline{\psfig{figure=ai_resul.eps,width=140mm}}
%\vspace*{-79mm}
\vspace*{-194mm}

\caption{Comparison on the Fifteen Puzzle (100 instances).}

\label{puzzl}
\end{figure}



Fig.\ \ref{puzzl} shows a comparison of several algorithms in terms of the
average number of node generations and their running times.
The data are normalized to the respective search effort of IDA* (in Korf's implementation).
%, since it was the first algorithm able to solve random instances of the Fifteen Puzzle.
As already noted above, IDA* needs on average slightly less than half an hour on the machine that we used to find an optimal solution
to one problem instance.
So, even slight improvements mean notable savings in time.


IDA*, Max-IDA* and IDA*-Probing are linear-space algorithms that use no additional storage, and so their performance cannot compete with the algorithms that use up to 256 Mbytes.
%!!!???	Max-IDA* (welche Variante) compared to IDA*:
%Our best variant of 
Max-IDA* generates 
only
54.4 percent of the number of nodes generated by IDA*
due to its dynamic improvements of the heuristic evaluations according to our {\it difference} approach.
Since these, however, imply some overhead per node searched,
it needs 76.1 percent of IDA*'s running time.
%Obviously, it cannot really compete with the algorithms that use additional space, but this result is good for a linear-space algorithm.
%Note also, that it improves relatively more for more difficult problem instances.
IDA*-Probing is a variant of IDA* that just uses our {\it probing} idea for selecting the search direction.
Although the search space of the sliding-tile puzzle appears to be quite symmetric, 
it is interesting to see how much can be gained here just by selecting the search direction dynamically.
Since IDA*-Probing has no overhead in running time, it is even faster than Max-IDA*.
%Moreover, the advantage of IDA*-Probing over pure IDA* is statistically significant.
% in absolute and relative terms.
In order to see how well probing via three iterations already indicates the better search direction, we compared its result with that of a
perfect oracle. Using it would still generate 64 percent of IDA*'s nodes, i.e.,
IDA*-Probing with an overhead in generated nodes for determining the search direction of only less than 0.1 percent is overall just 3 percent worse than this.
Systematically searching in the backward direction, however, is not significantly better 
than
systematically searching in the forward direction
due to high standard deviations, although it saves 17 percent.


IDPS* uses just some few nodes of additional storage for its perimeter.
Due to the related overhead of the {\it front-to-front} evaluations, it needs about the same running time as IDA*-Probing, although it generates much fewer nodes.\footnote{
The results reported 
%in 
by Dillenburg and Nelson \citeyear{Dillenburg_and_Nelson_94} are based on runs using a different sample set of the Fifteen Puzzle, and a different perimeter depth.
Using the same perimeter depth (4),
the results on Korf's set with our re-implementation are even better in terms of the number of node generations, but very much slower in terms of running time (even slower than IDA*).
In personal communication with John Dillenburg it turned out that their implementation of IDA* is slower than Korf's one 
%that 
(which we are using) 
by a factor of about 60 per generated node.
In such an implementation the overhead especially of wave shaping does not show up that clearly as it does in an efficient one.
Since smaller perimeter depth means fewer stored nodes and therefore less overhead through wave shaping,
the perimeter depth 2 results in better running time, and consequently we show these data in our figure.
}


%up to the given limit

Trans (using 256 Mbytes of memory) achieves savings of about half of the running time compared to IDA*.
It saves even much more node generations with this amount of memory, but
the effort for hashing slows it down.\footnote{
The data in the figure were gained using a re-implementation of Trans based on efficient code provided by Jonathan Shaeffer.
%They are even insignificantly better than those reported in \cite{Reinefeld_and_Marsland_94}.
Note the different way of presenting the results: {\it absolute} data in our figure vs.\ {\it relative} to problem difficulty 
%in 
by Reinefeld and Marsland \citeyear{Reinefeld_and_Marsland_94}.
We had to re-implement Trans, since 
no data about the performance of Trans with the amount of memory that we used were available, and since we integrate this technique into some of our algorithms.
%the detailed data in terms of node generation numbers provided by Alexander Reinefeld and the data reported in \cite{Reinefeld_and_Marsland_94} were insufficient to get comparable data on the running times.
Actually, Trans$+$Move is the best algorithm described 
%in 
by Reinefeld and Marsland \citeyear{Reinefeld_and_Marsland_94}, but its {\it absolute} results are 
less than one percent
%only slightly and insignificantly 
better than those of Trans.
Therefore, we did not re-implement Trans$+$Move and cannot include it into the figure.}
%, lacking data on the running times.}


Another technique to prune duplicate nodes was proposed 
%in 
by Taylor and Korf \citeyear{Taylor_and_Korf_93}, using a finite state machine.
Its results are not included in Fig.\ \ref{puzzl}, since we lack data on the running time (no such data 
%can be found in 
are given by Taylor and Korf \citeyear{Taylor_and_Korf_93}, and we did not re-implement this technique).
IDA* employing this pruning technique generated 100.7 million nodes on the same set of instances as reported 
%in 
by Taylor and Korf \citeyear{Taylor_and_Korf_93}, which means 27.7 percent of the number of nodes generated by pure IDA*.
The finite state machine that achieved this result contained 55,441 states, requiring only a modest amount of storage.
Of course, the finite state machine must be built in a pre-processing stage first.
But its use during the search involves only a small and constant
%Since this technique seems not to involve large 
overhead in running time.
So, 
for the sliding-tile puzzles, this approach seems to be better than transposition tables for eliminating duplicates.
It
actually
appears to
represent the most successful approach yet to solving Fifteen Puzzle problems using unidirectional search.



In principle, we have provided all the available storage to BIDA* \cite{Manzini_95}, the most efficient algorithm of the perimeter approach.
In the given 256 Mbytes of storage, BIDA* can store a maximum of 1 million perimeter nodes.
This would correspond to a perimeter depth of 19,
where BIDA* generates just 0.4 percent of the number of nodes generated by IDA*,
but needs 42 percent of IDA*'s running time.
So, as shown in Fig.\ \ref{BIDA-puzzl} above it can use more memory for further savings in the number of nodes generated, but it has an optimum in running time for a smaller perimeter size (16), that we show in Fig.\ \ref{puzzl}.
Also with the reduced perimeter, BIDA* achieves the best result in terms of nodes generated --- just 0.9 percent of the number of nodes generated by IDA*.
While BIDA*'s overhead for computing {\it front-to-front} evaluations is smaller than that of IDPS*, BIDA* needs 27.4 percent of IDA*'s running time.\footnote{
As noted already above in Subsection \ref{Empirical Results}, BIDA*'s result here is worse than the data reported by Manzini \citeyear{Manzini_95}, which is primarily due to 
using a different machine and
a different implementation that is based on the very efficient code of IDA* for the puzzle 
provided to us 
by Korf that we are using.}
%It corresponds to a perimeter depth of 16, but we do not claim that this is the best perimeter depth in all implementations.



Our algorithms 
BAI-Trans 
and Max-BAI-Trans
can store a maximum of 5 million nodes in our implementation of these algorithms in the given 256 Mbytes of storage.
BAI-Trans
generates 
clearly
more nodes (13.9 percent of IDA*)
than 
%that of 
BIDA*, but since its overhead per node is much smaller, 
its running time is even slightly better (24.5 percent).
%\footnote{
%The better results of BAI-Trans here as compared to \cite{Kaindl_et_al_95} are due to an increase of the given storage by a factor of 20, where most of this storage is given to the Trans part.}
%Max-BAI and 
Max-BAI-Trans --- additionally utilizing our new {\it difference} approach --- achieves the fastest searches,
%The fastest one is Max-BAI-Trans,
needing just 15.4 percent of the time needed by IDA*.
For achieving this result,
it uses 4 million nodes for the {\it Max} method (and BAI) and 1 million nodes for Trans.
In order to see the influence of Trans, we compare this result with that of
Max-BAI (not shown in Fig.\ \ref{puzzl} in order not to clutter it) that uses just the 4 million nodes for the {\it Max} method (and BAI).
Needing 19.2 percent of the time used by IDA*, it is just slightly slower than 
Max-BAI-Trans, which shows the comparably modest influence of Trans.


%!!!???		max-BS* 
%
%cannot solve all 100 given 5 million nodes of storage, but it can solve 80, whereas 
%BS* solves just 59 and
%A* 34
%
%
%for those instances solvable by all of these algorithms, we can compare the numbers of generated nodes and the time used with A*:
%
%max-BS*: 24.6% --- 36.5%
%BS*: 37.0% --- 48.8%
%
%
%for those instances solvable by the respective algorithm, we can compare
%the respective data with the number of nodes generated and the time used by IDA*:
%
%max-BS*: 2.2% --- 19.6%
%BS*: 5.6% --- 44.3%
%A*: 25.5% --- 159.3%


% (Cray?)






In summary, our new approach to bidirectional heuristic search enhanced by our
{\it Max} method 
%improves 
%a variety of 
%known search algorithms, and it
%o, utilizing our {\it difference} approach 
achieves the fastest searches for finding optimal solutions on the Fifteen Puzzle 
%that we are aware of
of all those using the Manhattan distance heuristic as the only knowledge source.
The superiority of 
%Max-BAI and 
Max-BAI-Trans in terms of running time over previous algorithms
% that do not use this approach 
is statistically significant. 
For example, the probability that the improvement 
%in terms of 
of the running time over BIDA* is due to chance fluctuation is smaller than 0.15 percent according to a test that compares the means of the paired samples of the absolute running times, and it is even much smaller according to the same test for the data relative to the difficulty of each instance as well as according to the sign test.\footnote{
%M
For more details on 
the statistic tests used 
%can be found in 
we refer the interested reader to \cite{Kaindl_et_al_94,Kaindl_and_Smetana_94}.}
When using less efficient implementations of IDA* as the basis, the difference would become smaller, since our approach has less overhead per node searched and therefore ``gains'' less compared to pure IDA*.
However, we prefer to compare the algorithms using the most efficient implementation that we have available.
For more details on these results see \cite{Kainz_96}.





\subsection{Mazes}


In order to get a better understanding of the usefulness of our new approach, we made also experiments in a second domain --- finding shortest paths in a maze.
These are the same maze problems as described above in Subsection \ref{Empirical Results}.
In addition to these $2000 \times 2000$ mazes, we also made experiments with much smaller $1000 \times 1000$ mazes, in order to see whether the size influences the relative performance of the various algorithms.
We compare known algorithms that achieve the best results in this domain (as far as we found)
with 
%one of these algorithms (A*) 
our algorithms Add-BAA and Add-BDA.
The traditional shortest-path algorithm 
%from 
by Dijkstra \citeyear{Dijkstra_59} corresponds to A* without using heuristic knowledge, so we need not explicitly include it in our experiments.
%enhanced by our new {\it difference} approach to dynamic improvement of heuristic evaluations.
Also in these experiments, all the compared algorithms use no domain-specific knowledge 
%about the puzzle 
other than the Manhattan distance heuristic,
and the main storage available on the Convex C3220 used was up to 256 Mbytes.


\begin{figure}[t]
%\vspace*{-25mm}
\vspace*{-7mm}
\hspace*{17mm}
%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_maze1.eps,width=140mm,clip=}}
%\centerline{\psfig{figure=ai_maze.eps,width=140mm,clip=}}
\centerline{\psfig{figure=ai_maze.eps,clip=}}
\vspace*{-207mm}

\caption{Comparison on the maze problems (100 instances).}

\label{maze}
\end{figure}



Fig.\ \ref{maze} shows a comparison of several algorithms in terms of the
average number of node generations and their running times.
The data are normalized to the respective search effort of A*.
%since this appears to be the previously best algorithm for these problems under the given conditions of this experiment.
As already noted above, A* needs on average less than two minutes on the machine that we used to find an optimal solution
to one problem instance.

%Labyrinth: 2000x2000
%Durchschnitt: A* Anzahl der generierten Knoten:      2738036.13
%                 CPU-Zeit in sec auf der Convex:         109.62


BS* generates slightly more nodes for solving these problems than A* (103.5 percent),
and its running time is even worse.
While it may seem that the implementation of BS* could be further optimized, it is clear that there is some overhead as compared to A*.
So, BS* can certainly not improve on A* here.


PS* \cite{Dillenburg_and_Nelson_94} --- using perimeter search, i.e., the {\it front-to-front} method --- generates 99.3 percent of the number of nodes of A*, but it needs 119.8 percent of the time used by A*.
These data correspond to a perimeter depth of 25, and they are the best 
%we achieved 
results of those shown in Fig.\ \ref{PS-maze}
above
%with this method 
in terms of running time (see also the discussion in Subsection \ref{Empirical Results}).
So, also PS* cannot really improve on A* here.

Our algorithms 
Add-BAA
and Add-BDA
generate clearly fewer nodes than A* (87.5 and 70.7 percent, respectively).
The better performance of Add-BDA reflects the higher $\Mindiff_1$ value that is achieved through guiding the first of the two best-first searches by expanding always one of those nodes $n$ with minimal $\Diff^{\hspace*{.7mm}\ast}_1(n)$.
More precisely, Add-BDA achieved $\Mindiff_1 = 1174$ (from a reverse search of 750k nodes), while Add-BAA achieved only $\Mindiff_1 = 811$ (from a reverse search of even 1000k nodes).
The performance of Add-BAA in terms of running time is, however, still much the same as that of A* (at least in this implementation as derived from BS*).
Add-BDA achieves the fastest searches,
needing just 71.7 percent of the time needed by A*.
So, the application of our approach to dynamically improving heuristic values is feasible here with very little overhead.


The superiority of 
Add-BDA 
%in terms of running time 
over previous algorithms
is statistically significant. 
For example, the probability that the improvement in terms of running time over A* is due to chance fluctuation is smaller than 0.005 percent according to all the three statistic tests that we made analogously to those for the Fifteen Puzzle data.
The same significance result holds for the improvement with respect to the number of node generations.
Both Add-BDA and A* as well as the other algorithms compared here generate all child nodes at once in node {\it expansions}, and the superiority of Add-BDA
over these algorithms is statistically significant also in this respect.
This is particularly interesting, since the optimality result of A* over unidirectional algorithms is stated in the sense that A* never expands a node that could be skipped by some other (unidirectional) algorithm \cite{Dechter_and_Pearl_85}.


%Since also the application of our {\it Max} method achieves significant improvements in this domain (as reported in \cite{Kainz_96}), we conclude that our new {\it difference} approach in general is useful in this domain.


Since the relative results on the $1000 \times 1000$ mazes are very similar, we do not show them explicitly here \cite<see, however,>{Kainz_96}. 
They provide some empirical evidence that the performance of these algorithms is not just peculiar for a certain size of mazes.





%%%\subsection{route planning!? --- Auer}






\section{Discussion}
%%%%%%%%%%%%%%%%%%%%




\begin{table*}[t]

\caption{Overview of approaches to bidirectional heuristic search.}
\label{overview}

\vspace*{2mm}

\centerline{
\begin{tabular}{|l||l|l|} \hline
                 & {\it front-to-front} & {\it front-to-end}     \\ \hline\hline
traditional      & BHFFA, BHFFA2        & BHPA, BS*              \\ \hline
non-traditional  & PS*, IDPS*, BIDA*    & Max-BAI-Trans, Add-BDA \\ \hline
\end{tabular}
}

\end{table*}



After this presentation of our new approach to bidirectional heuristic search and its experimental results, let us 
%in hindsight 
put it into perspective. 
Table \ref{overview} provides an overview of the existing approaches according to the way of evaluating and the way of organizing the change(s) of search direction.
The algorithms that instantiate our new generic approach fall into the category of non-traditional bidirectional heuristic search algorithms (that change the search direction only once)
and 
that perform {\it front-to-end} evaluations.
%	What are the strengths?
While this approach allows coping with limited memory (e.g., in Max-BAI and Max-BAI-Trans), it is also useful in the case of sufficient memory (e.g., Add-BDA).

Due to avoiding expensive {\it front-to-front} evaluations, our approach to dynamically improving heuristic evaluations is less effective than perimeter search in saving node generations (at least in the Fifteen Puzzle domain).
However, it has less overhead and is therefore more efficient per node searched  in terms of running time.
%balance
%Our difference approach is much cheaper in this regard.
%This can also be considered from the perspective that our {\it Add} technique for dynamic improvements of heuristic values is built on a model that abstracts from what perimeter search is based upon.
%Instead of computing the estimates to all perimeter nodes, it uses the minimum?!

From the viewpoint of Table \ref{overview}, our approach somehow ``completes'' the picture of bidirectional heuristic search.
(Note, however, that the non-traditional approach was found independently of the work on perimeter search.)
Still, there should be ample opportunity for further research on bidirectional search, especially when looking at it from other perspectives.
Another issue is, e.g., whether linear-space search is involved or not.
We propose in this paper Max-IDA*, an algorithm that alternates the search direction before every iteration in order to be able to use information from the previous iteration for improving the heuristic evaluations dynamically.
%using DFID, IDA*: limited memory (even linear-space search)
Yet another perspective is whether an algorithm is designed to find optimal solutions or not. In this paper, we only focused on admissible search algorithms. 
As discussed above, however, there also exist $\varepsilon$-admissible bidirectional search algorithms that guarantee solutions with a known error bound, as well as others that find solutions without any guarantee about their quality (e.g., d-node retargeting).


When contrasting the traditional and the non-traditional approaches to bidirectional heuristic search, it may appear to be strange that the less flexible approach delivers the better results.
Why should it be ``better'' to change the search direction just once?
While it is difficult to provide a generally convincing answer to this question, let us summarize some observations:

\begin{itemize}

\item	Traditional bidirectional search typically requires exponential space.
%IN
Kaindl and Khorsand \citeyear{Kaindl_and_Khorsand_94} 
%we 
showed that such a search is possible using limited memory, but because of the complexity of such algorithms the runtime efficiency was insufficient.

\item	For the perimeter depths where perimeter search is successful, its perimeters are much smaller than the frontiers of traditional {\it front-to-front} algorithms.
Through parameterizing the perimeter depth it is possible to balance the effort for {\it front-to-front} evaluations with their effect of improving heuristic evaluations dynamically.

\item	The runtime optimizations of BIDA* over IDPS* are only feasible when the perimeter stays constant (at least for each iteration).

\item	The $\Mindiff$ value of the {\it Add} method becomes higher when the search for computing it generates more nodes.
So, in the context of a traditional bidirectional search it is initially small.

\item	Applying the {\it Max} idea becomes much more complex, e.g., in BS* where both search frontiers change \cite{Kainz_96}.

\end{itemize}



%We think that this issue strongly relates to the implications about the use of memory.
%When a bidirectional search uses a given amount of memory for one search direction first, then it is easier to cope both with limited memory and with %Add-BDA --- more efficiently implemented


In general, one of the major problems of heuristic search is how to use available but limited memory effectively.
Pure {\it unidirectional} approaches to utilizing limited memory 
%still did not 
led to less convincing results 
%yet
\cite{Chakrabarti_et_al_89,Sen_and_Bagchi_89,Russell_92,Gosh_et_al_94,Reinefeld_and_Marsland_94}
than the non-traditional approaches to bidirectional search as shown in Table \ref{overview}.
In particular, our generic approach allows very flexible and effective use of available memory.
This is, however, partly due to its integration of various unidirectional strategies.
Future work may investigate the direct use of such unidirectional approaches to utilizing limited memory in instantiations of our generic approach to bidirectional search.



In addition, 
bidirectional search allows the use of memory for dynamically improving heuristic evaluations in ways that are infeasible for strictly unidirectional search.
This is demonstrated by the 
%perimeter 
{\it front-to-front}
approach as well as by our difference method.
The following simple idea implicitly behind these approaches may further illustrate this.
Given a breadth-first (uniform-cost) search to some depth $d$, any node outside its frontier must be at least $d+1$ steps away from its start $s$.
A reverse search towards $s$ may use this fact to compute an estimate for any node outside this frontier that is at least $d+1$.
This idea cannot be used in a strictly unidirectional search.
Note, however, that the approaches discussed here are much more complex and useful than this simple idea. 
Since they take 
known costs
and
heuristic estimates 
as well as differences of these into account, they can provide 
%also 
much
better estimates 
especially
for nodes that are far outside the already given opposite search frontier.


In some sense, it is also possible to view our difference approach as {\it learning}, since also there differences between predicted and actual outcomes are important.
Usual machine 
learning
research, however, strives for using the results from one problem instance for solving subsequent instances, which we did not attempt.
An in-depth discussion of this relationship is outside the scope of this paper.
Note, however, that also 
%perimeter search with its {\it front-to-front} evaluations could be thought of as ``learning while doing''.
the approaches using {\it front-to-front} evaluations could be considered from this viewpoint.


%In particular, the recently proposed {\it perimeter search} %\cite{Dillenburg_and_Nelson_94} 
%would fit 
%into a more general approach.
%However, we explicitly do {\it not} propose to use a {\it wave-shaping} %strategy, since it is inefficient in terms of running time.

%Under certain circumstances to be discussed below, one or more of the steps can also be omitted during instantiation.
%For instance, if the domain shows a strong asymmetry, the search direction is known {\it before} the search begins.
%Moreover, our generic approach can also be instantiated as unidirectional search. 

%DFBB


%	What are the limitations?
%
%Our 
%{\it Add} 
%technique for dynamic improvements of heuristic values proposed here 
%cannot be combined usefully with
%%does not improve 
%perimeter search, since 
%%they are 
%it is
%built on a model that abstracts from what perimeter search is based upon.


%\begin{figure}[t]
%\vspace*{-90mm}
%%\hspace*{-30mm}
%%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_theor1.eps,width=150mm,clip=}}
%%\centerline{\psfig{figure=/home1/kaih_home_extension_3/DynEval/d_theor1.eps,clip=}}
%\centerline{\psfig{figure=d_theor1.eps,width=150mm,clip=}}
%\vspace*{-88mm}
%
%\caption{A taxonomy of methods for dynamic improvement.}
%
%\label{theor}
%\end{figure}
%
%
%overview of approaches to dynamic improvements: Fig.\ \ref{theor} ???





\section{Conclusion}
%%%%%%%%%%%%%%%%%%%%


Based on new insights about previous approaches to bidirectional heuristic search, we propose in this paper 

\begin{itemize}

\item	a new generic approach to non-traditional bidirectional search with {\it front-to-end evaluations}, and

\item	a new approach to dynamically improving heuristic values in this context.

\end{itemize}

We showed how to successfully instantiate this generic approach for the very important case 
%of the availability of limited memory
when available memory is limited.
This memory can also be utilized for efficiently improving heuristic values.
For certain problems where sufficient memory is available, we proposed an instantiation in the form of an algorithm that challenges A*, which is in a certain sense optimal over unidirectional search algorithms.
The optimality result of A* over unidirectional competitors 
%in 
by Dechter and Pearl \citeyear{Dechter_and_Pearl_85} does {\it not} imply that {\it bidirectional} search cannot be more efficient, and in our experiments we found some empirical evidence that our new algorithm can be more efficient than A* both in terms of node expansions and running time.
We also showed that our approach was more efficient in terms of running time than any other bidirectional or unidirectional search approach using the same information
in two 
% three 
different domains.
These results are statistically significant.


While traditional bidirectional search did not yet achieve improvements over admissible unidirectional search, the non-traditional way of performing the opposing searches in sequence --- as exemplified by perimeter search and by our approach --- seems to have great potential.
%point sentence:
In this sense, we show that bidirectional heuristic search is viable and 
%Consequence:\\
consequently
propose that 
%it
this
%paradigm 
search strategy
be reconsidered.



\section*{Acknowledgements}

%\acks{
Over the years, several people cooperated with the first author on research in heuristic search and in particular bidirectional search: Aliasghar Khorsand, Andreas K\"{o}ll, Angelika Leeb, Harald Smetana and Roland Steiner. 
Some of their work served as a basis for the work presented in this paper.
For 
%some of 
our experiments we had a Convex C3220 at the computing center of the TU Vienna available.
Our implementations are based on the very efficient code of IDA* and A* for the puzzle made available by Richard Korf
and an efficient hashing schema by Jonathan Shaeffer.
%Alexander Reinefeld 
%provided the data on the generated nodes for Trans and Trans$+$Move. 
%!?as well as comments on an earlier draft of this paper.
Finally, we acknowledge the useful comments on 
%an 
earlier drafts by 
Andreas Auer,
%?Wilhelm Barth, 
Dennis de Champeaux,
Stefan Kramer,
Giovanni Manzini,
%Tony Marsland, 
%Peter Nelson,
Ira Pohl 
and
Roland Steiner.
Parts of this paper already appeared in 
{\em Proc.\ Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95)}
%\thanksref{IJCAI-95}}
and in 
{\em Proc.\ Thirteenth National Conference on Artificial Intelligence (AAAI-96)}.
%}



\appendix
\section*{Appendix. Glossary of Notation}

\vspace*{-4mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\input{notation}
%{\xpt

%{\footnotesize

%\begin{small}
%{\renewcommand{\arraystretch}{4}}
%\arraycolsep1cm    
\noindent
\parsep0mm
\begin{tabbing}                                                                   
\hspace*{24mm}\= \kill
%JAIR-CR{\bf Notation} \> \\ \vspace*{-30pt} 
$s,t$                \>  Start node and goal/target node, respectively.\\ \vspace*{-30pt} 
$d$                  \>  Current search direction index; when search is in the forward \\ \vspace*{-30pt}
{\ }                 \>  direction $d=1$, and when in the backward direction $d=2$.\\  \vspace*{-30pt}
%{\ }                 \>  \\  \vspace*{-30pt} 
$C^\ast$             \>  Cost of an optimal path from $s$ to $t$.\\ \vspace*{-30pt} 
$k_d(m,n)$           \>  Cost of an optimal path from $m$ to $n$ if $d=1$, or from $n$ to $m$ if $d=2$.\\ \vspace*{-30pt}
$g^\ast_d(n)$        \>  Cost of an optimal path from $s$ to $n$ if $d=1$, or from $n$ to $t$ if $d=2$.\\ \vspace*{-30pt}
%{\ }                 \>  .\\ \vspace*{-30pt} 
$h^\ast_d(n)$        \>  Cost of an optimal path from $n$ to $t$ if $d=1$, or from $s$ to $n$ if $d=2$.\\ \vspace*{-30pt}
%{\ }                 \>  \\ \vspace*{-30pt} 
$g_d(n),h_d(n)$      \>  Estimates of $g_d^\ast(n)$ and $h_d^\ast(n)$, respectively.\\ \vspace*{-30pt} 
% $h^\ast(m,n)$        \>  Cost of an optimal path from $m$ to $n$.\\ \vspace*{-30pt}
% $h(m,n)$             \>  Estimate of $h^\ast(m,n)$. \\ \vspace*{-30pt}
$f_d(n)$             \>  Static evaluation function: $g_d(n) + h_d(n)$.\\  \vspace*{-30pt}
$f^j_d$              \>  One of the $f$-values of expanded nodes in search direction $d$. \\ \vspace*{-30pt}
$H_d(n)$             \>  Dynamic estimate of $h_d^\ast(n)$.\\ \vspace*{-30pt}
$F_d(n)$             \>  Dynamic evaluation function: $g_d(n) + H_d(n)$.\\ 
\hspace*{1mm}$L_{\min}$           \>  Cost of the best (least costly) complete path found so far from $s$ to $t$.\\ \vspace*{-30pt}
{\open}$_d$          \>  The set of open nodes in search direction $d$.\\ \vspace*{-30pt} 
{\closed}$_d$        \>  The set of closed nodes in search direction $d$.\\ \vspace*{-30pt} 
$|{\open}_d|$        \>  Number of nodes in {\open}$_d$.\\ \vspace*{-30pt} 
$\#(a)$              \>  Number of nodes expanded by algorithm $a$.\\ \vspace*{-30pt} 
$\#_d(a)$            \>  Number of nodes expanded by algorithm $a$ in search direction $d$.\\ \vspace*{-30pt} 
$\#_d^j(a)$          \>  Number of those nodes with value $f^j_d$ expanded by algorithm $a$ in \\ \vspace*{-30pt}
{\ }                 \>  search direction $d$.\\ \vspace*{-30pt} 
\end{tabbing}
%\end{small}

%}

%}



\vspace*{-6mm}

%JAIR\bibliographystyle{plain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\bibliographystyle{theapa}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\bibliography{Search}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Chakrabarti, Ghose, Acharya, \BBA\ DeSarkar}{Chakrabarti
  et~al.}{1989}]{Chakrabarti_et_al_89}
Chakrabarti, P., Ghose, S., Acharya, A., \BBA\ DeSarkar, S. \BBOP1989\BBCP.
\newblock \BBOQ Heuristic search in restricted memory\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 41\/}(2), 197--221.

\bibitem[\protect\BCAY{Culberson \BBA\ Schaeffer}{Culberson \BBA\
  Schaeffer}{1996}]{Culberson_and_Schaeffer_96}
Culberson, J.\BBACOMMA\  \BBA\ Schaeffer, J. \BBOP1996\BBCP.
\newblock \BBOQ Searching with pattern databases\BBCQ\
\newblock In McCalla, G.\BED, {\Bem Advances in Artificial Intelligence},
  \BPGS\ 402--416. Springer-Verlag, Berlin.

\bibitem[\protect\BCAY{Davis, Pollack, \BBA\ Sudkamp}{Davis
  et~al.}{1984}]{Davis_84}
Davis, H., Pollack, R., \BBA\ Sudkamp, T. \BBOP1984\BBCP.
\newblock \BBOQ Towards a better understanding of bidirectional search\BBCQ\
\newblock In {\Bem Proc.\ Fourth National Conference on Artificial Intelligence
  (AAAI-84)}, \BPGS\ 68--72. Menlo Park, CA: AAAI Press / The MIT Press.

\bibitem[\protect\BCAY{de~Champeaux}{de~Champeaux}{1983}]{de_Champeaux_83}
de~Champeaux, D. \BBOP1983\BBCP.
\newblock \BBOQ Bidirectional heuristic search again\BBCQ\
\newblock {\Bem J. ACM}, {\Bem 30\/}(1), 22--32.

\bibitem[\protect\BCAY{de~Champeaux \BBA\ Sint}{de~Champeaux \BBA\
  Sint}{1977}]{de_Champeaux_and_Sint_77}
de~Champeaux, D.\BBACOMMA\  \BBA\ Sint, L. \BBOP1977\BBCP.
\newblock \BBOQ An improved bidirectional heuristic search algorithm\BBCQ\
\newblock {\Bem J. ACM}, {\Bem 24\/}(2), 177--191.

\bibitem[\protect\BCAY{Dechter \BBA\ Pearl}{Dechter \BBA\
  Pearl}{1985}]{Dechter_and_Pearl_85}
Dechter, R.\BBACOMMA\  \BBA\ Pearl, J. \BBOP1985\BBCP.
\newblock \BBOQ Generalized best-first strategies and the optimality of
  {\astern}\BBCQ\
\newblock {\Bem J. ACM}, {\Bem 32\/}(3), 505--536.

\bibitem[\protect\BCAY{Dijkstra}{Dijkstra}{1959}]{Dijkstra_59}
Dijkstra, E. \BBOP1959\BBCP.
\newblock \BBOQ A note on two problems in connexion with graphs\BBCQ\
\newblock In {\Bem Numerische Mathematik 1}, \BPGS\ 269--271.

\bibitem[\protect\BCAY{Dillenburg \BBA\ Nelson}{Dillenburg \BBA\
  Nelson}{1994}]{Dillenburg_and_Nelson_94}
Dillenburg, J.\BBACOMMA\  \BBA\ Nelson, P. \BBOP1994\BBCP.
\newblock \BBOQ Perimeter search\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 65\/}(1), 165--178.

\bibitem[\protect\BCAY{Ghosh, Mahanti, \BBA\ Nau}{Ghosh
  et~al.}{1994}]{Gosh_et_al_94}
Ghosh, S., Mahanti, A., \BBA\ Nau, D. \BBOP1994\BBCP.
\newblock \BBOQ {ITS}: an efficient limited-memory heuristic tree search
  algorithm\BBCQ\
\newblock In {\Bem Proc.\ Twelfth National Conference on Artificial
  Intelligence (AAAI-94)}, \BPGS\ 1353--1358. Menlo Park, CA: AAAI Press / The
  MIT Press.

\bibitem[\protect\BCAY{Hart, Nilsson, \BBA\ Raphael}{Hart
  et~al.}{1968}]{Hart_et_al_68}
Hart, P., Nilsson, N., \BBA\ Raphael, B. \BBOP1968\BBCP.
\newblock \BBOQ A formal basis for the heuristic determination of minimum cost
  paths\BBCQ\
\newblock {\Bem IEEE Transactions on Systems Science and Cybernetics (SSC)},
  {\Bem SSC-4\/}(2), 100--107.

\bibitem[\protect\BCAY{Kaindl}{Kaindl}{1990}]{Kaindl_90}
Kaindl, H. \BBOP1990\BBCP.
\newblock \BBOQ Tree searching algorithms\BBCQ\
\newblock In Marsland, T.\BBACOMMA\  \BBA\ Schaeffer, J.\BEDS, {\Bem Computers,
  Chess, and Cognition}, \BPGS\ 133--158. Springer-Verlag, New York.

\bibitem[\protect\BCAY{Kaindl, Kainz, Leeb, \BBA\ Smetana}{Kaindl
  et~al.}{1995}]{Kaindl_et_al_95}
Kaindl, H., Kainz, G., Leeb, A., \BBA\ Smetana, H. \BBOP1995\BBCP.
\newblock \BBOQ How to use limited memory in heuristic search\BBCQ\
\newblock In {\Bem Proc.\ Fourteenth International Joint Conference on
  Artificial Intelligence (IJCAI-95)}, \BPGS\ 236--242. San Francisco, CA:
  Morgan Kaufmann Publishers.

\bibitem[\protect\BCAY{Kaindl \BBA\ Khorsand}{Kaindl \BBA\
  Khorsand}{1994}]{Kaindl_and_Khorsand_94}
Kaindl, H.\BBACOMMA\  \BBA\ Khorsand, A. \BBOP1994\BBCP.
\newblock \BBOQ Memory-bounded bidirectional search\BBCQ\
\newblock In {\Bem Proc.\ Twelfth National Conference on Artificial
  Intelligence (AAAI-94)}, \BPGS\ 1359--1364. Menlo Park, CA: AAAI Press / The
  MIT Press.

\bibitem[\protect\BCAY{Kaindl, Leeb, \BBA\ Smetana}{Kaindl
  et~al.}{1994}]{Kaindl_et_al_94}
Kaindl, H., Leeb, A., \BBA\ Smetana, H. \BBOP1994\BBCP.
\newblock \BBOQ Improvements on linear-space search algorithms\BBCQ\
\newblock In {\Bem Proc.\ Eleventh European Conference on Artificial
  Intelligence (ECAI-94)}, \BPGS\ 155--159. Chichester, England: Wiley.

\bibitem[\protect\BCAY{Kaindl \BBA\ Scheucher}{Kaindl \BBA\
  Scheucher}{1992}]{Kaindl&Scheucher_92}
Kaindl, H.\BBACOMMA\  \BBA\ Scheucher, A. \BBOP1992\BBCP.
\newblock \BBOQ Reasons for the effects of bounded look-ahead search\BBCQ\
\newblock {\Bem IEEE Transactions on Systems, Man, and Cybernetics (SMC)},
  {\Bem 22\/}(5), 992--1007.

\bibitem[\protect\BCAY{Kaindl \BBA\ Smetana}{Kaindl \BBA\
  Smetana}{1994}]{Kaindl_and_Smetana_94}
Kaindl, H.\BBACOMMA\  \BBA\ Smetana, H. \BBOP1994\BBCP.
\newblock \BBOQ Experimental comparison of heuristic search algorithms\BBCQ\
\newblock In {\Bem AAAI-94 Workshop on Experimental Evaluation of Reasoning and
  Search Methods}, \BPGS\ 11--14.

\bibitem[\protect\BCAY{Kainz}{Kainz}{1994}]{Kainz_94}
Kainz, G. \BBOP1994\BBCP.
\newblock \BBOQ Heuristische {S}uche in {G}raphen mit der
  {D}ifferenz-{M}ethode\BBCQ\
\newblock Diplomarbeit, Technische Universit\"at Wien, Vienna, Austria.

\bibitem[\protect\BCAY{Kainz}{Kainz}{1996}]{Kainz_96}
Kainz, G. \BBOP1996\BBCP.
\newblock \BBOQ {Neue Algorithmen f\"ur die bidirektionale heuristische
  Suche}\BBCQ\
\newblock Doctoral dissertation, Technische Universit\"at Wien, Vienna,
  Austria.

\bibitem[\protect\BCAY{Kainz \BBA\ Kaindl}{Kainz \BBA\
  Kaindl}{1996}]{Kainz_and_Kaindl_96}
Kainz, G.\BBACOMMA\  \BBA\ Kaindl, H. \BBOP1996\BBCP.
\newblock \BBOQ Dynamic improvements of heuristic evaluations during
  search\BBCQ\
\newblock In {\Bem Proc.\ Thirteenth National Conference on Artificial
  Intelligence (AAAI-96)}, \BPGS\ 311--317. Menlo Park, CA: AAAI Press / The
  MIT Press.

\bibitem[\protect\BCAY{K{\"o}ll \BBA\ Kaindl}{K{\"o}ll \BBA\
  Kaindl}{1993}]{Koell_and_Kaindl_93}
K{\"o}ll, A.\BBACOMMA\  \BBA\ Kaindl, H. \BBOP1993\BBCP.
\newblock \BBOQ Bidirectional best-first search with bounded error: {S}ummary
  of results\BBCQ\
\newblock In {\Bem Proc.\ Thirteenth International Joint Conference on
  Artificial Intelligence (IJCAI-93)}, \BPGS\ 217--223. San Francisco, CA:
  Morgan Kaufmann Publishers.

\bibitem[\protect\BCAY{Korf}{Korf}{1985}]{Korf_85}
Korf, R. \BBOP1985\BBCP.
\newblock \BBOQ Depth-first iterative deepening: {A}n optimal admissible tree
  search\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 27\/}(1), 97--109.

\bibitem[\protect\BCAY{Korf}{Korf}{1990}]{Korf_90}
Korf, R. \BBOP1990\BBCP.
\newblock \BBOQ Real-time heuristic search\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 42\/}(2--3), 189--212.

\bibitem[\protect\BCAY{Korf \BBA\ Taylor}{Korf \BBA\
  Taylor}{1996}]{Korf_and_Taylor_96}
Korf, R.\BBACOMMA\  \BBA\ Taylor, L. \BBOP1996\BBCP.
\newblock \BBOQ Finding optimal solutions to the {Twenty-Four Puzzle}\BBCQ\
\newblock In {\Bem Proc.\ Thirteenth National Conference on Artificial
  Intelligence (AAAI-96)}, \BPGS\ 1202--1207. Menlo Park, CA: AAAI Press / The
  MIT Press.

\bibitem[\protect\BCAY{Kwa}{Kwa}{1989}]{Kwa_89}
Kwa, J. \BBOP1989\BBCP.
\newblock \BBOQ B{S}$^\ast$: {A}n {A}dmissible {B}idirectional {S}taged
  {H}euristic {S}earch {A}lgorithm\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 38\/}(2), 95--109.

\bibitem[\protect\BCAY{Lawler \BBA\ Wood}{Lawler \BBA\
  Wood}{1966}]{Lawler_and_Wood_66}
Lawler, E.\BBACOMMA\  \BBA\ Wood, D. \BBOP1966\BBCP.
\newblock \BBOQ Branch-and-bound methods: a survey\BBCQ\
\newblock {\Bem Operations Research}, {\Bem 14\/}(4), 699--719.

\bibitem[\protect\BCAY{Manzini}{Manzini}{1995}]{Manzini_95}
Manzini, G. \BBOP1995\BBCP.
\newblock \BBOQ {BIDA*}: an improved perimeter search algorithm\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 75\/}(2), 347--360.

\bibitem[\protect\BCAY{Nilsson}{Nilsson}{1980}]{Nilsson_80}
Nilsson, N. \BBOP1980\BBCP.
\newblock {\Bem {P}rinciples of {A}rtificial {I}ntelligence}.
\newblock Tioga, Palo Alto, CA.

\bibitem[\protect\BCAY{Pearl}{Pearl}{1984}]{Pearl_84}
Pearl, J. \BBOP1984\BBCP.
\newblock {\Bem Heuristics: Intelligent Search Strategies for Computer Problem
  Solving}.
\newblock Addison-Wesley, Reading, MA.

\bibitem[\protect\BCAY{Pohl}{Pohl}{1970}]{Pohl_70}
Pohl, I. \BBOP1970\BBCP.
\newblock \BBOQ First results on the effect of error in heuristic search\BBCQ\
\newblock In Meltzer, B.\BBACOMMA\  \BBA\ Michie, D.\BEDS, {\Bem Machine
  Intelligence 5}, \BPGS\ 219--236. Edinburgh University Press, Edinburgh.

\bibitem[\protect\BCAY{Pohl}{Pohl}{1971}]{Pohl_71}
Pohl, I. \BBOP1971\BBCP.
\newblock \BBOQ Bi-directional search\BBCQ\
\newblock In {\Bem Machine Intelligence 6}, \BPGS\ 127--140\ Edinburgh.
  Edinburgh University Press.

\bibitem[\protect\BCAY{Politowski \BBA\ Pohl}{Politowski \BBA\
  Pohl}{1984}]{Politowski_and_Pohl_84}
Politowski, G.\BBACOMMA\  \BBA\ Pohl, I. \BBOP1984\BBCP.
\newblock \BBOQ D-node retargeting in bidirectional heuristic search\BBCQ\
\newblock In {\Bem Proc.\ Fourth National Conference on Artificial Intelligence
  (AAAI-84)}, \BPGS\ 274--277. Menlo Park, CA: AAAI Press / The MIT Press.

\bibitem[\protect\BCAY{Rao, Kumar, \BBA\ Korf}{Rao et~al.}{1991}]{Rao_et_al_91}
Rao, V., Kumar, V., \BBA\ Korf, R. \BBOP1991\BBCP.
\newblock \BBOQ Depth-first vs best-first search\BBCQ\
\newblock In {\Bem Proc.\ Ninth National Conference on Artificial Intelligence
  (AAAI-91)}, \BPGS\ 434--440. Menlo Park, CA: AAAI Press / The MIT Press.

\bibitem[\protect\BCAY{Reinefeld \BBA\ Marsland}{Reinefeld \BBA\
  Marsland}{1994}]{Reinefeld_and_Marsland_94}
Reinefeld, A.\BBACOMMA\  \BBA\ Marsland, T. \BBOP1994\BBCP.
\newblock \BBOQ Enhanced iterative-deepening search\BBCQ\
\newblock {\Bem IEEE Transactions on Pattern Analysis and Machine Intelligence
  (PAMI)}, {\Bem 16\/}(12), 701--709.

\bibitem[\protect\BCAY{Russell}{Russell}{1992}]{Russell_92}
Russell, S. \BBOP1992\BBCP.
\newblock \BBOQ Efficient memory-bounded search methods\BBCQ\
\newblock In {\Bem Proc.\ Tenth European Conference on Artificial Intelligence
  (ECAI-92)}, \BPGS\ 1--5. Chichester, England: Wiley.

\bibitem[\protect\BCAY{Russell \BBA\ Norvig}{Russell \BBA\
  Norvig}{1995}]{Russell_and_Norvig_95}
Russell, S.\BBACOMMA\  \BBA\ Norvig, P. \BBOP1995\BBCP.
\newblock {\Bem {A}rtificial {I}ntelligence: A Modern Approach}.
\newblock Prentice Hall, Englewood Cliffs, NJ.

\bibitem[\protect\BCAY{Sen \BBA\ Bagchi}{Sen \BBA\
  Bagchi}{1989}]{Sen_and_Bagchi_89}
Sen, A.\BBACOMMA\  \BBA\ Bagchi, A. \BBOP1989\BBCP.
\newblock \BBOQ Fast recursive formulations for best-first search that allow
  controlled use of memory\BBCQ\
\newblock In {\Bem Proc.\ Eleventh International Joint Conference on Artificial
  Intelligence (IJCAI-89)}, \BPGS\ 297--302. San Francisco, CA: Morgan Kaufmann
  Publishers.

\bibitem[\protect\BCAY{Taylor \BBA\ Korf}{Taylor \BBA\
  Korf}{1993}]{Taylor_and_Korf_93}
Taylor, L.\BBACOMMA\  \BBA\ Korf, R. \BBOP1993\BBCP.
\newblock \BBOQ Pruning duplicate nodes in depth-first search\BBCQ\
\newblock In {\Bem Proc.\ Eleventh National Conference on Artificial
  Intelligence (AAAI-93)}, \BPGS\ 756--761. Menlo Park, CA: AAAI Press / The
  MIT Press.

\bibitem[\protect\BCAY{Zhang \BBA\ Korf}{Zhang \BBA\
  Korf}{1993}]{Zhang_and_Korf_93}
Zhang, W.\BBACOMMA\  \BBA\ Korf, R. \BBOP1993\BBCP.
\newblock \BBOQ Depth-first vs.\ best-first search: new results\BBCQ\
\newblock In {\Bem Proc.\ Eleventh National Conference on Artificial
  Intelligence (AAAI-93)}, \BPGS\ 769--775. Menlo Park, CA: AAAI Press / The
  MIT Press.

\end{thebibliography}


\end{document}
