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.
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.  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.
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:
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.
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.
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.
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.