OpenAIR @ RGU >
Design and Technology >
Theses (Computing) >
Please use this identifier to cite or link to this item:
|Title: ||Hybrid algorithms for distributed constraint satisfaction.|
|Authors: ||Lee, David Alexander James|
|Supervisors: ||Arana, Ines|
|Keywords: ||Hybrid algorithms|
|Issue Date: ||Apr-2010|
|Publisher: ||The Robert Gordon University|
|Citation: ||LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y., 2008. A hybrid approach to distributed constraint satisfaction. In: D. DOCHEV, P. TRAVERSO and M. PISTORE, eds. Artificial intelligence: methodology, systems and applications. Proceedings of the 13th International Conference, AIMSA 2008. Varna, Bulgaria, September 4-6 2008. pp. 375-379.|
LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y., 2009. Multi-hyb: a hybrid algorithm for solving DisCSPs with complex local problems. In: Proceedings of 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT 2009). Milan, Italy. 15th-18th September 2009. pp. 379-382.
LEE, D., ARANA, I., AHRIZ, H. and HUI, K.-Y., 2009. A hybrid approach to solving coarse-grained DisCSPs. In: Proceedings of the Eighth International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 09). Budapest, Hungary. 10th-15th May 2009. pp. 1235-1236.
|Abstract: ||A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP which is divided
into several inter-related complex local problems, each assigned to a different agent. Thus,
each agent has knowledge of the variables and corresponding domains of its local problem
together with the constraints relating its own variables (intra-agent constraints) and
the constraints linking its local problem to other local problems (inter-agent constraints).
DisCSPs have a variety of practical applications including, for example, meeting scheduling
and sensor networks. Existing approaches to Distributed Constraint Satisfaction can
be mainly classified into two families of algorithms: systematic search and local search.
Systematic search algorithms are complete but may take exponential time. Local search
algorithms often converge quicker to a solution for large problems but are incomplete.
Problem solving could be improved through using hybrid algorithms combining the completeness
of systematic search with the speed of local search.
This thesis explores hybrid (systematic + local search) algorithms which cooperate to
solve DisCSPs. Three new hybrid approaches which combine both systematic and local
search for Distributed Constraint Satisfaction are presented: (i) DisHyb; (ii) Multi-Hyb
and; (iii) Multi-HDCS. These approaches use distributed local search to gather information
about difficult variables and best values in the problem. Distributed systematic search is
run with a variable and value ordering determined by the knowledge learnt through local
Two implementations of each of the three approaches are presented: (i) using penalties
as the distributed local search strategy and; (ii) using breakout as the distributed local
search strategy. The three approaches are evaluated on several problem classes. The
empirical evaluation shows these distributed hybrid approaches to significantly outperform
both systematic and local search DisCSP algorithms.
DisHyb, Multi-Hyb and Multi-HDCS are shown to substantially speed-up distributed
problem solving with distributed systematic search taking less time to run by using the
information learnt by distributed local search. As a consequence, larger problems can now
be solved in a more practical timeframe.|
|Appears in Collections:||Theses (Computing)|
All items in OpenAIR are protected by copyright, with all rights reserved.