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

Kong, S; Lee, JH; Li, S

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

Kong, S Lee, JH

Li, S

Permalink

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

Closed Access

	Filename	Description	Size
	p203.pdf	Published version	612.95 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Kong, S	en_US
dc.contributor.author	Lee, JH https://orcid.org/0000-0001-9840-780X	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.date.issued	2017-01-01	en_US
dc.identifier.citation	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2017, 1 pp. 203 - 211	en_US
dc.identifier.isbn	9781510855076	en_US
dc.identifier.issn	1548-8403	en_US
dc.identifier.uri	http://hdl.handle.net/10453/125769
dc.description.abstract	© 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.	en_US
dc.relation.ispartof	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS	en_US
dc.title	A deterministic distributed algorithm for reasoning with connected row-convex constraints	en_US
dc.type	Conference Proceeding
utslib.citation.volume	1	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	1	en_US

Abstract:

© 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:

http://hdl.handle.net/10453/125769