\documentstyle[jair,twoside,11pt,theapa,epsf,epsfig]{article} 
\input{commands}
\jairheading{15}{2001}{289-318}{3/01}{10/01}
\ShortHeadings{Efficient Methods for Qualitative Spatial
  Reasoning}{Renz \& Nebel}
\begin{document}
\title{Efficient Methods for Qualitative Spatial Reasoning}
\author{\name Jochen Renz \email renz@dbai.tuwien.ac.at
        \\
	\addr Institut f\"ur Informationssysteme, Technische Universit\"at Wien\\ Favoritenstr.9, A-1040 Wien, Austria \vspace{2mm}\\
        \name Bernhard Nebel \email nebel@informatik.uni-freiburg.de \\
        \addr Institut f\"ur Informatik, Albert-Ludwigs-Universit\"at \\
        Am Flughafen 17, D-79110 Freiburg, Germany} 

\firstpageno{289}
\maketitle 
\nocite{renz:nebel:ecai-98}
\begin{abstract} 
  The theoretical properties of qualitative spatial reasoning in the
  $\rca$ framework have been analyzed extensively. However, no empirical
  investigation has been made yet. Our experiments show that the
adaption of
  the algorithms used for qualitative temporal reasoning can solve large
  $\rca$ instances, even if they are in the {\em phase
transition}
  region -- provided that one uses the maximal tractable subsets of $\rca$
that
  have been identified by us. In particular, we demonstrate that the
orthogonal
  combination of heuristic methods is successful in solving almost all
  apparently hard instances in the phase transition region up to a
  certain size in reasonable time.
\end{abstract} 
   
 \section{Introduction} 
\label{S:introduction} 
Representing qualitative spatial information and reasoning with such
information is an important subproblem in many applications, such as
natural language understanding, document interpretation, and
geographical information systems. The $\rca$ calculus
\cite{randell:et:al:kr-92} is well suited for representing topological
relationships between spatial regions. Inference in the full calculus
is, however, NP-hard \cite{grigni:et:al:ijcai-95,renz:nebel:aij99}.
While this means that it is unlikely that very large instances can be
solved in reasonable time, this result does not rule out the
possibility that we can solve instances up to a certain size in
reasonable time. 
Recently, maximal tractable subsets of $\rca$ were identified
\cite{renz:nebel:aij99,renz:ijcai-99} which can be
used to speed up backtracking search for the general $\NP$-complete
reasoning problem by reducing the search space considerably. 

In this paper we address several questions that emerge from previous
theoretical 
results on $\rca$ \cite{renz:nebel:aij99,renz:ijcai-99}: 
%
Up to which size is it possible to solve instances in reasonable time?
 Which heuristic is the best? 
Is it really so much  more efficient to use the maximal tractable subsets for
solving instances of the $\NP$-complete consistency problem as
the theoretical savings given by the smaller branching factors 
indicate or is this  
effect out-balanced by the forward-checking power of the interleaved
path-consistency computations? This was the case for similar  
temporal problems (pointisable vs.~ORD-Horn relations) \cite{nebel:constraints-97}. 
%
Is it possible to combine the different heuristics in such a way that more
instances can be solved in reasonable time than by each heuristic
alone? 
%

We treat these questions by randomly generating instances and solving
them using different heuristics. In doing so, we are particularly
interested in the hardest randomly generated instances which leads to
the question of phase-transitions \cite{cheeseman:et:al:ijcai-91}: 
Is there a parameter for randomly generating instances of the
consistency problem of $\rca$ that results in a phase-transition
behavior? If so, is it the case that the hardest
instances are mainly located in the
phase-transition region while the instances not contained in the
phase-transition region are easily solvable? 
In order to generate instances which are harder with a higher
probability, we generate two different kinds of instances. On the one
hand  we generated 
instances which contain constraints over all $\rca$ relations,
on the other hand we generated instances which contain only constraints over
relations which are not contained in any of the maximal tractable
subsets. We expect these instances to be harder on average than the
former instances. 

The algorithmic techniques we use for solving these randomly generated 
instances are borrowed from similar work on
qualitative temporal reasoning
\cite{nebel:constraints-97,beek:manchak:jair-96,ladkin:reinefeld:ai-92}.
Additionally, we make use of the fragments of $\rca$, named $\aha$,
$\Qmax$, and $\Cmax$, that
permit
polynomial-time inferences \cite{renz:nebel:aij99,renz:ijcai-99}. In the
backtracking algorithm, which is used to solve the reasoning problem
for full $\rca$, we decompose every disjunctive relation into relations of one of these tractable subsets instead of decomposing them into its base relations. This reduces the average branching factor of the backtracking tree from 4.0 for the 
base relations to
1.4375 for $\aha$, to 1.523 for $\Cmax$, and to 1.516 for $\Qmax$. Although these theoretical savings cannot be observed in our
experiments, using the maximal tractable subsets instead of the base
relations leads to 
significant performance improvements.



This paper is structured as follows. In
Section~\ref{S:calculus}, we give a brief sketch of the $\rca$
calculus and of the algorithms used for solving instances of $\rca$. In
Section~\ref{S:emp:test-instances} we describe the 
procedure for randomly generating instances, the different heuristics
we apply for solving these instances, and how we measure the
quality of the heuristics. 
In Section~\ref{S:emp:path-consistency} we evaluate different
path-consistency algorithms in order to find the most efficient one to 
be used for forward-checking in the backtracking search. 
In Section~\ref{S:emp:phase-transition} we observe a phase-transition
behavior of the randomly generated instances and show that the
instances in the phase-transition region are harder to solve than the
other instances. In Section~\ref{S:emp:evaluation} we report on the
outcome of running the different heuristics for solving the instances and identify several hard instances
which are mainly located in the phase-transition region. 
In Section~\ref{S:emp:orthogonal} we try to solve the hard instances
by orthogonally combining the different heuristics. This turns out to 
be very effective and leads to a very efficient solution strategy.  
Finally, in Section~\ref{S:emp:large} we evaluate this strategy by
trying to solve very large instances.% 
\footnote{The programs are available as an online appendix.}

\section{The Region Connection Calculus $\rca$}
\label{S:calculus}

The Region Connection Calculus (\rcc) is a first-order 
language for representation of and reasoning about 
topological relationships between extended spatial regions
\cite{randell:et:al:kr-92}.  
Spatial regions in $\rcc$ are non-empty regular subsets of some
topological space which do not have to be internally connected, i.e.,
a spatial region may consist of different disconnected pieces. 
Different relationships between spatial regions can be defined based on one
 dyadic relation, the {\em connected} relation ${\cl C}(a,b)$ which is true
 if the topological closures of the spatial regions $a$ and $b$ share
 a common point. 

The Region Connection Calculus $\rca$ is a constraint language 
formed by the eight jointly exhaustive and pairwise disjoint {\em base 
  relations} $\dc$, $\ec$, $\po$, $\eq$, $\tpp$, $\ntpp$, $\tppi$, and
$\ntppi$ definable in the $\rcc$-theory and by all possible unions of 
the base relations---giving a total number of $2^8=256$ different relations.  
The base relations have the meaning of 
{\it DisConnected, Externally Connected, Partial Overlap, EQual, Tangential 
  Proper Part, Non-Tangential Proper Part}, and their converses. 
Examples for these relations are shown in Figure~\ref{F:RCC8}.  
%
\begin{figure}[t] 
\vspace{-3mm}
\begin{center} 
\setlength{\unitlength}{0.011in} 
\begin{picture}(229,148)(8,672) 
\thinlines 
\scriptsize 
\put( 20,810){\circle{20}} 
\put( 20,785){\circle{20}} 
\put( 20,805){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put( 20,780){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put( 20,760){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf DC($\regx,\regy$)}}} 
\put( 75,810){\circle{20}} 
\put( 75,790){\circle{20}} 
\put( 75,805){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put( 75,785){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put( 75,760){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf EC($\regx,\regy$)}}} 
\put(200,800){\circle{40}} 
\put(190,800){\circle{20}} 
\put(190,795){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put(210,795){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put(195,715){\circle{20}} 
\put(195,710){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put( 20,725){\circle{30}} 
\put( 20,705){\circle{30}} 
\put(135,800){\circle{40}} 
\put(125,800){\circle{20}} 
\put( 75,715){\circle{40}} 
\put(200,715){\circle{40}} 
\put(135,715){\circle{20}} 
\put(140,715){\circle{40}} 
\put(135,760){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf TPP($\regx,\regy$)}}} 
\put(200,760){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf TPP$^{-1}$($\regx,\regy$)}}} 
\put( 20,725){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put( 20,700){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put(125,795){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put(145,795){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put(213,711){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put(136,711){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$}}} 
\put(153,711){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regy$}}} 
\put( 75,711){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm $\regx$  $\regy$}}} 
\put( 20,673){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf PO($\regx,\regy$)}}} 
\put( 75,673){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf EQ($\regx,\regy$)}}} 
\put(135,673){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf NTPP($\regx,\regy$)}}} 
\put(209,673){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tensf NTPP$^{-1}$($\regx,\regy$)}}} 
\end{picture} 
\end{center} 
\vspace{-5mm}
\caption{Two-dimensional examples for the eight base relations of
  $\rca$ \label{F:RCC8}} 
\vspace{-2mm} 
\end{figure} 
Constraints are written in the form $\varx R \vary$ where $\varx,
\vary$ are variables for spatial regions and $R$ is an $\rca$
relation. 
We write the union of base relations as $\{R,S\}$. The union of all base relations, the {\em universal relation}, is written as $\{\ast\}$. 
Apart from union $(\cup)$, other operations on relations 
are defined, namely, 
converse $(\mbox{}^{\smile})$, intersection $(\cap)$, and
composition $(\circ)$.   
The formal definitions of these operations are: 
 
\begin{center} 
\begin{tabular}{lrll} 
 $\forall \varx, \vary:$ & $\varx (R \cup S) \vary$ & $\leftrightarrow$ 
 & $\varx R \vary \vee \varx S \vary$, \\ 
 $\forall \varx, \vary:$ & $\varx (R \cap S) \vary$ & $\leftrightarrow$ 
 & $\varx R \vary \wedge \varx S \vary$, \\ 
 $\forall \varx, \vary:$ & $\varx R^{\smile} \vary$ & $\leftrightarrow$ 
 & $\vary R \varx$, \\ 
 $\forall \varx, \vary:$ & $\varx (R \circ S) \vary$ & $\leftrightarrow$ 
 & $\exists \varz: (\varx R \varz \wedge \varz S \vary).$ \\ 
\end{tabular} 
\end{center} 
%
The composition of base relations can be computed from the semantics of
the relations and is usually provided as a 
composition table \cite{randell:et:al:cade-92,bennett:kr-94}. 
The $\rca$ composition table corresponds to the given extensional definition of composition only if the universal region is not permitted \cite{bennett:thesis}. Based on this
table, compositions of  disjunctive
relations can be easily computed. 
In the following, $\widehat{{\cal S}}$ denotes the closure of a set of
$\rca$ relations ${\cal S}$ under 
 composition, intersection, and converse.  

A finite set of $\rca$ constraints $\Theta$ describing the topological
relationships of $n$ different regions can be represented by an $n
\times n$ matrix $M$, where each entry $M_{ij}$ represents the $\rca$
relation holding between region $i$ and region $j$. Without loss of
generality, $M_{ii} = \{\eq\}$ and $M_{ji} = M_{ij}^{\smile}$ can be
assumed. The fundamental reasoning problem  (named  $\RSAT$) in this framework
is deciding {\em consistency} of a set of spatial formulas $\Theta$, i.e.,
%
whether there is a spatial configuration where the
relations between the regions can be described by $\Theta$. 
%
All other interesting reasoning problem can be reduced to it
in polynomial time \cite{golumbic:shamir:jacm-93}. Unfortunately, $\RSAT$ is 
NP-complete \cite{renz:nebel:aij99}, i.e., it is unlikely
that there is any polynomial algorithm for deciding consistency. 
However, it was shown in Nebel's \citeyear{nebel:ki-conf-95} paper 
that there are subsets ${\cal S}$ of $\rca$ for which
the consistency problem (written $\RSAT({\cal S})$) can be decided
in polynomial time.%
\footnote{Strictly speaking, this applies only to systems of regions
  that do not require regularity.} 
In particular the set of eight base relations ${\cal B}$ was shown to
be tractable. From that it follows that $\widehat{\cal B}$ consisting of 32
relations is  also tractable. 
An even larger tractable subset containing all base relations
is $\aha$  \cite{renz:nebel:aij99},
which contains 148 out of the 256 $\rca$ relations.
%
This set was also shown to be
maximal with respect to tractability,
i.e., if any other $\rca$ relation is added, the 
consistency problem becomes NP-complete. 
Renz \citeyear{renz:ijcai-99} made a complete analysis of tractability of
$\RSAT$ by identifying all maximal tractable subsets which contain all
base relations, altogether three subsets $\aha$, $\Qmax$ (160
relations), and $\Cmax$ (158 relations). $\harda$ is the set of relations that by themselves result in $\NP$-completeness when
combined with the set of base relations. It contains the following 76 
relations which are not contained in one of $\aha, \Qmax,$ or $\Cmax$ \cite{renz:ijcai-99}: % 
\begin{eqnarray*} 
\harda &=& \{ R \, | \, \{\po\} \not \subseteq R
\mbox{ and } (\{\ntpp\} \subseteq R \mbox{ or } \{\tpp\} \subseteq R) \\
& & \hspace{6mm} \mbox{ and } (\{\ntppi\} \subseteq R \mbox{ or } \{\tppi\} \subseteq R)\} \\
& & \mbox{} \cup \{\{\ec,\ntpp,\eq\}, \{\dc,\ec,\ntpp,\eq\}, \\
& & \hspace{6mm} \{\ec,\ntppi,\eq\}, \{\dc, \ec,\ntppi,\eq\}\}. 
\end{eqnarray*} 
The maximal tractable subsets contain the following relations 
\cite{renz:ijcai-99}:  
\begin{eqnarray*} 
\aha &=& (\rca \setminus \harda) \setminus \{ R \; | \; (\{\eq, \ntpp\} \subseteq R \mbox{
  and } \{\tpp\} \not \subseteq R) \\
&&  \hspace{15mm} \mbox{ or } (\{\eq,\ntppi\} \subseteq R \mbox{ and }
\{\tppi\} \not \subseteq R) \}\\
\maxone &=& (\rca \setminus \harda) \setminus \{ R \; | \; \{\ec\} \subset R \mbox{
    and }  \{\po\} \not \subseteq R  \mbox{ and }  \\
&&  \hspace{16mm} R \cap \{\tpp,\ntpp,\tppi,\ntppi,\eq\} \neq \emptyset \}\\
\maxtwo &=& (\rca \setminus \harda) \setminus \{ R \; | \; \{\eq\} \subset R \mbox{ and } \{\po\} \not \subseteq R \mbox{ and }  \\
&& \hspace{16mm} R \cap \{\tpp,\ntpp,\tppi,\ntppi\} \neq \emptyset \}
\end{eqnarray*}

All relations of $\Qmax$ are contained in one of $\aha$ or $\Cmax$, i.e., $\aha \cup \Cmax = \rca \setminus \harda$. 
Although $\aha$ is the smallest of the three maximal tractable subsets, it best decomposes the $\rca$ relations: When decomposing an $\rca$ relation $R$ into sub-relations $S_i$ of one of the maximal tractable subsets, i.e., $R = S_1 \cup \ldots \cup S_k$, one needs on average 1.4375 $\aha$ relations, 1.516 $\Qmax$ relations, and 1.523 $\Cmax$ relations for decomposing all $\rca$ relations.
Renz \citeyear{renz:phd} gives a detailed enumeration of the relations of the three sets. 

\subsection{The Path-Consistency Algorithm}
 
As in the area of qualitative temporal reasoning based on Allen's interval
calculus \cite{allen:cacm-83}, the {\em path-consistency algorithm} 
\cite{montanari:is-74,mackworth:ai-77,mackworth:freuder:ai-85} 
can be used to approximate consistency and to realize  {\em
  forward-checking} \cite{haralick:elliot:ai-80} in a backtracking algorithm. 

The path-consistency algorithm checks the consistency of all triples
of relations and 
eliminates  relations that are impossible. 
This is done by iteratively performing the following operation
$$
M_{ij} \leftarrow M_{ij} \cap M_{ik} \circ M_{kj}
$$
for all triples of regions $i,j,k$ until a fixed point $\overline{M}$
is reached. If $\overline{M}_{ij} = \emptyset$ for a pair $i,j$,
then we know that 
$M$ is inconsistent, otherwise $\overline{M}$ is {\em
  path-consistent}.
Computing $\overline{M}$ can be done in $O(n^3)$ time (see
Figure~\ref{alg:bg:constraints:PC}).  
This is achieved by using a {\em queue} of triples of regions for which the
relations should be recomputed \cite{mackworth:freuder:ai-85}. 
\begin{figure}[t]
\begin{center}
%
\fbox{
\parbox{12.3cm}{
{\em Algorithm}: {\sc Path-consistency}
\\
{\em Input}: A set $\Theta$ of binary constraints over the variables  $x_1, x_2, \dots, x_n$ of $\Theta$ \\
\mbox{} \hspace{10mm} represented by an $n \times n$ matrix $M$.
\\
{\em Output}:  path-consistent set equivalent to $\Theta$; {\tt fail}, if such a set does not\\
\mbox{} \hspace{12mm} exist. 
\vspace{-0.2cm}
\begin{tabbing}
~~~\=~~~~~\=~~~~~\=~~~\= \\
1. $Q := \{(i,j,k), (k,i,j) \mid 1 \leq i,j,k \leq n, i < j, k \neq i, k \neq j
\}$; \\
\ \ \ \ \ \ \ \ \ \ ($i$ indicates the $i$-th variable
                                                of
                                                $\Theta$. Analogously
                                                for $j$ and $k$) 
\\
2. {\em while} $Q \neq \emptyset$ {\em do}
\\
3. select and delete a path $(p,r,q)$ from $Q$;
\\
4. \> \> {\em if} {\sc revise}($p,r,q$) {\em then}
\\
5. \> \> \> {\em if} $M_{pq} = \emptyset$ {\em then return} {\tt fail}
\\
6. \> \> \> \> {\em else} $Q :=  Q \cup \{(p,q,s), (s,p,q) \mid 1 \leq s \leq n, s \neq p, s \neq q \}$.
\\
\\
\\
{\em Function}: {\sc revise}$(i,k,j)$ \\
{\em Input}: three labels $i$, $k$ and $j$ indicating the variables $x_i, x_j, x_k$ of $\Theta$\\
{\em Output}: {\tt true}, if $M_{ij}$ is revised; {\tt false} otherwise. \\ 
{\em Side effects}:  $M_{ij}$ and $M_{ji}$ revised using the operations $\cap$ 
and $\circ$  \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ over the constraints involving $x_i$, $x_k$, and $x_j$.
\\ \\ 
%
1.  oldM := $M_{ij}$; 
\\
2.  $M_{ij}$ := $M_{ij} \cap$  ($M_{ik} \circ M_{kj}$);
\\
3.  {\em if} (oldM = $M_{ij}$) {\em then return} {\tt false};
\\
4.  $M_{ji}$ := $M^{\smile}_{ij}$; 
\\
5. {\em return} {\tt true}.
\\
\end{tabbing}
\vspace{-5mm}
\caption{\label{alg:bg:constraints:PC} {\sc Path-consistency} algorithm.}
 }}
\vspace{-4mm}
\end{center}
\end{figure}
Path-consistency does not imply consistency. For instance, 
the following set of spatial constraints is path-consistent but not
consistent:
\vspace{-3mm}
\begin{center} 
\setlength{\unitlength}{0.75mm} 
\begin{picture}(52,25) 
\thinlines 
\multiput(10,0)(40,0){2}{\circle{6}} 
\multiput(10,20)(40,0){2}{\circle{6}} 
\multiput(13,0)(0,20){2}{\vector(1,0){34}} 
\multiput(10,17)(40,0){2}{\vector(0,-1){14}} 
\put(13,18.5){\vector(2,-1){34}} 
\put(47,18.5){\vector(-2,-1){34}} 
\put(10,0){\makebox(0,0){$Z$}} 
\put(10,20){\makebox(0,0){$X$}} 
\put(50,20){\makebox(0,0){$Y$}} 
\put(50,0){\makebox(0,0){$W$}} 
\tiny 
\put(30,-3){\makebox(0,0){$\eq \vee \ntpp$}} 
\put(30,23){\makebox(0,0){$\tpp \vee \tppi$}} 
\put(3,10){\makebox(0,0){$\dc \vee \tpp$}} 
\put(58,10){\makebox(0,0){$\ec \vee \ntpp$}} 
\put(27,16){\makebox(0,0){$\ec \vee \tpp$}} 
\put(27,4){\makebox(0,0){$\ec \vee \tpp$}} 
\end{picture} 
\end{center}
\vspace{2mm}
%
On the other hand, consistency does not imply path-consistency, since path-consistency is not a form of consistency (in its logical sense), but a form of disjunctive non-redundancy. Nevertheless, path-consistency can be enforced to any consistent set of constraints by applying a path-consistency algorithm. 
%
If only relations in $\aha$, $\Qmax$, or $\Cmax$ are used, however,
the path-consistency algorithm is sufficient for deciding consistency, i.e.,  
path-consistency decides $\RSAT(\aha)$, $\RSAT(\Qmax)$, and $\RSAT(\Cmax)$,
\cite{renz:nebel:aij99,renz:ijcai-99}. 

\subsection{The Backtracking Algorithm}

In order to solve an instance $\Theta$ of $\RSAT$, we
have to explore the corresponding search space using some sort of 
backtracking.  In our experiments, we used a backtracking algorithm employed
for solving qualitative temporal reasoning problems
\cite{nebel:constraints-97}, which is based on the algorithm proposed by
Ladkin and Reinefeld \citeyear{ladkin:reinefeld:ai-92}. 
For this algorithm (see Figure~\ref{alg:bg:constraints:BT}) it is necessary to have a subset $\cal S \subseteq \rca$ for which consistency can be decided by using a sound and complete (and preferably polynomial) decision procedure {\sc Decide}. If $\cal S$ contains all base relations, then each relation $R \in \rca$ can be decomposed into sub-relations $S_i \in \cal S$ such that $R = \bigcup_i S_i$. The size of a particular decomposition is the minimal number of sub-relations $S_i$ which is used to decompose $R$.  
The backtracking algorithm successively selects constraints of $\Theta$, backtracks over all sub-relations of the constraints according to their decomposition and decides sub-instances which contain only constraints over $\cal S$ using {\sc Decide}. 

\begin{figure}[t] 
\begin{center}
\fbox{
\parbox{11.3cm}{ 
{\em Algorithm}: {\sc Consistency} 
\\
{\em Input}: A set $\Theta$ of $\rca$ constraints over the variables 
$x_1, x_2, \dots, x_n$ \\
\mbox{} \hspace{9mm} and a subset ${\cal S} \subseteq  
\rca$ that contains all base relations \\
\mbox{} \hspace{9mm} and for which {\sc Decide} is a sound and complete decision \\
\mbox{} \hspace{9mm} procedure. \\
{\em Output}: {\tt true}, iff $\Theta$ is consistent.
\vspace{-0.2cm}
\begin{tabbing}
~~~~~\=~~~~~\=~~~~~\=~~~\= \\
1. {\sc Path-Consistency}($\Theta$)
\\
2. {\em if} $\Theta$ contains the empty relation {\em then return}
{\tt false} 
\\
3. {\em else} choose an unprocessed constraint $x_i R x_j$ and \\
 \> \> split $R$ into $S_1, \ldots, S_k \in \cal S$ such that $S_1
 \cup \ldots \cup S_k = R$
\\ 
4. {\em if} no constraint can be split {\em then return}  {\sc Decide}($\Theta$)
\\
5. {\em for} all refinements $S_l$ ($1 \leq l \leq k$) {\em
  do}
\\
6. \> \> replace $x_i R x_j$ with $x_i S_l x_j$ in $\Theta$ 
\\
7. \> \> {\em if} {\sc Consistency}($\Theta$) {\em then return}
{\tt true}
\\
\end{tabbing}
\vspace{-5mm}
\caption{\label{alg:bg:constraints:BT} Backtracking algorithm for deciding consistency.}
 }}
\vspace{-4mm}
\end{center}
\end{figure}
The (optional) procedure {\sc Path-consistency} in line 1 is used for 
forward-checking and restricts the remaining search space. 
Nebel \citeyear{nebel:constraints-97} showed that this restriction does
not effect soundness and completeness of the algorithm. 
If enforcing path-consistency is sufficient for deciding
$\RSAT({\cal S})$,  
 {\sc Decide}($\Theta$) in line 5 is not necessary. Instead it is
 possible to always return {\tt true} there. 

The efficiency of the backtracking algorithm depends on several
factors. One of them is, of course, the size of the search space which 
has to be explored. 
 A common way of
measuring the size of the search space is the average {\em branching
  factor} $b$ of the search space, i.e., the average number of branches
each node in the search space has (a node is a recursive call of {\sc Consistency}). 
Then the average size of the search space can be computed as
$b^{(n^2-n)/2}$, where $(n^2-n)/2$ is the number of constraints which have to be split when $n$ variables are given. 
For the backtracking algorithm described in
Figure~\ref{alg:bg:constraints:BT} the branching factor 
depends on the average number of relations of the split set $\cal S$
into 
which a relation has to be split. The less splits on average the
better, i.e., it is to be expected that the efficiency of the 
backtracking algorithm depends on the split set $\cal S$ and its 
branching factor.   
Another factor is how the search space is explored. The backtracking
algorithm of Figure~\ref{alg:bg:constraints:BT} offers two possibilities for applying
heuristics. One is in line 3 where the next unprocessed constraint can 
be chosen, the other is in line 5 where the next refinement can be
chosen. These two choices influence the search space and the path
through the search space. 


\section{Test Instances, Heuristics, and Measurement}
\label{S:emp:test-instances}
There is no previous work on empirical evaluation of algorithms for reasoning
with $\rca$ and no benchmark problems are known.  Therefore we randomly
generated our test instances with a given number of regions $n$, an average
label-size $l$, and an average degree $d$ of the constraint graph.  Further, we
used two different sets of relations for generating test instances, the set of
all $\rca$ relations and the set of hard $\rca$ relations $\harda$, i.e., those
76 relations which are not contained in any of the maximal tractable
subsets $\aha$, $\maxone$, or $\maxtwo$. Based on these sets of relations,
we used two models to generate instances, denoted by  $A(n,d,l)$ and
$H(n,d,l)$. The former model uses all relations to generate instances, the
latter only the relations in $\harda$. The instances are generated as
follows:
\begin{enumerate}
\item  A constraint graph with $n$ nodes and an average degree of $d$ for each node is
  generated. This is accomplished by selecting $nd/2$ out of the $n(n-1)/2$
  possible edges using a uniform distribution.
\item  If there is no edge between the $i$th and $j$th node, we set
  $M_{ij} = M_{ji}$ to be the universal relation.
\item Otherwise a non-universal relation is selected according
  to the parameter $l$ such that the average size of 
  relations for selected edges
  is $l$. This is accomplished by selecting one of the
  base relations with uniform distribution and out of the remaining
  7 relations each one with probability $(l-1)/7$.\footnote{This
  method could result in the assignment of a universal constraint to a
  selected link, thereby changing the degree of the
  node. However, since the probability of getting the universal relation
  is very low, we ignore this in the following.}  
  If this results in an allowed relation (i.e., a relation of $\harda$ 
  for $H(n,d,l)$, any $\rca$ relation for $A(n,d,l)$), 
  we assign this relation to the edge. Otherwise
  we repeat the process.
\end{enumerate}

The reason for also generating instances using only relations of 
$\harda$ is that we assume that these instances are difficult to solve since
every relation has to be split during the backtracking search, even if we use
a maximal tractable subclass as the {split set}.  We only generated 
instances of average label size $l=4.0$, since in this case the
relations are equally distributed.   

%
This way of generating random instances is very similar to the way random CSP instances over finite domains are usually generated \cite{gent:et:al:constraints-01}.  
% 
Achlioptas et al.~\citeyear{achlioptas:et:al:cp-97} found that the standard models for generating random CSP instances over finite domains lead to trivially flawed instances for $n \rightarrow \infty$, i.e., instances become locally inconsistent without having to propagate constraints. 
Since we are using CSP instances over infinite domains, Achlioptas et al.'s result does not necessarily hold for our random instances. We, therefore, analyze in the following whether our instances are also trivially flawed for $n \rightarrow \infty$. In order to obtain a CSP over a finite domain, we first have to transform our constraint graph into its dual graph where each of the $n(n-1)/2$ edges $M_{ij}$ of our constraint graph corresponds to a node in the dual graph. Moreover, each of the $n$ variables of the constraint graph corresponds to $n-1$ edges in the dual graph, i.e., the dual graph contains $n(n-1)$ edges and $n(n-1)/2$ nodes. 
In the dual graph, each node corresponds to a variable over the eight-valued domain ${\cal D} = \{\dc, \ec, \po, \tpp, \tppi, \ntpp, \ntppi, \eq\}$. Ternary constraints over these variables are imposed by the composition table, i.e., the composition rules $M_{ij} \subseteq M_{ik} \circ M_{kj}$ must hold for all connected triples of nodes $M_{ij}, M_{ik}, M_{kj}$ of the dual graph ($M_{ij}=M^{\smile}_{ji}$ for all $i,j$). There are {\small $\left(\hspace{-1.7mm}\begin{array}{c}n\vspace{-0.7mm}\\3\end{array}\hspace{-1.7mm}\right)$} $= n(n-1)(n-2)/6$ connected triples in the dual graph. The overall number of triples in the dual graph is {\small $\left(\hspace{-1.7mm}\begin{array}{c}n(n-1)/2\vspace{-0.7mm}\\3 \end{array}\hspace{-1.7mm}\right)$}. 
$nd/2$ unary constraints on the domain of the variables $M_{ij}$ are given, i.e., there are {\small $\left(\hspace{-1.7mm}\begin{array}{c}nd/2\vspace{-0.7mm}\\3 \end{array}\hspace{-1.7mm}\right)$} triples in the dual graph where all nodes are restricted by unary constraints. 
Therefore, the expected number $E^n_{CT}$ of connected triples for which unary constraints are given can be computed as 
\[E^n_{CT} = \frac{\left( \begin{array}{c}n\\3 \end{array} \right) \cdot \left( \begin{array}{c}nd/2\\3 \end{array} \right)}{\left( \begin{array}{c}n(n-1)/2\\3 \end{array} \right)}.\] 
For $n \rightarrow \infty$, the expected number of triples $E^{\infty}_{CT}$ tends to $d^3/6$. 
For the instances generated according to the model $A(n,d,l)$, the probability that the unary constraints which are assigned to a triple lead to a local inconsistency is about $0,0036\%$ (only 58,989 out of the $255^3 = 16,581,375$ possible assignments are inconsistent). 
Since one locally inconsistent triple makes the whole instance inconsistent, we are interested in the average degree $d$ for which the expected number $E^n_{IT}$  of locally inconsistent triples is equal to one. For the model $A(n,d,l)$ this occurs for a value of $d=11.90$, and $E^{\infty}_{IT} = 0.5$ for $d=9.44$. For $n=100$, the expected number of locally inconsistent triples is one for $d=13.98$, and $E^{100}_{IT} = 0.5$ for $d=11.10$.  
For the model $H(n,d,l)$, none of the possible assignments of the triples leads to a local inconsistency, i.e., all triples of the randomly generated instances of the $H(n,d,l)$ model are locally consistent.% 
%
\footnote{This is similar to the result for CSPs over finite domains that by restricting the constraint type, e.g., if only ``not-equal'' constraints as in graph-coloring are used, it is possible to ensure that problems cannot be trivially flawed.}
This analysis shows that contrary to what Achlioptas et al.~found for randomly generated CSP instances over finite domains,
the model $H(n,d,l)$, and the model $A(n,d,l)$ for $d$ small do
not suffer from trivial local inconsistencies.  
%



We solve the randomly generated instances using the backtracking
algorithm described in the previous section. 
The search space on which backtracking is performed depends on the
split set, i.e., the set of sub-relations that is allowed in the
decompositions. 
Choosing the right split-set influences the search noticeably as it influences
the  average branching factor of the search space. 
We choose five different split sets, the three maximal tractable
subsets $\aha, \Qmax,$ and $\Cmax$, the set of base relations ${\cal
  B}$ and the closure of this set $\widehat{\cal B}$ which consists of 38 relations. These sets have
the following branching factors ${\cal B}$: 4.0,
$\widehat{\cal B}$: 2.50 ,$\aha$: 1.438, $\maxone$: 1.523, $\maxtwo$:
1.516. This is, of course, 
 a worst case measure
because the interleaved path-consistency computations reduce the branching
factor considerably \cite{ladkin:reinefeld:amai-96}.

Apart from the choice of the split set there are other heuristics
which influence the efficiency of the search. 
In general it is the best search strategy to proceed with the constraint with the most
constraining relation (line 3 of Figure~\ref{alg:bg:constraints:BT}) and the least constraining choice of a sub-relation (line 5 of Figure~\ref{alg:bg:constraints:BT}).
We investigated two different aspects for choosing the next
constraint to be processed \cite{nebel:constraints-97}. 
\begin{description}
\item[static/dynamic:] Constraints are processed according to a heuristic
  evaluation of their constrainedness which is determined {\em
    statically} before the backtracking starts or {\em dynamically}
  during the search.
\item[local/global:] The  evaluation of the constrainedness
  is based on a {\em local} heuristic weight criterion or on a {\em
    global} heuristic criterion \cite{beek:manchak:jair-96}.
\end{description}
This gives us four possibilities we can combine with the
five different split sets, i.e., a total number of 20 different
heuristics.   
%
The evaluation of constrainedness as well as how relations are decomposed into relations of different split sets depends on the {\em restrictiveness} of relations, which is a heuristic criterion \cite{beek:manchak:jair-96}.  
Restrictiveness of a relation is a measure of how a relation restricts its neighborhood. For instance, the universal relation given in a constraint network does not restrict its neighboring relations at all, the result of the composition of any relation with the universal relation is the universal relation. The identity relation, in contrast, restricts its neighborhood a lot. In every triple of variables where one relation is the identity relation, the other two relations must be equal. Therefore, the universal relation is usually the least restricting relation, while the identity relation is usually the most restricting relation. 
Restrictiveness of relations is represented as a weight in the range of $1$ to $16$ assigned to every relation, where $1$ is the value of the most and $16$ the value of the least restricting relation. 
We discuss in the following section in detail how the restrictiveness and the weight of a relation is determined. 

Given the weights assigned to every relation, we compute decompositions and estimate constrainedness as follows.  
For each split set $\cal S$ and for each $\rca$ relation $R$ we compute the smallest decomposition of $R$ into sub-relations of $\cal S$, i.e., the decomposition which requires the least number of sub-relations of $\cal S$. If there is more than one possibility, we choose the decomposition with the least restricting sub-relations.  
In line 5 of the backtracking algorithm (see Figure~\ref{alg:bg:constraints:BT}), the least restricting sub-relation of each decomposition is processed first. 
For the local strategy, the constrainedness of a constraint is determined by the size of its decomposition (which can be different for every split set) and by its weight. 
We choose the constraint with the smallest decomposition larger than one and, if there is more than one such constraint, the one with the smallest weight. The reason for choosing the relation with the smallest decomposition is that it is expected that forward-checking refines relations with a larger decomposition into relations with a smaller decomposition. This reduces the backtracking effort. 
For the global strategy, the constrainedness of a constraint $xRy$ is determined by adding the weights of all neighboring relations $S,T$ with $xSz$ and $zTy$ to the weight of $R$. The idea behind this strategy is that when refining the relation $R$ with the most restricted neighborhood, an inconsistency is detected faster than when refining a relation with a less restricted neighborhood.    


In order to evaluate the quality of the different heuristics, we
measured the run-time used for solving instances as well as the number 
of visited nodes in the search space. Comparing different approaches
by their run-time is often not very reliable as it depends on several
factors such as the implementation of the algorithms, the used
hardware, or the current load of the used 
machine which makes results sometimes not reproducible. 
For this reason, we ran all our run-time experiments on the same machine, a Sun Ultra 1
with 128 MB of main memory. Nevertheless, we suggest to use the
run-time results mainly for qualitatively comparing different
heuristics and for getting a rough idea of the order of magnitude for which
instances can be solved. 

In contrast to this, the number of visited nodes for solving an
instance with a particular heuristic is always the same on every
machine. This allows comparing the path  through the
search space taken by the single heuristics and to judge which
heuristic makes the better choices on average. 
However, this does not take into account the time that is needed to
make a choice at a single node. Computing the local constrainedness of
a constraint is certainly faster than computing its global
constrainedness. Similarly, computing constrainedness statically
should be faster than computing it dynamically. 
Furthermore, larger instances require more time at the nodes than
smaller instances, be it for computing path-consistency or for
computing the constrainedness. 
Taking running-time and the number of visited nodes together gives good
indications of the quality of the heuristics. 

A further choice we make in evaluating our measurements is that of how to
aggregate the measurements of the single instances to a total
picture.  Some possibilities are to use either the average or different
percentiles such as the median, i.e., the 50$\%$
percentile. The $d\%$ percentile for a value $0 < d < 100$ is
obtained by sorting the measurements in increasing order and picking
the measurement of the $d\%$ element, 
%
i.e., $d\%$ of the values are less than that value. 
%
Suppose that most instances have a low value (e.g. running time)
and only a few instances have a very large value. Then the average
might be larger than the values of almost all instances, while in this 
case the median is a better indication of the distribution of the
values. In this case the 99$\%$ percentile, for instance, gives a good 
indication of the value of the hardest among the ``normal''
instances. 
We have chosen to use the average value when the measurements are well
distributed and to use both 50$\%$ and 99$\%$ percentile when there
are only a few exceptional values in the distribution of the measurements. 

   

\section[Empirical Evaluation of the Path-Consistency
Algorithm]{Empirical Evaluation of the Path-Consistency Algorithm 
\label{S:emp:path-consistency}
\markright{\ref{S:emp:path-consistency}. EMPIRICAL EVALUATION OF PATH-CONSISTENCY}}
\markright{\ref{S:emp:path-consistency}. EMPIRICAL EVALUATION OF PATH-CONSISTENCY}

Since the efficiency of the backtracking algorithm
depends on the efficiency of the underlying path-consistency
algorithm, we will first compare different implementations of
the path-consistency algorithm. 
In previous empirical investigations \cite{beek:manchak:jair-96} of
reasoning with Allen's interval 
relations \cite{allen:cacm-83}, different methods for computing
the composition of two relations were evaluated. This was mainly
because the full composition table for the interval relations contains 
$2^{13} \times 2^{13} = 67108864$ entries, which was too large at that
time to be stored in the main memory. 
In our setting,
we simply use a composition table that specifies the compositions of all
$\rca$ relations, which is a  $256 \times 256$ table consuming approximately  128 KB
of main memory. This means that the composition of two arbitrary relations
is done by a simple table lookup.

Van Beek and Manchak \citeyear{beek:manchak:jair-96} also studied the
effect of weighting the relations in the queue according to their
restrictiveness and process the most restricting relation first. 
Restrictiveness was measured for each base relation by successively composing the base relation with every possible label, summing up the cardinalities, i.e., the number of base relations contained in the result of the composition, and suitably scaling the result. 
The reason for doing  so is that the most restricting relation restricts the other 
relations on average most and therefore decreases the probability that
they have to be processed again. Restrictiveness of a complex relation was
approximated by summing up the restrictiveness of the involved base
relations.
Van Beek and Manchak \citeyear{beek:manchak:jair-96} found that their method of weighting the triples in the queue is much more  
efficient than randomly picking an arbitrary triple. 
Because of the relatively small number of $\rca$ relations, we computed the
exact restrictiveness by composing each relation with every other relation and summing up the cardinalities of the resulting compositions. We scaled the result into weights from 1 (the most restricting relation) to 16 (the least restricting relations).  

This gives us three different implementations of the path-consistency
algorithm. One in which the entries in the queue are not weighted, 
one with approximated restrictiveness as done by van Beek and Manchak, 
and one with exact restrictiveness.%
\footnote{For the weighted versions we
select a path ($i,k,j$) 
from the queue $Q$ in 
line 3 of the algorithm of Figure~\ref{alg:bg:constraints:PC} according to the weights of the different
paths in $Q$ which are computed as specified above.} 
 In order to compare these implementations, we randomly generated
instances with 50 to 
1,000 regions. For each value of the average degree ranging from 8.0
stepping with 0.5 to 11.0 we generated 10 different
instances. 
\begin{figure}[t]
\begin{center}
%
    \epsfxsize=110mm
    \leavevmode
    \epsfbox{path-cons.eps}
  \caption[Comparing the performance of the path-consistency
      algorithm using different methods for weighting the queue]{Comparing the performance of the path-consistency
      algorithm using different methods for weighting the queue (70
      instances/data point, $d=8.0 - 11.0$)}
    \label{fig:emp:path-consistency}
\end{center}
\end{figure}
 Figure~\ref{fig:emp:path-consistency} displays the average CPU time of the
 different methods for applying the path-consistency algorithm to the
 same generated instances.
It can be seen that the positive effect of using a weighted queue is much
greater for our problem than for the temporal problem (about $10\times$ faster
than using an ordinary queue without weights 
compared to only about $2\times$ faster \cite{beek:manchak:jair-96}).  
Determining the weights of every relation using their exact restrictiveness
does not have much advantage over approximating their restrictiveness
using the approach by van Beek and Manchak \citeyear{beek:manchak:jair-96},
however. For our further experiments we always used the ``exact weights''
method because  determining the restrictiveness amounts to just one table
lookup. 

As mentioned in the previous section, one way of measuring the quality of
the heuristics is to count the number of visited nodes in the
backtrack search. In our backtracking algorithm, path-consistency is enforced in every visited
node. 
Note that it is not adequate to multiply the average running-time for
enforcing path-consistency of an instance of a particular size with
the number of visited nodes in order to obtain an approximation of the required running time for
that instance. 
The average running-time for enforcing path-consistency as given in
Figure~\ref{fig:emp:path-consistency} holds only when all possible paths
are entered into the queue at the beginning of the computation (see
line 1 of Figure~\ref{alg:bg:constraints:PC}).  
These are the paths which have to be checked by the algorithm. 
The path-consistency computation during the backtracking search is
different, however. There, only the paths involving the currently
changed constraint are entered in the queue, since only these paths
might result in changes of the constraint graph. This is much faster 
than the full computation of path-consistency which is only done once
at the beginning of the backtrack search. 


\section{The Phase-Transition of RCC-8}
\label{S:emp:phase-transition}
When randomly generating problem instances there is usually a problem-dependent parameter which determines the solubility of the instances. In one parameter range instances are underconstrained and are therefore soluble with a very high probability. In another range, problems are overconstrained and soluble with a very low probability. In between these ranges is the {\em phase-transition region} where the probability of solubility changes abruptly from very high to very low values \cite{cheeseman:et:al:ijcai-91}. 
In order to study the quality of different heuristics and algorithms
with randomly 
generated instances of an \NP-complete problem, it is very important to
be aware of the phase-transition behavior of the problem. 
This is because instances which are not contained in the phase-transition
region are often very easily solvable by most algorithms and
heuristics and are, thus, not very useful for comparing their
quality. Conversely, hard instances which are better suited for
comparing the quality of algorithms and heuristics are usually found
in the phase-transition region. 

In this section we identify the phase-transition region of
randomly generated instances of the $\RSAT$ problem, both for
instances using all $\rca$ relations and for instances using only
relations of $\harda$.  
Similarly to the empirical analysis of qualitative temporal reasoning problems
\cite{nebel:constraints-97}, it turns out that the  phase-transition
 depends most strongly on the average degree $d$  
of the nodes in the constraint graph. 
 If all relations are allowed, the phase-transition is
around $d=8$ to $d=10$ depending on the instance size (see Figure~\ref{fig:emp:phase-transition-all}). 
Because of the result of our theoretical analysis of the occurrence of trivial flaws (see Section~\ref{S:emp:test-instances}), it can be expected that for larger instance sizes the phase-transition behavior will be overlaid and mainly determined by the expected number of locally inconsistent triples which also depends on the average degree $d$. 
Thus, although it seems that the phase-transition shifts towards larger values of $d$ as the instance size increases, the phase-transition is asymptotically below $d=9.44$, the theoretical value for $n \rightarrow \infty$ (see Section~\ref{S:emp:test-instances}).    
\begin{figure}[t]
\begin{center}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{phase-trans_all.eps}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{median-all-hornsplit.eps}
    \caption[Probability of satisfiability and median CPU time for
      $A(n,d,4.0)$]{Probability of satisfiability and median CPU time for
      $A(n,d,4.0)$ using the $\aha$/static/global heuristic 
      (500 instances per data point)} 
    \label{fig:emp:phase-transition-all}
\end{center}
\end{figure}
Instances which are not path-consistent can be solved very fast by just one application of the path-consistency algorithm without further need for backtracking. 
When looking at the median CPU times given in Figure~\ref{fig:emp:phase-transition-all}, one notices that there is a sharp decline of the median CPU times at the phase transition. 
%
This indicates that for values of the average degree which are higher than where the phase-transition occurs, at least 50$\%$ of the instances are not path-consistent.  
%

When using only ``hard'' relations, i.e., relations in $\harda$,
the phase-transition appears at higher values for $d$, namely, between 
$d=10$ and $d=15$ (see
Figure~\ref{fig:emp:phase-transition-hard}). 
As the median runtime shows, 
 these instances are much harder in the phase-transition than in the
 former case. 
As in the previous case, but even more strongly, it seems that the phase-transition shifts towards larger values of $d$ as the instance size increases, and also that the phase-transition region narrows. 
%

\begin{figure}[t]
\begin{center}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{phase-trans_hard.eps}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{median-hard-hornsplit-fe.eps}
    \caption[Probability of satisfiability and median CPU time for
      $H(n,d,4.0)$]{Probability of satisfiability and median CPU time for
      $H(n,d,4.0)$ using the $\aha$/static/global heuristic 
      (500 instances per data point)}
    \label{fig:emp:phase-transition-hard}
\end{center}
\end{figure}
%

In order to evaluate the quality of the path-consistency method as an
approximation to consistency, we counted the number of instances
that are inconsistent but path-consistent (see
Figure~\ref{fig:emp:pc-fail}), i.e., those instances where the
approximation of the path-consistency algorithm to consistency is wrong. 
First of all, one notes that all such instances are close to the phase
transition region. 
In the general case, i.e., when constraints over all $\rca$ relations
are employed, only a very low percentage of instances are path-consistent but inconsistent. Therefore, the figure looks very erratic. More data points would be required in order to obtain a smooth curve. 
However, a few important observations can be made from this figure, namely, that path-consistency gives an excellent approximation to
consistency even for instances of a large size. Except for very few instances in the phase-transition
region, almost all instances which are path-consistent are also
consistent. 
This picture changes when looking at the $H(n,d,4.0)$ case. 
Here almost all instances in the phase-transition region and many
instances in the mostly insoluble region are
path-consistent, though only a few of them are consistent. 
\begin{figure}[t]
\begin{center} 
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{pc-fail_all.eps}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{pc-fail_hard.eps}
   \caption[Percentage points of incorrect answers of the
      path-consistency algorithm]{Percentage points of incorrect answers of the
      path-consistency algorithm for $A(n,d,4.0)$ and $H(n,d,4.0)$ }
    \label{fig:emp:pc-fail}
\end{center}
\end{figure}

%
For the following evaluation of the different heuristics we will
 randomly generate instances with an average degree between $d=2$ and
 $d=18$ in the $A(n,d,4.0)$ case and between $d=4$ and $d=20$ in the
 $H(n,d,4.0)$ case. This covers a large area around the
 phase-transition. 
We expect the instances in the phase-transition region of $H(n,d,4.0)$ 
to be particularly hard which makes them very interesting for
comparing the quality of the different heuristics. 


\section{Empirical Evaluation of the Heuristics}
\label{S:emp:evaluation}

In this section we compare the different heuristics by running them on 
the same randomly generated instances. For the instances of
$A(n,d,4.0)$ 
we ran all 20 different heuristics ({\em static/dynamic} and
{\em local/global} combined with the five split sets ${\cal B}, \widehat{\cal B}, 
\aha, \Cmax, \Qmax$) on the same randomly
generated instances of size $n=10$ up to $n=100$. 
For the instances of $H(n,d,4.0)$ we restricted ourselves to
instances with up to $n=80$ regions because larger ones appeared to be
too difficult. 

In first experiments we found that most of the instances were solved
very fast with less than 1,000 visited nodes in the search space when
using one of the maximal tractable subsets for splitting. However,
some instances turned out to be 
extremely hard, they could not be solved within our limit of 2
million visited nodes, which is about 1.5 hours of CPU time. 
Therefore, we ran all our programs up to a maximal number of 10,000
visited nodes and stored all instances for which at least one of the
different heuristics used more than 10,000
visited nodes for further experiments (see next
section). We call those instances the {\em hard instances}. 
The distribution of the hard instances is shown in
Figure~\ref{F:hard-distribution}. 
\begin{figure}
\begin{center}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{hardest_all.eps}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{hardest_hard.eps}
%
    \caption[Number of instances using more than 10,000 visited
    nodes]{Number of instances using more than 10,000 visited nodes 
      for some heuristic for $A(n,d,4.0)$ and $H(n,d,4.0)$}
    \label{F:hard-distribution}
%
\end{center}
\end{figure}
It turned out that for the heuristics using $\cal B$ as a split set and
for the heuristics using {\em dynamic} and {\em global} evaluation of the
constrainedness many more instances were hard than for the other
combinations of heuristics. 
We, therefore, did not include in Figure~\ref{F:hard-distribution} the
hard instances of the $\cal B$/{\em dynamic}/{\em global} heuristic for
$A(n,d,4.0)$ and the hard instances for the heuristics using $\cal B$
as a split set 
and the $\widehat{\cal B}$/{\em dynamic}/{\em global} heuristic for $H(n,d,4.0)$. 

As Figure~\ref{F:hard-distribution} shows, almost all of
the hard instances are in the phase-transition region. For
$A(n,d,4.0)$ only a few of the 500 instances per data point are hard
while for $H(n,d,4.0)$ almost all instances in the phase-transition
are hard. Altogether there are 788 hard instances for $A(n,d,4.0)$ (out
of a total number of 759,000 generated instances) and 75,081 hard instances 
for $H(n,d,4.0)$ (out of a total number of 594,000 generated
instances). 
\begin{table}[hbt]
\begin{center}
\footnotesize
\setlength{\tabcolsep}{1mm}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{|c|c|c|c|}
\hline
Heuristics & $A(n,d,4.0)$ & $H(n,d,4.0)$ & $H(80,14.0,4.0)$ 
 \\
\hline
\aha/sta/loc & $64$ & $21,129$ & $331$\\ %3
\aha/sta/glo & $42$ & $10,826$ & $227$\\ %0
\aha/dyn/loc & $52$ & $9,967$ & $217$\\ %1
\aha/dyn/glo & $100$ & $24,038$ & $345$\\ %2
\Cmax/sta/loc & $81$ & $28,830$ & $373$\\ %7
\Cmax/sta/glo & $58$ & $15,457$ & $277$\\ %8
\Cmax/dyn/loc & $78$ & $32,926$ & $412$\\ %5
\Cmax/dyn/glo & $108$ & $41,565$ & $428$\\ %6
\Qmax/sta/loc & $81$ & $24,189$ & $346$\\ %11
\Qmax/sta/glo & $54$ & $13,189$ & $239$\\ %8
\Qmax/dyn/loc & $74$ & $13,727$ & $255$\\ %9
\Qmax/dyn/glo & $104$ & $29,448$ & $368$\\ %10
$\widehat{\cal B}$/sta/loc & $68$ & $23,711$ & $344$\\ %15
$\widehat{\cal B}$/sta/glo & $89$ & $13,831$ & $249$\\ %12
$\widehat{\cal B}$/dyn/loc & $70$ & $29,790$ & $379$\\ %13
$\widehat{\cal B}$/dyn/glo & $162$ & --  & --\\ %14
${\cal B}$/sta/loc & $163$ & -- & --\\ %19
${\cal B}$/sta/glo & $222$ & -- & --\\ %16
${\cal B}$/dyn/loc & $209$ & -- & --\\ %17
${\cal B}$/dyn/glo & $(303)$ & -- & --\\ %18
\hline
total & $788$ & $75,081$ & $486$ \\
\hline
\end{tabular}
%
\caption{Number of hard instances for each heuristic \label{T:hard-instances}} 
%
\end{center}
\end{table}
Table~\ref{T:hard-instances} shows the number of hard instances for
each heuristic except for those which were excluded as mentioned above. The heuristics using $\aha$ as a split set solve more
instances than the heuristics using other split sets. Using $\Cmax$ or 
$\Qmax$ as a split set does not seem to be an improvement over using
$\widehat{\cal B}$. Among the different ways of computing
constrainedness, {\em static} and {\em global} appears to be the most effective
combination when using one of the maximal tractable subsets as a
split set. For some split sets, {\em dynamic} and {\em local} also seems to be an
effective combination while combining {\em dynamic} and {\em global} is in
all cases the worst choice with respect to the number of solved
instances. 


In Figure~\ref{F:comparing-heuristics_all} we compare the $50\%$ and
$99\%$ percentiles of the 
different heuristics 
on $A(n,d,4.0)$. We do not give the average run times since we ran all heuristics only up to at most 10,000 visited nodes which reduces the real average run time values.   
Each data point is the average of the values
for $d=8$ to $d=10$. We took the average of the different degrees in
order to cover the whole phase-transition region which is about $d=8$ for
instances of size $n=10$ and $d=10$ for instances of size $n=100$. 
\begin{figure}
 \begin{center}
\mbox{}
\vspace{3mm}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_all-f.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_all-f.eps}
\vspace{3mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_all-fe.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_all-fe.eps}
\vspace{3mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_all.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_all.eps}
\vspace{3mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_all-e.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_all-e.eps}

%
    \caption{Percentile $50\%$ and $99\%$ CPU time of the different
      heuristics for solving $A(n,d,4.0)$ $(d = 8.0$ to 
      $d=10.0$, 2,500 instances per data point)}
    \label{F:comparing-heuristics_all}
\end{center}
\end{figure}
For all different combinations of computing constrainedness, the ordering 
of the run times is the same for the different split sets: ${\cal B} \gg 
\widehat{\cal B} > \Cmax,\aha,\Qmax$. 
The run times of using {\em static}/{\em local}, {\em static}/{\em global}, or {\em 
  dynamic}/{\em local} 
for computing constrainedness are almost the same when combined with
the same split set while they are longer for all split sets when using
{\em dynamic}/{\em global} (about 3 times longer when using $\widehat{\cal B}$ as a
split set and
about 1.5 times longer when using the other split sets).  
The $99\%$ percentile run times are only about 1.5 times longer than
the $50\%$ percentile run times. Thus, even the harder among the
``normal'' instances can be solved easily, i.e., apart from a few hard 
instances, most instances can be solved efficiently within the size
range we analyzed. 
The erratic behavior of the median curves results from an aggregation of the 
effect which can be observed in Figure~\ref{fig:emp:phase-transition-all},
 namely, that some of the median elements in the phase-transition are 
 inconsistent and easily solvable. 
%

For the runtime studies for $H(n,d,4.0)$ we noticed that  there are 
 many hard instances  for $n > 40$ (see
Figure~\ref{F:hard-distribution}), for $n=80$ almost all instances in
the phase-transition region are 
hard (see last column of Table~\ref{T:hard-instances}). Also, as
Table~\ref{T:hard-instances} shows, the 
number of hard instances varies a lot for the different heuristics. 
Therefore, it is not possible to compare the percentile running times
of the different heuristics for $n > 40$. For $n=80$ and $d=14$ (see last column of Table~\ref{T:hard-instances}), for instance, the
$50\%$ and $99\%$ percentile element of the $\Cmax$/{\em dynamic}/{\em global} heuristic is
element no.36 and element no.72, while it is element no.141 and
element no.280 of the $\aha$/{\em dynamic}/{\em local} heuristic (out of the 500 sorted elements), respectively. 

For this reason we show the results only up to a size of $n=40$ (see
Figure~\ref{F:comparing-heuristics_hard}).  
\begin{figure}
 \begin{center}
\mbox{}
\vspace{3mm}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_hard-f.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_hard-f.eps}
\vspace{3mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_hard-fe.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_hard-fe.eps}
\vspace{3mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_hard.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_hard.eps}
\vspace{3mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{med_hard-e.eps}
%\hspace{5mm}
   \epsfxsize=60mm
    \leavevmode
    \epsfbox{nn_hard-e.eps}
    \caption{Percentile $50\%$ and $99\%$ CPU time of the different
      heuristics for solving $H(n,d,4.0)$ $(d = 10.0$ to 
      $d=15.0$, 5,500 instances per data point)}
    \label{F:comparing-heuristics_hard}
\end{center}
\end{figure}
%
Again, we took the average
of the different degrees from $d=10$ to $d=15$ in order to cover the
whole phase-transition region. The order of the run times is the same
for different combinations of computing constrainedness: ${\cal B} \gg \widehat{\cal B},\Cmax \gg 
\Qmax,\aha$, while $\aha$ is in most cases the fastest.  
As for the $A(n,d,4.0)$ instances,
 the run times for {\em
   dynamic}/{\em global} were much longer than the other
 combinations. 
The $99\%$ percentile run times of the {\em static}/{\em global} combination and for $\aha$ and $\Qmax$
 of the  {\em  dynamic}/{\em local} combination are faster than those
 of the other combinations.  
Although the median CPU times are about the same
as for $A(n,d,4.0)$ for $n < 40$, the percentile $99\%$ CPU times are much longer. 
As it was already shown in Figure~\ref{fig:emp:pc-fail} and \ref{F:hard-distribution}, this is further evidence that there are very
hard instances in the phase-transition region of $H(n,d,4.0)$. 
 

\section{Orthogonal Combination of the Heuristics}
\label{S:emp:orthogonal}
In the previous section we studied the quality of different
heuristics for solving randomly generated $\RSAT$ instances. 
We found that several instances which are mainly located in the
phase-transition region could not be solved by some heuristics
within our limit of 
10,000 visited nodes in the search space. 
Since the different heuristics have a different search space
(depending on the split set) and use a different path through the
search space (determined by the different possibilities of computing
constrainedness),  
it is possible that instances are hard for some heuristics but easily 
solvable for other heuristics. 
Nebel \citeyear{nebel:constraints-97} observed that running different
heuristics in parallel can solve more instances of a particular hard
set of temporal reasoning instances proposed by van Beek and Manchak
\citeyear{beek:manchak:jair-96} than any single
heuristic alone can solve, when using altogether the same number of visited nodes as for each heuristic alone. 
An open question of Nebel's investigation \cite{nebel:constraints-97}
was whether this is also the case for the hard instances in the 
phase-transition region. 

In this section we evaluate the power of ``orthogonally combining'' the
different heuristics for solving $\RSAT$ instances,  
%
i.e., running the different heuristics for each instance in parallel until one of the heuristics solves the instance. 
There are different ways for simulating this parallel processing on a single processor machine. One is to use time slicing between the different heuristics, another is to run the heuristics in a fixed or random order until a certain number of nodes in the search space is visited and if unsuccessful try the next heuristic (cf.~Huberman, Lukose, \& Hogg, 1997). %
Which possibility is chosen and with which parameters (e.g., the order in which the heuristics are run and the number of visited nodes which is spent for each heuristic) determines the efficiency of the single processor simulation of the orthogonal combination. 
In order to find the best parameters, we ran all heuristics using at most 10,000 visited nodes for each heuristic on the set of hard instances identified in the previous section (those instances for which at least one heuristic required more than 10,000 visited nodes) and compared their behavior. 
Since we ran all heuristics on all instances already for the experiments of the previous section, we only had to evaluate their outcomes.
%  
This led to a very surprising result
for the $A(n,d,4.0)$ instances, namely, all of the 788 hard
instances except for a single one were solved by at least one of the
heuristics using less than 10,000 visited nodes. 
 In Table~\ref{T:compare-heurisics} we list
the percentage of hard instances that could be solved
by the different heuristics and the percentage of first response
 by each of them when running the heuristics in parallel (i.e., which
 heuristic required the smallest number of visited nodes for solving the instance).  
%
\begin{table}[t]
\footnotesize
\setlength{\tabcolsep}{1mm}
\renewcommand{\arraystretch}{1.1}
\begin{center}
\begin{tabular}{|c|cc|cc|}
\hline
 & \multicolumn{2}{c|}{$A(n,d,4.0)$} &
 \multicolumn{2}{c|}{$H(n,d,4.0)$ }
 \\
Heuristics & \makebox[25mm]{Solved Instances} & \makebox[20mm]{1.~Response} &
\makebox[25mm]{Solved Instances} & \makebox[20mm]{1.~Response} \\
\hline
\aha/sta/loc & $91.88\%$ & $19.80\%$ & $71.86\%$ & $6.92\%$\\ %3
\aha/sta/glo & $94.67\%$ & $12.56\%$ & $85.58\%$ & $14.26\%$\\ %0
\aha/dyn/loc & $93.40\%$ & $24.37\%$ & $86.73\%$ & $22.28\%$\\ %1
\aha/dyn/glo & $87.31\%$ & $13.58\%$ & $67.98\%$ & $15.00\%$\\ %2
\Cmax/sta/loc & $89.72\%$ & $6.35\%$ & $61.60\%$ & $1.47\%$\\ %7
\Cmax/sta/glo & $92.64\%$ & $5.20\%$ & $79.41\%$ & $5.04\%$\\ %8
\Cmax/dyn/loc & $90.10\%$ & $5.96\%$ & $56.15\%$ & $2.26\%$\\ %5
\Cmax/dyn/glo & $86.63\%$ & $6.60\%$ & $44.64\%$ & $2.40\%$\\ %6
\Qmax/sta/loc & $89.72\%$ & $9.77\%$ & $67.78\%$ & $1.63\%$\\ %11
\Qmax/sta/glo & $93.15\%$ & $12.06\%$ & $82.43\%$ & $3.61\%$\\ %8
\Qmax/dyn/loc & $90.61\%$ & $10.15\%$ & $81.72\%$ & $1.83\%$\\ %9
\Qmax/dyn/glo & $86.80\%$ & $12.82\%$ & $60.78\%$ & $4.61\%$\\ %10
$\widehat{\cal B}$/sta/loc & $91.37\%$ & $1.40\%$ & $68.42\%$ & $1.84\%$\\ %15
$\widehat{\cal B}$/sta/glo & $88.71\%$ & $1.27\%$ & $81.58\%$ & $5.22\%$\\ %12
$\widehat{\cal B}$/dyn/loc & $91.12\%$ & $0.89\%$ & $60.32\%$ & $2.56\%$\\ %13
$\widehat{\cal B}$/dyn/glo & $79.44\%$ & $0.89\%$ & -- & $1.83\%$ \\ %14
${\cal B}$/sta/loc & $79.31\%$ & $0.51\%$ & -- & $1.67\%$\\ %19
${\cal B}$/sta/glo & $71.83\%$ & $0.25\%$ & -- & $1.13\%$\\ %16
${\cal B}$/dyn/loc & $73.48\%$ & $0.51\%$ & -- & $0.42\%$\\ %17
${\cal B}$/dyn/glo & -- & $0.13\%$ & --  & $0.49\%$\\ %18
\hline
combined & $99.87\%$ & & $96.48\%$ & \\
\hline
\end{tabular}
\end{center}
%\vspace{-3mm}
\caption[Orthogonal combination of the different heuristics]{\label{T:compare-heurisics}Percentage of solved hard
 instances for each heuristic and percentage of first response when
 orthogonally running all heuristics. Note that sometimes different
 heuristics are equally fast. Therefore the sum is more than 100$\%$.} 
%\vspace{-6mm}
\end{table}
%
It turns out that the heuristics using $\aha$ as a split set did not
only solve more instances than the other heuristics, they were also
more often the fastest in finding a solution. 
Although the heuristics using the other two maximal tractable subsets
$\Qmax$ and $\Cmax$ as a split set did not solve significantly more
instances than the heuristics using $\widehat{\cal B}$, they were much 
faster in finding a solution. Despite solving the least number of
instances, the heuristics using $\cal B$ as a
split set were in some cases the fastest in producing a solution.  

When comparing the minimal number of visited nodes
 of all the heuristics for all the hard instances, we found that
only five of them (which were all inconsistent) required more than 150
visited nodes. This is particularly 
remarkable as all these instances are from the phase-transition region of an
NP-hard problem, i.e., instances which are usually considered to be the most
difficult ones.  Further note that about
$15\%$ (120) of the 788 (path-consistent) instances were inconsistent, which is much higher than
usual (cf.~Figure~\ref{fig:emp:pc-fail}). Interestingly, most of
those inconsistent instances were solved faster than the consistent
instances. 
At this point, it
should be noted that combining heuristics orthogonally is very
similar to randomized search techniques with restarts
\cite{selman:et:al:aaai-92}. However, in contrast to
randomized search, our method can also determine whether an instance is
inconsistent. 
In Figure~\ref{F:emp:fastest-solution} we chart the number of hard
instances solved with the smallest number of visited nodes
with respect to their solubility. 
Due to the low number of hard instances of $A(n,d,4.0)$, the figure on the left looks a bit ugly but one can at least approximate the behavior of the curves when comparing it with the second figure on the right which is the same curve for $H(n,d,4.0)$ (see below). 
The oscillating behavior of the
inconsistent instances (more instances are solved with an odd than
with an
even number of visited nodes) might be due to the sizes of the
instances---we generated instances with an even number of nodes only.  
%
\begin{figure}
 \begin{center}
%   
\leavevmode
  \epsfig{file=easy-statistics-all.eps,width=60mm}
\leavevmode
  \epsfig{file=easy-statistics-hard.eps,width=60mm}
  \end{center}
\caption{Fastest solution of the hard instances when running all
  heuristics in parallel \label{F:emp:fastest-solution}} 
\end{figure}
%
The most difficult instance ($n=56,d=10$) was solved as inconsistent with the
$\widehat{\cal B}$/{\em static}/{\em global} heuristic using about
91,000 visited nodes while all heuristics using one of the maximal
tractable subsets as a split set failed to solve it even when each was allowed to visit 20,000,000 nodes in the search space. 


We did the same examination for the set of 75,081 hard instances
of $H(n,d,4.0)$. 
2,640 of these instances could not be solved by any of the 20
different heuristics using 10,000 visited nodes each. 
Their distribution is shown in Figure~\ref{F:hardest-distribution}(a). 
\begin{figure}
\begin{center}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{hardest_hard-combined.eps}
 \epsfxsize=60mm
    \leavevmode
    \epsfbox{hard-statistics.eps} 

(a) \hspace{60mm} (b)
%\vspace{-8mm}
    \caption[Hard instances using orthogonal
      combination of all heuristic for $H(n,d,4.0)$]{Hard instances using orthogonal
      combination of all heuristic for $H(n,d,4.0)$, (a) shows their
      distribution, (b) shows their fastest solution when using up to 100,000 visited nodes per heuristic}
    \label{F:hardest-distribution}
%\vspace{-4mm}
\end{center}
\end{figure}
Similar to the hard instances of $A(n,d,4.0)$, the heuristics using
$\aha$ as a split set were the most successful ones for solving the
hard instances of $H(n,d,4.0)$, as shown in
Table~\ref{T:compare-heurisics}. 
They solved more of the hard instances than any other heuristics and
produced the fastest 
response of more than $50\%$ of the hard instances. There is no
significant difference between using $\Cmax, \Qmax,$ or $\widehat{\cal 
  B}$ as a split set, neither in the number of solved instances nor in 
the percentage of first response. 
Like in the previous case, computing constrainedness using the
{\em static}/{\em global} or the {\em dynamic}/{\em local} heuristics resulted in more
successful paths through the search space by which more instances
were solved within 10,000 visited nodes than by the other combinations. 
On average they produced faster solutions than the other
combinations. 

The same observations as for $A(n,d,4.0)$ can be made when charting
the fastest solutions of the hard instances of $H(n,d,4.0)$ (see
Figure~\ref{F:emp:fastest-solution}). About $29\%$ (21,307) of the
solved instances are inconsistent. Most of them were, again, solved
faster than the consistent instances. More than $75\%$ of the hard
instances can be solved with at most 150 visited nodes. $90\%$ can be
solved with at most 1,300 visited nodes. 
Since the $\aha$/{\em dynamic}/{\em local} heuristic alone solves more than $86\%$ of
the instances, it seems difficult to combine different heuristics in a
way that more hard instances can be solved while using  not more
than 10,000 visited nodes altogether. However, when orthogonally combining the
two best performing 
 heuristics ($\aha$/{\em dynamic}/{\em local} and $\aha$/{\em
   static}/{\em global})  allowing each of them a maximal number of
 5,000 visitable nodes, we can solve 92$\%$ (69,056) of the hard
 instances. 

We tried to solve the 2,640 hard instances of $H(n,d,4.0)$ which are
not solvable using orthogonal combination of heuristics with at most
10,000 visited nodes by using a maximal number of 100,000 visited
nodes. 471 of these instances are still not solvable, more than 75$\%$ of the
solved instances are inconsistent. The fastest
response for the solved instances is charted in
Figure~\ref{F:hardest-distribution}(b). The most successful heuristics 
in giving the fastest response are $\aha$/{\em dynamic}/{\em local}
(42.5$\%$) and $\aha$/{\em static}/{\em global} (26.6$\%$). The three
heuristics using {\em static}/{\em global} computation of
constrainedness combined with using $\Qmax, \Cmax,$ and $\widehat{\cal 
  B}$ as a split set gave the fastest response for 15.9$\%$ of the
solved instances where the $\widehat{\cal B}$ strategy was by far the
best among the three (9.4$\%$). 

\section[Combining Heuristics for Solving Large Instances]{Combining
  Heuristics for Solving Large Instances
\label{S:emp:large}
\markright{\ref{S:emp:large}. SOLVING LARGE INSTANCES OF RCC-8}}
\markright{\ref{S:emp:large}. SOLVING LARGE INSTANCES OF RCC-8}
In the previous section we found that combining different heuristics
orthogonally can solve more instances using the same amount of visited 
nodes than any heuristic alone can solve. 
In this section we use these results in order to identify the
size of randomly generated instances up to which almost all of them,
especially those in the phase-transition region, 
can still be solved in acceptable time. 
Since many instances of $H(n,d,4.0)$ are already too difficult for a
size of $n=80$ (see Figure~\ref{F:hardest-distribution}), we restrict
our analysis to the instances of $A(n,d,4.0)$ and study randomly
generated instances with a size of more than $n=100$ nodes. 

For instances of a large size allowing a maximal number of 10,000
visited nodes in the 
search space is too much for obtaining an acceptable runtime. 10,000
visited nodes for instances of size $n = 100$ corresponds to a runtime of
more than 10 seconds on a Sun Ultra1, for larger instances it gets
much slower. Therefore, we have to restrict the maximal number of
visited nodes in order to achieve an acceptable runtime. 
Given a multi-processor machine, the different heuristics can be run
orthogonally on different processors using the maximal number of 
visited nodes each. If the orthogonal combination of the different
heuristics is simulated on a single-processor machine,  the maximal
number of nodes has to be divided by the number of used heuristics to
obtain the available number of visitable nodes for each 
heuristic. 
Thus, the more different heuristics we use, the less visitable nodes 
are available for each heuristic. Therefore, in order to achieve the
best performance, we have to find the combination of heuristics that
solves most instances within a given number of visitable nodes. 
The chosen heuristics should not only solve many instances alone, they
should also complement each other well, i.e., instances which cannot be
solved by one heuristic should be solvable by the other heuristic. 

We started by finding the optimal combination of heuristics for the
set of 788  hard instances of $A(n,d,4.0)$. From our empirical
evaluation given in Section~\ref{S:emp:evaluation} we know how many
visited nodes each  
heuristic needs in order to solve each of the 788 hard instances. 
Therefore, we computed the number of solved instances for
all $2^{20}$ possible combinations of the heuristics using an 
increasing maximal number of visitable nodes for all heuristics
together. Since we only tried to find the combination which solves the 
most instances, this can be computed quite fast. 
The results are given in Table~\ref{T:emp:best-performance}. 
\begin{table}[t]
  \begin{center}
    \leavevmode
    \begin{tabular}{|c|c|l|}
\hline
Max Nodes & Solved Instances & Combination of Heuristics \\
\hline
100 & 516 & \aha-d-l \\
200 & 705 & \aha-s-g \\
300 & 759 &  \aha-s-g, \aha-d-l \\
400 & 769 & \aha-s-g, \Cmax-d-l \\
500 & 774 & \aha-s-g, \aha-d-l, \Cmax-d-l \\
600 & 778 & \aha-s-g, \aha-d-l, \Cmax-d-l, $\widehat{\cal
  B}$-s-l \\
700 & 780 & \aha-s-g, \aha-d-l, \Cmax-d-l, $\widehat{\cal
  B}$-s-l \\
800 & 783 & \aha-s-g, \aha-d-l, \Cmax-d-l, $\widehat{\cal
  B}$-s-l \\
900 & 784 & \aha-s-g, \aha-d-l, \Cmax-d-l, $\widehat{\cal
  B}$-s-l \\
1100 & 785 & \aha-s-g, \aha-d-l, \Cmax-d-l, $\widehat{\cal
  B}$-s-l, $\widehat{\cal B}$-s-g \\
1300 & 786 & \aha-s-g, \aha-d-l, $\widehat{\cal B}$-s-l,
$\widehat{\cal B}$-s-g \\
3900 & 787 & \aha-s-g, \aha-d-l, $\widehat{\cal B}$-d-l \\
\hline
    \end{tabular}
  \end{center}
\caption[Best performance of combining different heuristics with a
  fixed maximal number of visited nodes]{Best performance of combining
    different heuristics for 
  solving the 787 solvable hard instances of $A(n,d,4.0)$ with a
  fixed maximal number of visited nodes \label{T:emp:best-performance}}
\end{table}
They show that a good performance can be obtained with a maximal number 
of 600 visited nodes. In this case four heuristics were involved,
i.e., 150 visitable nodes are spent on each of the four heuristics. 
Since the same combination of heuristics (\aha/{\em static}/{\em global}, \aha/{\em dynamic}/{\em local},
\Cmax/{\em dynamic}/{\em local}, $\widehat{\cal B}$/{\em static}/{\em local}) is also the best for up to 1,000
 visitable nodes, we choose this combination for our further
analysis. We choose the order in which they are processed to be
1.~\aha/{\em dynamic}/{\em local}, 2.~\aha/{\em static}/{\em global}, 3.~\Cmax/{\em dynamic}/{\em local}, 4.~$\widehat{\cal B}$/{\em static}/{\em local}
according to their first response behavior given in
Table~\ref{T:compare-heurisics}. 
Note that although the two heuristics \Cmax/{\em dynamic}/{\em local} and $\widehat{\cal
  B}$/{\em static}/{\em local} do not show a particularly good performance when running
them alone (see Table~\ref{T:compare-heurisics}), they seem
to best complement the other two heuristics. 

What we have to find next is the maximal number of visitable nodes
we spend for the heuristics. For this we ran the best performing
heuristic (\aha/{\em dynamic}/{\em local}) on instances of the
phase-transition region of varying sizes. It turned out that for
almost all consistent instances the number of visited nodes required
for solving them was slightly less than twice the size of the
instances while most inconsistent instances are also not
path-consistent and, thus, solvable with only one visited node. 
Therefore, we ran the four heuristics in the following
allowing $2n$ visited nodes each, where $n$ is the size of the instance,
i.e., together we allow at most $8n$ visitable nodes. 
We randomly generated test instances according to the $A(n,d,4.0)$ model
for a size of $n = 110$ regions up to a size of $n=500$ regions with a step of 
10 regions and 100 instances for each size and each average degree
ranging from $d=2.0$ to $d=18.0$ with a step of 0.5, a total number of 
132,000 instances. 
Since solving large instances using backtracking requires a lot of
memory, we solved the instances on a Sun Ultra60 with 1GB of main
memory. 

The generated instances display a phase-transition behavior which
continues the one given in Figure~\ref{fig:emp:phase-transition-all}. 
The phase-transition ranges from $d=10.0$ for $n=110$ to
$d=10.5$ for $n=500$ (see Figure~\ref{fig:emp:phase-transition-all-large}). 
\begin{figure}[t]
\begin{center}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{phase-trans_all-large.eps}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{visited_nodes.eps}
    \caption[Probability of satisfiability for
      $A(n,d,4.0)$ and average number of visited nodes]{Probability of satisfiability for $A(n,d,4.0)$ %
      (100 instances per data point) and average number of visited 
      nodes of the path-consistent instances when using orthogonal
      combination of the four selected heuristics} 
    \label{fig:emp:phase-transition-all-large}
\end{center}
\end{figure}
Apart from 112 instances, all other instances we generated were
solvable by orthogonal combination of the four heuristics (\aha/{\em static}/{\em global}, \aha/{\em dynamic}/{\em local},
\Cmax/{\em dynamic}/{\em local}, $\widehat{\cal B}$/{\em static}/{\em
  local}) spending less than 2n visited nodes each. 
In Figure~\ref{fig:emp:phase-transition-all-large} we give the average 
number of visited nodes of the path-consistent instances. 
It can be seen that for our test instances the average number of
visited nodes is linear in the size of the instances. 
The percentile 70$\%$ CPU time for instances of the phase-transition
with a size of $n=500$ regions is about 20 seconds, the percentile 99$\%$ CPU 
time is about 90 seconds. Up to a size of $n=400$ regions, the  percentile 99$\%$ CPU 
time is less than a minute (see Figure~\ref{fig:emp:cpu-all-large}). 
\begin{figure}[t]
\begin{center}
    \epsfxsize=60mm
    \leavevmode
    \epsfbox{cpu-all-large-70.eps}
  \epsfxsize=60mm
    \leavevmode
    \epsfbox{cpu-all-large-99.eps}
    \caption[Percentile 70$\%$ and 99$\%$ CPU time for solving
      large instances of $A(n,d,4.0)$.]{Percentile 70$\%$ and 99$\%$
        CPU time of the 
      orthogonal combination of four different heuristics for solving
      large randomly generated instances of $A(n,d,4.0)$} 
    \label{fig:emp:cpu-all-large}
\end{center}
\end{figure}

131,240 of our test instances were already solved by the  \aha/{\em
  static}/{\em global} heuristic, for 71 instances the \aha/{\em dynamic}/{\em
  local} heuristic was required and for 577 instances the \Cmax/{\em
  dynamic}/{\em local} heuristic produced the solution. None of the 112 instances which were 
not solved by one of those three heuristics were solved by the
$\widehat{\cal B}$/{\em static}/{\em local} heuristic. 
We tried to solve these instances using the other heuristics, again
using a maximal number of $2n$ visited nodes each. 
The best performing among those heuristics was the \Cmax/{\em dynamic}/{\em global}
heuristic which solved 87 of the 112 instances followed by the \Cmax/{\em
  static}/{\em global} heuristic (83) and the \Qmax/{\em dynamic}/{\em
  global} heuristic (63). 
 7 instances were not solved by any heuristic within a 
maximal number of $2n$ visited nodes. 

\section{Discussion}
\label{S:emp:discussion}
We empirically studied the behavior of solving
randomly generated $\RSAT$ instances using different backtracking heuristics some of which make use of the maximal tractable subsets
identified in previous work. 
%
We generated instances according to two different models of which the
``general model'' $A$ 
allows all 256 $\rca$ relations to be used while the ``hard model'' $H$ allows only
relations which are not contained in any of the maximal tractable
subsets.   
A theoretical analysis of the two models showed that the model $H$ and the model $A$ for a small average degree of the nodes in the constraint graph do
not suffer from trivial local inconsistencies
%
as it is the case for similar generation procedures for CSPs with finite domains \cite{achlioptas:et:al:cp-97}.
It turned out that randomly generated instances of both models show a
phase-transition behavior which depends most strongly on the average degree of the
instances. While most instances outside the phase-transition region can be
solved efficiently by each of our heuristics, instances in the
phase-transition region can be extremely hard. For the instances of
the general model, most path-consistent instances are also
consistent. Conversely, path-consistency is a bad approximation
to consistency for instances of the hard model. These instances are
also much 
harder to solve than instances of the general model.     

When comparing the different heuristics, we found that the heuristics
using one of the maximal tractable subsets as a split set are not as
much faster in deciding consistency of $\RSAT$ instances as their
theoretical advantage given by the reduced average branching factor
and the resulting exponentially smaller size of the search space
indicates. This is because using path-consistency as a forward
checking method considerably reduces the search space in all cases.  
Nevertheless, using one of the maximal tractable subsets as a
split set, in particular $\aha$, still leads to a much faster solution and solves more instances in
reasonable time than the other heuristics. 
Although the two maximal tractable subsets $\Qmax$ and $\Cmax$ contain more relations than $\aha$, their average branching factor is lower, i.e., when using $\aha$ one has to decompose more relations ($256-148=108$) than when using the other two sets ($96$ and $98$ relations, respectively), but $\aha$ splits the relations better than the other two sets. Most relations can be decomposed into only two $\aha$ sub-relations, while many relations must be decomposed into three $\Cmax$ sub-relations or into three $\Qmax$ sub-relations. This explains the superior performance of heuristics involving $\aha$ for decomposition.   

Among the instances we generated, we stored those
which could not be solved by all heuristics within a maximum number of 10,000
visited nodes in the search space in order to find out how the
different heuristics perform on these hard instances. We found that
almost all hard instances are located in the phase-transition region
and that there are many more hard instances in the hard model than in
the general model.  
We orthogonally combined all heuristics and ran them on all hard instances.  
This turned out to be very successful. Apart from one instance, all
hard instances of the general model could be solved, most of them
with a very low number of visited nodes. The hard instances of the hard
model were much more difficult: many of them could not be solved by
 any of the heuristics. Nevertheless, many more instances 
were solved by orthogonally combining the heuristics than 
by each heuristic alone. Again, most of them were solved using a low
number of visited nodes. 

Based on our observations on orthogonally combining different heuristics, we tried to identify the combination of heuristics which is most successful in efficiently solving many instances and used this combination for solving very large instances. 
It turned out that the best combination involves only heuristics which use maximal tractable subsets for decomposition. With this combination we were able to solve almost all randomly generated instances of the phase-transition region of the general model up to a size of $n = 500$ regions very efficiently. 
This seems to be impossible when considering the enormous size of the search space, which is on average $10^{39323}$ for instances of size $n=500$ when using $\aha$ as a split set. 

Our results show that despite its \NP-hardness, we were able to solve almost all randomly generated $\RSAT$ instances of the general model efficiently.  
%
This is neither due to the low number of different $\rca$ relations (instances generated according to the hard model are very hard in the phase-transition region) nor to our generation procedure for random instances which does not lead to trivially flawed instances asymptotically. 
It is mainly due to the maximal tractable subsets which cover a large fraction of $\rca$ and which lead to extremely low branching factors. 
Since there are different maximal tractable subsets, they allow choosing between many different backtracking heuristics which further increases efficiency: some instances can be solved easily by one heuristic, other instances by other heuristics. 
Heuristics involving maximal tractable subclasses  showed the best behavior but some instances can be solved faster when other tractable subsets are used.  
The full classification of tractable subsets gives the
possibility of generating hard instances with a high probability. 
Many randomly generated instances of the phase-transition region are
very hard when using only relations which are not contained in any of the
tractable subsets and consist of more than $n=60$ regions. 
The next step in developing efficient reasoning methods for $\rca$ is to find methods which are also successful in solving most of the hard instances of the hard model.  

The results of our empirical evaluation of reasoning with $\rca$
suggest that analyzing the computational properties of a reasoning
problem and identifying tractable subclasses of the problem is an
excellent way for achieving efficient reasoning mechanisms. 
In particular maximal tractable subclasses can be used to develop more
efficient methods for solving the full problem since their average branching factor is the lowest. Using the refinement method developed in Renz's \citeyear{renz:ijcai-99} paper, tractable subclasses of a set of relations forming a relation algebra can be identified almost automatically. This method makes it very easy to develop efficient algorithms. 
A further indication of our empirical evaluation is that it can be
much more effective (even and especially for hard instances of the
phase-transition region) to orthogonally combine different heuristics
than to try to get the final epsilon out of a single heuristic. 
This answers a question raised by Nebel \citeyear{nebel:constraints-97} of
 whether the orthogonal combination of heuristics is also useful in the 
 phase-transition region. 
In our experiments this lead to much better results even when simulating the orthogonal combination of different heuristics on a single processor machine and spending altogether the same resources as for any one heuristic alone. 
In contrast to the method of time slicing between different heuristics, we started a new heuristic only if the previous heuristic failed after a certain number of visited nodes in the search space. The order in which we ran the heuristics depended on their performance and on how well they complemented each other, more successful heuristics were used first. This is similar to using algorithm portfolios as proposed by Huberman et al.~\citeyear{huberman:et:al:science-97}. 
Which heuristics perform better and which combination is the most successful one is a matter of empirical evaluation and depends on the particular problem. Heuristics depending on maximal tractable subclasses, however, should lead to the best performance. 

 For CSPs with finite domains there are many theoretical results about localizing the phase-transition behavior and about predicting where hard instances are located. 
In contrast to this, there are basically no such theoretical results for CSPs with infinite domains as used in spatial and temporal reasoning. As our initial theoretical analysis shows, theoretical results on CSPs with finite domains do not necessarily extend to CSPs with infinite domains. It would be very interesting to develop a more general theory for CSPs with infinite domains, possibly similar to Williams and Hogg's ``Deep Structure'' \cite{williams:hogg:aij-94} or Gent et al.'s ``Kappa'' theory \cite{gent:et:at:aaai-96}.  

\section*{Acknowledgments}
We would like to thank Ronny Fehling for his assistance in
developing the programs, Malte Helmert for proof reading the paper, and the three anonymous reviewers for their very helpful comments. \\
This research has been supported by DFG as part of the project {\sc
fast-qual-space}, which is part of the DFG special research effort on ``Spatial
  Cognition''. The first author has been partially supported by a Marie Curie Fellowship of the European Community programme ``Improving Human Potential'' under contract number HPMF-CT-2000-00667. A preliminary version of this paper appeared in the {\em Proceedings of the 13th European Conference on Artificial
  Intelligence} (Renz \& Nebel, 1998).  


%

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Achlioptas, Kirousis, Kranakis, Krizanc, Molloy, \BBA\
  Stamatiou}{Achlioptas et~al.}{1997}]{achlioptas:et:al:cp-97}
Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., \BBA\
  Stamatiou, Y. \BBOP1997\BBCP.
\newblock \BBOQ Random constraint satisfaction: a more accurate picture\BBCQ\
\newblock In {\Bem 3rd Conference on the Principles and Practice of Constraint
  Programming (CP'97)}, \lowercase{\BVOL}\ 1330 of {\Bem LNCS}, \BPGS\
  107--120. Springer-Verlag.

\bibitem[\protect\BCAY{Allen}{Allen}{1983}]{allen:cacm-83}
Allen, J.~F. \BBOP1983\BBCP.
\newblock \BBOQ Maintaining knowledge about temporal intervals\BBCQ\
\newblock {\Bem Communications of the ACM}, {\Bem 26\/}(11), 832--843.

\bibitem[\protect\BCAY{Bennett}{Bennett}{1994}]{bennett:kr-94}
Bennett, B. \BBOP1994\BBCP.
\newblock \BBOQ Spatial reasoning with propositional logic\BBCQ\
\newblock In Doyle, J., Sandewall, E., \BBA\ Torasso, P.\BEDS, {\Bem Principles
  of Knowledge Representation and Reasoning: Proceedings of the 4th
  International Conference}, \BPGS\ 51--62,\ Bonn, Germany. Morgan Kaufmann.

\bibitem[\protect\BCAY{Bennett}{Bennett}{1997}]{bennett:thesis}
Bennett, B. \BBOP1997\BBCP.
\newblock {\Bem Logical Representations for Automated Reasoning about Spatial
  Relationships}.
\newblock Ph.D.\ thesis, School of Computer Studies, The University of Leeds.

\bibitem[\protect\BCAY{Cheeseman, Kanefsky, \BBA\ Taylor}{Cheeseman
  et~al.}{1991}]{cheeseman:et:al:ijcai-91}
Cheeseman, P., Kanefsky, B., \BBA\ Taylor, W.~M. \BBOP1991\BBCP.
\newblock \BBOQ Where the {\em really} hard problems are\BBCQ\
\newblock In {\Bem Proceedings of the 12th International Joint Conference on
  Artificial Intelligence}, \BPGS\ 331--337,\ Sydney, Australia. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Gent, MacIntyre, Prosser, Smith, \BBA\ Walsh}{Gent
  et~al.}{2001}]{gent:et:al:constraints-01}
Gent, I., MacIntyre, E., Prosser, P., Smith, B., \BBA\ Walsh, T.
  \BBOP2001\BBCP.
\newblock \BBOQ Random constraint satisfaction: Flaws and structure\BBCQ\
\newblock {\Bem CONSTRAINTS}, {\Bem 6\/}(4), 345--372.

\bibitem[\protect\BCAY{Gent, MacIntyre, Prosser, \BBA\ Walsh}{Gent
  et~al.}{1996}]{gent:et:at:aaai-96}
Gent, I., MacIntyre, E., Prosser, P., \BBA\ Walsh, T. \BBOP1996\BBCP.
\newblock \BBOQ The constrainedness of search\BBCQ\
\newblock In {\Bem Proceedings of the 13th National Conference on AI
  (AAAI'96)}, \BPGS\ 246--252.

\bibitem[\protect\BCAY{Golumbic \BBA\ Shamir}{Golumbic \BBA\
  Shamir}{1993}]{golumbic:shamir:jacm-93}
Golumbic, M.~C.\BBACOMMA\  \BBA\ Shamir, R. \BBOP1993\BBCP.
\newblock \BBOQ Complexity and algorithms for reasoning about time: A
  graph-theoretic approach\BBCQ\
\newblock {\Bem Journal of the Association for Computing Machinery}, {\Bem
  40\/}(5), 1128--1133.

\bibitem[\protect\BCAY{Grigni, Papadias, \BBA\ Papadimitriou}{Grigni
  et~al.}{1995}]{grigni:et:al:ijcai-95}
Grigni, M., Papadias, D., \BBA\ Papadimitriou, C. \BBOP1995\BBCP.
\newblock \BBOQ Topological inference\BBCQ\
\newblock In {\Bem Proceedings of the 14th International Joint Conference on
  Artificial Intelligence}, \BPGS\ 901--906,\ Montreal, Canada.

\bibitem[\protect\BCAY{Haralick \BBA\ Elliot}{Haralick \BBA\
  Elliot}{1980}]{haralick:elliot:ai-80}
Haralick, R.~M.\BBACOMMA\  \BBA\ Elliot, G.~L. \BBOP1980\BBCP.
\newblock \BBOQ Increasing tree search efficiency for constraint satisfaction
  problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 14}, 263--313.

\bibitem[\protect\BCAY{Huberman, Lukose, \BBA\ Hogg}{Huberman
  et~al.}{1997}]{huberman:et:al:science-97}
Huberman, B., Lukose, R., \BBA\ Hogg, T. \BBOP1997\BBCP.
\newblock \BBOQ An economics approach to hard computational problems\BBCQ\
\newblock {\Bem Science}, {\Bem 275}, 51--54.

\bibitem[\protect\BCAY{Ladkin \BBA\ Reinefeld}{Ladkin \BBA\
  Reinefeld}{1992}]{ladkin:reinefeld:ai-92}
Ladkin, P.~B.\BBACOMMA\  \BBA\ Reinefeld, A. \BBOP1992\BBCP.
\newblock \BBOQ Effective solution of qualitative interval constraint
  problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 57\/}(1), 105--124.

\bibitem[\protect\BCAY{Ladkin \BBA\ Reinefeld}{Ladkin \BBA\
  Reinefeld}{1997}]{ladkin:reinefeld:amai-96}
Ladkin, P.~B.\BBACOMMA\  \BBA\ Reinefeld, A. \BBOP1997\BBCP.
\newblock \BBOQ Fast algebraic methods for interval constraint problems\BBCQ\
\newblock {\Bem Annals of Mathematics and Artificial Intelligence}, {\Bem
  19\/}(3,4).

\bibitem[\protect\BCAY{Mackworth}{Mackworth}{1977}]{mackworth:ai-77}
Mackworth, A.~K. \BBOP1977\BBCP.
\newblock \BBOQ Consistency in networks of relations\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 8}, 99--118.

\bibitem[\protect\BCAY{Mackworth \BBA\ Freuder}{Mackworth \BBA\
  Freuder}{1985}]{mackworth:freuder:ai-85}
Mackworth, A.~K.\BBACOMMA\  \BBA\ Freuder, E.~C. \BBOP1985\BBCP.
\newblock \BBOQ The complexity of some polynomial network consistency
  algorithms for constraint satisfaction problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 25}, 65--73.

\bibitem[\protect\BCAY{Montanari}{Montanari}{1974}]{montanari:is-74}
Montanari, U. \BBOP1974\BBCP.
\newblock \BBOQ Networks of constraints: fundamental properties and
  applications to picture processing\BBCQ\
\newblock {\Bem Information Science}, {\Bem 7}, 95--132.

\bibitem[\protect\BCAY{Nebel}{Nebel}{1995}]{nebel:ki-conf-95}
Nebel, B. \BBOP1995\BBCP.
\newblock \BBOQ Computational properties of qualitative spatial reasoning:
  {F}irst results\BBCQ\
\newblock In Wachsmuth, I., Rollinger, C.-R., \BBA\ Brauer, W.\BEDS, {\Bem
  KI-95: Advances in Artificial Intelligence}, \lowercase{\BVOL}\ 981 of {\Bem
  {L}ecture {N}otes in {A}rtificial {I}ntelligence}, \BPGS\ 233--244,\
  Bielefeld, Germany. Springer-Verlag.

\bibitem[\protect\BCAY{Nebel}{Nebel}{1997}]{nebel:constraints-97}
Nebel, B. \BBOP1997\BBCP.
\newblock \BBOQ Solving hard qualitative temporal reasoning problems:
  Evaluating the efficiency of using the {ORD-Horn} class\BBCQ\
\newblock {\Bem CONSTRAINTS}, {\Bem 3\/}(1), 175--190.

\bibitem[\protect\BCAY{Randell, Cohn, \BBA\ Cui}{Randell
  et~al.}{1992a}]{randell:et:al:cade-92}
Randell, D.~A., Cohn, A.~G., \BBA\ Cui, Z. \BBOP1992a\BBCP.
\newblock \BBOQ Computing transitivity tables: A challenge for automated
  theorem provers\BBCQ\
\newblock In {\Bem Proceedings of the 11th CADE}. Springer-Verlag.

\bibitem[\protect\BCAY{Randell, Cui, \BBA\ Cohn}{Randell
  et~al.}{1992b}]{randell:et:al:kr-92}
Randell, D.~A., Cui, Z., \BBA\ Cohn, A.~G. \BBOP1992b\BBCP.
\newblock \BBOQ A spatial logic based on regions and connection\BBCQ\
\newblock In Nebel, B., Swartout, W., \BBA\ Rich, C.\BEDS, {\Bem Principles of
  Knowledge Representation and Reasoning: Proceedings of the 3rd International
  Conference}, \BPGS\ 165--176,\ Cambridge, MA. Morgan Kaufmann.

\bibitem[\protect\BCAY{Renz}{Renz}{1999}]{renz:ijcai-99}
Renz, J. \BBOP1999\BBCP.
\newblock \BBOQ Maximal tractable fragments of the {R}egion {C}onnection
  {C}alculus: A complete analysis\BBCQ\
\newblock In {\Bem Proceedings of the 16th International Joint Conference on
  Artificial Intelligence}, \BPGS\ 448--454,\ Stockholm, Sweden.

\bibitem[\protect\BCAY{Renz}{Renz}{2000}]{renz:phd}
Renz, J. \BBOP2000\BBCP.
\newblock {\Bem Qualitative Spatial Reasoning with Topological Information}.
\newblock Ph.D.\ thesis, Institut f{\"u}r Informatik,
  Albert-Ludwigs-Universit{\"a}t Freiburg.

\bibitem[\protect\BCAY{Renz \BBA\ Nebel}{Renz \BBA\
  Nebel}{1998}]{renz:nebel:ecai-98}
Renz, J.\BBACOMMA\  \BBA\ Nebel, B. \BBOP1998\BBCP.
\newblock \BBOQ Efficient methods for qualitative spatial reasoning\BBCQ\
\newblock In {\Bem Proceedings of the 13th European Conference on Artificial
  Intelligence}, \BPGS\ 562--566,\ Amsterdam, The Netherlands. Wiley.

\bibitem[\protect\BCAY{Renz \BBA\ Nebel}{Renz \BBA\
  Nebel}{1999}]{renz:nebel:aij99}
Renz, J.\BBACOMMA\  \BBA\ Nebel, B. \BBOP1999\BBCP.
\newblock \BBOQ On the complexity of qualitative spatial reasoning: A maximal
  tractable fragment of the {R}egion {C}onnection {C}alculus\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 108\/}(1-2), 69--123.

\bibitem[\protect\BCAY{Selman, Levesque, \BBA\ Mitchell}{Selman
  et~al.}{1992}]{selman:et:al:aaai-92}
Selman, B., Levesque, H.~J., \BBA\ Mitchell, D. \BBOP1992\BBCP.
\newblock \BBOQ A new method for solving hard satisfiability problems\BBCQ\
\newblock In {\Bem Proceedings of the 10th National Conference of the American
  Association for Artificial Intelligence}, \BPGS\ 440--446,\ San Jose, CA. MIT
  Press.

\bibitem[\protect\BCAY{van Beek \BBA\ Manchak}{van Beek \BBA\
  Manchak}{1996}]{beek:manchak:jair-96}
van Beek, P.\BBACOMMA\  \BBA\ Manchak, D.~W. \BBOP1996\BBCP.
\newblock \BBOQ The design and experimental analysis of algorithms for temporal
  reasoning\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 4}, 1--18.

\bibitem[\protect\BCAY{Williams \BBA\ Hogg}{Williams \BBA\
  Hogg}{1994}]{williams:hogg:aij-94}
Williams, C.~P.\BBACOMMA\  \BBA\ Hogg, T. \BBOP1994\BBCP.
\newblock \BBOQ Exploiting the deep structure of constraint problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 70}, 73--117.

\end{thebibliography}


\end{document}
