On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus

1 Introduction

When describing a spatial configuration or when reason­ ing about such a configuration, often it is not possible or desirable to obtain precise, quantitative data. In these cases, qualitative reasoning about spatial configurations may be used.

One particular approach in this context has been de­ veloped by Randell, Cui, and Cohn [1992], the so-called Region Connection Calculus (RCC), which is based on binary topological relations. One variant of this calcu­ lus, RCC-8, uses eight mutually exhaustive and pairwise disjoint relations, called base relations, to describe the topological relationship between two regions (see also Egenhofer [1991]).

Some of the computational properties of this calculus have been analyzed by Grigni et al. [1995] and Nebel [1995]. However, no attempt has yet been made to de­ termine the boundary between polynomial and NP-hard fragments of RCC-8, as it has been done for Allen's [1983]

*This research was partially supported by DFG as part of the project FAST-QUAL-SPACE, which is part of the DFG special research effort on "Spatial Cognition".

interval calculus [Nebel and Biirckert, 1995]. We address this problem and identify a maximal fragment of RCC-8 that is still tractable and contains all bas-e relations .

As in the case of qualitative temporal reasoning, this proof relies on a computer generated case-analysis that cannot be reproduced in a research paper. 1 Further, we show that for this fragment path-consistency is sufficient for deciding consistency. 2

2 Qualitative Spatial Reasoning with RCC

RCC is a topological approach to qualitative spatial rep­ resentation and reasoning where spatial regions are sub­ sets of topological space [Randell et al., 1992]. Relation­ ships between spatial regions are defined in terms of the relation C(a, b) which is true iff the closure of region a is connected to the closure of region b, i.e. if they share a common point . Regions themselves do not have to be internally connected, i.e. a region may consist of differ­ ent disconnected parts. The domain of spatial variables (denoted as X, Y, Z) is the whole topological space.

In this work we will focus on RCC-8, but most of our results can easily be applied to RCC-5, a subset of RCC-8 [Bennett, 1994]. RCC-8 uses a set of eight pairwise dis­ joint and mutually exhaustive relations, called base rela­ tions, denoted as DC, EC, PO, EQ, TPP, NTPP, TPP- 1 , and NTPP- 1 , with the meaning of DisConnected, Ex­ ternally Connected, Partial Overlap, EQual, Tangential Proper Part, Non- Tangential Proper Part, and their con­ verses. Examples for these relations are shown in Fig­ ure 1. In RCC-5 the boundary of a region is not taken into account, i.e. one does not distinguish between DC and EC and between TPP and NTPP. These relations are combined to the RCC-5 base relations DR for DiscRete and PP for Proper Part, respectively.

Sometimes it is not known which of the eight base relations holds between two regions, but it is possible to restrict to some of them. In order to represent this, unions of base relations can be used. Since base relations are pairwise disjoint, this results in 2 8 different relations, including the union of all base relations, which is called universal relation. In the following we will write sets of base relations to denote these unions. Using this nota­ tion, DR, e.g., is identical to {DC, EC} . Spatial formulas are written as X RY, where R is a spatial relation. Apart from union (U) , other operations are defined, namely, converse (~) , intersection (n), and composition ( o) of relations. The formal definitions of these operations are:

1 The programs can be obtained from the authors.

2 Full proofs can be found in our technical report [Renz and Nebel, 1997] .

The compositions of the eight base relations are shown in Table 1. Every entry in the composition table specifies the relation obtained by composing the base relation of the corresponding row with the base relation of the cor­ responding column. Composition of two arbitrary RCC-8 relations can be obtained by computing the union of the composition of the base relations.

A spatial configuration can be described by a set e of spatial formulas . One important computational prob­ lem is deciding consistency of e, i.e. deciding whether it is possible to assign regions to the spatial variables in a way that all relations hold. We call this problem RSAT. When only relations of a specific set S are used in e, the corresponding reasoning problem is denoted RSAT(S) . In the following S denotes the closure of S under composition, intersection, and converse.

3 Encoding of RCC-8 in Modal Logic

In this work we use Bennett's [1995] encoding of RCC-8 in propositional modal logic. 3 Bennett obtained this en­ coding by analyzing the relationship of regions to the universe U. He restricted his analysis to closed regions that are connected if they share a point and overlap if they share an interior point. If, e.g, X and Y are discon­ nected, the complement of the intersection of X and Y is equal to the universe. Further, both regions must not be empty, i.e. the complements of both X and Y are not equal to the universe. In this way the eight base relations can be represented by constraints of the form ( m = U), called model constraints, and ( m =I U), called entail­ ment constraints, where m is a set-theoretic expression containing perhaps the topological interior operator i. Any model constraint must hold, whereas no entailment constraint must hold [Bennett, 1994].

3 We assume in the remainder that the reader is familiar with modal logic as presented, e.g., by Fitting [1993] .

The model and entailment constraints can be encoded in modal logic, where spatial variables correspond to propositional atoms and the interior operator i to a modal operator I (see Table 2). The axioms for i must also hold for the modal operator I, which results in the following axioms [Bennett, 1995]:

Axioms 1 and 2 correspond to the modal logics T and 4, axioms 3 and 4 already hold for any modal logic K, so I is a modal 54-operator.

The four axioms specified by Bennett are not suffi­ cient to exclude non-closed regions. In order to account for that, we add two formulas for each atom, which cor­ respond to topological properties of closed regions. A closed region is the closure of an open region and the complement of a closed region is an open region:

In order to combine the different model and entailment constraints, Bennett [1995] uses another modal operator D. Om is interpreted as m = U and -,Om as m =P U. Any model constraint m can be written as Om and any entailment constraint as -,Om. If OX is true in a world w of a model M, written as (M, w If- OX), then X must be true in any world of M. So 0 is an 55-operator with the constraint that all worlds are mutually accessible. Therefore Bennett [1995] calls it a strong 55-operator. So the encoding of RCC-8 is done in multi-modal logic with an 54-operator and a strong 55-operator.

Let e be a set of RCC-8 formulas and Reg(8) be the set of spatial variables used in e, then m(8) specifies the modal encoding of e, where

m1 (X RY) is a disjunction of the conjunctively con­ nected model and entailment constraints for the base relations in R. m2 results from the axioms of the !­ operator and the additional properties of closed regions:

D(IIX-+ IX), D(J-,X-+ ·X) and 0(-,J-,IX-+ X) are entailed by the other formulas and can be ignored. As follows from the work by Bennett [1995], 8 is consistent iff m(8) is satisfiable.

In order to refer to the single model and entailment constraints, we will introduce some abbreviations.

Definition 3.1 Abbreviations for the model constraints:

As the entailment constraints are negations of the model constraints, they will be abbreviated as negations of the above abbreviations. When it is obvious which atoms are used, the abbreviations will be written without in­ dices. The abbreviations can be regarded as "proposi­ tional atoms". Then it is possible to write the modal encoding m1 (X RY) of every relation R of RCC-8 as a "propositional formula" of abbreviations. We will call this formula the abbreviated form of R. In the remain­ der we will use the encoding of m1 (X RY) such that the abbreviated form is in conjunctive normal form (CNF).

4 Computational Properties of RCC-8

In this section we prove that reasoning with RCC-8 as well as RCC-5 is NP-hard. A similar but weaker result has been proven by Grigni et al. [1995] (see Section 8) .

In this paper NP-hardness proofs for different sets S of RCC-8 relations will be carried out. All of them use a reduction of a propositional satisfiability problem to R5AT(S) by constructing a set of spatial formulas e for every instance I of the propositional problem, such that 8 is consistent iff I is a positive instance. These satisfi­ ability problems include 35AT, NOT-ALL-EQUAL-3SAT where every clause has at least one true and one false literal, and ONE-IN-THREE-35AT where exactly one lit­ eral in every clause must be true [Garey and Johnson, 1979].

The reductions have in common that every literal as well as every literal occurrence L is reduced to two spa­ tial variables XL and Y L and a relation R = Rt U Rj, where Rt n R1 = 0 and X LRY L· L is true iff X LRtY L holds and false iff X LRJ Y L holds. Additional "polar­ ity" constraints have to be introduced to assure that for the spatial variables X ~L and Y ~L, corresponding to the negation of L, X ~LRt Y ~L holds iff X LRJ Y L holds, and vice versa. Using these polarity constraints, spatial vari­ ables of negative literal occurrences are connected to the spatial variables of the corresponding positive literal, and likewise for positive literal occurrences and negative lit­ erals. Further, "clause" constraints have to be added to assure that the clause requirements of the specific propo­ sitional problem are satisfied in the reduction.

Proof Sketch. Transformation of NOT-ALL-EQUAL35AT to R5AT(RCC-5) (see also Grigni et al. [1995]). Rt = {PP} and R1 = {PP- 1 }. Polarity constraints:

Clause constraints for every clause c = { i, j, k}:

Since RCC-5 is a subset of RCC-8, this result can be easily applied to RCC-8.

Corollary 4.2 RSAT(RCC-8) is NP-hard.

In order to identify the borderline between tractabil­ ity and intractability, one has to examine all subsets of RCC-8. We limit ourselves to subsets containing all base relations, because these subsets still allow to express defi­ nite knowledge, if it is available. Additionally, we require the universal relation to be in the subset, so that it is possible to express complete ignorance. This reduces the search space from 2 256 subsets to 2 247 subsets. We proved a property that has likewise been used in iden­ tifying the maximal tractable subset of Allen's calculus [Nebel and Biirckert, 1995] that can be used to further reduce the search space.

Theorem 4.3 RSAT(S) can be polynomially reduced to RSAT(S)

Corollary 4.4 LetS be a subset of RCC-8.

1. RSAT(S) E P iff RSAT(S) E P.
2. RSAT(S) is NP-hard iff RSAT(S) is NP-hard.

The first statement of Corollary 4.4 can be used to increase the number of elements of tractable subsets of RCC-8 considerably. With the second statement of Corollary 4.4, NP-hardness proofs of RSAT can be used to exclude certain relations from being in any tractable subset of RCC-8. The NP-hardness proof of Theorem 4.1, e.g., only uses the relations {PO} and {PP,PP- 1 }. So for any subset S with the two relations contained in S, RSAT(S) is NP-hard. The following NP-hardness results can be used to exclude more relations.

Lemma 4.5 Let S be a subset of RCC-8 con­ taining all base relations. If any of the rela­ tions {TPP, NTPP, TPP- 1 , NTPP- 1 }, {TPP, TPP- 1 ~, {NTPP, NTPP- 1 }, {NTPP, TPP- 1 } or {TPP, NTPP- } is contained inS, then RSAT(S) is NP-hard.

Proof Sketch. When R1 U Rt is replaced by {TPP, NTPP, TPP- 1 , NTPP- 1 }, {TPP, TPP- 1 } or {NTPP, NTPP- 1 }, the transformation of Theorem 4.1 can be applied. For {NTPP, TPP- 1 } and {TPP, NTPP- 1 } ONE-IN-THREE-3SAT has to be used. ·

By computing the closure of all sets containing the eight base relations together with one additional relation, the following lemma can be obtained.

Lemma 4.6 RSAT(S) is NP-hard for any subset S of RCC-8 containing all base relations together with one of the 72 relations of the following sets:

5 · Transformation of RSAT to SAT

For transforming RSAT to propositional satisfiability (SAT) we will transform every instance e of RSAT to a propositional formula in CNF that is satisfiable iff e is consistent. We will start from m(e), the modal encoding of e, and show that whenever m(e) is satisfiable it has a Kripke model of a specific type. This model will then be used to transform m(e) to a propositional formula.

m(e) is satisfiable if it is true in a world w of a Kripke model M = (W,{R1 = W x W,R2 ~ W x W},rr), where W is a set of worlds, R1 the accessibility rela­ tion of the 0-operator, R2 the accessibility relation of the !-operator, and 7r a truth function that assigns a truth value to every atom in every world. The truth conditions for M, w If- m(0) can be specified as a com­ bination of truth conditions of the single atoms according to the form of m(e). In this way M, w If- I<p, e.g., can be written as (Vu : wR2u.M, u If- <p) and M, w If- ·l<p as (3u : wR2u.M, u If- ·<p). We will call this form of writing M If- m(e) the explicit form of m(e).

Before transforming m(0) to a propositional formula, we have to show that there is a Kripke model of m(0) that is polynomial in the number of spatial variables n.

Definition 5.1 Let u E W be a world of the model M .

• u is a world of level 0 if vR2u only holds for v = u.
• u is a world of level l + 1 if vR2u holds for a world v of level l and there is no world v f; u of level > l.

We assume that every occurrence of a sub-formula of m(0) of the form ·O<p, where <p contains no 0 opera­ tors, introduces a new world of level 0. As these sub­ formulas correspond to entailment constraints, the num­ ber of worlds of level 0 is polynomial in n.

For every spatial variable X and every world w there might be sub-formulas that force the existence of a world u with wR2u where X is true or where ·X is true. Be­ cause there are n different spatial variables, 2n different worlds u with wR2u are sufficient for each world w.

Definition 5.2 An RCC-8-frame F = (W, {R1 , R2 }) has the following properties:

1. W contains only worlds of level 0,1 and 2.
2. For every world w of level k (k = 0, 1) there are exactly 2n worlds u of level k + 1 with wR2u.
3. For every world w of level k there is exactly one world u for every level 0 ~ l ~ k with uR2w.

An RCC-8-model is based on an RCC-8-frame.

Lemma 5.3 m(e) is satisfiable iff M, w If- m(e) for an RCC-8-model M with polynomially many worlds.

Now it is possible to transform the explicit form of m(e) to a propositional formula p(m(0)) in CNF such that p(m(0)) is satisfiable iff m(e) is satisfiable in a polynomial RCC-8-model M. For this purpose, propo­ sitional atoms X w are introduced which stand for the truth of atom X in world w of the RCC-8-model M. Fur­ ther, universally quantified truth conditions are trans­ formed into conjunctions and existentially quantified truth conditions are transformed into truth conditions on particular worlds, which can be determined using the structure of the RCC-8-frame and the modal formula.

Theorem 5.4 RSAT(RCC-8) can be polynomially re­ duced to SAT.

With Corollary 4.2 this leads to the following theorem. Theorem 5.5 RSAT(RCC-8) is NP-complete.

6 Tractable Subsets of RCC-8

In order to identify a tractable subset of RCC-8, we an­ alyze which relations can be expressed as propositional Horn formulas, as satisfiability of Horn formulas (HORN­ SAT) is tractable.

Proposition 6.1 Applying the transformation p to the model and entailment constraints, to the axioms for I, and to the properties of closed regions leads to Horn for­ mulas.

Since the model constraints a and A are transformed to indefinite Horn formulas, the transformation of any disjunction of these constraints with any other constraint is also Horn. All relations with an abbreviated form using only abbreviations or disjunctions of abbreviations transformable to Horn formulas can be transformed to Horn formulas. In this way 64 different relations can be transformed to Horn formulas. We call the subset of RCC-8 containing these relations 1l8 .

Theorem 6.2 RSAT(1l8 ) can be polynomially reduced to HORNSAT and therefore RSAT(128 ) E P.

Theorem 6.3 128 contains the following 148 relations:

with N1 and N2 as defined in Lemma 4. 6 and

For proving that 128 is a maximal tractable subset of RCC-8, we have to show that no relation of N3 can be added to 128 without making RSAT intractable.

Lemma 6.4 The closure of every set containing 12s and one relation of N3 contains the relation {EQ, NTPP}.

Therefore it is sufficient to prove NP-hardness of RSAT(128 U {EQ, NTPP}) for showing that 128 is a max­ imal tractable subset of RCC-8.

Lemma 6.5 RSAT(128 u {EQ, NTPP}) is NP-hard.

Proof Sketch. Thansformation of 3SAT to RSAT(12su {EQ, NTPP}). Rt = {NTPP} and Rt = {EQ}. Polarity constraints:

XL{EC, NTPP}X~L, Y L{TPP}Y ~L,

XL{TPP, NTPP}Y ~L, Y L{EC, TPP}X~L, Clause constraints for each clause c = { i, j, k}: Yi{NTPP- 1 }Xj, Yj{NTPP- 1 }Xk, Y k{NTPP- 1 }Xi. ·

Theorem 6.6 H8 is a maximal tractable subset of RCC-8.

It has to be noted that there might be other maximal tractable subsets of RCC-8 that contain all base relations.

As 128 is tractable, the intersection of RCC-5 and fls is also tractable. We will call this subset 125.

Theorem 6. 7 125 is the only maximal tractable subset of RCC-5 containing all base relations.

7 Applicability of Path-Consistency

As shown in the previous section, RSAT(12s) can be solved in polynomial time by first transforming a set of 128 formulas to a propositional Horn formula and then deciding it in time linear in the number of literals. This way of solving RSAT does not appear to be very efficient.

As RSAT is a Constraint Satisfaction Problem (CSP) [Mackworth, 1987), where variables are nodes and rela­ tions are arcs of the constraint graph, algorithms for de­ ciding consistency of a CSP can also be used. A correct but in general not complete O(n 3 ) algorithm for deciding inconsistency of a CSP is the path-consistency method [Mackworth, 1977] that makes a CSP path-consistent by successively removing relations from all edges using Vk: Rij +- Rii n (Rik o Rkj), where i,j,k are nodes and Rij is the relation between i and j. If the empty relation occurs while performing this operation, the CSP is not path-consistent, otherwise it is.

In this section we will prove that path-consistency de­ cides RSAT(128 ). This is done by showing that the path­ consistency method finds an inconsistency whenever pos­ itive unit resolution (PUR) resolves the empty clause from the corresponding propositional formula. As PUR is refutation-complete for Horn formulas, it follows that the path-consistency method decides RSAT(1ls) . The only way to get the empty clause is resolving a positive and a negative unit clause of the same variable. Since the Horn formulas that are used contain only a few types of different clauses, there are only a few ways to resolve unit clauses using PUR.

Definition 7.1

• RK denotes the set of relations of 1ls with the conjunct K appearing in their abbreviated form.
• RK1 ,K2 denotesRK1 URK2 ·
• Rr denotes R-y URo:v1 URAv1 URc URo:vc URAvC·
• An RK-chain Ri<(X,Y) is a path from region X to region Y, where all relations between successive regions are from RK.

Lemma 7.2 Let e be a set of 1ls -formulas.

• A positive unit clause {X w} can only be resolved from {Y w} and a clause resulting from X Rr Y E e. When such a resolution is possible, X Ro: ,AY cannot hold, so XR 1 ,cY must hold.

• A negative unit clause {-,X w} can only be resolved from {Y w} and a clause resulting from XRa. ,AY E 8.

Lemma 7. 3 If the positive unit clause {X w} can be re­ solved with PUR using an Rr-chain from X toY, the path-consistency method results in X R'Y ,c Y .

Using Lemma 7.3, it can be proven that the path­ consistency method decides RSAT(H8 ) . Using the proof of Theorem 4.3, it is possible to express every relation of H8 as a Horn formula. Then the following theorem can be proven.

Theorem 7.4 The path-consistency method decides RSAT(H8 ) .

Another interesting question is whether the path­ consistency method computes minimal possible relations on H8 . As the following example demonstrates, this is not the case even for the set H5 . A{PP}D is impossible although the constraint graph is path-consistent:

8 Related Work

Nebel [1995] showed that RSAT(B) can be decided in polynomial time, where B is the set of the RCC-8 base relations. Since B s;; 1£8 , our result is more general. Fur­ ther, B contains only 38 relations, whereas Hs contains 148 relations, i.e. about 58% of RCC-8.

Grigni et al. [1995] proved NP-hardness of problems similar to RSAT. For instance, they considered the prob­ lem of relational consistency, which means that there exists a path-consistent refinement of all relations to base relations, and showed that this problem is NP­ hard. While our NP-hardness result on RSAT implies their result, the converse implication follows only using the above cited result by Nebel [1995] .

In addition to this syntactic notion of consistency, Grigni et al. [1995] considered a semantic notion of con­ sistency, namely, the realizability of spatial variables as internally connected planar regions. This notion is much more constraining than our notion of consistency. It is also computationally much harder.

9 Summary

We analyzed the computational properties of the qualita­ tive spatial calculus RCC-8 and identified the boundary between polynomial and NP-hard fragments . Using a modification of Bennett's encoding of RCC-8 in a multi­ modal propositional logic, we transformed the RCC-8 consistency problem to a problem in propositional logic and isolated the relations that are representable as Horn clauses. As it turns out , the fragment identified in this way is also a maximal fragment that contains all base relations and is still computationally tractable. Further, we showed that for this fragment path-consistency is suf­ ficient for deciding consistency.

As in the case of qualitative temporal reasoning, our result allows to check whether the relations that are used in an application allow for a polynomial reasoning algo­ rithm. Further, if the application requires an expressive power beyond the polynomial fragment, it can be used to speed up backtracking algorithms. Assuming that the relations are uniformly distributed, the avera&_e branch­ ing factor is reduced from 4.0 to 1.4375 using 1{.8 instead of B to split the relations (see also [Nebel , 1997]).