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 RCC-8 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 RCC-8 suggest that analyzing the computational properties of a reasoning problem and identifying tractable subclasses of the problem is an excellent way for aieving efficient reasoning meanisms. 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 (1999) 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 (1997) 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 sear space.  The order in whi 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. (1997). 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" (Williams &
Hogg, 1994) or Gent et al.'s "Kappa" theory (Gent, MacIntyre, Prosser, & Walsh, 1996).