A Deterministic Distributed Algorithm for Reasoning with Connected Row-Convex Constraints

摘要：

The class of CRC constraints generalizes several tractable classes of constraints and is expressive enough to model problems in domains such as temporal reasoning, geometric reasoning, and scene labelling. This paper presents the first distributed deterministic algorithm for connected row-convex (CRC) constraints. Our distributed (partial) path consistency algorithm efficiently transforms a CRC constraint network into an equivalent constraint network, where all constraints are minimal (i.e., they are the tightest constraints) and generating all solutions can be done in a backtrack- free manner. When compared with the state-of-the-art distributed algorithm for CRC constraints, which is a randomized one, our algorithm guarantees to generate a solution for satisfiable CRC constraint networks and it is applicable to solve large networks in real distributed systems. The experimental evaluations show that our al- gorithm outperforms the state-of-the-art algorithm in both practice and theory.

This paper is a joint work with Shufeng Kong and Jae Hee Lee. It was accepted to the Sixteenth International Joint Conference on Autonomous Agents and Multi-agent Systems to be held in Sao Paulo, Brazil in 8-12 May, 2017. 

报告人简介：

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 for Quantum Software & Information (QSI), School of Software, 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