报告题目：Qualitative Constraint Satisfaction Problems: An Extended Framework with Landmarks

报告时间：4月3日（星期三）下午3：00-4：30

报告地点：计算机科学学院报告厅

报告 人：李三江 副教授（澳大利亚悉尼科技大学）

报告简介：Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activity. The qualitative approach to spatial and temporal reasoning, known as Qualitative Spatial and Temporal Reasoning (QSTR), typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with spatial/temporal knowledge by solving qualitative constraints.

When formulating qualitative constraint satisfaction problems (CSPs), it is usually assumed that each variable could be “here, there and everywhere.” Practical applications such as urban planning, however, often require a variable to take its value from a certain finite domain, i.e. it is required to be ‘here or there, but not everywhere’. Entities in such a finite domain often act as reference objects and are called “landmarks” in this paper. The paper extends the classical framework of qualitative CSPs by allowing variables to take values from finite domains. The computational complexity of the consistency problem in this extended framework is examined for the five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC5, and RCC8. We show that all these consistency problems remain in NP and provide, under practical assumptions, efficient algorithms for solving basic constraints involving landmarks for all these calculi.

报告人简介：李三江，38岁，现任悉尼科技大学副教授，ARC（澳大利亚研究理事会） Future Fellow。 1996年本科毕业于陕西师范大学数学系，2001年博士毕业于四川大学数学系；2001年至2008年在清华大学计算机系工作，历任博士后(2001)，助理研究员(2003)，副研究员(2005)。2004年获德国洪堡基金会资助到德国弗赖堡大学访问18个月，任洪堡学者；2006年获首届微软青年教授奖、2008年获中创软件人才奖、2009年获 ARC Future Fellow奖，2010年获悉尼科技大学 ECR Research Excellence Award 获得者。

主要研究方向为空间推理和人工智能理论。自2001年以来他与合作者系统深入地研究了空间推理的拓扑方法，并在空间关系建模和空间约束求解等方面取得重要成果。这包括：提出一种能同时容纳空间拓扑信息的离散和连续模型的形式系统，建立了空间拓扑信息的分层表示理论；发展了复合推理方法，证明了关系模型是否对复合封闭与基于复合的推理方法是否完备无关；采用九交方法对平面区域间的拓扑关系进行了完备分类；针对著名的RCC8拓扑关系模型，设计了一个立方时间的实现算法并证明了RCC8的易处理子集的闭包也是易处理的；针对Goyal和Egenhofer提出的主方位关系模型，在国际上首次给出正确的多项式（立方）算法，在此之前这被国际同行认为是不可能的；系统研究了空间方位和拓扑关系的混合约束求解问题，给出其上一大类约束满足问题的判定方法。这些研究揭示了空间关系模型和时间区间代数在复合推理方面的重大差别，激发了国际同行对弱复合与外延性复合之间差异的研究。

这些成果主要发表在人工智能领域重要国际刊物和顶级国际会议，其中包括Artificial Intelligence Journal六篇。他主持的一项中国国家自然科学基金面上项目和参与的一项国家自然科学基金重大项目分别被评为“特优”结题项目。目前主持三项澳洲研究理事会研究项目。