A deterministic distributed algorithm for reasoning with connected row-convex constraints

Publication Type:
Conference Proceeding
Citation:
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2017, 1 pp. 203 - 211
Issue Date:
2017-01-01
Full metadata record
Files in This Item:
Filename Description Size
p203.pdfPublished version612.95 kB
Adobe PDF
© Copyright 2017, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All Rights Reserved. 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-ihe-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 statc-of-Thc-Art algorithm in both practice and theory.
Please use this identifier to cite or link to this item: