UTS site search

Professor Sanjiang Li

Biography

Education

1996-2001 Sichuan University, Chengdu, China
Ph.D. in Mathematics

1992-1996 Shaanxi Normal University, Xi’an, China
B.Sc. in Mathematics

Employment

From January 2009: Faculty of Engineering and Information Technology, University of Technology, Sydney

September 2001 – December 2008: Dept. Comp. Sci. & Technol., Tsinghua University

Image of Sanjiang Li
Professor, Faculty of Engineering & Information Technology
Core Member, Centre for Quantum Computation and Intelligent Systems
Core Member, Joint Research Centre in Intelligent Systems Membership
Science, Science
 
Phone
+61 2 9514 7872
Room
CB11.10.202

Research Interests

My research interests are mainly in spatial reasoning and artificial intelligence. The main objective of my research is to establish expressive representation formalism of spatial knowledge and provide effective reasoning mechanisms. This will contribute significantly to the advancement of knowledge in breakthrough science in qualitative spatial reasoning and smart information use in geographical information systems.

Logic in Computer Science

Conference Papers

Schockaert, S. & Li, S. 2013, 'Combining RCC5 relations with betweenness information', International Joint Conference on Artificial Intelligence, Beijing, China, August 2013 in Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), ed Rossi, Francesca, AAAI Press / International Joint Conferences on Artificial Intelligence, Menlo Park, California, pp. 1083-1089.
View/Download from: OPUS |
RCC5 is an important and well-known calculus for representing and reasoning about mereological relations. Among many other applications, it is pivotal in the formalization of commonsense reasoning about natural categories. In particular, it allows for a qualitative representation of conceptual spaces in the sense of Grdenfors. To further the role of RCC5 as a vehicle for conceptual reasoning, in this paper we combine RCC5 relations with information about betweenness of regions. The resulting calculus allows us to express, for instance, that some part (but not all) of region B is between regions A and C. We show how consistency can be decided in polynomial time for atomic networks, even when regions are required to be convex. From an application perspective, the ability to express betweenness information allows us to use RCC5 as a basis for interpolative reasoning, while the restriction to convex regions ensures that all consistent networks can be faithfully represented as a conceptual space.
Li, J.J. & Li, S. 2013, 'On Finding Approximate Solutions of Qualitative Constraint Networks', International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, December 2013 in IEEE 25th International Conference on Tools with Artificial Intelligence, ed Brodsky, Alexander, IEEE, USA, pp. 30-37.
View/Download from: OPUS | Publisher's site
Qualitative Spatial and Temporal Reasoning (QSTR) represents spatial and temporal information in terms of human comprehensible qualitative predicates and reasons about qualitative information by solving qualitative constraint networks (QCNs). Despite significant progress in the past three decades, more and more evidence has shown that it is inherently hard to find exact solutions for expressive qualitative constraints. In many applications, however, we are often required to make decisions in a very limited time. In these cases, finding a good approximate solution in seconds is much more desirable than waiting days for an exact solution. In this paper, we will exploit the algebraic structure of qualitative calculi (e.g. Interval Algebra and RCC8) as well as their conceptual neighbourhood graphs to develop approximate methods for consistency checking in QSTR. Moreover, we propose and empirically compare four independent methods to serve as tools for finding good approximate solutions for the given qualitative calculi.
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: OPUS | Publisher's site
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.
Duntsch, 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.
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.
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/Download from: OPUS |
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. & 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/Download from: OPUS |
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., 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: OPUS
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.
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: OPUS | Publisher's site
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
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: OPUS | Publisher's site
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: OPUS | Publisher's site
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
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: OPUS |
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.
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: OPUS |
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, 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: OPUS |
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.
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: OPUS | Publisher's site
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: OPUS | Publisher's site
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.

Journal Articles

Li, S., Liu, W. & Wang, S. 2013, 'Qualitative constraint satisfaction problems: An extended framework with landmarks', Artificial Intelligence Journal, vol. 201, no. 1, pp. 32-58.
View/Download from: OPUS | Publisher's site
Sanjiang Li, Weiming Liu, Shengsheng Wang: Qualitative constraint satisfaction problems: An extended framework with landmarks. Artificial Intelligence, 2013, 201: 32-58
Duntsch, I. & Li, S. 2013, 'On the homogeneous countable Boolean contact algebra', Logic and Logical Philosophy, vol. 22, no. 2, pp. 213-251.
View/Download from: OPUS |
Ivo Dntsch, Sanjiang Li. On the homogeneous countable Boolean contact algebra. Logic and Logical Philosophy, 2013, 22, 213+251.
Long, Z. & Li, S. 2013, 'A complete classification of spatial relations using the Voronoi-based nine- intersection model', International Journal Of Geographical Information Science, vol. 27, no. 10, pp. 2006-2025.
View/Download from: OPUS | Publisher's site
In this article we show that the Voronoi-based nine-intersection (V9I) model proposed by Chen et al. (2001, A Voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 15 (3), 201-220) is more ex
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
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, 'Reasoning about Cardinal Directions between Extended Objects: The NP-Hardness Result', Artificial Intelligence Journal, vol. 175, no. 18, pp. 2155-2169.
View/Download from: OPUS | Publisher's site
Weiming Liu, Sanjiang Li.Reasoning about Cardinal Directions between Extended Objects: The NP-Hardness Result. Artificial Intelligence, 2011, 175(18): 2155-2169.
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
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., 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: OPUS | Publisher's site
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.
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: OPUS | Publisher's site
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).
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: OPUS | Publisher's site
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. 2007, 'A representation theorem for minmax regret policies', Artificial Intelligence, vol. 171, no. 1, pp. 19-24.
View/Download from: OPUS | Publisher's site
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: OPUS | Publisher's site
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. & Wang, H. 2006, 'RCC8 binary constraint network can be consistently extended', Artificial Intelligence, vol. 170, no. 1, pp. 1-18.
View/Download from: OPUS | Publisher's site
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.
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: OPUS | Publisher's site
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.
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: OPUS
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. & Li, Y. 2006, 'On The Complemented Disk Algebra', Journal Of Logic And Algebraic Programming, vol. 66, no. 2, pp. 195-211.
View/Download from: OPUS | Publisher's site
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: OPUS | Publisher's site
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., Ying, M. & Li, Y. 2005, 'On Countable RCC Models', Fundamenta Informaticae, vol. 65, no. 4, pp. 329-351.
View/Download from: OPUS
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. & Ying, M. 2004, 'Generalized Region Connection Calculus', Artificial Intelligence, vol. 160, no. 1-2, pp. 1-34.
View/Download from: OPUS | Publisher's site
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.
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: OPUS | Publisher's site
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: OPUS | Publisher's site
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. 2003, 'Region Connection Calculus: Its models and composition table', Artificial Intelligence, vol. 145, no. 1-2, pp. 121-146.
View/Download from: OPUS | Publisher's site
Originating in Allen's analysis of temporal relations, the notion of composition table has become a key technique in providing an efficient inference mechanism for a wide class of theories in the field artificial intelligence. This paper is mainly about the consistency-based composition table (RCC8 CT) of the Region Connection Calculus (RCC) raised by Randell, Cui and Cohn. First we show each RCC model is a consistent model of the RCC8 CT. Then after an exhaustive analysis we show that no RCC model can be interpreted extensionally anyway and hence give a negative answer to a conjecture raised by Bennett. All these results are given in an `extensional+ RCC8 composition table, where we attach to each cell entry in the RCC8 CT a superscript to indicate in what circumstances an extensional interpretation is possible.
Li, S. & Luo, M. 2003, 'A Negative Answer To T. Kubiak'S Question', Fuzzy Sets and Systems, vol. 133, no. 3, pp. 407-409.
View/Download from: OPUS | Publisher's site
T. Kubiak raised in 1992 a question about Hausdorffness and compactness in L-topology. It is negatively solved in the present paper by constructing certain L-Hausdorffness and L-compactness axioms. (C) 2002 Elsevier Science B.V. All rights reserved.
Li, S. & Ying, M. 2003, 'Extensionality Of The RCC8 Composition Table', Fundamenta Informaticae, vol. 55, no. 3-4, pp. 363-385.
View/Download from: OPUS
This paper is mainly concerned with the RCC8 composition table entailed by the Region Connection Calculus (RCC), a well-known formalism for Qualitative Spatial Reasoning. This table has been independently generated by Egenhofer in the context of Geograph
Li, S. & Luo, M. 2003, 'FNS Is Not Isomorphic To FTS', Fuzzy Sets and Systems, vol. 136, no. 1, pp. 127-131.
View/Download from: OPUS | Publisher's site
In this paper, we show that there are exactly c different simultaneously bireffective and bicoreflective subconstructs of FNS, in fact there exists a one-to-one correspondence between those subconstructs of FNS and open sets of (0,1). We also prove that
Li, S. & Luo, M. 2003, 'Generalized Lowen Functors', Fuzzy Sets and Systems, vol. 133, no. 3, pp. 375-387.
View/Download from: OPUS | Publisher's site
According to their value ranges, L-topological spaces form different categories. Clearly, the investigation on their relationships is certainly important and necessary. Lowen was one of the first authors who had studied the relation between the category
Li, S. & Zhang, D. 2003, 'A Non-topologically Generated Hutton-lowen Uniformizable Space', Quaestiones Methematicae, vol. 26, no. 4, pp. 471-477.
View/Download from: OPUS
In this note, it is shown that there exist non-topologically generated spaces which are both Lowen uniformizable and Hutton uniformizable. On the other hand, the FNS-coreflection of the Hutton unit interval I(I) is neither Lowen uniformizable nor Hutton uniformizable.