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 backtrackfree 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 algorithm outperforms the state-of-the-art algorithm in both practice and theory.

Authors

• Shufeng Kong Department of Computer Science, Cornell University, USA School of Software Engineering, Sun Yat-sen University, China
• Jae Hee Lee
• Sanjiang Li University of Technology Sydney

Keywords

• Connected row-convex constraints
• deterministic algorithm
• distributed algorithm
• decomposable network