Concurrently Decomposable Constraint Systems

Cees Witteveen*, Wiebe van der Hoek, Nico Roos

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Abstract

In constraint satisfaction, decomposition is a common technique to split a problem in a number of parts in such a way that the global solution can be efficiently assembled from the solutions of the parts. In this paper, we study the decomposition problem from an autonomous agent perspective. Here, a constraint problem has to be solved by different agents each controlling a disjoint set of variables. Such a problem is called concurrently decomposable if each agent is (i) capable to solve its own part of the problem independently of the others, and (ii) the individual solutions always can be merged to a complete solution of the total problem. First of all, we investigate how difficult it is to decide whether or not a given constraint system and agent partitioning allows for such a concurrent decomposition. Secondly, we investigate how difficult it is to find suitable reformulations of the original constraint problem that allow for concurrent decomposition.
Original languageEnglish
Title of host publicationMultiagent System Technologies
Subtitle of host publication7th German Conference, MATES 2009, Hamburg, Germany, September 9-11, 2009. Proceedings
PublisherSpringer Verlag
Pages153-164
Number of pages12
ISBN (Electronic)978-3-642-04143-3
ISBN (Print)978-3-642-04142-6
DOIs
Publication statusPublished - 2009

Publication series

SeriesLecture Notes in Computer Science
Volume5774
ISSN0302-9743

Cite this