Qualitative Collaborative Planning in Geographic Space: Some Computational Issues

Dimitris Papadias and Max Egenhofer
National Center for Geographic Information and Analysis
Department of Spatial information Science and Engineering
University of Maine, ME 04469-5711

1. INTRODUCTION

Frequently people communicate spatial information usingqualitative relations (constraints) between distinct objects rather than absolute coordinates. The constraints that have been used in the GIS literature are topological (e.g., disjoint, overlap), direction(e.g., north, east) and distance constraints (e.g., near, far). The importance of qualitative spatial constraints has led to their application in several domains related to GIS and Spatial Databases (for an expended discussion see Papadias and Sellis, 94).

In this paper we study computational issuesinvolved in qualitative collaborative planning in geographic space. We assume a number of decision makers (thereafter called agents) each having a set of beliefs about a given spatial planning problem.These beliefs are expressed in the form of qualitative spatial constraints between a set of objects. The problem is to generate spatial plans that are consistent with the agents' constraints.

As an example consider the planning problem illustrated in Figure 1 (the example wasmotivated by Leitner, 95). The agents are given the map of an area with wetlands, national parks, mountainous areas, urban areas and railways, and they want to decide the best possible sites for a new airport. Each agent may have different backgrounds and consequently different priorities (e.g., environmental versus business interests and soon).

Figure 1. A Spatial Planning Problem

The general constraint (assumed by all the agents) is that the airport cannot be in a mountainous terrain, in awetland or in the park (constraint disjoint(airport, mountain) and disjoint(airport, park) and disjoint(airport, wetlands)). In addition, the first agent asserts that the airport should be somewhere east of the first lake and north of the major urban (direction constraints). The constraint imposed by the second agent is that the airport should not be very near or very far from the downtown of the major urban area (distance constraint: not_very_near(airport, major city) and not_very_far(airport, majorcity)). The third agent believes that the airport should be accessible using the train routes (topological constraint:intersects(railway, airport)). In Figure 1 we illustrate the constraints imposed by the three agents and a potential site that satisfies them.

We use the above example only for demonstration purposes since real applications can be much more complicated; they may involve a large number of agents with different backgrounds and numerous constraints. In general spatial planning problems can be very difficult and an optimal solution that satisfies all constraints may notexist. The first problem is to identify what the different agents imply by spatial terms and to model the various constraints in a unified framework (there is an obvious connection here with the problem of interoperability). After the constraints are expressed in a model there is the second problem, namely to devise tractable algorithms that efficiently check the satisfiability of the imposed constraints. The third problem is to perform the actual search in the (spatial) database using the set of consistent constraints of the second step. This problem involves spatial access methods that focus on the efficient processing of qualitative constraints. In the following sections we discuss these problems in more detail.

2. MODEL TRANSLATION

In order to demonstrate that different agents may have different models of space we will use the example of Figure 1. Figure 2a illustrates explicitly the direction constraints imposed by the first agent. In this Figure we assume a projection-based notion of directions, that is, direction relations are defined using parallel lines to some predefined coordinate axes. However, if the agent assumes cone-shaped directions (Frank, 92), the acceptance area imposed by the constrained is significantly different (Figure 2b). Especially in the case of direction relations, there are no widely accepted definitions and semantically different concepts are sometimes attached to the same linguistic terms. Furthermore, as it is shown in Figure 2, there is not even a universal model (e.g., projection or angular-based) according to which direction can be defined in geographic space.

Figure 2. Two different concepts of directions

Similar differences may occur in the case of topological relations. In Spatial Access Methods (e.g., window queries) the term overlap has been used to denote any configuration of objects that share somecommon point(s). This includes objects totally inside one another, objects that intersect at the boundaries but not at the interiors and so on. On the other hand, the intersection models (Egenhofer, 91), the main models used in the GIS literature, differentiate between these sub-cases resulting in a set of seven pairwise refinements of overlap as it is used in access methods terminology. One of these refinements is again called overlap. [1] Grigni et al., (95) used several sets of topological relations to reason in multiple levels of qualitative resolution. The same linguistic term has a different interpretation according to the resolution level; at the lowest level overlap has its access methods meaning, while at the highest resolution it assumes the 4-intersection semantics.

Obviously in the case of distance relations there can be significant differences in the notion that each agent has for near, far, etc. Such differences arise from subjective criteria, different metrics used (e.g., Euclidean vs. block worlds), and distortion caused by mental representations of space (for such examples see Hirtleand Jonides, 85). Only recently, work has focused on the formalization of the spatial relations that people evoke in everyday reasoning (Mark andEgenhofer, 94).

Therefore the first goal in a qualitative collaborative planning problem in space is to identify the differences between the semantics of each agent. Since a universally accepted model for all spatial relations does not exist at this point, agents should be provided with guidelines about the use of spatial relations. This could be achieved by Spatial Query Languages that permit only certain kinds of spatial constraints with well-defined semantics (Egenhofer, 94; Papadias and Sellis, 95). Although such languages may restrict expressive power, they could provide the foundation for a common set of constraints that facilitates satisfiability checking and query processing.

3. COLLABORATIVE CONSTRAINT SATISFACTION IN SPACE

After all qualitative constraints have been expressed in a single model, the problem of collaborative planing can be thought of as a constraint satisfaction problem with multiple goals: find one solution that satisfies all constraints, find all possible solutions, a number of possible solutions etc. If a solution that satisfies all constraints cannot be found, agents could be asked to reconsider their constraints and cancel the least important ones (obviously this canbe an iterative process until a solution is found). Alternatively they could assign weights proportional to the importance of each constraint. Weights can also be assigned to each agent externally (by the some administrator) to reflect his/her significance in decision making. If an optimal solution does not exist,then the solution which satisfies the constraints with the highest weights may be acceptable. A number of mechanisms can used to solve spatial constraint satisfaction problems such as traditional Artificial Intelligence techniques (e.g., backtracking, local consistency checking Macworth and Freuder, 85) or Neural Network Approaches (McClelland and Rumelhart, 87).

However, it is a difficult problem to develop a model that can express all types of spatial constraints and is capable of performing efficient satisfiability checking. Work on spatial constraint satisfaction problems has concentrated on homogeneous constraints, that is constraints of the same form (only topological or only direction relations). Even for such cases, a large class of problems is intractable (NP-Complete). Studies of consistency mechanisms for topological relations can be found in (Smith and Park, 92) and (Egenhofer and Sharma, 93).

Furthermore, different semantics used by different agents can complicate problem solving significantly and render a problem from tractable to NP-Complete. As an example consider a set of agents reasoning about a set of contiguous regions without holes. Each agent imposes a simple topological constraint for some pairs of objects (e.g., one of the eight topological relations of the 4-intersection model). The unified model that expresses all agents' constraints contains for each pair of objects either:

  1. a null constraint (if no constraint for this pair has been imposed by any agent)

  2. a single constraint (if only one agent has imposed a constraint for this pair, or if multiple agents have imposed the same constraint)

  3. a conjunction of different constraints imposed by different users (in which case we have an inconsistency).
Grigni et al., (95) have shown that the above problem is solvable by a polynomial path consistency algorithm. On the other hand, if some of the agents assume low resolution relations (e.g., they use the term overlap according to spatial access methods terminology) the same problem becomes exponential because the new meaning of overlap should be expressed by a disjunction of seven topological relations.

Although constraint satisfaction problems are in general NP-Complete, the specific structure of the Spatial Domain could facilitate the development of efficient heuristics for Spatial Planning problems, and lead to polynomial algorithms for certain sub-cases.

4. QUALITATIVE SPATIAL ACCESS METHODS

Assume that the constraint satisfaction problems have been solved, and a set of consistent constraints has been found. The remaining step is to identify the actual land parcels in the area of Figure 1 that could be used for the new airport site. This involves a search in the (spatial) database of the form "find all land parcels east of the first lake, and north of the major urban area, and ....".

However, most of the work on Spatial Access Methods has focused on window queries and does not support efficient processing of qualitative constraints. Only recently it has been shown how alternative indexing methods can be used to efficiently retrieve objects that satisfy certain topological, direction and distance relations (for samples of this work see Papadias et al., 1995; Theodoridis andPapadias, 95). This work provides the basis for database search in qualitative collaborative planning in space.

In our example, the output of the database search is a set of potential candidates out of which only a subset could be used for the new site. This is due to some unforeseen constraints that were not predicted by the agents because of data quality issues. For instance, the agents may have not been given all the information about the area, or they did not take it into account during the decision making process. Missing information possibly includes land parcels occupied by local industry, rivers and in general all areas inappropriate for airport sites.

One may argue that the decision making process could go directly to the database search phase without passing through satisfiability checking mechanisms. However, this is inappropriate. Spatial databases and GISs usually contain large volumes of data and search is very expensive because of large I/O load. The satisfiability mechanisms basically provides a fast filter step that recognises inconsistencies in the constraints themselves, without extensive access to the stored data. In addition, a query optimizer that generates efficient query plans consistent with the imposed constraints, can be incorporated as a part of the satisfiability mechanism.

In the extreme case where the database search fails and no potential sites are found, a new set of constraints should be used for the search. This is achieved by the satisfiability checking mechanism either by relaxing some (unimportant) constraints or by asking the agents to impose new ones.

5. CONCLUDING REMARKS

We believe that qualitative collaborative planning in geographic space is significant for a number of reasons, the most important of which is the fact that people usually communicate spatial knowledge by use of qualitative relations rather than absolute coordinates. In this paper we have outlined several concepts and problems that need to be dealt with, before qualitative collaborative planning becomes a reality:

Figure 3 illustrates the process of qualitative collaborative planning in space as described in this paper. In an ideal environment all the processes will be automated and the only human intervention will be the constraints imposed (and revised) by the agents. In the initial phases of such a project though, an administrator is necessary to organise the process and communicate potential inconsistencies to the individual agents.

Figure 3. Qualitative Collaborative Planning in Space

Qualitative collaborative planning in space is an interesting topic that involves several domains such as Query Languages, Constraint Satisfaction and Access Methods. Although solutions at this time are not straightforward, we believe that its significance and the range of potential applications poses a challenge for future work on this topic.

ACKNOWLEDGEMENTS

We would like to thank Nikos Karakapilidis, Jayant Sharma and Rashid Mohamed Shariff for providing useful comments on earlier drafts of this paper.

REFERENCES

Egenhofer, M. "Reasoning about Binary Topological Relations". In Gunther, O. and Schek, H.J. (eds.) Advances in Spatial Databases. Second Symposium, (SSD). Springer Verlag LNCS, 1991.

Egenhofer, M., Sharma, J. "Assessing the Consistency of Complete and Incomplete Topological Information". Geographical Systems, Vol. 1, pp.47-68, 1993.

Egenhofer, M."Spatial SQL: A Query and Presentation Language". IEEE Transactions on Knowledge and Data Engineering, Vol 6, no 1, pp.86-95, 1994.

Frank, A.U.,"Qualitative Spatial Reasoning about Distances and Directions in Geographic Space", Journal of Visual Languages andComputing, Vol. 3, pp. 343-371, 1992.

Grigni, M., Papadias, D., Papadimitriou, C. "Topological Inference". In the Proceedings of the International Joint Conference of Artificial Intelligence (IJCAI), Montreal, Canada, 1995.

Hirtle, S, Jonides, J. "Evidence of Hierarchies in Cognitive Maps". Memory and Cognition 13, pp. 208-217, 1985.

Mackworth, A, Freuder, E. "The Complexity of some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems". Artificial Intelligence, 25, pp. 65-74, 1985.

Mark, D, Egenhofer, M, "Calibrating the Meaning of Spatial Predicates from Natural Language: Line Region Relations". In the Proceedings of the 6th International Symposium on Spatial Data Handling (SDH), Edinburgh, U.K, 1994.

McClelland, J, Rumelhart, D. "Explorations in Parallel Distributed Processing". MIT Press (chap. 3), 1987.

Leitner, M. "The Impact of Data Quality Displays on Spatial Decision Support". Software Demonstration, Science Day, NCGIA Board of Directors' Meeting, SUNY, Buffalo, June 1995.

Papadias, D., Sellis, T. "Qualitative Representation of Spatial Knowledge in Two-Dimensional Space". Very Large Data Bases Journal, Special Issue on Spatial Databases, Vol. 3(4), pp. 479-516, 1994.

Papadias, D., Sellis, T. "A Pictorial Query-By-Example Language". Journal of Visual Languages and Computing, Special Issue on Visual Query Systems, Vol. 6(1), 53 -72, 1995.

Papadias, D., Theodoridis, Y., Sellis, T., Egenhofer, M. "Topological Relations in the World of Minimum Bounding Rectangles: a Study with R-trees". In the Proceedings of the ACM Conference on the Modeling of Data (SIGMOD), San Jose, CA, 1995.

Randell, D. A., Cui, Z., Cohn., A., "A Spatial Logic Based on Regions and Connection". In the Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning, 1992.

Smith, T., Park,K. "Algebraic Approach to Spatial Reasoning". International Journal of Geographic Information Systems, Vol. 6, No. 3,pp. 177-192, 1992.

Theodoridis, Y., Papadias, D. "Range Queries Involving Spatial Relations: A Performance Analysis". Proceedings of the Second European Conference on Spatial InformationTheory (COSIT), 1995.

Endnotes

[1] Randell et al., (92) who defined the same set of topological relations using a logic-based approach, called this relation partially_overlap.