OpenAIR @ RGU >
Design and Technology >
Computing >
Theses (Computing) >

Please use this identifier to cite or link to this item:
This item has been viewed 13 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
David A J Lee PhD thesis.pdf1.71 MBAdobe PDFView/Open
Title: Hybrid algorithms for distributed constraint satisfaction.
Authors: Lee, David Alexander James
Supervisors: Arana, Ines
Ahriz, Hatem
Hui, Kit-Ying
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 search. 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.


   Disclaimer | Freedom of Information | Privacy Statement |Copyright ©2012 Robert Gordon University, Garthdee House, Garthdee Road, Aberdeen, AB10 7QB, Scotland, UK: a Scottish charity, registration No. SC013781