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, A/DRsch Ctr Quantum Computat'n & Intelligent Systs
Core Member, Joint Research Centre in Intelligent Systems Membership
Core Member, QCIS - Quantum Computation and Intelligent Systems
Science, Science
 
Phone
+61 2 9514 7872

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.

Can supervise: Yes

Dr Weiming Liu, PhD student in Computer Science (graduated in July 2012, received the Chancellor's Award for the best PhD thesis, 2013)

Mr Zhiguo Long, PhD student in Computer Science (from July 2012)

Mr Shufeng Kong, PhD student in Computer Science (from July 2014)

Logic in Computer Science

Conferences

Meng, H., Kou, H. & Li, S. 2015, 'Belief Revision with General Epistemic States', Online proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, Austin, Texas, pp. 1553-1559.
View/Download from: UTS OPUS
In order to properly regulate iterated belief revision, Darwiche and Pearl (1997) model belief revision as revising epistemic states by propositions. An epistemic state in their sense consists of a belief set and a set of conditional beliefs. Although the denotation of an epistemic state can be indirectly captured by a total preorder on the set of worlds, it is unclear how to directly capture the structure in terms of the beliefs and conditional beliefs it contains. In this paper, we first provide an axiomatic characterisation for epistemic states by using nine rules about beliefs and conditional beliefs, and then argue that the last two rules are too strong and should be eliminated for characterising the belief state of an agent. We call a structure which satisfies the first seven rules a general epistemic state (GEP). To provide a semantical characterisation of GEPs, we introduce a mathematical structure called belief algebra, which is in essence a certain binary relation defined on the power set of worlds.We then establish a 1-1 correspondence between GEPs and belief algebras, and show that total preorders on worlds are special cases of belief algebras. Furthermore, using the notion of belief algebras, we extend the classical iterated belief revision rules of Darwiche and Pearl to our setting of general epistemic states.
Kong, S., Li, S., Li, Y. & Long, Z. 2015, 'On tree-preserving constraints', 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings, 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), Springer International Publishing, Cork, Ireland.
View/Download from: Publisher's site
Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. This paper studies and compares three subclasses of tree convex constraints which are called chain-, path- and tree-preserving constraints respectively. While the tractability of the subclass of chain-preserving constraints has been established before, this paper shows that every chain- or path-preserving constraint network is in essence the disjoint union of several independent connected row convex constraint networks, and hence (re-)establish the tractability of these two subclasses of tree convex constraints. We further prove that, when enforcing arc- and path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of the tree-preserving network if no inconsistency is detected. Moreover, it also guarantees the applicability of the partial path-consistency algorithm to tree-preserving constraint networks, which is usually more efficient than the path-consistency algorithm for large sparse networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.
Sioutis, M., Li, S. & Condotta, J.F. 2015, 'Efficiently characterizing non-redundant constraints in large real world qualitative spatial networks', IJCAI International Joint Conference on Artificial Intelligence, International Conference on Artificial Intelligence, AAAI Press, Buenos Aires, Argentina, pp. 3229-3235.
RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-consistency and -consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.
Sioutis, M., Li, S. & Condotta, J.F. 2015, 'On redundancy in linked geospatial data', CEUR Workshop Proceedings, 2nd Workshop on Linked Data Quality co-located with 12th Extended Semantic Web Conference, Aachen university, Portoroz, Slovenia, pp. 1-8.
RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. As such, RCC8 has been recently adopted by GeoSPARQL in an effort to enrich the Semantic Web with qualitative spatial relations. We focus on the redundancy that these data might harbor, which can throttle graph related applications, such as storing, representing, querying, and reasoning. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. In this paper, we present a practical approach for obtaining the prime networks of RCC8 networks that originate from the Semantic Web, by exploiting the sparse and loosely connected structure of their constraint graphs, and, consequently, contribute towards offering Linked Geospatial Data of high quality. Experimental evaluation exhibits a vast decrease in the total number of non-redundant constraints that we can obtain from an initial network, while it also suggests that our approach significantly boosts the state-of-the-art approach.
Duckham, M., Li, S., Liu, W. & Long, Z. 2014, 'On Redundant Topological Constraints', Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014.
View/Download from: UTS OPUS
Meng, H. & Li, S. 2014, 'A Topological Characterisation of Belief Revision over Infinite Propositional Languages', PRICAI 2014: Trends in Artificial Intelligence - 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014. Proceedings, pp. 77-90.
View/Download from: UTS OPUS or Publisher's site
Li, J.J. & Li, S. 2013, 'On Finding Approximate Solutions of Qualitative Constraint Networks', IEEE 25th International Conference on Tools with Artificial Intelligence, International Conference on Tools with Artificial Intelligence, IEEE, Herndon, VA, USA, pp. 30-37.
View/Download from: UTS OPUS or 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.
Schockaert, S. & Li, S. 2013, 'Combining RCC5 relations with betweenness information', Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), International Joint Conference on Artificial Intelligence, AAAI Press / International Joint Conferences on Artificial Intelligence, Beijing, China, pp. 1083-1089.
View/Download from: UTS 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 Gärdenfors. 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.
Duntsch, I. & Li, S. 2012, 'Extension Properties of Boolean Contact Algebras', Proceedings of the 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS), International Conference on Relational and Algebraic Methods in Computer Science, Springer-Verlag, Cambridge, UK, pp. 342-356.
View/Download from: UTS OPUS
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', Proceedings of the 20th European conference on artificial intelligence (ECAI-2012), European conference on artificial intelligence, IOS Press, Montpellier, France, pp. 552-557.
View/Download from: UTS OPUS or Publisher's site
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', Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP-2012), International Conference on Principles and Practice of Constraint Programming, Springer-Verlag, Quebec City, Canada, pp. 464-479.
View/Download from: UTS OPUS or 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.
Schockaert, S. & Li, S. 2012, 'Convex solutions of RCC8 networks', Proceedings of the 20th European conference on artificial intelligence (ECAI-2012), European conference on artificial intelligence, IOS Press, Montpellier, France, pp. 726-731.
View/Download from: UTS OPUS or Publisher's site
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', The 17th International Conference on Principles and Practice of Constraint Programming, International Conference on Principles and Practice, Springer-Verlag Berlin / Heidelberg, Perugia, Italy, pp. 523-537.
View/Download from: UTS 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', Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-10), National Conference of the American Association for Artificial Intelligence, AAAI Press, Atlanta, Georgia, USA, pp. 321-326.
View/Download from: UTS OPUS
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', GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, ACM International Symposium on Advances in Geographic Information Systems, ACM, San Jose, USA, pp. 414-417.
View/Download from: UTS OPUS or 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', Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning, International Conference on the Principles of Knowledge Representation and Reasoning, AAAI, Toronto, Canada, pp. 581-583.
View/Download from: UTS OPUS
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', Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence - vol 2, International Joint Conference on Artificial Intelligence, AAAI Press, Pasadena, California, USA, pp. 854-859.
View/Download from: UTS 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', Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1, National Conference of the American Association for Artificial Intelligence, AAAI Press, Chicago, Illinois, USA, pp. 387-392.
View/Download from: UTS 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', Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence: Frontiers in Artificial Intelligence and Applications, European Conference on Artificial Intelligence, IOS Press, Patras, Greece, pp. 515-519.
View/Download from: UTS 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', Proceedings of the 20th International Joint Conference on Artificial Intelligence, International Joint Conference on Artificial Intelligence, AAAI Press, Hyderabad, India, pp. 435-440.
View/Download from: UTS OPUS
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', Knowledge Science, Engineering And Management : Lecture Notes in Artificial Intelligence Vol 4092, International Conference on Knowledge Science, Engineering and Management, Springer-Verlag Berlin, Guilin, China, pp. 252-264.
View/Download from: UTS OPUS or 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

Long, Z., Duckham, M., Li, S. & Schockaert, S. 2016, 'Indexing large geographic datasets with compact qualitative representation', International Journal of Geographical Information Science, vol. 30, no. 6, pp. 1072-1094.
View/Download from: Publisher's site
© 2015 Taylor & Francis This paper develops a new mechanism to efficiently compute and compactly store qualitative spatial relations between spatial objects, focusing on topological and directional relations for large datasets of region objects. The central idea is to use minimum bounding rectangles (MBRs) to approximately represent region objects with arbitrary shape and complexity and only store spatial relations that cannot be unambiguously inferred from the relations of corresponding MBRs. We demonstrate, both in theory and practice, that our approach requires considerably less construction time and storage space, and can answer queries more efficiently than the state-of-the-art methods.
Li, S., Long, Z., Liu, W., Duckham, M. & Both, A. 2015, 'On redundant topological constraints', Artificial Intelligence, vol. 225, pp. 51-76.
View/Download from: UTS OPUS or Publisher's site
Abstract Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set of qualitative constraints, we say a constraint ( x R y ) in is redundant if it is entailed by the rest of . A prime subnetwork of is a subset of which contains no redundant constraints and has the same solution set as . It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from . As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.
Schockaert, S. & Li, S. 2015, 'Realizing RCC8 networks using convex regions', Artificial Intelligence, vol. 218, pp. 74-105.
View/Download from: UTS OPUS or Publisher's site
RCC8 is a popular fragment of the region connection calculus, in which qualitative spatial relations between regions, such as adjacency, overlap and parthood, can be expressed. While RCC8 is essentially dimensionless, most current applications are confined to reasoning about two-dimensional or three-dimensional physical space. In this paper, however, we are mainly interested in conceptual spaces, which typically are high-dimensional Euclidean spaces in which the meaning of natural language concepts can be represented using convex regions. The aim of this paper is to analyze how the restriction to convex regions constrains the realizability of networks of RCC8 relations. First, we identify all ways in which the set of RCC8 base relations can be restricted to guarantee that consistent networks can be convexly realized in respectively 1D, 2D, 3D, and 4D. Most surprisingly, we find that if the relation 'partially overlaps' is disallowed, all consistent atomic RCC8 networks can be convexly realized in 4D. If instead refinements of the relation 'part of' are disallowed, all consistent atomic RCC8 relations can be convexly realized in 3D. We furthermore show, among others, that any consistent RCC8 network with 2n+1 variables can be realized using convex regions in the n-dimensional Euclidean space.
Zhou, B., Xu, G. & Li, S. 2015, 'The Quintuple Implication Principle of fuzzy reasoning', Information Sciences, vol. 297, pp. 202-215.
View/Download from: UTS OPUS or Publisher's site
Li, S. & Liu, W. 2015, 'Cardinal directions: a comparison of direction relation matrix and objects interaction matrix', International Journal of Geographical Information Science, vol. 29, no. 2, pp. 194-216.
View/Download from: Publisher's site
© 2014 Taylor & Francis. How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.
Cohn, A.G., Li, S., Liu, W. & Renz, J. 2014, 'Reasoning about Topological and Cardinal Direction Relations Between 2-Dimensional Spatial Objects', J. Artif. Intell. Res. (JAIR), vol. 51, pp. 493-532.
View/Download from: UTS OPUS or Publisher's site
Meng, H. & Li, S. 2014, 'A topological characterisation of belief revision over infinite propositional languages', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8862, pp. 77-90.
View/Download from: Publisher's site
© Springer International Publishing Switzerland 2014. Belief revision mainly concerns how an agent updates her belief with new evidence. The AGM framework of belief revision models belief revision as revising theories by propositions. To characterise AGMstyle belief revision operators, Grove proposed in 1988 a representation model using systems of spheres. This 'spheres' model is very influential and has been extended to characterise multiple belief revision operators. Several fundamental problems remain unsettled regarding this 'spheres' model. In this paper we introduce a topology on the set of all worlds of an infinite propositional language and use this topology to characterise systems of spheres. For each AGM operator , we show that, among all systems of spheres deriving , there is a minimal one which is contained in every other system. We give a topological characterisation of these minimal systems. Furthermore, we propose a method for extending an AGM operator to a multiple revision operator and show by an example that the extension is not unique. This negatively answers an open problem raised by Peppas.
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: UTS OPUS or 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: UTS OPUS or Publisher's site
Ivo Düntsch, Sanjiang Li. On the homogeneous countable Boolean contact algebra. Logic and Logical Philosophy, 2013, 22, 213251.
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: UTS OPUS or 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
Düntsch, 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: Publisher's site
In a recent paper, we have shown that the class of Boolean contact algebras (BCAs) has the hereditary property, the joint embedding property and the amalgamation property. By Frassé's theorem, this shows that there is a unique countable homogeneous BCA. This paper investigates this algebra and the relation algebra generated by its contact relation. We first show that the algebra can be partitioned into four sets {0}, {1}, K, and L, which are the only orbits of the group of base automorphisms of the algebra, and then show that the contact relation algebra of this algebra is finite, which is the first non-trivial extensional BCA we know which has this property. © Nicolaus Copernicus University (Toruń) 2013.
Li, S. & Cohn, A. 2012, 'Reasoning with Topological and Directional Spatial Information', Computational Intelligence, vol. 28, no. 4, pp. 579-616.
View/Download from: UTS OPUS or 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: UTS OPUS or 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: UTS OPUS or 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: UTS OPUS or 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: UTS OPUS or 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) 201236], 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: UTS OPUS or 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: UTS OPUS or 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) 452482] 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: UTS OPUS or 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, Y.M. & Li, S.J. 2007, 'Representation of RCC11 composition table', Ruan Jian Xue Bao/Journal of Software, vol. 18, no. 10, pp. 2458-2468.
View/Download from: Publisher's site
This paper is mainly concerned with the relation-algebraic aspects of the well-known Region Connection Calculus (RCC). It is shown that the complemented closed disk algebra is a representation for the relation algebra determined by the RCC11 table, which was first described by Düntsch. The domain of this algebra contains two classes of regions, the closed disks and closures of their complements in the real plane, and the contact relation is the standard Whiteheadean contact (i.e. aCb iff aCb iff a).
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: UTS OPUS or 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) 69123], 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: UTS OPUS or 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: UTS 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: UTS OPUS or 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: UTS OPUS or 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. 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: 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. © 2006 Taylor & Francis.
Li, S., Ying, M. & Li, Y. 2005, 'On Countable RCC Models', Fundamenta Informaticae, vol. 65, no. 4, pp. 329-351.
View/Download from: UTS 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: UTS OPUS or 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: UTS OPUS or 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: UTS OPUS or 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: UTS OPUS or 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: UTS OPUS or 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: UTS 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: UTS OPUS or 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: UTS OPUS or 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: UTS 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.

Other

Long, Z. & Li, S. 2015, 'On distributive subalgebras of qualitative spatial and temporal calculi'.
View/Download from: Publisher's site
© Springer International Publishing Switzerland 2015. Qualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This paper studies distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition distributives over nonempty intersections. The well-known subclass of convex interval relations is an example of distributive subalgebras. It has been proven for RCC5 and RCC8 that path consistent constraint network over a distributive subalgebra is always minimal and strongly n-consistent in a qualitative sense (weakly globally consistent). We show that the result also holds for the four popular qualitative calculi, i.e. Point Algebra, Interval Algebra, Cardinal Relation Algebra, and Rectangle Algebra. Moreover, this paper gives a characterisation of distributive subalgebras, which states that the intersection of a set of m 3 relations in the subalgebra is nonempty if and only if the intersection of every two of these relations is nonempty. We further compute and generate all maximal distributive subalgebras for those four qualitative calculi mentioned above. Lastly, we establish two nice properties which will play an important role in efficient reasoning with constraint networks involving a large number of variables.