李三江

副研究员

电子邮件 lisanjiang@tsinghua.edu.cn

 

教育背景

理学学士 (数学), 陕西师范大学, 中国, 1996;

理学博士 (数学), 四川大学, 成都, 中国, 2001.

 

研究领域

人工智能, 空间推理

研究概况

空间知识的表示与推理在诸如地理信息系统、机器人学、计算机视觉等领域有重要应用。我和合作者系统研究了空间推理的拓扑方法,在空间关系建模和空间约束求解方面取得一些重要成果。我们工作的一大部分是建立在著名的区域连接演算RCC之上的。

1. 广义区域连接演算。为能同时容纳离散和连续模型,我们引入了广义的区域连接演算。原RCC理论只有连续模型,但实际应用中大量采用的却都是离散模型。通过引入一些范畴算子,我们建立了离散和连续模型之间的联系,调和了这一矛盾。基于GRCC理论,我们进一步建立了空间拓扑信息的一个分层表示理论。

2. 基于关系复合的推理技术。复合推理技术最初是由Allen在时序推理研究中提出的。我们证明了任意RCC模型都不是RCC8复合表的外延性模型,而Egenhofer的9交模型在一定意义下是最大的外延性模型。这表明:一个关系模型是否对复合运算封闭与复合推理是否完备是相互独立的。这否定地回答了Bennett、Isli和 Cohn 在1997年提出的一个猜想。

3. 拓扑关系建模。将9交方法应用于复杂平面区域,我们得到了38种基本拓扑关系。通过引入简单区域的补区域,我们提出了带补的Egenhofer模型,并证明其为Duentsch提出的 RCC11关系代数的一个模型。为处理非精确甚至模糊的拓扑信息,我们提出了一个基于模糊集理论的拓扑关系模型。

4. 空间约束求解算法。我们成功解决了空间推理中几个重要的约束可满足问题。对于RCC8代数,我们设计了一个复杂度为立方的实现算法,并证明:一个易处理子集相对于关系交、关系逆、和关系弱复合运算的闭包也是易处理子集。这保证了Renz和Nebel关于RCC8计算复杂性的著名论断的正确性。为此提出的“一步扩张”概念后来被证明为关系代数可表示的一个充分条件。Skiadopoulos和Koubarakis在其2005年发表在AIJ的论文中将主方位演算的可满足问题列为一个公开问题,我们完满地解决了这一问题,并提出了一个复杂度为立方时间的判定算法。鉴于在实际应用中方位关系和拓扑关系往往是结合使用的,我们进一步研究了RCC8约束与方位约束的综合求解问题。若考虑矩形代数,我们给出混合约束的一个易处理子集;对于主方位代数,我们证明即使只考虑基本约束,此综合约束求解问题也是NP完全的。

以上研究结果主要发表在国际期刊Artificial Intelligence Journal(AIJ,5 篇)和国际会议IJCAI、AAAI、ECAI上。

 

研究课题

国家自然科学基金青年基金项目: 定性空间推理的拓扑方法 (2004-2006);

国家自然科学基金面上基金项目: 基于定性演算的空间知识表示与推理 (2007-2009).

 

奖励与荣誉

澳大利亚研究理事会: Future Fellow (2009);

中创软件人才奖 (2008);

微软青年教授奖 (2006);

德国洪堡学者 (2004).

 

学术成果

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