Associate Professor Sanjiang Li

Li, S. & Cohn, A. 2012, 'Reasoning with Topological and Directional Spatial Information', Computational Intelligence, vol. 28, no. 4, pp. 579-616.
View/Download from: Publisher's site
View description>>

Sanjiang Li, Anthony G Cohn, Reasoning with Topological and Directional Spatial Information. Computational Intelligence, 2012, 28(4):579-616 (DOI=10.1111/j.1467-8640.2012.00431.x) (PDF) (An early version is available via arXiv) (This is a significant extension of the IJCAI-07 paper)

Liu, W. & Li, S. 2011, 'On standard models of fuzzy Region Connection Calculus', International Journal of Approximate Reasoning, vol. 52, no. 9, pp. 1337-1354.
View/Download from: Publisher's site
View description>>

The Region Connection Calculus (RCC) is perhaps the most influential topological relation calculus. Based on the first-order logic, the RCC, however, does not fully meet the needs of applications where the vagueness of entities or relations is important and not ignorable. This paper introduces standard models for the fuzzy region connection calculus (RCC) proposed by Schockaert et al. (2008) [18]. Each of such a standard fuzzy RCC model is induced by a standard RCC model in a natural way. We prove that each standard fuzzy RCC model is canonical in the sense that any satisfiable set of fuzzy RCC8 constraints have a solution in it. Apolynomial realization algorithm is also provided. As a side product,we showsimilar sets of fuzzy constraints have similar solutions if both are satisfiable. This allows us to approximate fuzzy RCC constraints that have arbitrary bounds by those have bounds with finite precision. -® 2011 Published by Elsevier Inc.

Liu, W. & Li, S. 2011, 'Reasoning about Cardinal Directions between Extended Objects: The NP-Hardness Result', Artificial Intelligence Journal, vol. 175, no. 18, pp. 2155-2169.
View/Download from: UTSePress | Publisher's site
View description>>

Weiming Liu, Sanjiang Li.Reasoning about Cardinal Directions between Extended Objects: The NP-Hardness Result. Artificial Intelligence, 2011, 175(18): 2155-2169.

Liu, W., Zhang, X., Li, S. & Ying, M. 2010, 'Reasoning about Cardinal Directions between Extended Objects', Artificial Intelligence Journal, vol. 174, no. 12-13, pp. 951-983.
View/Download from: UTSePress | Publisher's site
View description>>

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a relation model, known as the cardinal direction calculus (CDC), for representing direction relations between connected plane regions. The CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking the consistency of complete networks of basic CDC constraints, and proves that reasoning with the CDC is in general an NP-complete problem. For a consistent complete network of basic CDC constraints, our algorithm returns a Ô++canonicalÔ++ solution in cubic time. This cubic algorithm is also adapted to check the consistency of complete networks of basic cardinal constraints between possibly disconnected regions.

Gao, X., Lu, R., Ouyang, D., Sun, J., Li, S., Shi, C., Yao, T., Lu, R., Han, Z., Wang, J. & Cao, C. 2008, 'AI In China: A Survey', IEEE Intelligent Systems, vol. 23, no. 6, pp. 26-32.
View/Download from: UTSePress
View description>>

This article consists of nine short essays discussing research pursued by AI researchers in China and their perspectives on research in several AI subareas. The article first introduces the mechanization of mathematics, an area in which Chinese scientists have made significant contributions. It then discusses research in automated reasoning, temporal and spatial knowledge representation and reasoning, natural language understanding, intelligent diagnosis, multiagent systems, computational intelligence, large-scale knowledge processing, and several research streams integrating AI techniques with methods from other fields. Finally, the article makes suggestions concerning future AI research in China.

Li, S. & Ying, M. 2008, 'Soft constraint abstraction based on semiring homomorphism', Theoretical Computer Science, vol. 403, no. 2-3, pp. 192-201.
View/Download from: UTSePress | Publisher's site
View description>>

The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraints solving and optimization, Journal of the ACM 44 (2) (1997) 201+236], is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, we first work in the abstract problem and find its optimal solutions, and then use them to solve the concrete problem. In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism ? and a problem P over S, if t is optimal in ?(P), then there is an optimal solution View the MathML source of P such that View the MathML source has the same value as t in ?(P).

Li, S. 2007, 'A representation theorem for minmax regret policies', Artificial Intelligence, vol. 171, no. 1, pp. 19-24.
View/Download from: UTSePress | Publisher's site
View description>>

Decision making under uncertainty is one of the central tasks of artificial agents. Due to their simplicity and ease of specification, qualitative decision tools are popular in artificial intelligence. Brafman and Tennenholtz [R.I. Brafman, M. Tennenholtz, An axiomatic treatment of three qualitative decision criteria, J. ACM 47 (3) (2000) 452+482] model an agent's uncertain knowledge as her local state, which consists of states of the world that she deems possible. A policy determines for each local state a total preorder of the set of actions, which represents the agent's preference over these actions. It is known that a policy is maximin representable if and only if it is closed under unions and satisfies a certain acyclicity condition. In this paper we show that the above conditions, although necessary, are insufficient for minmax regret and competitive ratio policies. A complete characterization of these policies is obtained by introducing the best-equally strictness.

Li, S. & Nebel, B. 2007, 'Qualitative Spatial Representation and Reasoning: A Hierarchical Approach', The Computer Journal, vol. 50, no. 4, pp. 391-402.
View/Download from: UTSePress | Publisher's site
View description>>

The ability to reason in space is crucial for agents in order to make informed decisions. Current high-level qualitative approaches to spatial reasoning have serious deficiencies in not reflecting the hierarchical nature of spatial data and human spatial cognition. This article proposes a framework for hierarchical representation and reasoning about topological information, where a continuous model of space is approximated by a collection of discrete sub-models, and spatial information is hierarchically represented in discrete sub-models in a rough set manner. The work is based on the Generalized Region Connection Calculus theory, where continuous and discrete models of space are coped in a unified way. Reasoning issues such as determining the mereological (part-whole) relations between two rough regions are also discussed. Moreover, we consider an important problem that is closely related to map generalization in cartography and Geographical Information Science. Given a spatial configuration at a finer level, we show how to construct a configuration at a coarser level while preserving the mereological relations.

Li, S. 2006, 'A complete classification of topological relations using the 9-intersection method', International Journal of Geographical Information Science, vol. 20, no. 6, pp. 589-610.
View/Download from: UTSePress | Publisher's site
View description>>

Formalization of topological relations between spatial objects is an important aspect of spatial representation and reasoning. The well-known 9-Intersection Method (9IM) was previously used to characterize topological relations between simple regions, i.e. regions with connected boundary and exterior. This simplified abstraction of spatial objects as simple regions cannot model the variety and complexity of spatial objects. For example, countries like Italy may contain islands and holes. It is necessary that existing formalisms, 9IM in particular, cover this variety and complexity. This paper generalizes 9IM to cope with general regions, where a (general) region is a non-empty proper regular closed subset of the Euclidean plane. We give a complete classification of topological relations between plane regions. For each possible relation we either show that it violates some topological constraints and hence is non-realizable or find two plane regions it relates. Altogether 43 (out of 512) relations are identified as realizable. Among these, five can be realized only between exotic (plane) regions, where a region is exotic if there is another region that has the same boundary but is not its complement. For all the remaining 38 relations, we construct configurations by using sums, differences and complements of discs.

Li, S. & Li, Y. 2006, 'On The Complemented Disk Algebra', Journal Of Logic And Algebraic Programming, vol. 66, no. 2, pp. 195-211.
View/Download from: UTSePress | Publisher's site
View description>>

The importance of relational methods in temporal and spatial reasoning has been widely recognised in the last two decades. A quite large part of contemporary spatial reasoning is concerned with the research of relation algebras generated by the

Li, S. 2006, 'On Topological Consistency And Realization', Constraints, vol. 11, no. 1, pp. 31-51.
View/Download from: UTSePress | Publisher's site
View description>>

Topological relations are important in various tasks of spatial reasoning, scene description and object recognition. The RCC8 spatial constraint language developed by Randell, Cui and Cohn (1992) is widely recognized as of particular importance in both t

Li, S. & Wang, H. 2006, 'RCC8 binary constraint network can be consistently extended', Artificial Intelligence, vol. 170, no. 1, pp. 1-18.
View/Download from: UTSePress | Publisher's site
View description>>

The RCC8 constraint language developed by Randell et al. has been popularly adopted by the Qualitative Spatial Reasoning and GIS communities. The recent observation that RCC8 composition table describes only weak composition instead of composition raises questions about Renz and Nebel's maximality results about the computational complexity of reasoning with RCC8. This paper shows that any consistent RCC8 binary constraint network (RCC8 network for short) can be consistently extended. Given ?, an RCC8 network, and z, a fresh variable, suppose xTyset membership, variant? and T is contained in the weak composition of R and S. This means that we can add two new constraints xRz and zSy to ? without changing the consistency of the network. The result guarantees the applicability to RCC8 of one key technique, (Theorem 5) of [J. Renz, B. Nebel, On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Artificial Intelligence 108 (1999) 69+123], which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse.

Xia, L. & Li, S. 2006, 'On Minimal Models Of The Region Connection Calculus', Fundamenta Informaticae, vol. 69, no. 4, pp. 427-446.
View/Download from: UTSePress
View description>>

Region Connection Calculus (RCC) is one primary formalism of qualitative spatial reasoning. Standard RCC models are continuous ones where each region is infinitely divisible. This contrasts sharply with the predominant use of finite, discrete models in a

Li, S., Ying, M. & Li, Y. 2005, 'On Countable RCC Models', Fundamenta Informaticae, vol. 65, no. 4, pp. 329-351.
View/Download from: UTSePress
View description>>

Region Connection Calculus (RCC) is the most widely studied formalism of Qualitative Spatial Reasoning. It has been known for some time that each connected regular topological space provides an RCC model. These 'standard' models are inevitable uncountabl

Li, S. & Li, Y. 2004, 'A fuzzy sets theoretic approach to approximate spatial reasoning', IEEE Transactions on Fuzzy Systems, vol. 12, no. 6, pp. 745-754.
View/Download from: UTSePress | Publisher's site
View description>>

Relational composition-based reasoning has become the most prevalent method for qualitative reasoning since Allen's 1983 work on temporal intervals. Underlying this reasoning technique is the concept of a jointly exhaustive and pairwise disjoint set of relations. Systems of relations such as RCC5 and RCC8 were originally developed for ideal regions, not subject to imperfections such as vagueness or fuzziness which are found in many applications in geographic analysis and image understanding. This paper, however, presents a general method for classifying binary topological relations involving fuzzy regions using the RCC5 or the RCC8 theory. Our approach is based on fuzzy set theory and the theory of consonant random set. Some complete classifications of topological relations between fuzzy regions are also given. Furthermore, two composition operators on spatial relations between fuzzy regions are introduced in this paper. These composition operators provide reasonable relational composition-based reasoning engine for spatial reasoning involving fuzzy regions.

Li, S. & Luo, M. 2004, 'A Note On Stratified L-Real Line And Unit L-Interval', Fuzzy Sets and Systems, vol. 147, no. 2, pp. 327-332.
View/Download from: UTSePress | Publisher's site
View description>>

We show that the stratified L-real line and the stratified unit L-interval have no non-trivial crisp open sets. Simple characterizations for Boolean-valued stratified L-interval and L-line are also given. (C) 2004 Elsevier B.V. All rights reserved.

Li, S. & Ying, M. 2004, 'Generalized Region Connection Calculus', Artificial Intelligence, vol. 160, no. 1-2, pp. 1-34.
View/Download from: UTSePress | Publisher's site
View description>>

The Region Connection Calculus (RCC) is one of the most widely referenced system of high-level (qualitative) spatial reasoning. RCC assumes a continuous representation of space. This contrasts sharply with the fact that spatial information obtained from physical recording devices is nowadays invariably digital in form and therefore implicitly uses a discrete representation of space. Recently, Galton developed a theory of discrete space that parallels RCC, but question still lies in that can we have a theory of qualitative spatial reasoning admitting models of discrete spaces as well as continuous spaces? In this paper we aim at establishing a formal theory which accommodates both discrete and continuous spatial information, and a generalization of Region Connection Calculus is introduced. GRCC, the new theory, takes two primitives: the mereological notion of part and the topological notion of connection. RCC and Galton's theory for discrete space are both extensions of GRCC. The relation between continuous models and discrete ones is also clarified by introducing some operations on models of GRCC. In particular, we propose a general approach for constructing countable RCC models as direct limits of collections of finite models. Compared with standard RCC models given rise from regular connected spaces, these countable models have the nice property that each region can be constructed in finite steps from basic regions. Two interesting countable RCC models are also given: one is a minimal RCC model, the other is a countable sub-model of the continuous space R2.

D++ntsch, I. & Li, S. 2012, 'Extension Properties of Boolean Contact Algebras', International Conference on Relational and Algebraic Methods in Computer Science, Cambridge, UK, September 2012 in Proceedings of the 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS), ed Kahl, W; Griffin, T.G., Springer-Verlag, Berlin Heidelberg, pp. 342-356.
View description>>

Ivo D++ntsch, Sanjiang Li. Extension Properties of Boolean Contact Algebras, Proceedings of the 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS), pages 342-356, Cambridge, UK, September 17-20, 2012.

Liu, W. & Li, S. 2012, 'Here, There, but Not Everywhere: An Extended Framework for Qualitative Constraint Satisfaction', European conference on artificial intelligence, Montpellier, France, August 2012 in Proceedings of the 20th European conference on artificial intelligence (ECAI-2012), ed De Raedt, L.; et al., IOS Press, Amsterdam, pp. 552-557.
View description>>

Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activities. The qualitative approach to spatial and temporal reasoning (QSTR) provides a promising framework for spatial and temporal knowledge representation and reasoning. QSTR typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with the knowledge by solving qualitative constraints. When formulating a qualitative constraint satisfaction problem (CSP), it is usually assumed that each variable could be Ô++here, there and everywhere2.Ô+ Practical applications e.g. urban planning, however, often require a variable taking values from a certain finite subset of the universe, i.e. require it to be Ô++here or thereÔ++. This paper extends the classic framework of qualitative constraint satisfaction by allowing variables taking values from finite domains. The computational complexity of this extended consistency problem is examined for five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC-5, and RCC-8. We show that the extended consistency problem remains in NP, but when only basic constraints are considered, the extended consistency problem for each calculus except Point Algebra is already NP-hard.

Liu, W. & Li, S. 2012, 'Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning', International Conference on Principles and Practice of Constraint Programming, Quebec City, Canada, October 2012 in Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP-2012), ed Milano, M, Springer-Verlag, Berlin Heidelberg, pp. 464-479.
View/Download from: Publisher's site
View description>>

Weiming Liu, Sanjiang Li. Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning, Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP-2012), pages 464-479, Quebec City, Canada, October 8-12, 2012.

Schockaert, S. & Li, S. 2012, 'Convex solutions of RCC8 networks', European conference on artificial intelligence, Montpellier, France, August 2012 in Proceedings of the 20th European conference on artificial intelligence (ECAI-2012), ed De Raedt, L; et al., IOS Press, Amsterdam, pp. 726-731.
View description>>

RCC8 is one of the most widely used calculi for qualitative spatial reasoning. Although many applications have been explored where RCC8 relations refer to geographical or physical regions in two- or three-dimensional spaces, their use for conceptual reasoning is still at a rather preliminary stage. One of the core obstacles with using RCC8 to reason about conceptual spaces is that regions are required to be convex in this context. We investigate in this paper how the latter requirement impacts the realizability of RCC8 networks. Specifically, we show that consistent RCC8 networks over 2n + 1 variables are guaranteed to have a convex solution in Euclidean spaces of n dimensions and higher. We furthermore prove that our bound is optimal for 2- and 3-dimensional spaces, and that for any number of dimensions n Ô+Ñ 4, there exists a network of RCC8 relations over 3n variables which is consistent, but does not allow a convex solution in the n-dimensional Euclidean space.

Liu, W., Wang, S., Li, S. & Liu, D. 2011, 'Solving Qualitative Constraints Involving Landmarks', International Conference on Principles and Practice, Perugia, Italy, September 2011 in The 17th International Conference on Principles and Practice of Constraint Programming, ed Jimmy Lee, Springer-Verlag Berlin / Heidelberg, Berlin/Heidelberg, pp. 523-537.
View/Download from: UTSePress
View description>>

Consistency checking plays a central role in qualitative spatial and temporal reasoning. Given a set of variables V , and a set of constraints ++ taken from a qualitative calculus (e.g. the Interval Algebra (IA) or RCC-8), the aim is to decide if ++ is consistent. The consistency problem has been investigated extensively in the literature. Practical applications e.g. urban planning often impose, in addition to those between undetermined entities (variables), constraints between determined entities (constants or landmarks) and variables. This paper introduces this as a new class of qualitative constraint satisfaction problems, and investigates the new consistency problem in several well-known qualitative calculi, e.g. IA, RCC-5, and RCC-8.We show that the usual local consistency checking algorithm works for IA but fails in RCC-5 and RCC-8. We further show that, if the landmarks are represented by polygons, then the new consistency problem of RCC-5 is tractable but that of RCC-8 is NP-complete.

Duckham, M., Jeong, M., Li, S. & Renz, J. 2010, 'Decentralized querying of topological relations between regions without using localization', ACM International Symposium on Advances in Geographic Information Systems, San Jose, USA, November 2010 in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, ed NA, ACM, USA, pp. 414-417.
View/Download from: UTSePress | Publisher's site
View description>>

This paper proposes an efficient, decentralized algorithm for determining the topological relationship between two regions monitored by a geosensor network. Many centralized algorithms already exist for this purpose (used for example in spatial databases

Li, S. 2010, 'A Layered Graph Representation for Complex Regions', International Conference on the Principles of Knowledge Representation and Reasoning, Toronto, Canada, May 2010 in Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning, ed Lin, F. and Sattler, U., and Truszczynski, M., AAAI, USA, pp. 581-583.
View/Download from: UTSePress
View description>>

Sanjiang Li. A Layered Graph Representation for Complex Regions, in Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR-10), pages 581-583, Toronto, Canada, May 9-13, 2010

Li, S. & Liu, W. 2010, 'Topological Relations between Convex Regions', National Conference of the American Association for Artificial Intelligence, Atlanta, Georgia, USA, July 2010 in Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-10), ed Fox, Maria and Poole, David, AAAI Press, USA, pp. 321-326.
View/Download from: UTSePress
View description>>

Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet u, v, x, y. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description

Liu, W., Li, S. & Renz, J. 2009, 'Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity', International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 2009 in Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence - vol 2, ed Craig Boutilier, AAAI Press, USA, pp. 854-859.
View/Download from: UTSePress
View description>>

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from both calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculiwas very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.

Li, J., Kowalski, T., Renz, J. & Li, S. 2008, 'Combining binary constraint networks in qualitative reasoning', European Conference on Artificial Intelligence, Patras, Greece, July 2008 in Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence: Frontiers in Artificial Intelligence and Applications, ed Malik Ghallab and Constantine D. Spyropoulos and Nikos Fakotakis and Nikolaos M. Avouris, IOS Press, Holland, pp. 515-519.
View/Download from: UTSePress
View description>>

Constraint networks in qualitative spatial and temporal reasoning are always complete graphs. When one adds an extra element to a given network, previously unknown constraints are derived by intersections and compositions of other constraints, and this may introduce inconsistency to the overall network. Likewise, when combining two consistent networks that share a common part, the combined network may become inconsistent. In this paper, we analyse the problem of combining these binary constraint networks and develop certain conditions to ensure combining two networks will never introduce an inconsistency for a given spatial or temporal calculus. This enables us to maintain a consistent world-view while acquiring new information in relation with some part of it. In addition, our results enable us to prove other important properties of qualitative spatial and temporal calculi in areas such as representability and complexity.

Zhang, X., Liu, W., Li, S. & Ying, M. 2008, 'Reasoning with Cardinal Directions: An Efficient Algorithm', National Conference of the American Association for Artificial Intelligence, Chicago, Illinois, USA, July 2008 in Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1, ed Dieter Fox and Carla P. Gomes, AAAI Press, USA, pp. 387-392.
View/Download from: UTSePress
View description>>

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, called Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with disconnected regions, in which case the current best algorithm is of time complexity O(n5).

Li, S. 2007, 'Combining Topological and Directional Information for Spatial Reasoning', International Joint Conference on Artificial Intelligence, Hyderabad, India, January 2007 in Proceedings of the 20th International Joint Conference on Artificial Intelligence, ed Manuela M. Veloso, AAAI Press, USA, pp. 435-440.
View/Download from: UTSePress
View description>>

Current research on qualitative spatial representation and reasoning usually focuses on one single aspect of space. However, in real world applications, several aspects are often involved together. This paper extends the well-known RCC8 constraint language to deal with both topological and directional information, and then investigates the interaction between the two kinds of information. Given a topological (RCC8) constraint network and a directional constraint network, we ask when the joint network is satisfiable. We show that when the topological network is over one of the three maximal tractable subclasses of RCC8, the problem can be reduced into satisfiability problems in the RCC8 algebra and the rectangle algebra (RA). Therefore, reasoning techniques developed for RCC8 and RA can be used to solve the satisfiability problem of a joint network.

Li, S. 2006, 'Combining topological and directional information: First results', International Conference on Knowledge Science, Engineering and Management, Guilin, China, August 2006 in Knowledge Science, Engineering And Management : Lecture Notes in Artificial Intelligence Vol 4092, ed Lang, J, Lin, F, Wang, J, Springer-Verlag Berlin, Berlin, pp. 252-264.
View/Download from: UTSePress | Publisher's site
View description>>

Representing and reasoning about spatial information is important in artificial intelligence and geographical information science. Relations between spatial entities are the most important kind of spatial information. Most current formalisms of spatial relations focus on one single aspect of space. This contrasts sharply with real world applications, where several aspects are usually involved together. This paper proposes a qualitative calculus that combines a simple directional relation model with the well-known topological RCC5 model. We show by construction that the consistency of atomic networks can be decided in polynomial time.