讲座题目：树保持约束求解问题

讲座人:李三江 教授

讲座时间：10:00

讲座日期：2015-4-29

地点：长安校区 ABG欧博网平台登录学术报告厅

主办单位：ABG欧博网平台登录

讲座内容：

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 work 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 work 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 scene labeling problems.

讲座人简介：

Sanjiang Li received his B.Sc. and Ph.D. degrees in mathematics from, respectively, Shaanxi Normal University, in 1996, and Sichuan University, in 2001. He is now a full professor in Centre of Quantum Computation & Intelligent Systems (QCIS), Faculty of Engineering & Information Technology, University of Technology Sydney (UTS). Before joining UTS, he worked in the Department of Computer Science and Technology, Tsinghua University from September 2001 to December 2008. He was an Alexander von Humboldt research fellow at Freiburg University from January 2005 to June 2006; held a Microsoft Research Asia Young Professorship from July 2006 to June 2009; and held an ARC Future Fellowship from January 2010 to December 2013.

His research interests are mainly in spatial reasoning and artificial intelligence. The main objective of his 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 qualitative spatial reasoning and smart information use in geographical information systems. Some of his most important work has been published in international journals like Artificial Intelligence (AIJ, 9 papers) and international conferences like IJCAI, AAAI, KR, and ECAI.