Main content

An Empirical Study of Distributed Constraint Satisfaction Algorithms

Show simple item record

dc.contributor.advisor Xiang, Yang
dc.contributor.author Mohamed, Younis
dc.date.accessioned 2011-09-20T13:09:54Z
dc.date.available 2011-09-20T13:09:54Z
dc.date.copyright 2011-09
dc.date.created 2011-08-23
dc.date.issued 2011-09-20
dc.identifier.uri http://hdl.handle.net/10214/3038
dc.description.abstract Many real world problems are naturally distributed, whether they are spatially, cognitively, or otherwise. Distributed problems naturally lend themselves to solutions using multi-agent paradigms. Distributed Constraint Satisfaction Problems (DisCSPs) are a class of such distributed problems. In DisCSPs, variables and constraints are distributed between agents. Most distributed algorithms, although exponential in the worst-case, can have a good performance in the average case. The main purpose of this research is to statistically assess difference between the empirical performances of major state of the art DisCSP algorithms including Multi-Sectioned Constraint Network (MSCN) based algorithms, that have never been empirically compared against other DisCSP algorithms. In this thesis, we select a set of state of the art DisCSP algorithms and compare them on randomly generated instances of binary DisCSPs with a wide range of characteristics. Distributed algorithms ADOPT, DSA, DPOP, and MSCN based algorithms were selected based on a set of high level criteria. We explore how these algorithms relatively compare with each other on a range of DisCSPs with different parameters. Their performances are evaluated according to computation time (in the form of non-concurrent computational steps or NCCCs) and communication load (in the form of number of messages as well as volume of messages). Statistical parametric tests are used to aid interpretation of the performance results. In addition, this thesis discusses privacy issues associated with these DisCSP algorithms. en_US
dc.language.iso en en_US
dc.subject Multi-Agents en_US
dc.subject Empirical Study en_US
dc.subject Multiply-Sectioned Constraint Networks (MSCNs) en_US
dc.subject Constraint Satisfaction en_US
dc.subject Distributed Constraint Satisfaction en_US
dc.title An Empirical Study of Distributed Constraint Satisfaction Algorithms en_US
dc.type Thesis en_US
dc.degree.programme Computer Science en_US
dc.degree.name Master of Applied Science en_US
dc.degree.department Department of Computing and Information Science en_US
dc.rights.license All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.


Files in this item

Files Size Format View Description
thesis.pdf 1.226Mb PDF View/Open Thesis

This item appears in the following Collection(s)

Show simple item record