Education background
Bachelor of Mathematics, Shaanxi Normal University, Xi'an, China, 1996;
Ph.D. in Mathematics, Sichuan University, Chengdu, China, 2001.
Areas of Research Interests/ Research Projects
Artificial Intelligence, Spatial Reasoning
National Natural Science Foundation of China: Topological Representation and Reasoning of Spatial Knowledge (2004-2006);
National Natural Science Foundation of China: Representation and Reasoning of Spatial Knowledge based on Qualitative Calculi (2007-2009).
Research Status
Representation and reasoning of spatial knowledge are important in many application areas such as geographic information systems, geo-location services, robotics, and computer vision. I (with coauthors) have systematically investigated a comprehensive topological approach, making significant contributions in spatial relation modeling and constraint solving. A major part of these contributions were built on Region Connection Calculus (RCC), which is the most influential qualitative spatial reasoning paradigm.
1.The Formal Spatial Theory GRCC. We established a formal theory-Generalized Region Connection Calculus (GRCC), which accommodates discrete as well as continuous spatial models. The original RCC theory has only continuous models, but discrete models are evidently important in the implementation of spatial information systems. We solved this conflict and established the connection between continuous and discrete models. Based on GRCC, we established a framework for the hierarchical representation of topological information.
2.Composition-based Reasoning Technique. This is a predominant technique used in qualitative spatial and temporal reasoning. We proved that the composition specified in the RCC8 composition table cannot be interpreted extensionally in any RCC model, and that Egenhofer's 9-Intersection Model (1991) is a maximal extension model for the RCC8 composition table. This implies that whether a relation model is closed under composition is independent of the completeness of the composition-based reasoning. This refutes a conjecture made by Bennett, Isli, and Cohn (1997).
3.Expressive Topological Relation Models. Applying the 9-Intersection Method to two complex plane regions, we obtained a set of 38 basic topological relations among plane regions. By introducing the complements of simple regions, we proposed the complemented Egenhofer model and proved that this model provides a representation for the RCC11 algebra of Duentsch (2005). To cope with imprecise or vague topological information, we proposed a fuzzy set theoretic approach to topological relations.
4.Spatial Constraint Solving Algorithms.We solved several important constraint satisfaction problems in spatial reasoning. For RCC8 algebra, we devised a cubic realization algorithm, and proved that a subclass T is tractable if its closure in RCC8 is tractable. This removes any doubts about the complexity results of Renz and Nebel (1999). The key notion of one-shot extension we introduced was identified later as a sufficient condition for a relation algebra being representable. Skiadopoulos and Koubarakis listed the satisfaction problem of the Cardinal Direction Calculus as an open problem in their paper published in Artificial Intelligence (2005). We completely solved this problem by devising the first correct polynomial realization algorithm. Hybrid spatial constraints are often required in practical applications. We investigated the combination of topological and directional constraints in detail. For Rectangle Algebra (RA), we identified interesting tractable subclasses of hybrid RCC8 and RA constraints. For CDC, we proved that the combination problem is NP-Complete even for basic constraints.
The above results were mainly published on Artificial Intelligence Journal (AIJ, 5 papers) and international conferences IJCAI, AAAI, and ECAI.
Honors And Awards
Australian Research Council (ARC): Future Fellow (2009);
CVIC SE: Software Talents Prize (2008);
Microsoft Research Asia: Young Professor Award (2006);
Alexander von Humboldt Research Fellow (2004).
Academic Achievement
[1] Weiming Liu, Xiaotong Zhang, Sanjiang Li, Mingsheng Ying. Reasoning about Cardinal Directions between Extended Objects, Artificial Intelligence, 2010, 174 (12-13): 951-983. (33 pages, doi:10.1016/j.artint.2010.05.006)
[2] Sanjiang Li, Weiming Liu. Topological Relations between Convex Regions, in Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-10), Atlanta, Georgia, USA, July 11-15, 2010.
[3] Weiming Liu, Sanjiang Li, Jochen Renz. Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity, in: Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09), pages 854-859, Pasadena, CA, July 2009.
[4] Sanjiang Li, Mingsheng Ying. Soft constraint abstraction based on semiring homomorphism, Theoretical Computer Science (B), 403(2-3):192-201, 2008.
[5] Xiaotong Zhang, Weiming Liu, Sanjiang Li, Mingsheng Ying. Reasoning with Cardinal Directions: An Efficient Algorithm, in Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-08), Chicago, IL, 2008.
[6] Sanjiang Li, Bernhard Nebel. Qualitative Spatial Representation and Reasoning: A Hierarchical Approach, The Computer Journal, 2007, 50(4): 391-402.
[7] Sanjiang Li. A representation theorem for minmax regret policies, Artificial Intelligence, 2007, 171(1): 19-24.
[8] Sanjiang Li. Combining Topological and Directional Information for Spatial Reasoning, in M. Veloso, ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07), pages 435-440, AAAI Press, 2007.
[9] Sanjiang Li. A Complete Classification of Topological Relations Using 9-Intersection Method. International Journal of Geographical Information Science, 2006, 20(6): 589-610.
[10] Sanjiang Li, Huaiqing Wang. RCC8 binary constraint network can be consistently extended, Artificial Intelligence, 2006, 170(1): 1-18.
[11] Sanjiang Li, Mingsheng Ying. Generalized Region Connection Calculus, Artificial Intelligence, 2004, 160(1-2): 1-34.
[12] Yongming Li, Sanjiang Li. A Fuzzy Sets Theoretic Approach to Approximate Spatial Reasoning, IEEE Transactions on Fuzzy Systems, 2004, 12(6): 745-754.
[13] Sanjiang Li, Mingsheng Ying. Region Connection Calculus: its models and composition table, Artificial Intelligence, 2003, 145(1-2): 121-146.
